GuoXin Li's Blog

LeetCode TIPS

LeetCode
字数统计: 16.2k阅读时长: 86 min
2021/11/29 Share

LeetCode OWNTIPS

Type C++ Java
array T dirs[n] T[] dirs = new T[n]
dynamic array vector\ ArrayList\
list list\ LinkedList\
OrderedSet \ OrderedMap set\, map\ TreeSet\, TreeMap\
HashSet \ HashMap unordered_set\, unordered_map\ HashSet\, HashMap\
heap priority_queue\ PriorityQueue\
queue, deque queue\, deque\ Queue\, Deque\
stack stack\ Stack\
pair \ tuple pair\, tuple\ N/A
customized struct , class , long class

Screen Shot 2022-04-04 at 11.15.00

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
//蓝红左右双指针二分法
int findRight(vector<int>& nums, int target){
    int l = -1, r = nums.size();
    while(l + 1 != r){
        int mid = l + (r - l ) / 2;
        // isBlue  <= 
        if(nums[mid] <= target){
            l = mid;
        }else{
            r = mid;
        }
    }
    return l;
}

int findLeft(vector<int>& nums, int target){
    int l = -1, r = nums.size();
    while(l + 1 != r){
        int mid = l + (r - l ) / 2;
        // isBlue  < 
        // isRed >= target --> left is right first;
        if(nums[mid] < target){
            l = mid;
        }else{
            r = mid;
        }
    }
    return r;
}


//单调递增区间查找某个值
public int bsearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    // 找不到target返回-1
    return -1;
}

//单调区间查找第一个大于等于某个值的元素
public static int bsearch1(int[] nums, int target) {
    int left = 0, right = nums.length;
    while(left < right){
        int mid = left + (right - left) / 2;
        if(nums[mid] < target){
            left = mid + 1;
        }else{
            right = mid;
        }
    }
    if(left == nums.lenght){
        return -1;
    }
    return left;
}

//单调区间查找第一个小于等于某个值的元素
public static int bsearch1(int[] nums, int target) {
    int left = 0, right = nums.length;
    while(left < right){
        int mid = left + (right - left) / 2;
        if(nums[mid] > target){
            right = mid;
        }else{
            left = mid + 1;
        }
    }
    if(left = 0){
        return -1;
    }
    return left - 1;
}

nSum 之和问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
    public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        // n 为 4，从 nums[0] 开始计算和为 target 的四元组
        return nSumTarget(nums, 4, 0, target);
    }

    /* 注意：调用这个函数之前一定要先给 nums 排序 */
    // n 填写想求的是几数之和，start 从哪个索引开始计算（一般填 0），target 填想凑出的目标和
    vector<vector<int>> nSumTarget(
            vector<int>& nums, int n, int start, long target) {

        int sz = nums.size();
        vector<vector<int>> res;
        // 至少是 2Sum，且数组大小不应该小于 n
        if (n < 2 || sz < n) return res;
        // 2Sum 是 base case
        if (n == 2) {
            // 双指针那一套操作
            int lo = start, hi = sz - 1;
            while (lo < hi) {
                int sum = nums[lo] + nums[hi];
                int left = nums[lo], right = nums[hi];
                if (sum < target) {
                    while (lo < hi && nums[lo] == left) lo++;
                } else if (sum > target) {
                    while (lo < hi && nums[hi] == right) hi--;
                } else {
                    res.push_back({left, right});
                    while (lo < hi && nums[lo] == left) lo++;
                    while (lo < hi && nums[hi] == right) hi--;
                }
            }
        } else {
            // n > 2 时，递归计算 (n-1)Sum 的结果
            for (int i = start; i < sz; i++) {
                vector<vector<int>>
                        sub = nSumTarget(nums, n - 1, i + 1, target - nums[i]);
                for (auto& arr : sub) {
                    // (n-1)Sum 加上 nums[i] 就是 nSum
                    arr.emplace_back(nums[i]);
                    res.emplace_back(arr);
                }
                while (i < sz - 1 && nums[i] == nums[i + 1]) i++;
            }
        }
        return res;
    }
};

时间复杂度分析：

  • 对于两数之和，双指针操作时间复杂度为 O(N)，排序为 Nlog(N) —> 总时间复杂度为 Nlog(N)
  • 对于三数之和，因为有循环调用所以为 O (Nlog(N) (排序) + N^2(循环调用) ) = O(N^2)
  • 对于四数之和，同上分析多了一层循环调用，为 O(N^3)

快慢指针

1
2
3
4
5
6
7
8
9
10
11
12
bool isLoop(ListNode *head){
  ListNode *slow, *fast;
  slow = fast = head;
  while(fast != nullptr && fast->next->next != nullptr ){
        slow = slow->next;
    fast = fast->next->next;
    if(slow == fast){
      return true;
    }
  }
  return false;
}

合并两个链表

dump 指针的妙用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ListNode* mergeTwoList( ListNode* l1, ListNode* l2){
  ListNode* dump = new ListNode(-1);
  while(l1 != nullptr && l2 != nullptr){
    if(l1->val < l2->val){
      dump->next = l1;
      l1 = l1->next;
    }else{
      dump->next = l2;
      l2 = l2->next;
    }
  }
  dump->next = l1 == nullptr ? l2 : l1;
  return dump->next;
}

滑动窗口

  • 通常多是循环整个流水线

    • 右窗口移动时的条件：

      窗口未满足条件

      右窗口移动时，该做什么？添加谁，删除谁？

    • 左窗口移动的条件：

      窗口满了？

      需要删除什么元素？

    • 什么时间添加 ans 结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ans;
        deque<int> q;
        for(int right = 0; right < nums.size(); right++){
            while(!q.empty() && nums[right] >= nums[q.back()] ){
                q.pop_back();
            }
            q.push_back(right);

            int left = right - k + 1;
            while(!q.empty() && left > q.front() ){
                q.pop_front();
            }
          // right + 1 >= k 时，代表窗口已经形成，即已经满足窗口大小，再往后移动每一步都会满足一个窗口的大小。
            //由于下标是从0开始的，所以当right+1>=k时，意味着窗口形成。
            if(right + 1 >= k){
                ans.push_back(nums[q.front()]);
            }
        }
        return ans;
    }
};

优先队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
      //priority_queue 容器默认为按照元素值从大到小进行排序
        priority_queue<pair<int, int>> q;
        for (int i = 0; i < k; ++i) {
            q.emplace(nums[i], i);
        }
        vector<int> ans = {q.top().first};
        for (int i = k; i < n; ++i) {
            q.emplace(nums[i], i);
            while (q.top().second < i - k + 1) {
                q.pop();
            }
            ans.push_back(q.top().first);
        }
        return ans;
    }
};

二叉树的迭代-非递归遍历

思想即：

中左右，左中右，左右中。

利用 stack 来先入后出，即入栈的顺序与上述相反，记住此即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        if (root != NULL) st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            if (node != NULL) {
                st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                if (node->right) st.push(node->right);  // 添加右节点（空节点不入栈）

                st.push(node);                          // 添加中节点
                st.push(NULL); // 中节点访问过，但是还没有处理，加入空节点做为标记。

                if (node->left) st.push(node->left);    // 添加左节点（空节点不入栈）
            } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop();           // 将空节点弹出
                node = st.top();    // 重新取出栈中元素
                st.pop();
                result.push_back(node->val); // 加入到结果集
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
class TreePrint{
public:
        vector<int> preTreeorder(TreeNode* root){
          std::stack<TreeNode *> mystack;
          std::vector<int> ans;
          if( root != nullptr ){
                mystack.emplace(root);
             }else{
                return ans;
      }
      while( !mystack.empty() ){
          TreeNode* p = mystack.top();
          mystack.pop();
          if(p!=nullptr){
              if(p->right){
                    mystack.emplace(p->right);
              }
              if(p->left){
                    mystack.emplace(p->left);
              }
              mystack.emplace(p);
              mystack.emplace(nullptr);
          }else{
                p = mystack.top();
                mystack.pop();
                ans.push_back(p->val);
          }
      }
    }  

  vector<int> inOrder(TreeNode* root){
        std::stack<TreeNode *> mystack;
        std::vector<int> ans;
        if(root != nullptr){
            mystack.emplace(root);
      }else{
            return ans;
      }
        while(!mystack.empty()){
            TreeNode* p = mystack.top();
            mystack.pop();
            if(p != nullptr){
                if(p->right != nullptr ){
                    mystack.emplace(p->right);
              }
                mystack.emplace(p);
                mystack.emplace(nullptr);
                if(p->left != nullptr){
                    mystack.emplace(p->left);
              }
          }else{
                p = mystack.top();
                mystack.pop();
                ans.push_back(p->val);
          }
      }
        return ans;
      }

    vector<int> postOrder(TreeNode* root){
        std::stack<TreeNode *> mystack;
        std::vector<int> ans;
      //judge root whether is nullprt or not
        if(root != nullptr){
            mystack.emplace(root);
      }else{
            return ans;
      }
      //push into stack
        while(!mystack.empty()){
            TreeNode* p = mystack.top();
            mystack.pop();
            if(p != nullptr){
              mystack.emplace(p);
                mystack.emplace(nullptr);
              if(p->right != nullptr ){
                    mystack.emplace(p->right);
              }
              if(p->left != nullptr){
                    mystack.emplace(p->left);
              }
          }else{    // important: when to output and merge into anwser
                p = mystack.top();
                mystack.pop();
                ans.push_back(p->val);
          }
      }
        return ans;
  }

};

二叉树

二叉树题目的一个难点就是，如何把题目的要求细化成每个节点需要做的事情

构造最大树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
TreeNode* constructMaximumBinarytree(int &num[]){
      return buildTree( num, 0, num.size() - 1 );
}
TreeNode* buildTree(int num[], int low, int high){
      if(low > high){
          return nullptr;
    }
      int maxValue = MAX_INT;
      int index = -1;
      for(int i = low; i <= high; i++){
            if(maxValue < num[i]){
                maxValue = num[i];
              index = i;
        }
    }
      TreeNode* root = new TreeNode(maxValue);
      root->left = buildTree(num, low, index-1);
      root->right = buildTree(num, index+1, high);
      return root;
}

通过前序遍历中序遍历来构造二叉树

image-20211212212719158

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
TreeNode* treeBuildTree( int& preorder, int& inorder ){
    return build(preorder, 0, preorder.size() - 1 , 
                 inorder, 0, inorder.size() - 1 )
}
TreeNode* build(int& preorder[], int preStart, int preEnd, int& inorder[], int inStart, int inEnd){
    //base case: 
    if(preStart < preEnd || inStart < inEnd ){
        return nullptr;
    }
    int rootvalue = preorder[preStart];
    TreeNode* root = new TreeNode(rootValue);
    int index = -1;
    // find the index in order array;
    for(int i = inStart; i <= inEnd; i++){
        if(rootValue = inorder[i] ){
            index = i;
            break;
        }
    }
    // manage the root->left and root->right;
    int leftsize = index - preStart;
    root->left = build( preorder, preStart + 1, preStart + leftsize, 
                        inorder, inStart, index -1 );
    root->right = build(preorder, preStart + leftsize + 1, preEnd,
                        inorder, index + 1, inEnd );
    return root;
}

通过中序遍历后序遍历来构造二叉树

