Sekyoro的博客小屋

leetcode刷题记录

发表于 更新于
本文字数： 16k 阅读时长 ≈ 15 分钟

唉,很久没做做题了.这里记录一下每天刷题练习.

主要刷一些简单中等题,难了我也不会.

剑指Offer 启动

image-20221226173618143

09.用两个栈实现队列

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
package 用两个栈实现队列;

import java.util.ArrayDeque;
import java.util.Deque;

public class CQueue2 {

  Deque<Integer> inStack;
  Deque<Integer> outStack;

  public CQueue2() {
    inStack = new ArrayDeque<>();
    outStack = new ArrayDeque<>();

  }

  public void appendTail(int value) {
    inStack.push(value);
  }

  public int deleteHead() {
    if(outStack.isEmpty())
    {
      if(inStack.isEmpty())
      {
        return -1;
      }
      else
      {
        while(!inStack.isEmpty())
        {
          outStack.push(inStack.pop());
        }
        return outStack.pop();
      }
    }
    return outStack.pop();
  }
}

设计一个有getMin功能的栈

1
实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。

【要求】

1.pop、push、getMin 操作的时间复杂度都是 O(1)。 2.设计的栈类型可以使用现成的栈结构

设计方案

使用辅助栈,多一个存最小值的栈stackmin. 即有stackdata和stackmin

第一种

压入规则

压入数据时,stackdata直接压入;stackmin如果为空,直接压入,如果不为空,进行比较:将要压入的值和栈顶的值进行比较,如果栈顶值更小则不处理,否则压入.

弹出规则

stackdata弹出数据,将弹出的数据与stackmin顶数据比较,如果弹出数据等于stackmin栈顶数据,则同时弹出stackmin数据,否则不处理.

最小值即位stackmin中栈顶值

第二种

压入规则

压入数据时,stackdata直接压入;stackmin如果为空也直接压入,否则将栈顶数据与待压入数据比较,如果栈顶数据更小,则stackmin再压入一次栈顶数据,否则stackmin压入待压入数据.

弹出规则

两个栈都弹出

最小值也是stackmin的栈顶

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 MinStack {
public:
    stack<int>s,min_s;

    MinStack() {

    }
    
    void push(int val) {
        if(s.empty())
        {
            s.emplace(val);
            min_s.emplace(val);
        }
        else
        {
            int topvalue = min_s.top();
            if(topvalue>val)
            {
                min_s.emplace(val);
            }
            else{
                min_s.emplace(topvalue);
            }
            s.emplace(val);
        }
    }
    
    void pop() {
        s.pop();
        min_s.pop();
    }
    
    int top() {
        return s.top();

    }
    
    int min() {
        return min_s.top();
    }
};

从尾到头打印链表

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）

设计方案

利用栈结构或者使用递归

这里使用递归

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
      
        if(!head)
        {
            return {};
        }
        vector<int> v =reversePrint(head->next);
        v.push_back(head->val);
        return v;
        }
   }

使用辅助栈结构

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> reversePrint(ListNode* head) {
        stack<int> s;

        for(ptr it=head;it!=nullptr;it=it->next)
        {
            s.push(it->val);
        }

        vector<int> v;
        while(!s.empty())
        {
            int val = s.top();
            s.pop();
            v.push_back(val);
        }
        return v;

        
    }
};

反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:

1
2
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

解决方案

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 singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
  ListNode(int x):val(x),next(NULL){}
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
typedef ListNode* LN;
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head)
        {
            return nullptr;
        }
        LN nd = head->next;
        LN pre = head;
        pre->next = nullptr;
        for(LN it = nd;it!=nullptr;)
        {
            nd = it->next;
            it->next = pre;
            pre = it;
            it = nd;
            
        }
        return pre;
    }
};

使用递归方法

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;
    }
};

复杂链表的复制

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

