leetcode题目记录

发表于

20211004用两个栈实现队列

剑指 Offer 09. 用两个栈实现队列 - 力扣（LeetCode） (leetcode-cn.com)

我的思路

栈和队列是相反的，先后入两个不同的栈相当于入一个队列，

比如Q{1，2，3，4}，head =1，tail=4，

S1=[4，3，2，1]，top=4，bottom=1，让S1中的元素一个个弹出至S2中，可以得到S2=[1，2，3，4]，top=1，bottom=4。

对于刚建立的空CQueue，返回值为null，

需要实现appendTail和deleteHead，

appendTail返回值是null，需要把新tail元素压入S1中位于S1top，把S2全部更新才可以实现把tail放至S2的bottom，但是这样的话每次appendTail都要产生一个全新的S2，会开一块新的内存空间，并且出栈入栈，那复杂度。。。。不不不，不用啦哈哈，因为有两个栈一个出清空，另一个入填满，来回倒来倒去就可以啦!

所以过程是S1=[4，3，2，1]，S2=[]

S1=[3，2，1]，S2=[4]；S1=[2，1]，S2=[3，4]…S1=[]，S2=[1，2，3，4]

appendTail

初始S1=[]，S2=[1，2，3，4]；S2出栈至S1，元素顺序全部倒置，变为S1=[4，3，2，1]，S2=[]，此时把tail=5入栈到S1，变为S1=[5，4，3，2，1]，S2=[]；再次让S1中的元素一个个弹出至S2中，变为S1=[]，S2=[1，2，3，4，5]，实现了appendTail功能。

输出null。

每次append后重新倒了回去，多花了一倍时间20211028.

deleteHead

直接pop掉S2的顶部元素即可。输出栈顶元素。

忽略点

用size作为循环的终止条件，size是会随着每一次的pop、push操作更新的。

在构造函数中定义的变量是由于在构造函数中定义，作用域为局部变量。

20211010剑指 Offer 30. 包含min函数的栈

push、pop、top方法是一定的，当顶部数据弹出后，还是能够很快找到最小值，min的复杂度为O(1)。

设置一个数组用于排序或者从头到尾的hash表格也可以，但有负数。

20211024

1.想到啦！本题目的难点在于怎么可以找到一种数据结构，它有记忆性，当插入、删除一个数的时候，可以对数据进行排序，并且可以很方便的取出最小值。用最小优先队列就可以了，其实就是维护一个最小堆，一次操作中复杂度为O(lgn)但堆怎么删除一个数据呢？需要对于每个节点记录parent。

2.其实每次使用数组来存放stack里的所有数据的非降序排序结果也可以，但是每次push后需要扫描排序，排序复杂度为O(n)，当pop后也需要排序，主要是将后面的值向前挪动，复杂度为O(n)。

3.或者偷懒，使用优先队列priority_queue来实现自动排序 。orz

忽略点

对于priority_queue，pop掉的 是栈顶元素，即排序后的栈顶元素，而不是stack的顶部，怎么可以删除掉任意一个位置的元素呢？

(10条消息) O(1) 复杂度支持任意位置删除的 priority_queue 实现_努力中的老周的专栏-CSDN博客

MAXHEAP 内部有两个优先队列，其中 Q 队列保存当前元素，D 队列保存需要删除的元素。一个是数据，一个是待删除数据，当两个 priority_queue 的 top() 元素相同的时候，我们再删除两个优先队列的 top。

while(!D.empty()&&Q.top()==D.top()) {Q.pop();D.pop();}当删除的值是当前队列的头部，就删除，否则将其暂存在待删除队列当中，等到之后比待删除队列中大的元素删除后，再删除待删除队列的元素。

pq插入5，Q.top()=5,Q={5};

pq插入8，Q.top()=8,Q={8,5};

pq插入6，Q.top()=8,Q={8,5,6};

pq插入4，Q.top()=8,Q={8,5,6,4};

pq.erase(8),D.push(8),Q.pop(),Q={6,5,4};D.pop(),D={};Q.top()=6;

pq.erase(5),D.push(5),D={5}；

pq.erase(6),D.push(6),D={6,5}

开辟了两个优先队列，其实占用了空间，也可以用两个数组每次把排序的结果存下来，来回倒。

好思路

两个stack分别作用，一个当作主stack，另一个用于存放比当前元素小的值。

20211026剑指 Offer 06. 从尾到头打印链表 - 力扣（LeetCode） (leetcode-cn.com)

链表反转，怎么表示一个链表?

指针，或者是用类来写链表的每一个node，包含key、pre、next，但怎么访问下一个值呢？

或者用结构体，结构体指针指向向下一个node，每次把链表的相连处断开，用temp存储临时断开的指针，在重新连到合适的位置上。

但要怎么拿到最后一个node呢？从前向后访问到尾部，复杂度。

20211028

从头开始以链表中的每一个元素为单元，改变它的next就可以了。

对于head指针，若head指向了空，则是一个空链表。

对于第一个有数据的节点，将除开他的剩余部分先存下来，将其next赋值为NULL。

对于剩下的部分，若为NULL说明已经到达了，链表的尾部，可以结束扫描。

否则将剩余部分中第一个node的指针指向上一个已经处理过的node。

忽略点

比我想得简单，每一个node都带有数据。

纠结的是链表的格式，传入的参数是头节点的指针，此指针可以指向数据域和域。用阶梯状那样的链表来在脑中可视化

20211029剑指 Offer 35. 复杂链表的复制 - 力扣（LeetCode） (leetcode-cn.com)

看到题目的感觉是直接记录下一个节点的指针和random的值，但是random的类型是node型指针。怎么把*和出现的顺序的index结合起来呢？

官方题解

对一个特殊的链表进行深拷贝。如果是普通链表，可以直接按照遍历的顺序创建链表节点。

本题中因为随机指针的存在，当我们拷贝节点时，「当前节点的随机指针指向的节点」可能还没创建，因此我们需要变换思路。

一个可行方案是，我们利用回溯的方式，让每个节点的拷贝操作相互独立。

对于当前节点，我们首先要进行拷贝，然后我们进行「当前节点的后继节点」和「当前节点的随机指针指向的节点」拷贝，拷贝完成后将创建的新节点的指针返回，即可完成当前节点的两指针的赋值。

读完这个话也想不到应该怎么做呢？

具体地，我们用哈希表记录每一个节点对应新节点的创建情况，

遍历该链表的过程中，我们检查「当前节点的后继节点」和「当前节点的随机指针指向的节点」的创建情况。

如果这两个节点中的任何一个节点的新节点没有被创建，我们都立刻递归地进行创建。

当我们拷贝完成，回溯到当前层时，我们即可完成当前节点的指针赋值。注意一个节点可能被多个其他节点指向，因此我们可能递归地多次尝试拷贝某个节点，为了防止重复拷贝，我们需要首先检查当前节点是否被拷贝过，如果已经拷贝过，我们可以直接从哈希表中取出拷贝后的节点的指针并返回即可。

20211030

假如不是一个复杂链表，对于一个简单链表的复制,

算法笔记上是建立一个链表，他传入的参数是val的数组，而不是复制一个链表。

能想到的是扫描老链表，用它的val来新建立链表。如果直接指针复制的话，那各种指针就是乱的。

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
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    
    Node(int _val) {
        val = _val;
        next = NULL;
    }
};
*/
class Solution {
public:
    Node* buildList(Node* head) {
        Node* new_list_cur = new Node;
        Node* newHead = new_list_cur;
        Node* input_cur = head;
        while(input_cur!=NULL){
            new_list_cur.val = input_cur.val;
            new_list_cur.next =  new Node;
            input_cur = input_cur.next;
            new_list_cur = new_list_cur.next;
        }
        return newHead;
    }
};

官方给了两种思路

官方思路一

1.复制链表节点，两者建立map映射，key为输入链表节点，value为输出链表节点，一轮循环。

2.第二轮遍历，链接节点链接起来，对于新复制的节点，对于random和next使用输入链表的节点赋值。

两轮遍历复杂度O(N),使用map，空间复杂度O(N).

官方思路二

https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/comments/249391

1.第一轮遍历，在每一个节点后边复制一个一样值的新节点。

2.第二轮遍历，对于复制节点，赋值随即指针（假如没有random，就不赋值）。

3.第三轮遍历，链表拆分，stride的设计。对于原链表的尾节点需要单独处理。

剑指 Offer 03. 数组中重复的数字 - 力扣（LeetCode） (leetcode-cn.com)

20211102剑指 Offer 03. 数组中重复的数字 - 力扣（LeetCode） (leetcode-cn.com)

​ error: variable-sized object may not be initialized?这个提示是：变量大小的对象不能被初始化, const int max =100000;

剑指 Offer 03. 数组中重复的数字（哈希表 / 原地交换，清晰图解） - 数组中重复的数字 - 力扣（LeetCode） (leetcode-cn.com)

