LeetCode + 《剑指Offer II》刷题笔记。
贪心
870 Advantage Shuffle
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[] advantageCount(int[] nums1, int[] nums2) {
int n=nums1.length;
TreeMap<Integer,Integer> map=new TreeMap<>();
for(int num:nums1){
map.put(num,map.getOrDefault(num,0)+1);
}
int[] ans=new int[n];
for(int i=0;i<n;i++){
Integer higher=map.higherKey(nums2[i]);
if(higher==null){
higher=map.firstKey();
}
ans[i]=higher;
if(map.get(higher)==1){
map.remove(higher);
}else{
map.put(higher,map.get(higher)-1);
}
}
return ans;
}
}
|
优化：
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<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
int n=nums1.size();
vector<int> idx1(n),idx2(n);
for(int i=0;i<n;i++){
idx1[i]=i;
idx2[i]=i;
}
sort(idx1.begin(),idx1.end(),[&](int i,int j){return nums1[i]<nums1[j];});
sort(idx2.begin(),idx2.end(),[&](int i,int j){return nums2[i]<nums2[j];});
vector<int> res(n);
int left=0,right=n-1;
for(int i=0;i<n;i++){
if(nums1[idx1[i]]>nums2[idx2[left]]){
res[idx2[left]]=nums1[idx1[i]];
left++;
}else{
res[idx2[right]]=nums1[idx1[i]];
right--;
}
}
return res;
}
};
|
- 时间复杂度：O(nlogn)
- 空间复杂度：O(n)
1328 Break a Palindrome
贪心：找回文串中第一个大于’a’的字符，替换成’a’。如果没有，说明整串都是a，最后一个换成b。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution {
public:
string breakPalindrome(string palindrome) {
int len=palindrome.length();
if(len==1) return "";
for(int i=0;i<len/2;i++){
if(palindrome[i]>'a'){
palindrome[i]='a';
return palindrome;
}
}
palindrome[len-1]='b';
return palindrome;
}
};
|
分配问题
455 Assign Cookies
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
int maxContent=0;
sort(g.begin(),g.end());
sort(s.begin(),s.end());
int i=0,j=0;
while(i<g.size() && j<s.size()){
if(s[j]>=g[i]){
maxContent++;
i++;
j++;
}else{
j++;
}
}
return maxContent;
}
};
|
- 时间复杂度：O(mlogm+nlogn)
- 空间复杂度：O(logm+logn)
135 Candy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
public:
int candy(vector<int>& ratings) {
int n=ratings.size();
if(n==1) return 1;
vector<int> candies(n,1);
for(int i=1;i<n;i++){
if(ratings[i]>ratings[i-1]){
candies[i]=candies[i-1]+1;
}
}
for(int i=n-1;i>0;i--){
if(ratings[i-1]>ratings[i]){
candies[i-1]=max(candies[i-1],candies[i]+1);
}
}
return accumulate(candies.begin(),candies.end(),0);
}
};
|
区间问题
需要根据实际情况判断按区间开头排序还是按结尾排序。
435 Non-overlapping Intervals
Greedy
采取的贪心策略：优先保留结尾小且不相交的区间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
if(intervals.empty()) return 0;
int n=intervals.size();
sort(intervals.begin(),intervals.end(),[](vector<int>& a,vector<int>& b){
return a[1]<b[1];
});
int res=0;
int prev=intervals[0][1];
for(int i=1;i<n;i++){
if(intervals[i][0]<prev){
res++;
}else{
prev=intervals[i][1];
}
}
return res;
}
};
|
- 时间复杂度：O(nlogn)
- 空间复杂度：O(logn)
452 Minimum Number of Arrows to Burst Balloons
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points) {
int minArrow=1;
sort(points.begin(),points.end(),[](vector<int>& a,vector<int>& b){
return a[0]<b[0];
});
int n=points.size();
for(int i=1;i<n;i++){
if(points[i][0]>points[i-1][1]){
minArrow++;
}else{
//更新最小右边界
points[i][1]=min(points[i][1],points[i-1][1]);
}
}
return minArrow;
}
};
|
ELSE
334 Increasing Triplet Subsequence
双向遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
int n=nums.size();
if(n<3) return false;
//维护数组 nums 中的每个元素左边的最小值和右边的最大值
vector<int> leftMin(n),rightMax(n);
leftMin[0]=nums[0];
for(int i=1;i<n;i++){
leftMin[i]=min(leftMin[i-1],nums[i]);
}
rightMax[n-1]=nums[n-1];
for(int i=n-2;i>=0;i--){
rightMax[i]=max(rightMax[i+1],nums[i]);
}
for(int i=1;i<n-1;i++){
if(leftMin[i-1]<nums[i] && nums[i]<rightMax[i+1]) return true;
}
return false;
}
};
|
Greedy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
int n=nums.size();
if(n<3) return false;
int first=nums[0],second=INT_MAX;
for(int i=1;i<n;i++){
int num=nums[i];
if(num>second) return true;
else if(num>first) second=num;
else first=num;
}
return false;
}
};
|
605 Can Place Flowers
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
public:
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
vector<int> temp;
temp.push_back(0);
for(int flower:flowerbed){
temp.push_back(flower);
}
temp.push_back(0);
//skip first & last
for(int i=1;i<temp.size()-1;i++){
if(temp[i-1]==0 && temp[i]==0 && temp[i+1]==0){
temp[i]=1;
n--;
}
}
return n<=0;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution {
public:
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
int size=flowerbed.size();
for(int i=0;i<size;i++){
if(flowerbed[i]==0
&& (i==0 || flowerbed[i-1]==0)
&& (i==size-1 || flowerbed[i+1]==0)){
flowerbed[i]=1;
n--;
}
}
return n<=0;
}
};
|
注意：(i==0 || flowerbed[i-1]==0)和(i==size-1 || flowerbed[i+1]==0)的顺序是判断i==0和i==size-1在判0前面，否则会有runtime error: addition of unsigned offset…
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
public:
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
int empty=0;
if(flowerbed[0]==0){
empty=1;
}
for(int i=0;i<flowerbed.size();i++){
if(flowerbed[i]==1){
n-=(empty-1)/2;
empty=0;
}else{
empty+=1;
}
}
n-=empty/2;
return n<=0;
}
};
|
763 Partition Labels
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class Solution {
public:
vector<int> partitionLabels(string s) {
int len=s.length();
//key:letter value:last occurance index
unordered_map<char,int> mp;
for(int i=0;i<len;i++){
mp[s[i]]=i;
}
vector<int> res;
int start=0;
int end=0;
for(int i=0;i<len;i++){
end=max(end,mp[s[i]]);
if(i==end){
res.push_back(i-start+1);
start=i+1;
}
}
return res;
}
};
|
- 时间复杂度：O(n)
- 空间复杂度：O(∣Σ∣)，其中 Σ = 26。
769 Max Chunks To Make Sorted
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution {
public:
int maxChunksToSorted(vector<int>& arr) {
int res=0;
//arr:0~n-1
int maxValue=-1;
for(int i=0;i<arr.size();i++){
maxValue=max(maxValue,arr[i]);
if(i==maxValue){
res+=1;
}
}
return res;
}
};
|
注意：若数组存在重复元素，该解法无法得到正确答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
public:
int maxChunksToSorted(vector<int>& arr) {
stack<int> stk;
for(int a:arr){
if(stk.empty() || a>=stk.top()){
stk.push(a);
}else{
int maxValue=stk.top();
stk.pop();
while(!stk.empty() && a<stk.top()){
stk.pop();
}
stk.push(maxValue);
}
}
return stk.size();
}
};
|
768 Max Chunks To Make Sorted II
新添加的数字可能会改变原数组的分块方式。如果新添加的数字大于或等于原数组最后一个块的最大值，则这个新添加的数字可以自己形成一个块。如果新添加的数字小于原数组最后一个块的最大值，则它必须融入之前的块。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
public:
int maxChunksToSorted(vector<int>& arr) {
stack<int> stk;
for(int a:arr){
if(stk.empty() || a>=stk.top()){
stk.push(a);
}else{
int maxValue=stk.top();
stk.pop();
//判断加入a需要合并的所有排序块，每pop()一个代表合并一个块
while(!stk.empty() && a<stk.top()){
stk.pop();
}
stk.push(maxValue);
}
}
return stk.size();
}
};
|
Author
Anjana
LastMod
2022-08-05
License
原创文章，如需转载请注明作者和出处。谢谢！