YOLOのBLOG
刷题笔记
felicx 化神
  2023 年 08 月 07 日 15:20 2023-08-07 15:20   2023 年 08 月 07 日 15:42      15.3k 字  69 分钟  

LeetCode Hot 100

1-1、反转链表(简)

题解1

迭代法，记录pre节点和cur节点，不断交换pre和cur，同时cur后移

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
 public:
  ListNode* reverseList(ListNode* head) {
    ListNode* pre = NULL;
    ListNode* cur = head;

    while (cur != NULL) {
      ListNode* next = cur->next;  // 这里到最后一个数字时没有next了,返回NULL
      cur->next = pre;
      pre = cur;
      cur = next;
    }
    return pre;
  }
};

题解2

递归法，假设链表其余部分已被反转，怎么去反转它前面的部分
假设a->b->c->d->e->f->NULL
若e->f已经被反转，此时在d，我们希望d->next指向c，所以d->next->next=c
这时c和d互相指向，要断开，所以d->next=NULL

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
 public:
  ListNode* reverseList(ListNode* head) {
    if (!head || !head->next) {
      return head;
    }
    ListNode* newHead = reverseList(head->next);
    head->next->next = head;
    head->next = nullptr;
    return newHead;
  }
};

1-2、反转链表Ⅱ(中)

题解

参考反转链表，这题是特定位置反转，可以根据left和right取出需要反转的链表，代入反转链表的解法进行反转，再和前后链表拼接
另外，凡是链表题都可以创建个伪头节点，如下

1
2
ListNode* dummy = new ListNode(0);
dummy->next = head;
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
class Solution {
 public:
  // 照搬反转链表
  ListNode* reverseList(ListNode* head) {
    ListNode* pre = NULL;
    ListNode* cur = head;

    while (cur != NULL) {
      ListNode* next = cur->next;
      cur->next = pre;
      pre = cur;
      cur = next;
    }
    return pre;
  }

  ListNode* reverseBetween(ListNode* head, int left, int right) {
    ListNode* dummy = new ListNode(0);
    dummy->next = head;

    ListNode* pre = dummy;
    ListNode* end = dummy;

    for (int i = 0; i < left - 1; i++)
      pre = pre->next;  // 要截取链表的头节点的前一个节点
    ListNode* start = pre->next;  // 要截取链表的头节点
    for (int i = 0; i < right; i++)
      end = end->next;  // 要截取链表的尾节点
    ListNode* next = end->next; // 要截取链表的尾节点的后一个节点
    end->next = NULL; // 截断链表,才能用于反转
    pre->next = reverseList(start);
    start->next = next; // 链表拼接

    return dummy->next;
  }
};

1-3、K个一组翻转链表(困)

题解

参考反转链表Ⅱ，反转链表Ⅱ中是给定left和right进行截取来反转，这里可以通过遍历给定的链表，每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
class Solution {
 public:
  // 照搬反转链表
  ListNode* reverseList(ListNode* head) {
    ListNode* pre = NULL;
    ListNode* cur = head;

    while (cur != NULL) {
      ListNode* next = cur->next;
      cur->next = pre;
      pre = cur;
      cur = next;
    }
    return pre;
  }

  // 微调反转链表II
  ListNode* reverseKGroup(ListNode* head, int k) {
    ListNode* dummy = new ListNode(0);
    dummy->next = head;

    ListNode* pre = dummy;
    ListNode* end = dummy;

    while (end->next != NULL) {
      ListNode* start = pre->next;  // 要截取链表的头节点
      for (int i = 0; i < k && end != NULL; i++)
        end = end->next;  // 要截取链表的尾节点
      if (end == NULL)
        break;
      ListNode* next = end->next; // 要截取链表的尾节点的后一个节点
      end->next = NULL; // 截断链表,才能用于反转
      pre->next = reverseList(start);
      start->next = next; // 链表拼接

      // 开始下一次反转
      pre = start;
      end = pre;
    }
    return dummy->next;
  }
};

2、无重复字符的最长子串(中)

题解

对于数组或字符串寻找找最xx这一类的，都可以用滑动窗口法
这里用cur_len记录窗格的大小，有不同的字符就++，有相同的就–
如何过滤窗格中的重复值，可以用set容器，因为set仅包含唯一元素
通过set::count()返回元素在集合中出现的次数（由于set容器仅包含唯一元素，因此只能返回1或0）来过滤重复值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  int lengthOfLongestSubstring(std::string s) {
    if (s.size() == 0) {
      return 0;
    }
    int max_len, cur_len = 0;
    std::set<int> lookup;
    for (int i = 0; i < s.size(); i++) {
      cur_len++;
      // 用while是因为可能有连续多个相同的字母
      while (lookup.count(s[i])) {
        lookup.erase(s[i]);
        cur_len--;
      }
      if (cur_len > max_len) {
        max_len = cur_len;
      }
      lookup.insert(s[i]);
    }
    return max_len;
  }
};

3、LRU缓存机制(中)

题解

4、数组中的第K个最大元素(困)

题解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
class Solution {
 public:
  int findKthLargest(vector<int>& nums, int k) {
    int ve_len = nums.size();
    Quick_sort(nums, 0, ve_len - 1);
    return nums[ve_len - k];
  }

  // 快排
  void Quick_sort(vector<int>& arr, int left, int right) {
    if (left >= right)
      return;
    int i, j, base, temp;
    i = left, j = right;
    base = arr[left];
    while (i < j) {
      while (arr[j] >= base && i < j)
        j--;
      while (arr[i] <= base && i < j)
        i++;

      temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
    }
    arr[left] = arr[i];
    arr[i] = base;
    Quick_sort(arr, left, i - 1);
    Quick_sort(arr, i + 1, right);
  }
};

int main() {
  int arr[6] = {3, 1, 5, 6, 4, 7};
  vector<int> nums(begin(arr), end(arr));

  Quick_sort(nums, 0, nums.size() - 1);
  for (auto i : nums) {
    cout << i << " ";
  }
  return 0;
}

题解2

既然都想到排序了，何不用C++自带的优先队列，自动帮我们排序
首先回顾下优先队列priority_queue
普通队列是先进先出；而优先队列中具有最高优先级的元素将被首先删除
如下所示，升序队列从大到小排列，top()返回的是最小值；降序队列从小到大排列，top()返回的是最大值

1
2
3
4
// 升序队列
priority_queue <int, vector<int>, greater<int>> q;
// 降序队列
priority_queue <int, vector<int>, less<int>>q;

这道题就可以直接用降序队列，把nums存进队列中，让它自个排序，再取第k个就行

1
2
3
4
5
6
7
8
9
10
11
class Solution {
 public:
  int findKthLargest(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, less<int>> maxHeap;
    for (int x : nums)
      maxHeap.push(x);
    for (int i = 0; i < k - 1; i++)
      maxHeap.pop();
    return maxHeap.top();
  }
};

题解3

面试官肯定不希望你调库，所以自己实现大根堆才是加分项
首先要回顾下堆排序，忘记了就回去看这里
大根堆就是根节点一定大过左右节点的值。
这样我们就可以根据给定的数组，创建一个大根堆，让最大的值在栈顶，然后要找第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
57
58
59
class Solution {
 public:
  int findKthLargest(vector<int>& nums, int k) {
    int n = nums.size();
    build_maxHeap(nums);  // 创建大根堆
    for (int i = 0; i < k - 1; i++) {
      // 求第i个最大值,就把栈顶的值nums[0]和叶子节点nums[n-1-i]调换
      // 除去nums[n-1-i]，剩下其余节点再调整为大根堆
      swap(nums[0], nums[n - 1 - i]);
      adjust_down(nums, 0, n - 1 - i - 1);
    }
    for (auto i : nums) {
      cout << i << " ";
    }
    return nums[0];
  }

  void build_maxHeap(vector<int>& nums) {
    int n = nums.size();
    // 堆排序最后一个非叶子节点(父节点)的序号就是n/2-1
    for (int root = n / 2 - 1; root >= 0; root--) {
      adjust_down(nums, root, n - 1);
    }
  }

  // 向下调整算法
  void adjust_down(vector<int>& nums, int root, int size) {
    // root最开始指向根节点,child是左孩子
    if (root > size)
      return;
    int temp = nums[root];  // 把堆顶存起来
    int child = 2 * root + 1;
    while (child <= size) {
      if (child + 1 <= size && nums[child] < nums[child + 1]) {
        // 有右子树而且右子树更大
        child++;
      }
      if (nums[child] > temp) {
        // 如果child比temp大,child上去填到root的位置,更新root和child,看下一层
        nums[root] = nums[child];
        root = child;
        child = 2 * root + 1;
      } else {
        break;
      }
    }
    // 不管在哪退出循环,最后都要给空位root赋值
    // 如果child > size,把temp放到叶子节点上
    nums[root] = temp;
  }
};

int main() {
  Solution s;
  vector<int> nums = {3, 2, 1, 5, 6, 4};
  int k = 4;
  s.findKthLargest(nums, k);
  return 0;
}

