给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。
说明：
分隔时可以重复使用字典中的单词。
写了一个递归。。但是超时了
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 : vector<string> ret; int noWhitespaceStrLen (string s) int ret = s.length (); for (auto x : s) if (x == ' ' ) ret--; return ret; } void recur (int start, int end, const string& s, const set<string>& wordDic, string cur) if (end == s.length ()) { if (noWhitespaceStrLen (cur) >= s.length ()) ret.push_back (cur); return ; } string subst = s.substr (start, end-start+1 ); if (wordDic.count (subst) != 0 ) { recur (end+1 , end+1 , s, wordDic, cur + (cur.length () == 0 ? subst : " " + subst)); } recur (start, end+1 , s, wordDic, cur); } vector<string> wordBreak (string s, vector<string>& wordDict) { set<string> wordDic (wordDict.begin(), wordDict.end()) ; recur (0 , 0 , s, wordDic, "" ); return ret; } };
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 : vector<string> wordBreak (string s, vector<string>& wordDict) { unordered_set<string> dict (wordDict.begin(), wordDict.end()) ; vector<string> res; return backtrack (s, 0 , dict); } private : unordered_map<int , vector<string>> memo; vector<string> backtrack (string& s, int start, unordered_set<string>& dict) { if (start == s.size ()) { return {"" }; } if (memo.count (start)) { return memo[start]; } vector<string> res; for (int i = start; i < s.size (); i++) { auto prefix = s.substr (start, i - start + 1 ); if (dict.count (prefix)) { auto suffixes = backtrack (s, i + 1 , dict); for (const auto & suffix : suffixes) { auto str = prefix; if (!suffix.empty ()) { str += ' ' + suffix; } res.push_back (str); } } } memo[start] = res; return memo[start]; } };
所以需要记忆化。。。
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 : vector<int > intersection (vector<int >& nums1, vector<int >& nums2) { sort (nums1.begin (), nums1.end ()); sort (nums2.begin (), nums2.end ()); auto p1 = nums1.begin (), p2 = nums2.begin (); vector<int > ret; while (p1 != nums1.end () && p2 != nums2.end ()) { if (*p1 == *p2) { int tmp = *p1; ret.push_back (tmp); while (p1 != nums1.end () && *p1 == tmp) p1++; while (p2!= nums2.end () && *p2 == tmp) p2++; continue ; } if (*p1 < *p2) { p1++; continue ; } if (*p2 < *p1) { p2++; continue ; } } return ret; } };
给定一个整数数组 A，如果它是有效的山脉数组就返回 true，否则返回 false。
让我们回顾一下，如果 A 满足下述条件，那么它是一个山脉数组：
A.length >= 3
1 2 3 4 5 6 7 8 9 10 11 12 class Solution {public : bool validMountainArray (vector<int >& A) if (A.size () < 3 ) return false ; auto ABegin = A.begin (), AEnd = A.end (); auto f = ABegin, b = AEnd-1 ; while (f+1 !=AEnd && *(f+1 ) > *f) f++; while (b-1 != ABegin && *(b-1 ) > *b) b--; return (f==b && f!=ABegin && b != AEnd-1 ); } };
给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：
每次转换只能改变一个字母。
如果不存在这样的转换序列，返回 0。
双向bfs。主要是要读懂31行以下的部分，实际上是双向的BFS
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 class Solution {public : int ladderLength (string beginWord, string endWord, vector<string>& wordList) unordered_set<string> wordSet (wordList.begin(),wordList.end()) ; unordered_set<string> beginSet{beginWord}; unordered_set<string> endSet{endWord}; int res = 2 ; if (!wordSet.count (endWord)) return 0 ; while (!beginSet.empty ()) { for (auto & word:beginSet) { wordSet.erase (word); } unordered_set<string> nextSet; for (auto & word : beginSet) { for (int i = word.size ()-1 ; i>=0 ;i--) { string s = word; for (char j = 'a' ; j <='z' ;j++) { s[i] = j ; if (!wordSet.count (s)) continue ; if (endSet.count (s)) return res; nextSet.insert (s); } } } if (nextSet.size () < endSet.size ()) { beginSet = nextSet; } else { beginSet = endSet; endSet = nextSet; } res++; } return 0 ; } };
给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。
如果存在多个数字二进制中 1 的数目相同，则必须将它们按照数值大小升序排列。
请你返回排序后的数组。
1 2 3 4 5 6 7 8 9 10 11 12 class Solution {public : vector<int > sortByBits (vector<int >& arr) { auto proj = [](int x) { return pair{__builtin_popcount(x), x}; }; sort (begin (arr), end (arr), [&](int a, int b) {return proj (a) < proj (b);}); return arr; } };
给出一个无重叠的 ，按照区间起始端点排序的区间列表。
在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
示例 1：
输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
示例 2：
输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。
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<vector<int >> insert (vector<vector<int >>& intervals, vector<int >& newInterval) { vector<int > head, end; vector<vector<int >> ret; for (auto interval : intervals) { head.push_back (interval[0 ]); end.push_back (interval[1 ]); } head.push_back (newInterval[0 ]); sort (head.begin (), head.end ()); end.push_back (newInterval[1 ]); sort (end.begin (), end.end ()); for (int i = 0 ; i < head.size (); i++) { vector<int > tmp (2 ) ; tmp[0 ] = head[i]; while (i+1 != head.size () && end[i] >= head[i+1 ]) i++; tmp[1 ] = end[i]; ret.push_back (tmp); } return ret; } };
这个解法想到时很妙，但是实现起来复杂度稍高
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
动态规划
1 2 3 4 5 6 7 8 9 10 11 class Solution {public : int maxProfit (vector<int >& prices) int buy = -prices[0 ], notBuy = 0 ; for (int i = 1 ; i < prices.size (); i++) { buy = max (notBuy-prices[i],buy); notBuy = max (notBuy, buy+prices[i]); } return notBuy; } };
我们有一个由平面上的点组成的列表 points。需要从中找出 K 个距离原点 (0, 0) 最近的点。
（这里，平面上两点之间的距离是欧几里德距离。）
你可以按任何顺序返回答案。除了点坐标的顺序之外，答案确保是唯一的。
大根堆
C++中的优先队列是大根堆，故我们可以利用这一特性。空间复杂度为O(K)，时间复杂度为O(nlogK)，因为单次插入和推出的复杂度为O(logK)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 typedef pair<int , int > P;class Solution {public : vector<vector<int >> kClosest (vector<vector<int >>& points, int K) { priority_queue<P> q; for (int i = 0 ; i < K; i++) { q.emplace (pow (points[i][0 ], 2 ) + pow (points[i][1 ], 2 ), i); } int n = points.size (); for (int i = K; i < n; i++) { int dist = pow (points[i][0 ], 2 ) + pow (points[i][1 ], 2 ); if (dist < q.top ().first) { q.pop (); q.emplace (dist, i); } } vector<vector<int >> ret; while (!q.empty ()) { ret.push_back (points[q.top ().second]); q.pop (); } return ret; } };
快速排序
弄清原理就很简单，时间复杂度为O(N)，空间复杂度为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 typedef pair<int , int > P;class Solution {public : vector<vector<int >> quickSelect (vector<vector<int >> &points, int lo, int hi, int idx) { if (lo > hi) return vector<vector<int >>(0 , vector <int >(0 )); int j = partition (points, lo, hi); if (j == idx) return vector<vector<int >>(points.begin (), points.begin ()+idx+1 ); return j < idx ? quickSelect (points, j+1 , hi, idx) : quickSelect (points, lo, j-1 , idx); } int partition (vector<vector<int >> &points, int lo, int hi) vector<int > v = points[lo]; int dist = pow (v[0 ], 2 ) + pow (v[1 ], 2 ); int i = lo, j = hi+1 ; while (true ) { while (++i <= hi && (pow (points[i][0 ], 2 ) + pow (points[i][1 ], 2 )) < dist); while (--j >= lo && (pow (points[j][0 ], 2 ) + pow (points[j][1 ], 2 )) > dist); if (i >= j) break ; swap (points[i], points[j]); } points[lo] = points[j]; points[j] = v; return j; } vector<vector<int >> kClosest (vector<vector<int >>& points, int K) { return quickSelect (points, 0 , points.size ()-1 , K-1 ); } };
实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须原地修改，只允许使用额外常数空间。
通过两次遍历的方式解题。
对于本题来说，序列元素都是整数，所以将序列join后的数字大小就是我们说的“字典序”，故我们只需要从后往前找到一个相邻的升序对，将其反过来，肯定满足newValue>oldValue，但是又要求增加的幅度是最小的。例如"1342"的下一个应该是"1423"而不是"1432"，故对于升序对的第二个元素及其后面的序列需要进行sort，使其升序排列。但是在这个地方我们容易发现，这个“子序列”一定是降序的，我们使用reverse即可，并且降低了排序的复杂度。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution {public : void nextPermutation (vector<int >& nums) int i = nums.size () - 2 ; while (i >= 0 && nums[i] >= nums[i + 1 ]) { i--; } if (i >= 0 ) { int j = nums.size () - 1 ; while (j >= 0 && nums[i] >= nums[j]) { j--; } swap (nums[i], nums[j]); } reverse (nums.begin () + i + 1 , nums.end ()); } };
给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。
对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。
你可以返回任何满足上述条件的数组作为答案。
很简单的一道题，因为确定了一半奇一半偶，那么如果当前位置正确，那么往后移即可，如果不正确，可以直接向
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution {public : vector<int > sortArrayByParityII (vector<int >& A) { for (int i = 0 ; i < A.size () - 1 ; i++) { if ((A[i] & 1 ) != (i & 1 )) { for (int j = i + 1 ; j < A.size (); j++) { if ((A[j] & 1 ) != (j & 1 ) && ((i xor j) & 1 ) == 1 ) { swap (A[i], A[j]); break ; } } } } return A; } };
假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对 (h, k) 表示，其中 h 是这个人的身高，k 是应该排在这个人前面且身高大于或等于 h 的人数。 例如：[5,2] 表示前面应该有 2 个身高大于等于 5 的人，而 [5,0] 表示前面不应该存在身高大于等于 5 的人。
编写一个算法，根据每个人的身高 h 重建这个队列，使之满足每个整数对 (h, k) 中对人数 k 的要求。
示例：
输入：[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution {public : vector<vector<int >> reconstructQueue (vector<vector<int >>& people) { sort (people.begin (), people.end (), [](const vector<int > &a, const vector<int > &b) { return (a[0 ] == b[0 ] ? a[1 ] < b[1 ] : a[0 ] > b[0 ]) ; }); list<vector<int >> q; for (int i = 0 ; i < people.size (); i++) { int j = people[i][1 ]; auto it = q.begin (); while (j--) it++; q.insert (it, people[i]); } return vector<vector<int >> (q.begin (), q.end ()); } };
给出 R 行 C 列的矩阵，其中的单元格的整数坐标为 (r, c)，满足 0 <= r < R 且 0 <= c < C。
另外，我们在该矩阵中给出了一个坐标为 (r0, c0) 的单元格。
返回矩阵中的所有单元格的坐标，并按到 (r0, c0) 的距离从最小到最大的顺序排，其中，两单元格(r1, c1) 和 (r2, c2) 之间的距离是曼哈顿距离，|r1 - r2| + |c1 - c2|。（你可以按任何满足此条件的顺序返回答案。）
简单题，直接BFS就可以
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 class Solution {public : typedef pair<int , int > P; vector<vector<int >> allCellsDistOrder (int R, int C, int r0, int c0) { queue<P> next; vector<vector<int >> gone (R, vector <int >(C)), ret; int li[4 ] = {-1 , 1 , 0 , 0 }; int co[4 ] = {0 , 0 , 1 , -1 }; next.push (P (r0, c0)); gone[r0][c0] = 1 ; while (!next.empty ()) { P p = next.front (); next.pop (); int i = p.first; int j = p.second; vector<int > tmp{i,j}; ret.push_back (tmp); for (int k = 0 ; k < 4 ; k++) { int newi = i + li[k]; int newj = j + co[k]; if (newi >= 0 && newi < R && newj >= 0 && newj < C && !gone[newi][newj]) { next.push (P (newi, newj)); gone[newi][newj] = 1 ; } } } return ret; } };
详情比较长。。。直接去网站看比较好。
这道题就是直接循环解就好了
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 canCompleteCircuit (vector<int >& gas, vector<int >& cost) int n = gas.size (); int i = 0 ; while (i < n) { int sumOfGas = 0 , sumOfCost = 0 ; int cnt = 0 ; while (cnt < n) { int j = (i + cnt) % n; sumOfGas += gas[j]; sumOfCost += cost[j]; if (sumOfCost > sumOfGas) { break ; } cnt++; } if (cnt == n) { return i; } else { i = i + cnt + 1 ; } } return -1 ; } };
但是也有计算总油量和总消耗的方法。这个解有空间复杂度为1的方法，但是为了方便理解，就用了一个数组。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution {public : int canCompleteCircuit (vector<int >& gas, vector<int >& cost) int len = gas.size (); vector<int > arr (len, 0 ) ; for (int i = 0 ; i < len; i++) { arr[i] = gas[i] - cost[i] + (i == 0 ? 0 : arr[i-1 ]); } if (arr[len-1 ] >= 0 ) { int min = arr[0 ]; int mIdx = 0 ; for (int i = 1 ; i < len; i++) { if (min > arr[i]) {mIdx = i; min = arr[i];} } return (mIdx+1 )%len; } else { return -1 ; } } };
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution {public : void moveZeroes (vector<int >& nums) int i, j; i = j = 0 ; while (j < nums.size ()) { if (nums[j]) { if (j > i) { nums[i] = nums[j]; nums[j] = 0 ; } i++; } 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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 class Solution {public : void insert (ListNode *from, ListNode *to, ListNode *pre) if (pre == to) return ; pre->next = from->next; from->next = to->next; to->next = from; return ; } ListNode* insertionSortList (ListNode* head) { if (!head) return nullptr ; ListNode myHead (INT_MIN) ; myHead.next = head; int len = 0 ; ListNode *p, *q, *pre; q = pre = myHead.next; p = nullptr ; q = q->next; while (q != nullptr ) { if (q->val < pre->val) { p = &myHead; while (p->next->val < q->val) p = p->next; insert (q, p, pre); q = pre->next; } else { pre = q; q = q->next; } } return myHead.next; } };
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
进阶：
你可以在 O(n 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 41 42 43 44 class Solution {public : ListNode* sortList (ListNode* head) { if (!head || !head->next) { return head; } ListNode *fast = head->next, *slow = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } ListNode *tmp = slow->next; slow->next = nullptr ; ListNode *left = sortList (head); ListNode *right = sortList (tmp); ListNode *h = new ListNode (); ListNode *res = h; while (left && right) { if (left->val < right->val) { h->next = left; left = left->next; } else { h->next = right; right = right->next; } h = h->next; } h->next = left ? left : right; return res->next; } };
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
示例 1:
输入: s = “anagram”, t = “nagaram”
示例 2:
输入: s = “rat”, t = “car”
说明:
1 2 3 4 5 6 7 8 9 10 class Solution {public : bool isAnagram (string s, string t) vector<int > a (26 , 0 ) ; for (char x: s) a[x-'a' ]++; for (char x: t) a[x-'a' ]--; for (int x: a) if (x) return false ; return true ; } };
详情见网站。
对于这个题典型解法就是先排序再贪心。
首先按照气球的右边界排序，然后每次要射的气球都是本应射爆的气球的最右边界。
为什么选择最右边界，因为射爆Bi后，对于之后的气球Bk，若Bk的左边界小于或等于Bi的右边界，则Bk会被射爆，如果大于右边界，那么根据循环，之后Bk总会被直接射爆或者间接射爆(if b[1] > pos)，故该方法是可以的。
时间复杂度为排序和遍历O(nlogn + n) = O(nlogn)，空间复杂度为常数级。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution {public : int findMinArrowShots (vector<vector<int >>& points) if (points.empty ()) return 0 ; sort (points.begin (), points.end (), [](const vector<int > &a, const vector<int > &b) { return a[1 ] < b[1 ]; }); int pos = points[0 ][1 ]; int ret = 1 ; for (const vector<int >& b : points) { if (b[0 ] > pos) { ret++; pos = b[1 ]; } } return ret; } };
给出一个完全二叉树 ，求出该树的节点个数。
对于所有二叉树的解法
1 2 3 4 5 6 7 8 9 10 11 class Solution {public : int recur (TreeNode* root) if (!root) return 0 ; return recur (root->left) + recur (root->right) + 1 ; } int countNodes (TreeNode* root) return recur (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 class Solution {public : int levelCnt (TreeNode *root) int i = 0 ; TreeNode *node = root; while (node) { node = node->left; i++; } return i; } int recur (TreeNode* root, int lCnt) if (!root) return 0 ; if (!root->left) return 1 ; if (!root->right) return 2 ; int r = levelCnt (root->right); if (lCnt == r) { return 1 + pow (2 , lCnt) - 1 + recur (root->right, lCnt - 1 ); } else { return 1 + pow (2 , r) - 1 + recur (root->left, lCnt - 1 ); } } int countNodes (TreeNode* root) if (!root) return 0 ; if (!root->left) return 1 ; if (!root->right) return 2 ; int l = levelCnt (root->left), r = levelCnt (root->right); if (l == r) { return 1 + pow (2 , l) - 1 + recur (root->right, l - 1 ); } else { return 1 + pow (2 , r) - 1 + recur (root->left, l - 1 ); } } };
给你一个字符串 s ，请你根据下面的算法重新构造字符串：
从 s 中选出 最小 的字符，将它 接在 结果字符串的后面。
从 s 剩余字符中选出 最小的字符，且该字符比上一个添加的字符大，将它接在结果字符串后面。
重复步骤 2 ，直到你没法从 s 中选择字符。
从 s 中选出 最大 的字符，将它 接在 结果字符串的后面。
从 s 剩余字符中选出 最大 的字符，且该字符比上一个添加的字符小，将它 接在 结果字符串后面。
重复步骤 5 ，直到你没法从 s 中选择字符。
重复步骤 1 到 6 ，直到 s 中所有字符都已经被选过。
在任何一步中，如果最小或者最大字符不止一个 ，你可以选择其中任意一个，并将其添加到结果字符串。
请你返回将 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 class Solution {public : string sortString (string s) { string ret = "" ; int letterBarrel[26 ] = {}; int len = s.length (); for (char x : s) { letterBarrel[x-'a' ]++; } while (ret.length () != len) { int i = 0 ; while (i < 26 && ret.length () != len) { if (letterBarrel[i]) { ret += ('a' + i); letterBarrel[i]--; } i++; } i--; while (i >= 0 && ret.length () != len) { if (letterBarrel[i]) { ret += ('a' + i); letterBarrel[i]--; } i--; } } return ret; } };
用一个字母桶即可。
给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。
1 2 3 4 5 6 7 8 9 10 11 class Solution {public : int maximumGap (vector<int >& nums) sort (nums.begin (), nums.end ()); int max = 0 ; for (int i = 1 ; i < nums.size (); i++) { if (nums[i] - nums[i-1 ] > max) max = nums[i] - nums[i-1 ]; } return max; } };
给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。
为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -228 到 228 - 1 之间，最终结果不会超过 231 - 1 。
啪的一下就过了啊。本来开了两个map，于是乎时间空间复杂度都上去了，换成一个map找相反数就过了。
主要思想还是分组，把AB和CD分开，就从n4到了n2。然后哈希表存储即可
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 fourSumCount (vector<int >& A, vector<int >& B, vector<int >& C, vector<int >& D) const int N = A.size (); unordered_map<int , int > mapA; int ret = 0 ; for (int i = 0 ; i < N; i ++) { for (int j = 0 ; j < N; j ++) { if (mapA.find (A[i] + B[j]) == mapA.end ()) { mapA.insert (pair <int , int >(A[i] + B[j], 1 )); } else { mapA[A[i] + B[j]]++; } } } for (int i = 0 ; i < N; i ++) { for (int j = 0 ; j < N; j ++) { auto it = mapA.find (-(C[i] + D[j])); if (it != mapA.end ()) { ret += it->second; } } } return ret; } };
给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对 。
在上分治算法的时候，用归并排序做过类似的题目，当时求的是逆序对个数，也就是题目中没有2*，所以这道题可以用类似的思路。
但是我自己写的归并只能过38个。。然后就超时了。。很尴尬
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 class Solution {public : int reversePairsRecursive (vector<int >& nums, int left, int right) if (left == right) { return 0 ; } else { int mid = (left + right) / 2 ; int n1 = reversePairsRecursive (nums, left, mid); int n2 = reversePairsRecursive (nums, mid + 1 , right); int ret = n1 + n2; int i = left; int j = mid + 1 ; while (i <= mid) { while (j <= right && (long long )nums[i] > 2 * (long long )nums[j]) j++; ret += (j - mid - 1 ); i++; } vector<int > sorted (right - left + 1 ) ; int p1 = left, p2 = mid + 1 ; int p = 0 ; while (p1 <= mid || p2 <= right) { if (p1 > mid) { sorted[p++] = nums[p2++]; } else if (p2 > right) { sorted[p++] = nums[p1++]; } else { if (nums[p1] < nums[p2]) { sorted[p++] = nums[p1++]; } else { sorted[p++] = nums[p2++]; } } } for (int i = 0 ; i < sorted.size (); i++) { nums[left + i] = sorted[i]; } return ret; } } int reversePairs (vector<int >& nums) if (nums.size () == 0 ) return 0 ; return reversePairsRecursive (nums, 0 , nums.size () - 1 ); } };
给定由一些正数（代表长度）组成的数组 A，返回由其中三个长度组成的、面积不为零 的三角形的最大周长。
如果不能形成任何面积不为零的三角形，返回 0。
1 2 3 4 5 6 7 class Solution : def largestPerimeter (self, A: List [int ] ) -> int : arr = A.sort() for i in range (len (A) - 1 , 1 , -1 ): if A[i-2 ] + A[i-1 ] > A[i]: return sum (A[i-2 :i+1 ]) return 0
给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。
若可行，输出任意可行的结果。若不可行，返回空字符串。
解法一：
统计字符串中的字母个数，先排奇数位再排偶数位。
那么为什么不是先排偶数位再排奇数位，偶数位不是始终大于等于奇数位么？
理论上，并没有规定我们需要先排奇数/偶数，但是我们直接得到字符串的哈希表的话，没有按照值的大小排序，故可能出现先排一个小的，然后个数大的字母在奇数位和偶数位均有分布，直至相连，比如"baaba"，如果哈希表是{‘b’: 2, ‘a’: 3}，那么输出得到"babaa"，做法错误。
所以如果反过来，我们只要进行排序即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution : def reorganizeString (self, S: str ) -> str : if len (S) < 2 : return "" charCnts = dict (collections.Counter(S)) maxCnt = max (charCnts.values()) if maxCnt > (len (S) + 1 ) // 2 : return "" s = ["" ]*len (S) i, j = 0 , 1 for char, cnt in charCnts.items(): while cnt <= len (S) // 2 and cnt != 0 and j < len (S): s[j] = char cnt -= 1 j += 2 while cnt != 0 and i < len (S): s[i] = char cnt -= 1 i += 2 return '' .join(s)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 if len (S) < 2 : return "" charCnts = dict (collections.Counter(S)) maxCnt = max (charCnts.values()) if maxCnt > (len (S) + 1 ) // 2 : return "" charCnts = sorted (charCnts.items(), key=lambda x: x[1 ], reverse=True ) s = ["" ]*len (S) i, j = 0 , 1 for char, cnt in charCnts: while cnt <= (len (S) + 1 ) // 2 and cnt != 0 and i < len (S): s[i] = char cnt -= 1 i += 2 while cnt != 0 and j < len (S): s[j] = char cnt -= 1 j += 2 return '' .join(s)
运行速度是显然增加的了的，但是内存是类似的。