Screen Shot 2021-12-12 at 21.27.29

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
TreeNode* treeBuildTree( int& preorder, int& inorder ){
    return build(preorder, 0, preorder.size() - 1 , 
                 inorder, 0, inorder.size() - 1 )
}
TreeNode* build(int& postorder[], int posStart, int posEnd, int& inorder[], int inStart, int inEnd){
    //base case: 
    if(posStart < posEnd || inStart < inEnd ){
        return nullptr;
    }
    int rootvalue = posorder[posEnd];
    TreeNode* root = new TreeNode(rootValue);
    int index = -1;
    // find the index in order array;
    for(int i = inStart; i <= inEnd; i++){
        if(rootValue = inorder[i] ){
            index = i;
            break;
        }
    }
    // manage the root->left and root->right;
    int leftsize = index - preStart;
    root->left = build( posorder, posStart, posStart + leftsize - 1 , 
                        inorder, inStart, index -1 );
    root->right = build(posorder, posStart + leftsize, posEnd - 1,
                        inorder, index + 1, inEnd );
    return root;
}

寻找重复的子树

通过深度优先搜索，递归所有的子树的序列化的结果，并将其保存到 map 中，然后判断是否存在重复的子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solutio{
public:
    vector<TreeNode* > findDuplicateSubtrees(TreeNode* root){
        std::vector<TreeNode*> ans;
        std::unordered_map<string, int> mp;
        buildMap(root, mp, ans);
        return ans;
    }
    string buildMap(TreeNode* root, std::unordered_map<string, int>& mp, std::vector<TreeNode*>& ans){
        if(root == nullptr){
            return "";
        }
        string str = to_string( root->val ) + buildMap(root->left, mp, ans) + buildMap(root->right, mp, ans);
        if(mp[str] == 1){
            ans.emplace_back(root);
        }
        mp[str]++;
        return str;
    }
}

二叉树的序列化与反序列化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(root==nullptr){
            return "#";
        }
        return to_string(root->val) + ' ' + serialize(root->left) + ' ' + serialize(root->right);
    }

    TreeNode* mydeserialize(istringstream &ss ){
        string tmp;
        ss>>tmp;
        if(tmp=="#"){
            return nullptr;
        }
        TreeNode* node = new TreeNode(stoi(tmp));
        node->left = mydeserialize(ss);
        node->right = mydeserialize(ss);
        return node;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        istringstream ss(data);
        return mydeserialize(ss);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
       if(root == nullptr){
           return "#";
       } 
       return to_string(root->val) + ',' + serialize(root->left) + ',' + serialize(root->right);
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
       list<string> list = splitString(data, ','); 
       TreeNode* ans = buildTree(list);
       return ans;
    }
    TreeNode* buildTree(list<string>& list){
        if(list.empty()){
            return nullptr;
        }
        string temp = list.front();
        list.pop_front();
        if(temp == "#"){
            return nullptr;
        } 
        TreeNode* root = new TreeNode(stoi(temp));
        root->left = buildTree(list);
        root->right = buildTree(list);
        return root;
    }
    list<string> splitString(string& data, char c){
        list<string> res;
        for(int frontpot = -1,  pos = 0; pos < data.length(); pos++){
            if(data[pos] == c){
                res.emplace_back( data.substr(++frontpot, pos-frontpot) );
                frontpot = pos;
            }
        }
        return res;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));

二叉搜索子树的最大键值和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxSumBST(TreeNode* root) {
         vector<int> ans;
         int maxSum = 0;
         ans = tranverse(root, maxSum );
         return maxSum;
    }
    vector<int> tranverse(TreeNode* root, int& maxSum){
        if(root == nullptr){
            vector<int> temp{1,INT_MAX, INT_MIN, 0};
            return temp;
        }
        vector<int> left;
        vector<int> right;
        vector<int> res(4,-1);
        left = tranverse(root->left, maxSum);
        right = tranverse(root->right, maxSum);

        if(left[0] == 1 && right[0] == 1 && root->val > left[2] && root->val < right[1] ){
            res[0] = 1;
            res[1] = min( left[1], root->val );
            res[2] = max( right[2], root->val );
            res[3] = left[3] + right[3] + root->val;
            maxSum = max( res[3], maxSum);
        }else{
            res[0] = 0;
        }
        return res;
    }
};

二叉树的最近公共祖先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == nullptr){
            return nullptr;
        }
        if(root == p || root == q) {
            return root;
        }
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);

        if(left != nullptr && right != nullptr){
            return root;
        }
        if(left == nullptr && right == nullptr ){
            return nullptr;
        }
        return left == nullptr ? right : left;
    }
};

using postorder traversal to calculate the further node left and right.

完全二叉树节点个数

  • 完全二叉树：在完全二叉树中，除了最底层节点可能没有填满之外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。
  • 满二叉树，即所有节点都满，共有 $2^{i}-1$个节点，第 i 层上有 $2^{i-1}$个节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int countNodes(TreeNode* root) {
        TreeNode *l = root, *r = root;
        int hl = 0, hr = 0;
        while(l != nullptr){
            hl++;
            l = l->left;
        } 
        while(r != nullptr){
            hr++;
            r = r->right;
        } 
        if( hl == hr){
            return (pow(2, hl) - 1);
        }
        return ( 1 + countNodes(root->left) + countNodes(root->right) );
    }
};

图

图节点：（同多叉树）

1
2
3
4
class Vertex{
    int id;
    Vertex[] neighbors;
}

临接表和临接矩阵：

1
2
List<int[]>[] graph;
int[][] matrix;

多叉树-图的遍历方式

1
2
3
4
5
6
void traverse(TreeNode root){
    if(root == null) return;
    for(TreeNode child : root.children){
        traverse(child);
    }
}

若图中含有环：

1
2
3
4
5
6
7
8
9
10
11
boolean[] visited;
boolean[] onPath;
void traverse(Graph graph, int s){
    if(visited[s]) return;
    visted[s] = true;
    onPath[s] = true;
    for(int neighbor : graph.neighbors(s)){
        traverse(graph, neighbor);
    }
    onPath[s] = false;
}

所有可能的路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    List<List<Integer>> res = new LinkedList<>();
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        LinkedList<Integer> path = new LinkedList<>();
        traverse(graph, 0, path);
        return res;
   }
   public void traverse(int[][] graph, int s, LinkedList<Integer> path){
       path.add(s);
       int n = graph.length;
       if(s == n - 1 ){
           res.add(new LinkedList<Integer>(path));
           path.removeLast();
           return;
       }
       for(int v : graph[s]){
           traverse(graph, v, path);
       }
        path.removeLast();
}

课程表问题建图函数

1
2
3
4
5
6
7
8
9
10
11
12
List<Integer>[] buildGraph(int numCourses, int[][] prerequisites){
    // nodes of the map, its number is numCourses
    List<Integer>[] graph = new LinkedList[numCourses];
    for(int i = 0; i < numCourses; i++){
        graph[i] = new LinkedList<>();
    }
    for(int[] edge : prerequsities){
        int from = edge[1], to = edge[0];
        graph[from].add(to);
    }
    return graph;
}

注意：List<Integer>[] graph = new LinkdList[numCourses]; 的使用。

判断图是否有环的 DFS 算法

对应 课程表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
boolean[] onPath;
boolean[] visited;
boolean hasCycle = false;

boolean canFinish(int numCourses, int[][] prerequsities){
    List<Integer>[] graph = buildGraph(numCourses, prerequsities);
    visited = new boolean[numCourses];
    onPath = new boolean[numCourses];
    for(int i = 0; i < numCourses; i++){
        traverse(graph, i);
    }
    return !hasCycle;
}
public void traverse(List<Integer>[] graph, int s){
    if(onPath[s]){
        hasCycle = true;
    }
    if(hasCycle || visited[s]){
        return;
    }
    visited[s] = true;
    onPath[s] = true;
    for(int v : graph[s]){
        traverse(graph, v);
    }
    onPath[s] = false;
}

对应课程表II 后续遍历进行反转就是拓扑排序的结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
boolean[] onPath;
boolean[] visited;
List<Integer> postorder = new ArrayList<>();
boolean hasCycle = false;

public int[] findOrder(int numCourses, int[][] prerequsities){
    List<Integer>[] graph = buildGraph(numCourses, prerequsities);
    visited = new boolean[numCourses];
    onPath = new boolean[numCourses];

    for(int i = 0; i < numCourses; i++){
        traverse(graph, i);
    }
    if(hasCycle){
        return new int[]{};
    }
    Collections.reverse(postorder);
    int[] res = new int[numCourses];
    for(int i = 0; i < numCourses; i++){
        res[i] = postorder.get(i);
    }
    return res;
}
public void traverse(List<Integer>[] graph, int s){
    if(onPath[s]){
        hasCycle = true;
    }
    if(hasCycle || visited[s]){
        return;
    }
    visited[s] = true;
    onPath[s] = true;
    for(int v : graph[s]){
        traverse(graph, v);
    }
    postorder.add(s);
    onPath[s] = false;
}

判断二分图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    private boolean isB = true;
    private boolean[] color;
    private boolean[] visited;
    public boolean isBipartite(int[][] graph) {
        color = new boolean[graph.length];
        visited = new boolean[graph.length];
        for(int i = 0; i < graph.length; i++){
            if(!visited[i]){
                traverse(graph, i);
            }
        }
        return isB;
    }
    public void traverse(int[][] graph, int s){
        if(!isB) return;
        visited[s] = true;        //重点在于先进行访问标记，然后再进行判断。
        for(int v : graph[s]){
            if(!visited[v]){
                color[v] = !color[s];
                traverse(graph, v);
            }else{
                if(color[v] == color[s]){
                    isB = false;
                }
            }
        }
    }
}

先进行访问，可能已经访问过的，但不马上进行返回而是判断其后续节点有没有相同的颜色。

可能的二分法 链接给定一组 n 人（编号为 1, 2, ..., n）， 我们想把每个人分进任意大小的两组。每个人都可能不喜欢其他人，那么他们不应该属于同一组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
    boolean OK = true;
    boolean[] visited;
    boolean[] color;
    public boolean possibleBipartition(int n, int[][] dislikes) {
        List<Integer>[] graph = new LinkedList[n+1];
        visited = new boolean[n+1];
        color = new boolean[n+1];
        graph = buildGraph(dislikes, n);
        for(int i = 1; i < n+1; i++){
            traverse(graph, i);
        }
        return OK;

    }
    //建图函数
    private List<Integer>[] buildGraph(int[][] dislikes, int n){
        List<Integer>[] graph = new LinkedList[n+1];
        for(int i = 1; i < n+1; i++){
             graph[i] = new LinkedList<>();
        }
        for(int[] edge : dislikes){
            //无向图相当于双向图
            int from = edge[0];
            int to = edge[1];
            graph[from].add(to); 
            graph[to].add(from); 
        }
        return graph;
    }
    private void traverse(List<Integer>[] graph, int s){
        if(!OK) return;
        visited[s] = true;
        for(int v : graph[s]){
            if(!visited[v]){
                color[v] = !color[s];
                traverse(graph, v);
            }else{
                if(color[v] == color[s]){
                    OK = false;
                }
            }
        }
    }
}

并查集算法 (Union-Find)

动态连通性：

1～9个节点，

1
2
3
4
5
6
7
8
class UnionFind{
    //将节点 p，q进行连接
    void union(int p, int q);
    //判断节点 p q 是否连接 
    bool connected(int p, int q);
    //返回图中的连通分量
    int count();
}

