# LeetCode Insertion Sort List

147. Insertion Sort List

Sort a linked list using insertion sort.

A graphical example of insertion sort. The partial sorted list (black) initially contains only the first element in the list.
With each iteration one element (red) is removed from the input data and inserted in-place into the sorted list

Algorithm of Insertion Sort:

1. Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list.
2. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there.
3. It repeats until no input elements remain.

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4


Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

class Solution {
public:
{
while (insertPos && insertPos->val < head->val) {
insertPos = insertPos->next;
pre = pre->next;
}
tmp->next = insertPos;
pre->next = tmp;
}
}
};

class Solution {
public:
ListNode *dummy = new ListNode(INT_MIN);
while (l1 != NULL) {
l2 = l1->next;

ListNode *l3 = dummy, *l3_pre = dummy;
while (l3 != NULL && l1->val > l3->val) {
l3_pre = l3;
l3 = l3->next;
}
if (l1->val == INT_MIN) {
l1->next = dummy->next;
dummy->next = l1;
}
else {
l1->next = l3;
l3_pre->next = l1;
}

l1 = l2;
}
return dummy->next;
}
};

# LeetCode Construct Binary Tree from Inorder and Postorder Traversal

106. Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]

Return the following binary tree:

    3
/ \
9  20
/  \
15   7

class Solution {
private:
TreeNode* dfs(vector<int>& inorder, vector<int>& postorder, int inL, int inR, int postL, int postR, unordered_map<int, int>& hash)
{
if (inL > inR || postL > postR)
return NULL;
TreeNode* root = new TreeNode(postorder[postR]);
int idx = hash[root->val];
root->right = dfs(inorder, postorder, inL + 1, inR, postR – (inR – idx), postR – 1, hash);
root->left = dfs(inorder, postorder, inL, idx – 1, postL, postR – (inR – idx) – 1, hash);
return root;
}
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder)
{
if (inorder.size() == 0)
return NULL;
unordered_map<int, int> hash;
for (int i = 0; i < inorder.size(); ++i) {
hash[inorder[i]] = i;
}
return dfs(inorder, postorder, 0, inorder.size() – 1, 0, postorder.size() – 1, hash);
}
};

# LeetCode Construct Binary Tree from Preorder and Inorder Traversal

105. Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

    3
/ \
9  20
/  \
15   7

        3
/     \
9       20
/  \     /   \
1    2  15    17
• 先序遍历结果为：3, 9, 1, 2, 20, 15, 17
• 中序遍历结果为：1, 9, 2, 3, 15, 20, 17

• 先序遍历结果为：3, 9, 1, 2, 20, 15, 17
• 中序遍历结果为：1, 9, 2, 3, 15, 20, 17

class Solution {
private:
TreeNode* dfs(vector<int>& preorder, vector<int>& inorder, int preL, int preR, int inL, int inR, unordered_map<int, size_t>& hash)
{
if (preL > preR || inL > inR)
return NULL;
TreeNode* root = new TreeNode(preorder[preL]);
size_t idx = hash[root->val];
root->left = dfs(preorder, inorder, preL + 1, idx – inL + preL, inL, idx – 1, hash);
root->right = dfs(preorder, inorder, idx – inL + preL + 1, preR, idx + 1, inR, hash);
return root;
}
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)
{
if (preorder.size() == 0)
return NULL;
unordered_map<int, size_t> hash;
for (size_t i = 0; i < inorder.size(); ++i) {
hash[inorder[i]] = i;
}
return dfs(preorder, inorder, 0, preorder.size() – 1, 0, inorder.size() – 1, hash);
}
};

# LeetCode Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
/ \
9  20
/  \
15   7


return its zigzag level order traversal as:

[
[3],
[20,9],
[15,7]
]


talk is cheap, show you the code!

class Solution {
public:
vector<vector<int> > zigzagLevelOrder(TreeNode* root)
{
vector<vector<int> > ans;
if (!root)
return ans;
bool left2right = true;
stack<TreeNode*> stk;
stk.push(root);
while (!stk.empty()) {
stack<TreeNode*> stk2;
vector<int> cand;
size_t n = stk.size();
for (size_t i = 0; i < n; ++i) {
TreeNode* top = stk.top();
stk.pop();
if (!top)
continue;
cand.push_back(top->val);
if (left2right) {
stk2.push(top->left);
stk2.push(top->right);
}
else {
stk2.push(top->right);
stk2.push(top->left);
}
}
left2right = !left2right;
if (!cand.empty())
ans.push_back(cand);
stk = stk2;
}
return ans;
}
};