好思路，从前向后排字典，后边在遇到重复的就可以发现了。

遍历数组 numsnums ，设索引初始值为 i = 0i=0 :

若 nums[i] = inums[i]=i ： 说明此数字已在对应索引位置，无需交换，因此跳过；
若 nums[nums[i]] = nums[i]nums[nums[i]]=nums[i] ： 代表索引 nums[i]nums[i] 处和索引 ii 处的元素值都为 nums[i]nums[i] ，即找到一组重复值，返回此值 nums[i]nums[i] ；
否则： 交换索引为 ii 和 nums[i]nums[i] 的元素值，将此数字交换至对应索引位置。

作者：jyd
链接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/solution/mian-shi-ti-03-shu-zu-zhong-zhong-fu-de-shu-zi-yua/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

20211102剑指 Offer 53 - I. 在排序数组中查找数字 I - 力扣（LeetCode） (leetcode-cn.com)

此题在于怎么快速找到一个数字在排序中的位置。二分法。

20211103剑指 Offer 53 - II. 0～n-1中缺失的数字 题解 - 力扣（LeetCode） (leetcode-cn.com)

从头到尾扫描，遇到不一样的，break。假如是最后一个错误，for循环里边有个i++，可以自动的处理这种情况。

20211103剑指 Offer 04. 二维数组中的查找 - 力扣（LeetCode） (leetcode-cn.com)

感觉应该用DFS，或者BFS，斜着扫描。

面试题04. 二维数组中的查找（标志数，清晰图解） - 二维数组中的查找 - 力扣（LeetCode） (leetcode-cn.com)旋转45°

20211103剑指 Offer 11. 旋转数组的最小数字 - 力扣（LeetCode） (leetcode-cn.com)

找到一个数字比左边小，比右边大。

20211105剑指 Offer 11. 旋转数组的最小数字 - 力扣（LeetCode） (leetcode-cn.com)

硬找，用二分。

20211106 剑指 Offer 50. 第一个只出现一次的字符 - 力扣（LeetCode） (leetcode-cn.com)

unordered_map,排序方式不是按照进入的顺序排的。

哈希表，auto遍历

首先是c++中的哈希表和Python中的字典

20211108剑指 Offer 32 - II. 从上到下打印二叉树 II - 力扣（LeetCode） (leetcode-cn.com)

怎么记录每一层的高度呢？

分层打印的思路，一层开始时候，队列里边的元素是当前层的。面试题32 - II. 从上到下打印二叉树 II（层序遍历 BFS，清晰图解） - 从上到下打印二叉树 II - 力扣（LeetCode） (leetcode-cn.com)

dfs维护层数递归C++, 层序遍历, DFS+BFS, 套模板就完事了 - 从上到下打印二叉树 II - 力扣（LeetCode） (leetcode-cn.com)

20211108剑指 Offer 32 - III. 从上到下打印二叉树 III - 力扣（LeetCode） (leetcode-cn.com)

想到的是仅在tmp完全存储后，用stack来颠倒数据。

20211109递归方式解决 - 树的子结构 - 力扣（LeetCode） (leetcode-cn.com)

二叉树题解总结

一篇文章带你吃透对称性递归(思路分析+解题模板+案例解读) - 树的子结构 - 力扣（LeetCode） (leetcode-cn.com)

20211109剑指 Offer 27. 二叉树的镜像（递归 / 辅助栈，清晰图解） - 二叉树的镜像 - 力扣（LeetCode） (leetcode-cn.com)

递归。用栈。

4种解决方式（BFS，DFS，中序遍历，递归方式），最好的击败了100%的用户 - 二叉树的镜像 - 力扣（LeetCode） (leetcode-cn.com)

还有一些其他的方法。

20211109剑指 Offer 28. 对称的二叉树 - 力扣（LeetCode） (leetcode-cn.com)

对称二叉树，镜像二叉树后，看是不是一样的结构。

递归思路与上题类似，递归不能想太多啊 - 对称的二叉树 - 力扣（LeetCode） (leetcode-cn.com)

20211109动态规划套路详解 - 斐波那契数 - 力扣（LeetCode） (leetcode-cn.com)

动态规划套路详解

首先，动态规划问题的一般形式就是求最值。动态规划其实是运筹学的一种最优化方法，只不过在计算机问题上应用比较多，比如说让你求最长递增子序列呀，最小编辑距离呀等等。

重叠子问题。

最优子结构。

正确的状态转移方程。

明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义。

但凡遇到需要递归的问题，最好都画出递归树，这对你分析算法的复杂度，寻找算法低效的原因都有巨大帮助。

要符合「最优子结构」，子问题间必须互相独立。

确定 base case。确定「状态」，也就是原问题和子问题中会变化的变量。确定「选择」，也就是导致「状态」产生变化的行为。明确 dp 函数/数组的定义。一般来说函数的参数就是状态转移中会变化的量，也就是上面说到的「状态」；函数的返回值就是题目要求我们计算的量，与选择有关系的。

vector初始化

(12条消息) C++ vector的初始化_锤某的博客-CSDN博客_c++ vector 初始化

20211112

C++ std::vector::resize() 方法解析（菜鸟看了秒懂） - 云+社区 - 腾讯云 (tencent.com)

【零钱兑换】贪心 + dfs = 8ms （更新） - 零钱兑换 - 力扣（LeetCode） (leetcode-cn.com)

20211113青蛙跳台阶剑指 Offer 10- II. 青蛙跳台阶问题 - 力扣（LeetCode） (leetcode-cn.com)

1、确定base case，这个很简单，显然目标金额 amount 为 0 时算法返回 0，因为不需要任何硬币就已经凑出目标金额了。

2、确定「状态」，也就是原问题和子问题中会变化的变量。由于硬币数量无限，硬币的面额也是题目给定的，只有目标金额会不断地向 base case 靠近，所以唯一的「状态」就是目标金额 amount。

3、确定「选择」，也就是导致「状态」产生变化的行为。目标金额为什么变化呢，因为你在选择硬币，你每选择一枚硬币，就相当于减少了目标金额。所以说所有硬币的面值，就是你的「选择」。

4、明确 dp 函数/数组的定义。我们这里讲的是自顶向下的解法，所以会有一个递归的 dp 函数，一般来说函数的参数就是状态转移中会变化的量，也就是上面说到的「状态」；函数的返回值就是题目要求我们计算的量。就本题来说，状态只有一个，即「目标金额」，题目要求我们计算凑出目标金额所需的最少硬币数量。所以我们可以这样定义 dp 函数：

dp(n) 的定义：输入一个目标金额 n，返回凑出目标金额 n 的最少硬币数量。

是一个fib题目。

20211113剑指 Offer 63. 股票的最大利润 - 力扣（LeetCode） (leetcode-cn.com)

硬算，记录两个数字的差值，从前到后扫描是n(n-1)/2。

base

状态 i天数

选择

找到最小值，在最小值之后看是否会涨价。

动态规划

  • 状态定义： 设动态规划列表 dp ，dp[i] 代表以 prices[i]为结尾的子数组的最大利润（以下简称为 前 i 日的最大利润 ）。

  • 转移方程： 由于题目限定 “买卖该股票一次” ，因此前 i 日最大利润 dp[i]等于前 i - 1 日最大利润 dp[i-1]和第 i 日卖出的最大利润中的最大值。

  • 初始状态： dp[0] = 0，即首日利润为 0 ；

  • 返回值： dp[n - 1] ，其中 n 为 dp 列表长度。

20211114 贪心+分治+动态规划法_面试题42. 连续子数组的最大和 - 连续子数组的最大和 - 力扣（LeetCode） (leetcode-cn.com)

分治没怎么明白

20211114十大排序算法(背诵版+动图) - 力扣（LeetCode） (leetcode-cn.com)

帅地玩编程-校招|面试|学习路线，你都可以在这里找到 (iamshuaidi.com)面试经验

20211115对链表进行插入排序 - 对链表进行插入排序 - 力扣（LeetCode） (leetcode-cn.com)

0.若无空，直接返回。

1.哑节点，可以在head前插入节点。

2.lastSorted，已经排序部分的最后一个节点，开始为头节点。

3.维护待插入元素curr，开始时候为头节点下一个节点。

4.比较lastSorted和curr的节点值，开始时候为head.next。

a.lastSorted->val比curr->还小<=，直接把lastSorted后移一位。

b.否则从链表头向后遍历,找到插入curr的位置，prev为插入curr位置的前一个结点。

5.令 curr = lastSorted.next，此时 curr 为下一个待插入的元素。

6.重复4、5，直到curr变成空。

7.返回哑节点的下一位置。

20211116

内推｜字节跳动｜多项岗位｜北京+上海 - 力扣（LeetCode） (leetcode-cn.com)

不是每个题目都有参考的，要泛化呀。

20211117剑指 Offer 46. 把数字翻译成字符串 - 力扣（LeetCode） (leetcode-cn.com)

