E 是Easy N 是 Normal,也就是Medium,H 是 Hard
Array / String
- Merge Sorted Array E
设置答案表ans,设置两个指针i和j,表示当前所指的位置,一开始指针指向表头。比较两个指针所指元素大小,谁小谁先进ans表。如果有一个指针指到了表尾就不比了,直接把剩下没处理完的内容直接放进ans表。
- Remove Element E
太简单,略过。至于怎么使用O(1)的空间复杂度来进行操作。可以用双指针进行操作。i是表头,j是表尾,如果i表示的元素要被删除,就从j中取一个元素放到i对应的位置。(这样就被删掉了),如果不要被删除,那么让i+1就好。
- Remove Duplicates from Sorted Array E
这是有序数组,那么一切都好办了。规定一个双指针i和j都指向开头,如果这是重复元素,就移动j,如果不是重复元素,是新元素,那就先把j上的元素放到i处,然后i和j都移动(j是快指针,i是慢指针)
- Remove Duplicates from Sorted Array II N
这和上一题的区别就是只允许存在一次和两次的区别。改动也就是重复元素的判断。上一题是判断i和i-1是不是相等,这一题是i和i-2是不是相等。
- Majority Element E
可以使用哈希表,统计每个元素出现的次数,然后输出出现次数最多的元素。如果想省空间复杂度的话可以先排序,然后最中间的那个元素就是结果(因为)
- Rotate Array N
这一题可以使用数组翻转。比如说 1 2 3 4 5 6 7,移动k下,新数组的[0,k - 1]来源于尾部的k个元素。那么可以做一次翻转(把后面的k个元素放到前面),然后对[0,k - 1]和[k,n - 1]的元素进行调转。(把顺序调整回来)
- Best Time to Buy and Sell Stock E
不知道为什么现在就出现了dp,我们可以把这个状态记录在dp[i][j]。j=0的时候表示在第i天已经买入股票的收入最大值。j=1的时候就是在第i天卖出股票的收入最大值。
那么dp[i][0] = max(dp[i-1][0],-price[i])。dp[i][1] = max(dp[i-1][1],dp[i][0] + price[i])。初始值dp[0][0] = -price[0],dp[0][1] = 0。
- Best Time to Buy and Sell Stock II N
上面一题从只可以买一次编程可以买两次。那么dp的的第二维就是有4个状态。买了一个,买了一个卖了一个,买了两个卖了一个,买了两个卖了两个。
dp[i][0] = max(dp[i-1][0],-price[i])。dp[i][1] = max(dp[i-1][1],dp[i][0] + price[i])。dp[i][2] = max(dp[i-2][2],dp[i][1] - prices[i])。dp[i][3] = max(dp[i-1][3],dp[i][2] + price[i])。
- Jump Game N
这一题看题解似乎是可以用贪心。但我用倒推dp做的,dp[i]记录了可以到达最后结束位置的可能性。dp[最后一个位置]肯定为1,记录一个使dp[k]=1最小的k值,然后依次往后倒,如果nums[i] + i <= k的话就说明可以到达。dp[i] = 1,否则为0,看看dp[0]的取值就好。
- Jump Game II N
这一题相较于上一题多了一个记录最小步数的。那么这次就用dp[i]表示从0到这里最少几步。这里可以有这样的递推方程对于j属于[i,i+nums[i]],dp[j]=min(dp[j],dp[i]+1)
- H-Index N
对文章引用进行排序。h指的是什么,是h个index比h高的数,那就从0开始试,如果index[size - h - 1] > h,说明可以往上升。
- Insert Delete GetRandom O(1) N
O(1)的CURD,空间换时间,用一个额外的哈希表记录是否有重复元素。这个哈希表不记录元素的个数,记录元素在表中的索引。添加的时候在表中添加这个元素,哈希表记录index。删除k,如果k没有,就返回false,如果k有的话,那么找到index。表的index位置替换成表尾元素。删掉表尾元素更换哈希表。在O(1)时间内查询不说,太简单。
- Product of Array Except Self N
这里为什么不能计算出所有元素的积然后再除本元素呢,是因为可能本元素是0,所以可能有问题。所以可以进行一次前缀后缀积。s[i]记录从0一直积到i的值,[i]记录从最后积到i的值,后面就是s[i-1]*b[i+1](注意考虑一下边界)
- Gas Station N
先从0开始走,如果能绕一圈自然是好的,但是如果不能的话,在哪里走不动了,就在哪里的下一站试。为什么呢,比如说0->1->2,到2走不动了,那么从1出发从2出发也是不行的,只能试一下从3出发。这样可以减少搜索的次数。
- Candy H
分糖果,那么可以进行两次贪心。首先先从左往右走,如果i比i-1大,那么s[i] = s[i-1] + 1,如果小,s[i] = 1。然后从右往左走,如果i比i+1大,那么b[i] = b[i+1] + 1,如果小那么b[i] = 1。最后这个小孩分配的糖果数量是max(s[i],b[i])。首先这样可以保证题目的条件满足,如果是2 1 2的情况,那么就是1,如果是1 2 1的情况,那么就是max(左,右)。如果是3 2 1的情况,那么就以右边 + 1为准,右边+1怎么都比1大。所以这样做是可以保证对的。其次由于是贪心,我们可以保证分配的糖果数量是最少的。
- Trapping Rain Water H
维护一个单调栈,这里就是记录从[s[i],i]中的元素都满足单调性。(这里是单调递减)。这里说一下单调栈的维护,其实就是比较。如果元素比栈顶大,那么栈顶退出,一直到元素比栈顶小或者栈中没元素了。
如果栈中有元素退栈了,但是栈中元素还是不空,这是发生了什么呢?就是有水背围住了,这个时候可以记录水的数量了。这里套用题解就是:
1 | int currWidth = i - left - 1; |
作者:力扣官方题解
链接:https://leetcode.cn/problems/trapping-rain-water/solutions/692342/jie-yu-shui-by-leetcode-solution-tuvc/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
- Roman to Integer E
模拟即可。对字符串进行遍历。
- Integer to Roman N
贪心算法,先算有多少个1000,再算900,再算500,再算400,以此类推。然后做字符串的加运算即可,有多少个1000就加多少个’M’。
- Integer to Roman E
统计连续的非空格字符数。有一种优化方式是从后往前遍历字符串,遇到非空格字符开始计数,计数到遇到空格字符,即为答案。
- Longest Common Prefix E
找最长公共前缀。就遍历一下即可。比如说第一个单词的第一个字母是A,看看别的单词的第一个字母是不是A,是的话就把A放入答案中,以此类推,直到有差异或者到了一个单词的末尾。
- Reverse Words in a String N
这道题就是考验对字符串处理的基本功,首先把所有的单词提取出来,然后把单词逆序处理即可。提取出来的办法我想得比较笨,就是str += 非空格元素。遇到空格就代表单词处理完毕了,加入到一个单词表中。
- Zigzag Conversion N
数学题,首先先计算要用到的行数和列数。
1 | int route = numRows + (numRows > 1? numRows - 2:0); |
然后分配一下具体的位置。
1 | if(r < numRows) c[r][lie * p] = s[i]; |
其实就是数学题,建立字符串和Zigzag的映射。
- Find the Index of the First Occurrence in a String E
可以使用KMP算法进行匹配,但这里没有使用。就是使用朴素匹配的思路就可以。当然用KMP算法会更快。
- Text Justification
暂时略过。
Two Pointers
- Valid Palindrome E
设置两个指针i和j,i指向字符串头,j指向字符串尾。i和j相等的话就往内移。不相等返回false。如果i和j相遇了(i >= j),就可以返回true。
- Is Subsequence E
这个比字符串匹配要简单一点,设置两个指针i和j,i指向长串,j指向慢串。i和j对应的相等,则i后移j后移,否则就只有i后移。当i移动到最后j没移动到最后就返回false,否则返回true。
- Two Sum II - Input Array Is Sorted N
设置两个指针i和j,i指向表前,j指向表后。如果s[i]+s[j]大了,那就j–,如果小了i++,如果j比i小了,说明没结果。如果s[i]+s[j]刚刚好,说明结果找到了!
- Container With Most Water N
设置两个指针i和j,i指向表前,j指向表后。记录ans = min(height[i],height[j]) * (j - i)的最大值。如果s[i] < s[j],那就i++,否则j–,一直到j < i为止。(贪心+双指针)
- 3Sum N
基于第27题的题目,其实在第27题的基础上加了一个遍历。遍历1-n为i,然后在i+1~n之间做一次二数之和。
Sliding Window(滑动窗口【单调队列】)
- Minimum Size Subarray Sum N
首先先规定滑动窗口的范围[j,k]。假设滑动窗口内部的和是p。现在遍历这个数组,下标为i
(1)如果p + a[i] < target,让k = i
(2)p + a[i] = target,这是一个可能的结果,记录一下。
(3)p + a[i] > target。这时候要吐出滑动窗口的元素了。做p -= a[j++]一直到p + a[i] <= target为止。
对所有的可能的结果找最小值。
- Longest Substring Without Repeating Characters N
首先先规定滑动窗口的范围[j,k],然后构造一个Hash表来维护不重复性。遍历字符串,下标为i
(1)s[i]不重复,可以扩展k = i。记录一下当前滑动窗口长度。维护滑动窗口长度的最大值。
(2)s[i]重复,j++到不重复为止。
- Substring with Concatenation of All Words H
首先先规定滑动窗口的范围[j,k],然后构造一个Hash表来维护不重复性。首先我们直到滑动窗口的移动是按照单词表的元素为基准的。也就是说我们的初始滑动窗口是不同的,假设单词表元素的长度为k,那么从0,1,2…k-1开始都可以。所以说要遍历(0,k-1)。
之后和之前的滑动窗口操作一样。但是每次取字符串都是k个k个去取。
(1)不在单词表里。那么滑动窗口从[i+单词表长度,i+单词表长度]开始。
(2)在单词表里,而且在滑动窗口内没出现过(用std::map来维护)。k+=单词表长度。
(3)在单词表里,而且在滑动窗口内出现过,那就移动j一直到滑动窗口内部没出现过。
- Minimum Window Substring H
滑动窗口的范围[j,k],首先遍历一下要判别的串K。看看串内部字母的数量。构建一个hash表记录滑动窗口内部每个字母的数量。然后遍历字符串
(1)没达到要求,滑动窗口向右拓展。
(2)达到要求了,滑动窗口往左尽量收缩,尽量的含义是,收缩到i以致于滑动窗口[i+1,k]不满足要求而[i,k]满足要求,记录答案,维护答案的最小值。
矩阵(大部分就是做模拟)
- Valid Sudoku N
模拟,首先先把数独构造出来,然后按行按列去检查有无重复项(哈希表)
- Spiral Matrix N
这道题也是模拟。就是模拟矩阵旋转的过程。旋转可以分为四个部分,左下右上。做几次旋转可以通过min(m,n) + 1这个式子算出。左下右上每次怎么放元素的也可以算出。
- Rotate Image N
旋转矩阵,其实可以拆成四块去做的。左上到右上,右上到右下,右下到左下,左下到左上。每一次都是四个四个做的,而且可以写出映射。那么矩阵一块有多大呢,一块就是(n/2) * (n+1/2)大,四块的具体的划分也可以说出来。那么就做那么多次的循环交换就好了。
1 | int temp = matrix[i][j]; |
- Set Matrix Zeroes N
维护一个表b,记录哪些元素要设置为0。遍历一遍矩阵,对0元素,其所在行和所在列上所有位置,在表b中设置为1。矩阵遍历完了就统一设置为0。这样做是防止新生成出来的0会干扰操作。
- Game of Life N
暂时略过。
HashMap(哈希表)
- Ransom Note E
首先遍历magazine,记录magazine每个元素出现的次数,记录在哈希表中。然后遍历ransomNote,记录ransomNote每个元素出现的次数,出现比magazine多就判定false,没有的话就判定true。
- Isomorphic Strings E
将两个串进行字数统计,记录在哈希表1和2中,然后排序哈希表1和2,比较哈希表中元素数量是否相同。(当然也可以对哈希表进行再哈希)
- Word Pattern E
感觉这题并不像E的难度。将句子拆成若干个单词组,然后尝试构建一个字符串对字符的哈希映射,如果出现了哈希冲突,就是false,反之就是true。比如说dog cat cat dog和abba,就可以成功建立 dog-a cat-b的映射,dog cat cat dog和abbc,那么dog可以对a或者c,就产生了冲突,dog cat cat fog和abba,a可以对dog或者fog,也是出现了冲突。(查冲突的方法就是查哈希表的元素是否为空或者是否为不空)
- Valid Anagram E
构建两个字符串的哈希表,看哈希表是否完全相等。
- Group Anagrams N
这里本来是想让每组单词之间两两调用42题的API,结果TLE。上网看题解发现可以对字符串做sort,这样互为Anagrams的单词就是一样的。
- Two Sum E
这里本来可以使用暴力方式,搜索一遍就可以过。但是可以用哈希表。首先构建一个哈希表,然后。遍历数组,对于数组的元素x,希望能找到target-x的存在性,就搜索哈希表即可。
- Happy Number E
首先我们模拟上述的操作,然后我们用一个哈希表记录操作的结果的循环性,如果结果循环出现,我们知道时遇到了循环,就要返回false。遇到了1就返回true(我们知道如果不是快乐数就是一定遇到了循环,因为在做操作的时候,对于高位数,会单调递减,对于三位数以内的值,最多最多只能到243,所以一定会出现循环)只不过我们知道当遇到4的时候就代表遇到了循环,可以以此为着手进行优化。
- Contains Duplicate II E
在这里依然使用哈希,但是我哈希表的值记录上一次出现在数组的下标。然后每次出现就使用哈希表的值进行判断。
- Longest Consecutive Sequence N
做哈希然后找哈希表上连续元素的个数。
Intervals
- Summary Ranges E
遍历数组。记录连续的区间,记录的方法就是比较当前元素和之前元素的关系,如果满足+1,就不管,不满足+1,就意味着新的区间已经出现了。然后把记录的结果转化成字符串。
- Merge Intervals N
将区间按照左端递增的方式进行排序,然后每次比较都是比较上一个区间的右端和下一个区间的左端,观察可合并性。如果可合并,就更改右端的值作为一个新的区间。如果不可合并就重新构建新的待合并区间。(最重要的还是排序这一步)
- Insert Interval N
其实就是把新区间加进去,然后调用一次49。当然还可以直接遍历一遍所有区间,找到合适的位置进行合并。(找位置其实就是插入排序,因为左端的值是递增的,按照左端递增的规律进行插入就好)
- Minimum Number of Arrows to Burst Balloons N
按照右端递增进行排序。然后取一个p=第一个元素的右端。如果下一个元素的左端比上一个元素的右端要大,就说明不能在一起射了,就只能ans++,p=下一个元素的右端。如果不大,说明可以一起射,就可以不用做任何操作。
Stack
- Valid Parentheses E
非常典型的Stack问题,括号匹配,如果是左括号,入栈,右括号就和栈顶匹配。
- Simplify Path N
非常搞人心态的模拟题。首先用一个栈模拟文件夹路径。首先如果遇到了/,就代表该往下或者往上走一步了,如果是一个dot,就啥也不用做,两个dot就退栈,如果都不是,就往栈里push一个新的文件夹名字。其实本题的难dot在dot的处理上,有量个变量k和p(只有dot和不是只有dot)来记录上一级的名字里面是不是只有dot,如果不是只有dot就一律按照普通的名字来。如果遇到了..word.,在遇到第一个dot的时候k++,第二个也是k++,在遇到w的时候就把k=0,p=1。当p=1的时候,再遇到dot都不会k++了。而是保存起来。 反正是一个很折磨的模拟题。
- Min Stack N
维护最小值的栈。那就维护两个栈,一个是原始的栈,一个是到目前为止最小值的栈。在push的时候,就把要push的值push到原始栈中,要push的值和最小值栈的最小值push到最小值栈中。
- Evaluate Reverse Polish Notation N
暂时略过。
- Basic Calculator
力扣的链表数据结构定义:
1 | /** |
LinkList
- Linked List Cycle
双指针。设置一个快指针和慢指针。快指针一次性走两次,慢指针一次性走一次。如果有环,那么快慢指针会碰面,如果没有环,那么快指针马上会指向NULL。(当然要注意边界条件,因为当链表为空或者链表根本只有一个元素不可能有环。)
- Add Two Numbers
用链表模拟加,很折磨。用数组模拟竖式加法本来就很折磨,更何况链表。构建result表,首先先判断l1和l2指针是不是为空,如果为空的话就默认这是0,不为空的话该是什么是什么(后面移动l1和l2指针也是判断是否为空,为空的话就不用做操作)。然后两个指针对应内容和上一级进位相加。得到这一级加数和进位。加数插入进result表。以此类推,一直到l1和l2都是空。都是空了之后,在result表的队尾加上carry对应的节点。
这题和一般的模拟一样,首先要考虑两个加数不是同一个位的情况。然后还要考虑result表要构造头指针和尾指针。
- Merge Two Sorted Lists
构建一个res表,然后构建三个指针。i,j,k。i指向链表1,j指向链表2。k指向res表。i比j小,k后面补个i,i往后移。反之k后面补个j,j往后移,一直到i或者j到了尾部,把剩下那个没到尾部的那个表补到k后面
- Copy List with Random Pointer
深拷贝复制一个链表。那就构建一个老链表结点到新链表结点的映射,新链表构建完了需要完善random指针和next指针。所以之后遍历老链表。假设现在老链表遍历到了k,那么新链表为Hash(k),那么可以写出Hash(k)->next = Hash(k->next[老链表])[新链表],巧妙构建了新链表之间的联系。
- Reverse Linked List II N
详见62,62就是用了61的代码:
- Reverse Nodes in k-Group H
这一题就是折磨,狠狠地模拟了。这里Sukuna用了一个取巧的方法,用了一个Hash,把链表结点和结点所在的位置做了一次Hash。然后写了一个调换结点的代码。说白了就是对所有的next节点进行了狠狠地替换,代码非常长,算法很好懂,就是代码非常不好写:(注意一下首部的处理)
1 | void reverseBetween(ListNode* head, int left, int right) { |
然后以k个为一组进行替换。最后不足k个的就直接复制过去。
1 | ListNode* reverseKGroup(ListNode* head, int k) { |
- Remove Nth Node From End of List N
链表的删除。首先计算链表的长度l,然后删除掉l - n + 1上的节点。删除的办法在C语言课上讲过了。首先找到l - n + 2上的节点,然后让l - n + 2指向l - n即可(第l个默认是NULL)这样有个好处就是,不用对空指针进行处理。
但是如果要删除第一个的话,可以直接让head = head->next,就不能找到前一个了。
- Remove Duplicates from Sorted List II N
构造hash表,然后构造一个新表,把hash表里所有出现次数为1的数插到新表里。
- Rotate List N
首先要明确一点,rotate的次数 = k % 链表的长度。然后找到最后第k个元素,记作a,第k-1个元素为a-1。然后原链表的头head和尾tail。tail->next = head。a-1->next = NULL。(这里要考虑边界条件,如果k=0,就什么都不用做)
- Partition List N
构建两个表1和2,小于x的放入1,否则放入2.如果表1或者2是空表,就直接返回表2或者表1.如果不是的话表1末尾->next=表二开头。
- LRU Cache N
暂且不表。
Binariy Tree
1 | /** |
- Maximum Depth of Binary Tree E
求二叉树最大深度。那就是求左子树和右子树深度最大值+1。(如果是空树的话返回0)
- Same Tree E
先判空,如果两方有一个是空,返回false,如果两方都是空,返回true。如果都不是空,就看本节点值,左子树和右子树的一致性。(p->val == q->val) && (isSameTree(p->left,q->left)) && (isSameTree(p->right,q->right))
- Invert Binary Tree E
如果该树为空,那就什么都不用做。如果不空,那就交换左右子树,然后对左右子树递归调用交换函数。
- Symmetric Tree E
调用一下70,把右子树进行一次调转。然后看左子树和右子树是不是一个树(69)
- Construct Binary Tree from Preorder and Inorder Traversal N
给定前序排列和中序排列,构建一个树。非常经典的数据结构题。如果排列只有一个,那么就直接返回即可。如果有两个及以上,那首先要知道前序排列的第一个元素,在中序排列的位置,假设为i,那么中序遍历的[0,i-1]就是左子树[i+1,n]是右子树。然后递归构造就好。
- Construct Binary Tree from Inorder and Postorder Traversal N
还是经典,只不过从前序改成后序,还是一样的做法。只不过是后序排列的最后一个元素,在中序的位置。
- Populating Next Right Pointers in Each Node II N
这个可以首先构造一个层次的链表数组L。然后假设一个节点r的层数为n,那么L[n]->next = r,L[n] = r。这样子就可以巧妙地构造一个层次表了。
- Flatten Binary Tree to Linked List N
这个可以用一个很笨的方法,就是先前序遍历,把前序遍历的结果放在一个vector内部,然后遍历vector以分配左右子树指针的朝向。
- Path Sum E
递归计算。假设target=k,那就计算 左子树存在路径使路径和 == k - val || 右子树存在路径使路径和 == k - val。在递归的时候,有一个函数参数保留k - val的值。
- Sum Root to Leaf Numbers N
假设root的值是k,那么这个root对应的值可以这么表示,假设父亲传来了两个数,k和p(p是引用)【这相当于编译原理里面的综合变量和传递变量】,如果没有子树了,那么就让p += 10k + val。如果有子树,那么令k = 10k + val。(这样子可以把之前几层的信息传递给最后的叶节点,让叶节点做加法有依据)。可以这么理解:就是有儿子,奖池还在继续,没有儿子了,那么就把奖池兑现。
- Binary Tree Maximum Path Sum H
1 | class Solution { |
其实这个代码用得挺笨,我也不知道我搞了个isroot有啥用。不过在这里解释一下代码是怎么做的。我们假设路径是I型和V型。I型就是直勾勾往下走,V型是在某处拐了个弯。首先先记录一下左子树和右子树的I型路径的最大值,假设为l,r。那么算上本路径的I型路径最大值是$max(l,r)+val$。
那么在考虑V型路径(V型路径就是左右子树两部分构成的I型路径+自己,这样可以组成一个V型路径):if(res1 + root->val + res2 > maxs) maxs = res1 + root->val + res2;
那么维护一个最大值来记录答案。
- Binary Search Tree Iterator N
写一个基于二叉树的迭代器。这个非常简单,把二叉树做一次搜索,搜索结果放到stack里。
- Count Complete Tree Nodes E
左子树节点数 + 右子树节点数 + 1
- Lowest Common Ancestor of a Binary Tree
最近公共祖先(LCA)。首先维护一个dfs(k),这个值代表k内部是否存在p和q(我们找公共祖先的节点)。
如果左儿子的dfs和右儿子的dfs都是true,就说明本节点是一个公共祖先。或者本节点就是p或者q,然后左儿子的dfs和右儿子的dfs有一个是true,那也可以说明本节点是一个公共祖先。
Binariy Tree BFS
- Binary Tree Right Side View N
到了二叉树的层次遍历了。其实还是可以和之前一样,构造一个层次表L,然后做一次dfs(k,n)【代表第k个元素再第n层】然后令L[n] = k即可。
- Average of Levels in Binary Tree E
计算每一层的平均值。dfs一下,计算每一层的总和和结点数。除一下就好。
- Binary Tree Level Order Traversal
其实还是可以和之前一样,构造一个层次表L,然后做一次dfs(k,n)【代表第k个元素再第n层】然后令L[n].push_back(k)即可。当然还可以用队列模拟层次遍历(广度优先搜索),这样做不仅要维护一个搜索队列,还要维护一个搜索队列对应的层次队列。
1 | class Solution { |
- Binary Tree Zigzag Level Order Traversal N
暂不讨论
BST
- Minimum Absolute Difference in BST E
BST的前序遍历是按照升序排序的。那就先前序遍历,存一下遍历的结果,然后遍历比较即可。
- Kth Smallest Element in a BST N
第K小元素,那就还是存前序遍历的结果,然后取第k个元素就好。
- Validate Binary Search Tree N
验证BST的性质,存前序遍历的结果,看是不是前面的比后面的小。
Graph
- Number of Islands N
求连通分量的题目。首先找到一个1,把所有和这个连通分量一起的1全部改成0(这需要上下左右搜索,搜索的时候要注意边界条件)。再继续找1,以此循环往复。然后答案就是循环往复的次数。
- Surrounded Regions N
这里是将被围住的O变成X,那么标记和边界的O相同连通分量的O,没被标记的O就说明被围住了,变成X。
- Clone Graph N
深拷贝一个图。做一个老结点到新节点的Hash。然后对图做一次dfs。假设dfs(k),那么先查询Hash(k)存在否,不存在的话赋新值,对k每一个链接的节点,做一次dfs。然后把dfs的结果加入到链接表中。如果存在,就什么也不做。最后直接返回Hash(k)。其实还是和之前链表深拷贝一样,做一个老结点到新节点的Hash。
- Evaluate Division N
暂时不表
- Course Schedule N
建图。节点是课程号,边是上x课之前要上y课。这里使用邻接表。用E[x]表示所有y->x。这样很好计算入度了,那就是E[x].length。取出一个入度为0的元素,从图中删掉,更新一下邻接表。如果找不到入度为0的元素,但是还是有元素存在,说明有环,返回false。所有元素都可以被处理,返回true。
- Course Schedule II N
和之前一样,只不过把每一个入度为0的元素从图中删除的顺序记录下来而已。
Graph BFS
- Snakes and Ladders N
暂且不表
- Minimum Genetic Mutation
建图,顶点是可能出现的基因序列。边x->y,代表x可以变到y。建图之后然后求步数。求步数的方法可以使用bfs。构建一个结点队列和结点对应的步数队列,做dfs。把初始结点和0加入队列中做搜索,搜索到了返回答案,搜索不到(队列空了)就返回-1。
1 | class Solution { |
- Word Ladder
和96一样的bfs。暂且不表。
Trie(字典树)
- Implement Trie (Prefix Tree)
字典树就是前缀树,通过查前缀来判断是不是有。那就构建下面的26叉树。
1 | class TrieNode { |
比如说插入了单词cat,那么从字典树头开始在头的list[3]建立一个新的结点,c=’c’,然后再在这个结点的list[1]建立一个新的结点,c=’a’。最后在这个新的结点的list[‘t’-‘a’]建立一个新的结点,标记end=true,就是说有一个单词在这里结束了。
然后查cat的存在性就是按照上面的逻辑去查。如果走到某一步节点为空,说明肯定不对,如果走完了前缀存在。(如果end=true,说明这个单词也存在)这就是字典树,一个26叉树,树中有一个end标记代表有一个完整的单词的存在。
- Design Add and Search Words Data Structure N
是98的字典树的应用。
- Word Search II H
暂且不表。
Backtracking(回溯,其实也是一种搜索)
- Letter Combinations of a Phone Number N
构建dfs(stage,target,str)。如果stage == target,说明结束了,可以写入到res数组。如果是stage < target,说明还要继续往下搜索。那么str += 所有有可出现的字母,然后搜索k次 dfs(stage+1,target,str’)(k=所有可能出现的字母数量)
- Combination N
还是构建dfs(cur,n,k,temp)cur是当前所选的位置,n是个数,k是组合的个数。如果temp.size() == k,那么temp是一个正确的答案,return。然后在考虑选择cur和不选择cur,两个问题上做搜索。一个是temp.push(cur)之后在做dfs(cur+1,n,k,temp),做完这一部分搜索回溯之后 ,然后temp.pop()在做dfs(cur+1,n,k,temp)。
这里涉及到n的问题,这里就要对不满足n的要求的做一次剪枝。如果当前temp.size()+n-cur+1 < k,也就是说剩下的所有元素全放进去都不够k个的,那就趁早结束,不做了。
- Permutations N
涉及选不选的问题。还是构建dfs(p,n,temp,tag),用tag数组标记访问的情况。如果p == n,说明搜索到了终点。如果p < n,那么就在把所有tag=0的元素放入搜索中。首先找一个tag=0的数据,然后令tag=1,temp加入这个数,做dfs(p+1,n,temp,tag),结束搜索,也就是回溯后tag=0,temp丢出来。
- Combination Sum N
还是搜索。dfs(now,target,index)。搜索是对数组的每一项进行选取(dfs(now.push(x),target-x,index+1))和不选取(dfs(now,target,index+1))的搜索。搜索到的话就是target=0。
然后可以进行剪枝,就是index = nums.size()的话,就没必要继续做了,还有target<0,也没必要继续做了。
- N-Queens II H
太经典了,暂且不表。
- Generate Parentheses N
还是搜索,dfs(l,r,str,n)。对l和r构成的空间组进行搜索,要么加一个(,要么加一个)。dfs(l+1,r,str+’(‘),dfs(l,r+1,str+’)’)。搜索到了就是l=r=n。
还可以进行剪枝。如果l > n,r > n,l > r,都是不可以的。
- Word Search N
找存不存在word。dfs(pos,l,n)。上下左右搜索没有被搜索过的位置。
1 | class Solution { |
这样子会超时,要加一个hash的判断。比如说单词出现了N,但是matrix里一个N都没有,就可以直接剪枝了。
Divide & Conquer(分治)
- Convert Sorted Array to Binary Search Tree E
有序数组转化成BST。那就做分治。设置一个constructor,输入一个有序数组返回一个BST。那就c[0,n] = {val = c[n / 2],left = c[0, n / 2 - 1],right = [n / 2 + 1,n]}
- Sort List N
为链表排序。那就先用快慢指针找到链表的中间,然后做一次分支排序。l1 = sort(head),l2 = sort(slow).l = merge(l1,l2)。merge的办法是构建一个新的链表,方法参考题59。
- Construct Quad Tree N
暂且不表
- Merge k Sorted Lists H
假设有k个list。(力扣的测试集很弱,你按照顺序merge k次也可以过)
可以只用merge logk 级的次数。就是做分治。把merge k次的任务分解成。merge[0,k/2]和merge[k/2+1,k]两个子问题+对于子问题的结果进行一次merge。
Kadane’s Algorithm
- Maximum Subarray N
动态规划。dp[n] = max[a[n],dp[n-1] + a[n]] 要么接着拿,要么重开。
- Maximum Sum Circular Subarray N
动态规划,正常操作:dp[n] = max[a[n],dp[n-1] + a[n]]。现在有不涉及到循环的一个最大值max(dp[n])
现在考虑涉及到循环的最大值。固定最右边的元素,找到左边的元素。首先记最大前缀和l[k] = max(l[k-1],l1+l2+…lk)
假设右边的元素选了k个。那么左边的元素是n-k个,假设dp1[k] = (ln+ln-1+…l_k + l[n-k])
那么答案是max(max(dp[n]),max(dp1[n]))
Binary Search(二分搜索)
- Search Insert Position E
二分搜索。b(0,n-1,target). if a[mid] < target,l = mid + 1,ans = mid. else r = mid - 1.
- Search a 2D Matrix N
把矩阵展开成向量形式进行二分搜索。
- Find Peak Element N
如果mid比mid+1位置的元素小,说明答案很有可能是在右边。反之,说明答案很有可能在左边。然后以此为逻辑二分查找即可。
- Search in Rotated Sorted Array N
二分查找,但是这个查找相较于其他查找不同的是,数组分成两部分[A][B]。如果nums[mid] >= nums[0]。就说明mid在A区。如果target >= nums[0] 并且 target < nums[mid]。就说明target在A区mid左侧。否则target在A区mid右侧或者B区。
如果mid在B区。那么需要保证target > nums[mid]并且target <= nums[n-1]才能保证target在B区mid右侧。
- Find First and Last Position of Element in Sorted Array N
先二分查找,找到一个位置k,然后再往左往右遍历。
- Find Minimum in Rotated Sorted Array N
在这样的旋转表里找最小值。还是一样分成两部分[A][B],我们找B区第一个。如果nums[mid] < nums[r],则说明mid在B区。那就应该在左边找。那就令r = mid(因为mid可能是B区第一个)。的否则l = mid + 1.
- Median of Two Sorted Arrays H
想不到特别好的办法,我这里用的是朴素思考。
Heap(堆)
堆是一种有序队列。在C++的STL里有一个数据结构满足堆的要求,这里不需要我们搓轮子了。(下面叫优先队列)
1 | /* |
- Kth Largest Element in an Array N
放进所有元素,pop K-1个元素,取队列的top
- IPO H
这一题就是贪心。因为确保了最小投入资本capital是递增的。所以可以先找到所有满足的最小资本数 <= 持有资本数的项目。然后按照净利润递减的顺序放入优先队列里,每一次取出优先队列的最大值作为净利润,更新持有资本 = 之前持有资本 + 净利润。
- Find K Pairs with Smallest Sums
找到K个最小的pair。下面给一个使用这个STL,自定义比较函数的例子:
1 | struct lis { |
- Find Median from Data Stream H
找中位数。那就构建一个递增的优先队列和一个递减的优先队列。这两个优先队列分别记录大于中位数的数和小于中位数的数。还要保证小于中位数的数量和大于中位数的数量差不多一致。
Bit Manipulation(位运算)
- Add Binary E
位运算没有任何算法,就是纯模拟。
1 | class Solution { |
- Reverse Bits E
先转化成二进制,在reverse一下。
1 | class Solution { |
- Number of 1 Bits E
一直÷2,然后找÷2的余数为1的次数。
1 | class Solution { |
- Single Number E
根据a ^ a = 0的定律。对所有数异或在一起。剩下的那个数就是唯一一个。
- Single Number II N
这个比较搞。可以计算每一位出现1的次数。如果这一位出现1的次数 mod 3不为0,说明只出现1次的那个元素这一位为1.(看力扣题解好像可以用状态机来表示,感觉很酷)
- Bitwise AND of Numbers Range N
脑筋急转弯。对于按位与,我们知道,与里面出现一次0,那最终的答案就一定是0了。所以我们就可以推出,答案是m和n的二进制形态的公共前缀。
Math
- Palindrome Number E
回文数字。如果是负数就一定是错的。如果是正数的话可以构造逆数字,看看逆数字是不是和正数字一样。假设x的最后一位是k,那么令逆数字 = 逆数字 * 10 + k。
- Plus One E
模拟加。这里需要注意万一全部为9的情况。
- Factorial Trailing Zeroes N
0的个数,大家知道0 是由 2 和 5构成的。2明显很充裕,那就是看项目中5因数的个数。(25算两个,125算三个,625算四个)
- Sqrt(x) E
1 | class Solution { |
- Pow(x, n) N
快速幂算法。这里直接搬题解的。基于x^n + x^n = x^{2n}的道理快速算出来
1 | class Solution { |
- Max Points on a Line H
暂且不表
1D DP(一维动态规划)
动态规划就需要把dp递推方程给出来。给出dp递推方程就好办了。
- Climbing Stairs E
dp[n] = dp[n-1] + dp[n-2] dp[1] = 1,dp[2] = 2
- House Robber N
对于第n个要么偷,要么不偷(那就算上第n-1个)。可以写出
dp[n] = max(dp[n-2]+a[n],dp[n-1])
dp[1] = a[1]
dp[2] = max(a[1],a[2])
- Word Break N
dp[0] = true. 如果有个单词,长度为k,单词的最后一位刚好到n处,那么dp[n] = dp[n-k]。(这个的做法就是遍历n,然后从n往后推1,2,3….,k个字母,看构不构成单词,如果一个都构成不了,那就是false)
- Coin Change N
首先令dp[i] = 114514。那么dp[i] = min(dp[i],dp[i-coin[i]]+1)
- Longest Increasing Subsequence N
dp[0] = 1. 对于所有a[n] > a[k] dp[n] = max(dp[n],dp[k] + 1),然后找到最大的dp
对于dp,其递推方程的数据来源可以是一个数据(之前一个,之前两个);也可以一组数据中最大的或者是最小的。
多维DP
- Triangle N
dp[0][0] = a[0][0]
dp[i][0] = dp[i-1][0] + a[i][0]
dp[i][i] = dp[i-1][i-1] + a[i][i]
dp[i][k] = min(dp[i-1][k-1],dp[i-1][k]) + a[i][k]
- Minimum Path Sum N
dp[0][0] = a[0][0]
dp[i][0] = a[i][0] + dp[i-1][0]
dp[0][i] = a[0][i] + dp[0][i-1]
dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + a[i][j]
- Unique Paths II N
dp[0][0] = 1
dp[i][0] = 有阻碍?0 : (上一个有无阻碍?0:dp[i-1][0])
dp[0][i] = 有阻碍?0 : (左一个有无阻碍?0:dp[0][i-1])
dp[i][j] = 有阻碍?0 : (上一个有无阻碍?0:dp[i-1][j]) + (左一个有无阻碍?0:dp[i][j-1])
- Longest Palindromic Substring N
暂时不表
- Interleaving String N
首先看两个字符串的长度,长度不等是不可能成立的。
dp[0][0] = T
dp[i][j] = (dp[i-1][j] & s1[i-1] = s3[i+j-1]) | (dp[i][j-1] & s2[j-1] = s3[i+j-1])
解释:dp[i][j]解释了s3[i+j-1]可以被s1[0…i-1]和s2[0…j-1]构造。
- Edit Distance N
D[i][j]=min(D[i][j−1]+1,D[i−1][j]+1,D[i−1][j−1])=1+min(D[i][j−1],D[i−1][j],D[i−1][j−1]−1)
D[i][j]=1+min(D[i][j−1],D[i−1][j],D[i−1][j−1])
解释:D[i][j]是A[0..i]到B[0…j]的编辑距离。
- Best Time to Buy and Sell Stock III H
1 | p[0] = -prices[0]; // buy once |
- Best Time to Buy and Sell Stock IV H
从2次到k次,很快能能找到关系,从4个状态到2k个状态
1 | for(int i = 1;i <= k;i++){ |
- Maximal Square
dp(i,j)=min(dp(i−1,j),dp(i−1,j−1),dp(i,j−1))+1(dp为为1的边长)
这里我做了个很复杂的写法,贴在这里算了
1 | class Solution { |