5-1、二叉树的中序遍历(简)

题解

中序遍历：左 -> 根 -> 右；前序遍历：根 -> 左 -> 右；后序遍历：根 -> 左 -> 右
二叉树遍历这种，最好是用stack，把需要的入栈，再按条件出栈
比如二叉树如下：

graph TD
A((1)) --> B((2))
A((1)) --> C((3))
B((2)) --> D((4))
B((2)) --> E((5))
C((3)) --> F((6))
C((3)) --> G(( ))
E((5)) --> H((7))
E((5)) --> I((8))
style G fill:#f100,stroke-width:0px %% 设置G属性为填充为白色,边框宽度为0
linkStyle 5 stroke:#0ff,stroke-width:0px %%将第6条连接线的宽度设为0,即隐形

首先每个三角形的节点顺序必须是左根右，比如4->2->5，2->1->3。
中序遍历的过程就是把左侧子树全部入栈，然后一个个出栈，并取值。
这里1<-2<-4入栈，然后4出栈，取值4；到2，2有右子树5，5入栈；
5也执行一遍中序遍历，即左子树7入栈，然后7出栈，取值7；到5，5有右子树8，8入栈。
重复直到没有子树

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
struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  explicit 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:
  std::vector<int> inorderTraversal(TreeNode* root) {
    vector<int> res;
    if (root == NULL)
      return res;
    stack<TreeNode*> s;
    TreeNode* cur = root;
    while (cur || !s.empty()) {
      if (cur) {
        s.push(cur);
        cur = cur->left;  // left
      } else {
        cur = s.top();
        s.pop();
        res.push_back(cur->val);  // root
        cur = cur->right;         // right
      }
    }
    return res;
  }
};

5-2、二叉树的前序遍历(简)

题解

首先每个三角形的节点顺序必须是根左右，比如2->4->5，1->2->3。
参考中序遍历，中序遍历是左根右，所以要左子树入栈->出栈->取值->判断右子树；
而先序遍历是根左右，所以要取值->左子树入栈->出栈->判断右子树

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> preorderTraversal(TreeNode* root) {
    vector<int> res;
    if (root == NULL)
      return res;
    stack<TreeNode*> s;
    TreeNode* cur = root;
    while (cur || !s.empty()) {
      if (cur) {
        res.push_back(cur->val);  // root
        s.push(cur);
        cur = cur->left;  // left
      } else {
        cur = s.top();
        s.pop();
        cur = cur->right;  // right
      }
    }
    return res;
  }
};

5-3、二叉树的后序遍历(简)

题解1

首先每个三角形的节点顺序必须是左右根，比如4->5->2，2->3->1。
参考前序遍历的根左右，输出根右左，然后倒序，就是左右根

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  vector<int> postorderTraversal(TreeNode* root) {
    vector<int> res;
    if (root == NULL)
      return res;
    stack<TreeNode*> s;
    TreeNode* cur = root;
    while (cur || !s.empty()) {
      if (cur) {
        res.push_back(cur->val);  // root
        s.push(cur);
        cur = cur->right;  // right
      } else {
        cur = s.top();
        s.pop();
        cur = cur->left;  // left
      }
    }
    reverse(res.begin(), res.end());
    return res;
  }
};

题解2

顺便记录下递归的写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
 public:
  void postorder(TreeNode* root, vector<int>& res) {
    if (root == nullptr) {
      return;
    }
    postorder(root->left, res);
    postorder(root->right, res);
    res.push_back(root->val);
  }

  vector<int> postorderTraversal(TreeNode* root) {
    vector<int> res;
    postorder(root, res);
    return res;
  }
};

5-4、二叉树的层序遍历(中)

题解

首先要知道遍历二叉树，DFS和BFS的顺序是不一样的
image
从gif图可以看出，前中后序遍历就是DFS遍历，层序遍历就类似BFS遍历，不同的是BFS是输出一个一维数组，而层序遍历要求我们区分每一层，也就是返回一个二维数组
那首先我们可以先实现BFS遍历，用队列来存储遍历的节点，因为队列是先进先出，顺序不会乱

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 二叉树的BFS遍历
class Solution {
 public:
  vector<int> levelOrder(TreeNode* root) {
    vector<int> res;
    queue<TreeNode*> q;
    if (root != NULL) {
      q.push(root);
    }
    while (!q.empty()) {
      TreeNode* node = q.front();
      q.pop();
      res.push_back(node->val);
      if (node->left != NULL) {
        q.push(node->left);
      }
      if (node->right != NULL) {
        q.push(node->right);
      }
    }
    return res;
  }
};

有了BFS遍历，怎么把每一层的分别记录下来呢
很简单，在每一层遍历开始前，先记录队列中的结点数量n（也就是这一层的结点数量），然后一口气处理完这一层的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
class Solution {
 public:
  vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> res;
    queue<TreeNode*> q;
    if (root != NULL) {
      q.push(root);
    }
    while (!q.empty()) {
      int n = q.size();
      vector<int> temp;
      for (int i = 0; i < n; i++) {
        TreeNode* node = q.front();
        q.pop();
        temp.push_back(node->val);
        if (node->left != NULL) {
          q.push(node->left);
        }
        if (node->right != NULL) {
          q.push(node->right);
        }
      }
      res.push_back(temp);
    }
    return res;
  }
};

6-1、两数之和(简)

题解

当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。
数组可以做哈希表，set也可以，map也可以，用哪个呢
对于这道题，不仅要知道元素有没有遍历过，还有知道这个元素对应的下标。需要使用key-value结构来存放，key来存元素，value来存下标，那么使用map正合适
而C++中map有三种类型，如下所示:

映射 底层实现 是否有序 key的数量 能否更改数值 查询效率 增删效率
std::map 红黑树 key有序 只能有一个key key不可修改 O(log n) O(log n)
std::multimap 红黑树 key有序 可以有多个key key不可修改 O(log n) O(log n)
std::map 哈希表 key无序 只能有一个key key不可修改 O(1) O(1)

这道题目中并不需要key有序，所以选择std::unordered_map效率更高
接下来就很简单了，首先把数组中的元素作为key，value用来存下标；
我们只需要查找map中是否存在target-nums[i]的值，没有就将(nums[i],i)加入map，继续遍历即可

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> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> num_map;
    vector<int> res;
    for (int i = 0; i < nums.size(); i++) {
      auto iter = num_map.find(target - nums[i]);
      if (iter != num_map.end()) {
        res = {iter->second, i};
        break;
      }
      num_map.insert(pair<int, int>(nums[i], i));
    }
    return res;
  }
};

int main() {
  Solution s;
  vector<int> nums = {2, 7, 11, 15};
  int target = 22;
  vector<int> res = s.twoSum(nums, target);
  for (auto i : res) {
    cout << i << " ";
  }
}

6-2、三数之和(中)

题解

这道题只用求值，不用求下标，就不需要用哈希表了，用双指针就是最方便的。
从小到大排序后，就可以用双指针了
因为有需要三个数，可以固定一个数a，双指针遍历剩下的数组，求双指针之和target为0-a即可
left为数组头，right为数组尾，大于target则right--，小于target则left++
主要是去重，因为有可能数组中同一个数字出现多次，排完序后，相同的数字会连在一起，只要将当前的值和前一个值比就可以去重了

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
class Solution {
 public:
  vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> res;
    sort(nums.begin(), nums.end());
    // 目的是找出a + left + right = 0
    for (int i = 0; i < nums.size(); i++) {
      if (nums[i] > 0) {
        return res;
      }
      if (i > 0 && nums[i] == nums[i - 1]) {
        // 去重a
        continue;
      }
      int left = i + 1;
      int right = nums.size() - 1;
      int target = 0 - nums[i];
      while (left < right) {
        if (nums[left] + nums[right] > target) {
          right--;
        } else if (nums[left] + nums[right] < target) {
          left++;
        } else {
          res.push_back({nums[i], nums[left], nums[right]});
          // 找到答案时，双指针同时收缩
          left++;
          right--;
          while (left < right && nums[left] == nums[left - 1]) {
            // 去重left
            left++;
          }
          while (left < right && nums[right] == nums[right + 1]) {
            // 去重right
            right--;
          }
        }
      }
    }
  }
  return res;
};

6-3、最接近的三数之和(中)

题解

