Leetcode 101-200

101. Symmetric Tree (Easy)¶

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:
    1
   / \
  2   2
 / \ / \
3  4 4  3
检查二叉树是否对称

思路

递归比较即可

bool helper(TreeNode* node1, TreeNode* node2) {
    if (node1 == NULL && node2 == NULL) return true;
    if (node1 == NULL || node2 == NULL) return false;
    return (node1->val == node2 ->val) && helper(node1->left, node2->right)
        && helper(node1->right, node2->left);
}
bool isSymmetric(TreeNode* root) {
    return !root ? true : helper(root->left, root->right);
}

102. Binary Tree Level Order Traversal (Medium)¶

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example: Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
return its level order traversal as:
[
  [3],
  [9,20],
  [15,7]
]
层次遍历二叉树

思路

BFS来遍历即可

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int> > result;
    if (!root) return result;
    deque<TreeNode*> q;
    q.push_back(root);
    while (!q.empty()) {
        result.push_back(vector<int>());
        int size = q.size();
        while (size --) {
            TreeNode* node = q.front();
            if (node->left != NULL) q.push_back(node->left);
            if (node->right != NULL) q.push_back(node->right);
            q.pop_front();
            result.back().push_back(node->val);
        }
    }
    return result;
}

103. Binary Tree Zigzag Level Order Traversal (Medium)¶

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).

左->右、右->左逐层遍历树
Given binary tree
    3
   / \
  9  20
    /  \
   15   7
return
[
  [3],
  [20,9],
  [15,7]
]

思路

还是用deque来进行bfs，注意下扫描顺序即可

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    vector<vector<int> > result;
    if (root == nullptr) return result;
    deque<TreeNode*> q;
    #define L2R 0
    #define R2L 1
    bool direction = R2L;
    q.push_back(root);
    while (!q.empty()) {
        result.push_back(vector<int>());
        int size = q.size();
        for (int i = size - 1; i >= 0; i --) {
            TreeNode* node = q[i];
            TreeNode* n1 = (direction == R2L) ? node->right : node->left;
            TreeNode* n2 = (direction == R2L) ? node->left : node->right;
            if (n1 != nullptr) q.push_back(n1);
            if (n2 != nullptr) q.push_back(n2);
        }
        direction = 1 - direction;
        while (size --) {
            result.back().push_back(q.front()->val);
            q.pop_front();
        }
    }
    return result;
}

104. Maximum Depth of Binary Tree (Easy)¶

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
return its depth = 3. 求二叉树的最大深度

递归

int maxDepth(TreeNode* root) {
    if (root == nullptr) return 0;
    return 1 + max(maxDepth(root->left), maxDepth(root->right));
}

BFS

int maxDepth(TreeNode* root) {
    if (root == NULL) return 0;
    deque<TreeNode*> q;
    q.push_back(root);
    int result = 0;
    while (!q.empty()) {
        result ++;
        int size = q.size();
        while (size --) {
            TreeNode* node = q.front();
            if (node->left != NULL) q.push_back(node->left);
            if (node->right != NULL) q.push_back(node->right);
            q.pop_front();
        }
    }
    return result;
}

105. Construct Binary Tree from Preorder and Inorder Traversal (Medium)¶

Given preorder and inorder traversal of a tree, construct the binary 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
从前序和中序遍历恢复出二叉树

思路

前序遍历，即root|leftTree|rightTree的结构，而中序遍历为leftTree|root|rightTree的结构。前序第一个点即为根节点，在中序中查找，即可分割成left和right两部分，递归求解即可，以下代码时间为24ms(86.30%)。可以改进为不递归，用stack来求解，留作TODO吧

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    return helper(preorder, 0, inorder, 0, preorder.size());
}
TreeNode* helper(const vector<int>& preorder, int pp, const vector<int>& inorder, int ip, int len) {
    if (len == 0) return nullptr;
    int head = preorder[pp], rank = ip;
    while (inorder[rank] != head) rank ++;
    TreeNode* root = new TreeNode(head);
    root->left = helper(preorder, pp + 1, inorder, ip, rank - ip);
    root->right = helper(preorder, pp + rank - ip + 1, inorder, rank + 1, len - 1 - rank + ip);
    return root;
}

106. Construct Binary Tree from Inorder and Postorder Traversal (Medium)¶

Given inorder and postorder traversal of a tree, construct the binary tree.
inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]
return
    3
   / \
  9  20
    /  \
   15   7
从中序和后序恢复二叉树

思路

递归来做，时间为24ms (80.32%)

可以用栈来迭代，时间可以更短

TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
    return helper(inorder, 0, postorder, 0, inorder.size());
}
TreeNode* helper(const vector<int>& inorder, int ip, const vector<int>& postorder, int pp, int len) {
    if (len == 0) return nullptr;
    TreeNode* root = new TreeNode(postorder[pp + len - 1]);
    int head = postorder[pp + len - 1], rank = ip;
    while (inorder[rank] != head) rank ++;
    root->left = helper(inorder, ip, postorder, pp, rank - ip);
    root->right = helper(inorder, rank + 1, postorder, rank - ip + pp, len - 1 + ip - rank);
    return root;
}

107. Binary Tree Level Order Traversal II (Easy)¶

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).
    3
   / \
  9  20
    /  \
   15   7
return
[
  [15,7],
  [9,20],
  [3]
]
即从叶子节点开始层次遍历

思路

正常进行层次遍历，最后再倒序插入vector即可

vector<vector<int>> levelOrderBottom(TreeNode* root) {
    vector<vector<int> > result;
    if (!root) return result;
    deque<TreeNode*> q;
    q.push_back(root);
    while (!q.empty()) {
        result.push_back(vector<int>());
        int size = q.size();
        while (size --) {
            TreeNode* node = q.front();
            if (node->left != NULL) q.push_back(node->left);
            if (node->right != NULL) q.push_back(node->right);
            q.pop_front();
            result.back().push_back(node->val);
        }
    }
    vector<vector<int> > reverseResult;
    for (int i = result.size() - 1; i >= 0; i --) reverseResult.push_back(result[i]);
    return reverseResult;
}

108. Convert Sorted Array to Binary Search Tree (Easy)¶

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
Given the sorted array: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
      0
     / \
   -3   9
   /   /
 -10  5

思路

迭代即可

TreeNode* recursion(vector<int>& nums, int b, int e) {
    if (e < b) return nullptr;
    TreeNode* root = new TreeNode(nums[(b + e)/2]);
    root->left = recursion(nums, b, (b+e)/2-1);
    root->right = recursion(nums, (b+e)/2+1, e);
    return root;
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
    return recursion(nums, 0, nums.size() - 1);
}

109. Convert Sorted List to Binary Search Tree (Medium)¶

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
Given the sorted array: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
      0
     / \
   -3   9
   /   /
 -10  5

思路

同样迭代即可，需要注意的是中间节点的分割，除过双指针外还要维持一个保存后面指针的前继

TreeNode* sortedListToBST(ListNode* head) {
    if (head == nullptr) return nullptr;
    ListNode *first = head, *second = head, *prev = nullptr;
    while (first != nullptr && first->next != nullptr) {
        first = first->next->next;
        prev = second;
        second = second->next;
    }
    if (prev != nullptr) prev->next = nullptr;
    TreeNode* root = new TreeNode(second->val);
    if (head != second) root->left = sortedListToBST(head);
    root->right = sortedListToBST(second->next);
    return root;
}

110. Balanced Binary Tree (Easy)¶

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
    3
   / \
  9  20
    /  \
   15   7
return true

即判断一颗二叉树是不是平衡树

思路

迭代即可，一个小技巧是通过引用获取二叉树高度，一次迭代即可完成，控制迭代次数

bool recursion(TreeNode* root, int& depth) {
    if (root == nullptr) return true;
    depth = 1;
    int leftDepth = 0, rightDepth = 0;
    if (!recursion(root->left, leftDepth)) return false;
    if (!recursion(root->right, rightDepth)) return false;
    if ((leftDepth - rightDepth) * (leftDepth - rightDepth) > 1) return false;
    depth += max(leftDepth, rightDepth);
    return true;
}
bool isBalanced(TreeNode* root) {
    int depth = 0;
    return recursion(root, depth);
}

111. Minimum Depth of Binary Tree (Easy)¶

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf is a node with no children.

找一棵二叉树最短高度

思路

宽搜即可，要注意

用queue而不是deque，会快一些
depth是到叶子节点最短长度，而叶子节点左右孩子都要是空

int minDepth(TreeNode* root) {
    if (root == nullptr) return 0;
    queue<TreeNode*> q;
    q.push(root);
    int depth = 1;
    while (!q.empty()) {
        int size = q.size();
        while (size --) {
            TreeNode* node = q.front();
            q.pop();
            if (node->right == nullptr && node->left == nullptr) return depth;
            if (node->left != nullptr) q.push(node->left);
            if (node->right != nullptr) q.push(node->right);
        }
        depth ++;
    }
    return 0;
}

112. Path Sum (Easy)¶

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

Given the below binary tree and sum = 22,
      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1
return true

即看有没有一条从root到leaf的路径，val和正好是sum

思路

递归即可

bool hasPathSum(TreeNode* root, int sum) {
    if (root == nullptr) return false;
    if (root->left == nullptr && root->right == nullptr && root->val == sum)
        return true;
    return hasPathSum(root->left, sum-root->val) || hasPathSum(root->right, sum-root->val);
}

113. Path Sum II (Medium)¶

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

Note: A leaf is a node with no children.

和上题一样，不过要返回所有方案

思路

递归即可

void recursion(vector<vector<int>>& result, vector<int>& temp, TreeNode* root, int sum) {
    if (root == nullptr) return;
    int v = root->val;
    temp.push_back(v);
    if (root->left == nullptr && root->right == nullptr && v == sum)
        result.push_back(temp);
    recursion(result, temp, root->left, sum-v);
    recursion(result, temp, root->right, sum-v);
    temp.pop_back();   
}
vector<vector<int>> pathSum(TreeNode* root, int sum) {
    vector<vector<int>> result;
    vector<int> temp;
    recursion(result, temp, root, sum);
    return result;
}

114. Flatten Binary Tree to Linked List (Medium)¶

Given a binary tree, flatten it to a linked list in-place.

For example, given the following tree:
    1
   / \
  2   5
 / \   \
3   4   6
The flattened tree should look like:
1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

解法一递归

TreeNode* recursion(TreeNode* root) {
    if (root == NULL) return NULL;
    TreeNode* left = recursion(root->left);
    TreeNode* right = recursion(root->right);
    root->left = NULL;
    root->right = left;
    TreeNode* temp = root;
    while (temp->right != NULL) temp = temp->right;
    temp->right = right;
    return root;
}
void flatten(TreeNode* root) {
    recursion(root);
}

解法二栈

在用栈进行中序遍历基础上，每次入栈就把节点加在右边，最后覆盖root即可

void flatten(TreeNode* root) {
    if (root == NULL) return;
    stack<TreeNode*> s;
    TreeNode* head = new TreeNode(root->val);
    TreeNode* result = head;
    s.push(root);
    while (!s.empty()) {
        if (s.top()->left != NULL) {
            s.push(s.top()->left);
            TreeNode* node = new TreeNode(s.top()->val);
            head->right = node;
            head = node;
        }
        else {
            while (!s.empty()) {
                TreeNode* node = s.top();
                s.pop();
                if (node->right != NULL) {
                    s.push(node->right);
                    TreeNode* node = new TreeNode(s.top()->val);
                    head->right = node;
                    head = node;
                    break;
                }
            }
        }
    }
    *root = *result;
}

解法三

最快的一种解法，每次将左子树移到右边，示例如下

     1                         1                              1
  2     3         --->           2               -->            2
4   5      6                    4  5                              4
                                     3                              5
                                       6                              3
                                                                        6

void flatten(TreeNode* root) {
    while (root != NULL) {
        if (root->left != NULL) {
            TreeNode* r = root->right;
            root->right = root->left;
            root->left = NULL;
            TreeNode* temp = root->right;
            while (temp->right != NULL) temp = temp->right;
            temp->right = r;
        }
        root = root->right;
    }
}

115. Distinct Subsequences (Hard)¶

