516.最长回文子序列（dp）
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
1 2 3 输入：s = "bbbab" 输出：4 解释：一个可能的最长回文子序列为 "bbbb" 。
题解
用 dp[i][j] 表示字符串 s 的下标范围[i,j] 内的最长回文子序列的长度。假设字符串 s的长度为 n，则只有当0<=i<=j<n时,才会有dp[i][j]>0，否则dp[i][j]=0。
由于任何长度为 1 的子序列都是回文子序列，因此动态规划的边界情况是，对任意 0<=i<n，都有dp[i][i]=1。
当 i<j 时，计算 dp[i][j] 需要分别考虑 s[i] 和s[j] 相等和不相等的情况：
如果 s[i] = s[j]，则首先得到 s 的下标范围 [i+1,j−1] 内的最长回文子序列，然后在该子序列的首尾分别添加 s[i] 和s[j]，即可得到 s 的下标范围[i,j] 内的最长回文子序列，因此dp[i][j]=dp[i+1][j−1]+2；
如果s[i] !=s[j]，则 s[i] 和 s[j] 不可能同时作为同一个回文子序列的首尾，因此dp[i][j]=max(dp[i+1][j],dp[i][j−1])。
由于状态转移方程都是从长度较短的子序列向长度较长的子序列转移，因此需要注意动态规划的循环顺序。
最终得到 dp[0][n−1] 即为字符串 s 的最长回文子序列的长度。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 var longestPalindromeSubseq = function (s ) { const n = s.length ; const dp = new Array (n).fill (0 ).map (() => new Array (n).fill (0 )); for (let i = n - 1 ; i >= 0 ; i--) { dp[i][i] = 1 ; const c1 = s[i]; for (let j = i + 1 ; j < n; j++) { const c2 = s[j]; if (c1 === c2) { dp[i][j] = dp[i + 1 ][j - 1 ] + 2 ; } else { dp[i][j] = Math .max (dp[i + 1 ][j], dp[i][j - 1 ]); } } } return dp[0 ][n - 1 ]; };
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 int longestPalindromeSubseq (char * s) { int n = strlen (s); int dp[n][n]; memset (dp, 0 , sizeof (dp)); for (int i = n - 1 ; i >= 0 ; i--) { dp[i][i] = 1 ; char c1 = s[i]; for (int j = i + 1 ; j < n; j++) { char c2 = s[j]; if (c1 == c2) { dp[i][j] = dp[i + 1 ][j - 1 ] + 2 ; } else { dp[i][j] = fmax(dp[i + 1 ][j], dp[i][j - 1 ]); } } } return dp[0 ][n - 1 ]; }
1143.最长公共子序列（dp）
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列 的长度。如果不存在公共子序列 ，返回 0 。
一个字符串的子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的公共子序列是这两个字符串所共同拥有的子序列。
状态转移方程为 ：
当text1[i−1]==text2[j−1]: dp[i][j]=dp[i−1][j−1]+1;
当text1[i−1]!=text2[j−1]: dp[i][j]=max(dp[i−1][j],dp[i][j−1]);
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 int longestCommonSubsequence (char * text1, char * text2) { int n1 = strlen (text1); int n2 = strlen (text2); int dp[n1+1 ][n2+1 ]; memset (dp,0 ,sizeof (dp)); for (int i=1 ; i<=n1; i++){ for (int j=1 ; j<=n2; j++){ if (text1[i-1 ]==text2[j-1 ]){ dp[i][j]=dp[i-1 ][j-1 ]+1 ; } else { dp[i][j]=fmax(dp[i-1 ][j],dp[i][j-1 ]); } } } return dp[n1][n2]; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 var longestCommonSubsequence = function (text1, text2 ) { const m = text1.length , n = text2.length ; const dp = new Array (m + 1 ).fill (0 ).map (() => new Array (n + 1 ).fill (0 )); for (let i = 1 ; i <= m; i++) { const c1 = text1[i - 1 ]; for (let j = 1 ; j <= n; j++) { const c2 = text2[j - 1 ]; if (c1 === c2) { dp[i][j] = dp[i - 1 ][j - 1 ] + 1 ; } else { dp[i][j] = Math .max (dp[i - 1 ][j], dp[i][j - 1 ]); } } } return dp[m][n]; };
1312.让字符串成为回文串的最少插入次数（dp）
是前两个题的变种，有两种解法
求字符串与逆序串的最长公共子序列s，然后用n-s即可
该题的状态转移方程如下：
1 2 3 4 5 if (s[i] == s[j]) { dp[i][j] = dp[i + 1][j - 1] + 2; } else { dp[i][j] = fmax(dp[i + 1][j], dp[i][j - 1]); }
405. 数字转换为十六进制数（位运算）
给定一个整数，编写一个算法将这个数转换为十六进制数。对于负整数，我们通常使用 补码运算 方法。
注意:
十六进制中所有字母(a-f)都必须是小写。
十六进制字符串中不能包含多余的前导零。如果要转化的数为0，那么以单个字符’0’来表示；对于其他情况，十六进制字符串中的第一个字符将不会是0字符。
给定的数确保在32位有符号整数范围内。
不能使用任何由库提供的将数字直接转换或格式化为十六进制的方法。
C语言动态分配
malloc函数。其原型void *malloc(unsigned int num_bytes)；
calloc函数，其原型void *calloc(size_t n, size_t size)；
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 //主要是通过与操作来实现 char * toHex(int num){ char c[16]={'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f'}; char * ans; ans=(char *)malloc(sizeof(char)*9); for(int i=7;i>=0;--i){ ans[i]=c[num&0xF];//每位16进制 num=num>>4; } ans[8]='\0'; while(ans[0]=='0'&&*(ans+1)!='\0'){//剔除前缀0 ans=ans+1;//指针右移 } return ans; }
200.岛屿数量 （DFS）
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
题解
一共三种方法，DFS,BFS和并查集，此处只给出DFS的方法
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 /* *dfs:将数组grid中(i,j)元素至0 char ** grid：目标数组 int i：需要至0的位置 int j: 需要至0的位置 int m：数组行数 int n：数组列数 返回值：无 */ void dfs(char ** grid, int i, int j, int m, int n) { if(i < 0 || i >= m || j < 0 || j >= n) { return; } if(grid[i][j] == '1') { grid[i][j] = '0'; } else { return; } dfs(grid, i+1, j, m, n); dfs(grid, i-1, j, m, n); dfs(grid, i, j+1, m, n); dfs(grid, i, j-1, m, n); return; } /* *numIslands：计算grid中存在相邻为1的个数 char** grid：数组 int gridSize:数组行数 int* gridColSize:数组列数 返回值：相邻为1的个数 */ int numIslands(char** grid, int gridSize, int* gridColSize){ int m = gridSize; int n = gridColSize[0]; int sum = 0; int i,j; for(i = 0; i < m; i++) { for(j = 0; j < n; j++) { if(grid[i][j] == '1') { sum++; dfs(grid, i, j, m, n); } } } return sum; }
695.岛屿的最大面积 （DFS）
给你一个大小为 m x n 的二进制矩阵 grid 。
岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
岛屿的面积是岛上值为 1 的单元格的数目。
计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。
题解
在200的基础上，在DFS中计算面积即可
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 int dfs(int ** grid, int i, int j, int m, int n) { if(i < 0 || i >= m || j < 0 || j >= n) { return 0; } if(grid[i][j] == 1) { grid[i][j] = 0; } else { return 0; } return 1+dfs(grid, i+1, j, m, n)+dfs(grid, i-1, j, m, n)+dfs(grid, i, j+1, m, n)+dfs(grid, i, j-1, m, n); } int maxAreaOfIsland(int** grid, int gridSize, int* gridColSize){ int m = gridSize; int n = gridColSize[0]; int max = 0; int i,j; int count = 0; for(i = 0; i < m; i++) { for(j = 0; j < n; j++) { if(grid[i][j] == 1) { count = dfs(grid, i, j, m, n); max = fmax(max,count); } } } return max; }
3.无重复字符的最长子串 （hash+滑动窗口）
给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。
滑动窗口解决
需要借助hash结构存储重复元素
此处使用数组模拟hash表
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 int lengthOfLongestSubstring(char * s){ int sLen = strlen(s); //获取字符串长度 int left=0, right = 0; //左右指针 int res=0, cnt=0; //结果和计数 int tmp[128] = {0}; //以128位数组记录字串中的字符是否已经出现 while(right < sLen) { //循环条件为右指针小于字符串长度 if(tmp[s[right]] == 0) { //当右指针指向的字符没出现在子串中时 tmp[ s[right] ]=1; //使用tmp数组记录右指针指向的字符在ascii码中对应的位置 right++; //右指针右移 cnt++; //计数加1 res = res > cnt ? res : cnt; //记录结果 } else { //当右指针指向的字符出现在子串中时 tmp[ s[left] ] = 0; //左指针指向字符的ascii码不再出现在tmp数组中 left++; //左指针右移 cnt--; //计数减1 } } return res; //返回最终无重复字串长度 }
javascript解法(使用set)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 var lengthOfLongestSubstring = function(s) { // 哈希集合，记录每个字符是否出现过 const occ = new Set(); const n = s.length; // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动 let rk = -1, ans = 0; for (let i = 0; i < n; ++i) { if (i != 0) { // 左指针向右移动一格，移除一个字符 occ.delete(s.charAt(i - 1)); } while (rk + 1 < n && !occ.has(s.charAt(rk + 1))) { // 不断地移动右指针 occ.add(s.charAt(rk + 1)); ++rk; } // 第 i 到 rk 个字符是一个极长的无重复字符子串 ans = Math.max(ans, rk - i + 1); } return ans; };
5.最长回文子串 (dp)
给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
动态规划
状态转移方程：
也就是说，只有s[i+1:j−1] 是回文串，并且 s 的第 i 和 j 个字母相同时，s[i:j]才会是回文串。
动态规划中的边界条件，即子串的长度为 1 或 2。对于长度为 1 的子串，它显然是个回文串；对于长度为 2 的子串，只要它的两个字母相同，它就是一个回文串。因此我们就可以写出动态规划的边界条件：
P(i,i)=true
P(i,i+1)=(Si==Si+1)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 //C char * longestPalindrome(char * s){ int n = strlen(s); if(n<2){ return s; } int maxLen = 1; int begin = 0; // dp[i][j] 表示 s[i..j] 是否是回文串 int dp[n][n]; memset(dp,0,sizeof(dp)); for (int i = 0; i < n; i++) { dp[i][i] = 1; } for (int j=1 ; j < n; j++) { // 左下角先填 for (int i = 0; i < j; i++) { if (s[i] != s[j]) { dp[i][j] = false; } else { if (j - i < 3) { dp[i][j] = true; } else { dp[i][j] = dp[i + 1][j - 1]; } } // 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置 if (dp[i][j] && j - i + 1 > maxLen) { maxLen = j - i + 1; begin = i; } } } char *ans; ans=(char *)malloc(sizeof(char)*(maxLen+1)); for(int i=0; i<maxLen; i++){ ans[i]=s[begin+i]; } ans[maxLen]='\0'; return ans; }
9.回文数
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
例如，121 是回文，而 123 不是。
将数字本身反转，然后将反转后的数字与原始数字进行比较，如果它们是相同的，那么这个数字就是回文。
为了避免数字反转可能导致的溢出问题，为什么不考虑只反转 int 数字的一半？毕竟，如果该数字是回文，其后半部分反转后应该与原始数字的前半部分相同。
题解
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: bool isPalindrome(int x) { // 特殊情况： // 如上所述，当 x < 0 时，x 不是回文数。 // 同样地，如果数字的最后一位是 0，为了使该数字为回文， // 则其第一位数字也应该是 0 // 只有 0 满足这一属性 if (x < 0 || (x % 10 == 0 && x != 0)) { return false; } int revertedNumber = 0; while (x > revertedNumber) { revertedNumber = revertedNumber * 10 + x % 10; x /= 10; } // 当数字长度为奇数时，我们可以通过 revertedNumber/10 去除处于中位的数字。 // 例如，当输入为 12321 时，在 while 循环的末尾我们可以得到 x = 12，revertedNumber = 123， // 由于处于中位的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。 return x == revertedNumber || x == revertedNumber / 10; } };
7.整数反转
给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围，就返回 0。
1 2 3 4 5 6 7 8 9 10 11 12 int reverse(int x){ int rev = 0; while (x != 0) { if (rev < INT_MIN / 10 || rev > INT_MAX / 10) { return 0; } int digit = x % 10; x /= 10; rev = rev * 10 + digit; } return rev; }
15.三数之和（快排+双指针）
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意 ：答案中不可以包含重复的三元组。
使用快排+双指针
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 int cmp(const void *a,const void *b) { return *(int*)a - *(int*)b; } int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) { *returnSize = 0; if(numsSize < 3) return NULL; qsort(nums,numsSize,sizeof(int),cmp); int **ans = (int **)malloc(sizeof(int *) * numsSize *numsSize); *returnColumnSizes = (int *)malloc(sizeof(int) * numsSize * numsSize); int i,j,k,sum; int indexLeft = 0; int indexMiddle = 0; int indexRight = 0; //快排过后，使用三指针 遍历 //左边遍历到倒数第三位即可 for(indexLeft = 0; indexLeft< numsSize - 2; indexLeft++) { if(nums[indexLeft] > 0) { //因为是快排的结果，所以如果出现大零的 //后面的值都是大于0的 return ans; } //如果值相同 则不需要遍历 if(indexLeft > 0 && nums[indexLeft] == nums[indexLeft-1]) continue; indexMiddle = indexLeft + 1; indexRight = numsSize - 1; //双指遍历 找到所有的可能 while(indexMiddle < indexRight) { sum = nums[indexLeft] + nums[indexMiddle] + nums[indexRight]; if(sum == 0) { ans[*returnSize] = (int*)malloc(sizeof(int)*3); (*returnColumnSizes)[*returnSize] = 3; ans[*returnSize][0] = nums[indexLeft]; ans[*returnSize][1] = nums[indexMiddle]; ans[*returnSize][2] = nums[indexRight]; *returnSize += 1; //过滤相等的值 while(indexMiddle < indexRight && nums[indexMiddle] == nums[++indexMiddle]); while(indexMiddle < indexRight && nums[indexRight] == nums[--indexRight]); } else if(sum > 0) { //左边递减 indexRight--; } else { //右边递增 indexMiddle++; } } } return ans; }
11.盛最多水的容器（双指针）
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
使用双指针解决
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 int maxArea(int* height, int heightSize){ int marea = 0; int carea = 0; int left = 0; int right = heightSize-1; while(left<right){ carea = (right-left)*fmin(height[left],height[right]); marea = fmax(carea,marea); if(height[left]<=height[right]){ left++; } else{ right--; } } return marea; }
20.有效的括号（栈）
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
用栈解决
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 bool isValid(char * s){ int n = strlen(s); if(n%2!=0) return 0; char *stack = (char *)malloc(sizeof(char)*n); int top = -1; for(int i = 0; i<n ;i++){ if(s[i]=='('||s[i]=='{'||s[i]=='['){ stack[++top] = s[i]; } if(s[i]==')'){ if(top==-1) return 0; if(stack[top]=='('){ top -- ; } else{ return 0; } } if(s[i]=='}'){ if(top==-1) return 0; if(stack[top]=='{'){ top -- ; } else{ return 0; } } if(s[i]==']'){ if(top==-1) return 0; if(stack[top]=='['){ top -- ; } else{ return 0; } } } if(top==-1) return 1; else return 0; }
19.删除链表的倒数第N个结点（快慢指针）
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
官方题解，使用哑结点dummy避免头结点的讨论
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 /** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* removeNthFromEnd(struct ListNode* head, int n) { struct ListNode* dummy = malloc(sizeof(struct ListNode)); dummy->next = head;//构造虚拟节点，避免头节点的讨论 struct ListNode* first = head; struct ListNode* second = dummy;//定义快慢指针 for (int i = 0; i < n; ++i) {//快指针先走 first = first->next; } while (first) {//慢指针跟上 first = first->next; second = second->next; } second->next = second->next->next;//删除慢指针指向的下一个元素 struct ListNode* ans = dummy->next; free(dummy); return ans; }
自己的想法
利用两个指针，一个在前，一个在后，相差n；让p1先走n步。
如果p1为空，说明n正好为链表长度，所以删除倒数第n个就是删除第一个；
如果p1不为空，p2从头开始和p1一起移动，此时二者相差n个，当p1的下一个为空，说明p1正好是最后一个，倒数第n就正好是p2的下一个，所以删除p2的下一个即可；
1 2 3 4 5 6 7 8 9 10 11 12 13 struct ListNode* removeNthFromEnd(struct ListNode* head, int n){ int i; struct ListNode *p1=head,*p2=head; for(i=0;i<n;i++) p1=p1->next; while(p1!=NULL&&p1->next!=NULL){ p1=p1->next; p2=p2->next; } if(p1==NULL) head=head->next; else p2->next=p2->next->next; return head; }
21.合并两个有序链表（迭代）
将两个升序链表合并为一个新的升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
迭代
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ struct ListNode * preHead = malloc(sizeof(struct ListNode)); struct ListNode* prev = preHead; while (list1 != NULL && list2 != NULL) { if (list1->val < list2->val) { prev->next = list1; list1 = list1->next; } else { prev->next = list2; list2 = list2->next; } prev = prev->next; } // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可 prev->next = list1 == NULL ? list2 : list1; return preHead->next; }
22.括号生成（回溯 模板）
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。
示例 ：
1 2 输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]
题解
1 2 3 4 5 6 7 8 9 10 11 12 void backtracking(参数) { if (终止条件) { 存放结果; return; } for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) { 处理节点; backtracking(路径，选择列表); // 递归 回溯，撤销处理结果 } }
就是不停选括号，要么选左括号，要么选右括号。
只要(有剩，就可以选(。(((((这么选，都还不能判定为非法。
当剩下的)比(多时，才可以选)，否则，)不能选，选了就非法。因为：剩下的)比(少，即，使用的)比(多，不能成双成对。
描述节点的状态有：当前构建的字符串，和左右括号所剩的数量。
选择
在这里，每次最多两个选择，选左括号或右括号，“选择”会展开出一棵解的空间树。
约束条件：
即，什么情况下可以选左括号，什么情况下可以选右括号。
if (right > left) { // 右括号剩的比较多，才能选右括号
目标：
构建出一个用尽 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 void generate(int left,int right,int size,char* str,int n, int* returnSize,char** result) //left代表左括号数量，right代表右括号数量，str代表储存几组有效组合，returnsize表示返回数量 { if (left == n && right == n) { // 满足题意的题解 result[(*returnSize)] = (char*)calloc((2 * n + 1), sizeof(char)); strcpy(result[(*returnSize)++], str); return; } // 如果左括号数量不大于 n，可以放一个左括号 if (left < n) { str[size] = '('; generate(left + 1, right, size + 1, str, n, returnSize, result); } // 如果右括号数量小于左括号的数量，可以放一个右括号 if (right < left) { str[size] = ')'; generate(left , right+1, size + 1, str, n, returnSize, result); } } char ** generateParenthesis(int n, int* returnSize) { char *str = (char*)calloc((2 * n + 1), sizeof(char)); char **result = (char**)malloc(sizeof(char*) * 1430); // 卡特兰数: 1, 2, 5, 14, 42, 132, 429, 1430，题目中最多生成1430组 *returnSize = 0; generate(0, 0, 0, str, n, returnSize, result); return result; }
1 2 3 4 5 6 7 8 9 10 11 //卡特兰数的一个递推函数 int catalan(n) { int i, j, h[n + 1]; h[0] = h[1] = 1; for (i = 2; i <= n; i++) { h[i] = 0; for (j = 0; j < i; j++) h[i] = h[i] + h[j] * h[i - j - 1]; } return h[n]; }
28.找出字符串中第一个匹配项的下标（KMP）
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
KMP算法
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 int strStr(char* haystack, char* needle) { int n = strlen(haystack), m = strlen(needle); if (m == 0) { return 0; } int next[m]; //求next数组 next[0] = 0; for (int i = 1, j = 0; i < m; i++) { while (j > 0 && needle[i] != needle[j]) { j = next[j - 1]; } if (needle[i] == needle[j]) { j++; } next[i] = j; } //求第一个匹配项下标 for (int i = 0, j = 0; i < n; i++) { while (j > 0 && haystack[i] != needle[j]) { j = next[j - 1]; } if (haystack[i] == needle[j]) { j++; } if (j == m) { return i - m + 1; } } return -1; }
17.电话号码的字母组成（回溯）
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
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 : string temp; vector<string> res; vector<string> map = {"" ,"" ,"abc" ,"def" ,"ghi" ,"jkl" ,"mno" ,"pqrs" ,"tuv" ,"wxyz" }; void DFS (string digits,int pos) int len = digits.size (); if (pos == len){ res.push_back (temp); return ; } int num = digits[pos] - '0' ; for (int i = 0 ; i < map[num].size (); i++){ temp.push_back (map[num][i]); DFS (digits,pos+1 ); temp.pop_back (); } } vector<string> letterCombinations (string digits) { if (digits.size () == 0 ) return res; DFS (digits,0 ); return res; } };
34.在排序数组中查找元素的第一个和最后一个位置（二分查找）
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log 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 int findmid(int *nums, int low , int high , int target){ //递归实现二分查找 //if(low > high) return -1; //int mid = (low + high)/2; //if(nums[mid]==target) return mid; //else if(nums[mid]>target) return findmid(nums,low,mid-1,target); //else return findmid(nums,mid+1,high,target); //迭代实现 while(low<=high){ int mid = (low + high)/2; if(nums[mid]==target) return mid; else if(nums[mid]>target)high = mid -1; else low = mid + 1; } return -1; } int* searchRange(int* nums, int numsSize, int target, int* returnSize){ *returnSize=2; int *result = (int*)malloc(sizeof(int)*2); if(numsSize == 0){ result[0]=-1;result[1]=-1; return result; } int ans = findmid(nums,0,numsSize-1,target); if(ans == -1){ result[0]=-1;result[1]=-1; return result; } else{ int low=ans,high=ans; while((low-1)>=0&&nums[low-1]==target) low--; while((high+1)<numsSize&&nums[high+1]==target) high++; result[0]=low;result[1]=high; return result; } result[0]=-1;result[1]=-1; return result; }
53.最大子数组和（dp||贪心）
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
1 2 3 4 5 6 7 8 9 //dp解 int maxSubArray(int* nums, int numsSize) { int pre = 0, maxAns = nums[0]; for (int i = 0; i < numsSize; i++) { pre = fmax(pre + nums[i], nums[i]); maxAns = fmax(maxAns, pre); } return maxAns; }
1 2 3 4 5 6 7 8 9 10 11 //贪心解 int maxSubArray(int* nums, int numsSize) { int result = INT_MIN; int tmp = 0; for(int i = 0; i < numsSize; i++) { tmp += nums[i]; result = fmax(tmp, result); if(tmp < 0) tmp = 0; } return result; }
46.全排列（回溯）
给定一个不含重复数字的数组 nums ，返回其所有可能的全排列 。你可以按任意顺序返回答案。
回溯
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 void swap(int * nums,int indexA,int indexB) { int temp = nums[indexA]; nums[indexA]= nums[indexB]; nums[indexB]= temp; } void prem(int* nums, int numsSize, int* returnSize, int** returnColumnSizes,int** returnNums,int offset) { if(offset == numsSize) { //遍历到末尾了 //申请returnNums returnNums[*returnSize] = (int *)malloc(sizeof(int ) * numsSize); //拷贝内容到returnNums memcpy(returnNums[*returnSize],nums,sizeof(int) * numsSize ); //记录当前拷贝内容的长度 (*returnColumnSizes)[*returnSize] = numsSize; *returnSize = *returnSize + 1; } else { //回溯算法的核心 int i; for(i = offset; i < numsSize; i++) { swap(nums,i,offset);//i 和 offset 交换 prem(nums,numsSize,returnSize,returnColumnSizes,returnNums,offset+1); swap(nums,i,offset);//i 和 offset 交换 } } } int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) { //不重复的数字的全排序 //组合次数为 n！= n *( n - 1) *( n - 2) ...... 2 * 1 //这样的方法适合回溯的方法 //取值范围1 <= nums.length <= 6 = 6 * 5 * 4 * 3 *2 * 1 = 720中可能 int **returnNums = (int **)malloc(sizeof(int *) * 721); *returnColumnSizes= (int *)malloc(sizeof(int ) * 721); *returnSize = 0; prem(nums,numsSize,returnSize,returnColumnSizes,returnNums,0); return returnNums; }
55.跳跃游戏（贪心）
给定一个非负整数数组 nums ，你最初位于数组的第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
题解
对于每一个可以到达的位置 i，它使得 i+1, i+2,···,i+nums[i] 这些连续的位置都可以到达。
这样以来，我们依次遍历数组中的每一个位置，并实时维护 最远可以到达的位置。对于当前遍历到的位置 i，如果它在 最远可以到达的位置 的范围内，那么我们就可以从起点通过若干次跳跃到达该位置，因此我们可以用 i+nums[i] 更新 最远可以到达的位置。
在遍历的过程中，如果 最远可以到达的位置 大于等于数组中的最后一个位置，那就说明最后一个位置可达，我们就可以直接返回 True 作为答案。反之，如果在遍历结束后，最后一个位置仍然不可达，我们就返回 False 作为答案。
1 2 3 4 5 6 7 8 9 10 11 12 bool canJump(int* nums, int numsSize){ int mostf = 0; for(int i=0;i<numsSize;i++){ if(i<=mostf){ mostf =fmax(mostf,i+nums[i]); if(mostf>=numsSize-1){ return true; } } } return false; }
198.打家劫舍（dp）
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例：
1 2 3 4 输入：[2,7,9,3,1] 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。
题解
对于第 i(i>2) 间房屋，有两个选项：
偷窃第 i 间房屋，那么就不能偷窃第 i−1 间房屋，偷窃总金额为前 i−2 间房屋的最高总金额与第 i 间房屋的金额之和。
不偷窃第 i 间房屋，偷窃总金额为前 i−1 间房屋的最高总金额。
在两个选项中选择偷窃总金额较大的选项，该选项对应的偷窃总金额即为前 i 间房屋能偷窃到的最高总金额。
用 dp[i] 表示前 i 间房屋能偷窃到的最高总金额，那么就有如下的状态转移方程：
dp[i]=max(dp[i−2]+nums[i],dp[i−1])
边界条件为：
只有一间房屋，则偷窃该房屋：dp[0]=nums[0]
只有两间房屋，选择其中金额较高的房屋进行偷窃：dp[1]=max(nums[0],nums[1])
最终的答案即为 dp[n−1]，其中 n 是数组的长度。
1 2 3 4 5 6 7 8 9 10 11 12 int rob(int* nums, int numsSize){ int dp[numsSize]; if(numsSize==0) return 0; dp[0] = nums[0]; if(numsSize>=2){ dp[1] = fmax(nums[0],nums[1]); } for(int i = 2 ; i < numsSize ; i++){ dp[i] = fmax(dp[i-1],dp[i-2]+nums[i]); } return dp[numsSize-1]; }
6.Z字形变化
将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution {public : string convert (string s, int numRows) { if (numRows < 2 ) return s; vector<string> res (numRows) ; int i = 0 ; int flag = -1 ; for (char &ch : s) { res[i] += ch; if (i == 0 || i == numRows - 1 ) { flag = -flag; } i += flag; } for (int i = 1 ; i < numRows; i++) { res[0 ] += res[i]; } return res[0 ]; } };
122.买卖股票的最佳时机II（dp||贪心）
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在同一天出售。
返回你能获得的最大利润 。
题解
贪心
1 2 3 4 5 6 7 int maxProfit(int* prices, int pricesSize) { int ans = 0; for (int i = 1; i < pricesSize; ++i) { ans += fmax(0, prices[i] - prices[i - 1]); } return ans; }
dp
定义状态 dp[i][0] 表示第 ii 天交易完后手里没有股票的最大利润，dp[i][1] 表示第 i 天交易完后手里持有一支股票的最大利润（i 从 0 开始）。
考虑 dp[i][0] 的转移方程，如果这一天交易完后手里没有股票，那么可能的转移状态为前一天已经没有股票，即 dp[i−1][0]，或者前一天结束的时候手里持有一支股票，即 dp[i−1][1]，这时候我们要将其卖出，并获得 prices[i] 的收益。因此为了收益最大化，我们列出如下的转移方程：
dp[i][0]=max{dp[i−1][0],dp[i−1][1]+prices[i]}
再来考虑 dp[i][1]，按照同样的方式考虑转移状态，那么可能的转移状态为前一天已经持有一支股票，即 dp[i−1][1]，或者前一天结束时还没有股票，即 dp[i−1][0]，这时候我们要将其买入，并减少 prices[i] 的收益。可以列出如下的转移方程：
dp[i][1]=max{dp[i−1][1],dp[i−1][0]−prices[i]}
对于初始状态，根据状态定义我们可以知道第 0 天交易结束的时候 dp[0][1]=−prices[0]。
因此，我们只要从前往后依次计算状态即可。由于全部交易结束后，持有股票的收益一定低于不持有股票的收益，因此这时候 dp[n−1][0] 的收益必然是大于 dp[n−1][1] 的，最后的答案即为 dp[n−1][0]。
注意到上面的状态转移方程中，每一天的状态只与前一天的状态有关，而与更早的状态都无关，因此我们不必存储这些无关的状态，只需要将 dp[i−1][0] 和 dp[i−1][1] 存放在两个变量中，通过它们计算出 dp[i][0] 和 dp[i][1] 并存回对应的变量，以便于第 i+1 天的状态转移即可。
1 2 3 4 5 6 7 8 9 10 int maxProfit(int* prices, int pricesSize) { int dp0 = 0, dp1 = -prices[0]; for (int i = 1; i < pricesSize; ++i) { int newDp0 = fmax(dp0, dp1 + prices[i]); int newDp1 = fmax(dp1, dp0 - prices[i]); dp0 = newDp0; dp1 = newDp1; } return dp0; }
300.最长递增子序列（dp）
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
题解
定义 dp[i] 为考虑前 i 个元素，以第 i 个数字结尾的最长上升子序列的长度，注意 nums[i] 必须被选取。
我们从小到大计算 dp 数组的值，在计算 dp[i] 之前，我们已经计算出 dp[0…i−1] 的值，则状态转移方程为：
dp[i]=max(dp[j])+1,其中0≤j<i且num[j]<num[i]
即考虑往 dp[0…i−1] 中最长的上升子序列后面再加一个 nums[i]。由于 dp[j] 代表 nums[0…j] 中以 nums[j] 结尾的最长上升子序列，所以如果能从 dp[j] 这个状态转移过来，那么 nums[i] 必然要大于 nums[j]，才能将 nums[i] 放在 nums[j] 后面以形成更长的上升子序列。
最后，整个数组的最长上升子序列即所有 dp[i] 中的最大值。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 int lengthOfLIS(int* nums, int numsSize){ int dp[numsSize]; dp[0]=1; int maxans = 1; for(int i = 1; i<numsSize ; i++){ dp[i] = 1; for (int j = 0; j < i; j++) { if (nums[i] > nums[j]) { dp[i] = fmax(dp[i], dp[j] + 1); } } maxans = fmax(maxans, dp[i]); } return maxans; }
78.子集（回溯 迭代 递归）
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
1 2 输入：nums = [1,2,3] 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
记原序列中元素的总数为 n。原序列中的每个数字 a_i 的状态可能有两种，即「在子集中」和「不在子集中」。我们用 1 表示「在子集中」，0 表示不在子集中，那么每一个子集可以对应一个长度为 n 的 0/1 序列，第 i 位表示a_i是否在子集中。
可以发现 0/1 序列对应的二进制数正好从 0 到 2^n - 1。我们可以枚举 mask∈[0,2n−1]，mask 的二进制表示是一个 0/1 序列，我们可以按照这个 0/1 序列在原集合当中取数。当我们枚举完所有 2^n个 mask，我们也就能构造出所有的子集。
迭代
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 int** subsets(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) { int** ans = malloc(sizeof(int*) * (1 << numsSize)); *returnColumnSizes = malloc(sizeof(int) * (1 << numsSize)); *returnSize = 1 << numsSize; int t[numsSize]; for (int mask = 0; mask < (1 << numsSize); ++mask) { int tSize = 0; for (int i = 0; i < numsSize; ++i) { if (mask & (1 << i)) { //<<表示向左移位，1 << i 表示第i位为1，其他位为0的整型值，Mask & ( 1 << i )表示检验标志变量Mask的第i位是否为1 t[tSize++] = nums[i]; } } int* tmp = malloc(sizeof(int) * tSize); memcpy(tmp, t, sizeof(int) * tSize); (*returnColumnSizes)[mask] = tSize; ans[mask] = tmp; } return ans; }
递归
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 : vector<int > t; vector<vector<int >> ans; void dfs (int cur, vector<int >& nums) if (cur == nums.size ()) { ans.push_back (t); return ; } t.push_back (nums[cur]); dfs (cur + 1 , nums); t.pop_back (); dfs (cur + 1 , nums); } vector<vector<int >> subsets (vector<int >& nums) { dfs (0 , nums); return ans; } };
上面的代码中，dfs(cur,n) 参数表示当前位置是 cur，原序列总长度为 n。原序列的每个位置在答案序列中的状态有被选中和不被选中两种，我们用 t 数组存放已经被选出的数字。在进入 dfs(cur,n) 之前 [0,cur−1] 位置的状态是确定的，而 [cur,n−1] 内位置的状态是不确定的，dfs(cur,n) 需要确定 cur 位置的状态，然后求解子问题 dfs(cur+1,n)。对于 cur 位置，我们需要考虑 a[cur] 取或者不取，如果取，我们需要把 a[cur] 放入一个临时的答案数组中（即上面代码中的 t），再执行 dfs(cur+1,n)，执行结束后需要对 t 进行回溯；如果不取，则直接执行 dfs(cur+1,n)。在整个递归调用的过程中，cur 是从小到大递增的，当 cur 增加到 n 的时候，记录答案并终止递归。可以看出二进制枚举的时间复杂度是 O(2 ^ n)。
62.不同路径（dp）
一个机器人位于一个 m x n 网格的左上角。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。
问总共有多少条不同的路径？
题解
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 int uniquePaths(int m, int n){ int dp[m][n]; for(int i = 0 ; i< m ; i++){ dp[i][0] = 1; } for(int i = 0 ; i< n ; i++){ dp[0][i] = 1; } for(int i =1 ; i<m ; i++){ for(int j = 1 ; j<n ; j++){ dp[i][j]=dp[i-1][j]+dp[i][j-1]; } } return dp[m-1][n-1]; }
59. 螺旋矩阵 II（模拟）
给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 nxn 正方形矩阵 matrix 。
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 int** generateMatrix(int n, int* returnSize, int** returnColumnSizes){ int left = 0, right = n-1, top = 0, bottom = n-1; int count = 1, target = n * n; int** matrix = malloc(sizeof(int*) * n); *returnSize = n; *returnColumnSizes = malloc(sizeof(int) * n); for (int i = 0; i < n; i++) { matrix[i] = malloc(sizeof(int) * n); memset(matrix[i], 0, sizeof(int) * n); (*returnColumnSizes)[i] = n; } while(count <= target){ //从左到右填充，相当于缩小上边界 for(int j = left; j <= right; j++) matrix[top][j] = count++; //缩小上边界 top++; //从上向下填充，相当于缩小右边界 for(int i = top; i <=bottom; i++) matrix[i][right] = count++; //缩小右边界 right--; //从右向左填充，相当于缩小下边界 for(int j = right; j >= left; j--) matrix[bottom][j] = count++; //缩小下边界 bottom--; //从下向上填充，相当于缩小左边界 for(int i = bottom; i >= top; i--) matrix[i][left] = count++; //缩小左边界 left++; } return matrix; }
92. 反转链表 II
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
1 2 3 4 5 6 7 8 9 10 11 12 void reverseLinkedList(struct ListNode *head) { // 也可以使用递归反转一个链表 struct ListNode *pre = NULL; struct ListNode *cur = head; while (cur != NULL) { struct ListNode *next = cur->next; cur->next = pre; pre = cur; cur = next; } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 struct ListNode *reverseBetween(struct ListNode *head, int left, int right) { // 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论 struct ListNode *dummyNode = malloc(sizeof(struct ListNode)); dummyNode->val = -1; dummyNode->next = head; struct ListNode *pre = dummyNode; for (int i = 0; i < left - 1; i++) { pre = pre->next; } struct ListNode *cur = pre->next; struct ListNode *next; for (int i = 0; i < right - left; i++) { next = cur->next; cur->next = next->next; next->next = pre->next; pre->next = next; } return dummyNode->next; }
322. 零钱兑换（dp）
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
题解
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 int cmp(const void * a, const void * b) { return *(int *)a - *(int *)b; } #define MIN(a , b) ((a) < (b) ? (a) : (b)) int coinChange(int* coins, int coinsSize, int amount){ qsort(coins, coinsSize, sizeof(coins[0]), cmp);//升序 int dp[amount + 1]; dp[0] = 0; for(int i = 1; i <= amount; i++)//遍历dp数组 { dp[i] = amount + 1;//初始化最大值 for(int j = 0; j < coinsSize; j++)//动态更新dp[i] { if(coins[j] > i) { break; } else { dp[i] = MIN(dp[i] , dp[i - coins[j]] + 1); } } } return dp[amount] == (amount+1) ? -1 : dp[amount]; }
76.最小覆盖子串(滑动窗口+hash)
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 class Solution { public String minWindow (String s, String t) { if (s == null || s == "" || t == null || t == "" || s.length() < t.length()) { return "" ; } int [] need = new int [128 ]; int [] have = new int [128 ]; for (int i = 0 ; i < t.length(); i++) { need[t.charAt(i)]++; } int left = 0 , right = 0 , min = s.length() + 1 , count = 0 , start = 0 ; while (right < s.length()) { char r = s.charAt(right); if (need[r] == 0 ) { right++; continue ; } if (have[r] < need[r]) { count++; } have[r]++; right++; while (count == t.length()) { if (right - left < min) { min = right - left; start = left; } char l = s.charAt(left); if (need[l] == 0 ) { left++; continue ; } if (have[l] == need[l]) { count--; } have[l]--; left++; } } if (min == s.length() + 1 ) { return "" ; } return s.substring(start, start + min); } }
45.跳跃游戏II（贪心）
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
0 <= j <= nums[i]
i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。
1 2 3 4 5 6 7 8 9 10 11 12 13 int jump(int* nums, int numsSize){ int maxPos = 0, end = 0, step = 0; for (int i = 0; i < numsSize - 1; ++i) { if (maxPos >= i) { maxPos = fmax(maxPos, i + nums[i]); if (i == end) { end = maxPos; ++step; } } } return step; }
31. 下一个排列
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。必须原地修改，只允许使用额外常数空间。
题解
首先从后向前查找第一个顺序对 (i,i+1)，满足 a[i]<a[i+1]。这样「较小数」即为 a[i]。此时 [i+1,n) 必然是下降序列。
如果找到了顺序对，那么在区间 [i+1,n) 中从后向前查找第一个元素 a[i]<a[j]。这样「较大数」即为 a[j]。
交换 a[i] 与 a[j]，此时可以证明区间 [i+1,n) 必为降序。我们可以直接使用双指针反转区间 [i+1,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 void swap(int *a, int *b) { int t = *a; *a = *b, *b = t; } void reverse(int *nums, int left, int right) { while (left < right) { swap(nums + left, nums + right); left++, right--; } } void nextPermutation(int *nums, int numsSize) { int i = numsSize - 2; while (i >= 0 && nums[i] >= nums[i + 1]) { i--; } if (i >= 0) { int j = numsSize - 1; while (j >= 0 && nums[i] >= nums[j]) { j--; } swap(nums + i, nums + j); } reverse(nums, i + 1, numsSize - 1); }
61. 旋转链表（闭合为环）
给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
题解 闭合为环
记给定链表的长度为 n，注意到当向右移动的次数 k≥n 时，我们仅需要向右移动 k mod n 次即可。因为每 n 次移动都会让链表变为原状。这样我们可以知道，新链表的最后一个节点为原链表的第 (n−1)−(k mod n) 个节点（从 0 开始计数）。
这样，我们可以先将给定的链表连接成环，然后将指定位置断开。
具体代码中，我们首先计算出链表的长度 n，并找到该链表的末尾节点，将其与头节点相连。这样就得到了闭合为环的链表。然后我们找到新链表的最后一个节点（即原链表的第 (n−1)−(k mod n) 个节点），将当前闭合为环的链表断开，即可得到我们所需要的结果。
特别地，当链表长度不大于 1 ，或者 k 为 n 的倍数时，新链表将与原链表相同，我们无需进行任何处理。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 struct ListNode* rotateRight(struct ListNode* head, int k) { if (k == 0 || head == NULL || head->next == NULL) { return head; } int n = 1; struct ListNode* iter = head; while (iter->next != NULL) { iter = iter->next; n++; } int add = n - k % n; if (add == n) { return head; } iter->next = head; while (add--) { iter = iter->next; } struct ListNode* ret = iter->next; iter->next = NULL; return ret; }
77. 组合（回溯）
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 int* temp; int tempSize; int** ans; int ansSize; void dfs(int cur, int n, int k) { // 剪枝：temp 长度加上区间 [cur, n] 的长度小于 k，不可能构造出长度为 k 的 temp if (tempSize + (n - cur + 1) < k) { return; } // 记录合法的答案 if (tempSize == k) { int* tmp = malloc(sizeof(int) * k); for (int i = 0; i < k; i++) { tmp[i] = temp[i]; } ans[ansSize++] = tmp; return; } // 考虑选择当前位置 temp[tempSize++] = cur; dfs(cur + 1, n, k); tempSize--; // 考虑不选择当前位置 dfs(cur + 1, n, k); } int** combine(int n, int k, int* returnSize, int** returnColumnSizes) { temp = malloc(sizeof(int) * k); ans = malloc(sizeof(int*) * 10001); tempSize = ansSize = 0; dfs(1, n, k); *returnSize = ansSize; *returnColumnSizes = malloc(sizeof(int) * ansSize); for (int i = 0; i < ansSize; i++) { (*returnColumnSizes)[i] = k; } return ans; }
739. 每日温度(单调栈)
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
示例 1:
题解
正向遍历温度列表。对于温度列表中的每个元素 temperatures[i]，如果栈为空，则直接将 i 进栈，如果栈不为空，则比较栈顶元素 prevIndex 对应的温度 temperatures[prevIndex] 和当前温度 temperatures[i]，如果 temperatures[i] > temperatures[prevIndex]，则将 prevIndex 移除，并将 prevIndex 对应的等待天数赋为 i - prevIndex，重复上述操作直到栈为空或者栈顶元素对应的温度小于等于当前温度，然后将 i 进栈。
为什么可以在弹栈的时候更新 ans[prevIndex] 呢？因为在这种情况下，即将进栈的 i 对应的 temperatures[i] 一定是 temperatures[prevIndex] 右边第一个比它大的元素，试想如果 prevIndex 和 i 有比它大的元素，假设下标为 j，那么 prevIndex 一定会在下标 j 的那一轮被弹掉。
由于单调栈满足从栈底到栈顶元素对应的温度递减，因此每次有元素进栈时，会将温度更低的元素全部移除，并更新出栈元素对应的等待天数，这样可以确保等待天数一定是最小的。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution {public : vector<int > dailyTemperatures (vector<int >& temperatures) { int n = temperatures.size (); vector<int > ans (n) ; stack<int > s; for (int i = 0 ; i < n; ++i) { while (!s.empty () && temperatures[i] > temperatures[s.top ()]) { int previousIndex = s.top (); ans[previousIndex] = i - previousIndex; s.pop (); } s.push (i); } return ans; } };
116. 填充每个节点的下一个右侧节点指针（链表）
给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
1 2 3 4 5 6 struct Node { int val; Node *left; Node *right; Node *next; }
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
迭代 使用next指针 两种连接方式
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 struct Node* connect(struct Node* root) { if (root == NULL) { return root; } // 从根节点开始 struct Node* leftmost = root; while (leftmost->left != NULL) { // 遍历这一层节点组织成的链表，为下一层的节点更新 next 指针 struct Node* head = leftmost; while (head != NULL) { // CONNECTION 1 连接同一个父节点的两个子节点 head->left->next = head->right; // CONNECTION 2 在不同父亲的子节点之间建立连接 if (head->next != NULL) { head->right->next = head->next->left; } // 指针向后移动 head = head->next; } // 去下一层的最左的节点 leftmost = leftmost->left; } return root; }
递归 使用层序遍历和队列
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 struct Node* connect(struct Node* root) { if (root == NULL) { return root; } // 初始化队列同时将第一层节点加入队列中，即根节点 struct Node* Q[5000]; int left = 0, right = 0; Q[right++] = root; // 外层的 while 循环迭代的是层数 while (left < right) { // 记录当前队列大小 int size = right - left; // 遍历这一层的所有节点 for (int i = 0; i < size; i++) { // 从队首取出元素 struct Node* node = Q[left++]; // 连接 if (i < size - 1) { node->next = Q[left]; } // 拓展下一层节点 if (node->left != NULL) { Q[right++] = node->left; } if (node->right != NULL) { Q[right++] = node->right; } } } // 返回根节点 return root; }
139. 单词拆分（dp）
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 1：
1 2 输入: s = "applepenapple", wordDict = ["apple", "pen"] 输出: true
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 const wordBreak = (s, wordDict) => { const wordSet = new Set(wordDict); const len = s.length; const dp = new Array(len + 1).fill(false); dp[0] = true; for (let i = 1; i <= len; i++) { for (let j = i - 1; j >= 0; j--) { // j去划分成两部分 const suffix = s.slice(j, i); // 后缀部分 s[j: i-1] if (wordSet.has(suffix) && dp[j]) { // 后缀部分是单词，且左侧子串[0,j-1]的dp[j]为真 dp[i] = true; break; // dp[i] = true了，i长度的子串已经可以拆成单词了，不需要j继续划分子串了 } } } return dp[len]; };
567. 字符串的排列（双指针+滑动窗口）
给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
换句话说，s1 的排列之一是 s2 的 子串 。
1 2 3 4 5 6 7 8 9 10 11 示例 1： 输入：s1 = "ab" s2 = "eidbaooo" 输出：true 解释：s2 包含 s1 的排列之一 ("ba"). 示例 2： 输入：s1= "ab" s2 = "eidboaoo" 输出：false
题解
然后用两个指针 left 和 right 表示考察的区间 [left,right]。right 每向右移动一次，就统计一次进入区间的字符 x。
为保证 cnt 的值不为正，若此时 cnt[x]>0，则向右移动左指针，减少离开区间的字符的 cnt 值直到 cnt[x]≤0。
注意到 [left,right] 的长度每增加 1，cnt 的元素值之和就增加 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 bool checkInclusion(char* s1, char* s2) { int n = strlen(s1), m = strlen(s2); if (n > m) { return false; } int cnt[26]; memset(cnt, 0, sizeof(cnt)); for (int i = 0; i < n; ++i) { --cnt[s1[i] - 'a']; } int left = 0; for (int right = 0; right < m; ++right) { int x = s2[right] - 'a'; ++cnt[x]; while (cnt[x] > 0) { --cnt[s2[left] - 'a']; ++left; } if (right - left + 1 == n) { return true; } } return false; }
128. 最长连续序列(哈希表 js:set)
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
1 2 3 输入：nums = [100,4,200,1,3,2] 输出：4 解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
题解
对于匹配的过程，暴力的方法是 O(n) 遍历数组去看是否存在这个数，但其实更高效的方法是用一个哈希表存储数组中的数，这样查看一个数是否存在即能优化至 O(1) 的时间复杂度。
仅仅是这样我们的算法时间复杂度最坏情况下还是会达到 O(n^2)（即外层需要枚举 O(n) 个数，内层需要暴力匹配 O(n) 次），无法满足题目的要求。但仔细分析这个过程，我们会发现其中执行了很多不必要的枚举，如果已知有一个 x,x+1,x+2,⋯,x+y 的连续序列，而我们却重新从 x+1，x+2 或者是 x+y 处开始尝试匹配，那么得到的结果肯定不会优于枚举 x 为起点的答案，因此我们在外层循环的时候碰到这种情况跳过即可。
那么怎么判断是否跳过呢？由于我们要枚举的数 x 一定是在数组中不存在前驱数 x−1 的，不然按照上面的分析我们会从 x−1 开始尝试匹配，因此我们每次在哈希表中检查是否存在 x−1 即能判断是否需要跳过了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 var longestConsecutive = function(nums) { let num_set = new Set(); for (const num of nums) { num_set.add(num); } let longestStreak = 0; for (const num of num_set) { if (!num_set.has(num - 1)) { let currentNum = num; let currentStreak = 1; while (num_set.has(currentNum + 1)) { currentNum += 1; currentStreak += 1; } longestStreak = Math.max(longestStreak, currentStreak); } } return longestStreak; }
394. 字符串解码
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
1 2 3 示例： 输入：s = "2[abc]3[cd]ef" 输出："abcabccdcdcdef"
数字存放在数字栈，字符串存放在字符串栈，遇到右括号时候弹出一个数字栈，字母栈弹到左括号为止。就是逆波兰式那种题。
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 /** * @param {string} s * @return {string} */ const decodeString = (s) => { let numStack = []; // 存倍数的栈 let strStack = []; // 存 待拼接的str 的栈 let num = 0; // 倍数的“搬运工” let result = ''; // 字符串的“搬运工” for (const char of s) { // 逐字符扫描 if (!isNaN(char)) { // 遇到数字 num = num * 10 + Number(char); // 算出倍数 } else if (char == '[') { // 遇到 [ strStack.push(result); // result串入栈 result = ''; // 入栈后清零 numStack.push(num); // 倍数num进入栈等待 num = 0; // 入栈后清零 } else if (char == ']') { // 遇到 ]，两个栈的栈顶出栈 let repeatTimes = numStack.pop(); // 获取拷贝次数 result = strStack.pop() + result.repeat(repeatTimes); // 构建子串 } else { result += char; // 遇到字母，追加给result串 } } return result; };
29. 两数相除
给你两个整数，被除数 dividend 和除数 divisor。将两数相除，要求 不使用 乘法、除法和取余运算。
整数除法应该向零截断，也就是截去（truncate）其小数部分。例如，8.345 将被截断为 8 ，-2.7335 将被截断至 -2 。
返回被除数 dividend 除以除数 divisor 得到的 商 。
注意：假设我们的环境只能存储 32 位 有符号整数，其数值范围是 [−2^31, 2^31 − 1] 。本题中，如果商 严格大于 2^31 − 1 ，则返回 2^31 − 1 ；如果商 严格小于 -2^31 ，则返回 -2^31 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 class Solution { public int divide(int dividend, int divisor) { // 被除数 除数 if(divisor == -1 && dividend == Integer.MIN_VALUE) return Integer.MAX_VALUE; // 溢出 int sign = 1; if((dividend > 0 && divisor < 0)||(dividend < 0 && divisor > 0)) sign = -1; // if(divisor == 1) return dividend; // if(divisor == -1) return -dividend; int a = dividend>0 ? -dividend : dividend; int b = divisor>0 ? -divisor : divisor; // 都改为负号是因为int 的范围是[2^31, 2^31-1]，如果a是-2^32，转为正数时将会溢出 //System.out.println(a + " " + b); if(a > b) return 0; int ans = div(a,b); return sign == -1 ? -ans : ans; } int div(int a, int b) { if(a > b) return 0; int count = 1; int tb = b; while(tb+tb >= a && tb+tb < 0){ // 溢出之后不再小于0 tb += tb; count += count; //System.out.println(tb + " " + count + " " + count*b); } return count+div(a-tb,b); } }
剑指 Offer 12. 矩阵中的路径（回溯[visited使用]）
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
思路与算法
设函数 check(i,j,k) 表示判断以网格的 (i,j) 位置出发，能否搜索到单词 word[k…]，其中 word[k…] 表示字符串 word 从第 k 个字符开始的后缀子串。如果能搜索到，则返回 true，反之返回 false。函数 check(i,j,k) 的执行步骤如下：
如果 board[i][j] =s[k]，当前字符不匹配，直接返回 false。
如果当前已经访问到字符串的末尾，且对应字符依然匹配，此时直接返回 true。
否则，遍历当前位置的所有相邻位置。如果从某个相邻位置出发，能够搜索到子串 word[k+1…]，则返回 true，否则返回 false。
这样，我们对每一个位置 (i,j) 都调用函数 check(i,j,0) 进行检查：只要有一处返回 true，就说明网格中能够找到相应的单词，否则说明不能找到。
为了防止重复遍历相同的位置，需要额外维护一个与 board 等大的 visited 数组，用于标识每个位置是否被访问过。每次遍历相邻位置时，需要跳过已经被访问的位置。
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 var exist = function(board, word) { const h = board.length, w = board[0].length; const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]; const visited = new Array(h); for (let i = 0; i < visited.length; ++i) { visited[i] = new Array(w).fill(false); } const check = (i, j, s, k) => { if (board[i][j] != s.charAt(k)) { return false; } else if (k == s.length - 1) { return true; } visited[i][j] = true; let result = false; for (const [dx, dy] of directions) { let newi = i + dx, newj = j + dy; if (newi >= 0 && newi < h && newj >= 0 && newj < w) { if (!visited[newi][newj]) { const flag = check(newi, newj, s, k + 1); if (flag) { result = true; break; } } } } visited[i][j] = false; return result; } for (let i = 0; i < h; i++) { for (let j = 0; j < w; j++) { const flag = check(i, j, word, 0); if (flag) { return true; } } } return false; };
剑指 Offer 38. 字符串的排列
输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
示例：
1 2 输入：s = "abc" 输出：["abc","acb","bac","bca","cab","cba"]
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 void backtrace(char** rec , int * recSize, int* vis, char * s , int i , int n , char* perm){ if(i == n){ char* tmp = malloc(sizeof(char) * (n+1)); strcpy(tmp,perm); rec[(*recSize)++] = tmp; return; } for(int j=0 ; j<n ; j++){ if(vis[j] || (j>0&&!vis[j-1]&&s[j-1]==s[j])){ continue; } vis[j] = true; perm[i] = s[j]; backtrace(rec, recSize, vis, s, i + 1, n, perm); vis[j] = false; } } int cmp(char* a,char *b){ return *a-*b; } char** permutation(char* s, int* returnSize){ int n = strlen(s); int recMaxSize = 1; for(int i =2 ; i<=n ; i++){ recMaxSize*=i; } char **rec = malloc(sizeof(char*)*recMaxSize); *returnSize = 0; int vis[n]; memset(vis,0,sizeof(vis)); char perm[n+1]; perm[n] = '\0'; qsort(s,n,sizeof(char),cmp); backtrace(rec, returnSize, vis, s, 0, n, perm); return rec; }
剑指 Offer 51. 数组中的逆序对(归并排序)
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例1：
题解
终止条件： 当 l≥r 时，代表子数组长度为 1 ，此时终止划分；
递归划分： 计算数组中点 m ，递归划分左子数组 merge_sort(l, m) 和右子数组 merge_sort(m + 1, r);
合并与逆序对统计：
暂存数组 nums 闭区间 [i,r] 内的元素至辅助数组 tmp ；
循环合并： 设置双指针 i , j 分别指向左 / 右子数组的首元素；
当 i=m+1 时： 代表左子数组已合并完，因此添加右子数组当前元素 tmp[j] ，并执行 j=j+1 ；
否则，当 j=r+1 时： 代表右子数组已合并完，因此添加左子数组当前元素 tmp[i] ，并执行 i=i+1 ；
否则，当 tmp[i]≤tmp[j] 时： 添加左子数组当前元素 tmp[i] ，并执行 i=i+1；
否则（即 tmp[i]>tmp[j]）时： 添加右子数组当前元素 tmp[j] ，并执行 j=j+1 ；此时构成 m−i+1 个「逆序对」，统计添加至 res ；
返回值： 返回直至目前的逆序对总数 res ；
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 int mergeSort(int l, int r , int* nums, int* tmp){ // 终止条件 if(l>=r) return 0; // 递归划分 int m = (l+r)/2; int res = mergeSort(l, m, nums, tmp) + mergeSort(m + 1, r, nums, tmp); // 合并阶段 int i = l, j = m + 1; for (int k = l; k <= r; k++) tmp[k] = nums[k]; for (int k = l; k <= r; k++) { if (i == m + 1) nums[k] = tmp[j++]; else if (j == r + 1 || tmp[i] <= tmp[j]) nums[k] = tmp[i++]; else { nums[k] = tmp[j++]; res += m - i + 1; // 统计逆序对 } } return res; } int reversePairs(int* nums, int numsSize){ int * tmp = malloc(sizeof(int) * numsSize); return mergeSort(0,numsSize-1,nums,tmp); }
剑指 Offer 68 - I. 二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
1 2 3 4 5 6 7 8 9 10 11 12 13 struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) { struct TreeNode* ancestor = root; while (true) { if (p->val < ancestor->val && q->val < ancestor->val) { ancestor = ancestor->left; } else if (p->val > ancestor->val && q->val > ancestor->val) { ancestor = ancestor->right; } else { break; } } return ancestor; }
剑指 Offer 68 - II. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) { /* 当前节点为p、q、NULL都返回本身即可 */ if (root == q || root == p || !root) { return root; } /* 递归处理左子树 */ struct TreeNode* left = lowestCommonAncestor(root->left, p, q); /* 递归处理右子树 */ struct TreeNode* right = lowestCommonAncestor(root->right, p, q); /* 处理当前根节点 */ /* 当前节点左右子树均不为NULL，则找到公共祖先 */ if (left != NULL && right != NULL) { return root; } if (left == NULL && right != NULL) { /* 左子树未发现p、q、右子树发现p、q */ return right; } else if (left != NULL && right == NULL) { /* 右子树未发现p、q、左子树发现p、q */ return left; } else { /* 左、右子树均未发现p、q */ return NULL; } }
1019. 链表中的下一个更大节点(单调栈)
给定一个长度为 n 的链表 head
对于列表中的每个节点，查找下一个 更大节点 的值。也就是说，对于每个节点，找到它旁边的第一个节点的值，这个节点的值 严格大于 它的值。
返回一个整数数组 answer ，其中 answer[i] 是第 i 个节点( 从1开始 )的下一个更大的节点的值。如果第 i 个节点没有下一个更大的节点，设置 answer[i] = 0 。
1 2 输入：head = [2,7,4,3,5] 输出：[7,0,5,5,0]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 var nextLargerNodes = function (head ) { const ans = []; const stack = []; let cur = head; let idx = -1 ; while (cur) { ++idx; ans.push (0 ); while (stack.length && stack[stack.length - 1 ][0 ] < cur.val ) { ans[stack.pop ()[1 ]] = cur.val ; } stack.push ([cur.val , idx]); cur = cur.next ; } return ans; };
1388. 3n 块披萨(dp)
给你一个披萨，它由 3n 块不同大小的部分组成，现在你和你的朋友们需要按照如下规则来分披萨：
你挑选任意 一块披萨。
请你返回你可以获得的披萨大小总和的最大值。
1 2 输入：slices = [1,2,3,4,5,6] 输出：10
题解
给一个长度为 3n 的环状序列，你可以在其中选择 n 个数，并且任意两个数不能相邻，求这 n 个数的最大值。
用 dp[i][j] 表示在前 i 个数中选择了 j 个不相邻的数的最大和:
当 i<2 或 j=0 时:
当 j = 0 , dp = 0;
当 i = 0, j = 1, dp = slices[0];
当 i = 1, j = 1, dp = max(slices[0], slices[1]);
当 i < 2, j >= 2, dp = -∞;
当 i≥2 且 j>0 时:
dp[i][j]=max(dp[i−2][j−1]+slices[i],dp[i−1][j]);
环状序列相较于普通序列，相当于添加了一个限制：普通序列中的第一个和最后一个数不能同时选。这样一来，我们只需要对普通序列进行两遍动态即可得到答案，第一遍动态规划中我们删去普通序列中的第一个数，表示我们不会选第一个数；第二遍动态规划中我们删去普通序列中的最后一个数，表示我们不会选最后一个数。将这两遍动态规划得到的结果去较大值，即为在环状序列上的答案。
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 : int calculate (const vector<int >& slices) int N = slices.size (), n = (N + 1 ) / 3 ; vector<vector<int >> dp (N, vector <int >(n + 1 , INT_MIN)); dp[0 ][0 ] = 0 ; dp[0 ][1 ] = slices[0 ]; dp[1 ][0 ] = 0 ; dp[1 ][1 ] = max (slices[0 ], slices[1 ]); for (int i = 2 ; i < N; i++) { dp[i][0 ] = 0 ; for (int j = 1 ; j <= n; j++) { dp[i][j] = max (dp[i - 1 ][j], dp[i - 2 ][j - 1 ] + slices[i]); } } return dp[N - 1 ][n]; } int maxSizeSlices (vector<int >& slices) vector<int > v1 (slices.begin() + 1 , slices.end()) ; vector<int > v2 (slices.begin(), slices.end() - 1 ) ; int ans1 = calculate (v1); int ans2 = calculate (v2); return max (ans1, ans2); } };
2512. 奖励最顶尖的 K 名学生(哈希)
给你两个字符串数组 positive_feedback 和 negative_feedback ，分别包含表示正面的和负面的词汇。不会 有单词同时是正面的和负面的。
一开始，每位学生分数为 0 。每个正面的单词会给学生的分数加 3 分，每个负面的词会给学生的分数减 1 分。
给你 n 个学生的评语，用一个下标从 0 开始的字符串数组 report 和一个下标从 0 开始的整数数组 student_id 表示，其中 student_id[i] 表示这名学生的 ID ，这名学生的评语是 report[i] 。每名学生的 ID互不相同 。
给你一个整数 k ，请你返回按照得分从高到低 最顶尖的 k 名学生。如果有多名学生分数相同，ID 越小排名越前。
1 2 3 4 输入：positive_feedback = ["smart","brilliant","studious"], negative_feedback = ["not"], report = ["this student is studious","the student is smart"], student_id = [1,2], k = 2 输出：[1,2] 解释： 两名学生都有 1 个正面词汇，都得到 3 分，学生 1 的 ID 更小所以排名更前。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 class Solution {public : vector<int > topStudents (vector<string>& positive_feedback, vector<string>& negative_feedback, vector<string>& report, vector<int >& student_id, int k) { unordered_map<std::string, int > words; for (const auto & word : positive_feedback) { words[word] = 3 ; } for (const auto & word : negative_feedback) { words[word] = -1 ; } vector<vector<int >> A; for (int i = 0 ; i < report.size (); i++) { stringstream ss; string w; int score = 0 ; ss << report[i]; while (ss >> w) { if (words.count (w)) { score += words[w]; } } A.push_back ({-score, student_id[i]}); } sort (A.begin (), A.end ()); vector<int > top_k; for (int i = 0 ; i < k; i++) { top_k.push_back (A[i][1 ]); } return top_k; } };
8026. 构造乘积矩阵
给你一个下标从 0 开始、大小为 n * m 的二维整数矩阵 grid ，定义一个下标从 0 开始、大小为 n * m 的的二维矩阵 p。如果满足以下条件，则称 p 为 grid 的 乘积矩阵 ：
对于每个元素 p[i][j] ，它的值等于除了 grid[i][j] 外所有元素的乘积。乘积对 12345 取余数。
1 2 3 4 5 6 7 8 9 10 11 12 输入：grid = [[1,2],[3,4]] 输出：[[24,12],[8,6]] 解释：p[0][0] = grid[0][1] * grid[1][0] * grid[1][1] = 2 * 3 * 4 = 24 p[0][1] = grid[0][0] * grid[1][0] * grid[1][1] = 1 * 3 * 4 = 12 p[1][0] = grid[0][0] * grid[0][1] * grid[1][1] = 1 * 2 * 4 = 8 p[1][1] = grid[0][0] * grid[0][1] * grid[1][0] = 1 * 2 * 3 = 6 所以答案是 [[24,12],[8,6]] 。 1 <= n == grid.length <= 105 1 <= m == grid[i].length <= 105 2 <= n * m <= 105 1 <= grid[i][j] <= 109
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<vector<int>> constructProductMatrix(vector<vector<int>> &grid) { const int MOD = 12345; int n = grid.size(), m = grid[0].size(); vector<vector<int>> p(n, vector<int>(m)); long long suf = 1; // 后缀乘积 for (int i = n - 1; i >= 0; i--) { for (int j = m - 1; j >= 0; j--) { p[i][j] = suf; // p[i][j] 先初始化成后缀乘积 suf = suf * grid[i][j] % MOD; } } long long pre = 1; // 前缀乘积 for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { p[i][j] = p[i][j] * pre % MOD; // 然后再乘上前缀乘积 pre = pre * grid[i][j] % MOD; } } return p; } };
2530. 执行 K 次操作后的最大分数 (优先队列)
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。你的 起始分数 为 0 。
在一步 操作 中：
选出一个满足 0 <= i < nums.length 的下标 i ，
向上取整函数 ceil(val) 的结果是大于或等于 val 的最小整数。
1 2 3 输入：nums = [10,10,10,10,10], k = 5 输出：50 解释：对数组中每个元素执行一次操作。最后分数是 10 + 10 + 10 + 10 + 10 = 50 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution {public : long long maxKelements (vector<int >& nums, int k) priority_queue<int > q (nums.begin(), nums.end()) ; long long ans = 0 ; for (int _ = 0 ; _ < k; ++_) { int x = q.top (); q.pop (); ans += x; q.push ((x + 2 ) / 3 ); } return ans; } };
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 void swap (int *nums, int i, int j) { int x = nums[i]; nums[i] = nums[j]; nums[j] = x; } void down (int *nums, int size, int i) { for (int k = 2 * i + 1 ; k < size; k = 2 * k + 1 ) { if (k + 1 < size && nums[k] < nums[k + 1 ]) { k++; } if (nums[k] < nums[(k - 1 ) / 2 ]) { break ; } swap(nums, k, (k - 1 ) / 2 ); } } void Init (int *nums, int size) { for (int i = size / 2 - 1 ; i >= 0 ; i--) { down(nums, size, i); } } void Push (int *nums, int size, int x) { nums[size] = x; for (int i = size; i > 0 && nums[(i - 1 ) / 2 ] < nums[i]; i = (i - 1 ) / 2 ) { swap(nums, i, (i - 1 ) / 2 ); } } int Pop (int *nums, int size) { swap(nums, 0 , size - 1 ); down(nums, size - 1 , 0 ); return nums[size - 1 ]; } long long maxKelements (int *nums, int numsSize, int k) { Init(nums, numsSize); long long ans = 0 ; for (int i = 0 ; i < k; i++) { int x = Pop(nums, numsSize); ans += x; Push(nums, numsSize - 1 , (x + 2 ) / 3 ); } return ans; }
2316. 统计无向图中无法互相到达点对数(并查集 or DFS)
给你一个整数 n ，表示一张 无向图 中有 n 个节点，编号为 0 到 n - 1 。同时给你一个二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条 无向 边。
请你返回 无法互相到达 的不同 点对数目 。
1 2 3 4 5 输入：n = 7, edges = [[0,2],[0,5],[2,4],[1,6],[5,4]] 输出：14 解释：总共有 14 个点对互相无法到达： [[0,1],[0,3],[0,6],[1,2],[1,3],[1,4],[1,5],[2,3],[2,6],[3,4],[3,5],[3,6],[4,6],[5,6]] 所以我们返回 14 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 class Solution { public: int dfs(int x ,vector<bool>& visited,vector<vector<int>>& graph){ visited[x] = true; long long count = 1; for(int y : graph[x]){ if (!visited[y]) { count += dfs(y,visited,graph); } } return count; } long long countPairs(int n, vector<vector<int>> &edges) { vector<vector<int>> graph(n); for (const auto &edge : edges) { int x = edge[0], y = edge[1]; graph[x].emplace_back(y); graph[y].emplace_back(x); } vector<bool> visited(n,false); long long res = 0; for (int i = 0; i < n; i++) { if(!visited[i]){ long long count = dfs(i,visited,graph); res += count * (n - count); } } return res / 2; } };
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 class UnionFind { private: vector<int> parents; vector<int> sizes; public: UnionFind(int n) : parents(n), sizes(n, 1) { iota(parents.begin(), parents.end(), 0); } int Find(int x) { if (parents[x] == x) { return x; } return parents[x] = Find(parents[x]); } void Union(int x, int y) { int rx = Find(x), ry = Find(y); if (rx != ry) { if (sizes[rx] > sizes[ry]) { parents[ry] = rx; sizes[rx] += sizes[ry]; } else { parents[rx] = ry; sizes[ry] += sizes[rx]; } } } int GetSize(int x) { return sizes[x]; } }; class Solution { public: long long countPairs(int n, vector<vector<int>> &edges) { UnionFind uf(n); for (const auto &edge : edges) { uf.Union(edge[0], edge[1]); } long long res = 0; for (int i = 0; i < n; i++) { res += n - uf.GetSize(uf.Find(i)); } return res / 2; } };
146. LRU 缓存(哈希表+双向链表)
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。LRUCache 类：
LRUCache(int capacity) 以正整数 作为容量 capacity 初始化 LRU 缓存int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以O(1)的平均时间复杂度运行。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 struct DLinkedNode { int key, value; DLinkedNode* prev; DLinkedNode* next; DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {} DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {} }; class LRUCache { private: unordered_map<int, DLinkedNode*> cache; DLinkedNode* head; DLinkedNode* tail; int size; int capacity; public: LRUCache(int _capacity): capacity(_capacity), size(0) { // 使用伪头部和伪尾部节点 head = new DLinkedNode(); tail = new DLinkedNode(); head->next = tail; tail->prev = head; } int get(int key) { if (!cache.count(key)) { return -1; } // 如果 key 存在，先通过哈希表定位，再移到头部 DLinkedNode* node = cache[key]; moveToHead(node); return node->value; } void put(int key, int value) { if (!cache.count(key)) { // 如果 key 不存在，创建一个新的节点 DLinkedNode* node = new DLinkedNode(key, value); // 添加进哈希表 cache[key] = node; // 添加至双向链表的头部 addToHead(node); ++size; if (size > capacity) { // 如果超出容量，删除双向链表的尾部节点 DLinkedNode* removed = removeTail(); // 删除哈希表中对应的项 cache.erase(removed->key); // 防止内存泄漏 delete removed; --size; } } else { // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部 DLinkedNode* node = cache[key]; node->value = value; moveToHead(node); } } void addToHead(DLinkedNode* node) { node->prev = head; node->next = head->next; head->next->prev = node; head->next = node; } void removeNode(DLinkedNode* node) { node->prev->next = node->next; node->next->prev = node->prev; } void moveToHead(DLinkedNode* node) { removeNode(node); addToHead(node); } DLinkedNode* removeTail() { DLinkedNode* node = tail->prev; removeNode(node); return node; } };
421. 数组中两个数的最大异或值(字典树/前缀树)
给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < 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 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 struct Trie { // 左子树指向表示 0 的子节点 Trie* left = nullptr; // 右子树指向表示 1 的子节点 Trie* right = nullptr; Trie() {} }; class Solution { private: // 字典树的根节点 Trie* root = new Trie(); // 最高位的二进制位编号为 30 static constexpr int HIGH_BIT = 30; public: void add(int num) { Trie* cur = root; for (int k = HIGH_BIT; k >= 0; --k) { int bit = (num >> k) & 1; if (bit == 0) { if (!cur->left) { cur->left = new Trie(); } cur = cur->left; } else { if (!cur->right) { cur->right = new Trie(); } cur = cur->right; } } } int check(int num) { Trie* cur = root; int x = 0; for (int k = HIGH_BIT; k >= 0; --k) { int bit = (num >> k) & 1; if (bit == 0) { // a_i 的第 k 个二进制位为 0，应当往表示 1 的子节点 right 走 if (cur->right) { cur = cur->right; x = x * 2 + 1; } else { cur = cur->left; x = x * 2; } } else { // a_i 的第 k 个二进制位为 1，应当往表示 0 的子节点 left 走 if (cur->left) { cur = cur->left; x = x * 2 + 1; } else { cur = cur->right; x = x * 2; } } } return x; } int findMaximumXOR(vector<int>& nums) { int n = nums.size(); int x = 0; for (int i = 1; i < n; ++i) { // 将 nums[i-1] 放入字典树，此时 nums[0 .. i-1] 都在字典树中 add(nums[i - 1]); // 将 nums[i] 看作 ai，找出最大的 x 更新答案 x = max(x, check(nums[i])); } return x; } };
微信
支付宝