class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> ans;
if (root == NULL)return ans;
deque<TreeNode*> q;
q.push_back(root);
bool left2right = true;
while (!q.empty()) {
vector<int> cur;
if (left2right) {
int n = q.size();
for (int i = 0; i < n; ++i) {
cur.push_back(q[i]->val);
}
ans.push_back(cur);
for (int i = n - 1; i >= 0; --i) {
TreeNode* tn = q.back();
q.pop_back();
if (tn->right)q.push_front(tn->right);
if (tn->left)q.push_front(tn->left);
}
left2right = false;
}
else {
int n = q.size();
for (int i = n - 1; i >= 0; --i) {
cur.push_back(q[i]->val);
}
ans.push_back(cur);
for (int i = 0; i < n; ++i) {
TreeNode* tn = q.front();
q.pop_front();
if (tn->left)q.push_back(tn->left);
if (tn->right)q.push_back(tn->right);
}
left2right = true;
}
}
return ans;
}
};

# LeetCode Intersection of Two Linked Lists

160. Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

begin to intersect at node c1.

Example 1:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
Output: Reference of the node with value = 8
Input Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,0,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.

Example 2:

Input: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Reference of the node with value = 2
Input Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [0,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.


Example 3:

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: null
Input Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.


Notes:

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1) memory.

class Solution {
public:
{
int len1 = 0, len2 = 0;
while (h1) {
++len1;
h1 = h1->next;
}
while (h2) {
++len2;
h2 = h2->next;
}
if (len1 > len2) {
while (len1 > len2) {
h1 = h1->next;
–len1;
}
}
else if (len2 > len1) {
while (len2 > len1) {
h2 = h2->next;
–len2;
}
}
while (h1 && h2 && h1 != h2) {
h1 = h1->next;
h2 = h2->next;
}
if (!h1 || !h2)
return NULL;
else
return h1;
}
};

class Solution {
public:
{
return NULL;
ListNode *tail1 = NULL, *tail2 = NULL;
while (true) {
if (h1 == NULL)
if (h2 == NULL)
if (h1->next == NULL)
tail1 = h1;
if (h2->next == NULL)
tail2 = h2;
if (tail1 != NULL && tail2 != NULL && tail1 != tail2)
return NULL;
if (h1 == h2)
return h1;
h1 = h1->next;
h2 = h2->next;
}
}
};

class Solution {
public:
bool la_changed = false, lb_changed = false;
while (la != lb) {
la = la->next;
lb = lb->next;
if (la == NULL) {
if (la_changed)return NULL;
else {
la_changed = true;
}
}
if (lb == NULL) {
if (lb_changed)return NULL;
else {
lb_changed = true;
}
}
}
return la;
}
};

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

1. Only one letter can be changed at a time.
2. Each transformed word must exist in the word list.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• You may assume no duplicates in the word list.
• You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output: 5

Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.


Example 2:

Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Output: 0

Explanation: The endWord "cog" is not in wordList, therefore no possibletransformation.

typedef struct Item {
string cur;
string used;
int step;
Item(string c, string u, int s)
: cur(c)
, used(u)
, step(s){};
};
class Solution {
public:
bool differOne(const string& s1, const string& s2)
{
int cnt = 0;
for (size_t i = 0; i < s1.size(); ++i) {
if (s1[i] != s2[i]) {
++cnt;
if (cnt > 1)
return false;
}
}
return cnt == 1;
}
int ladderLength(string beginWord, string endWord, vector<string>& wordList)
{
size_t n = wordList.size();
queue<Item> q;
Item it(beginWord, string(n, ‘0’), 1);
q.push(it);
while (!q.empty()) {
Item t = q.front();
q.pop();
if (t.cur == endWord)
return t.step;
for (size_t i = 0; i < n; ++i) {
if (t.used[i] == ‘0’&& differOne(t.cur, wordList[i])) {
string newUsed = t.used;
newUsed[i] = ‘1’;
Item tmp(wordList[i], newUsed, t.step + 1);
q.push(tmp);
}
}
}
return 0;
}
};