类似于青蛙跳台阶，一次可以跳一格还是跳两格，是每次用一个字符还是两个字符。

两个字符可能会无效，必须小于25。

to_string 函数

(17条消息) C++编程语言中整型转换为字符串类型的方法_liitdar的博客-CSDN博客_c++整型转字符串

20211119面试题25. 合并两个排序的链表（伪头节点，清晰图解） - 合并两个排序的链表 - 力扣（LeetCode） (leetcode-cn.com)

双指针

20211120【一句话，两张图】优雅理解原理 为何这样设计 - 两个链表的第一个公共节点 - 力扣（LeetCode） (leetcode-cn.com)

比较地址。

20211120剑指 Offer 21. 调整数组顺序使奇数位于偶数前面（双指针，清晰图解） - 调整数组顺序使奇数位于偶数前面 - 力扣（LeetCode） (leetcode-cn.com)

快慢指针 用于调整数组位置。

【题解】：首尾双指针，快慢双指针 - 调整数组顺序使奇数位于偶数前面 - 力扣（LeetCode） (leetcode-cn.com)

20211120 面试题57. 和为 s 的两个数字（双指针 + 证明，清晰图解） - 和为s的两个数字 - 力扣（LeetCode） (leetcode-cn.com)

相当于一种剪枝。

20211125礼物的最大价值 - 礼物的最大价值 - 力扣（LeetCode） (leetcode-cn.com)

除了使用dp之外，还可以使用dfs。

礼物的最大价值 - 礼物的最大价值 - 力扣（LeetCode） (leetcode-cn.com)

dp是从上到下，dfs是从下到上回溯。

20211127三种方法： DFS, BFS, 回溯（递归 + 迭代） - 二叉树中和为某一值的路径 - 力扣（LeetCode） (leetcode-cn.com)二叉树路径寻找

20211129 二叉树的最近公共祖先 - 二叉树的最近公共祖先 - 力扣（LeetCode） (leetcode-cn.com)

https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/solution/mian-shi-ti-68-ii-er-cha-shu-de-zui-jin-gong-gon-7/512814

https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/solution/mian-shi-ti-68-ii-er-cha-shu-de-zui-jin-gong-gon-7/1076018

1
2
3
1. 若树里面存在p，也存在q，则返回他们的公共祖先。
2. 若树里面只存在p，或只存在q，则返回存在的那一个。
3. 若树里面既不存在p，也不存在q，则返回null。

20211129 11. 盛最多水的容器（双指针，清晰图解） - 盛最多水的容器 - 力扣（LeetCode） (leetcode-cn.com)

2021130剑指 Offer 07. 重建二叉树（分治算法，清晰图解） - 重建二叉树 - 力扣（LeetCode） (leetcode-cn.com)

20211202面试题55 - II. 平衡二叉树（从底至顶、从顶至底，清晰图解） - 平衡二叉树 - 力扣（LeetCode） (leetcode-cn.com)

202112024种解法秒杀TopK（快排/堆/二叉搜索树/计数排序）❤️ - 最小的k个数 - 力扣（LeetCode） (leetcode-cn.com)

C++ vector::assign()用法及代码示例 - 纯净天空 (vimsky.com)是C%2B%2B中的STL，它通过替换旧元素为向量元素分配新值。 如果需要，它也可以修改向量的大小。 size-必须从头开始分配的元素数。 first,- 输入迭代器到初始位置范围。 last - 输入迭代器到最终位置范围。)

20211209【图解】我们之前可能没有搞懂这个题 - 把数组排成最小的数 - 力扣（LeetCode） (leetcode-cn.com)

【图解】我们之前可能没有搞懂这个题 - 把数组排成最小的数 - 力扣（LeetCode） (leetcode-cn.com)

正确性、然后反正。

20211210强连通分量

【MIX】强连通分量(1) Tarjan SCC 缩点 - 力扣（LeetCode） (leetcode-cn.com)

【MIX】强连通分量(2) Kosaraju & 扩展 - 力扣（LeetCode） (leetcode-cn.com)

图的相关算法 - 力扣（LeetCode） (leetcode-cn.com)

