分发糖果 n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。 你需要按照以下要求，给这些孩子分发糖果
每个孩子至少分配到 1 个糖果 相邻两个孩子评分更高的孩子会获得更多的糖果。 请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目
解题思路：
初始化变量作用：
pre记录上一个数的大小，inc记录递增数列的长度，dec记录递减数列的长度。
默认情况下，将数组作为递增数列看待，所以pre = 1， inc = 1， dec = 0。
当前元素大于等于上一位元素的时候，为递增数列，此时初始化递减数列的长度 = 0，计算pre的大小，pre的大小有一下几种情况
如果元素大于上一位元素，说明为严格递增，此时元素可以接受的最小赋值为pre+1
如果元素等于上一位元素，当前元素可以不需要比上一位高，可以接受的最小赋值为1
当前元素小于上一位元素的时候，数列转为递减数列，该数列中的加值dec从1开始递增
每次新增的一位元素可以接受的最小赋值为1，但是dec（递减数列的长度）数列中的每一位都需要+1，所以最后的ret需要加上dec
如果dec超过inc，说明转折点（也就是最高点）的原先高度已经不足以支撑新的递减数列，所以需要额外+1
pre需要置为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 class Solution {public : int candy (vector<int >& ratings) int pre = 1 , inc = 1 , dec = 0 ; int n = ratings.size (); int ret = 1 ; for (int i = 1 ;i < n;i++){ if (ratings[i] >= ratings[i - 1 ]){ dec = 0 ; pre = ratings[i] == ratings[i - 1 ] ? 1 : pre + 1 ; ret += pre; inc = pre; }else { dec++; if (dec == inc){ dec++; } ret += dec; pre = 1 ; } } return ret; } };
文本左右对齐 给定一个单词数组 words 和一个长度 maxWidth ，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。 你应该使用 “贪心算法” 来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ‘ ‘ 填充，使得每行恰好有 maxWidth 个字符。 要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数 文本的最后一行应为左对齐，且单词之间不插入额外的空格。 注意:
单词是指由非空格字符组成的字符序列。 每个单词的长度大于 0，小于等于 maxWidth。 输入单词数组 words 至少包含一个单词。
解题思路：
根本没用什么技巧，非常直接的解法
要求有点绕，归根结底还是笔者太菜了
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 : string MultipleEmpty (int n) { string s = "" ; for (int i = 0 ;i < n;i++){ s += " " ; } return s; } vector<string> fullJustify (vector<string>& words, int maxWidth) { vector<string> res; vector<string> DividedString; int n = words.size (); int curWidth = 0 ; for (int i = 0 ;i < n;i++){ DividedString.push_back (words[i]); curWidth += words[i].size (); if (i == n - 1 || curWidth + words[i + 1 ].size () + DividedString.size () > maxWidth ){ int empty = maxWidth - curWidth; int perEmpty, RemainEmpty; if (DividedString.size () != 1 ){ perEmpty = empty / (DividedString.size () - 1 ); RemainEmpty = empty % (DividedString.size () - 1 ); if (i == n - 1 ){ perEmpty = 1 ; RemainEmpty = 0 ; } }else { perEmpty = empty; RemainEmpty = 0 ; } string SingleLine = "" ; for (int j = 0 ;j < DividedString.size ();j++){ SingleLine += DividedString[j]; if (j < RemainEmpty) SingleLine += MultipleEmpty (perEmpty + 1 ); else if (j >= RemainEmpty && j < DividedString.size () - 1 ){ SingleLine += MultipleEmpty (perEmpty); }else if (DividedString.size () == 1 ){ SingleLine += MultipleEmpty (perEmpty); } if (i == n - 1 && j == DividedString.size () - 1 && DividedString.size () != 1 ){ SingleLine += MultipleEmpty (empty - DividedString.size () + 1 ); } } res.push_back (SingleLine); DividedString.clear (); curWidth = 0 ; } } return res; } };
串联所有单词的子串 给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。
例如，如果 words = [“ab”,”cd”,”ef”]， 那么 “abcdef”， “abefcd”，”cdabef”， “cdefab”，”efabcd”， 和 “efcdab” 都是串联子串。 “acdbef” 不是串联子串，因为他不是任何 words 排列的连接。 返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。
解题思路：
滑动窗口方算法
需要注意的条件为：words中的所有字符串长度相同。对于滑动窗口来说，我们每次将窗口往右滑动一格会破坏窗口内单词的连贯性，需要重新对窗口里的所有单词进行归纳和计数，时间复杂度大大增加。
因为，我们需要根据每个word的长度m，来存储多起点的滑动窗口，从0 ～ m-1 创建m个不同起点的滑动窗口。对于已经创建的滑动窗口，我们只需要每次向右滑动m个格子，删除最前端的word，加入最末端的一个word，即可不破坏窗口内单词的连贯性。
在创建滑动窗口后和向右移动m位后，我们将滑动窗口与words的哈希表进行对比，可以得到是否满足条件。
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 class Solution {public : vector<int > findSubstring (string s, vector<string>& words) { int n = words.size (), m = words[0 ].size (), len = n * m; vector<int > ret; if (s.size () < len) return {}; unordered_map<string, int > key; for (string& word : words){ key[word]++; } vector<unordered_map<string, int >> dWindow (m); for (int i = 0 ;i < m && i + len <= s.size ();i++){ for (int j = i;j < i + len;j += m){ string str = s.substr (j, m); dWindow[i][str]++; } if (dWindow[i] == key){ ret.push_back (i); } } for (int i = m;i + len <= s.size ();i++){ int r = i % m; string del = s.substr (i - m, m); string add = s.substr (i + len - m, m); if (--dWindow[r][del] == 0 ) dWindow[r].erase (del); dWindow[r][add]++; if (dWindow[r] == key){ ret.push_back (i); } } return ret; } };
接雨水 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
解题思路：
最简单的方法：直接使用left和right数组存储每个元素左右的最大值，然后再遍历数组得到每个格子的水量。
单调栈方法：使用一个单调栈存储遍历过的元素下标，当单调栈不为空且当前元素高度大于单调栈顶部高度时候，不断取出单调栈中的两个元素，得到一格可以接雨水的区域，计算宽高得到雨水量。
不太会解释，可以查看官方题解。
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 class Solution {public : int trap (vector<int >& height) stack<int > stk; int n = height.size (); int sum = 0 ; for (int i = 0 ;i < n;i++){ while (!stk.empty () && height[i] > height[stk.top ()]){ int p1 = stk.top (); stk.pop (); if (stk.empty ()) break ; int p2 = stk.top (); int h = min (height[p2], height[i]) - height[p1]; sum += (h * (i - p2 - 1 )); } stk.push (i); } return sum; } };
最小覆盖子串 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
解题思路：
使用滑动窗口
由于数组里面只有字母，所以可以提前创建两个大小为128的ASCII字符数组，用于比较子串内元素的个数。
先预设ansLeft为-1， ansRight为n（s的长度），在遍历的过程中，如果得到长度更小且满足条件的子串，则替换。
遍历：枚举s子串的右端点right， 如果子串涵盖了t，则不断地移动左端点直到子串不包含。在移动的期间，如果满足条件则更新最短子串的左右端点。
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 : bool isContain (int cnt_s[], int cnt_t []) for (int i = 'A' ; i <= 'Z' ; i++) { if (cnt_s[i] < cnt_t [i]) { return false ; } } for (int i = 'a' ; i <= 'z' ; i++) { if (cnt_s[i] < cnt_t [i]) { return false ; } } return true ; } string minWindow (string s, string t) { int n = s.size (); int cnt_s[128 ]{}; int cnt_t [128 ]{}; for (char c : t) { cnt_t [c]++; } int ansLeft = -1 , ansRight = n; int left = 0 ; for (int right = 0 ;right < n;right++){ cnt_s[s[right]]++; while (isContain (cnt_s, cnt_t )){ if (right - left < ansRight - ansLeft){ ansLeft = left; ansRight = right; } cnt_s[s[left]]--; left++; } } return ansLeft < 0 ? "" : s.substr (ansLeft, ansRight - ansLeft + 1 ); } };
K个一组翻转链表 给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
使用头插法，重要是创建一个虚拟头节点，然后理清楚插入的关系。
头插法比其他更简单一些：我们只需要确定一个pre节点（也就是每组的前一个节点）以及一个cur节点（每组的第一个节点）即可。
pre保持不变，先取出cur的next节点（tmp节点），然后我们需要将cur等效前进一位，也就是让cur的next指向tmp节点的next。接着我们将tmp插入到链表的头部，也就是pre的下一位。链表中插入一个元素的方法这边不过多赘述。
1 2 3 4 ListNode* tmp = cur->next; cur->next = tmp->next; tmp->next = pre->next; pre->next = tmp;
完成一个周期后，重要的两个元素：pre和cur需要更新。pre跳到cur，也就是下一组链表的前一个节点，cur直接进一位，变为下一组链表的第一个节点。
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 class Solution {public : ListNode* reverseKGroup (ListNode* head, int k) { int n = 0 ; ListNode* node = head; while (node){ n++; node = node->next; } if (n < k) return head; ListNode* dummy = new ListNode (-1 , head); ListNode* pre = dummy; ListNode* cur = head; for (int i = 0 ;i < n / k;i++){ for (int j = 0 ;j < k - 1 ;j++){ ListNode* tmp = cur->next; cur->next = tmp->next; tmp->next = pre->next; pre->next = tmp; } pre = cur; cur = cur->next; } return dummy->next; } };
二叉树中的最大路径和 二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
解题思路：
递归
在递归的过程中，我们将得到的结果分为这么两种：第一种是无法进入下一次递归的，也就是折线类型的。第二种是直线类型的，它可以作为下一次递归的量。这两种结果都可能是最后的结果，所以我们都要探讨。第一种我们使用一个外部的变量来存储更新它，第二种我们直接用函数的返回值来存储它。
对于第一种折线类型，我们使用当前节点的val+递归得到的左右两个子树的返回值（也就是两个子树的直线最大值）来获取。对于第二种直线类型，我们使用val+左右子树的最大值来获取。
需要注意的点：
在得到左右子树返回值的时候，如果比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 class Solution {public : int ret = INT_MIN; int getMaxSum (TreeNode* node) if (node == nullptr ) return 0 ; int leftGain = max (getMaxSum (node->left), 0 ); int rightGain = max (getMaxSum (node->right), 0 ); int NewSum = node->val + leftGain + rightGain; ret = max (ret, NewSum); return node->val + max (leftGain, rightGain); } int maxPathSum (TreeNode* root) getMaxSum (root); return ret; } };
合并K个升序链表 给你一个链表数组，每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中，返回合并后的链表。
解题思路：
用分治的方法进行合并
将 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 41 42 43 44 45 46 47 48 class Solution {public : ListNode* merge (ListNode* node1, ListNode* node2) { ListNode* newHead = new ListNode (-1 ); ListNode* pre = newHead; while (node1 != nullptr && node2 != nullptr ){ if (node1->val <= node2->val){ pre->next = node1; node1 = node1->next; }else { pre->next = node2; node2 = node2->next; } pre = pre->next; } if (node1 != nullptr ){ pre->next = node1; }else if (node2 != nullptr ){ pre->next = node2; } return newHead->next; } ListNode* mergeSort (vector<ListNode*>& lists, int left, int right) { if (left > right) return nullptr ; if (left == right) return lists[left]; int mid = left + (right - left) / 2 ; ListNode* leftNode = mergeSort (lists, left, mid); ListNode* rightNode = mergeSort (lists, mid + 1 , right); return merge (leftNode, rightNode); } ListNode* mergeKLists (vector<ListNode*>& lists) { int n = lists.size (); return mergeSort (lists, 0 , n - 1 ); } };
最长连续序列 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
解题思路：
重要的事这个需要实现时间复杂度为On的要求，如果我们按照最普通的思路，先排序再找最长的连续序列，那么时间复杂度就会超过On，具体的时间复杂度由使用的排序算法决定。
我们可以使用一个unordered_set来解决这个问题，首先，我们遍历整个数据，将所有的数据装载进set里面，顺便去重。
紧接着，我们遍历这个set取出元素，对于每个已经装进set的元素来说，我们只需要确认它是不是一段连续序列的开头就可以了，具体的方法为：我们遍历set取出num，然后在set里面查找是否有num-1这个元素的存在，如果有的话，说明我们现在遍历的这个num并不是连续序列的开头，我们可以直接忽略，如果是的话，进入下一步。
如果我们取出来的元素是连续序列的开头，我们可以在set里面查找这个元素的后续是否存在，也就是不断地将该元素+1（变量current），并在set中查找。最后得到一段连续序列以及它的长度，将该长度与现有的最长连续序列长度进行对比，更新结果。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution {public : int longestConsecutive (vector<int >& nums) unordered_set<int > numsSet; for (int num : nums){ numsSet.insert (num); } int longStreak = 0 ; for (const int & num : numsSet){ if (!numsSet.count (num - 1 )){ int current = num; int currentStreak = 1 ; while (numsSet.count (current + 1 )){ current += 1 ; currentStreak += 1 ; } longStreak = max (longStreak, currentStreak); } } return longStreak; } };
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public int longestConsecutive (int [] nums) { Set<Integer> num_set = new HashSet <Integer>(); for (int num : nums){ num_set.add(num); } int longestStreak = 0 ; for (int num : num_set){ if (!num_set.contains(num - 1 )){ int current = num; int currentStreak = 1 ; while (num_set.contains(current + 1 )){ current += 1 ; currentStreak += 1 ; } longestStreak = Math.max(longestStreak, currentStreak); } } return longestStreak; } }
最长公共子序列 给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。 例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
解题思路：
这道题需要使用动态规划的方法来解决。
我们需要得知，n长度的text1和m长度的text2之间，最多有多长的公共子序列，因此，可以将问题分解为text1[0:i]与text2[0:j]之间的公共子序列。
因此使用动态规划，转移状态方程式为:dp[i][j] = dp[i - 1][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 18 19 class Solution {public : int longestCommonSubsequence (string text1, string text2) int n = text1. size (), m = text2. size (); vector<vector<int >> dp (n + 1 , vector <int >(m + 1 )); for (int i = 1 ;i <= n;i++){ char c1 = text1. at (i - 1 ); for (int j = 1 ;j <= m;j++){ char c2 = text2. at (j - 1 ); if (c1 == c2){ dp[i][j] = dp[i - 1 ][j - 1 ] + 1 ; }else { dp[i][j] = max (dp[i - 1 ][j], dp[i][j - 1 ]); } } } return dp[n][m]; } };
动态规划 打家劫舍II 解题思路：
因为首尾相连，所以我们直接当作两个序列来处理，一个包含头一个包含尾
然后使用动态规划，dp[i - start] = max(dp[i - start - 1], dp[i - start - 2] + nums[i]);
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution {public : int robRange (vector<int >& nums, int start, int end) vector<int > dp (end - start + 1 , 0 ) ; dp[0 ] = nums[start]; dp[1 ] = max (nums[start + 1 ], nums[start]); for (int i = start + 2 ;i <= end;i++){ dp[i - start] = max (dp[i - start - 1 ], dp[i - start - 2 ] + nums[i]); } return dp[end - start]; } int rob (vector<int >& nums) int n = nums.size (); if (n == 1 ) return nums[0 ]; else if (n == 2 ) return max (nums[0 ], nums[1 ]); return max (robRange (nums, 0 , n - 2 ), robRange (nums, 1 , n-1 )); } };
最长回文子串 给你一个字符串 s，找到 s 中最长的 回文 子串。
解题思路：
同样是使用动态规划的方法来解决。
使用一个二维数组来表示字符串中，start与end之间的字符串是否是一个回文子串，如果是的话则标记为true。
首先我们需要列举出可能的回文子串的长度，从2到n遍历。
转移状态方程式为：dp[left][left + L - 1] = dp[left + 1][left + L - 2];
对于首尾两个字符相等的情况，只需要分成两种情况，一种是L只有2，那么我们可以直接设置为true，一种是扣除首尾后dp数组对应元素仍然为true，此时为回文子串。
每次遍历中更新最大回文子串。
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 : string longestPalindrome (string s) { int n = s.size (); int maxStart = 0 ; int maxEnd = 0 ; int maxLen = 1 ; vector<vector<bool >> dp (n, vector <bool >(n, false )); for (int i = 0 ;i < n;i++){ dp[i][i] = true ; } for (int l = 2 ;l <= n;l++){ for (int left = 0 ;left <= n - l;left++){ if (s[left] == s[left + l - 1 ]){ if (l == 2 ) dp[left][left + l - 1 ] = true ; else { dp[left][left + l - 1 ] = dp[left + 1 ][left + l - 2 ]; } } if (dp[left][left + l - 1 ] && l > maxLen){ maxStart = left; maxEnd = left + l - 1 ; maxLen = l; } } } return s.substr (maxStart, maxLen); } };