class Solution {
public:
bool differOne(const string& s1, const string& s2)
{
int cnt = 0;
for (size_t i = 0; i < s1.size(); ++i) {
if (s1[i] != s2[i]) {
++cnt;
if (cnt > 1)
return false;
}
}
return cnt == 1;
}
int ladderLength(string beginWord, string endWord, vector<string>& wordList)
{
size_t n = wordList.size();
queue<string> q;
q.push(beginWord);
int step = 1;
while (!q.empty()) {
size_t len = q.size();
for (size_t i = 0; i < len; ++i) {
string t = q.front();
q.pop();
if (t == endWord)
return step;
for (size_t j = 0; j < wordList.size(); ++j) {
if (wordList[j] != "" && differOne(t, wordList[j])) {
q.push(wordList[j]);
wordList[j] = "";
}
}
}
++step;
}
return 0;
}
};

class Solution {
public:
bool IsConnect(const string &a, const string &b) {
int diff = 0, n = a.size();
for (int i = 0; i < n; ++i) {
if (a[i] != b[i]) {
++diff;
if (diff > 1)return false;
}
}
return diff == 1;
}
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
int n = wordList.size();
if (n == 0)return 0;

vector<int> visited(n, 0);
queue<string> q;
q.push(beginWord);
int ans = 0;
while (!q.empty()) {
++ans;
int m = q.size();
for (int i = 0; i < m; ++i) {
string cur = q.front();
if (cur == endWord)return ans;
q.pop();
for (int j = 0; j < n; ++j) {
if (visited[j] == 0 && IsConnect(cur, wordList[j])) {
visited[j] = 1;
q.push(wordList[j]);
}
}
}
}
return 0;
}
};

# LeetCode Word Search

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example:

board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.


Constraints:

• board and word consists only of lowercase and uppercase English letters.
• 1 <= board.length <= 200
• 1 <= board[i].length <= 200
• 1 <= word.length <= 10^3

class Solution {
private:
bool dfs(vector<vector<char> >& board, vector<vector<char> >& mark, int row, int col, string& word, int step)
{
if (board[row][col] != word[step])
return false;
if (step == word.size() – 1)
return true;
mark[row][col] = 1;
if (row – 1 >= 0 && mark[row – 1][col] == 0) {
bool ans = dfs(board, mark, row – 1, col, word, step + 1);
if (ans)
return true;
}
if (row + 1 < board.size() && mark[row + 1][col] == 0) {
bool ans = dfs(board, mark, row + 1, col, word, step + 1);
if (ans)
return true;
}
if (col – 1 >= 0 && mark[row][col – 1] == 0) {
bool ans = dfs(board, mark, row, col – 1, word, step + 1);
if (ans)
return true;
}
if (col + 1 < board[0].size() && mark[row][col + 1] == 0) {
bool ans = dfs(board, mark, row, col + 1, word, step + 1);
if (ans)
return true;
}
mark[row][col] = 0;
return false;
}
public:
bool exist(vector<vector<char> >& board, string word)
{
if (word.size() == 0)
return true;
int m = board.size();
if (m == 0)
return false;
int n = board[0].size();
if (n == 0)
return false;
vector<vector<char> > mark(m, vector<char>(n, 0));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (board[i][j] == word[0] && dfs(board, mark, i, j, word, 0))
return true;
}
}
return false;
}
};

# LeetCode Insert Interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]


Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

class Solution {
public:
vector<Interval> insert(vector<Interval>& intervals, Interval newInterval)
{
vector<Interval> ans;
int i = 0, n = intervals.size();
while (i < n && intervals[i].end < newInterval.start)
ans.push_back(intervals[i++]);
while (i < n && newInterval.end >= intervals[i].start) {
newInterval.start = min(newInterval.start, intervals[i].start);
newInterval.end = max(newInterval.end, intervals[i].end);
++i;
}
ans.push_back(newInterval);
while (i < n)
ans.push_back(intervals[i++]);
return ans;
}
};

# LeetCode Merge Intervals

56. Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].


Example 2:

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

bool comp(const Interval& i, const Interval& j)
{
return (i.start < j.start) || ((i.start == j.start) && (i.end < j.end));
}
class Solution {
public:
vector<Interval> merge(vector<Interval>& intervals)
{
if (intervals.size() == 0)
return vector<Interval>();
sort(intervals.begin(), intervals.end(), comp);
vector<Interval> ans = { intervals[0] };
for (int i = 1; i < intervals.size(); ++i) {
if (intervals[i].start <= ans.back().end) {
ans.back().end = max(ans.back().end, intervals[i].end);
}
else {
ans.push_back(intervals[i]);
}
}
return ans;
}
};