如果增加图中某个相互连通的节点，那么图中的连通分量就会少一个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class UF{
    //连通分量
    private int count;
    //存储每个节点的父节点
    private int[] parent;
    //构造函数
    public UF(int n){
        this.count = n;
        for(int i = 0 ; i < n; i++){
            parent[i] = i;
            //*********添加此是为了进行大小树的优化，以此判断某个节点下包含多少节点（即数量）
            size[i] = 1;
        }
    }
    //将节点 p，q 进行连通
    public void union(int p, int q){
        int rootP = find(p);
        int rootQ = find(q);
        if(rootP == rootQ) return;
         //进行连通的时候使用了size进行大小判断，可以保证 find 的时间复杂度为 O(N) 
        if(size[rootP] > size[rootQ]){
            parent[rootQ] = rootP;
            size[rootP] += size[rootQ]
        }else{
            parent[rootP] = rootQ;
            size[rootQ] += size[rootP]
        }
        count--;
    }

    //判断节点 p，q 是否连通
    public void connected(int p, int q){
        int rootP = find(p);
        int rootQ = find(q);
        return rootP == rootQ;
    }

    //返回节点 x 的连通分量的根节点

        //使用了 parent[x] = parent[parent[x]] 路经压缩技巧
    private int find(int x){
        while(parent[x] != x){
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x
    }
    // 返回图中连通个数
    public int returnCount(){
        return count;
    }
}

力扣第 323 题「 无向图中连通分量的数目」就是最基本的连通分量题目：

给你输入一个包含 n 个节点的图，用一个整数 n 和一个数组 edges 表示，其中 edges[i] = [ai, bi]表示图中节点 ai 和 bi 之间有一条边。请你计算这幅图的连通分量个数。

1
2
3
4
5
6
7
8
9
10
11
public int countComponents(int n, int[][] edges){
    UF uf = new UF(n);
    for(int[] e : edges){
        uf.union(e[0], e[1]);
    }
    return uf.count();
}

class UF{
    ...
}

给你一个 M×N 的二维矩阵，其中包含字符 X 和 O，让你找到矩阵中四面被 X 围住的 O，并且把它们替换成 X 130. 被围绕的区域

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//DFS 解法
class Solution {
    public void solve(char[][] board) {
        if(board == null || board.length == 0) return;
        int n = board.length;
        int m = board[0].length;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                boolean isEdge = i == 0 || i == n - 1 || j == 0 || j == m -1;
                if(isEdge && board[i][j] == 'O' ){
                    dfs(board, i, j);
                }
            }
        }
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(board[i][j] == 'O'){
                    board[i][j] = 'X';
                }
                if(board[i][j] == '#'){
                    board[i][j] = 'O';
                }

            }
        }
    }
    public void dfs(char[][] board, int i , int j){
        if(i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] == 'X' || board[i][j] == '#'){
            return;
        }
        board[i][j] = '#';
        dfs(board, i - 1, j);
        dfs(board, i + 1, j);
        dfs(board, i, j - 1);
        dfs(board, i, j + 1);
    }
}

990. 等式方程的可满足性

用并查集的方法来解决，现将 == 条件的进行连通，然后再进行 != 的连通，如果此过程中，存在==，则有冲突的存在。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
boolean equationPossible(String[] equations){
    UF uf = new UF(26);
    for(String eq : equations){
        if(eq.charAt[1] == '='){
            char x = eq.charAt(0);
            char y = eq.charAt(3);
            uf.union(x - 'a', y - 'a');
        }
    }
    //检查 != 关系
   for(String eq : equations){
        if(eq.charAt[1] == '！'){
            char x = eq.charAt(0);
            char y = eq.charAt(3);
            if(uf.connected(x - 'a', y - 'a')){
                return false;
            }
        }
    }
}
class UF{}

kruskal最小生成树

prime算法：选择与已知相连中最小的边，不能构成环。

kruskal算法：选择边最小的，无需与已知相连，不能构成环。

以图判树

给你输入编号从 0 到 n - 1 的 n 个结点，和一个无向边列表 edges（每条边用节点二元组表示），请你判断输入的这些边组成的结构是否是一棵树。

产生树的条件是不能够产生环。

即在生成树的过程中如果两个节点在之前已经是连通的（处在同一个连通分量里）那么就会产生环。

利用 Union-Find 算法：

1
2
3
4
5
6
7
8
9
10
11
12
boolean validTree(int n, int[][] edges){
    UF uf = new UF(n);
    for(int [] e : edges){
        int x = e[0];
        int y = e[1];
        if(uf.connected(x,y)){
            return false;
        }
        uf.union(x,y);
    }
    return uf.count() == 1;        //保证最后的树为一个树，只有一个连通分量。
}

最低成本的联通所有城市

Image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int minimumCost(int n, int[][] connections ){
    UF uf = new UF(n+1);    // 1~n
    Array.sort(connections, (a,b)->(a[2] - b[2]) );
    int mst = 0;
    for(int edge : connections){
        int x = edge[0];
        int y = edge[1];
        int v = edge[2];
        if(uf.connected(x, y)){
            return false;
        }
        uf.connected(x, y);
        mst += v;
    }
    return uf.count() == 2 ? mst : -1;
}
class UF{}

1584. 连接所有点的最小费用

kruskal 算法，适合边少点多的稀疏图。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution {
    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        List<int[]> edges = new ArrayList<>();
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                edges.add(new int[]{
                    i, j, Math.abs( points[i][0] - points[j][0])+Math.abs(points[i][1] - points[j][1])
                });
            }
        }
        //排序，使用 lambda 
        Collections.sort(edges, (a,b)->(a[2] - b[2]) );
        // Collections.sort(edges, (a,b)->{
        //     return a[2] - b[2];
        // } );
        int mst = 0;
        UF uf = new UF(n);
        for(int[] edge : edges){
            int x = edge[0];
            int y = edge[1];
            int w = edge[2];
            if(uf.connected(x, y)){
                continue;
            }
            uf.union(x, y);
            mst += w;
        }
        return mst;
    }
}
class UF{
    private int[] parent;

    public UF(int n){
        parent = new int[n];
        for(int i = 0; i < n; i++){
            parent[i] = i;
        }
    }
    public int find(int index){
        while(parent[index] != index){
            parent[index] = parent[parent[index]];
            index = parent[index];
        }
        return index;
    }
    public boolean connected(int x, int y){
        int rootX = find(x); 
        int rootY = find(y); 
        return rootX == rootY;
    }
    public void union(int x, int y){
        int rootX = find(x);
        int rootY = find(y);
        if(rootX == rootY) return;
        parent[rootX] = rootY;
    }
}

Prim算法：

该算法以顶点为单元，与图中的边数无关，比较适合稠密图。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Prim{
    //优先队列存储边
    private PriorityQueue<int[]> pq;
    //记录哪些节点已经成为最小生成树的一部分
    private boolean[] inMST;
    //记录最小生成树的权重
    private int weightSum = 0;
    //graph 为用临接表表示的一幅图。graph[s] 记录节点S的所有相邻边。
    //int[]{from, to, weight}表示为一条边
    private List<int[]>[] graph;

    public Prime(List<int[]>[] graph){
        this.graph = graph;
        this.pq = new PriorityQueue<>( (a,b)->{
            return a[2] - b[2];
        } );
        int n = graph.length;
        this.inMST = new boolean[n];

        //从第一个点开始切分
        minMST[0] = true;
        cut(0);
        while(!pq.isEmpty()){
            int[] edge = pd.poll();
            int to = edge[1];
            if(inMST[to]){
                continue;
            }
            inMST[to] = true;
            weightSum += edge[2];
            cut(to);
        }
    }
    //将s的横向切向边加入优先队列
    private void cut(int s){
        for(int[] edge : graph[s]){
            int to = edge[1];
            if(inMST[to]){
                continue;
            }
            pd.offer(edge);
        }
    }
    private int returnWeight(){
        return weightSum;
    }
    //判断最小生成树是否包含图中的所有的节点
    public boolean allConnected(){
        for(int i = 0; i < graph.length; i++){
            if(!inMST[i]){
                return false;
            }
        }
        return true;
    }
}

名流问题

名流条件：

  • 所有其他人都认识「名人」
  • 名人不认识其他所有人

图论关系：

  • 临接表：适合存储，节约存储空间
  • 邻接矩阵：快速判断两个节点是否相邻

通过暴力解法双层循环判断

1
2
3
4
5
6
7
8
9
10
11
12
13
int findCele(int n){
    for(int cand = 0; cand < n; cand++){
        int other;
        for(other = 0; other < n; other++){
            if(cand == other) continue;
            if(knows(cand, other) || !know(other, cand)){
                break;
            }
        }
        //当满足所有人都认识名人，而名人不认识所有人
        if(other == n) return cand;
    }
}

优化解法：

只需要判断任意两个人之间的关系：

  • cand 认识 other，other 不认识 cand –> 排除 cand
  • cand 不认识 other，other 认识 cand –> 排除 other
  • cand other 互相认识，两人都不是名人 –> 随便排除一人
  • cand other 互不认识，两人都不是名人 –> 随便排除一人
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int findCelebrity(int n) {
    if (n == 1) return 0;
    // 将所有候选人装进队列
    LinkedList<Integer> q = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        q.addLast(i);
    }
    // 一直排除，直到只剩下一个候选人停止循环
    while (q.size() >= 2) {
        // 每次取出两个候选人，排除一个
        int cand = q.removeFirst();
        int other = q.removeFirst();
        // cand 一定不是名人的条件：cand 认识 other ，或 other 不认识 cand
        //cand 认识 other，other不认识 cand
        if (knows(cand, other) || !knows(other, cand)) {
            // cand 不可能是名人，排除，让 other 归队
            q.addFirst(other);
        } else {    //其余情况下 cand 可能是名人，other 一定不是名人
            // other 不可能是名人，排除，让 cand 归队
            q.addFirst(cand);
        }
    }
    // 现在排除得只剩一个候选人，判断他是否真的是名人
    int cand = q.removeFirst();
    for (int other = 0; other < n; other++) {
        if (other == cand) {
            continue;
        }
        // 保证其他人都认识 cand，且 cand 不认识任何其他人
        if (!knows(other, cand) || knows(cand, other)) {
            return -1;
        }
    }
    // cand 是名人
    return cand;
}

通过 cand 与 other 交替变换来消除队列的操作，降低空间复杂度：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int findCelebrity(int n) {
    // 先假设 cand 是名人
    int cand = 0;
    for (int other = 1; other < n; other++) {
        if (!knows(other, cand) || knows(cand, other)) {
            // cand 不可能是名人，排除
            // 假设 other 是名人
            cand = other;
        } else {
            // other 不可能是名人，排除
            // 什么都不用做，继续假设 cand 是名人
        }
    }
    // 现在的 cand 是排除的最后结果，但不能保证一定是名人
    for (int other = 0; other < n; other++) {
        if (cand == other) continue;
        // 需要保证其他人都认识 cand，且 cand 不认识任何其他人
        if (!knows(other, cand) || knows(cand, other)) {
            return -1;
        }
    }
    return cand;
}

Dijkstra 最小路径算法

Dijkstra 算法的前提，加权有向图，没有负权重边，求最短路径