leetcode刷题（四）：搜索(深度优先搜索,广度优先搜索）拓扑排序，强连通分量 - 知乎 (zhihu.com)

可能是可读性最强的题解。（TypeScript） - 边界着色 - 力扣（LeetCode） (leetcode-cn.com)

20211211剑指 Offer 38. 字符串的排列 - 力扣（LeetCode） (leetcode-cn.com)

回溯算法详解（修订版） (qq.com)讲的不错！

1、 路径：也就是已经做出的选择。

2、选择列表：也就是你当前可以做的选择。

3、结束条件：也就是到达决策树底层，无法再做选择的条件。\

请问大佬判断重复字符条件这里 !vis[j - 1] && s[j - 1] == s[j] 是啥意思？

https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/solution/zi-fu-chuan-de-pai-lie-by-leetcode-solut-hhvs/994831

https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/solution/zi-fu-chuan-de-pai-lie-by-leetcode-solut-hhvs/995294

若当前字符和上一个字符一样 并且 上一个字符处于未被访问 的状态，说明在上一轮回溯中排列了。

1
2
3
4
5
6
7
8
9
10
result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

20211211下一个排列算法详解：思路+推导+步骤，看不懂算我输！ - 下一个排列 - 力扣（LeetCode） (leetcode-cn.com)

20211213一个模板刷遍所有字符串句子题目！（归纳总结+分类模板+题目分析） - 翻转单词顺序 - 力扣（LeetCode） (leetcode-cn.com)

20211213剑指 Offer 31. 栈的压入、弹出序列 - 力扣（LeetCode） (leetcode-cn.com)

https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/solution/mian-shi-ti-31-zhan-de-ya-ru-dan-chu-xu-lie-mo-n-2/507148

20211215剑指 Offer 14- I. 剪绳子 - 力扣（LeetCode） (leetcode-cn.com)

剑指 Offer 14- I. 剪绳子，还是动态规划好理解，但是贪心真的快 - 剪绳子 - 力扣（LeetCode） (leetcode-cn.com)

343. 整数拆分 - 力扣（LeetCode） (leetcode-cn.com)

20211215剑指 Offer 19. 正则表达式匹配 - 力扣（LeetCode） (leetcode-cn.com)

20211213面试题29. 顺时针打印矩阵（模拟、设定边界，清晰图解） - 顺时针打印矩阵 - 力扣（LeetCode） (leetcode-cn.com)

202111216面试题16. 数值的整数次方（快速幂，清晰图解） - 数值的整数次方 - 力扣（LeetCode） (leetcode-cn.com)

Picture2.png

n=5，res=3，x=3*3=9，n=2。

n =2，x=9*9=81，n=1。

n=1，res=81*3，x=81X81，n=0。

20211218剑指 Offer 65. 不用加减乘除做加法 - 力扣（LeetCode） (leetcode-cn.com)

https://leetcode-cn.com/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof/comments/242474

https://leetcode-cn.com/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof/solution/mian-shi-ti-65-bu-yong-jia-jian-cheng-chu-zuo-ji-7/809000 sum、carry

https://leetcode-cn.com/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof/solution/mian-shi-ti-65-bu-yong-jia-jian-cheng-chu-zuo-ji-7/539350// C++中负数不支持左移位，因为结果是不定的

20211218剑指 Offer 62. 圆圈中最后剩下的数字 - 力扣（LeetCode） (leetcode-cn.com)

0，1，2，3，4。

删除2，从3开始。

https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/jian-zhi-offer-62-yuan-quan-zhong-zui-ho-dcow/1154322

https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/jian-zhi-offer-62-yuan-quan-zhong-zui-ho-dcow/1152926

讲的最好的

换个角度举例解决约瑟夫环 - 圆圈中最后剩下的数字 - 力扣（LeetCode） (leetcode-cn.com)

https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/huan-ge-jiao-du-ju-li-jie-jue-yue-se-fu-huan-by-as/771860

20211220剑指 Offer 56 - I. 数组中数字出现的次数 - 力扣（LeetCode） (leetcode-cn.com)

https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/solution/jian-zhi-offer-56-i-shu-zu-zhong-shu-zi-tykom/889103

20211221剑指 Offer 56 - II. 数组中数字出现的次数 II - 力扣（LeetCode） (leetcode-cn.com)

https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/comments/501039

20211121剑指 Offer 66. 构建乘积数组 - 力扣（LeetCode） (leetcode-cn.com)

剑指 Offer 66. 构建乘积数组（表格分区，清晰图解） - 构建乘积数组 - 力扣（LeetCode） (leetcode-cn.com)

这两个思路写的比较好

https://leetcode-cn.com/problems/gou-jian-cheng-ji-shu-zu-lcof/solution/mian-shi-ti-66-gou-jian-cheng-ji-shu-zu-biao-ge-fe/417592

https://leetcode-cn.com/problems/gou-jian-cheng-ji-shu-zu-lcof/solution/mian-shi-ti-66-gou-jian-cheng-ji-shu-zu-biao-ge-fe/447760

20211221 剑指 Offer 49. 丑数 - 力扣（LeetCode） (leetcode-cn.com)

数组合并

https://leetcode-cn.com/problems/chou-shu-lcof/comments/250364

i,j,k=0;

idx=1，tmp=min(1x2,min(1x3,1x5))=2;i++;u=1,2

idx=2，tmp=min(2x2,min(1x3,1x5))=3;j++;u=1,2,3

idx=3，tmp=min(2x2,min(2x3,1x5))=4;i++;u=1,2,3,4

idx=4，tmp=min(3x2,min(2x3,1x5))=5;k++;u=1,2,3,4,5

idx=5，tmp=min(3x2,min(2x3,2x5))=5;i++,k++;u=1,2,3,4,5,6

丑数II， 合并 3 个有序数组， 清晰的推导思路 - 丑数 - 力扣（LeetCode） (leetcode-cn.com)

https://leetcode-cn.com/problems/chou-shu-lcof/comments/250364

20211221 剑指 Offer 60. n个骰子的点数 - 力扣（LeetCode） (leetcode-cn.com)

https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof/solution/jian-zhi-offer-60-n-ge-tou-zi-de-dian-sh-z36d/882642

20211218 面试题17. 打印从 1 到最大的 n 位数（分治算法 / 全排列，清晰图解） - 打印从1到最大的n位数 - 力扣（LeetCode） (leetcode-cn.com)

大数加减乘除运算总结 - 力扣（LeetCode） (leetcode-cn.com)

20211223Dijkstra 相关题目 - 概率最大的路径 - 力扣（LeetCode） (leetcode-cn.com)

Dijkstra 算法详解 - 概率最大的路径 - 力扣（LeetCode） (leetcode-cn.com)

20211223207. 课程表 - 力扣（LeetCode） (leetcode-cn.com)

https://leetcode-cn.com/problems/course-schedule/solution/course-schedule-tuo-bu-pai-xu-bfsdfsliang-chong-fa/286184

[[1,4],[2,4],[3,1],[3,2]],n=5。

adj：

0：

1：3

2：3

3：

4：1，2

indegree：

0：0

1：1

2：1

3：2

4：0

num=3,Q={0,4}.

f=4,

0：0

1：0

2：0

3：2

4：0

num=1,Q={1,2}.

20211227吃🐳！🤷‍♀️竟然一眼秒懂合并区间！ - 合并区间 - 力扣（LeetCode） (leetcode-cn.com)

2022010333. 搜索旋转排序数组 - 力扣（LeetCode） (leetcode-cn.com)

一文解决 4 道「搜索旋转排序数组」题！ - 搜索旋转排序数组 - 力扣（LeetCode） (leetcode-cn.com)

20220106128. 最长连续序列 - 力扣（LeetCode） (leetcode-cn.com)

只关注第一个打头的字符就可以了。

【小白郎】哈希集合/哈希表/动态规划/并查集四种方法，绝对够兄弟们喝一壶的！ - 最长连续序列 - 力扣（LeetCode） (leetcode-cn.com)

https://leetcode.cn/problems/longest-consecutive-sequence/solution/dong-tai-gui-hua-python-ti-jie-by-jalan/791527

https://leetcode.cn/problems/longest-consecutive-sequence/solution/dong-tai-gui-hua-python-ti-jie-by-jalan/950323

20220113

240. 搜索二维矩阵 II - 力扣（LeetCode） (leetcode-cn.com)

二分，旋转数组那道题目。

20220119图解k个一组翻转链表 - K 个一组翻转链表 - 力扣（LeetCode） (leetcode-cn.com)

动画演示 25. K 个一组翻转链表 - K 个一组翻转链表 - 力扣（LeetCode） (leetcode-cn.com)

K 个一组翻转链表 - K 个一组翻转链表 - 力扣（LeetCode） (leetcode-cn.com)

20220122 https://leetcode-cn.com/problems/search-insert-position/solution/te-bie-hao-yong-de-er-fen-cha-fa-fa-mo-ban-python-/

35. 搜索插入位置 - 力扣（LeetCode） (leetcode-cn.com)

回文链表 - 回文链表 - 力扣（LeetCode） (leetcode-cn.com)

20220126https://leetcode-cn.com/problems/minimum-window-substring/solution/zui-xiao-fu-gai-zi-chuan-by-leetcode-solution/409075

76. 最小覆盖子串

简简单单，非常容易理解的滑动窗口思想 - 最小覆盖子串 - 力扣（LeetCode） (leetcode-cn.com)

这个看懂啦！最小覆盖子串 | 图解滑动窗口 | 最通俗易懂的讲解【c++/java版本】 - 最小覆盖子串 - 力扣（LeetCode） (leetcode-cn.com)

谢谢。0802再次谢谢

20220128 148. 排序链表 - 力扣（LeetCode） (leetcode-cn.com)

https://leetcode-cn.com/problems/sort-list/solution/sort-list-gui-bing-pai-xu-lian-biao-by-jyd/257267

https://leetcode-cn.com/problems/sort-list/solution/sort-list-gui-bing-pai-xu-lian-biao-by-jyd/1316428

https://leetcode-cn.com/problems/sort-list/solution/pai-xu-lian-biao-by-leetcode-solution/675207

二分查找

写对二分查找不是套模板并往里面填空，需要仔细分析题意 - 搜索插入位置 - 力扣（LeetCode） (leetcode-cn.com)

二分查找细节详解，顺便赋诗一首 - 二分查找 - 力扣（LeetCode） (leetcode-cn.com)

为什么要取右边中间数呢？这是因为在区间里 只有 22 个元素的时候，把 [left..right] 划分成 [left..mid - 1] 和 [mid..right] 这两个区间，int mid = (left + right) / 2 这种取法不能把搜索区间缩小。

作者：liweiwei1419
链接：https://leetcode-cn.com/problems/search-insert-position/solution/te-bie-hao-yong-de-er-fen-cha-fa-fa-mo-ban-python-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

写成 while(left < right) ，退出循环的时候有 left == right 成立，好处是：不用判断应该返回 left 还是 right；
区间 [left..right] 划分只有以下两种情况：
分成 [left..mid] 和 [mid + 1..right]，分别对应 right = mid 和 left = mid + 1；
分成 [left..mid - 1] 和 [mid..right]，分别对应 right = mid - 1 和 left = mid，这种情况下。需要将 int mid = (left + right) / 2 改成 int mid = (left + right + 1) / 2，否则会出现死循环，这一点不用记，出现死循环的时候，把 left 和 right 的值打印出来看一下就很清楚了；
退出循环 left == right，如果可以确定区间 [left..right] 一定有解，直接返回 left 就可以，否则还需要对 left 这个位置单独做一次判断；
始终保持不变的是：在区间 [left..right] 里查找目标元素。

35. 搜索插入位置 - 力扣（LeetCode） (leetcode-cn.com)

69. x 的平方根 - 力扣（LeetCode） (leetcode-cn.com)

20220227

动画演示 递归+迭代 617.合并二叉树 - 合并二叉树 - 力扣（LeetCode） (leetcode-cn.com)

https://leetcode-cn.com/problems/diameter-of-binary-tree/solution/er-cha-shu-de-zhi-jing-by-leetcode-solution/1101419

337. 打家劫舍 III - 力扣（LeetCode） (leetcode-cn.com)

https://leetcode-cn.com/problems/house-robber-iii/comments/20026

把二叉搜索树转换为累加树 - 把二叉搜索树转换为累加树 - 力扣（LeetCode） (leetcode-cn.com)

20220209

这要从最大子序和说起，由简到繁 - 最大子矩阵 - 力扣（LeetCode） (leetcode-cn.com)

20220217

详细通俗的思路分析，多解法 - 二叉树展开为链表 - 力扣（LeetCode） (leetcode-cn.com)、、

20220225

史上最全遍历二叉树详解 - 二叉树的前序遍历 - 力扣（LeetCode） (leetcode-cn.com)

20220226

前缀和，递归，回溯 - 路径总和 III - 力扣（LeetCode） (leetcode-cn.com)

20220303

LRU 策略详解和实现 - LRU 缓存 - 力扣（LeetCode） (leetcode-cn.com)

要让 put 和 get 方法的时间复杂度为 O(1)，我们可以总结出 cache 这个数据结构必要的条件：查找快，插入快，删除快，有顺序之分。

哈希表查找快，但是数据无固定顺序；

链表有顺序之分，插入删除快，但是查找慢。所以结合一下，形成一种新的数据结构：哈希链表。

https://leetcode-cn.com/problems/lru-cache/solution/lru-ce-lue-xiang-jie-he-shi-xian-by-labuladong/

20220304

15. 三数之和 - 力扣（LeetCode） (leetcode-cn.com)

https://leetcode-cn.com/problems/3sum/solution/san-shu-zhi-he-by-leetcode-solution/696825’

20220325 找硬币（again）好好体会一下吧

动态规划套路详解 - 斐波那契数 - 力扣（LeetCode） (leetcode-cn.com)

暴力法类似于回溯dfs。

dp的要素，明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义。

换零钱，base是是否可以换到。状态是还需要换多少，选择是选择硬币。

相比于暴力回溯，带有备忘录的解法，把已经计算过的直接返回。

20220403股票持有

跌妈不认？一口气团灭6道股票算法打打气 - 童欧巴的文章 - 知乎 https://zhuanlan.zhihu.com/p/353885321

此题解对k的解释有问题，k应该是已经买入了多少次

leetcode 买卖股票合集 - 木吉子的文章 - 知乎 https://zhuanlan.zhihu.com/p/127085446

1
2
3
4
5
6
7
8
9
10
11
12
dp[i][k][0]
dp[i][k][1]
//不同情况下的股票利润和
i: 天数 范围是 (0 <= i <= n - 1)
k: k是买入的次数，也就是记录交易次数（这里不是卖出）。
0: 没有持有股票
1: 持有股票
n: 股票数组长度

// 举个 
dp[2][2][1] // 今天是第 2 天，手中持有股票，进行了 2 次交易，最大的股票利润和

状态转移

1
2
3
4
5
6
7
//第i天没有持有，已经买入了k次，最大股票利润和转移方程
//前一天无持有；前一天有持有，今日卖出。都已经买入了k次。
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + price[i])

