Fork me on GitHub

力扣题解合集（日期版）

字数统计: 3.7k字   |   阅读时长≈ 18分

力扣题解合集（按日期汇总）

说明：本文整合 source/_posts 目录下带日期的力扣题解，按时间顺序汇总，保留原文内容与代码。

2023-3-20 · 3 无重复字符的最长子串

无重复字符的最长子串

给定一个字符串 s ，找出其中不含有重复字符的最长子串的长度。

示例 1:

1
2
3
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

1
2
3
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

1
2
3
输入: s = "pwwkew"
输出: 3
解释: 无重复字符的最长子串是 "wke"，长度为 3。注意答案必须是子串长度，"pwke" 是子序列。

思路: 利用滑动窗口，两个指针 right 和 left 作为窗口左右边界。右边逐渐扩大，利用 map 统计字符次数，若次数大于 1 说明重复，再收缩左边直到窗口无重复，窗口大小即答案。

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 lengthOfLongestSubstring(string s) {
        unordered_map<char, int> window;
        int left = 0, right = 0;
        int res = 0;
        while (right < s.size()) {
            char c = s[right];
            right++;
            window[c]++;

            while (window[c] > 1) {
                char d = s[left];
                left++;
                window[d]--;
            }

            res = max(res, right - left);
        }
        return res;
    }
};

为什么要用 unordered_map:

  • unordered_map 查询单个 key 时效率比 map 高，查询范围时比 map 低。

内部实现机理:

  • map：红黑树，有序；效率由树操作决定。
  • unordered_map：哈希表，元素无序。

2023-3-20 · 997 有序数组的平方

997 有序数组的平方

给你一个按非递减顺序排序的整数数组 nums，返回每个数字平方组成的新数组，要求也按非递减顺序排序。

示例 1：

1
2
3
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后 [16,1,0,9,100]，排序后 [0,1,9,16,100]

示例 2：

1
2
输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

方法：首尾双指针，绝对值大的在两侧。比较平方大的放入结果数组尾部，移动对应指针，直到头指针大于尾指针。

第一遍没过：截至条件写成 >= 导致漏掉中间数字。

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> sortedSquares(vector<int>& nums) {
    int length = nums.size();
    vector<int> result(length, 0);
    int k = length - 1;
    for (int i = 0, j = nums.size() - 1; i < nums.size();) { // 双指针 O(n)
        int pre = nums[i] * nums[i];
        int las = nums[j] * nums[j];
        if (pre > las) {
            result[k] = pre;
            k--;
            i++;
        } else {
            result[k] = las;
            k--;
            j--;
        }
        if (i > j) {
            break;
        }

    }
    return result;
}
};

双指针也可先找到负数/正数分界线，复杂度相同。

2023-3-21 · 7 整数反转

7 整数反转

给你一个 32 位有符号整数 x，返回数字部分反转后的结果；若溢出 [−2^31, 2^31−1] 返回 0。假设环境不允许存储 64 位整数。

示例 1： x = 123 -> 321

示例 2： x = -123 -> -321

示例 3： x = 120 -> 21

示例 4： x = 0 -> 0

思路: 取余获得末位，res = res*10 + rem，同时缩小 x/=10，每次检查溢出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int reverse(int x) {
      long reslut = 0;
      while (x != 0) {
          int res;
          res = x % 10; /////保留出第一个余数
          int new_int = reslut * 10 + res;
          if ((new_int - res) / 10 != reslut)    /////边界检查
              return 0;
          x = x / 10;   /////x 缩小为之前的十分之一丢掉余数
          reslut = new_int;
      }
    return reslut;
    }
};
1
2
3
4
5
table Title,Status,file.tags as Tags
from ""
where
contains(file.name,"Lit. Rev.")
sort file.name

2023-3-25 · 盛最多水的容器

11. 盛最多水的容器

给定整数数组 height，找两条线与 x 轴组成的容器最大水量。不能倾斜容器。