class Solution {
public:
bool IsOverlap(const pair<int, int>& interval1, const pair<int, int>& interval2) {
return interval1.second >= interval2.first;
}
vector<vector<int>> merge(vector<vector<int>>& intervals) {
vector<pair<int, int>> intervals2;
for (int i = 0; i < intervals.size(); ++i) {
intervals2.push_back(make_pair(intervals[i][0], intervals[i][1]));
}
sort(intervals2.begin(), intervals2.end());
vector<vector<int>> ans;
stack<pair<int, int>> stk;
for (int i = 0; i < intervals2.size(); ++i) {
if (stk.empty()) {
stk.push(intervals2[i]);
}
else {
pair<int, int> top = stk.top();
stk.pop();
if (IsOverlap(top, intervals2[i])) {
stk.push(make_pair(top.first, max(top.second, intervals2[i].second)));
}
else {
ans.push_back({ top.first,top.second });
stk.push({ intervals2[i].first,intervals2[i].second });
}
}
}
if (!stk.empty())ans.push_back({ stk.top().first,stk.top().second });
return ans;
}
};

# LeetCode Jump Game II

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

Example:

Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
Jump 1 step from index 0 to 1, then 3 steps to the last index.

Note:

You can assume that you can always reach the last index.

class Solution {
public:
int jump(vector<int>& nums)
{
int n = nums.size();
if (n <= 1)
return 0;
int maxJump = n – 1;
vector<int> dp(n, 0);
for (int i = n – 2; i >= 0; –i) {
int curMinJump = maxJump;
for (int j = i + 1; j <= nums[i] + i && j < n; ++j) {
curMinJump = min(curMinJump, dp[j] + 1);
}
dp[i] = curMinJump;
}
return dp[0];
}
};

class Solution {
public:
int jump(vector<int>& nums)
{
int n = nums.size();
if (n <= 1)
return 0;
int maxJump = n – 1;
vector<int> dp(n, 0), pre(n, 0);
for (int i = n – 2; i >= 0; –i) {
int curMinJump = maxJump, k = 0;
for (int j = i + 1; j <= nums[i] + i && j < n; ++j) {
if (dp[j] + 1 < curMinJump) {
curMinJump = dp[j] + 1;
k = j;
}
}
dp[i] = curMinJump;
pre[k] = i; // 从i跳到k能获得最小跳数
}
return dp[0];
}
};

class Solution {
public:
int jump(vector<int>& nums)
{
int jumps = 0, curEnd = 0, curFarthest = 0;
for (int i = 0; i < nums.size() – 1; ++i) {
curFarthest = max(curFarthest, i + nums[i]);
if (i == curEnd) {
curEnd = curFarthest;
++jumps;
if (curEnd >= nums.size() – 1)
break;
}
}
return jumps;
}
};

class Solution {
public:
int jump(vector<int>& nums) {
int n = nums.size();
vector<int> steps(n, INT_MAX);
steps[0] = 0;
for (int i = 0; i < n; ++i) {
for (int j = 1; j <= nums[i]; ++j) {
int target = i + j;
if (target < n) {
steps[target] = min(steps[target], steps[i] + 1);
}
else {
break;
}
}
}
return steps[n - 1];
}
};

2
3,1
1,4

class Solution {
public:
int jump(vector<int>& nums) {
int level = 0, current_fastest = 0, next_fastest = 0;
int n = nums.size(), i = 0;
if (n == 1)return 0;
while (true) {
++level;
while (i <= current_fastest && i < n) {
next_fastest = max(next_fastest, i + nums[i]);
++i;
}
if (next_fastest >= n - 1)return level;
current_fastest = next_fastest;
}
return 0;
}
};


class Solution {
public:
int jump(vector<int>& nums) {
int n = nums.size();
int step = 0, pre_max = 0, next_max = 0;
for(int i = 0; i < n; ++i) {
if(i > pre_max) {
++step;
pre_max = next_max;
}
next_max = max(next_max, i + nums[i]);
}
return step;
}
};