//第i天持有，买入了k次，最大股票利润和转移矩阵
//前一天有持有，已经买了k此。前一天没有持有，已经买了k-1次数，今日再次买。
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0]-price(1))

121. 买卖股票的最佳时机 - 力扣（LeetCode） (leetcode-cn.com)

basecase：第0天买入或者什么也不做的利润。

状态：哪一天。

选择，加入今天持有，今天是在昨天这一状态上做选择获得今天的状态。

dp：股票利润。

1、确定 base case，这个很简单，显然目标金额 amount 为 0 时算法返回 0，因为不需要任何硬币就已经凑出目标金额了。

2、确定「状态」，也就是原问题和子问题中会变化的变量。由于硬币数量无限，硬币的面额也是题目给定的，只有目标金额会不断地向 base case 靠近，所以唯一的「状态」就是目标金额 amount。

3、确定「选择」，也就是导致「状态」产生变化的行为。目标金额为什么变化呢，因为你在选择硬币，你每选择一枚硬币，就相当于减少了目标金额。所以说所有硬币的面值，就是你的「选择」。

4、明确 dp 函数/数组的定义。我们这里讲的是自顶向下的解法，所以会有一个递归的 dp 函数，一般来说函数的参数就是状态转移中会变化的量，也就是上面说到的「状态」；函数的返回值就是题目要求我们计算的量。就本题来说，状态只有一个，即「目标金额」，题目要求我们计算凑出目标金额所需的最少硬币数量。所以我们可以这样定义 dp 函数：

作者：labuladong
链接：https://leetcode-cn.com/problems/fibonacci-number/solution/dong-tai-gui-hua-tao-lu-xiang-jie-by-labuladong/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

122. 买卖股票的最佳时机 II - 力扣（LeetCode） (leetcode-cn.com)

可以无限次买入卖出，但买入前必须手上没有 股票，即买入前已经卖出了。

当前手上没有股票，也可能时已经交易过很多次了，dp可能为负数。（与k无关）。

123. 买卖股票的最佳时机 III - 力扣（LeetCode） (leetcode-cn.com)

1
dp[i - 1][0][0] 当前手上没有股票，也没有交易过。0

188. 买卖股票的最佳时机 IV - 力扣（LeetCode） (leetcode-cn.com)

可以买卖k次数。

图解 k 次交易股票+三维 dp - 买卖股票的最佳时机 IV - 力扣（LeetCode） (leetcode-cn.com)

309. 最佳买卖股票时机含冷冻期 - 力扣（LeetCode） (leetcode-cn.com)

『 动态规划 』 DP模板解决一众买卖股票问题 - 买卖股票的最佳时机 III - 力扣（LeetCode） (leetcode-cn.com) 最多k次交易，最多两次交易。

20220415

45. 跳跃游戏 II - 力扣（LeetCode） (leetcode-cn.com)

如果有多个位置通过跳跃都能够到达最后一个位置，那么我们应该如何进行选择呢？直观上来看，我们可以「贪心」地选择距离最后一个位置最远的那个位置，也就是对应下标最小的那个位置。因此，我们可以从左到右遍历数组，选择第一个满足要求的位置。

找到最后一步跳跃前所在的位置之后，我们继续贪心地寻找倒数第二步跳跃前所在的位置，以此类推，直到找到数组的开始位置。

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/jump-game-ii/solution/tiao-yue-you-xi-ii-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

当位置超前倒，倒到0是贪心完毕。

https://leetcode-cn.com/problems/jump-game-ii/solution/tiao-yue-you-xi-ii-by-leetcode-solution/751983

如果我们「贪心」地进行正向查找，每次找到可到达的最远位置，就可以在线性时间内得到最少的跳跃次数。选最远可到达的地方。

end当前可以扫描的范围，这一步可以到的范围。

更新下一步可以去的最远距离maxreach。在i到end这个范围内搜索是不是有某一步可以去更远的，如果有就更新可以去的最远距离maxreach。如果i和end碰上了，扫描完成 ，这一步跳完了，其实下一步能取得最远距离，和是从哪一个台阶跳的已经被maxreach选择好了。用maxreach更新end。

在遍历数组时，我们不访问最后一个元素，这是因为在访问最后一个元素之前，我们的边界一定大于等于最后一个位置，否则就无法跳到最后一个位置了。如果访问最后一个元素，在边界正好为最后一个位置的情况下，我们会增加一次「不必要的跳跃次数」，因此我们不必访问最后一个元素。、

能继续向后扫描，i可以一直加到n-2。 i是起跳点。

二叉树中序遍历的迭代写法

二叉树的中序遍历 - 二叉树的中序遍历 - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stk;
        while (root != nullptr || !stk.empty()) {//判断右侧是不是空
            while (root != nullptr) {    //一直进递归栈，判断左侧是不是空
                stk.push(root);
                root = root->left;      //inorder(root->left)
            }
            root = stk.top();          //if root==null ,return ,print(root),如果到了nullptr，返回上一层递归栈
            stk.pop();
            res.push_back(root->val);   
            root = root->right;		   //inorder(root->right)
        }
        return res;
    }
};

https://leetcode-cn.com/problems/binary-tree-postorder-traversal/comments/495211

三种二叉树非递归解法的统一写法。https://leetcode-cn.com/problems/binary-tree-postorder-traversal/comments/495211

https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/er-cha-shu-de-hou-xu-bian-li-by-leetcode-solution/1194730

20220423 124. 二叉树中的最大路径和 - 力扣（LeetCode） (leetcode-cn.com)

https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/comments/690627

20220430

【最小公倍数】【C++】 - 镜面反射 - 力扣（LeetCode） (leetcode-cn.com)

光会反射吗？那我们假设光不反射好了。 - 镜面反射 - 力扣（LeetCode） (leetcode-cn.com)

20220502

「手画图解」动态规划，需要仔细的分情况讨论 - 正则表达式匹配 - 力扣（LeetCode） (leetcode-cn.com)

20220503

一套框架解决「背包问题」 - 单词拆分 - 力扣（LeetCode） (leetcode-cn.com)

「手画图解」剖析三种解法: DFS, BFS, 动态规划 |139.单词拆分 - 单词拆分 - 力扣（LeetCode） (leetcode-cn.com)

20220506【先排序，再插队】动画演示算法过程，有点小套路 - 根据身高重建队列 - 力扣（LeetCode） (leetcode-cn.com)

https://leetcode-cn.com/problems/queue-reconstruction-by-height/solution/406du-shuo-shi-tan-xin-na-yao-wei-shi-yao-yong-tan/

(30条消息) reference to non-static member function must be called 解决方案_ForeverHaibara的博客-CSDN博客

原因

class中函数参数隐藏了this指针，实际上cmp的参数有3个而非2个，不符合sort函数的期望。

20220507

思路清晰明了，看不懂？？不存在的！！ - 最短无序连续子数组 - 力扣（LeetCode） (leetcode-cn.com)

【任务调度器】C++ 桶子_配图理解 - 任务调度器 - 力扣（LeetCode） (leetcode-cn.com)

遇到比前面小的 ，更新结束位置。

遇到比后面大的，更新开始位置。

20220510

【最简单易懂的】动态规划 - 括号生成 - 力扣（LeetCode）

20220511

39. 组合总和 - 力扣（LeetCode）

20220513