方法一：暴力遍历（超时）。

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 maxArea(vector<int>& height) {

        auto* head = &height[0];
        auto* tail = &height[height.size()-1];
        vector<int> res;
        while (head <= &height[height.size()-1]) {
            while (head < tail) {
                auto h = (*head > *tail) ? *tail : *head;
                int l = tail - head;
                int size = h * l;
                res.push_back(size);
                
                tail--;
            }
            head++;
            tail = &height[height.size() - 1];
        }
        auto a = max_element(res.begin(), res.end());
        return *a;
    }

};

双指针解法：left 从头，right 从尾，面积 min(height[left], height[right]) * (right - left)，移动较低的一边以期增大面积。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size() - 1;
        int res = 0;
        while (left < right) {
            // [left, right] 之间的矩形面积
            int cur_area = min(height[left], height[right]) * (right - left);
            res = max(res, cur_area);
            // 双指针技巧，移动较低的一边
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return res;
    }
};

2023-4-1 · 1008 前序遍历构造二叉搜索树

1008. 前序遍历构造二叉搜索树

给定整数数组（BST 的先序遍历），构造树并返回根。保证有解。BST 满足左子树 < 根 < 右子树。

思路：先序第一个是根，根据根值划分左右子树，递归构建；idx==p.size() 截至。null 节点不增加 idx。

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
/**
 * 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 {
    int idx = 0;
    vector<int> p;

public:
    TreeNode* bstFromPreorder(vector<int>& preorder) {
        p = preorder;
        return dfs(INT_MIN, INT_MAX);
    }
    
    TreeNode *dfs(int l ,int r) {

        if (idx == p.size() || p[idx] < INT_MIN || p[idx] > r) {
            return nullptr;
        }
        TreeNode* ans = new TreeNode(p[idx++]);
        ans->left = dfs(l, ans->val);
        ans->right = dfs(ans->val, r);

        return ans;

    }

};

2023-4-5 · 两整数之和

两整数之和

不使用 + -，计算 a 和 b 之和。

思路：无进位加法 a ^ b；进位 a & b << 1，循环直到进位为 0。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int getSum(int a, int b) {
        while (b != 0) {
            unsigned int carry = (unsigned int)(a & b) << 1;
            a = a ^ b;
            b = carry;
        }
        return a;
    }
};

进位示例

  • a = 0101
  • b = 0100
  • carry = 0100 << 1 = 1000
  • a = 0001, b = 1000
  • carry = 0000 << 1 = 0000
  • a = 1001, b = 0000 输出 1001

2023-4-5 · 82 删除排序链表中的重复元素 II

82. 删除排序链表中的重复元素 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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }
        if (head->val != head->next->val) {
            head->next = deleteDuplicates(head->next);
        } else {
            ListNode * move;
            move = head->next;
            while (move && move->val == head->val) {
                move = move->next;
            }
            return head->next = deleteDuplicates(move);
        }
        return 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
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (!head) {
            return head;
        }

        ListNode *dummy = new ListNode(0, head);

        ListNode *cur = dummy;

        while (cur->next && cur->next->next) {
            if (cur->next->val == cur->next->next->val) {
                int x = cur->next->val;
                while (cur->next && cur->next->val == x) {
                    cur->next = cur->next->next;
                }
            } else {
                cur = cur->next;
            }
        }

      return dummy->next;


    }
};

一次遍历，cur/cur->next/cur->next->next 三指针，遇重复跳过所有重复值。

2023-4-15 · 动态规划

动态规划专题 — 322 零钱兑换

给你 k 种面值 c1..ck 的硬币（数量无限）和总金额 amount，求最少硬币数；不可达返回 -1。

如何正确列出状态转移：

  1. base：amount=0 返回 0。
  2. 状态：amount。
  3. 选择：硬币面值。
  4. 定义：dp(amount) 为凑出金额的最少硬币数。

朴素递归（指数级）：

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
int dp(vector<int>& coins, int amount);

int coinChange(vector<int>& coins, int amount) {
    // 题目要求的最终结果是 dp(amount)
    return dp(coins, amount);
}

// 定义：要凑出金额 n，至少要 dp(coins, n) 个硬币
int dp(vector<int>& coins, int amount) {
    // base case
    if (amount == 0) return 0;
    if (amount < 0) return -1;

    int res = INT_MAX;
    for (int coin : coins) {
        // 计算子问题的结果
        int subProblem = dp(coins, amount - coin);
        // 子问题无解则跳过
        if (subProblem == -1) continue;
        // 在子问题中选择最优解，然后加一
        res = min(res, subProblem + 1);
    }

    return res == INT_MAX ? -1 : res;
}

2. 带备忘录的递归

消除冗余：子问题总数 O(n)，时间 O(kn)。

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> memo;
    int dp(vector<int> &coins,int amount)
    {
        if (amount == 0) {return 0 ;}
        if (amount < 0) {return -1;}
        if (memo[amount] != -666) return memo[amount];
        int res = INT_MAX;
        for (int coin: coins)
        {
            int subproblem = dp(coins,amount-coin);
            if (subproblem == -1) continue;
            res = min(subproblem+1,res);
        }
        memo[amount] = res==INT_MAX?-1:res;
        return memo[amount];
    }
    int coinChange(vector<int>& coins, int amount) {
        memo = vector<int>(amount+1,-666);
        return dp(coins,amount);
    }
};

3. dp 数组迭代方法

自底向上，dp[i] 表示金额 i 最少硬币数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, amount + 1);
    // 数组大小为 amount + 1，初始值也为 amount + 1
    dp[0] = 0;

    // 外层 for 循环在遍历所有状态的所有取值
    for (int i = 0; i < dp.size(); i++) {
        // 内层 for 循环在求所有选择的最小值
        for (int coin : coins) {
            // 子问题无解，跳过
            if (i - coin < 0) {
                continue;          ////第一个写成了-1 错误在于-1只能存在于总问题的返回值中，子问题如果无解选择的是跳过。
            }
            dp[i] = min(dp[i], 1 + dp[i - coin]);
        }
    }
    return (dp[amount] == amount + 1) ? -1 : dp[amount];
}

dp 图

2023-4-30 · C++ 常用的函数

常用的函数

无序集合:

1
2
unordered_set<int> visited;
visited.insert(path[i][0]);

vector:

1
vector<int> IN(N+10001);  // 初始化大小为 N+10001 的全 0 列表

哈希表:

1
2
3
4
5
6
7
8
9
#include<unordered_map>

unordered_map<int, int> map;
unordered_map<int, int> hmap{ {1,10},{2,12},{3,13} };
hmap[4] = 14;  /// 赋值

// 根据 key 查找
unordered_map<int, int> hmap{ {1,10},{2,12},{3,13} };
int elem = hmap.at(3);

C++ 二分查找的函数

Lower_bound() 函数

find/find_if 顺序查找，lower_bound/upper_bound/equal_range 二分查找。

语法：

1
2
3
4
5
6
// 在 [first, last) 区域内查找不小于 val 的元素
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
                             const T& val);
// 在 [first, last) 区域内查找第一个不符合 comp 规则的元素
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
                             const T& val, Compare comp);

lower_bound 底层实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template <class ForwardIterator, class T>
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val)
{
    ForwardIterator it;
    iterator_traits<ForwardIterator>::difference_type count, step;
    count = distance(first,last);
    while (count>0)
    {
        it = first; step=count/2; advance (it,step);
        if (*it<val) {  //或者 if (comp(*it,val))，对应第 2 种语法格式
            first=++it;
            count-=step+1;
        }
        else count=step;
    }
    return first;
}

适用于已排好序的序列（不要求全局升降序，只需满足小于 val 的在前）。

upper_bound() 函数

类似 lower_bound，同样要求序列满足上面“已排好序”。

equal_range() 函数

1
2
// 找到 [first, last) 范围中所有等于 val 的元素
pair<ForwardIterator,ForwardIterator> equal_range (ForwardIterator first, ForwardIterator last, const T& val);

参考链接

2023-6-4 · 75 颜色分类

颜色分类

给定 n 个元素数组 nums，值为 0/1/2，原地排序为红白蓝（0/1/2）。不能用库 sort。

思路: 一次遍历把 0 插头、2 插尾；数组移动耗时，可用链表。或单指针两次遍历：先放 0 到头，再放 1 到头（从非零处开始）。

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

复杂度：时间 O(n)，空间 O(1)。

方法二：双指针

两个指针 p0/p1 分别交换 0 和 1，一次遍历。

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

2023-6-5 · 设计哈希映射

设计哈希映射

不使用内建哈希表，设计 MyHashMap：put/get/remove。

优化小 tips：emplace_back 代替 push_back(make_pair(...))。

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
class MyHashMap {
private:
    vector<list<pair<int,int>>> data;
    static const int base=79;
    static int hash(int key)
    {
        return key%base;
    }
public:
    MyHashMap() :data(base) {}
    
    void put(int key, int value) {
        int h=hash(key);
        for(auto it=data[h].begin(); it!=data[h].end();it++)
        {
            if((*it).first==key)
            {
                (*it).second=value;
                return;
            }
        }
        data[h].emplace_back(key,value);
    }
    
    int get(int key) {
        int h=hash(key);
        for(auto it=data[h].begin(); it!=data[h].end();it++)
        {
            if((*it).first==key)
            {
                return (*it).second;
            }
        }
        return -1;
    }
    
    void remove(int key) {
        int h=hash(key);
        for (auto it = data[h].begin(); it != data[h].end(); it++) {
            if ((*it).first == key) {
                data[h].erase(it);
                return;
            }
        }
    }

};

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

2023-6-7 · 48 旋转图像

旋转图像

给定 n×n 矩阵 matrix，原地顺时针旋转 90 度。不能使用额外矩阵。

思路: 先按主对角线翻转，再反转每行；逆时针则按副对角线翻转再反转每行。

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:
    void rotate(vector<vector<int>>& matrix) {
        for(int i=0;i<matrix.size();i++) {
            for(int j=i;j<matrix.size();j++) {
                int temp=matrix[i][j];
                matrix[i][j]=matrix[j][i];
                matrix[j][i]=temp;
            }
        }
        ///逆转每一行
        for(vector<int>&row:matrix) {
             reverse(row);
         }
    }
    void reverse(vector<int> &arr)
    {
        int i=0,j=arr.size()-1;
        while(j>i)
        {
            int temp=arr[i];
            arr[i]=arr[j];
            arr[j]=temp;
            i++;
            j--;
        }
    }
};

2023-6-10 · 59 螺旋矩阵

59 螺旋矩阵

给你正整数 n，生成 1..n^2 顺时针螺旋的 n x n 矩阵。

解题思路: 按上/右/下/左界收缩螺旋填充，num<=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
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:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> martix(n,vector<int>(n,0));
        int upper_bound=0;
        int low_bound=n-1;
        int right_bound=n-1;
        int left_bound=0;
        int num=1;
        while(num<=n*n)
        {
            if(upper_bound<=low_bound)
            {
                for(int j=left_bound;j<=right_bound;j++)
                {
                    martix[upper_bound][j]=num++;
                }
                upper_bound++;
            }
            if(left_bound<=right_bound)
            {
                for(int j=upper_bound;j<=low_bound;j++)
                {
                    martix[j][right_bound]=num++;
                }
            right_bound--;

            }
            if(upper_bound<=low_bound)
            {
                for(int j=right_bound;j>=left_bound;j--)
                {
                    martix[low_bound][j]=num++;
                }
                low_bound--;
            }
            if(left_bound<=right_bound)
            {
                for(int j=low_bound;j>=upper_bound;j--)
                {
                    martix[j][left_bound]=num++;
                }            
                left_bound++;
            }

        }
        return martix;





    }
};

spiral

谢谢你请我吃糖果。

赏

谢谢你请我吃糖果

支付宝
微信

扫一扫，分享到微信

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia-plus根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

主要涉及技术：
Java后端开发、聚合支付、
公众号开发、开源爱好者、Linux

联系QQ:2434387555

很惭愧

只做了一点微小的工作
谢谢大家