解题思路

  1. 回溯和哈希表(或者单独使用哈希表)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution
{
public:
    unordered_map<Node *, Node *> cachedNode;
    Node *copyRandomList(Node *head)
    {
        if (!head)
        {
            return nullptr;
        }
        if (!cachedNode.count(head))
        {
            cachedNode[head] = new Node(head->val);
            cachedNode[head]->next = copyRandomList(head->next);
            cachedNode[head]->random = copyRandomList(head->random);
        }

        return cachedNode[head];
    }
};

  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
    class Solution {
    public:
        Node* copyRandomList(Node* head) {
            if (head == nullptr) {
                return nullptr;
            }
            for (Node* node = head; node != nullptr; node = node->next->next) {
                Node* nodeNew = new Node(node->val);
                nodeNew->next = node->next;
                node->next = nodeNew;
            }
            for (Node* node = head; node != nullptr; node = node->next->next) {
                Node* nodeNew = node->next;
                nodeNew->random = (node->random != nullptr) ? node->random->next : nullptr;
            }
            Node* headNew = head->next;
            for (Node* node = head; node != nullptr; node = node->next) {
                Node* nodeNew = node->next;
                node->next = node->next->next;
                nodeNew->next = (nodeNew->next != nullptr) ? nodeNew->next->next : nullptr;
            }
            return headNew;
        }
    };

Update

Source:

将题型按照算法类型和使用的数据结构进行分类.

贪心算法

顾名思义，贪心算法或贪心思想 区间问题 采用贪心的策略，保证每次操作都是局部 最优的，从而使最后得到的结果是全局最优的

证明一道题能用贪心算法解决，有时远比用贪心算法解决该题更复杂。一般情况下，在简单 操作后，具有明显的从局部到整体的递推关系，或者可以通过数学归纳法推测结果时，我们才会 使用贪心算法。

121 买卖股票最佳时机

我们来假设自己来购买股票。随着时间的推移，每天我们都可以选择出售股票与否。那么，假设在第 i 天，如果我们要在今天卖股票，那么我们能赚多少钱呢？

显然，如果我们真的在买卖股票，我们肯定会想：如果我是在历史最低点买的股票就好了.在题目中，只要用一个变量记录一个历史最低价格 minprice，我们就可以假设自己的股票是在那天买的。那么我们在第 i 天卖出股票能得到的利润就是 prices[i] - minprice。

因此，我们只需要遍历价格数组一遍，记录历史最低点，然后在每一天考虑这么一个问题：如果我是在历史最低点买进的，那么我今天卖出能赚多少钱？当考虑完所有天数之时，我们就得到了最好的答案。

作者：力扣官方题解
链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/solutions/136684/121-mai-mai-gu-piao-de-zui-jia-shi-ji-by-leetcode-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int maxProfit = 0;
if (prices.size() < 2) {
  return maxProfit;
}
int sellDay = 1;
int minPrice = prices[0];
while (sellDay < prices.size()) {
  minPrice = std::min(minPrice, prices[sellDay - 1]);
  int profit = prices[sellDay] - minPrice;
  if (profit > maxProfit) {
    maxProfit = profit;
  }
  ++sellDay;
}
return maxProfit;

122 买卖股票的最佳时机 II

代码随想录

1
2
3
4
5
6
7
8
int maxProfit = 0;
   if (prices.size() < 2) {
     return maxProfit;
   }
   for (int i = 1; i < prices.size(); i++) {
     maxProfit += std::max(prices[i] - prices[i - 1], 0);
   }
   return maxProfit;

只需要计算有利益的区间和即可.

455分发饼干

因为饥饿度最小的孩子最容易吃饱，所以我们先考虑这个孩子。为了尽量使得剩下的饼干可 以满足饥饿度更大的孩子，所以我们应该把大于等于这个孩子饥饿度的、且大小最小的饼干给这个孩子。满足了这个孩子之后，我们采取同样的策略，考虑剩下孩子里饥饿度最小的孩子，直到 没有满足条件的饼干存在。 简而言之，这里的贪心策略是，给剩余孩子里最小饥饿度的孩子分配最小的能饱腹的饼干

1
2
3
4
5
6
7
8
9
10
11
12
13
int findContentChildren(vector<int> &children, vector<int> &cookies) {
 sort(children.begin(), children.end());
 sort(cookies.begin(), cookies.end());
 int child_i = 0, cookie_i = 0;
 int n_children = children.size(), n_cookies = cookies.size();
 while (child_i < n_children && cookie_i < n_cookies) {
 if (children[child_i] <= cookies[cookie_i]) {
 ++child_i;
 }
 ++cookie_i;
 }
 return child_i;
 }

135分发糖果