https://leetcode.cn/problems/subsets/comments/1011321

1
python -m pip install --upgrade pip

# 20220515

检查是否有合法括号字符串路径 - 提交记录 - 力扣（LeetCode）

20220519

https://leetcode.cn/problems/sliding-window-maximum/solution/hua-dong-chuang-kou-zui-da-zhi-by-leetco-ki6m/

20220525

【柱状图中最大的矩形】单调栈入门，使用单调栈快速寻找边界 - 柱状图中最大的矩形 - 力扣（LeetCode）

暴力解法、栈（单调栈、哨兵技巧） - 柱状图中最大的矩形 - 力扣（LeetCode）

看了一圈 最后还是别的题解几句话看明白了 明确一点，遍历每个高度，是要以当前高度为基准，寻找最大的宽度 组成最大的矩形面积那就是要找左边第一个小于当前高度的下标left，再找右边第一个小于当前高度的下标right 那宽度就是这两个下标之间的距离了 但是要排除这两个下标 所以是right-left-1 用单调栈就可以很方便确定这两个边界了 题解讲了很多 但是貌似没有点明为什么这么做

https://leetcode.cn/problems/largest-rectangle-in-histogram/solution/bao-li-jie-fa-zhan-by-liweiwei1419/942639

[【接雨水】单调递减栈，简洁代码，动图模拟 - 接雨水 - 力扣（LeetCode）

20220528

739. 每日温度 - 力扣（LeetCode）

https://leetcode.cn/problems/daily-temperatures/comments/11938

https://leetcode.cn/problems/daily-temperatures/comments/13032

动归跳着。比较大的数值。

85. 最大矩形 - 力扣（LeetCode）

https://leetcode.cn/problems/maximal-rectangle/comments/80595

20220530

98. 验证二叉搜索树 - 力扣（LeetCode）

20220531

最长回文子串 - 最长回文子串 - 力扣（LeetCode）

20220601

297. 二叉树的序列化与反序列化 - 力扣（LeetCode）

https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/comments/27600

isalnum()

判断一个字符是否是字母或者（十进制）数字，若为字母或者数字，则返回True(非0值)，否者返回False(0)

atoi()

atoi()函数将数字格式的字符串转换为整数类型。例如，将字符串“12345”转换成数字12345。

(30条消息) C语言字符类型和数字类型互相转换_qq742143797的博客-CSDN博客_c语言把字符型转为数值型

用atoi，atol，atof函数，分别对应的是整型，long型，double型。
以整型为例：
char str[]=“1234”;
int a=atoi(str);

(30条消息) C++数字转字符串 to_string()_qq_46027243的博客-CSDN博客_数字转字符串

头文件：#include < string >

to_string() 可以将整数、浮点数等数字转换为字符串并返回得到的字符串(注意：只有支持C++11标准的编译器才可以编译成功)

20220620

比特位计数 - 比特位计数 - 力扣（LeetCode）

20220621

移动零 - 移动零 - 力扣（LeetCode）

20220622

画解算法：279. 完全平方数 - 完全平方数 - 力扣（LeetCode）

20220625

513. 找树左下角的值 - 力扣（LeetCode）

(38条消息) bisect——模块_NightCharm的博客-CSDN博客

二分

20220628

一篇文章吃透背包问题！（细致引入+解题模板+例题分析+代码呈现） - 分割等和子集 - 力扣（LeetCode）

$再回顾一下dp[i][j]的含义：从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。$

动态规划（转换为 0-1 背包问题） - 分割等和子集 - 力扣（LeetCode）

在0到i的物品编号内能不能，选择出和为j的物品。

【宫水三叶】一题四解 : 「DFS」&「记忆化搜索」&「全量 DP」&「优化 DP」 - 目标和 - 力扣（LeetCode）

494. 目标和 - 力扣（LeetCode）

动态规划思考全过程 - 目标和 - 力扣（LeetCode）

20220702

241. 为运算表达式设计优先级 - 力扣（LeetCode）

我们可以定义 f[i][j]f[i][j] 为考虑下标不超过 ii 的房子，且最后一间房子颜色为 jj 时的最小成本。

后边的由前边的转移过去。

20220705

两种 O(n) 做法：刷表法 / 填表法（Python/Java/C++/Go） - 知道秘密的人数 - 力扣（LeetCode）

1.向右边填表格，用当前的状态更新之后的状态度。在可以传播秘密的时候，传播。

2.计算当前的值，使用可以传播秘密区间的值更新当前值。dp是当前天

20220710

记忆化搜索（Python/Java/C++/Go） - 网格图中递增路径的数目 - 力扣（LeetCode）

我们把四个方向可以走的格子所对应的状态 f[i’][j’]f[i
′
][j
′
] 累加起来，再加上 11，即当前格子组成的长度为 11 的路径，即为 f[i][j]f[i][j]。

代码实现时可以用记忆化搜索。

作者：endlesscheng
链接：https://leetcode.cn/problems/number-of-increasing-paths-in-a-grid/solution/ji-yi-hua-sou-suo-pythonjavacgo-by-endle-xecc/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

20220714

2337. 移动片段得到字符串 - 力扣（LeetCode）

https://leetcode.cn/problems/move-pieces-to-obtain-a-string/solution/nao-jin-ji-zhuan-wan-pythonjavacgo-by-en-9sqt/1646279

20220716

经典插板法,个人总结版 - 百度文库 (baidu.com)

(38条消息) 隔板法详解（各种方法）_pxlsdz的博客-CSDN博客_隔板法

插板法 - 简书 (jianshu.com)

把10个相同的小球放入3个不同的箱子，每个箱子至少一个，问有几种情况？

C（n-1，m-1）=C(9.2)

求方程 x+y+z=10的正整数解的个数。

求方程 x+y+z=10的非负整数解的个数。

例1 ：把10个相同的小球放入3个不同的箱子，问有几种情况？

例1 ：把10个相同的小球放入3个不同的箱子，问有几种情况？

3个箱子都可能取到空球，条件（2）不满足，此时如果在3个箱子种各预先放入1个小球，则问题就等价于把13个相同小球放入3个不同箱子，每个箱子至少一个，有几种情况？

显然就是 C12 2=66

有一类自然数，从第三个数字开始，每个数字都恰好是它前面两个数字之和，直至不能再写为止，如257，1459等等，这类数共有几个？

第一个位置不能为0，最后一个数字不能为0

0-9分三份数，第二个可以

有一类自然数，从第三个数字开始，每个数字都恰好是它前面两个数字之和，直至不能再写为止…._百度知道 (baidu.com)

设前两位为ab 显然a+b<=9

有空的情况预先+1个虚拟小球

纯数学做法（Python/Java/C++/Go） - 统计理想数组的数目 - 力扣（LeetCode）

相当于k1个隔板，质因子出现的位置，有n-1+k1个位置可以放置。

1
2
3
4
若结尾数字由多个不同的质因子组成，例如：k1个2、k2个3、k3个5，则可将问题分解为：
1、从n-1 + k1个位置中选出k1个位置放质因子2，得到 C(n-1+k1)(k1)
        2、从n-1 + k2个位置中选出k2个位置放质因子3，得到 C(n-1+k2)(k2)
        3、从n-1 + k3个位置中选出k3个位置放质因子5，得到 C(n-1+k3)(k3)
1
假设dp[i][j] 表示从i个位置中选择j个，即 C(i)(j) 组合数可以计算

统计每个数字的某个质因子出现几次。

8里边有3个2

20220718

「手画图解」手写UnionFind，并查集 不再畏惧 - 等式方程的可满足性 - 力扣（LeetCode）

399. 除法求值 - 力扣（LeetCode）

好像是因为Python不支持dict的key为list或dict类型，因为list和dict类型是unhashable（不可哈希）的。也就是说，list的索引不是使用hash值的。所以每次在做两个数组的运算时，都会报错。所以解决方法是把它内部元素改成非list的

使用并查集处理不相交集合问题（Java、Python） - 等式方程的可满足性 - 力扣（LeetCode）

https://leetcode.cn/problems/evaluate-division/solution/399-chu-fa-qiu-zhi-nan-du-zhong-deng-286-w45d/

在「并查集」的一个优化技巧中，「路径压缩」就恰好符合了这样的应用场景。

为了避免并查集所表示的树形结构高度过高，影响查询性能。「路径压缩」就是针对树的高度的优化。「路径压缩」的效果是：在查询一个结点 a 的根结点同时，把结点 a 到根结点的沿途所有结点的父亲结点都指向根结点。如下图所示，除了根结点以外，所有的结点的父亲结点都指向了根结点。特别地，也可以认为根结点的父亲结点就是根结点自己。如下国所示：路径压缩前后，并查集所表示的两棵树形结构等价，路径压缩以后的树的高度为 22，查询性能最好。

作者：LeetCode
链接：https://leetcode.cn/problems/evaluate-division/solution/399-chu-fa-qiu-zhi-nan-du-zhong-deng-286-w45d/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时间复杂度：O((N + Q)\log A)O((N+Q)logA)，

构建并查集 O(N \log A)O(NlogA) ，这里 NN 为输入方程 equations 的长度，每一次执行合并操作的时间复杂度是 O(\log A)O(logA)，这里 AA 是 equations 里不同字符的个数；
查询并查集 O(Q \log A)O(QlogA)，这里 QQ 为查询数组 queries 的长度，每一次查询时执行「路径压缩」的时间复杂度是 O(\log A)O(logA)。
空间复杂度：O(A)O(A)：创建字符与 id 的对应关系 hashMap 长度为 AA，并查集底层使用的两个数组 parent 和 weight 存储每个变量的连通分量信息，parent 和 weight 的长度均为 AA。

作者：LeetCode
链接：https://leetcode.cn/problems/evaluate-division/solution/399-chu-fa-qiu-zhi-nan-du-zhong-deng-286-w45d/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

https://leetcode.cn/problems/evaluate-division/solution/399-chu-fa-qiu-zhi-nan-du-zhong-deng-286-w45d/733897

20220720

547. 省份数量 - 力扣（LeetCode）

986. 区间列表的交集 - 力扣（LeetCode）

区间列表的交集 - 区间列表的交集 - 力扣（LeetCode）

「图解」优雅的双指针解法 | 986. 区间列表的交集 - 区间列表的交集 - 力扣（LeetCode）

我们称 b 为区间 [a, b] 的末端点。

在两个数组给定的所有区间中，假设拥有最小末端点的区间是 A[0]。（为了不失一般性，该区间出现在数组 A 中)