和三数之和非常类似，求与target最接近的三元组，即差值的绝对值最小。
和三数之和一样，从小到大排序后，固定一个数a，求双指针之和尽可能接近target-a即可
如果a+b+c>target，right--；如果a+b+c<target，left++，同时和三数之和一样需要去重，只是增加一步，在和taget比较之前，需要先update一下三数之和，记录下最接近target的值

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:
  int threeSumClosest(vector<int>& nums, int target) {
    int best = 1e7;
    // 根据差值的绝对值来更新答案
    auto update = [&](int cur) {
      // auto的特殊用法
      if (abs(cur - target) < abs(best - target)) {
        best = cur;
      }
    };

    sort(nums.begin(), nums.end());
    // 目的是找出a + left + right = 0
    for (int i = 0; i < nums.size(); i++) {
      if (i > 0 && nums[i] == nums[i - 1]) {
        // 去重a
        continue;
      }
      int left = i + 1;
      int right = nums.size() - 1;
      while (left < right) {
        int sum = nums[i] + nums[left] + nums[right];
        if (sum == target) {
          return target;
        }
        update(sum);
        if (sum > target) {
          right--;
          while (right > left && nums[right] == nums[right + 1]) {
            // 去重right
            right--;
          }
        } else {
          left++;
          while (right > left && nums[left] == nums[left - 1]) {
            // 去重left
            left++;
          }
        }
      }
    }
    return best;
  }
};

7、手撕快速排序(中)

题解

8、最大子数组和(中)

题解

9、合并两个有序链表(简)

题解

10-1、搜索旋转排序数组(中)

题解

首先要明白这道题问的是啥，很简单就是从给定的数组中找出target的下标。
那为啥题目描述的花里胡哨的，还有什么旋转呢，主要是怕你想不到，因为要设计O(log n)的算法，单纯暴力搜索肯定是不行的。那是不是可以用二分法呢？严格来说，标准的二分法只适用于有序数组，但题目给我们的是旋转后的数组，它不是有序的，所以需要对二分法进行修改变形。
这个旋转后的数组有什么特点呢？可以发现的是，我们将数组从中间分开成左右两部分的时候，一定有一部分的数组是有序的。
所以我们在常规二分查找的时候，可以查看当前mid为分割位置分割出来的两个部分[left, mid]和[mid+1, right]哪个部分是有序的，根据有序的那部分判断出target在不在这个部分。
所以我们在用二分法时有两种情况:
1、若nums[0] ≤ nums[mid]，说明[left, mid]是有序的，则当nums[0] ≤ target < nums[mid]时target在[left, mid-1]中，否则在[mid+1, right]中；
2、若nums[0] > nums[mid]，说明[mid+1, right]是有序的，则当nums[mid] < target ≤ nums[size-1]时target在[mid+1, right]中，否则在[left, mid-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
class Solution {
 public:
  int search(vector<int>& nums, int target) {
    if (nums.empty()) {
      return -1;
    }
    int n_size = nums.size();
    int left = 0;
    int right = n_size - 1;
    int res = -1;
    while (left <= right) {
      int mid = (left + right) / 2;
      if (nums[mid] == target) {
        res = mid;
        break;
      }
      if (nums[0] <= nums[mid]) {
        if (nums[0] <= target && target < nums[mid]) {
          right = mid - 1;
        } else {
          left = mid + 1;
        }
      } else {
        if (nums[mid] < target && target <= nums[n_size - 1]) {
          left = mid + 1;
        } else {
          right = mid - 1;
        }
      }
    }
    return res;
  }
};

int main() {
  Solution s;
  vector<int> nums = {4, 5, 6, 7, 0, 1, 2};
  cout << s.search(nums, 0);
}

10-2、搜索旋转排序数组 II(中)

题解

和上一题一样，只不过因为数组中有重复元素，二分查找时可能会有num[left] = num[mid] = num[right]。
比如数组[3,1,2,3,3,3,3]，target = 2，首次二分时无法判断区间[0, 3]和[4, 6]哪个是有序的。
对于这种情况，我们只能将当前二分区间的左边界加一，右边界减一，然后在新区间上继续二分查找。

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
class Solution {
 public:
  int search(vector<int>& nums, int target) {
    if (nums.empty()) {
      return -1;
    }
    int n_size = nums.size();
    int left = 0;
    int right = n_size - 1;
    bool res = false;
    while (left <= right) {
      int mid = (left + right) / 2;
      if (nums[mid] == target) {
        res = true;
        break;
      }
      if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
        left++;
        right--;
      } else if (nums[0] <= nums[mid]) {
        if (nums[0] <= target && target < nums[mid]) {
          right = mid - 1;
        } else {
          left = mid + 1;
        }
      } else {
        if (nums[mid] < target && target <= nums[n_size - 1]) {
          left = mid + 1;
        } else {
          right = mid - 1;
        }
      }
    }
    return res;
  }
};

10-3、寻找旋转排序数组中的最小值(中)

题解

首先对于这个旋转数组，它的特点是：
1、以最小值为分界线的左子序列是单调递增的，右子序列也是单调递增的；
2、对于数组中最后一个元素x，左子序列全大于x，右子序列全小于x。
通过nums[mid]和nums[right]比较，判断nums[mid]在左子序列还是右子序列。
右两种情况：
1、如果nums[mid] < nums[right]，则mid在右子序列，即在最小值右边，所以right左移；
2、如果nums[mid] > nums[right]，则mid在左子序列，即在最小值右左边，所以left右移。

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:
  int findMin(vector<int>& nums) {
    int left = 0;
    int right = nums.size() - 1;
    while (left < right) {
      int mid = (left + right) / 2;
      if (nums[mid] < nums[right]) {
        right = mid;  // right左移
        // 为什么right=mid,而不是right=mid-1;
        // nums[mid]<nums[right]时,有可能nums[mid]本身就是最小值,然后mid-1就错过了,所以不要减1.比如{4,5,1,2,3},如果right=mid-1,则丢失了最小值1
      } else {
        left = mid + 1;  // left右移
        // 为什么low=mid+1,而不是low=mid;
        // 因为我们这题是求最小值,而nums[mid]>nums[right],自然nums[mid]绝对不会是最小值,所以可以+1过滤掉mid这个下标.比如{4,5,6,1,2,3},nums[mid]=6,low=mid+1,刚好nums[low]=1
      }
    }
    return nums[left];
    // 这里返回的是left,所以只能while(left<right).如果返回的是right,就可以while(left<=right)和while(left<right);
    // 因为若循环条件为while(left<=right),则进入最后一个循环的时候,left=right=mid,都指向最小值,接着执行left=mid+1.这时left便跑到mid和right右边一位去了,因此若要用while(left<=right)条件必须返回 nums[right]或者nums[left-1].
  }
};

10-4、寻找旋转排序数组中的最小值 II(困)

题解

这道题和上一题区别就在于数组元素是可以重复的，所以对于右重复元素的旋转数组，它的特点是：
1、以最小值为分界线的左子序列是单调递增的，右子序列也是单调递增的；
2、对于数组中最后一个元素x，左子序列全大于或等于x，右子序列全小于或等于x。
同样通过nums[mid]和nums[right]比较，判断nums[mid]在左子序列还是右子序列。只不过因为右重复值，所以多了一种情况。
有三种情况：
1、如果nums[mid] < nums[right]，则mid在右子序列，即在最小值右边，所以right左移；
2、如果nums[mid] > nums[right]，则mid在左子序列，即在最小值右左边，所以left右移；
3、如果nums[mid] = nums[right]，则不能确定mid在左子序列还是右子序列；由于它们的值相同，所以无论nums[right]是不是最小值，都有一个最小值nums[mid]，因此我们可以忽略二分查找区间的右端点。
解释下第3点，比如数组[1,0,1,1,1]，left = 0，right = 4，mid = 2，无法判断mid在在左子序列还是右子序列，我们采用right--解决此问题
那这个操作会不会影响取最小值呢，证明如下：
1、此操作不会使数组越界：因为迭代条件保证了right>left>=0；
2、此操作不会使最小值丢失：假设nums[right]是最小值，有两种情况：
2-1、若nums[right]是唯一最小值：那就不可能满足判断条件nums[mid]==nums[right]，因为mid<right（left!=right && mid=(left + right)/2）；
2-2、若nums[right]不是唯一最小值，由于mid<right而nums[mid]==nums[right]，即还有最小值存在于[left,right−1]区间，因此不会丢失最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
 public:
  int findMin(vector<int>& nums) {
    int left = 0;
    int right = nums.size() - 1;
    while (left < right) {
      int mid = (left + right) / 2;
      if (nums[mid] < nums[right]) {
        right = mid;  // right左移
      } else if (nums[mid] > nums[right]) {
        left = mid + 1;  // left右移
      } else {
        right--;
      }
    }
    return nums[left];
  }
};

11-1、买卖股票的最佳时机(简)

题解1

用一个变量记录一个最低价格min_price，在第i天卖出股票能得到的利润就是prices[i]-min_price
我们只需要遍历一遍价格数组，求出每一天卖出股票得到的利润，取最大值max_profit，同时更新最低价格min_price

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
  int maxProfit(vector<int>& prices) {
    int min_price = INT_MAX;
    int max_profit = 0;
    for (auto price : prices) {
      max_profit = max(max_profit, price - min_price);
      min_price = min(min_price, price);
    }
    return max_profit;
  }
};

题解2

