给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。
说明：
分隔时可以重复使用字典中的单词。
写了一个递归。。但是超时了
class Solution {public :truevector <string > ret; trueint noWhitespaceStrLen (string s) truetrueint ret = s.length(); truetruefor (auto x : s) truetruetrueif (x == ' ' ) ret--; truetruereturn ret; true} truevoid recur (int start, int end, const string & s, const set <string >& wordDic, string cur) truetrueif (end == s.length()) { if (noWhitespaceStrLen(cur) >= s.length()) truetruetruetrueret.push_back(cur); truetruetruereturn ; truetrue} truetruestring subst = s.substr(start, end-start+1 ); truetrueif (wordDic.count(subst) != 0 ) { truetruetruerecur(end+1 , end+1 , s, wordDic, cur + (cur.length() == 0 ? subst : " " + subst)); truetrue} truetruerecur(start, end+1 , s, wordDic, cur); true} truevector <string > wordBreak(string s, vector <string >& wordDict) { truetrueset <string > wordDic(wordDict.begin(), wordDict.end()); truetruerecur(0 , 0 , s, wordDic, "" ); truetruereturn ret; true} };
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]; } };
所以需要记忆化。。。
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
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
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 的数目相同，则必须将它们按照数值大小升序排列。
请你返回排序后的数组。
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] 重叠。
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 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
动态规划 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)。
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)
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即可，并且降低了排序的复杂度。
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 也是偶数。
你可以返回任何满足上述条件的数组作为答案。
很简单的一道题，因为确定了一半奇一半偶，那么如果当前位置正确，那么往后移即可，如果不正确，可以直接向
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]]
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就可以
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; } };
详情比较长。。。直接去网站看比较好。
这道题就是直接循环解就好了
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的方法，但是为了方便理解，就用了一个数组。
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 移动到数组的末尾，同时保持非零元素的相对顺序。
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++; } } };
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) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
没有做进阶，就是归并排序了
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”
说明:
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)，空间复杂度为常数级。
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; } };
给出一个完全二叉树 ，求出该树的节点个数。
对于所有二叉树的解法
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); } };
但是也可以根据完全二叉树的性质：子树必为一颗完全二叉树和一颗满二叉树
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 中字符重新排序后的 结果字符串 。
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; } };
用一个字母桶即可。
给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。
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。然后哈希表存储即可
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个。。然后就超时了。。很尴尬
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。
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”，做法错误。
所以如果反过来，我们只要进行排序即可。
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)
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)
运行速度是显然增加的了的，但是内存是类似的。