存在比较关系的贪心策略并不一定需要排序。虽然这一道题也是运用贪心策略，但我们只需 要简单的两次遍历即可：把所有孩子的糖果数初始化为；先从左往右遍历一遍，如果右边孩子 的评分比左边的高，则右边孩子的糖果数更新为左边孩子的糖果数加；再从右往左遍历一遍， 如果左边孩子的评分比右边的高，且左边孩子当前的糖果数不大于右边孩子的糖果数，则左边孩子的糖果数更新为右边孩子的糖果数加。通过这两次遍历，分配的糖果就可以满足题目要求了。 这里的贪心策略即为，在每次遍历中，只考虑并更新相邻一侧的大小关系

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int candy(std::vector<int> &ratings) {
   std::vector<int> candies(ratings.size(), 1);
   for (int i = 0; i < candies.size() - 1; i++) {
     // 从左到右遍历,如果右边比左边大,右边糖果比左边+1
     if (ratings[i] < ratings[i + 1]) {
       candies[i + 1] = candies[i] + 1;
     }
     // 如果左边与右边的相等,均不增加
   }
   for (int i = candies.size() - 1; i > 0; i--) {
     // 从右到左遍历,如果左边比右边大,并且左边的糖果不大于右边的糖果,左边的糖果=右边的糖果+1
     if (ratings[i] < ratings[i - 1] && candies[i] >= candies[i - 1]) {
       candies[i - 1] = candies[i] + 1;
     }
   }
   return std::accumulate(candies.begin(), candies.end(), 0);
 }

435无重叠区间

求最少的移除区间个数，等价于尽量多保留不重叠的区间。在选择要保留区间时，区间的结尾十分重要：选择的区间结尾越小，余留给其它区间的空间就越大，就越能保留更多的区间。因此，我们采取的贪心策略为，优先保留结尾小且不相交的区间。

具体实现方法为，先把区间按照结尾的大小进行增序排序（利用 lambda 函数），每次选择结尾最小且和前一个选择的区间不重叠的区间。

在样例中，排序后的数组为 [[1,2], [1,3], [2,4]]。按照我们的贪心策略，首先初始化为区间[1,2]；由于 [1,3] 与 [1,2] 相交，我们跳过该区间；由于 [2,4] 与 [1,2] 不相交，我们将其保留。因此最终保留的区间为 [[1,2], [2,4]]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
if (intervals.size() <= 1) {
  return 0;
}
// 排序,根据start
std::sort(intervals.begin(), intervals.end(),
          [](const std::vector<int> &a, const std::vector<int> &b) {
            return a[1] < b[1];
          });
int count = 0;
// 当根据开始时间排序后,下一个的开始时间必须大于等于当前结束时间
int prevEnd = intervals[0][1];
for (int i = 0; i < intervals.size() - 1; i++) {
  if (prevEnd > intervals[i + 1][0]) {
    count++;
  }else{
    prevEnd = intervals[i + 1][1];
  }
}
return count;

双指针

双指针主要用于遍历数组，两个指针指向不同的元素，从而协同完成任务。也可以延伸到多 个数组的多个指针。 若两个指针指向同一数组，遍历方向相同且不会相交，则也称为滑动窗口（两个指针包围的 区域即为当前的窗口），经常用于区间搜索。

若两个指针指向同一数组，但是遍历方向相反，则可以用来进行搜索，待搜索的数组往往是 排好序的。

167 两数之和

因为数组已经排好序，我们可以采用方向相反的双指针来寻找这两个数字，一个初始指向最 小的元素，即数组最左边，向右遍历；一个初始指向最大的元素，即数组最右边，向左遍历。 如果两个指针指向元素的和等于给定值，那么它们就是我们要的结果。如果两个指针指向元 素的和小于给定值，我们把左边的指针右移一位，使得当前的和增加一点。如果两个指针指向元 素的和大于给定值，我们把右边的指针左移一位，使得当前的和减少一点。 可以证明，对于排好序且有解的数组，双指针一定能遍历到最优解。证明方法如下：假设最 优解的两个数的位置分别是l和r。我们假设在左指针在l左边的时候，右指针已经移动到了r； 此时两个指针指向值的和小于给定值，因此左指针会一直右移直到到达l。同理，如果我们假设 在右指针在r右边的时候，左指针已经移动到了l；此时两个指针指向值的和大于给定值，因此 右指针会一直左移直到到达r。所以双指针在任何时候都不可能处于l,r之间，又因为不满足条 件时指针必须移动一个，所以最终一定会收敛在l和r。