Given a string S and a string T, count the number of distinct subsequences of S which equals T.
Input: S = "rabbbit", T = "rabbit"
Output: 3
Explanation:
As shown below, there are 3 ways you can generate "rabbit" from S.
(The caret symbol ^ means the chosen letters)
rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^
给两个字符串S和T，求S子串中与T相同个数

思路

动态规划，dp[i][j]表示S前i位的子串中，与T前j位相同个数，转移方程为

dp[i][j] = dp[i-1][j-1] + dp[i-1][j] if S[i] == T[j] else dp[i-1][j]

用long long数组代替vector，然后只保留一维数组，时间和空间会有改进

int numDistinct(string s, string t) {
    int n = s.size(), m = t.size();
    if (n == 0 || m == 0 || n < m) return 0;
    // long long dp[n]();
    long long *dp = new long long[n]();
    // vector<vector<long long>> dp(n, vector<long long>(m, 0));
    for (int i = 0; i < n; i ++) {
        if (i > 0) dp[i] += dp[i-1];
        if (s[i] == t[0]) dp[i] ++;
    }
    for (int i = 1; i < m; i ++) {
        int prev = dp[i - 1];
        for (int j = i; j < n; j ++) {
            int temp = dp[j];
            dp[j] = 0;
            if (s[j] == t[i]) dp[j] += prev;
            if (j - 1 >= i) dp[j] += dp[j-1];
            prev = temp;
        }
    }
    return dp[n-1];
}

116. Populating Next Right Pointers in Each Node （Medium）¶

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:
struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}
Po ulate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

即一棵完整二叉树，将每层都连接起来，如下图

思路

层次遍历即可

Node* connect(Node* root) {
    if (root == nullptr) return nullptr;
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        int size = q.size();
        Node* prev = nullptr;
        while (size --) {
            Node* node = q.front();
            q.pop();
            if (node->left == nullptr) return root;
            if (prev != nullptr) prev->next = node->left;
            node->left->next = node->right;
            prev = node->right;
            q.push(node->left);
            q.push(node->right);
        }
    }
    return root;
}

117. Populating Next Right Pointers in Each Node II (Medium)¶

和116一样，区别在于不是完整二叉树，如下图

思路

同样层次遍历即可

Node* connect(Node* root) {
    if (root == nullptr) return nullptr;
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        int size = q.size();
        Node* prev = nullptr;
        while (size --) {
            Node* node = q.front();
            q.pop();
            if (node->left == nullptr) {
                if (node->right == nullptr) continue;
                if (prev != nullptr) prev->next = node->right;
                prev = node->right;
            } else {
                q.push(node->left);
                if (prev != nullptr) prev->next = node->left;
                node->left->next = node->right;
                prev = (node->right == nullptr) ? node->left : node->right;
            }
            if (node->right != nullptr) q.push(node->right);
        }
    }
    return root;
}

118. Pascal's Triangle (Easy)¶

Given a non-negative integer numRows, generate the first numRows of Pascal's triangle.
Input: 5
Output:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

思路

求解杨辉三角，逐层加即可

vector<vector<int>> generate(int numRows) {
    vector<vector<int>> result;
    for (int i = 0; i < numRows; i ++) {
        vector<int> temp = {1};
        for (int j = 1; j < i; j ++) temp.push_back(result[i-1][j] + result[i-1][j-1]);
        if (i > 0) temp.push_back(1);
        result.push_back(temp);
    }
    return result;
}

119. Pascal's Triangle II (Easy)¶

求杨辉三角第n层

思路

同样逐层加即可

vector<int> getRow(int numRows) {
    vector<int> result;
    for (int i = 0; i <= numRows; i ++) {
        vector<int> temp = {1};
        for (int j = 1; j < i; j ++) temp.push_back(result[j] + result[j-1]);
        if (i > 0) temp.push_back(1);
        result = temp;
    }
    return result;
}

120. Triangle (Medium)¶

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

三角形，从顶向下找一条和最小的道路

思路

主要就是对adjacent的判定，就是i-1和i，对越界情况判断一下，然后累加就行

int minimumTotal(vector<vector<int>>& triangle) {
    int n = triangle.size();
    if (n == 0) return 0;
    vector<int> result(n, 0);
    result[0] = triangle[0][0];
    for (int i = 1; i < n; i ++) {
        vector<int> temp(n, 0);
        for (int j = 0; j <= i; j ++) {
            int r0 = (j == 0) ? j : j - 1;
            int r1 = (j < i) ? j : i - 1;
            temp[j] = min(result[r0], result[r1]) + triangle[i][j];
        }
        result = temp;
    }
    int mn = result[0];
    for (auto n : result) mn = min(n, mn);
    return mn;
}

121. Best Time to Buy and Sell Stock (Easy)¶

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6)
profit = 6-1 = 5.
Not 7-1 = 6, as selling price needs to be larger than buying price.

思路

扫描一遍，记录差值即可

int maxProfit(vector<int>& prices) {
    if (prices.size() <= 1) return 0;
    int mx = 0, mn = prices[0];
    for (int i = 1; i < prices.size(); i ++) {
        mx = max(prices[i]-mn, mx);
        mn = min(mn, prices[i]);
    }
    return mx;
}

122. Best Time to Buy and Sell Stock II (Easy)¶

n天股票价格，可以无限买卖，问最大profit

思路

将所有前一天价格小于后一天的delta加起来即可

int maxProfit(vector<int>& prices) {
    int profit = 0;
    for (int i = 0; i < prices.size(); i ++)
        if (i > 0 && prices[i] > prices[i-1])
            profit += (prices[i] - prices[i-1]);
    return profit;
}

123. Best Time to Buy and Sell Stock III (Hard)¶

有n天的股票价格数据，最多只能交易两次，求最大profit

必须先买后卖，但可以在同一天先卖再买
Input: [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3)
profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.

思路

因为可以同天买卖，所以对每天，记录在这天及之前交易所得到的最大收益，再记录这天开始交易得到的最大收益，然后扫描一遍，将每天的这两个值相加，最大值即为答案

这天为止交易最大收益，从左向右扫描即可得到

这天开始最大收益，从右向左扫描即可得到

int maxProfit(vector<int>& prices) {
    if (prices.size() < 2) return 0;
    int n = prices.size();
    vector<int> v1(n, 0), v2(n, 0);
    int mn = prices[0], mx = 0;
    for (int i = 1; i < n; i ++) {
        mx = max(mx, prices[i] - mn);
        v1[i] = mx;
        mn = min(prices[i], mn);
    }
    mn = prices[prices.size()-1], mx = 0;
    for (int i = n - 1; i >= 0; i --) {
        mx = max(mx, mn - prices[i]);
        v2[i] = mx;
        mn = max(mn, prices[i]);
    }
    int profit = 0;
    for (int i = 1; i < prices.size(); i ++)
        profit = max(profit, v1[i] + v2[i]);
    return profit;
}

124. Binary Tree Maximum Path Sum (Hard)¶

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.
Input: [1,2,3]
       1
      / \
     2   3
Output: 6
二叉树中最大路径和，至少包含一个节点

思路

这里要注意的是因为是路径，所以除过最终根节点外，其余点只能选择加左节点或右节点

递归来解，这里recursion返回的是只加一个孩子的最大值，这里也可以不选，即采用0，但同时引用一个mx来在过程中计算最大路径，即每次尝试把left和right和val加在一起，更新mx

int recursion(TreeNode* root, int& mx) {
    if (root == nullptr) return 0;
    int left = recursion(root->left, mx);
    int right = recursion(root->right, mx);
    int val = root->val;
    if (left > 0) val += left;
    if (right > 0) val += right;
    mx = max(val, mx);
    return max(0, max(max(left, right), 0) + root->val);
}
int maxPathSum(TreeNode* root) {
    if (root == nullptr) return 0;
    int mx = root->val;
    recursion(root, mx);
    return mx;
}

125. Valid Palindrome (Easy)¶

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
Input: "A man, a plan, a canal: Panama"
Output: true
即看一个字符串数字字母部分是否是回文串，忽略字母大小写

思路

双指针比较即可

bool isPalindrome(string s) {
    int l = 0, r = s.size() - 1;
    while (l < r) {
        while (l < s.size() &&
               !((s[l] >= 'a' && s[l] <= 'z') || (s[l] >= 'A' && s[l] <= 'Z')
                 || (s[l] >= '0' && s[l] <= '9'))) l ++;
        while (r >= 0 && !((s[r] >= 'a' && s[r] <= 'z') ||
            (s[r] >= 'A' && s[r] <= 'Z') || (s[r] >= '0' && s[r] <= '9'))) r --;
        if (l >= r) return true;
        if (s[l] >= 'A' && s[l] <= 'Z') s[l] += int('a' - 'A');
        if (s[r] >= 'A' && s[r] <= 'Z') s[r] += int('a' - 'A');
        if (s[l] != s[r]) return false;
        l ++; r --;
    }
    return true;
}

126. Word Ladder II (Hard)¶

Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

Only one letter can be changed at a time

Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
Output:
[
  ["hit","hot","dot","dog","cog"],
  ["hit","hot","lot","log","cog"]
]
从beginWord起，每次只变换一个位置的字母，一直到endWord，而且保证每个word都在wordList里

思路

同样是粗暴的BFS，不过改为记录path，这里有个点是从beginWord起，一个单词在某层level被加入队列后，之后不会再次加入，因此可以从记录单词存不存在的unordered_set里erase掉

运行时间有点长，420 ms (53.35%)

vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
    vector<vector<string>> result;
    unordered_set<string> dict(wordList.begin(), wordList.end());
    if (!dict.count(endWord)) return result;
    if (dict.count(beginWord)) dict.erase(beginWord);

    vector<string> path = {beginWord};
    queue<vector<string>> q;
    q.push(path);
    bool reachEnd = false;
    while (!q.empty() && !reachEnd) {
        int size = q.size();
        unordered_set<string> words;
        while (size --) {
            vector<string> path = q.front();
            q.pop();
            string word = path.back();
            for (auto& s : word) {
                char prev = s;
                for (char a = 'a'; a <= 'z'; a ++) {
                    s = a;
                    if (dict.count(word)) {
                        words.insert(word);
                        path.push_back(word);
                        if (word == endWord) {
                            result.push_back(path);
                            reachEnd = true;
                        }
                        q.push(path);
                        path.pop_back();
                    }
                }
                s = prev;
            }
        }
        for (auto word : words) dict.erase(word);
    }
    return result;
}

127. Word Ladder (Medium)¶

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:

Only one letter can be changed at a time. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
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.
即从beginWord开始，每次换一个字母，一直变到endWord为止

思路

比较简单粗暴的BFS，用一个unorder_set来记录单词在不在，然后对每一个单词进行26*size的枚举，如果在就加入队列，同时从set中删除该元素

int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    unordered_set<string> set(wordList.begin(), wordList.end());
    if (!set.count(endWord)) return 0;
    queue<string> q;
    q.push(beginWord);
    int length = 1;
    while (!q.empty()) {
        int size = q.size();
        while (size --) {
            string word = q.front();
            q.pop();
            if (word == endWord) return length;
            for (auto& s : word) {
                char prev = s;
                for (char a = 'a'; a <= 'z'; a ++) {
                    if (a == prev) continue;
                    s = a;
                    if (set.count(word)) {
                        q.push(word);
                        set.erase(word);
                    }
                }
                s = prev;
            }
        }
        length ++;
    }
    return 0;
}

128. Longest Consecutive Sequence (Hard)¶

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.
Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

思路

用hashmap来保存一个数前后最长连续数，这里要注意的是只要保持两边正确即可，代码如下

int longestConsecutive(vector<int>& nums) {
    int res = 0;
    unordered_map<int, int> m;
    for (int num : nums) {
        if (m.count(num)) continue;
        int left = m.count(num - 1) ? m[num - 1] : 0;
        int right = m.count(num + 1) ? m[num + 1] : 0;
        int sum = left + right + 1;
        m[num] = sum;
        res = max(res, sum);
        m[num - left] = sum;
        m[num + right] = sum;
    }
    return res;
}

129. Sum Root to Leaf Numbers (Medium)¶

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