这道题是最基础的动态规划，下面讲下证明用动态规划解决。
题目只问最大利润，没有问这几天具体哪一天买、哪一天卖，因此可以考虑使用 动态规划的方法来解决。
根据题目意思，有以下两个约束条件：1、不能在买入股票前卖出股票；2、最多只允许完成一笔交易。
首先先定义好现金数这个概念，买入股票手上的现金数减少，卖出股票手上的现金数增加。对于这道题，当天是否持股会影响现金数，因为持股表示你还没卖掉，不持股表示卖掉了。
所以动态规划的状态需要用到二维数组表示，一方面表示第几天，一方面表示是否持股。
1、状态定义：

  • dp[i][0]表示第i天，不持股，手上拥有的现金数
  • dp[i][1]表示第i天，持股，手上拥有的现金数

2、状态转移方程：
第1天，dp[0][0] = 0，dp[0][1] = -prices[0]
第i天，对于dp[i][0]，有两种情况

  • 昨天不持股，今天什么都不做
  • 昨天持股，今天卖出股票（现金数增加）

因此dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
同样对于dp[i][1]，也有两种情况

  • 昨天持股，今天什么都不做（现金数与昨天一样）
  • 昨天不持股，今天买入股票（注意：只允许交易一次，因此手上的现金数就是当天的股价的相反数）

因此dp[i][1] = max(dp[i-1][1], -prices[i])

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 Solution {
 public:
  int maxProfit(vector<int>& prices) {
    int n = prices.size();
    if (n < 2) {
      return 0;
    }
    // vector<vector<int>> dp(n, vector<int>(2));
    // 数据量大尽量用数组,vector操作太耗时
    int dp[n][2];

    // dp[i][0],下标为i这天结束的时候,不持股,手上拥有的现金数
    // dp[i][1],下标为i这天结束的时候,持股,手上拥有的现金数
    // 初始化:不持股显然为0,持股就需要减去第1天(下标为0)的股价
    dp[0][0] = 0;
    dp[0][1] = -prices[0];

    // 从第2天开始遍历
    for (int i = 1; i < n; i++) {
      dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
      dp[i][1] = max(dp[i - 1][1], -prices[i]);
    }
    return dp[n - 1][0];
  }
};

11-2、买卖股票的最佳时机 II(中)

题解

和上一题一样，状态定义不变，只不过状态方程有点变化。
第i天，对于dp[i][0]，有两种情况

  • 昨天不持股，今天什么都不做
  • 昨天持股，今天卖出股票（现金数增加）

因此dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
同样对于dp[i][1]，也有两种情况

  • 昨天持股，今天什么都不做（现金数与昨天一样）
  • 昨天不持股，即dp[i-1][0]，今天买入股票（注意：允许交易多次，因此手上的现金数就是dp[i-1][0]-prices[i]）

因此dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])。
其余照搬

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  int maxProfit(vector<int>& prices) {
    int n = prices.size();
    if (n < 2) {
      return 0;
    }
    int dp[n][2];

    dp[0][0] = 0;
    dp[0][1] = -prices[0];

    // 从第2天开始遍历
    for (int i = 1; i < n; i++) {
      dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
      dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
    }
    return dp[n - 1][0];
  }
};

11-3、买卖股票的最佳时机 III(困)

题解

分析步骤参照11-1题，但这道题状态比11-1多。一天结束时，可能有持股、可能未持股、可能卖出过1次、可能卖出过2次、也可能未卖出过
所以定义状态转移数组dp[天数][当前是否持股][卖出的次数]
1、状态定义：

  • dp[i][0][0]表示第i天，不持股，不卖出过股票，手上拥有的现金数
  • dp[i][0][1]表示第i天，不持股，卖出1次股票，手上拥有的现金数
  • dp[i][0][2]表示第i天，不持股，卖出2次股票，手上拥有的现金数
  • dp[i][1][0]表示第i天，持股，不卖出过股票，手上拥有的现金数
  • dp[i][1][1]表示第i天，持股，卖出1次股票，手上拥有的现金数
  • dp[i][1][2]表示第i天，持股，卖出2次股票，手上拥有的现金数

2、状态转移方程：
第1天有，

  • 第1天休息：dp[0][0][0] = 0
  • 第1天买入：dp[0][1][0] = -prices[0]
  • 第1天不可能已经有卖出：dp[0][0][1] = float('-inf')、dp[0][0][2] = float('-inf')
  • 第一天不可能已经卖出：dp[0][1][1] = float('-inf')、dp[0][1][2] = float('-inf')

第i天有，

  • 对于dp[i][0][0]，有一种情况，未持股，未卖出过，说明从未进行过买卖。
    因此dp[i][0][0] = 0
  • 对于dp[i][0][1]，有两种情况，未持股，卖出过1次，可能是之前卖的，可能是今天卖的。因此dp[i][0][1]=max(dp[i-1][0][1], dp[i-1][1][0]+prices[i])
  • 对于dp[i][0][2]，有两种情况，未持股，卖出过2次，可能是之前卖的，可能是今天卖的。因此dp[i][0][2]=max(dp[i-1][0][2], dp[i-1][1][1]+prices[i])
  • 对于dp[i][1][0]，有两种情况，持股，未卖出过，可能是之前买的，可能是今天买的。因此dp[i][0][1]=max(dp[i-1][1][0], dp[i-1][0][0]-prices[i])
  • 对于dp[i][1][1]，有两种情况，持股，卖出过1次，可能是之前买的，可能是今天买的。因此dp[i][0][1]=max(dp[i-1][1][1], dp[i-1][0][1]-prices[i])
  • 对于dp[i][1][2]，有两种情况，持股，卖出过2次，不可能（因为最多只允许买卖两次）。因此dp[i][1][2]=float('-inf')
    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:
      int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n < 2) {
          return 0;
        }
        int MIN_VALUE = INT_MIN / 2;
        // 这里除2是因为最小值加上1就变成最大值了,会影响max()函数的结果,除数只要比1大就行
        int dp[n][2][3];

        dp[0][0][0] = 0;           // 第一天休息
        dp[0][1][0] = -prices[0];  // 第一天买入
        dp[0][0][1] = MIN_VALUE;   // 第一天不可能已经有卖出
        dp[0][0][2] = MIN_VALUE;   // 第一天不可能已经卖出
        dp[0][1][1] = MIN_VALUE;
        dp[0][1][2] = MIN_VALUE;

        // 从第2天开始遍历
        for (int i = 1; i < n; i++) {
          dp[i][0][0] = 0;  // 未持股，未卖出过
          dp[i][0][1] = max(dp[i - 1][1][0] + prices[i],
                            dp[i - 1][0][1]);  // 未持股，卖出过1次
          dp[i][0][2] = max(dp[i - 1][1][1] + prices[i],
                            dp[i - 1][0][2]);  // 未持股，卖出过2次
          dp[i][1][0] =
              max(dp[i - 1][0][0] - prices[i], dp[i - 1][1][0]);  // 持股，未卖出过
          dp[i][1][1] =
              max(dp[i - 1][0][1] - prices[i], dp[i - 1][1][1]);  // 持股，卖出过1次
          dp[i][1][2] = MIN_VALUE;  // 持股，卖出过2次
        }
        return max(max(dp[n - 1][0][1], dp[n - 1][0][2]), 0);
      }
    };

12-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
class Solution {
 public:
  bool hasCycle(ListNode *head) {
    if (!head || !head->next) {
      return false;
    }
    ListNode *slow = head;
    ListNode *fast = head;
    while (fast->next && fast->next->next) {
      if(!slow->next) {
        return false;		// 稍微加个判断，减少下用时
      }
      slow = slow->next;
      fast = fast->next->next;
      if (fast == slow) {
        return true;
      }
    }
    return false;
  }
};

// 另一种表示方法是
slow = head;
fast = head->next;
// 两种方式不同点在于,一般用fast=head->next较多,因为这样可以知道中点的上一个节点,可以用来删除等操作
// fast如果初始化为head->next,则中点在slow->next
// fast初始化为head,则中点在slow

12-2、环形链表 II(中)

题解

这道题是要求入环点，首先要判断有环，这个就直接照搬上一题。主要是怎么找入环点。可以看下面这张图
image
F为第一个节点-F到入环点0的距离；
a为入环点0到相遇点h距离；
b为相遇点h到入环点0距离；
当fast和slow相遇时，因为fast每次走两步，slow每次一步，所以fast走过的是slow的两倍，设slow走过为S，则S=F+a，2S=F+a+b+a，故F=b；
现在让slow返回第一个节点，fast处于第一次相遇的节点，此时slow从第一个节点出发，因为F=b，所以fast和slow会在入环口第二次相遇，即为所求节点。

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:
  ListNode* detectCycle(ListNode* head) {
    if (!head || !head->next) {
      return NULL;
    }
    bool hasCycle = false;
    // 先判断是否有环
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast->next && fast->next->next) {
      if (!slow->next) {
        break;
      }
      slow = slow->next;
      fast = fast->next->next;
      if (fast == slow) {
        hasCycle = true;
        break;
      }
    }
    // 有环则找入环开始的节点
    if (hasCycle) {
      slow = head;
      while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
      }
      return slow;
    }
    return NULL;
  }
};