1
2
3
4
5
6
7
8
9
10
11
12
13
std::vector<int> twoSum(std::vector<int> &numbers, int target) {
  int i = 0, j = numbers.size() - 1;
  while (i < j) {
    if (numbers[i] + numbers[j] < target) {
      i++;
    } else if (numbers[i] + numbers[j] > target) {
      j--;
    } else {
      return {i+1, j+1};
    }
  }
  return {};
}

88 归并有序数组

因为这两个数组已经排好序，我们可以把两个指针分别放在两个数组的末尾，即 nums1 的 m − 1 位和 nums2 的 n − 1 位。每次将较大的那个数字复制到 nums1 的后边，然后向前移动一位。 因为我们也要定位 nums1 的末尾，所以我们还需要第三个指针，以便复制。

在以下的代码里，我们直接利用 m 和 n 当作两个数组的指针，再额外创立一个 pos 指针，起始位置为 m +n − 1。每次向左移动 m 或 n 的时候，也要向左移动 pos。这里需要注意，如果 nums1 的数字已经复制完，不要忘记把 nums2 的数字继续复制；如果 nums2 的数字已经复制完，剩余 nums1 的数字不需要改变，因为它们已经被排好序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void merge(std::vector<int> &nums1, int m, std::vector<int> &nums2, int n) {
    int pos = m + n - 1; // 指向最后一个位置
    // 将最大的元素往后放
    while (m > 0 && n > 0) {
      if (nums1[m - 1] > nums2[n - 1]) {
        nums1[pos] = nums1[m - 1];
        // 指针后移
        m--;
      } else {
        nums1[pos] = nums2[n - 1];
        n--;
      }
      pos--;
    }
    while (n) {
      nums1[pos--] = nums2[n--];
    }
  }

二分查找

二分查找也常被称为二分法或者折半查找 ，每次查找时通过将待查找的单调区间分成两部分并只取一部分继续查找，将查找的复杂度大大减少。对于一个长度为On 的数组，二分查找的时间复杂度为Ologn。

具体到代码上，二分查找时区间的左右端取开区间还是闭区间在绝大多数时候都可以，因此 有些初学者会容易搞不清楚如何定义区间开闭性。这里笔者提供两个小诀窍，第一是尝试熟练使用一种写法，比如左闭右开（满足、等语言的习惯）或左闭右闭（便于处理边界条 件），尽量只保持这一种写法；第二是在刷题时思考如果最后区间只剩下一个数或者两个数，自 己的写法是否会陷入死循环，如果某种写法无法跳出死循环，则考虑尝试另一种写法。

此外在更新left和right时,使用left=mid+1还是left=mid有差别,如果是前者,在下一次更新mid时仍有可能为mid(下一轮循环仍可能考虑 mid 这个位置的值)

旋转数组查找数字

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
/*
 * @lc app=leetcode.cn id=81 lang=cpp
 *
 * [81] 搜索旋转排序数组 II
 */

// @lc code=start
#include <vector>

using namespace std;
class Solution {
public:
  bool search(vector<int> &nums, int target) {
    const auto size = nums.size();
    int l = 0, r = size - 1;
    while (l <= r) {
      int mid = (r - l) / 2 + l;
      if (nums.at(mid) == target) {
        return true;
      }
      if (nums.at(mid) == nums.at(l)) {
        l += 1;
      } else if (nums.at(mid) == nums.at(r)) {
        r--;
      } else if (nums.at(mid) > nums.at(r)) {
        // 如果大于右端,则左半区间为递增(非降) [l,mid]
        // 如果target在递增区间中,进行二分法搜索
        if (target >= nums.at(l) && target <= nums.at(mid)) {
          r = mid - 1;
        } else {
          // 在另一个区间
          l = mid + 1;
        }
      } else {
        // 右半区间递增 [mid,r]
        if (target >= nums.at(mid) && target <= nums.at(r)) {
          l = mid + 1;
        } else {
          // 在另一个区间
          r = mid - 1;
        }
      }
    }
    return false;
  }
};
// @lc code=end

查找峰值

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
/*
 * @lc app=leetcode.cn id=162 lang=cpp
 *
 * [162] 寻找峰值
 */