Note: A leaf is a node with no children.
Input: [4,9,0,5,1]
    4
   / \
  9   0
 / \
5   1
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.
即从跟到叶子节点是一个数字，求所有这种数字的和

思路

递归即可

void recursion(TreeNode* root, int& result, int parentVal) {
    if (root == nullptr) return;
    if (root->left == nullptr && root->right == nullptr) {
        result += (parentVal * 10 + root->val);
        return;
    }
    recursion(root->left, result, parentVal * 10 + root->val);
    recursion(root->right, result, parentVal * 10 + root->val);
}
int sumNumbers(TreeNode* root) {
    if (root == nullptr) return 0;
    int result = 0;
    recursion(root, result, 0);
    return result;
}

130. Surrounded Regions (Medium)¶

Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

given
X X X X
X O O X
X X O X
X O X X
return
X X X X
X X X X
X X X X
X O X X
删除被X包围的O

思路一并查集

要注意的是如何记录没有被包围的O群，这里用一个hashmap来记录，但要注意的是，在向左和向上归并时，之前存在map里的那个rank可能会被覆盖，造成不该被删的区域被删

改正就是在归并时判断一下要覆盖的rank是否在map里面，如果在不要覆盖它

int find(vector<int>& set, int rank) {
    while (set[rank] != rank) {
        rank = set[rank];
    }
    return rank;
}
void solve(vector<vector<char>>& board) {
    if (board.size() == 0 || board[0].size() == 0) return;
    int n = board.size(), m = board[0].size();
    vector<int> set(m * n, 0);
    unordered_map<int, int> map;
    for (int i = 0; i < m * n; i ++) set[i] = i;
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < m; j ++) {
            int x = i * m + j;
            if (board[i][j] == 'O') {
                if (i > 0 && board[i - 1][j] == 'O')
                    set[find(set, x)] = find(set, x - m);
                if (j > 0 && board[i][j - 1] == 'O') {
                    if (map.count(find(set, x)))
                        set[find(set, x - 1)] = set[find(set, x)];
                    else
                        set[find(set, x)] = find(set, x - 1);
                 }
                if (i == 0 || i == n - 1 || j == 0 || j == m - 1)
                    map[set[x]] = 1;
            } else set[x] = -1;
        }
    }
    for (int x = 0; x < m * n; x ++) {
        if (set[x] == -1) continue;
        int rank = find(set, x);
        if (map.count(rank) == 0) board[x / m][x % m] = 'X';
    }
}

思路二递归

这个思路很简单，时间也最快 32ms (98.91%)

找到在边缘的O，然后从这点开始递归，标记相邻的所有O，最后再把标记改回来，同时把没有标记的O全部改为X

void recursion(vector<vector<char>>& board, int i, int j, int n, int m) {
    if (i < 0 || i >= n || j < 0 || j >= m) return;
    if (board[i][j] == 'O') board[i][j] = 'A';
    else return;
    recursion(board, i + 1, j, n, m);
    recursion(board, i - 1, j, n, m);
    recursion(board, i, j + 1, n, m);
    recursion(board, i, j - 1, n, m);
}
void solve(vector<vector<char>>& board) {
    if (board.size() == 0 || board[0].size() == 0) return;
    int n = board.size(), m = board[0].size();
    for (int i = 0; i < n; i ++) {
        if (board[i][0] == 'O') recursion(board, i, 0, n, m);
        if (board[i][m - 1] == 'O') recursion(board, i, m - 1, n, m);
    }
    for (int i = 0; i < m; i ++) {
        if (board[0][i] == 'O') recursion(board, 0, i, n, m);
        if (board[n - 1][i] == 'O') recursion(board, n - 1, i, n, m);
    }
    for (auto& v : board)
        for (auto& c : v)
            if (c == 'A') c = 'O';
            else if (c == 'O') c = 'X';
}

131. Palindrome Partitioning (Medium)¶

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.
Input: "aab"
Output:
[
  ["aa","b"],
  ["a","a","b"]
]
把字符串切割成回文子串集，所用次数最少的所有方案

思路

递归直接求解也可以，要节省时间，也可以先打表算出所有s[i][j]位是不是回文串

注意传参的时候传引用，两种方法都可以达到12ms(100.00%)

// 直接回溯求解
bool isPalindrome(string& s, int begin, int end) {
    int l = begin, r = end;
    while (l < r) if (s[l ++] != s[r --]) return false;
    return true;
}
void recursion(vector<vector<string>>& result, vector<string>& temp, string& s, int begin) {
    if (begin >= s.size()) {
        result.push_back(temp);
        return;
    }
    for (int i = begin; i < s.size(); i ++) {
        if (!isPalindrome(s, begin, i)) continue;
        temp.push_back(s.substr(begin, i - begin + 1));
        recursion(result, temp, s, i + 1);
        temp.pop_back();
    }
}
vector<vector<string>> partition(string s) {
    vector<vector<string>> result;
    int n = s.size();
    if (n == 0) return result;
    vector<string> temp;
    recursion(result, temp, s, 0);
    return result;
}

下面是先打表再回溯

void recursion(vector<vector<string>>& result, vector<string>& temp, vector<vector<int>>& record, string& s, int begin) {
    if (begin >= s.size()) {
        result.push_back(temp);
        return;
    }
    for (int i = begin; i < s.size(); i ++) {
        if (!record[begin][i]) continue;
        temp.push_back(s.substr(begin, i - begin + 1));
        recursion(result, temp, record, s, i + 1);
        temp.pop_back();
    }
}
vector<vector<string>> partition(string s) {
    vector<vector<string>> result;
    int n = s.size();
    if (n == 0) return result;
    vector<vector<int>> record (n, vector<int>(n, 0));
    for (int length = 0; length < n; length ++)
        for (int i = 0; i + length < n; i ++)
            if (length == 0) record[i][i] = 1;
            else if (length == 1) record[i][i+length] = (s[i] == s[i+length]) ? 1 : 0;
            else record[i][i+length] = (s[i] == s[i+length] && record[i+1][i+length-1]) ? 1 : 0;
    vector<string> temp;
    recursion(result, temp, record, s, 0);
    return result;
}

132. Palindrome Partitioning II (Hard)¶

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.
Input: "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.
最少切割几次能把一个字符串切成全是回文串的子串

思路

动归，这里设计比较巧妙，只用一维数组， $dp[i]$ 表示前i位切割成回文子串所用最少次数

转移条件即为找到最后一个回文串，然后加上前面部分字符串的最少切割次数即可

如果整体为回文串，需要特判一下， $dp[i] = 0$

为方便判断回文串，开一个二维vector来动归记录i-j位是不是回文串

int minCut(string s) {
    if (s.empty()) return 0;
    int n = s.size();
    vector<vector<bool>> p(n, vector<bool>(n));
    vector<int> dp(n);
    for (int i = 0; i < n; ++i) {
        dp[i] = i;
        for (int j = 0; j <= i; ++j) {
            if (s[i] == s[j] && (i - j < 2 || p[j + 1][i - 1])) {
                p[j][i] = true;
                dp[i] = (j == 0) ? 0 : min(dp[i], dp[j - 1] + 1);
            }
        }
    }
    return dp[n - 1];
}

133. Clone Graph (Medium)¶

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors.
class Node {
public:
    int val;
    vector<Node*> neighbors;
    Node() {}
    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
即深拷贝一个无向图

思路

BFS即可，需要用一个map来记录已经访问过的节点

Node* cloneGraph(Node* node) {
    if (node == nullptr) return node;
    unordered_map<Node*, Node*> dict;
    queue<Node*> q;
    q.push(node);
    Node* head = new Node(node->val);
    dict[node] = head;
    while (!q.empty()) {
        Node* n = q.front();
        q.pop();
        for (auto i : n->neighbors) {
            Node* temp = new Node(i->val);
            if (!dict.count(i)) {
                dict[i] = temp;
                q.push(i);
                dict[n]->neighbors.push_back(temp);
            }
            else dict[n]->neighbors.push_back(dict[i]);
        }
    }
    return head;
}

134. Gas Station (Medium)¶

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1.

Note:

If there exists a solution, it is guaranteed to be unique.

Both input arrays are non-empty and have the same length.

Each element in the input arrays is a non-negative integer.
Input: 
gas  = [1,2,3,4,5]
cost = [3,4,5,1,2]
Output: 3
Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas.
Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5.
Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.
即n个加油站围成一圈，每个加油站有gas量和cost量，看能不能从一个加油站出发顺时针一圈再回到该站

思路

每个加油站都作为出发点，尝试一遍即可，但递归来做会很慢 (264ms)

这里能用到的改进是，如果从i出发，到j时sum为负数，说明从i到j所有点都不适合作为起点，原因也很简单，在这个过程中，到达i点的时候，油量sum大于等于0，而作为起点油量sum则为0

又因为题目保证如果有解一定唯一，故整体扫描一遍即可得出答案，代码如下，start从0到n-1来尝试作为起点，当发现要更新的位置不在start之前，说明无法完成，直接返回-1即可

int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
    int ptr = 0, start = 0;
    long long sum = 0;
    while (true) {
        sum += (gas[ptr] - cost[ptr]);
        if (sum < 0) {
            if ((ptr + 1) % gas.size() <= start) return -1;
            start = (ptr + 1) % gas.size(), sum = 0, ptr = start;
            continue;
        }
        ptr = (ptr + 1) % gas.size();
        if (ptr == start) return start;
    }
    return -1;
}

135. Candy (Hard)¶

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy.