首先从二叉树的层序遍历算法开始：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void gradeTraverse(TreeNode root){
    if(root == null) return 0;
    List<TreeNode> q = LinkedList<>();
    q.offer(root);
    int depth = 1;
    while(!q.isEmpty()){
        int sz = q.size();
        for(int i = 0; i < sz; i++){
            TreeNode tempNode = q.poll();
            printf("节点：%s 在第%s层", tempNode, depth);
            if(tempNode.left){
                q.offer(tempNode.left);
            }
            if(tempNode.right){
                q.offer(tempNode.right);
        }
        depth++;
    }
}

其中 while 负责的是从上到下，for循环负责的是每一层中的遍历。

如果为多叉树，则只需要变更其子节点的判断的地方即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
...
...
    while(!q.isEmpty()){
        int sz = q.size();
        for(int i = 0; i < sz; i++){
            TreeNode tempNode = q.poll();
            printf("...");
               for( TreeNode child : tempNode.child){
                q.offer(child);
            }
        }
        depth++;
    }

基于以上便可以拓展出 BFS（广度优先搜索）算法框架：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int BFS(Node start){
    if(start == nullptr) return 0;
    Queue<Node> q;
    Set<Node> visited;    //记录已经访问节点
    q.emplace(start);
    visited.add(start);
    int step = 0;
    while(!q.empty()){
        int sz = q.size();
        for(int i = 0; i < sz; i++){
            Node tempNode = q.pop();
            print("the minimum distance from start %s to current node %s is %s", start, tempNode, step);
            for(Node child : tempNode.child){
                if(visited(child) == 0){
                    q.emplace(child);
                    visited.add(child);
                }
            }
        }
        step++;
    }
}

二叉树去掉for循环，使用类。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class State{
    TreeNode curNode;
    int depth;
    State(TreeNode curNode, int depth){
        this.curNode = curNode;
        this.depth = depth;
    }
}
void BFS(TreeNode root){
    if(root == null) return 0;
    Queue<State> q = new LinkedList<>();
    q.offer(new State(root, 1));
    while(!q.isEmpty()){
        State new curState = q.poll();
        TreeNode curNode = curState.node;
        int curDepth = curState.depth;
        print("....");
        if(curNode.left != null){
            q.offer(new state(curNode.left, curDepth+1));
        }
        if(curNode.right != null){
            q.offer(new state(curNode.right, curDepth+1));
        }
    }
}

Dijkstra算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class State{
    // id of map
    int id;
    // distance between start to id
    int distFromStart;
    State(int id, int distFromStart){
        this.id = id;
        this.distFromStart = distFromStart;
    }
}
// calculate the distance between start to id
int[] dijkstra(int start, List<int[]>[] graph){
    int[] dist2Id = new int[graph.length];
    Arrays.fill(dist2Id, Integer.MAX_VALUE);
    dist2Id[start] = 0;
    Queue<State> pq = new PriorityQueue<>( (a,b)->{
        return a.distFromStart - b.distFromStart;
    } );
    pq.offer(new State(start, 0));
    while(!pq.isEmpty()){
        State curState = pq.poll();
        int curNodeID = curState.id;
        int curDistFromStart = curState.distFromStart;
        //
        if(dist2Id[curNodeID] < curDistFromStart){
            continue;
        }
        for(int[] neighbor : graph[curNodeID]){
            int nextNodeId = neighbor[0];
            int dist2NextNode = dist2Id[curNodeID] + neighbor[1];
            只需要更新比已知路径大的目标
            if(dist2Id[nextNodeId] > dist2NextNode){
                dist2Id[nextNodeId] = dist2NextNode;
                pq.offer(new State(nextNodeId, dist2NextNode));
            }
        }
    }
    return dist2Id;
}

743. 网络延迟时间

有 n 个网络节点，标记为 1 到 n。

给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。

现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。

需要注意特别注意是从1～k，涉及数组索引问题，特别重视。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<vector<pair<int,int>>> graph(n+1);
        for(auto &child : times){
            int from = child[0];
            int to = child[1];
            int weight = child[2];
            graph[from].push_back({to, weight});
        }
        vector<int> distTO = dijkstra(k, graph);
        int ans = 0;
        for(int i = 1; i < distTO.size(); i++){
            if(distTO[i] == INT_MAX){
                return -1;
            }
            ans = max(ans, distTO[i]);
        }
        return ans;

    }
    vector<int> dijkstra(int &start, vector<vector<pair<int, int>>> &graph){
        vector<int> distTO (graph.size(), INT_MAX);
        distTO[start] = 0;
        auto cmp = [](State const &a, State const &b){
            return a.distFromStart > b.distFromStart;
        };
        priority_queue<State, vector<State>, decltype(cmp)> pq(cmp);
        pq.push(State(start, 0));
        while(!pq.empty()){
            State cur = pq.top();
            pq.pop();
            if(cur.distFromStart > distTO[cur.id]){
                continue;
            }
            for(auto neighbors : graph[cur.id]){
                int nextID = neighbors.first;
                int nextIDFromDist = neighbors.second + cur.distFromStart;
                if(distTO[nextID] > nextIDFromDist){
                    distTO[nextID] = nextIDFromDist;
                    pq.push(State(nextID, nextIDFromDist));
                }
            }
        }
        return distTO;
    }
    class State{
        public:
            int id;
            int distFromStart;
            State(int id, int distFromStart){
                this->id = id;
                this->distFromStart = distFromStart;
            }
    };
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int networkDelayTime(int[][] times, int n, int k){
    if(n == 0) return -1;
    List<int[]>[] graph = new LinkedList[n+1];
    for(int i = 1; i < n+1; i++){
        graph[i] = new LinkedList<>();
    }
    for(int[] edge : times ){
        int from = edge[0];
        int to = edge[1];
        int weight = edge[2];
        graph[from].add(new int[]{to, weight});
    }
    int[] dist2Id = dijkstra(k, graph);
    int res = 0;
    for(int i = 1; i < dist2Id.length; i++){
        if(dist2Id[i] == Integer.MAX_VALUE){
            return -1;
        }
        res = Math.max(res, dist2Id[i]);
    }
    return res;
}

1631. 最小体力消耗路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
public:
    int minimumEffortPath(vector<vector<int>>& heights) {
        int m = heights.size(), n = heights[0].size();
        vector<vector<int>> effortTo ( m, vector<int>(n, INT_MAX) );
        effortTo[0][0] = 0;
        auto cmp = [](State const &a, State const &b){
            //此处与java的比较相区别，pop返回的是尾，poll返回的是头。堆每次都是从队尾弹出元素。
            return a.effortFromStart > b.effortFromStart;
        };
        priority_queue<State, deque<State>, decltype(cmp) > pq(cmp);
        //from (0,0) to (m-1, n-1)
        pq.push(State(0, 0, 0));
        while(!pq.empty()){
            State cur = pq.top();
            pq.pop();
            //reach the end point(m-1, n-1)
            if(cur.x == m-1 && cur.y == n-1)
                return cur.effortFromStart;
            if(cur.effortFromStart > effortTo[cur.x][cur.y])
                continue;
            for(vector<int> neighbor : adj(heights, cur.x, cur.y)) {
                int nextX = neighbor[0], nextY = neighbor[1];
                int effortToNext = max(
                    effortTo[cur.x][cur.y] , abs(heights[nextX][nextY] - heights[cur.x][cur.y])
                );
                if(effortTo[nextX][nextY] > effortToNext){
                    effortTo[nextX][nextY] = effortToNext;
                    pq.push(State(nextX, nextY, effortToNext));
                }
            }
        }
        return -1;
    }

    vector<vector<int>> dirs = { {0,1}, {1,0},{0,-1},{-1,0} };
    vector<vector<int>> adj( vector<vector<int>> &matrix, int &x, int &y ){
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> neighbors;
        for(auto dir : dirs){
            int nx = x + dir[0];
            int ny = y + dir[1];
            if(nx >= m || nx < 0 || ny >= n || ny < 0){
                continue;
            }
            neighbors.push_back( {nx, ny});
        }
        return neighbors;
    }

    class State{
        public:
        int x, y;
        int effortFromStart;
        State(int x, int y, int effortFromStart){
            this->x = x;
            this->y = y;
            this->effortFromStart = effortFromStart;
        }
    };   
};

1514. 概率最大的路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
public:
    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
        vector<vector<pair<int, double>>> graph(n);
        for(int i = 0; i < edges.size(); i++){
            graph[edges[i][0]].push_back({edges[i][1], (double)succProb[i]});
            graph[edges[i][1]].push_back({edges[i][0], (double)succProb[i]});
        }
        return dijkstra(start,end, graph);
    }


    class State{
        public:
            int id;
            double distFromStart;
            State(int id, double distFromStart){
                this->id = id;
                this->distFromStart = distFromStart;
            }
    };
    double dijkstra(int &start, int &end, vector<vector<pair<int, double>>> &graph){
        int V = graph.size();
        vector<double> distTO(V, INT_MIN);
        distTO[start] = 1;
        auto cmp = [](State const &a, State const &b){
            return a.distFromStart < b.distFromStart;
        };
        priority_queue<State, vector<State>, decltype(cmp) > pq(cmp);
        pq.push(State(start, 1));

        while(!pq.empty()){
            State curState = pq.top();
            pq.pop();
            //if reach the end
            if(curState.id == end){
                return curState.distFromStart;
            }
            if(curState.distFromStart < distTO[curState.id]){
                continue;
            }
            for(auto &neighbor : graph[curState.id]){
                int nextId = neighbor.first;
                double nextWeight = neighbor.second;
                double nextDist = curState.distFromStart * nextWeight;
                if(distTO[nextId] < nextDist){
                    distTO[nextId] = nextDist;
                    pq.push(State(nextId, nextDist));
                }
            }
        }
        return 0.0;
    }
};

注意使用 pair

注意使用自定义的compare：

1
2
3
auto cmp = [](State const &a, State const &b){
            return a.distFromStart < b.distFromStart;
        };

设计数据结构系列

LRU 算法

146. LRU 缓存

  • 首先实现 DoubleList 双链表存储 Node (包含 key 和 value )
  • 通过使用 HashMap 建立 key 与 Node 之间的关联。

image-20220403202829151

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
//Java 实现，另 Java 还可以通过使用 LinkedHashMap 进行实现。
class LRUCache {
    private HashMap<Integer, Node> map;
    private DoubleList cache;
    private int cap;

    public LRUCache(int capacity) {
        this.cap = capacity;
        map = new HashMap<>();
        cache = new DoubleList();
    }

    public int get(int key) {
        if(!map.containsKey(key)){
            return -1;
        }
        makeRecent(key);
        return map.get(key).value;
    }

    public void put(int key, int value) {
        if(map.containsKey(key)){
            deleteKey(key);
            addRecent(key, value);
            return;
        }
        if(cap == cache.size()){
            deleteLeastRecent();
        }
        addRecent(key, value);
    }

    public void makeRecent(int key){
        Node x = map.get(key);
        cache.remove(x);
        cache.addLast(x);
    }
    public void addRecent(int key, int value){
        Node x = new Node(key, value);
        cache.addLast(x);
        map.put(key, x);
    }
    public void deleteKey(int key){
        Node x = map.get(key);
        cache.remove(x);
        map.remove(key);
    }
    public void deleteLeastRecent(){
        Node deletedNode = cache.removeFirst();
        int deletekey = deletedNode.key;
        map.remove(deletekey);
    }

    class Node{
        int key, value;
        Node prev, next;
        public Node(int k, int v){
            this.key = k;
            this.value = v;
        }
    }

    class DoubleList{
        private Node head, tail;
        private int cap;
        public DoubleList( ){
            head = new Node(0, 0);
            tail = new Node(0,0);
            head.next = tail;
            tail.prev = head;
            this.cap = 0;
        }
        public void addLast(Node x){
            x.prev = tail.prev;
            x.next = tail;
            tail.prev.next = x;
            tail.prev = x;
            this.cap++; 
        }
        public void remove(Node x){
            x.prev.next = x.next;
            x.next.prev = x.prev;
            this.cap--;
        }
        public Node removeFirst(){
            if(head.next == tail){
                return null;
            }
            Node first = head.next;
            remove(first);
            return first;
        }
        public int size(){
            return this.cap;
        }

    }
}
/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