// @lc code=start
#include <iterator>
#include <limits>
#include <vector>
using namespace std;
class Solution {
public:
  int findPeakElement(vector<int> &nums) {
    auto size = nums.size();
    if (size == 1) {
      return 0;
    }
    // 长度大于1,先判断两边
    if (nums.at(0) > nums.at(1)) {
      return 0;
    }
    if (nums.at(size - 1) > nums.at(size - 2)) {
      return size - 1;
    }
    // 判断两边后判断剩下位置
    int l = 1, r = size - 2;
    while (l <= r) {
      int mid = (r - l) / 2 + l;
      // 判断是否是峰值
      if (nums.at(mid) > nums.at(mid + 1) && nums.at(mid) > nums.at(mid - 1)) {
        return mid;
      }
      // 二分
      if (nums.at(mid) <= nums.at(mid + 1)) {
        // 如果后面值更大,则后面一定存在峰值
        l = mid + 1;
      } else {
        // 同理
        r = mid - 1;
      }
    }
    return -1;
  }
};
// @lc code=end

排序算法

虽然在和里都可以通过sort函数排序，而且刷题时很少需要自己手写排序算 法，但是熟习各种排序算法可以加深自己对算法的基本理解，以及解出由这些排序算法引申出来 的题目。这里我们展示两种复杂度为Onlogn的排序算法：快速排序和归并排序，其中前者实 际速度较快，后者可以保证相同值的元素在数组中的相对位置不变（即“稳定排序”）

快速排序

快速排序的原理并不复杂：对于当前一个未排序片段，我们先随机选择一个位置当作中枢点， 然后通过遍历操作，将所有比中枢点小的数字移动到其左侧，再将所有比中枢点大的数字移动到 其右侧。操作完成后，我们再次对中枢点左右侧的片段再次进行快速排序即可。可证明，如果中 枢点选取是随机的，那么该算法的平均复杂度可以达到Onlogn，最差情况下复杂度则为On2。 我们采用左闭右闭的二分写法，初始化条件为l=0，r=n 1。

归并排序

归并排序是典型的分治法，简单来讲，对于一个未排序片段, 我们可以先分别排序其左半侧和右半侧，然后将两侧重新组合（“治”）；排序每个半侧时可以通 过递归再次把它切分成两侧（“分”）。 我们采用左闭右闭的二分写法，初始化条件为l=0，r =n 1，另外提前建立一个和 大小相同的数组，用来存储临时结果。

排序算法最好时间复杂度最坏时间复杂度平均时间复杂度空间复杂度稳定性
冒泡排序O(n)O(n²)O(n²)O(1)是
插入排序O(n)O(n²)O(n²)O(1)是
选择排序O(n²)O(n²)O(n²)O(1)否
希尔排序O(n)O(n²)O(nlogn)~O(n²)O(1)否
归并排序O(nlogn)O(nlogn)O(nlogn)O(n)是
快速排序O(nlogn)O(n²)O(nlogn)O(logn)否
堆排序O(nlogn)O(nlogn)O(nlogn)O(1)否
计数排序O(n+k)O(n+k)O(n+k)O(k)是
桶排序O(n+k)O(n²)O(n+k)O(n+k)是
基数排序O(n×k)O(n×k)O(n×k)O(n+k)是

说明：

  • 稳定性：稳定的排序算法在排序过程中不会改变相等元素的相对顺序。
  • 空间复杂度：表示算法在运行过程中所需的额外空间。
  • 计数排序、桶排序、基数排序：适用于数据范围有限或特定场景，能达到线性时间复杂度。

快速选择

在一个未排序的数组中，找到第k大的数字。

快速选择一般用于求解k-th Element 问题，可以在平均On时间复杂度，O1空间复杂度完 成求解工作。快速选择的实现和快速排序相似，不过只需要找到第k大的枢即可，不需 要对其左右再进行排序。与快速排序一样，快速选择一般需要先打乱数组，否则最坏情况下时间 复杂度为On2。

桶排序

给定一个数组，求前k个最频繁的数字。

搜索

深度优先搜索和广度优先搜索是两种最常见的优先搜索方法，它们被广泛地运用在图和树等 结构中进行搜索。

​ 深度优先搜索在搜索到一个新的节点时，立即对该新节点进行遍 历；因此遍历需要用先入后出的栈（）来实现，也可以通过与栈等价的递归来实现。对于树 结构而言，由于总是对新节点调用遍历，因此看起来是向着“深”的方向前进。

​ 深度优先搜索也可以用来检测环路：记录每个遍历过的节点的父节点，若一个节点被再次遍 历且父节点不同，则说明有环。我们也可以用之后会讲到的拓扑排序判断是否有环路，若最后存 在入度不为零的点，则说明有环。

最大岛屿面积