Children with a higher rating get more candies than their neighbors.
Input: [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

思路

ratings[i]位置要放的糖果数量即左边递减和右边递减的最大值+1，左右各扫描一遍统计即可

int candy(vector<int>& ratings) {
    if (ratings.size() == 0) return 0;
    vector<int> numbers(ratings.size(), 1);
    int prev = ratings[0], number = 0;
    for (int i = 1; i < ratings.size(); i ++) {
        if (ratings[i] > prev) number ++;
        else number = 0;
        numbers[i] += number;
        prev = ratings[i];
    }
    prev = ratings[ratings.size() - 1], number = 0;
    for (int i = ratings.size() - 2; i >= 0; i --) {
        if (ratings[i] > prev) number ++;
        else number = 0;
        numbers[i] = max(numbers[i], number + 1);
        prev = ratings[i];
    }
    int result = 0;
    for (auto n : numbers) result += n;
    return result;
}

136. Single Number (Easy)¶

给定数组，里面所有数都出现两次，只有一个数出现一次，O(N)时间O(1)空间找到这个数

思路

两个相等的数异或得0，所以全部异或起来即可

int singleNumber(vector<int>& nums) {
    int res = 0;
    for (int num : nums) res ^= num;
    return res;
}

137. Single Number II (Medium)¶

n个数，每个数出现3次，只有一个数出现1次，O(N)时间 O(1)空间求解

思路

将32位上每位出现1次数加起来，再模3，将结果是1的位合并起来即是答案

int singleNumber(vector<int>& nums) {
    int result = 0;
    for (int i = 0; i < 32; i ++) {
        int n = 0;
        for (auto num : nums)
            if (num >> i & 1) n ++;
        if (n % 3 == 1) result |= (1 << i);
    }
    return result;
}

更巧妙的做法如下，因为过程中保留每位模3的结果就可以，即0 1 2，二进制即00 01 11，因此用a和b两个32位的int，即可表示32位模3的结果

转移过程为00->01->10->00

这里归纳为下面两个式子，这里有些难想

int singleNumber(vector<int>& nums) {
    int a = 0, b = 0;
    for (auto num : nums) {
        b = (b ^ num) & ~a;
        a = (a ^ num) & ~b;
    }
    return b;
}

138. Copy List with Random Pointer (Medium)¶

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

思路

BFS，用hashmap记录原先点和拷贝点的映射，只有没有加入映射的点才能加入队列

Node* copyRandomList(Node* head) {
    if (head == nullptr) return head;
    unordered_map<Node*, Node*> map;
    Node* cohead = new Node(head->val, nullptr, nullptr);
    map[head] = cohead;
    queue<Node*> q;
    q.push(head);
    while (!q.empty()) {
        Node* n = q.front();
        q.pop();
        if (n->next != nullptr) {
            if (!map.count(n->next)) {
                Node* temp = new Node(n->next->val, nullptr, nullptr);
                map[n->next] = temp;
                q.push(n->next);
            }
            map[n]->next = map[n->next];
        }
        if (n->random != nullptr) {
            if (!map.count(n->random)) {
                Node* temp = new Node(n->random->val, nullptr, nullptr);
                map[n->random] = temp;
                q.push(n->random);
            }
            map[n]->random = map[n->random];
        }
    }
    return cohead;
}

139. Word Break (Medium)¶

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

给一个字符串s和一个词典，看这个字符串能不能由词典中的词构成

思路

思路类似于dp，但这里只存储所有可以匹配的位置i，即存储可以由词典中词构成的位置，然后每次遍历这些位置，看多出来的单词能否被匹配到，运行时间为8ms(99.55%)

时间复杂度还是 $O(mn)$ ，一个是s长度，一个是n的size，改进的话可以记录一下词典里词的长度种类，然后只对这几个种类看大小

bool wordBreak(string s, vector<string>& wordDict) {
    vector<int> positions;
    positions.push_back(0);
    unordered_map<string, bool> map;
    for (string s : wordDict) map[s] = true;
    for (int i = 0; i < s.size(); i ++) {
        for (int j = positions.size() - 1; j >= 0; j --) {
            int rank = positions[j];
            if (map.count(s.substr(rank, i+1-rank))) {
                positions.push_back(i+1);
                break;
            }
        }
    }
    return positions.back() == s.size();
}

140. Word Break II (Hard)¶

给一个string s和一个vector wordList，求s由wordList中的word组合而成的所有方案
Input:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:
[
  "cats and dog",
  "cat sand dog"
]

思路

递归来做，这里巧妙的一点是拿map记录string可以分割成的vector方案数，这样可以直接读取使用

比如aaaaaaaaaaaaaaaaaaaaaaa分割成['a', 'aa', 'aaa', 'aaaa', 'aaaaa']这样的case，这样的方案可以降低很多重复运算

vector<string> recursion(string s, vector<string>& wordDict,
                         unordered_map<string, vector<string>>& map) {
    if (map.count(s)) return map[s];
    vector<string> result;
    if (s.size() == 0) return result;
    for (auto& word : wordDict) {
        if (word.size() > s.size()) continue;
        if (word == s.substr(0, word.size())) {
            if (word.size() == s.size()) {
                result.push_back(s);
                continue;
            }
            vector<string> remaining = recursion(s.substr(word.size()), wordDict, map);
            for (auto& str : remaining) result.push_back(word + " " + str);
        }
    }
    return map[s] = result;
}
vector<string> wordBreak(string s, vector<string>& wordDict) {
    unordered_map<string, vector<string>> map;
    return recursion(s, wordDict, map);
}

141. Linked List Cycle (Easy)¶

Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

思路

快慢指针，看两者是否重叠

bool hasCycle(ListNode *head) {
    ListNode* first = head, *second = head;
    while (first != NULL) {
        first = first->next;
        if (first != NULL) first = first->next;
        else break;
        second = second->next;
        if (first == second) return true;
    }
    return false;
}

142. Linked List Cycle II (Medium)¶

对一个有环链表，返回环起点，如果没有环，就返回NULL

思路

设环长为c，之前的链长为l，则快慢指针相遇的地方，在环起点出发c-l%c处，距离起点还有l+k*c步

因为当second到达起点时，first已经在环内走了l步，领先l%c步，此时再追击 $c-l\%c$ 步刚好碰到，则此时second刚走了 $c-l\%c$ 步，整个过程一共走了l+c-l%c步，如果要求circle长度，再相遇后继续走，即能得到最后长度

所以要求起点，在first和second相遇后，再从起点出发，然后和meet点同时往前，相遇处即为起点

ListNode *detectCycle(ListNode *head) {
    ListNode* first = head, *second = head;
    while (first != NULL && first->next != NULL) {
        first = first->next->next;
        second = second->next;
        if (first == second) break;
    }
    if (first == NULL || first->next == NULL) return NULL;
    first = head;
    while (first != second) {
        first = first->next;
        second = second->next;
    }
    return first;
}

143. Reorder List (Medium)¶

Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You may not modify the values in the list's nodes, only nodes itself may be changed.
Given 1->2->3->4, reorder it to 1->4->2->3.
Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

思路

首先找到中间点，然后将后半部分链表翻转，然后拼接即可

ListNode* reverse(ListNode* head) {
    if (head->next == nullptr) return head;
    ListNode *prev = nullptr, *node = head;
    while (true) {
        ListNode *next = node->next;
        node->next = prev;
        if (next == nullptr) return node;
        prev = node;
        node = next;
    }
    return nullptr;
}
void reorderList(ListNode* head) {
    if (head == nullptr || head->next == nullptr) return;
    ListNode *first = head, *second = head, *prev = nullptr;
    while (first != nullptr) {
        first = first->next;
        if (first != nullptr) first = first->next;
        prev = second;
        second = second->next;
    }
    prev->next = nullptr;
    ListNode *head1 = reverse(second);
    ListNode* tail = nullptr;
    while (head1 != nullptr) {
        if (tail != nullptr) tail->next = head;
        ListNode* next = head->next;
        head->next = head1;
        tail = head1;
        head = next;
        head1 = head1->next;
    }
    tail->next = head;
}

144. Binary Tree Preorder Traversal (Meidum)¶

前序遍历二叉树

link

用栈遍历

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> v;
    if (root == nullptr) return v;
    stack<TreeNode*> s;
    s.push(root);
    while (!s.empty()) {
        TreeNode *node = s.top();
        s.pop();
        v.push_back(node->val);
        if (node->right != nullptr) s.push(node->right);
        if (node->left != nullptr) s.push(node->left);
    }
    return v;
}

Morris遍历

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> v;
    TreeNode *cur = root, *prev = nullptr;
    while (cur != nullptr) {
        if (cur->left == nullptr) {
            v.push_back(cur->val);
            cur = cur->right;
        } else {
            prev = cur->left;
            while (prev->right != nullptr && prev->right != cur)
                prev = prev->right;
            if (prev->right == nullptr) {
                prev->right = cur;
                v.push_back(cur->val);
                cur = cur->left;
            } else {
                prev->right = nullptr;
                cur = cur->right;
            }
        }
    }
    return v;
}

145. Binary Tree Postorder Traversal (Hard)¶

后序遍历二叉树

link

栈遍历

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> v;
    if (root == nullptr) return v;
    stack<TreeNode*> s;
    s.push(root);
    TreeNode *prev = root;
    while (!s.empty()) {
        TreeNode *ptr = s.top();
        if ((ptr->left == nullptr && ptr->right == nullptr) ||
           (ptr->right == nullptr && ptr->left == prev) ||
           (ptr->right == prev)) {
            v.push_back(ptr->val);
            s.pop();
            prev = ptr;
        } else {
            if (ptr->right != nullptr) s.push(ptr->right);
            if (ptr->left != nullptr) s.push(ptr->left);
        }
    }
    return v;
}