13-1、岛屿数量(中)

题解

我们知道，DFS通常是在树或者图结构上进行的，而我们这道题是网格，能不能用DFS呢？可以，记住，凡是网格的都应该想到用DFS，岛屿问题就是一类典型的网格问题。
首先我们要清楚DFS的基本结构，先看简单的二叉树DFS遍历结构

1
2
3
4
5
6
7
8
9
void traverse(TreeNode* root) {
  // 判断base case
  if (root == NULL) {
    return;
  }
  // 访问两个相邻结点:左子结点,右子结点
  traverse(root->left);
  traverse(root->right);
}

可以看到，二叉树的DFS有两个要素：访问相邻结点、判断base case
1、二叉树的相邻结点非常简单，只有左子结点和右子结点两个。二叉树本身就是一个递归定义的结构：一棵二叉树，它的左子树和右子树也是一棵二叉树。那么我们的DFS遍历只需要递归调用左子树和右子树即可。
2、二叉树遍历的base case是root == Null。这样一个条件判断其实有两个含义：一方面，这表示 root 指向的子树为空，不需要再往下遍历了。另一方面，在root == Null的时候及时返回，可以让后面的root->left和root->right操作不会出现空指针异常。

那么对于网格上的DFS，我们完全可以参考二叉树的DFS，写出网格DFS的两个要素。
1、首先看相邻结点。很明显，网格结构中的格子的相邻结点是上下左右四个，即(row-1, col),(row+1, col),(row, col-1),(row, col+1)
2、然后是base case。根据二叉树的对应过来，是超出网格范围的格子，即row >= grid.size() || col >= grid[0].size() || row < 0 || col < 0。

根据分析，可以得出网格DFS遍历的框架代码：

1
2
3
4
5
6
7
8
9
10
11
void dfsGrid(vector<vector<char>>& grid, int row, int col) {
  if (row >= grid.size() || col >= grid[0].size() || row < 0 || col < 0) {
    // 防止row和col越界(上下左右)
    return;
  }

  dfsGrid(grid, row - 1, col);  // 上
  dfsGrid(grid, row + 1, col);  // 下
  dfsGrid(grid, row, col - 1);  // 左
  dfsGrid(grid, row, col + 1);  // 右
}

这里有个问题，这么避免重复值，比如下面这张图，dfsGrid遍历时会一直在这里不断循环。
image
简单的方法就是标记已经遍历过的格子。比如岛屿问题，把走过的陆地格子的值改为2.这样就能得到一个网格DFS遍历的通用框架代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void dfsGrid(vector<vector<char>>& grid, int row, int col) {
  if (row >= grid.size() || col >= grid[0].size() || row < 0 || col < 0) {
    // 防止row和col越界(上下左右)
    return;
  }

  if (grid[row][col] != '1') {
    // 遍历到海洋或者已经遍历过的陆地,退出
    return;
  }

  grid[row][col] = '2';         // 去重,防止多次遍历
  dfsGrid(grid, row - 1, col);  // 上
  dfsGrid(grid, row + 1, col);  // 下
  dfsGrid(grid, row, col - 1);  // 左
  dfsGrid(grid, row, col + 1);  // 右
}

有了网格DFS遍历的通用框架，我们只需要用两层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
26
27
28
29
30
31
32
33
34
class Solution {
 public:
  int numIslands(vector<vector<char>>& grid) {
    int res = 0;
    // 两层for循环,遍历整张二维表格中所有的陆地,i是行,j是列
    for (int i = 0; i < grid.size(); i++) {
      for (int j = 0; j < grid[0].size(); j++) {
        if (grid[i][j] == '1') {
          dfsGrid(grid, i, j);  // 深度递归，遍历所有的陆地
          res++;
        }
      }
    }
    return res;
  }

  void dfsGrid(vector<vector<char>>& grid, int row, int col) {
    if (row >= grid.size() || col >= grid[0].size() || row < 0 || col < 0) {
      // 防止row和col越界(上下左右)
      return;
    }

    if (grid[row][col] != '1') {
      // 遍历到海洋或者已经遍历过的陆地,退出
      return;
    }

    grid[row][col] = '2';         // 去重,防止多次遍历
    dfsGrid(grid, row - 1, col);  // 上
    dfsGrid(grid, row + 1, col);  // 下
    dfsGrid(grid, row, col - 1);  // 左
    dfsGrid(grid, row, col + 1);  // 右
  }
};

13-2、岛屿的周长(简)

题解