给定一个二维的矩阵，其中表示海洋，表示陆地。单独的或相邻的陆地可以形成岛 屿，每个格子只与其上下左右四个格子相邻。求最大的岛屿面积。

城市数量

给定一个二维的矩阵，如果第位置是，则表示第个城市和第个城市处于同一 城市圈。已知城市的相邻关系是可以传递的，即如果a和b相邻，b和c相邻，那么a和c也相 邻，换言之这三个城市处于同一个城市圈之内。求一共有多少个城市圈。

太平洋大西洋水流问题

给定一个二维的非负整数矩阵，每个位置的值表示海拔高度。假设左边和上边是太平洋，右 边和下边是大西洋，求从哪些位置向下流水，可以流到太平洋和大西洋。水只能从海拔高的位置 流到海拔低或相同的位置。

回溯法

回溯法是优先搜索的一种特殊情况，又称为试探法，常用于需要记录节点状 态的深度优先搜索。通常来说，排列、组合、选择类问题使用回溯法比较方便

​ 。 顾名思义，回溯法的核心是回溯。在搜索到某一节点的时候，如果我们发现目前的节点（及 其子节点）并不是需求目标时，我们回退到原来的节点继续搜索，并且把在目前节点修改的状态 还原。这样的好处是我们可以始终只对图的总状态进行修改，而非每次遍历时新建一个图来储存 状态。

​ 在具体的写法上，它与普通的深度优先搜索一样，都有修改当前节点状态递归子节 点的步骤，只是多了回溯的步骤，变成了修改[当前节点状态]->[递归子节点]->[回改当前节点状态]。

可以记住两个小诀窍，一是按引用传状态，二是所有的状态修 改在递归完成后回改。 回溯法修改一般有两种情况，一种是修改最后一位输出，比如排列组合；一种是修改访问标 记，比如矩阵里搜字符串。

全排列

给定一个无重复数字的整数数组，求其所有的排列方式。

组合

给定一个整数n和一个整数k，求在到n中选取k个数字的所有组合方法。

单词搜索

给定一个字母矩阵，所有的字母都与上下左右四个方向上的字母相连。给定一个字符串，求 字符串能不能在字母矩阵中寻找到。

K皇后

给定一个大小为n的正方形国际象棋棋盘，求有多少种方式可以放置n个皇后并使得她们互 不攻击，即每一行、列、左斜、右斜最多只有一个皇后。

广度优先搜索

广度优先搜索（ 此需要用先入先出的队列 ，）不同与深度优先搜索，它是一层层进行遍历的，因 而非先入后出的栈 进行遍历。由于是按层次进行遍历， 广度优先搜索时按照“广”的方向进行遍历的，也常常用来处理最短路径等问题。

这里要注意，深度优先搜索和广度优先搜索都可以处理可达性问题，即从一个节点开始是否 能达到另一个节点。因为深度优先搜索可以利用递归快速实现，很多人会习惯使用深度优先搜索 刷此类题目。实际软件工程中，笔者很少见到递归的写法，因为一方面难以理解，另一方面可能 产生栈溢出的情况；而用栈实现的深度优先搜索和用队列实现的广度优先搜索在写法上并没有太 大差异，因此使用哪一种搜索方式需要根据实际的功能需求来判断。另外，如果需要自定义搜索 优先级，我们可以利用优先队列，这个我们会在数据结构的章节讲到。—leetcode101

动态规划

​ 动态规划在查找有很多 重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问 题，它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。因此，动态规划 保存递归时的结果，因而不会在解决同样的问题时花费时间 动态规划只能应用于有最优 子结构的问题。最优子结构的意思是局部最优解能决定全局最优解（对有些问题这个要求并不能 完全满足，故有时需要引入一定的近似）。简单地说，问题能够分解成子问题来解决

​ 动态规划和其它遍历算法（如深广度优先搜索）都是将原问题拆成多个子问 题然后求解，他们之间最本质的区别是，动态规划保存子问题的解，避免重复计算。解决动态规 划问题的关键是找到状态转移方程，这样我们可以通过计算和储存子问题的解来求解最终问题。

​ 同时，也可以对动态规划进行空间压缩，起到节省空间消耗的效果。

​ 在一些情况下，动态规划可以看成是带有状态记录（ ）的优先搜索。状态记录的 意思为，如果一个子问题在优先搜索时已经计算过一次，我们可以把它的结果储存下来，之后遍 历到该子问题的时候可以直接返回储存的结果。