然后，

在数组 B 的区间中， A[0] 只可能与数组 B 中的至多一个区间相交。（如果 B 中存在两个区间均与 A[0] 相交，那么它们将共同包含 A[0] 的末端点，但是 B 中的区间应该是不相交的，所以存在矛盾）

作者：LeetCode
链接：https://leetcode.cn/problems/interval-list-intersections/solution/qu-jian-lie-biao-de-jiao-ji-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

20220722

购物车_牛客博客 (nowcoder.net)

定义状态转移数组dp[i][j]，表示前i个物品，背包重量为j的情况下能装的最大价值。

例如，$dp[3][4]=6$，表示用前3个物品装入重量为4的背包所能获得的最大价值为6，此时并不是3个物品全部装入，而是3个物品满足装入背包的条件下的最大价值。

考虑前三个物品

前i个物品装入容量为j的背包获得的最大价值，有两种可能，第i件商品不装。或者是装入第i件商品，装之后重量变为j。

20220725

动态规划（转换为 0-1 背包问题） - 一和零 - 力扣（LeetCode）

20220726

【宫水三叶】详解完全背包问题（附背包问题攻略） - 零钱兑换 II - 力扣（LeetCode）

我们求的是「取得特定价值所需要的最小物品个数」。

对于本题，我们求的是「取得特定价值的方案数量」。

被选物品之间不需要满足特定关系，只需要选择物品，以达到「全局最优」或者「特定状态」即可。

377. 组合总和 Ⅳ - 力扣（LeetCode）

选择方案中的不同的物品顺序代表不同方案。

二分

二分的重点在于仔细看题，缩减区间，下一轮搜索范围是啥，进而设置左右边界。

在做题的过程中，会遇到两个难点：1、取 mid 的时候，有些时候需要 +1，这是因为需要避免死循环；2、只把区间分成两个部分，这是因为：只有这样，退出循环的时候才有 left 与 right 重合，我们才敢说，找到了问题的答案。（这两个难点，在练习的过程中，会逐渐清晰，不用着急一下子搞懂，事实上并不难理解）。

链接：https://leetcode.cn/problems/search-insert-position/solution/te-bie-hao-yong-de-er-fen-cha-fa-fa-mo-ban-python-/

写成 while(left < right) ，退出循环的时候有 left == right 成立，好处是：不用判断应该返回 left 还是 right；
区间 [left..right] 划分只有以下两种情况：
分成 [left..mid] 和 [mid + 1..right]，分别对应 right = mid 和 left = mid + 1；
分成 [left..mid - 1] 和 [mid..right]，分别对应 right = mid - 1 和 left = mid，这种情况下。需要将 int mid = (left + right) / 2 改成 int mid = (left + right + 1) / 2，否则会出现死循环，这一点不用记，出现死循环的时候，把 left 和 right 的值打印出来看一下就很清楚了；

分成 [left..mid] 和 [mid + 1..right]，分别对应 right = mid 和 left = mid + 1；
分成 [left..mid - 1] 和 [mid..right]，分别对应 right = mid - 1 和 left = mid，

35. 搜索插入位置 - 力扣（LeetCode）

找第一个大于等于target的位置，

长度len可能也是答案。

mid小于target，mid和mid左侧一定不是答案。mid大于等于target，mid可能是答案。

上面的两点中，「情况 2」其实不用分析得那么细致， 因为只要「情况 1」的区间分析是正确的，「情况 2」一定是「情况 1」得到的区间的反面区间。

69. x 的平方根 - 力扣（LeetCode）

返回平方小于等于x的最后一个数字

假如mid*mid大于x，right = mid-1

20220727

20220729

航班预订统计 - 航班预订统计 - 力扣（LeetCode）

20220731

🥹 含泪总结周赛中的两道「图」问题 - 找到离给定两个节点最近的节点 - 力扣（LeetCode）

重建序列 - 重建序列 - 力扣（LeetCode）

能不能判断最短超序列里边谁前谁后。

1.table.get(key, [])

2.输入子序列，其实会很长。

【宫水三叶】一题双解 :「差分」&「线段树」（附区间求和目录） - 航班预订统计 - 力扣（LeetCode）

20220801

【宫水三叶】建图 + 拓扑排序 运用题 - 外星文字典 - 力扣（LeetCode）

https://leetcode.cn/problems/Jf1JuT/solution/by-ac_oier-4xmv/1590006

《剑指offer 2 面试题114》 书中算法C++实现 - 外星文字典 - 力扣（LeetCode）

685. 冗余连接 II:【并查集的应用】详解 - 冗余连接 II - 力扣（LeetCode）

20220803

非常好理解的动态规划，看完之后再也不怕了 - 分隔数组以得到最大和 - 力扣（LeetCode）

dp[i] 表示前i个元素分割为长度小于k的连续子数组，分隔变换后能够得到的元素最大和。

统计xy 和 yx 个数 - 交换字符使得字符串相同 - 力扣（LeetCode）

Java - 贪心算法详解 - 交换字符使得字符串相同 - 力扣（LeetCode）

20220804

【宫水三叶】简单二叉树遍历运用题 - 在二叉树中增加一行 - 力扣（LeetCode）

20220805

636. 函数的独占时间 - 力扣（LeetCode）

【宫水三叶】简单栈运用模拟题 - 函数的独占时间 - 力扣（LeetCode）

使用「栈」来模拟执行过程：当一个函数被调用（op = start）时，压入栈内，当函数调用完成（op = end）时，从栈顶弹出（此时栈顶元素必然是该结束函数的入栈记录），使用变量 cur 记录当前时间。

从前往后处理所有的 log[i]log[i]，根据 log[i]log[i] 是属于函数调用还是函数结束进行分情况讨论：

当 log[i]log[i] 为函数调用：此时从该函数的调用发起时间 ts 到上一次记录的当前时间，都是前一函数的执行时间，因此可以将 ts - cur 累加到栈帧中的前一函数。即若栈不为空，则将该时间累加到栈顶对应的函数上，然后将 log[i]log[i] 入栈，同时更新当前时间；

当 log[i]log[i] 为函数结束：此时栈顶元素必然是该函数的调用记录，此时 log[i]log[i] 的结束时间与上一次记录的当前时间的时长 ts - cur + 1，必然是该函数的执行时间，将其累加到当前函数中，并更新当前时间。

【函数的独占时间】栈模拟 - 函数的独占时间 - 力扣（LeetCode）

题目其实说得已经很明确了，使用 调用栈 来进行函数的运行调度，只有栈顶函数在运行，所以使用栈进行模拟即可。具体来说：在栈中存储函数的标识符

如果是 start, 需要计算保存之前正在运行函数(即栈顶函数的运行时间)，然后压栈
如果是 end, 栈顶肯定是当前函数的标识符，直接出栈然后计算函数的运行时间即可

48. 旋转图像 - 力扣（LeetCode）

理清底层思路，各种对称/旋转一网打尽 - 旋转图像 - 力扣（LeetCode）

221. 最大正方形 - 力扣（LeetCode）

1277. 统计全为 1 的正方形子矩阵 - 力扣（LeetCode）

20220808

49. 字母异位词分组 - 力扣（LeetCode）

2368. 受限条件下可到达节点的数目 - 力扣（LeetCode）