146. LRU Cache (Hard)¶

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
LRUCache cache = new LRUCache( 2 /* capacity */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

思路

维护一个链表，用一个hashmap记录key对应的node的前一个node，链表头为单独的一个node，每次访问后将node移到最后，同时更新map里key对应的prev

class CacheNode {
public:
    int val;
    int key;
    CacheNode* next;
    CacheNode(int k, int v) : key(k), val(v), next(NULL) {}
};

class LRUCache {
private:
    CacheNode* head, *tail;
    int capacity, size;
    unordered_map<int, CacheNode*> map;

    void moveToTail(CacheNode* prev) {
        if (prev->next == tail) return;
        CacheNode* node = prev->next;
        prev->next = node->next;
        if (prev->next != NULL) map[prev->next->key] = prev;
        tail->next = node;
        node->next = NULL;
        map[node->key] = tail;
        tail = node;
    }
public:
    LRUCache(int capacity) {
        this->capacity = capacity;
        this->size = 0;
        this->head = new CacheNode(0, 0);
        this->tail = this->head;
    }

    int get(int key) {
        if (!map.count(key)) return -1;
        moveToTail(map[key]);
        return map[key]->next->val;
    }

    void put(int key, int value) {
        if (map.count(key)) {
            moveToTail(map[key]);
            map[key]->next->val = value;
        } else {
            CacheNode* node = new CacheNode(key, value);
            tail->next = node;
            map[key] = tail;
            tail = node;
            size ++;
            if (size > capacity) {
                map.erase(head->next->key);
                head->next = head->next->next;
                if (head->next != NULL) map[head->next->key] = head;
                size --;
            }
        }
    }
};

147. Insertion Sort List (Medium)¶

用插入排序将链表排序

思路

每次选一个node，从头开始找到插入位置再插入即可

ListNode* insertionSortList(ListNode* head) {
    if (head == nullptr) return head;
    ListNode* node = head->next;
    ListNode* newHead = head;
    head->next = nullptr;
    while (node != nullptr) {
        ListNode* next = node->next;
        node->next = nullptr;
        ListNode* temp = newHead, *prev = nullptr;
        while (temp != nullptr && temp->val < node->val) {
            prev = temp;
            temp = temp->next;
        }
        if (prev != nullptr) prev->next = node;
        else newHead = node;
        if (temp != nullptr) node->next = temp;
        node = next;
    }
    return newHead;
}

148. Sort List (Medium)¶

Sort a linked list in O(n log n) time using constant space complexity.
Input: 4->2->1->3
Output: 1->2->3->4

快排

快排，这里注意的是把等于pivot的node专门拿出来作为一个list，然后合并，时间为52ms(99.25%)

struct List {
    int length;
    ListNode *head, *tail;
    List() : length(0), head(NULL), tail(NULL) {}
};
void addNode(List *list, ListNode *node) {
    if (list->head == NULL) list->head = list->tail = node;
    else {
        list->tail->next = node;
        list->tail = node;
    }
    list->length ++;
}
void quickSort(List *list) {
    if (list->length < 2) return;
    ListNode* node = list->head;

    List *leftList = new List(), *rightList = new List(), *middleList = new List();
    ListNode* ptr = node;
    while (ptr != NULL) {
        if (ptr->val < node->val) addNode(leftList, ptr);
        else if (ptr->val == node->val) addNode(middleList, ptr);
        else addNode(rightList, ptr);
        ptr = ptr->next;
    }
    if (leftList->head != NULL) leftList->tail->next = NULL;
    if (rightList->head != NULL) rightList->tail->next = NULL;

    if (leftList->length > 1) quickSort(leftList);
    if (rightList->length > 1) quickSort(rightList);

    if (leftList->head != NULL) leftList->tail->next = middleList->head;
    if (rightList->head != NULL) middleList->tail->next = rightList->head;
    list->head = (leftList->head != NULL) ? leftList->head : middleList->head;
    list->tail = (rightList->head != NULL) ? rightList->tail : middleList->tail;
    list->tail->next = NULL;
}
ListNode* sortList(ListNode* head) {
    List *list = new List();
    list->head = list->tail = head;
    if (head != NULL) list->length ++;
    while (list->tail != NULL && list->tail->next != NULL) {
        list->tail = list->tail->next;
        list->length ++;
    }
    quickSort(list);
    return list->head;
}

归并排序

时间为56ms(67.33%)

ListNode* merge(ListNode* headA, ListNode* headB) {
    ListNode* head = new ListNode(-1);
    ListNode* rank = head;
    while ((headA != NULL) && (headB != NULL)) {
        if (headA->val < headB->val) {
            rank->next = headA;
            rank = headA;
            headA = headA->next;
        } else {
            rank->next = headB;
            rank = headB;
            headB = headB->next;
        }
    }
    if (headA != NULL) rank->next = headA;
    if (headB != NULL) rank->next = headB;
    return head->next;
}
ListNode* sortList(ListNode* head) {
    if (head == NULL || head->next == NULL) return head;
    ListNode *fast = head, *slow = head;
    while (fast->next != NULL) {
        if (fast->next->next == NULL) {
            fast = fast->next;
            break;
        }
        fast = fast->next->next;
        slow = slow->next;
    }
    ListNode* temp = slow;
    slow = slow->next;
    temp->next = NULL;
    ListNode* tmp0 = sortList(head);
    ListNode* tmp1 = sortList(slow);
    ListNode* res = merge(tmp0, tmp1);
    return res;
}

149. Max Points on a Line (Hard)¶

给出n个点，判断同一条直线上最多点的个数

思路

对每个点，求经过该点的所有直线，统计其中经过最多点的个数

需要建立一个斜率-点个数的hashmap，但因为斜率是小数，无法准确作为key，这里巧妙的地方在于拿分数代替，除去最大公约数即为分数形式

最大公约数用一个函数就能完成

auto gcd = [&](int a, int b) -> int {
    while (a != 0) {
        int temp = a; a = b % a, b = temp;
    }
    return b;
};

这里要注意因为unordered_map无法用pair作为key，除非自定义一下pair的hash，改用基于红黑树的map来存储

struct hash_pair { 
    template <class T1, class T2> 
    size_t operator() (const pair<T1, T2>& p) const { 
        auto hash1 = hash<T1>{}(p.first); 
        auto hash2 = hash<T2>{}(p.second); 
        return hash1 ^ hash2; 
    } 
}; 
unordered_map<pair<int, int>, bool, hash_pair> um;

完整代码如下

int maxPoints(vector<Point>& points) {
    auto gcd = [&](int a, int b) -> int { while (a != 0) { int temp = a; a = b % a, b = temp; } return b; };
    int result = 0;
    for (int i = 0; i < points.size(); i ++) {
        map<pair<int, int>, int> m;
        int repeat = 1;
        for (int j = i + 1; j < points.size(); j ++) {
            int dx = points[i].x - points[j].x, dy = points[i].y - points[j].y;
            if (dx == 0 && dy == 0) {
                repeat ++;
                continue;
            }
            int d = gcd(dx, dy);
            m[{dx / d, dy / d}] ++;
        }
        int res = 0;
        for (auto it = m.begin(); it != m.end(); it ++) res = max(res, it->second);
        res += repeat;
        result = max(result, res);
    }
    return result;
}

150. Evaluate Reverse Polish Notation (Medium)¶

求解逆波兰表达式，用栈即可，注意波兰表达式含义，有运算符进来时一定是栈顶两个数字来运算，运算结束将结果入栈即可，如下例

# Case 1
Input: ["2", "1", "+", "3", "*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9
# Case 2
Input: ["4", "13", "5", "/", "+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6
# Case 3
Input: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
Output: 22
Explanation: 
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

思路

用栈记录即可

int evalRPN(vector<string>& tokens) {
    stack<int> s;
    if (tokens.size() == 0) return 0;
    for (string token : tokens) {
        if (token == "*") {
            int n2 = s.top(); s.pop();
            int n1 = s.top(); s.pop();
            s.push(n1 * n2);
        } else if (token == "+") {
            int n2 = s.top(); s.pop();
            int n1 = s.top(); s.pop();
            s.push(n1 + n2);
        } else if (token == "-") {
            int n2 = s.top(); s.pop();
            int n1 = s.top(); s.pop();
            s.push(n1 - n2);
        } else if (token == "/") {
            int n2 = s.top(); s.pop();
            int n1 = s.top(); s.pop();
            s.push(n1 / n2);
        } else {
            s.push(stoi(token));
        }
    }
    return s.top();
}

151. Reverse Words in a String (Medium)¶

Given an input string, reverse the string word by word.
Input: "the sky is blue"
Output: "blue is sky the"

思路

先扫描分割，放在一个栈里，然后空格连接输出即可

注意

末尾可能没有0，这时候扫描结束后最末尾单词没有入栈，需要单独判断一下
字符串开头可能是空格，需要先排除

string reverseWords(string s) {
    stack<string> st;
    int prev = 0;
    while (prev < s.size() && s[prev] == ' ') prev ++;
    for (int i = prev; i < s.size(); i ++) {
        if (s[i] == ' ') {
            st.push(s.substr(prev, i - prev));
            while (i < s.size() && s[i] == ' ') i ++;
            prev = i;
        }
    }
    if (prev < s.size()) st.push(s.substr(prev));
    if (st.size() == 0) return "";
    string res = st.top();
    st.pop();
    while (!st.empty()) {
        res += " ";
        res += st.top();
        st.pop();
    }
    return res;
}

152. Maximum Product Subarray (Medium)¶

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.
Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

思路

DP，维护包含这个数的最大正数乘积和最大负数乘积，然后分正负更新，返回max(positive[0-n])即为答案

int maxProduct(vector<int>& nums) {
    if (nums.size() == 0) return 0;
    vector<int> positive(nums.size(), 0);
    vector<int> negative(nums.size(), 0);
    if (nums[0] > 0) positive[0] = nums[0];
    else negative[0] = nums[0];
    int mx = nums[0];
    for (int i = 1; i < nums.size(); i ++) {
        if (nums[i] > 0) {
            positive[i] = max(nums[i], nums[i] * positive[i-1]);
            negative[i] = nums[i] * negative[i-1];
        }
        else if (nums[i] < 0) {
            negative[i] = min(nums[i], nums[i] * positive[i-1]);
            positive[i] = nums[i] * negative[i-1];
        }
        mx = max(mx, positive[i]);
    }
    return mx;
}

153. Find Minimum in Rotated Sorted Array (Medium)¶

一个增序排列好的数组移动过几位，找数组最小位，数组没有重复数字
Input: [4,5,6,7,0,1,2]
Output: 0

思路

类似于33和81

二分稍微变体，用中间位和末尾比较

如果小，则右指针r置为m
否则，左指针l置为m+1

int findMin(vector<int>& nums) {
    int l = 0, r = nums.size() - 1;
    if (l == r) return nums[0];
    while (l < r) {
        int m = (l + r) / 2;
        int am = (m + nums.size() - 1) % nums.size();
        if (nums[m] < nums[am]) return nums[m];
        if (nums[m] < nums[nums.size() - 1]) r = m;
        else l = m + 1;
    }
    return nums[l];
}

154. Find Minimum in Rotated Sorted Array II (Hard)¶

一个增序排列好的数组移动过几位，找数组最小位，但数组会有重复数字
Input: [2,2,2,0,1]
Output: 0

思路

和上题类似，但当m和末尾相等时，会无法确定范围划分

比如2 2 2 2 1 2 2 2，如果m是2，那么无法知道往哪边划分可以找到1，这时候只能退化为线性查找，即把右指针逐渐左移，然后每次对右指针位置做一个判断

int findMin(vector<int>& nums) {
    int l = 0, r = nums.size() - 1, n = nums.size() - 1;
    while (l < r) {
        int m = (l + r) / 2;
        int prev = (m + n) % (n + 1);
        if (nums[m] < nums[prev]) return nums[m];
        if (nums[r] < nums[(r+n)%(n+1)]) return nums[r];
        if (nums[m] < nums[n]) r = m;
        else if (nums[m] > nums[n]) l = m + 1;
        else r --;
    }
    return nums[l];
}

155. Min Stack (Easy)¶

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) -- Push element x onto stack.

pop() -- Removes the element on top of the stack.

top() -- Get the top element.

getMin() -- Retrieve the minimum element in the stack.
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

思路

这里要注意的是，因为栈的后入先出特性，一个数入栈后，之后入栈比它大的数都不会影响min

所以用一个栈维护所有数，一个栈记录最小值即可

class MinStack {
private:
    stack<int> s0, s1;
public:
    MinStack() {}
    void push(int x) {
        if (s1.empty() || x <= s1.top()) s1.push(x);
        s0.push(x);
    }
    void pop() {
        if (s0.top() == s1.top()) s1.pop();
        s0.pop();
    }
    int top() { return s0.top(); }
    int getMin() { return s1.top(); }
};

156. Binary Tree Upside Down (Meidum)¶

Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.
Input: [1,2,3,4,5]
    1
   / \
  2   3
 / \
4   5
Output: return the root of the binary tree [4,5,2,#,#,3,1]
   4
  / \
 5   2
    / \
   3   1  

思路

题意有点疑惑，是这样的，之前二叉树上每个右节点要么是叶子节点要么是空；然后将每个左孩子变为父亲节点，右孩子是之前的父亲节点，左孩子是之前的右孩子

用一个栈记录所有的左孩子，然后逆序输出即可。

TreeNode* upsideDownBinaryTree(TreeNode* root) {
    if (root == nullptr) return root;
    stack<TreeNode*> s;
    TreeNode* node = root;
    while (node != nullptr) {
        s.push(node);
        node = node->left;
    }
    node = s.top();
    while (!s.empty()) {
        TreeNode* temp = s.top();
        s.pop();
        if (!s.empty()) {
            temp->right = s.top();
            temp->left = s.top()->right;
        } else {
            temp->right = nullptr;
            temp->left = nullptr;
        }
    }
    return node;
}

157. Read N Characters Given Read4 (Easy)¶

Given a file and assume that you can only read the file using a given method read4, implement a method to read n characters.

File file("abcdefghijk"); // File is "abcdefghijk", initially file pointer (fp) points to 'a'
char[] buf = new char[4]; // Create buffer with enough space to store characters
read4(buf); // read4 returns 4. Now buf = "abcd", fp points to 'e'
read4(buf); // read4 returns 4. Now buf = "efgh", fp points to 'i'
read4(buf); // read4 returns 3. Now buf = "ijk", fp points to end of file

思路

又是一道题意很迷的题，大概是说read4(buf)每次可以读入4个byte，然后实现一个read(buf, n)

方法就是在通过buf+num来偏移读入，只会调用一次，所以即使读完后fp指针不在结束的地方也可以

int read(char *buf, int n) {
    int num = 0;
    while (n) {
        int t = read4(buf + num);
        if (t == 0) break;
        num += t;
        if (num >= n) return n;
    }
    return num;
}

158. Read N Characters Given Read4 II - Call multiple times (Hard)¶

题意和上题一样，区别在于这次会调用多次，也就是说需要回退fp指针，这个因为没有权限做不到，所以只能本地维护一个char*的buffer，然后每次复制buffer里的一个char到buf中，如果buffer空了就调用read4读入

class Solution {
public:
    int read(char *buf, int n) {
        for (int i = 0; i < n; i ++) {
            if (readPtr == writePtr) {
                readPtr = 0;
                writePtr = read4(buffer);
                if (writePtr == 0) return i;
            }
            buf[i] = buffer[readPtr ++];
        }
        return n;
    }
private:
    char buffer[4];
    int readPtr = 0, writePtr = 0;
};

159. Longest Substring with At Most Two Distinct Characters (Hard)¶

Given a string s , find the length of the longest substring t that contains at most 2 distinct characters.

求最多包含两个不同字母的连续子串的最长长度
Input: "ccaabbb"
Output: 5
Explanation: t is "aabbb" which its length is 5.

思路

记录如下信息

两个不同的字母
两个字母出现的最后位置

从前向后扫描，遇到两个字母的话更新其最后位置，遇到不一样的字母，两个位置中靠前的字母要去掉，算出length即可，实现细节多注意，调bug调了挺久

int lengthOfLongestSubstringTwoDistinct(string s) {
    if (s.size() <= 2) return s.size();
    char c0 = s[0], c1 = s[1];
    int ptr0 = 0, ptr1 = 1;
    if (c0 == c1) { ptr0 = 1, ptr1 = -1; }
    int result = 0, length = 2;
    for (int i = 2; i < s.size(); i ++) {
        char c = s[i];
        if (c == c0) ptr0 = i;
        else if (c == c1 || ptr1 < 0) {
            c1 = c;
            ptr1 = i;
        } else {
            result = max(result, length);
            length = i - min(ptr0, ptr1) - 1;
            if (ptr0 < ptr1) {
                c0 = c;
                ptr0 = i;
            } else {
                c1 = c;
                ptr1 = i;
            }
        }
        length ++;
    }
    return max(result, length);
}

160. Intersection of Two Linked Lists (Easy)¶

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

思路

先求出两个链的长度，然后长的一个链先往前走 $\triangledown length$ ，然后两个链同时走，直到相遇为止

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    int lengthA = 0, lengthB = 0;
    ListNode *tempA = headA, *tempB = headB;
    while (tempA != NULL) {
        lengthA ++;
        tempA = tempA->next;
    }
    while (tempB != NULL) {
        lengthB ++;
        tempB = tempB->next;
    }
    ListNode *first = (lengthA > lengthB) ? headA : headB;
    ListNode *second = (lengthA > lengthB) ? headB : headA;
    int delta = (lengthA > lengthB) ? lengthA - lengthB : lengthB - lengthA;
    while (delta --) first = first->next;
    while (first != second) {
        first = first->next;
        second = second->next;
    }
    return first;
}

¶

161. One Edit Distance (Medium)¶

给两个字符串，只能修改一位(增/删/改)，判断是否可以

思路

直接比较即可

bool isOneEditDistance(string s, string t) {
    if (s.size() + 2 <= t.size() || t.size() + 2 <= s.size()) return false;
    int sptr = 0, tptr = 0;
    bool update = false;
    while (sptr < s.size() && tptr < t.size()) {
        if (s[sptr] == t[tptr]) { sptr ++; tptr ++; }
        else {
            if (!update) update = true;
            else return false;
            if (s.size() == t.size()) { sptr ++; tptr ++; }
            else if (s.size() > t.size()) sptr ++;
            else tptr ++;
        }
    }
    if (!update && (s.size() + t.size() - sptr - tptr) == 1) return true;
    return update;
}

162. Find Peak Element (Medium)¶

一个数组，相邻数不相等，返回数组的一个peak，即大于两侧数
Input: nums = [1,2,1,3,5,6,4]
Output: 1 or 5 
Explanation: Your function can return either index number 1
where the peak element is 2,
or index number 5 where the peak element is 6.

思路

扫描即可

int findPeakElement(vector<int>& nums) {
    int ptr = 0;
    while (ptr < nums.size()) {
        if ((ptr==nums.size()-1 || nums[ptr]>nums[ptr+1])
           && (ptr==0 || nums[ptr]>nums[ptr-1]))
            return ptr;
        if (ptr == nums.size() - 1) break;
        if (nums[ptr] < nums[ptr + 1]) ptr ++;
        else ptr += 2;
    }
    return -1;
}

163. Missing Ranges (Medium)¶

Given a sorted integer array nums, where the range of elements are in the inclusive range [lower, upper], return its missing ranges.
Input: nums = [0, 1, 3, 50, 75], lower = 0 and upper = 99,
Output: ["2", "4->49", "51->74", "76->99"]
给定一个有序数组，再给出一个上下限，数组元素都在这个范围内，返回缺失的range

思路

细节题，代码思路很简单，就是很多边界条件都要考虑到

[1], 1, 1 -> []
[INT_MAX], INT_MAX, INT_MAX -> []
[], 1, 1 -> ["1"]

整数加减时要考虑是否越界
数组为空，lower和upper相等
lower和数组补充完后，可能会和upper一样，这时要判断退出循环返回结果
可能数组中连续多个值一样，这时候

string func(int l, int r) {
    if (l == r) return to_string(l);
    else return to_string(l) + "->" + to_string(r);
}
vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
    vector<string> res;
    int ptr = 0;
    while (true) {
        while (ptr < nums.size() && nums[ptr] <= lower) {
            if (lower == INT_MAX) return res;
            lower = nums[ptr] + 1;
            ptr ++;
        }
        if (lower > upper) break;
        if (ptr < nums.size()) {
            res.push_back(func(lower, nums[ptr] - 1));
            lower = nums[ptr];
        } else {
            res.push_back(func(lower, upper));
            break;
        }
        if (lower >= upper) break;
    }
    return res;
}

164. Maximum Gap (Hard)¶

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

Try to solve it in linear time/space.
Input: [3,6,9,1]
Output: 3
Explanation: The sorted form of the array is [1,3,6,9], either
             (3,6) or (6,9) has the maximum difference 3.
给一个未排序数组，返回排序后两个数之间的最大gap，要求线性时间+空间内完成

思路一基数排序

因为都是非负数，可以直接应用基数排序来做，但其实和直接调stl的sort时间相同，都是12ms (73.28%)，因为基数排序常数会较大

int maximumGap(vector<int>& nums) {
    if (nums.size() < 2) return 0;
    int mx = nums[0];
    for (auto num : nums) mx = max(mx, num);
    int radix = 1;
    while (mx / radix > 0) {
        vector<int> temp(nums.size(), 0);
        vector<int> cnt(10, 0);
        for (auto num : nums) cnt[(num / radix) % 10] ++;
        for (int i = 1; i < 10; i ++) cnt[i] += cnt[i - 1];
        for (int i = nums.size() - 1; i >= 0; i --) {
            temp[cnt[(nums[i] / radix) % 10] - 1] = nums[i];
            cnt[(nums[i] / radix) % 10] --;
        }
        nums.swap(temp);
        radix *= 10;
    }
    mx = 0;
    for (int i = 0; i < nums.size() - 1; i ++) mx = max(mx, nums[i + 1] - nums[i]);
    return mx;
}

思路二桶划分

桶划分的思路很巧妙，先找出数组最大值和最小值，记数组大小为 $n$ ，那么数组平均每两个数之前的gap是 $(max-min)/(n-1)$ ，先不考虑取整，就拿这个真实值来划分 $n-1$ 个桶，那么桶内元素间隔一定小于这个值，而一定有gap大于这个值，所以这样就不用管桶内元素顺序，只统计桶间元素大小即可，时间是8ms (99.74%)

注意思考问题时先不要考虑取整，就想理想状态下的情况，方案明确了再看怎么实现

int maximumGap(vector<int>& nums) {
    class Bucket{
    public:
        bool used;
        int mn, mx;
        Bucket() : used(false), mn(INT_MAX), mx(INT_MIN) {}
    };
    int n = nums.size();
    if (n < 2) return 0;
    int mnv = nums[0], mxv = nums[0];
    for (auto num : nums) {
        mnv = min(num, mnv);
        mxv = max(num, mxv);
    }
    int bucketSize = max(1, (mxv - mnv) / (n + 1));
    int bucketNum = (mxv - mnv) / bucketSize + 1;
    vector<Bucket> buckets(bucketNum, Bucket());
    for (auto&& num : nums) {
        int idx = (num - mnv) / bucketSize;
        buckets[idx].used = true;
        buckets[idx].mn = min(num, buckets[idx].mn);
        buckets[idx].mx = max(num, buckets[idx].mx);
    }
    int prev = mnv, maxGap = 0;
    for (auto&& bucket : buckets) {
        if (!bucket.used) continue;
        maxGap = max(maxGap, bucket.mn - prev);
        prev = bucket.mx;
    }
    return maxGap;
}

165. Compare Version Numbers (Medium)¶

Compare two version numbers version1 and version2. If version1 > version2 return 1; if version1 < version2 return -1;otherwise return 0.
Input: version1 = "1.0", version2 = "1.0.0"
Output: 0
Explanation: The first version number does not have a third level revision number, which means its third level revision number is default to "0"
版本号的比较就是从头到尾，每个.划分一下数字，然后依次比较

思路

依次比较即可

int getNum(string& version, int& ptr) {
    if (ptr >= version.size()) return 0;
    int prev = ptr;
    while (ptr < version.size() && version[ptr] != '.') ptr ++;
    ptr ++;
    return stoi(version.substr(prev, ptr - 1 - prev));
}
int compareVersion(string version1, string version2) {
    int ptr1 = 0, ptr2 = 0;
    while (ptr1 < version1.size() || ptr2 < version2.size()) {
        int num1 = getNum(version1, ptr1), num2 = getNum(version2, ptr2);
        if (num1 > num2) return 1;
        else if (num1 < num2) return -1;
    }
    return 0;
}

166. Fraction to Recurring Decimal (Medium)¶

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in pa rentheses.
Input: numerator = 2, denominator = 3
Output: "0.(6)"

注意

注意判断符号，在后面运行时n和d应该为正，但取反时就可能带来int溢出，因为int负数范围更大，所以一开始改为long long
注意后面循环节的判断，应该是拿每次的被除数当key，发现重复时即发现循环节

string fractionToDecimal(int numerator, int denominator) {
    unordered_map<int, int> dict;
    string s = "";
    long long num = numerator, den = denominator;
    if (num < 0 && den < 0) {
        num = -num;
        den = -den;
    } else if (num < 0) {
        s = "-";
        num = -num;
    } else if (den < 0 && num > 0) {
        s = "-";
        den = -den;
    }
    s += to_string(num / den);
    num %= den;
    if (num == 0) return s;
    s += ".";
    string temp = "";
    while (true) {
        num *= 10;
        int n = num / den;
        if (dict.count(num))
            return s + temp.substr(0, dict[num]) \
                + "(" + temp.substr(dict[num]) + ")";
        dict[num] = temp.size();
        num %= den;
        temp += ('0' + n);
        if (num == 0) return s + temp;
    }
    return s;
}

167. Two Sum II - Input array is sorted (Easy)¶

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.
给一个升序排列数组，求两个数加起来为target，返回这两个数的index(从1开始计数)

思路

双指针遍历即可

vector<int> twoSum(vector<int>& numbers, int target) {
    int ptr0 = 0, ptr1 = numbers.size() - 1;
    while (numbers[ptr0] + numbers[ptr1] != target) {
        if (numbers[ptr0] + numbers[ptr1] > target) ptr1 --;
        else ptr0 ++;
    }
    return {ptr0 + 1, ptr1 + 1};
}

168. Excel Sheet Colume Title (Easy)¶

Given a positive integer, return its corresponding column title as appear in an Excel sheet.
    1 -> A
    2 -> B
    3 -> C
    ...
    26 -> Z
    27 -> AA
    28 -> AB 
    ...

思路

即转换成26进制，按照进制转换方法来即可

先求个位
然后将个位减去，再右移一位，即除以radix

string convertToTitle(int n) {
    string res = "";
    while (n) {
        char c = 'A' + (n - 1) % 26;
        res = c + res;
        n -= ((n - 1) % 26);
        n /= 26;
    }
    return res;
}

169. Majority Element (Easy)¶

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

思路

维护一个计数器，并记录之前一个元素，当计数器为0时，更改元素并增加计数器，计数器不为0且相等时增加计数，否则减少计数

最后记录的元素即为超过一半的元素

int majorityElement(vector<int>& nums) {
    int times = 0, prev = 0;
    for (auto i : nums) {
        if (times == 0) {
            prev = i;
            times = 1;
        }
        else if (prev == i) times ++;
        else times --;
    }
    return prev;
}

170. Two Sum III - Data structure design (Easy)¶

Design and implement a TwoSum class. It should support the following operations: add and find. + add - Add the number to an internal data structure. + find - Find if there exists any pair of numbers which sum is equal to the value.
add(1); add(3); add(5);
find(4) -> true
find(7) -> false

思路

维护一个哈希表，查找即可

class TwoSum {
public:
    TwoSum() {}

    void add(int number) { dict[number] ++; }

    bool find(int value) {
        for (auto it : dict) {
            if (value - it.first == it.first && dict[it.first] > 1)
                return true;
            else if (value - it.first != it.first && dict.count(value - it.first))
                return true;
        }
        return false;
    }
private:
    unordered_map<int, int> dict;
};

171. Excel Sheet Column Number (Easy)¶

Given a column title as appear in an Excel sheet, return its corresponding column number.
    A -> 1
    B -> 2
    C -> 3
    ...
    Z -> 26
    AA -> 27
    AB -> 28 
    ...

思路

进制转换，逐个加即可

int titleToNumber(string s) {
    int res = 0;
    for (auto c : s) {
        res *= 26;
        res += (c - 'A' + 1);
    }
    return res;
}

172. Factorial Trailing Zeroes (Easy)¶

n的阶乘末尾有几个0

思路

即看 $n!$ 里有几个5，每隔5会有一个5，5 10 15 20 25，每隔25会有两个5，25 50 75，所以一直除以5并累加即可

int trailingZeroes(int n) {
    int res = 0;
    while (n > 0) {
        res += (n / 5);
        n /= 5;
    }
    return res;
}

173. Binary Search Tree Iterator (Medium)¶

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.
BSTIterator iterator = new BSTIterator(root);
iterator.next();    // return 3
iterator.next();    // return 7
iterator.hasNext(); // return true
iterator.next();    // return 9
iterator.hasNext(); // return true
iterator.next();    // return 15
iterator.hasNext(); // return true
iterator.next();    // return 20
iterator.hasNext(); // return false
即一个类可以查询二叉树有没有下一个节点，以及下一个节点是什么，维护一个栈即可

思路

维护一个栈，最开始把root及向左路径的所有节点依次入栈，之后每次出栈都判断一下出栈的元素有没有右孩子，有的话将右孩子及它的所有左孩子都入栈，因为除过最开始入栈的一路向左路径外，其余节点的路径都含有一个向右的路径

class BSTIterator {
public:
    BSTIterator(TreeNode* root) {
        while (root != nullptr) {
            s.push(root);
            root = root->left;
        }
    }
    int next() {
        TreeNode* node = s.top();
        s.pop();
        TreeNode* r = node->right;
        while (r != nullptr) {
            s.push(r);
            r = r->left;
        }
        return node->val;
    }
    bool hasNext() {
        return (s.size() > 0);
    }
private:
    stack<TreeNode*> s;
};

174. Dungeon Game (Hard)¶

恶魔抓了公主将她关在地牢右下角，地牢是 $M \times N$ 的2D房间，勇士从左上角出发，每个房间有一个魔力值，为负代表扣除生命值，为正表示加上生命值，勇士有初始生命值，到每个房间后会随之变化。过程中勇士的生命值不能低于1，求勇士到达右下角需要的最小生命值

-2 -3 3

-5 -10 1

10 30 -5

return 7

思路

从右下角开始向回倒推，维护一个同样大小的dp数组，表示从某一个房间走到终点所需要的最小生命值，然后一直更新到左上角为止

int calculateMinimumHP(vector<vector<int>>& dungeon) {
    int n = dungeon.size(), m = dungeon[0].size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, INT_MAX));
    dp[n][m-1] = 1;
    for (int i = n - 1; i >= 0; i --)
        for (int j = m - 1; j >= 0; j --)
            dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]);
    return dp[0][0];
}