这道题最牛逼的一点是你要想到，岛屿的周长就是岛屿方格和非岛屿方格相邻的边的数量（如下图所示）。也就是说，在DFS遍历中，从一个岛屿方格走向一个非岛屿方格，就将周长加1。
image
所以，我们可以修改下网格DFS遍历的通用框架：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int dfsGrid(vector<vector<int>>& grid, int row, int col) {
  if (row >= grid.size() || col >= grid[0].size() || row < 0 || col < 0) {
    // 从一个岛屿方格走向网格边界,周长加1
    return 1;
  }
  if (grid[row][col] == 0) {
    // 从一个岛屿方格走向水域方格,周长加1
    return 1;
  }
  if (grid[row][col] != 1) {
    // 过滤掉已经遍历过的
    return 0;
  }

  grid[row][col] = 2;  // 去重,防止多次遍历
  int res = dfsGrid(grid, row - 1, col) + dfsGrid(grid, row + 1, col) +
            dfsGrid(grid, row, col - 1) + dfsGrid(grid, row, col + 1);
  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
class Solution {
 public:
  int islandPerimeter(vector<vector<int>>& grid) {
    for (int i = 0; i < grid.size(); i++) {
      for (int j = 0; j < grid[0].size(); j++) {
        if (grid[i][j] == 1) {
          return dfsGrid(grid, i, j);
        }
      }
    }
    return 0;
  }

  int dfsGrid(vector<vector<int>>& grid, int row, int col) {
    if (row >= grid.size() || col >= grid[0].size() || row < 0 || col < 0) {
      // 从一个岛屿方格走向网格边界,周长加1
      return 1;
    }
    if (grid[row][col] == 0) {
      // 从一个岛屿方格走向水域方格,周长加1
      return 1;
    }
    if (grid[row][col] != 1) {
      // 过滤掉已经遍历过的
      return 0;
    }

    grid[row][col] = 2;  // 去重,防止多次遍历
    int res = dfsGrid(grid, row - 1, col) + dfsGrid(grid, row + 1, col) +
              dfsGrid(grid, row, col - 1) + dfsGrid(grid, row, col + 1);
    return res;
  }
};

13-3、岛屿的最大面积(中)

题解

从上面两道我们已经知道怎么计算岛屿数量和一个岛屿的周长，这道题是结合了上面两道。
因此我们可以对每个岛屿计算它的面积，最后返回最大的那个面积即可。

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
class Solution {
 public:
  int maxAreaOfIsland(vector<vector<int>>& grid) {
    int res = 0;
    for (int i = 0; i < grid.size(); i++) {
      for (int j = 0; j < grid[0].size(); j++) {
        if (grid[i][j] == 1) {
          res = max(dfsGrid(grid, i, j), res);
        }
      }
    }
    return res;
  }

  int dfsGrid(vector<vector<int>>& grid, int row, int col) {
    if (row >= grid.size() || col >= grid[0].size() || row < 0 || col < 0) {
      // row和col越界,都不算岛屿中的陆地,面积为0
      return 0;
    }
    if (grid[row][col] != 1) {
      // 遍历到海洋或者已经遍历过的陆地,面积为0
      return 0;
    }

    grid[row][col] = 2;  // 去重,防止多次遍历
    int res = dfsGrid(grid, row - 1, col) + dfsGrid(grid, row + 1, col) +
              dfsGrid(grid, row, col - 1) + dfsGrid(grid, row, col + 1) +
              1;  // 加1是因为第一次肯定是一块陆地才进来的dfsGrid
    return res;
  }
};

13-4、最大人工岛(困)

题解

这道题是13-3的升级版，现在我们可以将一个海洋变成陆地，从而连接两个岛屿。那我们就需要先统计各个岛屿面积，找到最大的岛屿；然后把一个海洋变成陆地，再统计一遍连接后各个岛屿面积，找到最大的岛屿。
因此需要两次DFS遍历
1、划分岛屿，给每个岛屿标号
标号要标什么呢？假设我们在所有的格子上标记出岛屿的面积。然后搜索哪个海洋格子相邻的两个岛屿面积最大。例如下图中红色方框内的海洋格子，上边、左边都与岛屿相邻，我们可以计算出它变成陆地之后可以连接成的岛屿面积为7 + 1 + 2 = 10。
image
然而，这种做法可能遇到一个问题。如下图中红色方框内的海洋格子，它的上边、左边都与岛屿相邻，这时候连接成的岛屿面积难道是7 + 1 + 7 = 15？显然不是。这两个7来自同一个岛屿，所以填海造陆之后得到的岛屿面积应该只有7 + 1 = 8。
image
可以看到，要让算法正确，我们得能区分一个海洋格子相邻的两个7是不是来自同一个岛屿。那么，我们不能在方格中标记岛屿的面积，而应该用map记录每个岛屿面积，给每个岛屿标记map的key。如下图所示。这样我们就可以发现红色方框内的海洋格子，它的两个相邻的岛屿实际上是同一个。
image
2、填充海洋，连接四周的岛屿
和上面类似，要遍历每个海洋格子上下左右的格子。又因为我们已经有map来记录了各个岛屿的面积，所以只需要在遍历时发现是岛屿，加上对应的面积即可，不需要再全部遍历该岛屿的陆地。
要注意的是，我们是将一个海洋变为陆地，所以海洋会占一个面积。

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
class Solution {
 public:
  unordered_map<int, int> area;  // 存放各岛屿面积

 public:
  int largestIsland(vector<vector<int>>& grid) {
    int res = 0;
    int index = 2;  // 从2开始是为了和陆地的1做区分,防止多次遍历
    // 不同岛屿用不同的数字标记,统计各岛屿面积,同时记录最大值
    for (int i = 0; i < grid.size(); i++) {
      for (int j = 0; j < grid[0].size(); j++) {
        if (grid[i][j] == 1) {
          area[index] = dfsGrid(grid, i, j, index);
          res = max(res, area[index]);
          index++;
        }
      }
    }
    // 连接岛屿
    for (int i = 0; i < grid.size(); i++) {
      for (int j = 0; j < grid.size(); j++) {
        if (grid[i][j] == 0) {
          res = max(res, linkland(grid, i, j));
        }
      }
    }
    return res;
  }

  int dfsGrid(vector<vector<int>>& grid, int row, int col, int index) {
    if (row >= grid.size() || col >= grid[0].size() || row < 0 || col < 0) {
      return 0;
    }
    if (grid[row][col] != 1) {
      return 0;
    }

    grid[row][col] = index;
    int res = dfsGrid(grid, row - 1, col, index) +
              dfsGrid(grid, row + 1, col, index) +
              dfsGrid(grid, row, col - 1, index) +
              dfsGrid(grid, row, col + 1, index) + 1;
    return res;
  }

  int linkland(vector<vector<int>>& grid, int row, int col) {
    unordered_set<int> around;
    int linkarea = 1;  // 海洋占一个面积
    if (row - 1 >= 0 && grid[row - 1][col] > 1) {
      // 左
      around.insert(grid[row - 1][col]);
    }
    if (row + 1 < grid.size() && grid[row + 1][col] > 1) {
      // 右
      around.insert(grid[row + 1][col]);
    }
    if (col - 1 >= 0 && grid[row][col - 1] > 1) {
      // 上
      around.insert(grid[row][col - 1]);
    }
    if (col + 1 < grid.size() && grid[row][col + 1] > 1) {
      // 下
      around.insert(grid[row][col + 1]);
    }
    for (auto i : around) {
      linkarea += area[i];
    }
    return linkarea;
  }
};

14、有效的括号(简)

题解1

首先要知道哪些case是有效的，比如{()}是有效的，{(})是无效的。
这种有对称性的，一般都是用栈来解决。
遇到一个左括号，先入栈；遇到一个右括号，我们需要将一个相同类型的左括号闭合。
此时，我们可以取出栈顶的左括号并判断它们是否是相同类型的括号。如果不是相同的类型，或者栈中并没有左括号，则字符串无效。
问题是怎么判断括号的类型呢？可以使用哈希表存储每一种括号。哈希表的键为右括号，值为相同类型的左括号。
在遍历结束后，如果栈中没有左括号，说明我们将字符串中的所有左括号闭合，返回true，否则false。
另外有效字符串的长度一定为偶数，因此如果字符串的长度为奇数，我们可以直接返回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 {
 public:
  bool isValid(string s) {
    if (s.empty()) {
      return true;
    }
    int n = s.size();
    if (n % 2 == 1) {
      return false;
    }

    unordered_map<char, char> pairs = {{')', '('}, {']', '['}, {'}', '{'}};
    stack<char> stk;
    for (char ch : s) {
      if (pairs.count(ch)) {
        if (stk.empty() || stk.top() != pairs[ch]) {
          return false;
        }
        stk.pop();
      } else {
        stk.push(ch);
      }
    }
    if (stk.empty()) {
      return true;
    }
    return false;
  }
};

题解2

那要是不想用map做哈希表呢？其实也很简单，就用if和else解决。

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
class Solution {
 public:
  bool isValid(string s) {
    if (s.empty()) {
      return true;
    }
    if (s.size() % 2 == 1) {
      return false;
    }
    stack<char> stk;
    for (auto ch : s) {
      if (ch == '(') {
        stk.push(')');
      } else if (ch == '[') {
        stk.push(']');
      } else if (ch == '{') {
        stk.push('}');
      } else if (stk.empty()) {
        return false;
      } else {
        if (stk.empty() || stk.top() != ch) {
          return false;
        }
        stk.pop();
      }
    }
    if (stk.empty()) {
      return true;
    }
    return false;
  }
};

15、最长回文子串(中)

题解1

因为回文串是对称的，这道题推荐用中心扩散法。
顾名思义，从每一个位置出发，向两边扩散，遇到不是回文的时候结束。
所以可以对每个字符进行扩散，以字符为中心点，left为中心点-1，right为中心点+1，有三种情况：
1、left没有超出左边界同时与中心点相等，继续向左扩展
2、right没有超出右边界同时与中心点相等，继续向右扩展
3、left和right都没超出边界，且left的字符等于right的字符，两边同时扩散
另外，题目要输出的是子串，所以要记录left的位置和最大长度

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
class Solution {
 public:
  string longestPalindrome(string s) {
    int sLen = s.size();
    if (sLen == 0) {
      return "";
    }
    int left = 0, right = 0, maxLen = 0, start = 0;
    for (int i = 0; i < sLen; i++) {
      int len = 1;
      left = i - 1;   // 取中心点左边
      right = i + 1;  // 取中心点右边
      while (left >= 0 && s[left] == s[i]) {
        // 没有超过左边界同时与中心点相等,继续向左扩展
        left--;
        len++;
      }
      while (right < sLen && s[right] == s[i]) {
        // 没有超过右边界同时与中心点相等,继续向右扩展
        right++;
        len++;
      }
      while (left >= 0 && right < sLen && s[left] == s[right]) {
        // 没有超过边界同时左右点都与中心点相等,两边都扩展
        // 这里要注意, 在最后一次循环中left还是做了
        // -1操作,实际上子串不包含这个位置, 所以下面start=left+1
        left--;
        right++;
        len += 2;
      }
      if (len > maxLen) {
        maxLen = len;
        start = left + 1;
      }
    }
    return s.substr(start, maxLen);
  }
};

题解2

当然这道题也可以用动态规划来做，只不过复杂度会高一点。
1、状态定义：
dp[left][right]表示区间范围[left,right]的子串是否是回文子串
2、状态转移方程：
在确定转移方程时，就要分析如下几种情况。
整体上是两种，就是s[left]与s[right]相等和不相等两种情况。
当s[left]与s[right]不相等，那没啥好说的了，dp[left][right]一定是false。
当s[left]与s[right]相等时，这就复杂一些了，有如下三种情况:

  • 下标left与right相同，是同一个字符例如a，当然是回文子串
  • 下标left与right相差在2以内，例如aa或aba，也是回文子串
  • 下标left与right相差大于1的时候，例如cabac，此时s[left]与s[right]已经相同了，我们看left到right区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是left+1与right-1区间，这个区间是不是回文就看dp[left + 1][right - 1]是否为true。

那么状态转移方程就是

1
2
3
if ((s[left] == s[right]) && (right - left <= 2 || dp[left + 1][right - 1])) {
  dp[left][right] = 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
class Solution {
 public:
  string longestPalindrome(string s) {
    int sLen = s.size();
    if (sLen < 2) {
      return s;
    }
    int maxLen = 1, start = 0;
    int dp[sLen][sLen];
    memset(dp, 0, sizeof(dp));
    for (int right = 1; right < sLen; right++) {
      for (int left = 0; left < right; left++) {
        if ((s[left] == s[right]) &&
            (right - left <= 2 || dp[left + 1][right - 1])) {
          dp[left][right] = true;
          if (right - left + 1 > maxLen) {
            maxLen = right - left + 1;
            start = left;
          }
        }
      }
    }
    return s.substr(start, maxLen);
  }
};

16、合并两个有序数组(简)

题解1

首先我们可以用双指针+额外存储空间来实现O(m + 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
class Solution {
 public:
  void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int p1 = m - 1, p2 = n - 1; // 双指针
    int sorted[m + n];  // 额外存储空间
    int cur;
    while (p1 >= 0 || p2 >= 0) {
      if (p1 == -1) {
        // p1遍历到头时,记录nums2[p2]的值
        cur = nums2[p2];
        p2--;
      } else if (p2 == -1) {
        // p2遍历到头时,记录nums1[p1]的值
        cur = nums1[p1];
        p1--;
      } else if (nums1[p1] > nums2[p2]) {
        // nums1[p1]>nums2[p2]时,记录nums1[p1]的值
        cur = nums1[p1];
        p1--;
      } else {
        // nums1[p1]<=nums2[p2]时,记录nums2[p2]的值
        cur = nums2[p2];
        p2--;
      }
      // 向后更新sorted
      sorted[p1 + p2 + 2] = cur;  // 从最后一个开始,m+n=p1+p2+2
    }
    for (int i = 0; i < m + n; ++i) {
      nums1[i] = sorted[i];
    }
  }
};

题解2

首先题目里告诉了我们nums1.length>=m+n，所以我们可以直接原地修改，把nums2放入nums1中，将空间复杂度降低到O(1)。
建立三个指针，两个指针用于指向nums1和nums2的初始化元素数量的末位，也就是分别指向m-1和n-1的位置（设为p1，p2），还有一个指针，我们指向nums1数组m+n-1的位置即可（设为tail）。
其余的跟上面一样

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
class Solution {
 public:
  void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int p1 = m - 1, p2 = n - 1;
    int tail = m + n - 1;
    int cur = 0;
    while (p1 >= 0 || p2 >= 0) {
      if (p1 == -1) {
        // p1遍历到头时,记录nums2[p2]的值
        cur = nums2[p2];
        p2--;
      } else if (p2 == -1) {
        // p2遍历到头时,记录nums1[p1]的值
        cur = nums1[p1];
        p1--;
      } else if (nums1[p1] > nums2[p2]) {
        // nums1[p1]>nums2[p2]时,记录nums1[p1]的值
        cur = nums1[p1];
        p1--;
      } else {
        // nums1[p1]<=nums2[p2]时,记录nums2[p2]的值
        cur = nums2[p2];
        p2--;
      }
      // 向后更新nums1
      nums1[tail] = cur;
      tail--;
    }
  }
};

17、二叉树的最近公共祖先(中)

题解

这跟后序遍历类似，用递归是最好理解的
1、如果当前结点root等于NULL，则直接返回NULL
2、如果root等于p或q，直接返回p或q
3、递归左右子树找左右结点的最近祖先，因为是递归，所以可以认为，使用函数后左右子树已经算出结果了（理解这句话很重要，递归的精髓），用left_parents和right_parents表示
4、若left_parents为空，说明p和q在右子树，只要看right_parents即可；反之亦然
5、若left_parents和right_parents都为空，说明p和q一边一个，所以root是最近的公共祖先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root == NULL)
      return NULL;
    if (root == p || root == q)
      return root;

    // 求左子树最近祖先
    TreeNode* left_parents = lowestCommonAncestor(root->left, p, q);
    // 求右子树最近祖先
    TreeNode* right_parents = lowestCommonAncestor(root->right, p, q);

    if (left_parents == NULL)
      return right_parents;
    if (right_parents == NULL)
      return left_parents;
    if (left_parents && right_parents)  // p和q在两侧
      return root;

    return NULL;  // 必须有返回值
  }
};