判断list里有没有某个字符，用 a in set更快。

2370. 最长理想子序列 - 力扣（LeetCode）

https://leetcode.cn/problems/longest-ideal-subsequence/comments/1691329

线性 DP + 空间优化（Python/Java/C++/Go） - 最长理想子序列 - 力扣（LeetCode）

定义 f[i][c]f[i][c] 表示 ss 的前 ii 个字母中的以 cc 结尾的理想字符串的最长长度。

20220810

761. 特殊的二进制序列 - 力扣（LeetCode）

转换为括号字符串，就很容易了 - 特殊的二进制序列 - 力扣（LeetCode）

  • 第一步，将字符串拆分成一段或几段 “不可拆分的有效的括号字符串”。

  • 第二步，将每一段 内部 的子串（也是 “有效的括号字符串”）分别重新排列成字典序最大的字符串（解决子问题）。1 1010 0，1 1100 0。

  • 第三步，由于 每一对相邻的段都可以交换，因此无限次交换相当于我们可以把各个段以 任意顺序 排列。我们要找到字典序最大的排列。
    这里有一个值得思考的地方：由于每一 “段” 必会以 “0” 结尾，因此只要将 “字典序最大” 的串放在第一位，“字典序次大” 的串放在第二位，…，就可以得到字典序最大的排列。（即将各个段按照字典序从大到小排序即可）。

640. 求解方程 - 力扣（LeetCode）

[Python/Java/TypeScript/Go] 模拟 - 求解方程 - 力扣（LeetCode）

求解方程【模拟】 - 求解方程 - 力扣（LeetCode）

我们根据题意进行模拟即可，设xSum表示合并同类项的x的系数，valSum表示合并数字的值。

  • 若字符是x，加到xSum上
  • 若字符是+或者-,改变符号位
  • 若字符是数字，则判断后边有没有跟x，有则加到xSum上，没有加到valSum上

20220824

剑指 Offer 59 - I. 滑动窗口的最大值 - 力扣（LeetCode）

单调队列

20220904

类型题：二分应用

437 · 书籍复印 - LintCode

把一个数组分成k段，每一段和的最大值最小, leetcode410.

(38条消息) 【Lintcode】437. Copy Books（配数学证明）_记录算法题解的博客-CSDN博客

动态规划、二分查找（Java） - 分割数组的最大值 - 力扣（LeetCode）

  • 我们需要找到一种拆分，使得这个最大值 val 的值是所有分成 m 段拆分里值最小的那个；具体怎么拆，题目不用我们求，只需要我们计算出 val 的值。
  • $dp[i][k]=max(dp[j][k−1],rangeSum(j+1,i))$

【宫水三叶】简单二分运用题 - 爱吃香蕉的珂珂 - 力扣（LeetCode）、

20220905

2251. 花期内花的数目 - 力扣（LeetCode）

https://leetcode.cn/problems/number-of-flowers-in-full-bloom/comments/1525484

2251. 花期内花的数目 - 力扣（LeetCode）节约空间的做法。

20220909

1143. 最长公共子序列 - 力扣（LeetCode）

20220911

919 · 会议室 II - LintCode

三种方法汇总「贪心 + 堆」「线段树」「差分数组」🔥🔥🔥 - 将区间分为最少组数 - 力扣（LeetCode）

堆

20220915

线段树详解「汇总级别整理 🔥🔥🔥」 - 最长递增子序列 II - 力扣（LeetCode）

线段树 python 实现 - r1-12king - 博客园 (cnblogs.com)

1
2
3
4
5
1 class TreeNode:
2     def __init__(self, left, right, mx):
3         self.left = left
4         self.right = right
5         self.mx = mx

(38条消息) python版线段树_icyday的博客-CSDN博客

(5条未读通知) 躲藏题目题解_牛客竞赛OJ (nowcoder.com)

115. 不同的子序列 - 力扣（LeetCode）

20220917

「代码随想录」带你学透DP子序列问题！392. 判断子序列【动态规划经典题目】详解 - 判断子序列 - 力扣（LeetCode）

$dp[i][j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]。$

s:abc, t: abcd

if (s[i - 1] == t[j - 1])
t中找到了一个字符在s中也出现了
if (s[i - 1] != t[j - 1])
相当于t要删除元素，继续匹配,相当于t里边的新字符没用上

1
2
3
if (s[i - 1] == t[j - 1])，那么dp[i][j] = dp[i - 1][j - 1] + 1;，因为找到了一个相同的字符，相同子序列长度自然要在dp[i-1][j-1]的基础上加1（如果不理解，在回看一下dp[i][j]的定义）

if (s[i - 1] != t[j - 1])，此时相当于t要删除元素，t如果把当前元素t[j - 1]删除，那么dp[i][j] 的数值就是 看s[i - 1]与 t[j - 2]的比较结果了，即：dp[i][j] = dp[i][j - 1];

作者：carlsun-2
链接：https://lems/is-subsequence/solution/dai-ma-sui-xiang-lu-dai-ni-xue-tou-dpzi-knntf/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

115. 不同的子序列 - 力扣（LeetCode）

一开始一直没理解为啥，用s[i-1]来匹配个数为dp[i-1][j-1]，不用s[i-1]来匹配个数为dp[i-1][j] 。后来才知道原来用s[i-1]来匹配时，s[i-1]与t[j-1]匹配了，即不需要考虑当前s子串和t子串的最后一位字母，所以只需要 dp[i-1][j-1]。感谢dalao的详细题解，附一份java版

20220919

贪心算法， 代码简洁 - 无重叠区间 - 力扣（LeetCode）

435. 无重叠区间 - 力扣（LeetCode）

简介：

贪心算法， 代码简洁 - 无重叠区间 - 力扣（LeetCode）

1049. 最后一块石头的重量 II - 力扣（LeetCode）

https://leetcode.cn/problems/last-stone-weight-ii/comments/977212

20220920

经典回溯算法：集合划分问题「重要更新 🔥🔥🔥」 - 划分为k个相等的子集 - 力扣（LeetCode）

初始条件

20220922

82. 删除排序链表中的重复元素 II - 力扣（LeetCode）

https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/comments/101023

20220928

剑指 Offer 19. 正则表达式匹配 - 力扣（LeetCode）

https://leetcode.cn/problems/zheng-ze-biao-da-shi-pi-pei-lcof/

20221001

127. 单词接龙 - 力扣（LeetCode）

【小魏】看不懂打我系列 面试题 17.22. 单词转换 - 单词转换 - 力扣（LeetCode）

题目要我们找 最短转换序列，提示我们需要使用 广度优先遍历。广度优先遍历就是用于找无权图的最短路径。

【单词接龙 II】图的BFS+DFS(Java) - 单词接龙 II - 力扣（LeetCode）

20221003

1801. 积压订单中的订单总数 - 力扣（LeetCode）

c++/python3 最大堆，最小堆，优先队列 模拟过程，分情况讨论 - 积压订单中的订单总数 - 力扣（LeetCode）

20221010

856. 括号的分数 - 力扣（LeetCode）

[Python3/Java/C++/Go] 一题一解：计数（附题单） - 括号的分数 - 力扣（LeetCode）

题目

https://mp.weixin.qq.com/mp/homepage?__biz=MzI4Njc4MzMwMw==&hid=1&sn=58bf8e995138b26984c05fd51f198196经典重点题目归纳

代码随想录 (programmercarl.com)可以看看题目分类

力扣 (leetcode-cn.com)

LeetCode 热题 HOT 100a

力扣 (leetcode-cn.com)

剑指 Offer（第 2 版）

「剑指 Offer」 - 学习计划 - 力扣（LeetCode）全球极客挚爱的技术成长平台 (leetcode-cn.com)

剑指 Offer（第 2 版）分类

C++ 总结了回溯问题类型 带你搞懂回溯算法(大量例题) - 子集 - 力扣（LeetCode）

力扣 (leetcode-cn.com)

LeetCode 精选 TOP 面试题

image-20211028152640610

「剑指 Offer」 - 学习计划 - 力扣（LeetCode）全球极客挚爱的技术成长平台 (leetcode-cn.com)

学习计划广场

学习计划 - 力扣（LeetCode）全球极客挚爱的技术成长平台 (leetcode-cn.com)

可以做单题

图论

递推-综合应用，图 - 力扣（LeetCode） (leetcode-cn.com)

Dijkstra 算法详解 - 概率最大的路径 - 力扣（LeetCode） (leetcode-cn.com)

CodeTop企业题库

论如何4个月高效刷满 500 题并形成长期记忆 - 力扣（LeetCode）

[回溯算法入门级详解 + 练习（持续更新） - 全排列 - 力扣（LeetCode）

数据库知识点题库 - 力扣（LeetCode）

(38条消息) leetcode HOT100总结_wang-jue的博客-CSDN博客

(38条消息) leetcode hot100 梳理_smallplum123的博客-CSDN博客_hot100 leetcode