175 Combine Two Tables (Easy)¶

如下两张表，合并起来

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| PersonId    | int     |
| FirstName   | varchar |
| LastName    | varchar |
+-------------+---------+
PersonId is the primary key column for this table.

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| AddressId   | int     |
| PersonId    | int     |
| City        | varchar |
| State       | varchar |
+-------------+---------+
AddressId is the primary key column for this table.

返回如下字段

FirstName, LastName, City, State

select Person.FirstName, Person.LastName, Address.City, Address.State
    from Person left join Address
    on Person.PersonId = Address.PersonId
    order by Person.PersonId

176. Second Highest Salary (Easy)¶

Write a SQL query to get the second highest salary from the Employee table.
+----+--------+
| Id | Salary |
+----+--------+
| 1  | 100    |
| 2  | 200    |
| 3  | 300    |
+----+--------+
如上数据库，应返回
+---------------------+
| SecondHighestSalary |
+---------------------+
| 200                 |
+---------------------+

思路

注意

select as 可以指定字段名
(SQL)可以起和shell中`Shell`相同的作用

select MAX(Salary) as SecondHighestSalary from Employee 
where Salary not in
(select MAX(Salary) from Employee)

177. Nth Highest Salary (Medium)¶

返回第N高的工资

+----+--------+
| Id | Salary |
+----+--------+
| 1  | 100    |
| 2  | 200    |
| 3  | 300    |
+----+--------+