​ 动态规划是自下而上的，即先解决子问题，再解 决父问题；而用带有状态记录的优先搜索是自上而下的，即从父问题搜索到子问题，若重复搜索 到同一个子问题则进行状态记录，防止重复计算。如果题目需求的是最终状态，那么使用动态搜 索比较方便；如果题目需要输出所有的路径，那么使用带有状态记录的优先搜索会比较方便

一维

给定n节台阶，每次可以走一步或走两步，求一共有多少种方式可以走完这些台阶。

假如你是一个劫匪，并且决定抢劫一条街上的房子，每个房子内的钱财数量各不相同。如果 你抢了两栋相邻的房子，则会触发警报机关。求在不触发机关的情况下最多可以抢劫多少钱。

给定一个数组，求这个数组中连续且等差的子数组一共有多少个

二维

给定一个m n大小的非负整数矩阵，求从左上角开始到右下角结束的、经过的数字的和最 小的路径。每次只能向右或者向下移动。

给定一个由和组成的二维矩阵，求每个位置到最近的的距离。

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积

分割类型

给定一个正整数，求其最少可以由几个完全平方数相加构成

已知字母可以表示成数字。给定一个数字串，求有多少种不同的字符串等价于这个 数字串

给定一个字符串和一个字符串集合，求是否存在一种分割方式，使得原字符串分割后的子字 符串都可以在集合内找到。

给定一个数组，每个元素代表一本书的厚度和高度。问对于一个固定宽度的书架，如果按照 数组中书的顺序从左到右、从上到下摆放，最小总高度是多少。

给定一个不重复数字的数组和一个目标数，求加起来是目标数的所有排列的总数量

子序列问题

​ 对于子序列问题，第一种动态规划方法是，定义一个数组,其中dp[i]表示以i结尾的子 序列的性质。在处理好每个位置后，统计一遍各个位置的结果即可得到题目要求的结果。

​ 对于子序列问题，第二种动态规划方法是，定义一个数组，其中表示dp[i]到位置i为止的子序列的性质，并不必须以结尾。这样数组的最后一位结果即为题目所求，不需要再对每 个位置进行统计。

背包问题

背包问题是一种组合优化的完全问题：有n个物品和载重为w的背包和价值，求拿哪些物品可以使得背包所装下物品的总价值最大。如果限定每种物品只能选择0个或1个，则问题称为背包问题（ 如果不限定每种物品的数量，则问题称为无界背包问题或完全背包问题)

给定一个正整数数组，求是否可以把这个数组分成和相等的两部分

给定一些硬币的面额，求最少可以用多少颗硬币组成给定的金额。

给定m个数字和n个数字，以及一些由构成的字符串，求利用这些数字最多可以构 成多少个给定的字符串，字符串只可以构成一次。

字符串编辑

给定两个字符串，已知你可以删除、替换和插入任意字符串的任意字符，求最少编辑几步可 以将两个字符串变成相同。

给定一个字母，已知你可以每次选择复制全部字符，或者粘贴之前复制的字符，求最少需 要几次操作可以把字符串延展到指定长度。

股票交易

股票交易类问题通常可以用动态规划来解决。对于稍微复杂一些的股票交易类问题，比如需要冷却时间或者交易费用，则可以用通过动态规划实现的状态机来解决。

给定一段时间内每天某只股票的固定价格，已知你只可以买卖各k次，且每次只能拥有一支 股票，求最大的收益。

给定一段时间内每天某只股票的固定价格，已知每次卖出之后必须冷却一天，且每次只能拥 有一支股票，求最大的收益。

image-20250522171311869

树

作为（单）链表的升级版，我们通常接触的树都是二叉树, 两个子节点；且除非题目说明，默认树中不存在循环结构。

有用的资料

  1. 代码随想录

  2. changgyhub/leetcode_101: LeetCode 101：力扣刷题指南

  3. 剑指offer（专项突破） - 力扣（LeetCode）全球极客挚爱的技术成长平台

  4. CodeTop 面试题目总结

  5. LeetCode 101: 力扣刷题指南 (第二版) | LeetCode 101 - A Grinding Guide

  6. leetcode_101/LeetCode 101 - A Grinding Guide.pdf at master · changgyhub/leetcode_101

  7. 本站简介 | labuladong 的算法笔记

-------------本文结束感谢您的阅读-------------
感谢阅读.

欢迎关注我的其它发布渠道