avatar

Leetcode-202011

140. 单词拆分 II - 20201101

给定一个非空字符串 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}
};
// Recursion with memoization (AC)
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];
}
};

所以需要记忆化。。。

349. 两个数组的交集 - 20201102

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;
}
};

image-20201102233510661

941. 有效的山脉数组 - 20201103

给定一个整数数组 A,如果它是有效的山脉数组就返回 true,否则返回 false。

让我们回顾一下,如果 A 满足下述条件,那么它是一个山脉数组:

A.length >= 3
在 0 < i < A.length - 1 条件下,存在 i 使得:
A[0] < A[1] < … A[i-1] < A[i]
A[i] > A[i+1] > … > A[A.length - 1]

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);
}
};

127. 单词接龙 - 20201105

给定两个单词(beginWord 和 endWord)和一个字典,找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则:

每次转换只能改变一个字母。
转换过程中的中间单词必须是字典中的单词。
说明:

如果不存在这样的转换序列,返回 0。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的,且二者不相同。

双向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初始化,将wordlist内的元素全部拷贝到wordset中
unordered_set<string> beginSet{beginWord};//从头到尾的标记set
unordered_set<string> endSet{endWord};//从尾到头的标记set
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;
}
};

1356. 根据数字二进制下 1 的数目排序 - 20201106

给你一个整数数组 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;
}
};

57. 插入区间 - 29291107

给出一个无重叠的 ,按照区间起始端点排序的区间列表。

在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。

示例 1:

输入:intervals = [[1,3],[6,9]], newInterval = [2,5]
输出:[[1,5],[6,9]]

示例 2:

输入:intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出:[[1,2],[3,10],[12,16]]

解释:这是因为新的区间 [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;
}
};

这个解法想到时很妙,但是实现起来复杂度稍高

122. 买卖股票的最佳时机 II - 20201108

给定一个数组,它的第 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;
}
};

973. 最接近原点的 K 个点 - 20201109

我们有一个由平面上的点组成的列表 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);
}
};

31. 下一个排列 - 20201110

实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。

必须原地修改,只允许使用额外常数空间。

通过两次遍历的方式解题。

对于本题来说,序列元素都是整数,所以将序列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());
}
};

922. 按奇偶排序数组 II - 20201112

给定一个非负整数数组 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;
}
};

406. 根据身高重建队列 - 20201116

假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对 (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]]
输出:[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

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());

}
};

1030. 距离顺序排列矩阵单元格 - 20201117

给出 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};
// cout << "i & j :" << i << j << endl;
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));
// cout << "new: " << newi << newj << endl;
gone[newi][newj] = 1;
}
}
}
return ret;
}

};

134. 加油站 - 20201118

详情比较长。。。直接去网站看比较好。

这道题就是直接循环解就好了

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;
}
}
};

283. 移动零 - 20201119

给定一个数组 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++;
}
}
};

147. 对链表进行插入排序 - 20201120

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
// from 是要移动的 移动到to的后面
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;
// pre用于维护已经排序的数组
// p用来遍历
// q用来往后找
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;
// printf("now is at %d, pre is %d, head is %d\n", q->val, pre->val, myHead.next->val);
insert(q, p, pre);
q = pre->next;
// cout << "hhh" << endl;
// printf("inserted %d back to %d\n\n", q->val, p->val);
} else {
pre = q;
q = q->next;
}
}
return myHead.next;
}
};

148. 排序链表 - 20201121

给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。

进阶:

你可以在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序吗?

没有做进阶,就是归并排序了

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
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;
}
};

242. 有效的字母异位词 - 20201122

给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1:

输入: s = “anagram”, t = “nagaram”
输出: true

示例 2:

输入: s = “rat”, t = “car”
输出: false

说明:
你可以假设字符串只包含小写字母。

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;
}
};

452. 用最少数量的箭引爆气球 - 20201123

详情见网站。

对于这个题典型解法就是先排序再贪心。

首先按照气球的右边界排序,然后每次要射的气球都是本应射爆的气球的最右边界。

为什么选择最右边界,因为射爆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;
}
};

222. 完全二叉树的节点个数 - 20201124

给出一个完全二叉树,求出该树的节点个数。

对于所有二叉树的解法

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);
}
}
};

image-20201124222740082运行速度是显然增加的了的,但是内存是类似的。

1370. 上升下降字符串 - 20201125

给你一个字符串 s ,请你根据下面的算法重新构造字符串:

  1. 从 s 中选出 最小 的字符,将它 接在 结果字符串的后面。
  2. 从 s 剩余字符中选出 最小的字符,且该字符比上一个添加的字符大,将它接在结果字符串后面。
  3. 重复步骤 2 ,直到你没法从 s 中选择字符。
  4. 从 s 中选出 最大 的字符,将它 接在 结果字符串的后面。
  5. 从 s 剩余字符中选出 最大 的字符,且该字符比上一个添加的字符小,将它 接在 结果字符串后面。
  6. 重复步骤 5 ,直到你没法从 s 中选择字符。
  7. 重复步骤 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;
}
};

用一个字母桶即可。

164. 最大间距 - 20201126

给定一个无序的数组,找出数组在排序之后,相邻元素之间最大的差值。

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;
}
};

454. 四数相加 II - 20201127

给定四个包含整数的数组列表 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;
}
};

493. 翻转对 - 20201128

给定一个数组 nums ,如果 i < jnums[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);
}
};

976. 三角形的最大周长 - 20201129

给定由一些正数(代表长度)组成的数组 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

767. 重构字符串 - 20201130

给定一个字符串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)
文章作者: X Mεl0n
文章链接: http://www.zrzz.site/posts/bb5ea601/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 X Mεl0n | 随手记

评论