18、二叉树的锯齿形层序遍历(中)

题解

有了5-4的二叉树层次遍历，直接对于偶数行进行反转即可

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<vector<int>> zigzagLevelOrder(TreeNode* root) {
    vector<vector<int>> res;
    queue<TreeNode*> q;
    if (root != NULL) {
      q.push(root);
    }
    bool flag = true;
    while (!q.empty()) {
      int n = q.size();
      vector<int> temp;
      for (int i = 0; i < n; i++) {
        TreeNode* node = q.front();
        q.pop();
        temp.push_back(node->val);
        if (node->left != NULL) {
          q.push(node->left);
        }
        if (node->right != NULL) {
          q.push(node->right);
        }
      }
      if (!flag) {
        reverse(temp.begin(), temp.end());
        flag = true;
      } else {
        flag = false;
      }
      res.push_back(temp);
    }
    return res;
  }
};

19、全排列(中)

题解

回溯法实际上是一个类似穷举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”（即回退），尝试别的路径。
回溯法有“通用解题法”之称，它适合于解一些组合数较大的最优化问题。
那回溯法和DFS有啥区别呢？
回溯法以DFS的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。
所以可以理解为，回溯算法 = 树的深度优先搜索 + 剪枝函数
那这道题用回溯法怎么解呢。
这里维护两个数组，分别记录当前排列和每个数字的使用情况，之后枚举每个位置可能出现的数字。
看下面这张图，应该就好理解了
image

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
class Solution {
  vector<vector<int>> ans;
  vector<int> combine;  // 当前组合
  vector<bool> used;    // 数字是否使用

 public:
  vector<vector<int>> permute(vector<int>& nums) {
    used = vector<bool>(nums.size());
    dfs(nums, 0);
    return ans;
  }

  void dfs(vector<int>& nums, int idx) {
    // idx为当前枚举的位置
    if (idx == nums.size()) {
      // 遍历完数组中最后一个数字,把当前组合加入结果
      ans.push_back(combine);
      return;
    }
    for (int i = 0; i < nums.size(); i++) {
      if (!used[i]) {
        // 当前数字没有使用,加入组合
        combine.push_back(nums[i]);
        // 更新使用状态
        used[i] = true;
        // 继续搜索下一个位置
        dfs(nums, idx + 1);
        // 回退使用状态
        used[i] = false;
        // 把数字从当前组合中删除
        combine.pop_back();
      }
    }
  }
};

19-2、全排列 II(中)

题解

这道题和19-1区别就在于数字是与重复的，那我们就需要在做回溯前先把已经枚举过的数字去重。
有两种情况，1、数字已使用过；2、前后数字重复且前面数字已经使用过（这个我们就需要先对数组排序，让相同的数字都在一块）。
其余的照搬19-1的回溯就ok了。

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 Solution {
  vector<vector<int>> ans;
  vector<int> combine;  // 当前组合
  vector<bool> used;    // 数字是否使用

 public:
  vector<vector<int>> permuteUnique(vector<int>& nums) {
    sort(nums.begin(), nums.end());  // 先排个序,让重复的数字都在一块
    used = vector<bool>(nums.size());
    dfs(nums, 0);
    return ans;
  }

  void dfs(vector<int>& nums, int idx) {
    // idx为当前枚举的位置
    if (idx == nums.size()) {
      // 遍历完数组中最后一个数字,把当前组合加入结果
      ans.push_back(combine);
      return;
    }
    unordered_set<int> s;
    for (int i = 0; i < nums.size(); i++) {
      if (used[i] || (i > 0 && nums[i] == nums[i - 1] && used[i - 1])) {
        // 1、数字已使用过; 2、前后数字重复且前面数字已经使用过
        continue;
      }
      // 当前数字没有使用,加入组合
      combine.push_back(nums[i]);
      // 更新使用状态
      used[i] = true;
      // 继续搜索下一个位置
      dfs(nums, idx + 1);
      // 回退使用状态
      used[i] = false;
      // 把数字从当前组合中删除
      combine.pop_back();
    }
  }
};

20、相交链表(简)

题解

直接看图更好理解，
1、指针 pA 指向 A 链表，指针 pB 指向 B 链表，依次往后遍历；
2、如果 pA 到了末尾，则 pA = headB 继续遍历；
3、如果 pB 到了末尾，则 pB = headA 继续遍历；
4、比较长的链表指针指向较短链表head时，长度差就消除了；
5、如此，只需要将最短链表遍历两次，当 pA = pB 时，即找到位置。\

image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
 public:
  ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
    if (headA == NULL || headB == NULL) {
      return NULL;
    }
    ListNode *pA = headA, pB = headB;
    while (pA != pB) {
      pA = (pA == NULL) ? headB : pA->next;
      pB = (pB == NULL) ? headA : pB->next;
    }
    return pA;
  }
};

21、螺旋矩阵(中)

题解

1、首先设定上下左右边界（上为0，下为行数，左为0，右为列数）；
2、其次向右移动到最右，此时第一行因为已经使用过了，可以将其从图中删去，体现在代码中就是重新定义上边界；
3、判断若重新定义后，上下边界交错，表明螺旋矩阵遍历结束，跳出循环，返回答案；
4、若上下边界不交错，则遍历还未结束，接着向下向左向上移动，操作过程与第一，二步同理；
5、不断循环以上步骤，直到某两条边界交错，跳出循环，返回答案。

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
class Solution {
 public:
  vector<int> spiralOrder(vector<vector<int>>& matrix) {
    vector<int> ans;
    if (matrix.empty())
      return ans;   // 若数组为空,直接返回答案
    int upper = 0;  // 赋值上下左右边界
    int down = matrix.size() - 1;
    int left = 0;
    int right = matrix[0].size() - 1;
    while (true) {
      for (int i = left; i <= right; ++i)
        ans.push_back(matrix[upper][i]);  // 向右移动直到最右
      if (++upper > down)
        break;  // 先++,重新设定上边界;若上边界大于下边界,则遍历遍历完成,下同
      for (int i = upper; i <= down; ++i)
        ans.push_back(matrix[i][right]);  // 向下
      if (--right < left)
        break;  // 重新设定有边界
      for (int i = right; i >= left; --i)
        ans.push_back(matrix[down][i]);  // 向左
      if (--down < upper)
        break;  // 重新设定下边界
      for (int i = down; i >= upper; --i)
        ans.push_back(matrix[i][left]);  // 向上
      if (++left > right)
        break;  // 重新设定左边界
    }
    return ans;
  }
};