+------------------------+
| getNthHighestSalary(2) |
+------------------------+
| 200                    |
+------------------------+

思路

了解如何写函数
如何定义变量
Group by 即按照这个字段不同值分组
ORDER BY DESC 降序排列
LIMIT 1 只输出一个
OFFSET N 去除前N位

CREATE FUNCTION getNthHighestSalary(N INT) RETURNS INT
BEGIN
    SET N = N - 1;
    RETURN (
        SELECT Salary FROM Employee GROUP BY Salary
        ORDER BY Salary DESC LIMIT 1 OFFSET N
    );
END

178. Rank Scores (Medium)¶

对分数给出排名，相同分数给出相同排名，排名不随人数变化，比如前面是两个第一名，接下来还是第二名
+----+-------+
| Id | Score |
+----+-------+
| 1  | 3.50  |
| 2  | 3.65  |
| 3  | 4.00  |
| 4  | 3.85  |
| 5  | 4.00  |
| 6  | 3.65  |
+----+-------+
给定上表，应输出如下结果
+-------+------+
| Score | Rank |
+-------+------+
| 4.00  | 1    |
| 4.00  | 1    |
| 3.85  | 2    |
| 3.65  | 3    |
| 3.65  | 3    |
| 3.50  | 4    |
+-------+------+

思路

嵌套语句，对每个分数查找表中不小于它的distinct分数个数

SELECT Score,
(SELECT COUNT(DISTINCT Score) FROM Scores WHERE Score >= s.Score) Rank 
FROM Scores s ORDER BY Score DESC;

179. Largest Number (Medium)¶

给出一些非负整数，求这些数拼起来所组成的最大数

如以下例子
Input: [3,30,34,5,9]
Output: "9534330"

思路

对其排序即可，注意排序方法很巧妙，直接将两段字符串拼接起来看谁大即可

string largestNumber(vector<int>& nums) {
    if (nums.size() == 0) return "0";
    auto comp = [](int a, int b) {
       return to_string(a) + to_string(b) > to_string(b) + to_string(a); 
    };
    sort(nums.begin(), nums.end(), comp);
    if (nums[0] == 0) return "0";
    string res = "";
    for (auto num : nums) res += to_string(num);
    return res;
}

180. Consecutive Numbers (Medium)¶

找出所有连续出现至少3次的数

+----+-----+
| Id | Num |
+----+-----+
| 1  |  1  |
| 2  |  1  |
| 3  |  1  |
| 4  |  2  |
| 5  |  1  |
| 6  |  2  |
| 7  |  2  |
+----+-----+

应返回

+-----------------+
| ConsecutiveNums |
+-----------------+
| 1               |
+-----------------+

思路

如下，连续Inner Join即可

SELECT DISTINCT l1.Num AS ConsecutiveNums FROM Logs l1
INNER JOIN Logs l2 ON l1.Id = l2.Id - 1
INNER JOIN Logs l3 ON l1.Id = l3.Id - 2
WHERE l1.Num = l2.Num AND l2.Num = l3.Num;

181. Employees Earning More Than Their Managers (Easy)¶

找比其Manager工资更高的Employee，如下例

+----+-------+--------+-----------+
| Id | Name  | Salary | ManagerId |
+----+-------+--------+-----------+
| 1  | Joe   | 70000  | 3         |
| 2  | Henry | 80000  | 4         |
| 3  | Sam   | 60000  | NULL      |
| 4  | Max   | 90000  | NULL      |
+----+-------+--------+-----------+

+----------+
| Employee |
+----------+
| Joe      |
+----------+

思路

直接Join比较即可

SELECT e1.Name AS Employee FROM Employee e1 JOIN Employee e2 ON e1.ManagerId = e2.Id AND e1.Salary > e2.Salary

182. Duplicate Emails (Easy)¶

找出所有重复的邮箱

思路

使用GROUP进行分组，然后用COUNT作为过滤条件，注意Group的过滤语句是having

select Email from Person group by Email having count(Email) > 1

183. Customers Who Never Order (Easy)¶

给一个Customers表和一个Orders表，列出没有下过单的Customer

+----+-------+
| Id | Name  |
+----+-------+
| 1  | Joe   |
| 2  | Henry |
| 3  | Sam   |
| 4  | Max   |
+----+-------+

+----+------------+
| Id | CustomerId |
+----+------------+
| 1  | 3          |
| 2  | 1          |
+----+------------+

+-----------+
| Customers |
+-----------+
| Henry     |
| Max       |
+-----------+

思路

使用not in排除即可

select Name as Customers from Customers where Id not in (select CustomerId from Orders)

184. Department Highest Salary (Medium)¶

给出两个表Employee和Department，求每个寝室salary最高的员工

+----+-------+--------+--------------+
| Id | Name  | Salary | DepartmentId |
+----+-------+--------+--------------+
| 1  | Joe   | 70000  | 1            |
| 2  | Jim   | 90000  | 1            |
| 3  | Henry | 80000  | 2            |
| 4  | Sam   | 60000  | 2            |
| 5  | Max   | 90000  | 1            |
+----+-------+--------+--------------+
+----+----------+
| Id | Name     |
+----+----------+
| 1  | IT       |
| 2  | Sales    |
+----+----------+

返回

+------------+----------+--------+
| Department | Employee | Salary |
+------------+----------+--------+
| IT         | Max      | 90000  |
| IT         | Jim      | 90000  |
| Sales      | Henry    | 80000  |
+------------+----------+--------+

思路

select语句里造一个最高工资表，然后三张表连接起来

select
d.Name as Department, e.Name as Employee, e.Salary as Salary
from Department d, Employee e,
(select MAX(Salary) as Salary,  DepartmentId from Employee GROUP BY DepartmentId) h
where
e.Salary = h.Salary and
e.DepartmentId = h.DepartmentId and
e.DepartmentId = d.Id;

185. Department Top Three Salaries (Hard)¶

Employee
+----+-------+--------+--------------+
| Id | Name  | Salary | DepartmentId |
+----+-------+--------+--------------+
| 1  | Joe   | 85000  | 1            |
| 2  | Henry | 80000  | 2            |
| 3  | Sam   | 60000  | 2            |
| 4  | Max   | 90000  | 1            |
| 5  | Janet | 69000  | 1            |
| 6  | Randy | 85000  | 1            |
| 7  | Will  | 70000  | 1            |
+----+-------+--------+--------------+
Department
+----+----------+
| Id | Name     |
+----+----------+
| 1  | IT       |
| 2  | Sales    |
+----+----------+
return
+------------+----------+--------+
| Department | Employee | Salary |
+------------+----------+--------+
| IT         | Max      | 90000  |
| IT         | Randy    | 85000  |
| IT         | Joe      | 85000  |
| IT         | Will     | 70000  |
| Sales      | Henry    | 80000  |
| Sales      | Sam      | 60000  |
+------------+----------+--------+

思路

join后加条件判断，用count(distinct Salary)来统计工资前三位

Order by 可以接多个字段

SELECT d.Name AS Department, e.Name AS Employee, e.Salary FROM Employee e
JOIN Department d on e.DepartmentId = d.Id
WHERE (SELECT COUNT(DISTINCT Salary) FROM Employee WHERE Salary > e.Salary
AND DepartmentId = d.Id) < 3 ORDER BY d.Name, e.Salary DESC;

186. Reverse Words in a String II (Medium)¶

给出一系列由空格分割的字符串，进行翻转