C++ 版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class LRUCache {
public:
    LRUCache(int capacity):cap(capacity) {

    }

    int get(int key) {
        //如果没有这个值
        if(map.find(key) == map.end()){ return -1;}
        //有这个值
        auto key_value = *map[key];
        cache.erase(map[key]);
        cache.push_front(key_value);
        map[key] = cache.begin();
        return key_value.second;
    }

    void put(int key, int value) {
        //没有
        if(map.find(key) == map.end() ){
            //如果满
            if(cache.size() == cap){
                map.erase(cache.back().first);
                cache.pop_back();
            }
        }else{
            cache.erase(map[key]);
        }
        cache.push_front({key, value});
        map[key] = cache.begin();
    }
private:
    int cap;
    list<pair<int,int>> cache;
    unordered_map<int, list<pair<int, int>>::iterator> map;
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

LFU 算法

LFU 算法的淘汰策略是每次淘汰使用频次最少的数据，如果频次相同则淘汰最早插入的数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
class LFUCache{
    HashMap<Integer, Integer> key2Val;
    HashMap<Integer, Integer> key2Freq;
    HashMap<Integer, LinkedHashSet<Integer>> freq2Key;
    //需要时间复杂度为O(1)，不能使用遍历查找最小 freq，所以使用 minFreq 记录最小 Freq
    int minFreq;

    int cap;
    public LFUCache(int capacity){
        key2Val = new HashMap<>();
        key2Freq = new HashMap<>();
        freq2Key = new HashMap<>();
        this.minFreq = 0;
        this.cap = capacity;
    }
    public int get(int key){
        if(!key2Val.containsKey(key)){
            return -1;
        }
        //存在 key
        increaseFreq(key);
        return key2Val.get(key);
    }

    public void put(int key, int val){
        if(this.cap <= 0) return;
        //key exists
        if(key2Val.containsKey(key)){
            key2Val.put(key, val);
            increaseFreq(key);
            return;
        }
        // key not exist
        if(this.cap <= key2Val.size()){
            removeMinFreq();
        }
        key2Val.put(key, val);
        key2Freq.put(key, 1);    //increaseFreq(key);
        freq2Key.putIfAbsent(1, new LinkedHashSet<>());
        freq2Key.get(1).add(key);
        this.minFreq = 1;
    }

    private void removeMinFreq(){
        LinkedHashSet<Integer> kList = freq2Key.get(this.minFreq);
        int deleteKey = kList.iterator().next();
        kList.remove(deleteKey);
        if(kList.isEmpty()){
            freq2Key.remove(this.minFreq);
        }
        key2Val.remove(deleteKey);
        key2Freq.remove(deleteKey);
    }
    //增加key的freq
    private void increaseFreq(int key){
        int freq = key2Freq.get(key);
        //更新 key2Freq
        key2Freq.put(key,freq+1);
        //更新 freq2Key
        //删除原有freq中的 key
        freq2Key.get(freq).remove(key);
        //将key添加到freq+1中
        freq2Key.putIfAbsent(freq+1, new LinkedHashSet<>());
        freq2Key.get(freq+1).add(key);
        //如果删除导致原有 freq2Key 中的 freq 对应列表为空，则删除此freq
        if(freq2Key.get(freq).isEmpty()){
            freq2Key.remove(freq);
            if(freq == this.minFreq){
                this.minFreq++;
            }
        }
    }
}

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache obj = new LFUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

前缀树算法

常见的 Map 和 Set 的底层实现原理有哈希表和二叉搜索树两种，比如 Java 的 HashMap/HashSet 和 C++ 的 unorderd_map/unordered_set 底层就是用哈希表实现，而 Java 的 TreeMap/TreeSet 和 C++ 的 map/set 底层使用红黑树这种自平衡 BST 实现的。

Trie 树本质为一棵二叉树衍生出来的多叉树。

1
2
3
4
5
6
7
8
9
10
11
//二叉树
class TreeNode{
    int val;
    TreeNode left, right;
}

//多叉树
class TreeNode{
    int val;
    TreeNode [] child;
}

Trie 树用「树枝」存储字符串「键」，用「节点」存储字符串（键）对应的数据。

实现前缀树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Trie{
private:
    bool isEnd;
    //多种定义子成员的方法 vector, [], unordered_map
    // Trie* next[26];
    vector<Trie*> next;
    // unordered_map<char, Trie*> next;
public:
    Trie():isEnd(false), next(26){
        // isEnd = false;
        // memset(next, 0, sizeof(next));    []需要初始化    //C++里NULL的定义就是0
    }
    void insert(string word){
        Trie* node = this;
        for(char c : word){
            //对于不同的定义子成员的方式
            //只需要改变判断方式：
            //[]: if(node->next[c-'a'] == NULL)
            //vector: if(node-next[c-'a']==nullptr)
            //unordered_map: if(!node->next.count(c-'a'))
            if(node->next[c-'a']==nullptr){        
                node->next[c-'a'] = new Trie();
            }
            node = node->next[c-'a'];
        }
        node->isEnd = true;
    }
    bool search(string word){
        Trie* node = this;
        for(auto c : word){
            if(node->next[c-'a']==nullptr){
                return false;
            }
            node = node->next[c-'a'];
        }
        return node->isEnd;
    }
    bool startsWith(string prefix){
        Trie* node = this;
        for(auto c : prefix){
            if(node->next[c-'a']==nullptr){
                return false;
            }
            node = node->next[c-'a'];
        }
        return true;       
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

需要特别注意：NULL与nullptr的区别，以及0与NULL的关系。

实现前缀树II

定义Trie类时，设置 count_prefix 和 count_word 属性，分别记录当前词作为前缀和作为独立词的数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Trie{
private:
    int count_prefix;
    int count_word;
    vector<Trie*> child;
    Trie():count_prefix(0), count_word(0), child(26){

    }
    void insert(string word){
        Trie* node = this;
        for(auto& c : word){
            if(node->child[c-'a']==nullptr){
                node->child[c-'a'] = new Trie();
            }
            node = node->child[c-'a'];
            node->count_prefix += 1;
        }
        node->count_word += 1;
    }
    int countWordsEqualTo(string word){
        Trie* node = this;
        for(auto& c : word){
            if(node->child[c-'a'] == nullptr){
                return 0;
            }
            node = node->child[c-'a'];
        }
        return node->count_word;
    }
    int countWordsStartingWith(string prefix){
        Trie* node = this;
        for(auto& c : word){
            if(node->child[c-'a'] == nullptr){
                return 0;
            }
            node = node->child[c-'a'];
        }
        return node->count_prefix;
    }
    void erase(string word){
        Trie* node = this;
        for(auto& c : word){
            if(node->child[c-'a']==nullptr){
                return;
            }
            node = node->child[c-'a'];
            node->count_prefix -= 1;
        }
        node->count_word -= 1;
    }
}

C++使用 stringstream 分割字符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <sstream>
#include <vector>
using namespace std;

int main(){
    vector<string> ans;
    string data = "ni_hao_yi_ding";
    stringstream ss (data);
    string word;
    while(getline(ss, word, '_')){
        ans.emplace_back(word);
    }
    for(auto val : ans){
        cout << val << endl;
    }
}

单词替换

Screen Shot 2022-04-07 at 21.30.40

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
//C++ Smart point version
class Trie{
public:
    bool is_end;
    vector<unique_ptr<Trie>> arr;

public:
    Trie():is_end(false), arr(26){
        
    }
    void insert(const string& word){
        Trie* node = this;
        for(const auto& c : word){
            if(!node->arr[c-'a']){
                node->arr[c-'a'] =  make_unique<Trie>();
            }
            node = node->arr[c-'a'].get();
        }
        node->is_end = true;
    }
    string find_prefix(const string& word){
        Trie* node = this;
        string res;
        for(const auto& c : word){
            res+=c;
            if(!node->arr[c-'a']) {return word;}
            if(node->arr[c-'a']->is_end) {return res;}
            node = node->arr[c-'a'].get();
        }
        return res;
    }

};


class Solution {
public:
    string replaceWords(vector<string>& dictionary, string sentence) {
        Trie* root = new Trie();
        string ans;
        for(const auto& d : dictionary){
            root->insert(d);
        }
        vector<string> words = split(sentence, ' ');
        for(const auto& word : words){
            string tmp = root->find_prefix(word);
            ans.append(tmp);
            // ans.append(" ");
            ans+=' ';
        }
        ans.erase(ans.size()-1);
        return ans;

    }
    vector<string> split(const string& str, char ch){
        int l = 0, r = 0;
        vector<string> res;
        while(r < str.size()){
            while(r < str.size() && str[r] == ch){
                r++;
            }
            l = r;
            while(r < str.size() && str[r] != ch){
                r++;
            }
            if(l < str.size()){
                res.emplace_back(str.substr( l, r - l ) );
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
//Java
class Solution{
    public String replaceWords(List<String> roots, String sentence){
        TrieNode trie = new TrieNode();
        for(String root : roots){
            TrieNode cur = trie;
            for(char c : root.toCharArray()){
                if(cur.children[c-'a'] == null){
                    cur.children[c-'a'] = new TrieNode();
                }
                cur = cur.children[c-'a'];
            }
            cur.word = root;
        }
        StringBuilder ans = new StringBuilder();
        //C++ 方式分割字符串

        //while(ss>>word)        //stringstream ss; string word

        //while(getline(ss, word, ' '))
        for(String word : sentence.split("\\s+")){
            TrieNode cur = trie;
            for(char c : word.toCharArray()){
                if(cur.children[c-'a'] == null||cur.word != null) {break;}
                cur = cur.children[c-'a'];
            }
            if(ans.length() > 0){
                ans.append(" ");
            }
            ans.append( cur.word != null ? cur.word : word );
        }
        return ans.toString();
    }
}

class TrieNode{
    String word;
    TrieNode[] children;
    TrieNode(){
        children = new TrieNode[26];
    }
}

哈希集合方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
public:
    string replaceWords(vector<string>& dictionary, string sentence) {
        string ans;
        vector<string_view> words = splitString(sentence, ' ');
        unordered_set<string_view> dictSet;
        for(const auto& root : dictionary){
            dictSet.emplace(root);
        }
        for( auto& word : words){
            for(int i = 0; i < word.size(); i++){
                if(dictSet.count(word.substr(0, 1+i))){
                    word = word.substr(0, 1+i);
                    break;
                }
            }
        }
        for(const auto& word : words){
            ans.append(word);
            ans.append(" ");
        }
        ans.erase(ans.size()-1);
        return ans;
    }
    vector<string_view> splitString(string& sentence, char blank){
        vector<string_view> res;
        string_view s(sentence);
        int r = 0, l = 0;
        int n = s.size();
        while(r < n){
            while(r < n && s[r] == blank ){
                r++;
            }
            l = r;
            while(r < n && s[r] != blank){
                r++;
            }
            if(l < n){
                res.emplace_back(s.substr(l, r-l));
            }
        }
        return res;
    }
    unordered_map<int, pair<int, int>> map;
};

大小堆求中位数

295. 数据流的中位数

图形学Games101 有关光线追踪之前的判断光线是否与物体相交之前的预处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class MedianFinder {
public:
    MedianFinder() {

    }
    //重点在于添加数据的时候保证，下三角▼，和梯形 的接口处数据大小为：下三角面 <= 梯形上面
    //所以无论如何，在插入哪方时，都先提前插入另一方，让其排序后，插入，再删除。
    void addNum(int num) {
        if(large.size() <= small.size()){
            small.push(num);
            large.push(small.top());
            small.pop();
        }else{
            large.push(num);
            small.push(large.top());
            large.pop();
        }
    }

    double findMedian() {
        if(small.size() > large.size()){
            return small.top();
        }else if(small.size() < large.size()){
            return large.top();
        }
        return (double)(small.top() + large.top())/2;
    }
public:
    struct cmp{
        bool operator()(int a, int b){
            return a > b;
        }
    };
    priority_queue<int, vector<int>, cmp> small;
    priority_queue<int> large;
    //priority_queue<int, vector<int>, less<int>> small;
    //priority_queue<int, vector<int>, greater<int>> large;

};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */

单调栈结构

739. 每日温度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int> res(temperatures.size());
        stack<int> s;
        //从后往前，依次判断的是每日的温度
        for(int i = temperatures.size() - 1; i >= 0; i--){
            //while循环判断个子矮的出栈
            while(!s.empty() && temperatures[s.top()] <= temperatures[i]){
                s.pop();
            }
            res[i] = s.empty() ? 0 : (s.top() - i);
            //特别注意，此处进栈的是索引值
            s.push(i); 
        }
        return res;
    }
};

496. 下一个更大元素 I

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> map;
        stack<int> s;
        for(int i = nums2.size()-1; i >= 0; i--){
            while(!s.empty() && nums2[i] >= s.top()){
                s.pop();
            }
            map[nums2[i]] = s.empty() ? -1 : s.top();
            s.push(nums2[i]);
        }
        vector<int> res(nums1.size());
        for(int i = 0; i < nums1.size(); i++){
            res[i] = map[nums1[i]];
        }
        return res;
    }
};
  • 通过单调栈来进行计算
  • 通过 map 来进行 num1[i] 与 num2[i] 的数值对应。

503. 下一个更大元素 II

首先接受循环数组的概念：

1
2
3
4
5
6
arr = [1,2,3,4,5]
n = arr.lenght
index = 0
while True:
    print(arr[n % index]
    index += 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n);
        stack<int> s;
        for(int i = 2*n - 1; i >= 0; i--){
            while(!s.empty() && s.top() <= nums[i % n] ){
                s.pop();
            }
            res[i % n] = s.empty() ? -1 : s.top();
            s.push(nums[i % n]);
        }
        return res;
    }
};

