小扣出去秋游，途中收集了一些红叶和黄叶，他利用这些叶子初步整理了一份秋叶收藏集 leaves， 字符串 leaves 仅包含小写字符 r 和 y， 其中字符 r 表示一片红叶，字符 y 表示一片黄叶。
正值双节，力扣来了个开幕雷击，这种题还是有难度，从题解来分析吧。
动态规划
题解中有提到一个词 - 示性函数，其实就是一个结果为二元的函数，或者说布尔函数，这个问题不大，主要是对状态的分析，题解使用了f[i][j]来存储状态，最后取f[n-1][2]来作为return。
其中j可以为0、1、2，分别表示头部的红、中间的黄、和尾部的红，然后对每个j进行分析
j == 0，这个是最简单的，只需要把第i片叶子变成红色 ，题解的说明可能不太明了，其实这时候的意思是，f[i][j]是如果第i片叶子应该是头部红的话至此应该操作的次数。然后f[i][0] = f[i-1][0] + isYellow(i)，因为第i片叶子需要是头部红，所以前面的叶子也应该是头部红，加上的就是f[i-1][0]
j == 1，第i - 1片叶子既可以是头部红又可以是中间黄，取其中最小的就可以，直接写f[i][1] = f[i-1][0] + isRed(i)
j == 2，稍微复杂一些，第i - 1片叶子既可以是中间黄又可以是尾部红，但是不能是头部黄（即不能跳过中间黄的状态，题目要求3种状态各个至少为1），f[i][2] = min(f[i-1][1], f[i-1][2]) + isYellow(i)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution {public : int minimumOperations (string leaves) int n = leaves.size (); vector<vector<int >> f (n, vector <int >(3 )); f[0 ][0 ] = (leaves[0 ] == 'y' ); f[0 ][1 ] = f[0 ][2 ] = f[1 ][2 ] = INT_MAX; int isRed, isYellow; for (int i = 1 ; i < n; i++) { isRed = (leaves[i] == 'r' ); isYellow = (leaves[i] == 'y' ); f[i][0 ] = f[i-1 ][0 ] + isYellow; f[i][1 ] = min (f[i-1 ][0 ], f[i-1 ][1 ]) + isRed; if (i >= 2 ) f[i][2 ] = min (f[i-1 ][1 ], f[i-1 ][2 ]) + isYellow; } return f[n-1 ][2 ]; } };
但是空间复杂度为O(n)，可以简化状态存储，仔细查看上面的代码，所谓f[i-1]不过是上一次的f，并无必要开一个双重数组，使用一个vector<int>f(3)即可，使用以下代码。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution {public : int minimumOperations (string leaves) int n = leaves.size (); vector<int > f (3 ) ; f[0 ] = (leaves[0 ] == 'y' ); f[1 ] = f[2 ] = INT_MAX; int isRed, isYellow; for (int i = 1 ; i < n; i++) { isRed = (leaves[i] == 'r' ); isYellow = (leaves[i] == 'y' ); if (i >= 2 ) f[2 ] = min (f[1 ], f[2 ]) + isYellow; f[1 ] = min (f[0 ], f[1 ]) + isRed; f[0 ] += isYellow; } return f[2 ]; } };
771. 宝石与石头 - 20201002
给定字符串J 代表石头中宝石的类型，和字符串 S代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。
J 中的字母不重复，J 和 S中的所有字符都是字母。字母区分大小写，因此"a"和"A"是不同类型的石头。
示例 1:
输入: J = “aA”, S = “aAAbbbb”
示例 2:
输入: J = “z”, S = “ZZ”
注意:
S 和 J 最多含有50个字母。
水题，但是可以学习一下bitset，C++中的bitset类似封装过的bitmap，内存小，可以作为bool数组使用，(原来8位的bool现在只需要1位)。bitset不仅可以像一个int一样进行位运算，还有一些实例函数可以使用。
初始化方法: bitset<size> name(to_int_size)
size是指bitset长度，to_int_size是作为int的大小，
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 c.size () c.count () c.any () c.none () c.set () c.set (p) c.set (p, x) c.reset () c.reset (p) c.flip () c.flip (p) c.to_ulong () c.to_ullong () c.to_string ()
1 2 3 4 5 6 7 8 9 10 11 12 class Solution {public : int numJewelsInStones (string J, string S) bitset<128> arr (0 ) ; for (char i : J) arr[(int )i] = 1 ; int ret = 0 ; for (char i : S) if (arr[(int ) i]) ret++; return ret; } };
过于简单 不叙 （还忘记打卡了）
2. 两数相加 - 20201004
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
很直接的方法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 class Solution {public : ListNode* addTwoNumbers (ListNode* l1, ListNode* l2) { bitset<2> pend (0 ) ; int tmp = 0 ; if (!l1) return l2; if (!l2) return l1; ListNode* n1 = l1; ListNode* n2 = l2; while (n1 && n2) { n1 = n1->next; n2 = n2->next; } if (n2) { swap (l1, l2); } n1 = l1; n2 = l2; while (n1 && n2) { tmp = (pend[0 ]) ? 1 : 0 ; tmp += (n1->val + n2->val); if (tmp >= 10 ) { tmp %= 10 ; pend[0 ] = 1 ; } else { pend[0 ] = 0 ; } n1->val = tmp; n1 = n1->next; n2 = n2->next; } if (n1) { if (pend[0 ]) { while (n1->val == 9 ) { n1->val = 0 ; if (n1->next) n1 = n1->next; else pend[1 ] = 1 ; } if (n1 && !pend[1 ]) { n1->val += 1 ; } if (pend[1 ]) { n1->next = new ListNode (1 ); } } } else if (pend[0 ]) { n1 = l1; while (n1->next) n1 = n1->next; n1->next = new ListNode (1 ); } return l1; } };
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：
答案中不可以包含重复的四元组。
示例：
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
满足要求的四元组集合为：
本来用9月的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 class Solution {public : vector<vector<int >> fourSum (vector<int >& nums, int target) { vector<vector<int >> ret; if (nums.size () < 4 ) return ret; int size = nums.size (); sort (nums.begin (), nums.end ()); for (int i = 0 ; i < size - 3 ; i++) { if (target <= 0 && nums[i] > 0 ) break ; if (nums[i] + nums[i+1 ] + nums[i+2 ] + nums[i+3 ] > target) break ; if (nums[i] + nums[size-1 ] + nums[size-2 ] + nums[size-3 ] < target) continue ; if (i > 0 && nums[i] == nums[i-1 ]) continue ; for (int j = i + 1 ; j < size-2 ; j++) { if (nums[i] + nums[j] + nums[j+1 ] + nums[j+2 ] > target) break ; if (nums[i] + nums[j] + nums[size-1 ] + nums[size-2 ] < target) continue ; if (j > i + 1 && nums[j] == nums[j-1 ]) continue ; int start = j+1 , end = size-1 ; while (start < end) { int sum = nums[i] + nums[j] + nums[start] + nums[end]; if (sum < target) start++; else if (sum>target) end--; else { ret.push_back ({nums[i], nums[j], nums[start], nums[end]}); int last_start=start, last_end=end; while (start<end && nums[start] == nums[last_start]) start++; while (start<end && nums[end] == nums[last_end]) end--; } } } } return ret; } };
给定一个无向、连通的树。树中有 N 个标记为 0…N-1 的节点以及 N-1 条边 。
第 i 条边连接节点 edges[i][0] 和 edges[i][1] 。
返回一个表示节点 i 与其他所有节点距离之和的列表 ans。
示例 1:
输入: N = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
0
/ \
1 2
/|\
3 4 5
我们可以计算出 dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5)
今天这个题目很有意思，但同时也有一定难度，这个说是一个无向联通树，但也是可以用到图的方法来做
思路来自https://leetcode-cn.com/problems/sum-of-distances-in-tree/solution/shou-hua-tu-jie-shu-zhong-ju-chi-zhi-he-shu-xing-d/
首先解决一棵树的子树节点，到根节点的距离，是一个后序遍历的递归求和，由distSum和nodeNum两个数组完成，至于根节点的父节点以外的，可以利用父节点的后序遍历通过减法和加法就可以完成。
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 class Solution {public : int N; vector<vector<int >> graph; vector<int > nodeNum; vector<int > distSum; void postOrder (int root, int parent) vector<int > neighbors = graph[root]; for (auto neighbor : neighbors) { if (neighbor == parent) continue ; postOrder (neighbor, root); nodeNum[root] += nodeNum[neighbor]; distSum[root] += nodeNum[neighbor] + distSum[neighbor]; } } void preOrder (int root, int parent) vector<int > neighbors = graph[root]; for (auto neighbor : neighbors) { if (neighbor == parent) continue ; distSum[neighbor] = distSum[root] - 2 * nodeNum[neighbor] + N; preOrder (neighbor, root); } } vector<int > sumOfDistancesInTree (int N, vector<vector<int >>& edges) { this ->N = N; this ->graph.resize (N, vector <int >()); for (auto edge : edges) { graph[edge[0 ]].push_back (edge[1 ]); graph[edge[1 ]].push_back (edge[0 ]); } this ->nodeNum.resize (N, 1 ); this ->distSum.resize (N, 0 ); postOrder (0 , -1 ); preOrder (0 , -1 ); return this ->distSum; } };
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
示例:
输入: [2,0,2,1,1,0]
进阶：
一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗？
这个还算比较简单的，要么是空间换时间要么反过来就是按照进阶里的思路
1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution {public : void sortColors (vector<int >& nums) int len = nums.size (); int head = 0 , tail = len-1 ; vector<int > arr (len, 0 ) ; for (int i = 0 ; i < len; i++) { if (nums[i] == 0 ) arr[head++] = 0 ; else if (nums[i] == 2 ) arr[tail--] = 2 ; } while (head<=tail) arr[head++] = 1 ; nums = arr; } };
当然，利用循环不变量来设定两个边界，利用swap可以在一个数组中完成操作。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution {public : void sortColors (vector<int >& nums) int len = nums.size (); int head = 0 , tail = len; int i = 0 ; while (i < tail) { if (nums[i]==0 ) swap (nums[i++], nums[head++]); else if (nums[i] == 2 ) swap (nums[i], nums[--tail]); else i++; } } };
极为基础的一道题，但是发现了一个神奇的交换方法
1 2 3 s[i] ^= s[j]; s[j] ^= s[i]; s[i] ^= s[j];
很妙!
给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。
进阶：
你能用 O(1)（即，常量）内存解决此问题吗？
INT_MAX
但是这一种方法改变了链表的值，虽然能过，但是实际应用不大行
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution {public : bool hasCycle (ListNode *head) if (!head) return false ; ListNode* node = head; while (node->next != NULL && node->val != INT_MAX) { node->val = INT_MAX; node = node->next; } return (node->val == INT_MAX); } };
快慢指针
只要我比你跑得快，那么如果存在环，那我一定能追上你
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution {public : bool hasCycle (ListNode* head) if (head == nullptr || head->next == nullptr ) { return false ; } ListNode* slow = head; ListNode* fast = head->next; while (slow != fast) { if (fast == nullptr || fast->next == nullptr ) { return false ; } slow = slow->next; fast = fast->next->next; } return true ; } };
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。
昨天的题加大了难度。借给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
首先借一个图
我们先设置fast、slow和done指针从head出发（这里done指针先不动，作用在之后提到），那么fast的路程为a + b + n * (b + c) ，slow的路程为a + b，最后得到a = c + (n - 1) * (b + c)
那么我们有三个点需要进行证明
n >= 1
C(slow) == a + b
a = c + (n - 1) * (b + c)
第一点容易证明，既然fast追上了slow，那么一定是多跑了至少一圈的距离
第二点，假设fast需要走最大的距离追上slow，那么就是slow刚入环的时候，fast在slow的下一个结点上，那么2k - k = b + c - 1 => k =( b + c - 1) / 2，即slow走的距离连环的一半都不到，肯定是C(slow) = a + b而不是 a + (b + c) + b的
第三点，由设定条件和C(fast) = 2C(slow) => a + b + n * (b + c) = 2(a + b)可以得到证明
由于证明了第三点，在fast和slow相遇后，开头的done和slow开始移动，当done指针和slow指针相遇时，指向的便是入口结点。
如何证明呢，此时C(slow) = a + b + c + (n - 1) * (b + c) = a + n * (b + c)，即刚好走到环起始点。
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 : ListNode *detectCycle (ListNode *head) { if (!head) return nullptr ; ListNode *fast, *slow, *done; fast = slow = done = head; while (fast != nullptr ) { if (fast->next == nullptr ) return nullptr ; fast = fast->next->next; slow = slow->next; if (fast == slow) break ; } if (fast == nullptr ) return nullptr ; while (done != slow) { done = done->next; slow = slow->next; } return done; } };
都是动态规划，但是思路不一样。
第二种相对容易理解，但是第一种的背包等学了《背包九讲》再回过头看看吧。
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 class Solution {public : bool canPartition (vector<int >& nums) int len = nums.size (); if (len == 0 ) return false ; int sum = 0 ; for (auto i : nums) sum += i; if (sum & 1 ) return false ; int target = sum / 2 ; vector<vector<int >> dp (len, vector <int >(target+1 , 0 )); if (nums[0 ] <= target) dp[0 ][nums[0 ]] = true ; for (int i = 1 ; i < len; i++) { for (int j = 0 ; j <= target; j++) { dp[i][j] = dp[i-1 ][j]; if (nums[i] == j) { dp[i][j] = true ; continue ; } if (nums[i] < j) dp[i][j] = (dp[i-1 ][j] | dp[i-1 ][j-nums[i]]); } } return dp[len-1 ][target]; } };
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution {public : bool canPartition (vector<int >& nums) int sum = accumulate (nums.begin (), nums.end (), 0 ); if (sum & 1 ) return false ; unordered_set<int > dp ({ sum / 2 }) , tmp {}; for (int i : nums) { for (int j : dp) { if (i - j == 0 || j == 0 ) return true ; if (j - i < 0 || dp.find (j-i)!=dp.end ()) continue ; tmp.insert (j-i); } dp.insert (tmp.begin (), tmp.end ()); tmp.clear (); } return false ; } };
给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。
搜索树的中序遍历。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution {public : vector<int > arr; void inOrder (TreeNode* root) if (!root) return ; inOrder (root->left); arr.push_back (root->val); inOrder (root->right); } int getMinimumDifference (TreeNode* root) inOrder (root); int ret = INT_MAX; for (auto i = (arr.begin () + 1 ); i != arr.end (); i++) { ret = min (abs (*i - *(i-1 )), ret); } return ret; } };
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值 ，而是需要实际的进行节点交换。
简单题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution {public : ListNode* swapPairs (ListNode* head) { ListNode* hhead = new ListNode (0 ); hhead->next = head; ListNode* node = hhead, *node1, *node2; while (node->next && node->next->next) { node1 = node->next; node2 = node->next->next; node->next = node2; node1->next = node2->next; node2->next = node1; node = node1; } return hhead->next; } };
给定仅有小写字母组成的字符串数组 A，返回列表中的每个字符串中都显示的全部字符（包括重复字符）组成的列表。例如，如果一个字符在每个字符串中出现 3 次，但不是 4 次，则需要在最终答案中包含该字符 3 次。
你可以按任意顺序返回答案。
简单题
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 class Solution {public : vector<string> commonChars (vector<string>& A) { vector<int > tmp; vector<int > ret (26 , INT_MAX) ; vector<int > cnt (26 , 0 ) ; vector<string> sret; for (string i:A) { tmp = vector <int >(26 , 0 ); for (char x: i){ tmp[x-'a' ]++; } for (int i = 0 ; i < 26 ; i++) if (tmp[i] != 0 ) { cnt[i]++; if (ret[i] > tmp[i]) ret[i] = tmp[i]; } } int lenA = A.size (); for (int i = 0 ; i < 26 ; i++) { if (ret[i] != INT_MAX && cnt[i] == lenA) { for (int j = 0 ; j < ret[i]; j ++){ string a = "a" ; a[0 ] = i+'a' ; sret.push_back (a); } } } return sret; } };
给定一个完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
提示：
你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution {public : Node* connect (Node* root) { if (!root) return root; Node* lMost = root; while (lMost->left) { Node* head = lMost; while (head) { head->left->next = head->right; if (head->next) head->right->next = head->next->left; head = head->next; } lMost = lMost->left; } return root; } };
给定一个按非递减顺序排序的整数数组 A，返回每个数字的平方组成的新数组，要求也按非递减顺序排序
1 2 3 4 5 6 7 8 9 10 11 class Solution {public : vector<int > sortedSquares (vector<int >& A) { vector<int > ans; for (int num: A) { ans.push_back (num * num); } sort (ans.begin (), ans.end ()); return ans; } };
给定一个整数 n ，返回 n 皇后不同的解决方案的数量。
用三个int来作为bitset减少复杂度
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution {public : int totalNQueens (int n) return solve (n, 0 , 0 , 0 , 0 ); } int solve (int n, int row, int columns, int diagonals1, int diagonals2) if (row == n) { return 1 ; } else { int count = 0 ; int availablePositions = ((1 << n) - 1 ) & (~(columns | diagonals1 | diagonals2)); while (availablePositions != 0 ) { int position = availablePositions & (-availablePositions); availablePositions = availablePositions & (availablePositions - 1 ); count += solve (n, row + 1 , columns | position, (diagonals1 | position) << 1 , (diagonals2 | position) >> 1 ); } return count; } } };
给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。
注意：如果对空文本输入退格字符，文本继续为空。
这道题还比较简单，想到逆序的话就可以将空间复杂度控制在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 class Solution {public : bool backspaceCompare (string S, string T) int sSkipNum = 0 ; int tSkipNum = 0 ; int i = S.size () - 1 ; int j = T.size () - 1 ; while (1 ) { while (i >= 0 ) { if (S[i] == '#' ) sSkipNum++; else { if (sSkipNum > 0 ) sSkipNum--; else break ; } i--; } while (j >= 0 ) { if (T[j] == '#' ) tSkipNum++; else { if (tSkipNum > 0 ) tSkipNum--; else break ; } j--; } if (i < 0 || j < 0 ) break ; if (S[i] != T[j]) return false ; i--;j--; } if (i == -1 && j == -1 ) return true ; return false ; } };
给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
思路很简单
先把链表分为两半，然后把后一半翻转
再将两个链表Merge
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 class Solution {public : ListNode* findMid (ListNode* head) { ListNode* slow,* fast; slow = fast = head; while (fast->next && fast->next->next) { fast = fast->next->next; slow = slow->next; } return slow; } ListNode* reversedList (ListNode* node) { ListNode* pre = nullptr ; ListNode* cur = node; ListNode* tmp; while (cur) { tmp = cur->next; cur->next = pre; pre = cur; cur = tmp; } return pre; } void mergeList (ListNode* l1, ListNode* l2) ListNode *l1tmp, *l2tmp; while (l1 && l2) { l1tmp = l1->next; l2tmp = l2->next; l1->next = l2; l2->next = l1tmp; l1 = l1tmp; l2 = l2tmp; } } void reorderList (ListNode* head) if (!head) return ; ListNode* mid = findMid (head); ListNode* l1 = head, *l2 = mid->next; mid->next = nullptr ; l2 = reversedList (l2); mergeList (l1, l2); } };
你的朋友正在使用键盘输入他的名字 name。偶尔，在键入字符 c 时，按键可能会被长按，而字符可能被输入 1 次或多次。
你将会检查键盘输入的字符 typed。如果它对应的可能是你的朋友的名字（其中一些字符可能被长按），那么就返回 True。
超简单
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution {public : bool isLongPressedName (string name, string typed) if (name == typed) return true ; auto nameEnd = name.end (), typedEnd = typed.end (); if (*(nameEnd-1 ) != *(typedEnd-1 )) return false ; auto a = name.begin (), b = typed.begin (); while (a != nameEnd && b != typedEnd) { if (*a == *b) { a++; b++; } else if (*b == *(a-1 )) b++; else return false ; } return true ; } };
给定一个链表，删除链表的倒数第 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 class Solution {public : ListNode* removeNthFromEnd (ListNode* head, int n) { if (!head->next) { delete (head); return nullptr ; } ListNode *f, *s, *pre; pre = f = s = head; for (int i = 0 ; i < n-1 ; i++) f = f->next; while (f->next) { f = f->next; pre = s; s = s->next; } pre->next = s->next ? s->next : nullptr ; if (s == head) head = head->next; delete (s); return head; } }
请判断一个链表是否为回文链表。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 class Solution {public : ListNode* findMid (ListNode* head) { ListNode* slow,* fast; slow = fast = head; while (fast->next && fast->next->next) { fast = fast->next->next; slow = slow->next; } return slow; } ListNode* reversedList (ListNode* node) { ListNode* pre = nullptr ; ListNode* cur = node; ListNode* tmp; while (cur) { tmp = cur->next; cur->next = pre; pre = cur; cur = tmp; } return pre; } bool isPalindrome (ListNode* head) if (!head) return true ; ListNode* mid = findMid (head); ListNode *l1 = head, *l2 = mid->next; l2 = reversedList (l2); bool ret = true ; while (ret && l2) { if (l1->val != l2->val) return false ; l1=l1->next;l2=l2->next; } return true ; } };
当然，也可以在return前把列表再翻转回来，这里就没做了。
你将会获得一系列视频片段，这些片段来自于一项持续时长为 T 秒的体育赛事。这些片段可能有所重叠，也可能长度不一。
视频片段 clips[i] 都用区间进行表示：开始于 clips[i][0] 并于 clips[i][1] 结束。我们甚至可以对这些片段自由地再剪辑，例如片段 [0, 7] 可以剪切成 [0, 1] + [1, 3] + [3, 7] 三部分。
我们需要将这些片段进行再剪辑，并将剪辑后的内容拼接成覆盖整个运动过程的片段（[0, T]）。返回所需片段的最小数目，如果无法完成该任务，则返回 -1 。
Dp算法。。。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class ssSort {public : bool operator () (vector<int > a, vector<int > b) return (a[0 ] < b[0 ]); } }; class Solution {public : int videoStitching (vector<vector<int >>& clips, int T) for (int i = 0 ; i < clips.size (); i++) if (clips[i][0 ] == 0 && clips[i][1 ] >= T) return 1 ; sort (clips.begin (), clips.end (), ssSort ()); vector<int > dp (101 , 101 ) ; dp[0 ] = 0 ; for (int i = 0 ; i < clips.size (); i++) { int start = clips[i][0 ], end = clips[i][1 ]; for (int j = start + 1 ; j <= end; j++) dp[j] = min (dp[j], dp[start] + 1 ); } return dp[T] == 101 ? -1 : dp[T]; } };
我们把数组 A 中符合下列属性的任意连续子数组 B 称为 “山脉”：
B.length >= 3
给出一个整数数组 A，返回最长 “山脉” 的长度。
如果不含有 “山脉” 则返回 0。
是DP的思路，从左边和右边走一遍，找到“坡”最大的下标，返回两边的和减一，就是结果。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution {public : int longestMountain (vector<int >& A) int aLen = A.size (); if (aLen < 3 ) return 0 ; vector<int > arr1 (aLen, 1 ) , arr2 (aLen, 1 ) ; for (int i = 1 ; i < aLen; i++) arr1[i] = (A[i] > A[i-1 ] ? arr1[i-1 ] + 1 : 1 ); for (int i = aLen - 2 ; i >= 0 ; i--) arr2[i] = (A[i] > A[i+1 ] ? arr2[i+1 ] + 1 : 1 ); int ret = 0 ; for (int i = 1 ; i < aLen - 1 ; i++) if (arr1[i] > 1 && arr2[i] > 1 ) ret = max (ret, arr1[i] + arr2[i] - 1 ); return ret; } };
给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。
换而言之，对于每个 nums[i] 你必须计算出有效的 j 的数量，其中 j 满足 j != i 且 nums[j] < nums[i] 。
以数组形式返回答案。
直接暴力即可
1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution {public : vector<int > ret; vector<int > smallerNumbersThanCurrent (vector<int >& nums) { ret = vector <int >(nums.size (), 0 ); for (int i = 0 ; i < nums.size (); i++) for (int j = 0 ; j < nums.size (); j++) { if (nums[j] < nums[i]) ret[i]++; } return ret; } };
简单题，不过可以复习一下栈知识。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution {public : vector<int > preorderTraversal (TreeNode* root) { vector<int > ret; if (!root) return ret; stack<TreeNode*> s; TreeNode* node = root; s.push (node); while (!s.empty ()) { node = s.top (); s.pop (); ret.push_back (node->val); if (node->right) s.push (node->right); if (node->left) s.push (node->left); } return ret; } };
给你一个整数数组 arr，请你帮忙统计数组中每个数的出现次数。
如果每个数的出现次数都是独一无二的，就返回 true；否则返回 false。
简单题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution {public : bool uniqueOccurrences (vector<int >& arr) map<int , int > m; for (int i : arr) { auto it = m.find (i); if (it != m.end ()) (it->second)++; else m.insert (pair <int , int >(i, 1 )); } bitset<1000> b (0 ) ; for (auto i = m.begin (); i!=m.end (); i++) { if (b[i->second] == 0 ) b[i->second] = 1 ; else return false ; } return true ; } };
给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。
例如，从根到叶子节点路径 1->2->3 代表数字 123。
计算从根到叶子节点生成的所有数字之和。
一道简单的回溯
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 class Solution {public : int ret; vector<int > cur; void addToRet () int i = 0 ; for (int x:cur) { i = i * 10 + x; } ret += i; return ; } void dfs (TreeNode* root) if (!root) return ; cur.push_back (root->val); dfs (root->left); dfs (root->right); if (!root->left && !root->right) { addToRet (); } cur.pop_back (); return ; } int sumNumbers (TreeNode* root) if (!root) return 0 ; dfs (root); return ret; } }; class Solution {public : int dfs (TreeNode* root, int i) if (!root) return 0 ; i = i*10 + root->val; if (!root->left && !root->right) return i; return dfs (root->left, i) + dfs (root->right, i); } int sumNumbers (TreeNode* root) if (!root) return 0 ; return dfs (root, 0 ); } };
给定一个包含 0 和 1 的二维网格地图，其中 1 表示陆地 0 表示水域。
网格中的格子水平和垂直方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。
岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。
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 class Solution {public : int calCount (const vector<vector<int >>& grid, int i, int j, int W, int L) int tmp = 0 ; if (i > 0 ){ if (!grid[i-1 ][j]) tmp++; } else tmp++; if (i < W-1 ){ if (!grid[i+1 ][j]) tmp++; } else tmp++; if (j > 0 ){ if (!grid[i][j-1 ]) tmp++; } else tmp++; if (j < L-1 ){ if (!grid[i][j+1 ]) tmp++; } else tmp++; return tmp; } int islandPerimeter (vector<vector<int >>& grid) if (grid.empty ()) return 0 ; int W = grid.size (), L = grid[0 ].size (); int ret = 0 ; for (int i = 0 ; i < W; i++) for (int j = 0 ; j < L; j++) if (grid[i][j]) ret += calCount (grid, i, j, W, L); return ret; } };