Input:  ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]
Output: ["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]

思路

先整体翻转，然后找到每个word，进行翻转即可

void reverseWords(vector<char>& str) {
    int ptr0 = 0, ptr1 = str.size() - 1;
    while (ptr1 > ptr0) swap(str[ptr0 ++], str[ptr1 --]);
    int ptr = 0, head = 0;
    while (ptr < str.size()) {
        if (ptr == str.size() - 1 || str[ptr + 1] == ' ') {
            int tail = ptr;
            while (head < tail) swap(str[head ++], str[tail --]);
            head = ptr + 2;
            ptr ++;
        }
        ptr ++;
    }
}

187. Repeated DNA Sequences (Medium)¶

给出一个DNA序列，求长度为10且出现不止一次的所有序列
Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output: ["AAAAACCCCC", "CCCCCAAAAA"]

思路

思路就是遍历来检查，但可以利用bitset来提高效率

做法为将ACGT映射为从0到3，都可以用2个bit来表达，所以长度为10的字符串可以转成一个20bit有数值的int，然后用bitset来置对应位

bitset操作为

reset(int pos); // 设一位为0
set(int pos, int val=1); // 设一位为1
flip(int pos); // 翻转一位

vector<string> findRepeatedDnaSequences(string s) {
    if (s.size() <= 10) return {};
    vector<string> res;
    bitset<1 << 20> s1, s2;
    int val = 0;
    for (int i = 0; i < 10; i ++) val = (val << 2) | char2val(s[i]);
    s1.set(val);
    int mask = (1 << 20) - 1;
    for (int i = 10; i < s.size(); i ++) {
        val = ((val << 2) & mask) | char2val(s[i]);  
        if (s2[val]) continue;
        else if (s1[val]) {
            res.push_back(s.substr(i - 9, 10));
            s2.set(val);
        }
        else s1.set(val);
    }
    return res;
}
int char2val(char c) {
    switch (c) {
        case 'A': return 0;
        case 'C': return 1;
        case 'G': return 2;
        case 'T': return 3;
    }
    return -1;
}

188. Best Time to Buy and Sell Stock IV (Hard)¶

有n天的股票价格数据，最多只能交易k次，求最大profit
Input: [3,2,6,5,0,3], k = 2
Output: 7
(6-2) + (3-0) = 7

思路

动归来做，开一个n位的数组profits，循环k次来更新，第j次循环时profits[i]表示到第i天为止完成最多j次交易的最大收益

更新方法也很简单，假设已经完成前j-1次循环，那么第i天卖出股票完成第j次交易所得的最大收益，就是第i天的价格加上前面max(profits[q]-prices[q]) q < i，所以过程中需要维持两个值

mx1: 当天完成j-1次的最大收益减去当天价格的最大值 mx2: 之前完成j次交易出现的最大收益

如例子，在完成一次交易后，各天所得的最大收益为0 0 4 4 4 4，之后过程为

mx2 = max(mx2, mx1 + prices[i]);
mx1 = max(mx1, profits[i] - prices[i]);
profits[i] = max(profits[i], mx);

day	mx1	mx2
0	-3	0
1	-2	0
2	-2	4
3	-1	4
4	4	4
5	4	7

要注意的是如果k >= prices.size() - 1，直接退化为求和所有delta即可

int maxProfit(int k, vector<int>& prices) {
    if (prices.size() < 2 || k == 0) return 0;
    if (k >= prices.size() - 1) {
        int result = 0;
        for (int i = 1; i < prices.size(); i ++)
            result += (prices[i] > prices[i-1]) ? prices[i] - prices[i - 1] : 0;
        return result;
    }
    vector<int> profits(prices.size(), 0);
    while (k --) {
        int mn = profits[0] - prices[0], mx = 0;
        for (int i = 1; i < prices.size(); i ++) {
            mx = max(mx, prices[i] + mn);
            mn = max(profits[i] - prices[i], mn);
            profits[i] = max(profits[i], mx);
        }
    }
    return profits.back();
}

189. Rotate Array (Easy)¶

给一个整数数组，向右移动k位，如下例

Input: [1,2,3,4,5,6,7] and k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

要求用

$O(1)$ 空间

思路一逐个替换

将第一个数向后挪k位，到第k%n位，然后将k%n位的数挪到2k%n上，依次进行

这里存在问题是可能粒度无法覆盖n个数，比如1 2 3 4 5 6挪4位，从第一位开始，1->5->3->1，从第1位出发只能移动3位，这时再改为从第2位出发，则完成整个移动

可以证明的是每次移动到出现重复，然后右移一位再移动，这样可以完成所有数的移动，直观上也可以想一下，就是固定一些位在一次可以被覆盖到，留下的空位也是有规律的，将第1位旁边的空位通过右移覆盖掉后，其它的空位也都会被覆盖掉

判断是否出现重复，看移动总位数是否被n整数即可，代码如下 $$ P® = \lim_{N \rightarrow \infty}\frac{r}{N}\sum_{n=r}^{{N-1}\frac{N}{n}\frac{1}{N}=x\int_{x}}{1}\frac{1}{t}dt=-x \ln x $$

void rotate(vector<int>& nums, int k) {
    if (nums.size() == 0) return;
    k %= nums.size();
    if (k == 0) return;
    int buf = nums[0], num = 0, ptr = 0, start = 0;
    long long s = 0;
    while (num < nums.size()) {
        s += k;
        num ++;
        int next = (ptr + k) % nums.size();
        swap(buf, nums[next]);
        ptr = next;
        if (s % nums.size() == 0) {
            cout << num << '\n';
            s = 0;
            ptr = ++ start;
            buf = nums[ptr];
        }
    }
}

思路二翻转

将后k位和前n-k位各自翻转，然后统一翻转即可，更简洁

比如1 2 3 4 5 6 7和k=3，先翻转成4 3 2 1 7 6 5，然后整体翻转，即5 6 7 1 2 3 4

代码如下

inline void reverse(vector<int>& nums, int l, int r) {
    while (l < r) swap(nums[l ++], nums[r --]);
}
void rotate(vector<int>& nums, int k) {
    if (nums.size() == 0) return;
    k %= nums.size();
    reverse(nums, 0, nums.size() - k - 1);
    reverse(nums, nums.size() - k, nums.size() - 1);
    reverse(nums, 0, nums.size() - 1);
}

190. Reverse Bits (Easy)¶

将一个unsigned int的所有位颠倒
Input: 00000010100101000001111010011100
Output: 00111001011110000010100101000000

思路

逐位操作即可

uint32_t reverseBits(uint32_t n) {
    uint32_t num = 32, res = 0;
    while (num --) res |= (((n >> num) & 1) << (31 - num));
    return res;
}

191. Number of 1 Bits (Easy)¶

对一个unsigned int，计算它包含的1个数

思路

32个位都求下即可

int hammingWeight(uint32_t n) {
    int res = 0, num = 32;
    while (num --) res += ((n >> num) & 1);
    return res;
}

192. Word Frequency (Medium)¶

Write a bash script to calculate the frequency of each word in a text file words.txt.

例如输入为
the day is sunny the the
the sunny is is
输出为
the 4
is 3
sunny 2
day 1

思路

tr -s ' ' '\n' 按字符分割

sort -rn n是按数字大小排序，r是逆序

cat words.txt | tr -s ' ' '\n' | sort | uniq -c | sort -rn | awk '{print $2" "$1}'

193. Valid Phone Numbers (Easy)¶

给一个文件file.txt，输出符合(xxx) xxx-xxxx or xxx-xxx-xxxx (x means a digit)模式的号码

思路

grep加正则表达式完成，这里-P选项表示用Perl形式的正则表达式

-P, --perl-regexp         PATTERN is a Perl regular expression

grep -P '^(\d{3}-|\(\d{3}\) )\d{3}-\d{4}$' file.txt

194. Transpose File (Medium)¶

将输入文件file.txt转置输出
input:
name age
alice 21
ryan 30
output:
name alice ryan
age 21 30

思路

awk判断连接即可，注意这里awk总是逐行处理的

awk '{for(i=1;i<=NF;i++) if(NR==1) a[i]=$i;else a[i]=(a[i]" "$i);} END{for (i in a) print a[i];}' file.txt

195. Tenth Line (Easy)¶

给定一个文件file.txt，输出它的第十行

思路

awk加if判断即可

cat file.txt | awk '{if(NR==10){print $0;}}'

196. Delete Duplicate Emails (Easy)¶

从表Person中删除重复的邮箱，保留最小Id，如下

+----+------------------+
| Id | Email            |
+----+------------------+
| 1  | john@example.com |
| 2  | bob@example.com  |
| 3  | john@example.com |
+----+------------------+
return
+----+------------------+
| Id | Email            |
+----+------------------+
| 1  | john@example.com |
| 2  | bob@example.com  |
+----+------------------+

思路

group by来得到最小Id，然后再把Id集合起来，再删除不在其中的项即可

用两次嵌套

DELETE FROM Person WHERE  Id NOT IN(
     SELECT Id FROM(
         SELECT MIN(Id) AS Id FROM Person GROUP BY Email
     ) AS p
)

197. Rising Temperature (Easy)¶

给出一个Weather表，求比昨天温度高的Id，如下例

+---------+------------------+------------------+
| Id(INT) | RecordDate(DATE) | Temperature(INT) |
+---------+------------------+------------------+
|       1 |       2015-01-01 |               10 |
|       2 |       2015-01-02 |               25 |
|       3 |       2015-01-03 |               20 |
|       4 |       2015-01-04 |               30 |
+---------+------------------+------------------+
Return
+----+
| Id |
+----+
|  2 |
|  4 |
+----+

思路

TO_DAYS可以将Date转换成天数

select t.Id from Weather t join Weather y on TO_DAYS(t.RecordDate) - TO_DAYS(y.RecordDate) = 1 and t.Temperature > y.Temperature

198. House Robber (Easy)¶

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

抢劫非连续房间，最大收益

思路

DP

int rob(vector<int>& nums) {
    if (nums.size() == 0) return 0;
    if (nums.size() == 1) return nums[0];
    if (nums.size() > 2) nums[2] += nums[0];
    for (int i = 3; i < nums.size(); i ++) nums[i] += max(nums[i-2], nums[i-3]);
    return max(nums[nums.size()-1], nums[nums.size()-2]);
}

199. Binary Tree Right Side View (Medium)¶

给一棵二叉树，返回从右侧看这棵树看到的所有结点

Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation:
   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

思路

层次遍历，每次加入最右端元素即可

vector<int> rightSideView(TreeNode* root) {
    vector<int> res;
    if (root == nullptr) return res;
    deque<TreeNode*> q;
    q.push_back(root);
    while (!q.empty()) {
        res.push_back(q.back()->val);
        int s = q.size();
        while (s --) {
            TreeNode* node = q.front();
            q.pop_front();
            if (node->left != nullptr) q.push_back(node->left);
            if (node->right != nullptr) q.push_back(node->right);
        }
    }
    return res;
}

200. Number of Islands (Medium)¶

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Input:
11000
11000
00100
00011
Output: 3

DFS

记录已经访问过的点，然后dfs即可，这里bfs也可以

void dfs(vector<vector<bool> >& visit, vector<vector<char>>& grid, int i, int j, int m, int n) {
    visit[i][j] = 1;
    if (j > 0 && !visit[i][j-1] && grid[i][j-1] == '1') dfs(visit, grid, i, j-1, m, n);
    if (i > 0 && !visit[i-1][j] && grid[i-1][j] == '1') dfs(visit, grid, i-1, j, m, n);
    if (i < m - 1 && !visit[i+1][j] && grid[i+1][j] == '1') dfs(visit, grid, i+1, j, m, n);
    if (j < n - 1 && !visit[i][j+1] && grid[i][j+1] == '1') dfs(visit, grid, i, j+1, m, n);
}
int numIslands(vector<vector<char>>& grid) {
    if (grid.size() == 0 || grid[0].size() == 0) return 0;
    vector<vector<bool> > visit;
    int m = grid.size(), n = grid[0].size();
    for (int i = 0; i < m; i ++) visit.push_back(vector<bool>(n, false));
    int result = 0;
    for (int i = 0; i < m; i ++)
        for (int j = 0; j < n; j ++)
            if (!visit[i][j] && grid[i][j] == '1') {
                dfs(visit, grid, i, j, m, n);
                result ++;
            }
    return result;
}

并查集

set[find(x)] = find(y)这一句就可以合并两个集合

int find(vector<int>& set, int rank) {
    while (set[rank] != rank) rank = set[rank];
    return rank;
}
int numIslands(vector<vector<char>>& grid) {
    if (grid.size() == 0 || grid[0].size() == 0) return 0;
    int m = grid.size(), n = grid[0].size();
    vector<int> set;
    for (int i = 0; i < m*n; i ++) set.push_back(i);
    for (int i = 0; i < m; i ++)
        for (int j = 0; j < n; j ++) {
            int x = i*n + j;
            if (grid[i][j] == '0') set[x] = -1;
            else {
                if (j > 0 && grid[i][j-1] == '1') set[find(set, x)] = find(set, x-1);
                if (i > 0 && grid[i-1][j] == '1') set[find(set, x)] = find(set, x-n);
            }
        }
    unordered_map<int, int> map;
    int result = 0;
    for (int i = 0; i < m*n; i ++) {
        if (set[i] == -1) continue;
        else if (!map.count(find(set, i))) map[find(set, i)] = result ++;
    }
    return result;
}

1