二叉堆实现优先级队列

二叉堆，即逻辑上是一种特殊的二叉树（完全二叉树），二叉堆存储在数组里。一般的二叉树为链表的形式，操作的节点为指针，而在数组中，数组的索引作为指针。

1
2
3
4
5
6
7
8
9
int parent(int root){
    return root/2;
}
int left(int root){
    return root*2;
}
int right(int root){
    return root*2+1;
}

二叉堆分为最大堆和最小堆。分别的性质为其每个节点都大于等于/小于等于它的两个子节点。

交换数组两个元素

1
2
3
4
5
void exch(int i, int j){
    int temp = i;
    pq[i] = j;
    pq[j] = temp;
}

上浮第K个元素

1
2
3
4
5
6
void swim(int k){
    while(k > 1 && less(parent(k) < k)){
        exch(parent(k), k);
        k = parent(k);
    }
}

下沉第k个元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void sink(int k ){
    while(left(k) <= N){
        int older = left(k);
        if(right(k) <= N && right(k) > older){
            older = right(k);
        }
        if(older >= k){
            exch(oler, k);
            k = older;
        }else if(older < k){
            break;
        }
    }
}

插入insert

先插入到最后，然后让其上浮

1
2
3
4
5
void insert(int k){
    N++;
    pq[N] = k;
    swin(N);
}

delMax 删除最大节点

1
2
3
4
5
6
7
8
Key delMax(){
    Key max = pq[1];
    exch(1, N);
    pq[N] = nullptr;
    N--;
    swin(1);
    return max;
}

时间复杂度：插入和删除 O(log(N))

用栈实现队列

思想：两个栈来回调用。

时间复杂度：主要操作为 peek 操作，调用时触发 while 循环时间复杂度为 O(N)，但不会每次都触发，所以时间复杂度为 O(1)。 其余操作间接使用 peek 所以最终时间复杂度O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class MyQueue {
public:
    stack<int> s1, s2;
    MyQueue() {

    }

    void push(int x) {
        s1.emplace(x);
    }

    int pop() {
        peek();
        int res = s2.top();
        s2.pop();
        return res;

    }

    int peek() {
        if(s2.empty()){
            while(!s1.empty()){
                s2.emplace(s1.top());
                s1.pop();
            }
        }
        return s2.top();
    }

    bool empty() {
        return s1.empty() && s2.empty();
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

用队列实现栈

队列实现栈的想法，使用一个队列的核心思想为，在删除的时候使用循环的思想。

时间复杂度主要在于 pop 时为 O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class MyStack {
public:
    queue<int> q1;
    int topItem;
    MyStack() {
        topItem = 0;
    }

    void push(int x) {
        q1.emplace(x);
        topItem = x;
    }

    int pop() {
        int size = q1.size();
        while(size > 2){
            q1.emplace(q1.front());
            q1.pop();
            size--;
        }
        topItem = q1.front();
        q1.emplace(q1.front());
        q1.pop();
        int res = q1.front();
        q1.pop();
        return res;
    }

    int top() {
        return topItem;
    }

    bool empty() {
        return q1.empty();
    }
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */

设计推特

355. 设计推特

image-20220418172811432

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
class Twitter {
public:
    inline static int timeStamp = 0;
    Twitter() {
    }

    class Tweet{
    public:
        int id;
        int time;
        Tweet *next;
        Tweet(int _id, int _time):id(_id), time(_time), next(nullptr){

        }
    };

    class User{
    public:
        int id;
        unordered_set<int> followed;
        Tweet *head;
        User(int userId): id(userId), head(nullptr){
            follow(id);
        }
        void follow(int userId){
            followed.emplace(userId);
        }
        void unfollow(int userId){
            if(userId != this->id){
                followed.erase(userId);
            }
        }
        void post(int tweetId){
            Tweet *twt = new Tweet(tweetId, timeStamp);
            timeStamp++;
            //将新建的推文插入到链表头
            twt->next = head;
            head = twt;
        }
    };
    unordered_map<int, User*> userMap;

    void postTweet(int userId, int tweetId) {
        if(userMap.count(userId) == 0){
            User *u = new User(userId);
            userMap.emplace( userId, u );
        }
        // auto u = userMap.find(userId);
        // u->second->post(tweetId);
        User *u = userMap.at(userId);
        u->post(tweetId);
    }

    vector<int> getNewsFeed(int userId) {
        vector<int> res;
        if(userMap.find(userId) == userMap.end()){
            return res;
        }
        unordered_set<int> followUsers = userMap.find(userId)->second->followed;
        //通过lambda表达式进行自定义比较大小的方式
        auto cmp=[](const auto&a,const auto&b)->bool{
            return a->time < b->time;
        };
        priority_queue< Tweet*, vector<Tweet*>, decltype(cmp)> pq(cmp);

        for(const auto& id : followUsers){
            //auto twt = userMap.find(id)->second->head;
            Tweet *twt = userMap.at(id)->head;
            if(twt == nullptr) continue;
            pq.emplace(twt);
        }
        while(!pq.empty()){
            if(res.size() == 10) break;
            Tweet *twt = pq.top();
            pq.pop();
            res.emplace_back(twt->id);
            if(twt->next != nullptr){
                pq.emplace(twt->next);
            }
        }
        return res;
    }

    void follow(int followerId, int followeeId) {
        if(userMap.count(followerId) == 0){
            User *u = new User(followerId);
            userMap.emplace(followerId, u);
        }
        if(userMap.count(followeeId) == 0){
            User *u = new User(followeeId);
            userMap.emplace(followeeId, u);
        }
        userMap.at(followerId)->follow(followeeId);
    }

    void unfollow(int followerId, int followeeId) {
        if(userMap.count(followerId) != 0){
            userMap.at(followerId)->unfollow(followeeId);
        }
    }
};
//重载类型的<运算符
// bool operator< (Twitter::Tweet &a, Twitter::Tweet &b)
// {
//     return a.time < b.time;
// }
/*或者使用结构体类型
struct cmp{
        bool operator()(Twitter::Tweet *a, Twitter::Tweet *b){
            return a->time < b->time;
        }
    };
*/
/**
 * Your Twitter object will be instantiated and called as such:
 * Twitter* obj = new Twitter();
 * obj->postTweet(userId,tweetId);
 * vector<int> param_2 = obj->getNewsFeed(userId);
 * obj->follow(followerId,followeeId);
 * obj->unfollow(followerId,followeeId);
 */

最大栈

895. 最大频率栈

  • 值对应频率 hashmap
  • 频率对应值 hashmap
  • 最大的频率，最大频率所对应的栈的顶端即对应最新插入的最大频率值
  • 当最大频率所对应栈/组，为空，则证明最大频率值已无数值对应，最大频率应为下一个（maxFreq- -)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class FreqStack {
    int maxFreq = 0;
    HashMap<Integer, Integer> val2freq = new HashMap<>();
    HashMap<Integer, Stack<Integer>> freq2vals = new HashMap<>();
    public FreqStack() {
    }

    public void push(int val) {
        //val2freq ++
        int freq = val2freq.getOrDefault(val, 0) + 1;
        val2freq.put(val, freq);
        //freq2vals push
        freq2vals.putIfAbsent(freq, new Stack<>());
        freq2vals.get(freq).push(val);
        //tempStack = freq2vals.putIfAbsent(freq, new Stack<>());
        //tempStack.push(val);

        //max maxFreq
        maxFreq = Math.max(maxFreq, freq);

    }

    public int pop() {
        Stack<Integer> vals = freq2vals.get(maxFreq);
        int res = vals.pop();
        // update val2freq
        int freq = val2freq.get(res) - 1;
        val2freq.put(res, freq);
        // update maxFreq
        if(vals.isEmpty()){
            maxFreq--;
        }

        return res;
    }
}

/**
 * Your FreqStack object will be instantiated and called as such:
 * FreqStack obj = new FreqStack();
 * obj.push(val);
 * int param_2 = obj.pop();
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class FreqStack {
public:
    FreqStack() {
    }

    void push(int val) {
        // add to val2freq
        val2Freq[val]++;
        // add to freq2val
        freq2Val[val2Freq[val]].emplace_back(val);
        // max maxFreq
        maxFreq = max( maxFreq, val2Freq[val] );
    }

    int pop() {
        // del maxFreq val2ferq
        int resPop = freq2Val[maxFreq].back();
        freq2Val[maxFreq].pop_back();
        // del val2Freq
        val2Freq[resPop]--;
        // if maxFreq group is None.
        if( freq2Val[maxFreq].size() == 0 ){
            maxFreq--;
        }
        return resPop;
    }
    int maxFreq = 0;
    //val to frequency
    unordered_map<int, int> val2Freq;
    //freq to val: group
    unordered_map<int, vector<int>> freq2Val;
};

/**
 * Your FreqStack object will be instantiated and called as such:
 * FreqStack* obj = new FreqStack();
 * obj->push(val);
 * int param_2 = obj->pop();
 */

动态规划

DP

俄罗斯套娃问题

354. 俄罗斯套娃信封问题

Screen Shot 2022-04-27 at 15.48.54

Screen Shot 2022-04-27 at 15.48.14

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        if (envelopes.empty()) {
            return 0;
        }
        int n = envelopes.size();
        sort(envelopes.begin(), envelopes.end(), [](const auto& e1, const auto& e2) {
            return e1[0] < e2[0] || (e1[0] == e2[0] && e1[1] > e2[1]);
        });

        vector<int> f(n, 1);
        int ans = 1;
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (envelopes[j][1] < envelopes[i][1]) {
                    f[i] = max(f[i], f[j] + 1);
                }
            }
            ans = max(f[i], ans);
        }
        return ans;
    }
};