22、字符串相加(简)

题解

可以使用双指针来模拟人工计算，步骤如下：
1、创建指针i指向num1末位数字，j指向num2末位数字。
2、i, j数字相加，进位就用add来记录进位值，无则为0。
3、若产生进位，则当前数字为(i+j)%10的值。
4、若遍历过程中，num1或num2当前已无数字，则用0补位来计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
 public:
  string addStrings(string num1, string num2) {
    int i = num1.length() - 1, j = num2.length() - 1, add = 0;
    string nums = "";
    while (i >= 0 || j >= 0 || add != 0) {
      int x = i < 0 ? 0 : num1[i] - '0';
      int y = j < 0 ? 0 : num2[j] - '0';
      int res = x + y + add;
      nums.push_back(res % 10);
      add = res / 10;
      i--;
      j--;
    }
    return nums;
  }
};

23、最长递增子序列(中)

题解

动态规划四步走。
1、$dp[i]$的定义
$dp[i]$表示$nums$以$nums[i]$结尾的最长子序列长度
2、状态转移方程
设$j∈[0,i)$，考虑每轮计算新$dp[i]$时，遍历$[0,i)$列表区间，做以下判断：

  • 当$nums[i] > nums[j]$时：$nums[i]$可以接在$nums[j]$之后（此题要求严格递增），此情况下最长上升子序列长度为$dp[j] + 1$；
    • 这种情况下计算出的$dp[j] + 1$的最大值，为直到$i$的最长上升子序列长度（即$dp[i]$）。实现方式为遍历$j$时，每轮执行$dp[i] = max(dp[i], dp[j] + 1)$
  • 当$nums[i] <= nums[j]$时：$nums[i]$无法接在$nums[j]$之后，此情况上升子序列不成立，跳过。

3、$dp[i]$的初始化
$dp[i]$所有元素置1，含义是每个元素都至少可以单独成为子序列，此时长度都为1
4、$dp[i]$的返回值
返回$dp$列表最大值，即可得到全局最长上升子序列长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    int dp[n];
    dp[0] = 1;
    int maxLen = 1;
    for (int i = 1; i < n; i++) {
      dp[i] = 1;
      for (int j = 0; j < i; j++) {
        if (nums[j] < nums[i]) {
          dp[i] = max(dp[i], dp[j] + 1);
        }
      }
      maxLen = max(dp[i], maxLen);
    }

    return maxLen;
  }
};
刷题笔记
2022806970.html
作者
felicx
发布于
2023-08-07 15:20
许可
 评论
评论插件加载失败
正在加载评论插件
  1. LeetCode Hot 100
    1. 1-1、反转链表(简)
      1. 题解1
      2. 题解2
    2. 1-2、反转链表Ⅱ(中)
      1. 题解
    3. 1-3、K个一组翻转链表(困)
      1. 题解
    4. 2、无重复字符的最长子串(中)
      1. 题解
    5. 3、LRU缓存机制(中)
      1. 题解
    6. 4、数组中的第K个最大元素(困)
      1. 题解1
      2. 题解2
      3. 题解3
    7. 5-1、二叉树的中序遍历(简)
      1. 题解
    8. 5-2、二叉树的前序遍历(简)
      1. 题解
    9. 5-3、二叉树的后序遍历(简)
      1. 题解1
      2. 题解2
    10. 5-4、二叉树的层序遍历(中)
      1. 题解
    11. 6-1、两数之和(简)
      1. 题解
    12. 6-2、三数之和(中)
      1. 题解
    13. 6-3、最接近的三数之和(中)
      1. 题解
    14. 7、手撕快速排序(中)
      1. 题解
    15. 8、最大子数组和(中)
      1. 题解
    16. 9、合并两个有序链表(简)
      1. 题解
    17. 10-1、搜索旋转排序数组(中)
      1. 题解
    18. 10-2、搜索旋转排序数组 II(中)
      1. 题解
    19. 10-3、寻找旋转排序数组中的最小值(中)
      1. 题解
    20. 10-4、寻找旋转排序数组中的最小值 II(困)
      1. 题解
    21. 11-1、买卖股票的最佳时机(简)
      1. 题解1
      2. 题解2
    22. 11-2、买卖股票的最佳时机 II(中)
      1. 题解
    23. 11-3、买卖股票的最佳时机 III(困)
      1. 题解
    24. 12-1、环形链表(简)
      1. 题解
    25. 12-2、环形链表 II(中)
      1. 题解
    26. 13-1、岛屿数量(中)
      1. 题解
    27. 13-2、岛屿的周长(简)
      1. 题解
    28. 13-3、岛屿的最大面积(中)
      1. 题解
    29. 13-4、最大人工岛(困)
      1. 题解
    30. 14、有效的括号(简)
      1. 题解1
      2. 题解2
    31. 15、最长回文子串(中)
      1. 题解1
      2. 题解2
    32. 16、合并两个有序数组(简)
      1. 题解1
      2. 题解2
    33. 17、二叉树的最近公共祖先(中)
      1. 题解
    34. 18、二叉树的锯齿形层序遍历(中)
      1. 题解
    35. 19、全排列(中)
      1. 题解
    36. 19-2、全排列 II(中)
      1. 题解
    37. 20、相交链表(简)
      1. 题解
    38. 21、螺旋矩阵(中)
      1. 题解
    39. 22、字符串相加(简)
      1. 题解
    40. 23、最长递增子序列(中)
      1. 题解
© 2018 - 2024    felicx
由 Hexo 驱动 & 主题 Keep
访客数 访问量
  1. LeetCode Hot 100
    1. 1-1、反转链表(简)
      1. 题解1
      2. 题解2
    2. 1-2、反转链表Ⅱ(中)
      1. 题解
    3. 1-3、K个一组翻转链表(困)
      1. 题解
    4. 2、无重复字符的最长子串(中)
      1. 题解
    5. 3、LRU缓存机制(中)
      1. 题解
    6. 4、数组中的第K个最大元素(困)
      1. 题解1
      2. 题解2
      3. 题解3
    7. 5-1、二叉树的中序遍历(简)
      1. 题解
    8. 5-2、二叉树的前序遍历(简)
      1. 题解
    9. 5-3、二叉树的后序遍历(简)
      1. 题解1
      2. 题解2
    10. 5-4、二叉树的层序遍历(中)
      1. 题解
    11. 6-1、两数之和(简)
      1. 题解
    12. 6-2、三数之和(中)
      1. 题解
    13. 6-3、最接近的三数之和(中)
      1. 题解
    14. 7、手撕快速排序(中)
      1. 题解
    15. 8、最大子数组和(中)
      1. 题解
    16. 9、合并两个有序链表(简)
      1. 题解
    17. 10-1、搜索旋转排序数组(中)
      1. 题解
    18. 10-2、搜索旋转排序数组 II(中)
      1. 题解
    19. 10-3、寻找旋转排序数组中的最小值(中)
      1. 题解
    20. 10-4、寻找旋转排序数组中的最小值 II(困)
      1. 题解
    21. 11-1、买卖股票的最佳时机(简)
      1. 题解1
      2. 题解2
    22. 11-2、买卖股票的最佳时机 II(中)
      1. 题解
    23. 11-3、买卖股票的最佳时机 III(困)
      1. 题解
    24. 12-1、环形链表(简)
      1. 题解
    25. 12-2、环形链表 II(中)
      1. 题解
    26. 13-1、岛屿数量(中)
      1. 题解
    27. 13-2、岛屿的周长(简)
      1. 题解
    28. 13-3、岛屿的最大面积(中)
      1. 题解
    29. 13-4、最大人工岛(困)
      1. 题解
    30. 14、有效的括号(简)
      1. 题解1
      2. 题解2
    31. 15、最长回文子串(中)
      1. 题解1
      2. 题解2
    32. 16、合并两个有序数组(简)
      1. 题解1
      2. 题解2
    33. 17、二叉树的最近公共祖先(中)
      1. 题解
    34. 18、二叉树的锯齿形层序遍历(中)
      1. 题解
    35. 19、全排列(中)
      1. 题解
    36. 19-2、全排列 II(中)
      1. 题解
    37. 20、相交链表(简)
      1. 题解
    38. 21、螺旋矩阵(中)
      1. 题解
    39. 22、字符串相加(简)
      1. 题解
    40. 23、最长递增子序列(中)
      1. 题解