方法二：

Screen Shot 2022-04-27 at 15.49.20

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        if (envelopes.empty()) {
            return 0;
        }

        int n = envelopes.size();
        sort(envelopes.begin(), envelopes.end(), [](const auto& e1, const auto& e2) {
            return e1[0] < e2[0] || (e1[0] == e2[0] && e1[1] > e2[1]);
        });
        vector<int> dq(1, envelopes[0][1]);
        for(int i = 1; i < envelopes.size(); i++){
            int index = -1;
            int left = 0, right = dq.size() - 1;
            while(left <= right){
                int mid = left + (right - left)/2;
                if(dq[mid] >= envelopes[i][1]){
                    index = mid;
                    right = mid - 1;
                }else{
                    left = mid + 1;
                }
            }
            if(index == -1){
                dq.emplace_back(envelopes[i][1]);
            }else{
                dq[index] = envelopes[i][1];
            }
        }
        return dq.size();
    }
};

最大回文子串

image-20220429151440951

目标和

1
2
3
4
5
6
7
8
输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

Screen Shot 2022-04-30 at 22.08.27

Screen Shot 2022-04-30 at 22.08.40

最长公共子序列

image-20220501212041777

image-20220627233456943

编辑距离

Screen Shot 2022-05-02 at 23.57.09

image-20220503233617821

最大子数组和

image-20220504233051828

增减字符串匹配

image-20220509195453140

背包问题

image-20220510203209056

贪心类型问题

贪心算法的性质：每一步都选择局部最优，最终结果就是全局最优（只能满足部分类型）。

435. 无重叠区间

image-20220705214824153

452. 用最少数量的箭引爆气球

image-20220705220534306

课程表I (区间冲突问题)

image-20220706230950381

岛屿问题

岛屿数量

image-20220513200751095

封闭岛屿数量

image-20220514213823238

打家劫舍

198 打家劫舍，不可循环

两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警

image-20220517194648381

213 可循环打家劫舍

image-20220519230737029

337 二叉树类型打家劫舍

image-20220525220406826

动态规划最小路径和

image-20220622223538205

动态规划之地下城游戏（动态规划最小路径和逆向思想）

image-20220623234526006

动态规划通向“自由之路”

image-20220624231516052

10. 正则表达式匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
public:
    bool isMatch(string s, string p) {
        memo.resize(s.size(), vector<int>(p.size(), -1));
        return dp(s, 0, p, 0);
    }
    bool dp(string& s, int i, string& p, int j){
        int m = s.size(), n = p.size();
        //base case
        if(j == n){
            return i == m;
        }
        if(i == m){
            if( (n-j) & 1 != 0  ){
            // if( (n-j) % 2 == 1  ){
                return false;
            }
            for(;j+1 < n; j += 2){
                if(p[j+1] != '*'){
                    return false;
                }
            }
            return true;
        }


        if(memo[i][j] != -1){
            return memo[i][j];
        }


        bool res = false;
        
        if(s[i] == p[j] || p[j] == '.'){
            if(j < n-1 && p[j+1] == '*'){
                res = dp(s, i, p, j+2) || dp(s, i+1, p, j);
            }else{
                res = dp(s, i + 1, p, j + 1);
            }
        }else{
            if( j < n-1 && p[j+1] == '*' ){
                res = dp(s, i, p, j+2);
            }else{
                res = false;
            }
        }
        memo[i][j] = res;
        return res;
    }
    vector<vector<int>> memo;
};

953. 验证外星语词典

某种外星语也使用英文小写字母，但可能顺序 order 不同。字母表的顺序（order）是一些小写字母的排列。

给定一组用外星语书写的单词 words，以及其字母表的顺序 order，只有当给定的单词在这种外星语中按字典序排列时，返回 true；否则，返回 false。

示例 1：

1
2
3
输入：words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
输出：true
解释：在该语言的字母表中，'h' 位于 'l' 之前，所以单词序列是按字典序排列的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    vector<int> mapOrd;
    //front > latter 1
    //front < latter -1
    //front == latter 0
    int check(string s1, string s2){
        int i = 0, j = 0;
        while(i < s1.size() && j < s2.size()){
            int c1 = s1[i] - 'a', c2 = s2[j] - 'a';
            if(c1 != c2){
                return mapOrd[c1] - mapOrd[c2];
            }
            i++;
            j++;
        }
        if(i < s1.size()) {return 1;}
        if(j < s2.size()) {return -1;}
        return 0;
    }
    bool isAlienSorted(vector<string>& words, string order) {
        mapOrd.resize(26, 0);
        //map 
        for(int i = 0; i < order.size(); i++){
            int pos = order[i] - 'a';
            mapOrd[pos] = i;
        }
        //check neighboring word
        for(int i = 1; i < words.size(); i++){
            if( check(words[i-1], words[i] ) > 0 ) {return false;}
        }
        return true;
    }
};

1021 删除最外层的括号

有效括号字符串为空 “”、”(“ + A + “)” 或 A + B ，其中 A 和 B 都是有效的括号字符串，+ 代表字符串的连接。

例如，””，”()”，”(())()” 和 “(()(()))” 都是有效的括号字符串。
如果有效字符串 s 非空，且不存在将其拆分为 s = A + B 的方法，我们称其为原语（primitive），其中 A 和 B 都是非空有效括号字符串。

给出一个非空有效字符串 s，考虑将其进行原语化分解，使得：s = P_1 + P_2 + … + P_k，其中 P_i 是有效括号字符串原语。

对 s 进行原语化分解，删除分解中每个原语字符串的最外层括号，返回 s 。

示例 1：

输入：s = “(()())(())”
输出：”()()()”
解释：
输入字符串为 “(()())(())”，原语化分解得到 “(()())” + “(())”，
删除每个部分中的最外层括号后得到 “()()” + “()” = “()()()”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    string removeOuterParentheses(string s) {
        stack<char> st;
        string ans;
        //当栈为空的时候，说明已经形成了『原语』
        //当遇到 "("时，将其入栈；
        //当遇到 ")"时，说明匹配了前面最近一个 "("，因此将栈顶弹出；
        //当"("入栈前，栈是空，说明 "(" 是『原语』的开头，因此不放入 res中。
        //当遇到 ")" 弹出栈顶以后，栈是空，说明 ")" 是『原语』的结束，因此不放入 res中。
        for(const auto c : s){
            if(c==')'){
                st.pop();
            }
            if(!st.empty()){
                ans += c;
            }
            if(c=='('){
                st.emplace(c);
            }
        }
        return ans;
    }
};

20. 有效的括号

labuladong 题解思路

难度简单

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。

示例 1：

1
2
输入：s = "()"
输出：true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for(const auto c : s){
            if(c == '(' || c == '{' || c == '['){   // left bracket, then push it
                st.emplace(c);
            }else{                                  // situation: !/st.empty(); right bracket; 
                if(!st.empty()){
                    if(c == ')'){
                        char temp_c = st.top();
                        st.pop();
                        if(temp_c != '(' ){
                            return false;
                        }
                    }else if (c == '}'){
                        char temp_c = st.top();
                        st.pop();
                        if(temp_c != '{' ){
                            return false;
                        }
                    }else if( c == ']'){
                        char temp_c = st.top();
                        st.pop();
                        if(temp_c != '['){
                            return false;
                        }
                    }
                }else {             // st.empty()
                    return false;
                }
            }
        }
        // if ()(,  st is not empty, but false;
        return st.empty();
    }
};

1022. 从根到叶的二进制数之和

给出一棵二叉树，其上每个结点的值都是 0 或 1 。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。

  • 例如，如果路径为 0 -> 1 -> 1 -> 0 -> 1，那么它表示二进制数 01101，也就是 13 。

对树上的每一片叶子，我们都要找出从根到该叶子的路径所表示的数字。

返回这些数字之和。题目数据保证答案是一个 32 位 整数。

1
2
3
输入：root = [1,0,1,0,1,0,1]
输出：22
解释：(100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int ans;
    int sumRootToLeaf(TreeNode* root) {
        if(root == nullptr){return 0;}
        //printf root->val
        dfs(root, 0);
        return ans;
    }
    void dfs(TreeNode* root, int nodeCur){
        if(root == nullptr) return;
        // nodeCur = (nodeCur<<1) + root->val ,效率低
        nodeCur = (nodeCur << 1) | root->val;
        if(!root->left && !root->right) {
           ans += nodeCur; 
        }
        dfs(root->left, nodeCur);
        dfs(root->right, nodeCur);
    }
};

有关使用与符号进行判断奇偶性：

1
2
3
int isOdd(int num){
    return (num & 1) != 0;
}

分冶算法——241. 为运算表达式设计优先级

Screen Shot 2022-07-01 at 22.25.38

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    vector<int> diffWaysToCompute(string expression) {
        if(memo.find(expression) != memo.end()){
            return memo[expression];
        }
        vector<int> res;
        for(int i = 0; i < expression.size(); i++){
            char c = expression.at(i);
            if(c == '-' || c == '+' || c == '*' ) {
                vector<int> left_diff_way = diffWaysToCompute(expression.substr(0,i));
                vector<int> right_diff_way = diffWaysToCompute(expression.substr(i+1, expression.size()- i ));
                for(const auto& a : left_diff_way){
                    for(const auto& b : right_diff_way){
                        if(c=='-'){
                            res.emplace_back(a-b);
                        }else if(c == '+'){
                            res.emplace_back(a+b);
                        }else if(c == '*'){
                            res.emplace_back(a*b);
                        }
                    }
                }
            }
        }
        if(res.empty()){
            res.emplace_back(std::stoi(expression));
        }
        memo.emplace(expression, res);
        return res;
    }
    unordered_map<string, vector<int>> memo;
};

31. 下一个排列

Screen Shot 2022-07-03 at 23.21.32

Screen Shot 2022-07-03 at 23.39.25

设计双端循环队列

链表设计，头节点，尾节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
class MyCircularDeque {
    class Node{
        int val;
        Node pre, next;
        Node(int _val){
            val = _val;
        }
    }
    Node head, tail;
    int cnt, size;
    public MyCircularDeque(int k) {
        size = k;
        head = new Node(-1);
        tail = new Node(-1);
        head.next = tail;
        tail.pre = head;
    }
    
    public boolean insertFront(int value) {
        if(isFull()) {return false;}
        //      node
        //head      tail;
        /* Node node = new Node(value);
        node.next = he.next;
        node.prev = he;
        he.next.prev = node;
        he.next = node;
*/
        Node node = new Node(value);
        node.next = head.next;
        node.pre = head;
        head.next.pre = node;
        head.next = node;
        cnt++;
        return true;

    }
    
    public boolean insertLast(int value) {
        if(isFull()) {return false;}
        //        node 
        // bksec       tail
        Node node = new Node(value);
        node.next = tail;
        node.pre = tail.pre;
        tail.pre.next = node;
        tail.pre = node;
        cnt++;
        return true;

    }
    
    public boolean deleteFront() {
        if(isEmpty()) {return false;}
        //head node tial
        // head.next = head.next.next;
        // head.next.pre = head;
        head.next.next.pre = head;
        head.next = head.next.next;
        cnt--;
        return true;
    }
    
    public boolean deleteLast() {
        if(isEmpty()) {return false;}
        //bdsecond node tail
        // tail.pre = tail.pre.pre;
        // tail.pre.next = tail;
        tail.pre.pre.next = tail;
        tail.pre = tail.pre.pre;
        cnt--;
        return true;
    }
    
    public int getFront() {
        return isEmpty() ? -1 : head.next.val;
    }
    
    public int getRear() {
        return isEmpty() ? -1 : tail.pre.val;
    }
    
    public boolean isEmpty() {
        return cnt == 0;
    }
    
    public boolean isFull() {
        return size ==cnt;
    }
}

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * MyCircularDeque obj = new MyCircularDeque(k);
 * boolean param_1 = obj.insertFront(value);
 * boolean param_2 = obj.insertLast(value);
 * boolean param_3 = obj.deleteFront();
 * boolean param_4 = obj.deleteLast();
 * int param_5 = obj.getFront();
 * int param_6 = obj.getRear();
 * boolean param_7 = obj.isEmpty();
 * boolean param_8 = obj.isFull();
 */

剑指Offer

剑指 Offer 03. 数组中重复的数字

image-20220717223240874

剑指 Offer 04. 二维数组中的查找

Screen Shot 2022-07-18 at 21.37.57

剑指 Offer 29. 顺时针打印矩阵

image-20220719222456995

栈和队列

包含mini函数的栈

image-20220724224015274

栈的压入和弹出

image-20220724224444146

面试题40. 最小的k个数

难度简单461收藏分享切换为英文接收动态反馈

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

示例 1：

1
2
输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]

示例 2：

1
2
输入：arr = [0,1,2,1], k = 1
输出：[0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        if(arr.size() < k || k < 0){
            return {};
        }
        // auto cmp = [](){};
        priority_queue<int> max_heap;
        for(const auto& num : arr ){
            max_heap.emplace(num);
            if(max_heap.size() > k ){
                max_heap.pop();
            }
        }
        vector<int> ans;
        while(!max_heap.empty()){
            ans.emplace_back(max_heap.top());
            max_heap.pop();
        }
        return ans;
    }
};
  • 设置大顶堆来维护最小堆
  • 大顶堆大小如果大于k，则删除顶端元素

数据流中的中位数

image-20220728231339998

滑动窗口的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ans;
        priority_queue<pair<int, int>> pq;
        if(k > nums.size() || nums.size() == 0 || k < 1){
            return ans;
        }
        for(int i = 0; i < k; i++){
            pq.emplace(nums[i], i);
        }
        ans.emplace_back(pq.top().first);
        for(int i = k; i < nums.size(); ++i) {
            pq.emplace(nums[i], i);
            int left = i - k + 1;
            while(pq.top().second < left){
                pq.pop();
            }
            ans.emplace_back(pq.top().first);
        }
        return ans;

    }
};
  • 关键点在于 priority_queue< pair> 使用，因为 priority_queue 没有直接删除某个 value 的方法，所以使用 pair 对应 value, index，利用 pair 的 second 来标记 index，当 pq.top().second < left 时，进行删除移出窗口。

双指针

和为s的两个数字 && 和为s的连续正数序列

image-20220801220249301

链表

剑指 Offer 06. 从尾到头打印链表

image-20220802230701753

删除链表中重复的结点

image-20220803233954275

链表的倒数第K个节点

image-20220804210303381

链表中环的入口节点

image-20220804214852798

合并两个排序的链表

image-20220805214436978

复杂链表的复制

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

思路：原地克隆

  • 原地克隆上一节点 ： A->A’->B->B’->C->C’
  • 重建 random 节点，注意 clone->random = cur->random->next，其中的->next 是保证为新客隆的节点。
  • 然后分离节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(!head) {return nullptr; }
        Node* cur = head;
        //insert clone node; 
        while(cur){
            Node* clone = new Node(cur->val);
            clone->next = cur->next;
            cur->next = clone;
            cur = clone->next;
        } 
        //restruct clone node;
        cur = head;
        while(cur){
            Node* s_clone = cur->next;
            if(cur->random){
                //note the cur->random->next meas the new clone node.
                s_clone->random = cur->random->next;
            }
            cur = s_clone->next;
        }
        cur = head;
        Node* ans_node = head->next;
        while(cur->next){
            Node* t_clone = cur->next;
            cur->next = t_clone->next;
            cur = t_clone;
        }
        return ans_node;
    }
};

两个链表的第一个公共节点

image-20220807211256783

树

通过前序遍历和中序遍历重构二叉树

image-20220808215217691

二叉树的下一个结点

image-20220808223154246

树的子结构

image-20220809223437158

剑指 Offer 32 - I. 从上到下打印二叉树

image-20220812202213757

打印二叉树分层打印

image-20220814213317305

打印二叉树之字打印

只需在👆题中加入 flag 判断，然后reverse即可。

二叉搜索树的后序遍历序列

image-20220815214852290

二叉搜索树与双向链表

image-20220817222332285

二叉树序列化反序列化

image-20220818232201927

二叉搜索树的第k大节点

image-20220819213239639

判断平衡二叉树

image-20220822195944823

​

输出二叉树

Screen Shot 2022-08-22 at 20.03.23

二叉树最近公共祖先

image-20220823204335775

二叉搜索树最近公共祖先

image-20220823204418306

二叉树最大宽度

image-20220829234624208

CATALOG
  1. 1. LeetCode OWNTIPS
    1. 1.1. 二分查找
    2. 1.2. 快慢指针
    3. 1.3. 合并两个链表
    4. 1.4. 滑动窗口
    5. 1.5. 二叉树的迭代-非递归遍历
    6. 1.6. 二叉树
      1. 1.6.1. 构造最大树
      2. 1.6.2. 通过前序遍历中序遍历来构造二叉树
      3. 1.6.3. 通过中序遍历后序遍历来构造二叉树
      4. 1.6.4. 寻找重复的子树
      5. 1.6.5. 二叉树的序列化与反序列化
      6. 1.6.6. 二叉搜索子树的最大键值和
      7. 1.6.7. 二叉树的最近公共祖先
      8. 1.6.8. 完全二叉树节点个数
    7. 1.7. 图
      1. 1.7.1. 所有可能的路径
      2. 1.7.2. 判断图是否有环的 DFS 算法
      3. 1.7.3. 对应课程表II 后续遍历进行反转就是拓扑排序的结果
      4. 1.7.4. 判断二分图
      5. 1.7.5. 并查集算法 (Union-Find)
        1. 1.7.5.1. 990. 等式方程的可满足性
      6. 1.7.6. kruskal最小生成树
        1. 1.7.6.1. 以图判树
        2. 1.7.6.2. 最低成本的联通所有城市
      7. 1.7.7. Prim算法：
      8. 1.7.8. 名流问题
      9. 1.7.9. Dijkstra 最小路径算法
        1. 1.7.9.1. 二叉树去掉for循环，使用类。
        2. 1.7.9.2. Dijkstra算法实现
        3. 1.7.9.3. 743. 网络延迟时间
        4. 1.7.9.4. 1631. 最小体力消耗路径
    8. 1.8. 设计数据结构系列
      1. 1.8.1. LRU 算法
      2. 1.8.2. LFU 算法
    9. 1.9. 前缀树算法
      1. 1.9.0.1. 实现前缀树
      2. 1.9.0.2. 实现前缀树II
      3. 1.9.0.3. 单词替换
      4. 1.9.0.4. 哈希集合方法
  2. 1.10. 大小堆求中位数
  3. 1.11. 单调栈结构
    1. 1.11.1. 739. 每日温度
    2. 1.11.2. 496. 下一个更大元素 I
    3. 1.11.3. 503. 下一个更大元素 II
  4. 1.12. 二叉堆实现优先级队列
    1. 1.12.0.1. 交换数组两个元素
    2. 1.12.0.2. 上浮第K个元素
  5. 1.12.1. 下沉第k个元素
    1. 1.12.1.1. 插入insert
    2. 1.12.1.2. delMax 删除最大节点
  • 1.13. 用栈实现队列
  • 1.14. 用队列实现栈
  • 1.15. 设计推特
  • 1.16. 最大栈
  • 1.17. 动态规划
    1. 1.17.1. 俄罗斯套娃问题
    2. 1.17.2. 最大回文子串
    3. 1.17.3. 目标和
    4. 1.17.4. 最长公共子序列
    5. 1.17.5. 编辑距离
    6. 1.17.6. 最大子数组和
    7. 1.17.7. 增减字符串匹配
    8. 1.17.8. 背包问题
  • 1.18. 贪心类型问题
    1. 1.18.1. 435. 无重叠区间
    2. 1.18.2. 452. 用最少数量的箭引爆气球
  • 1.19. 课程表I (区间冲突问题)
  • 1.20. 岛屿问题
    1. 1.20.1. 岛屿数量
    2. 1.20.2. 封闭岛屿数量
  • 1.21. 打家劫舍
    1. 1.21.1. 198 打家劫舍，不可循环
    2. 1.21.2. 213 可循环打家劫舍
    3. 1.21.3. 337 二叉树类型打家劫舍
  • 1.22. 动态规划最小路径和
  • 1.23. 动态规划之地下城游戏（动态规划最小路径和逆向思想）
  • 1.24. 动态规划通向“自由之路”
  • 1.25. 10. 正则表达式匹配
  • 1.26. 953. 验证外星语词典
  • 1.27. 1021 删除最外层的括号
  • 1.28. 20. 有效的括号
    1. 1.28.1. 1022. 从根到叶的二进制数之和
  • 1.29. 分冶算法——241. 为运算表达式设计优先级
  • 1.30. 31. 下一个排列
    1. 1.30.1. 设计双端循环队列
  • 1.31. 剑指Offer
  • 1.32. 栈和队列
    1. 1.32.1. 包含mini函数的栈
    2. 1.32.2. 栈的压入和弹出
    3. 1.32.3. 面试题40. 最小的k个数
    4. 1.32.4. 数据流中的中位数
    5. 1.32.5. 滑动窗口的最大值
  • 1.33. 双指针
    1. 1.33.1. 和为s的两个数字 && 和为s的连续正数序列
  • 1.34. 链表
    1. 1.34.1. 剑指 Offer 06. 从尾到头打印链表
    2. 1.34.2. 删除链表中重复的结点
    3. 1.34.3. 链表的倒数第K个节点
    4. 1.34.4. 链表中环的入口节点
    5. 1.34.5. 合并两个排序的链表
    6. 1.34.6. 复杂链表的复制
    7. 1.34.7. 两个链表的第一个公共节点
  • 1.35. 树
    1. 1.35.1. 通过前序遍历和中序遍历重构二叉树
    2. 1.35.2. 二叉树的下一个结点
    3. 1.35.3. 树的子结构
    4. 1.35.4. 剑指 Offer 32 - I. 从上到下打印二叉树
    5. 1.35.5. 打印二叉树分层打印
    6. 1.35.6. 打印二叉树之字打印
    7. 1.35.7. 二叉搜索树的后序遍历序列
    8. 1.35.8. 二叉搜索树与双向链表
    9. 1.35.9. 二叉树序列化反序列化
    10. 1.35.10. 判断平衡二叉树
    11. 1.35.11. 输出二叉树
    12. 1.35.12. 二叉树最近公共祖先
    13. 1.35.13. 二叉搜索树最近公共祖先
    14. 1.35.14. 二叉树最大宽度
    • Total : 89
    2022
    2021
    2020
    2019
    2018
    essay Deep Learning Paper-reading learning-note C++ CUDA cmake LeetCode DataStructure Numpy OS-Linux PAT slidingwindow git golang BuaaAssignments CG
    Machine-Learning Data-Structure