从排序数组中删除重复项
双指针法解决。当数值不同且不指向同一个时替换。写的有点丑陋，可以利用nums[i]的值去替代temp
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:
int removeDuplicates(vector<int>& nums) {
if(nums.empty()) return 0;
int i=j=0;
int temp=nums[i];
int res=1;
while(j<nums.size()){
if(temp<nums[j]){
res++;
if(i!=j)
{
i++;
nums[i]=nums[j];
}
temp=nums[j];
}
j++;
}
return res;
}
};
|
买卖股票的最佳时机
动态规划 前i天的最大收益 = max{前i-1天的最大收益，第i天的价格-前i-1天中的最小价格}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.empty()) return 0;
vector<int> dp;
dp.resize(prices.size());
dp[0]=0;
int minp=prices[0];
for(int i=1;i<prices.size();i++){
if(prices[i]<=prices[i-1])
dp[i]=dp[i-1];
else if(prices[i]-minp>dp[i-1])
dp[i]=prices[i]-minp;
else dp[i]=dp[i-1];
minp=min(minp,prices[i]);
}
return dp[prices.size()-1];
}
};
|
- 买卖股票的最佳时机 II
贪心没啥思路，偷看了评论区的答案：[7, 1, 5, 6] 第二天买入，第四天卖出，收益最大（6-1），所以一般人可能会想，怎么判断不是第三天就卖出了呢? 这里就把问题复杂化了，根据题目的意思，当天卖出以后，当天还可以买入，所以其实可以第三天卖出，第三天买入，第四天又卖出（（5-1）+ （6-5） === 6 - 1）。所以算法可以直接简化为只要今天比昨天大，就卖出。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.empty()) return 0;
int res=0;
int pricenow=prices[0]; //默认持有价格
for(int i=1;i<prices.size();i++){
if(prices[i]<=pricenow) //当天价格比你持有的低,直接放弃之前的
pricenow=prices[i];
else{
res+=prices[i]-pricenow;
pricenow=prices[i];
}
}
return res;
}
};
|
旋转图像
虽然是道medium题，但是感觉其实也没很难。。想了很久才明白旋转规则。（四个结点旋转）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
if(matrix.empty()) return;
int n=matrix.size();
for(int i=0;i<n/2;i++){
for(int j=i;j<n-i-1;j++){
int temp=matrix[i][j];
matrix[i][j]=matrix[n-1-j][i];
matrix[n-1-j][i]=matrix[n-1-i][n-1-j];
matrix[n-1-i][n-1-j]=matrix[j][n-1-i];
matrix[j][n-1-i]=temp;
}
}
return;
}
};
|
- 有效的字母异位词
建立字母表 再比较。 也可以用map去做。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
bool isAnagram(string s, string t) {
int a[26]={0};
int b[26]={0};
for(int i=0;i<s.length();i++)
a[s[i]-'a']++;
for(int i=0;i<t.length();i++)
b[t[i]-'a']++;
for(int i=0;i<26;i++)
if(a[i]!=b[i]) return false;
return 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
| class Solution {
public:
bool isPalindrome(string s) {
if(s.empty()) return true;
int i=0,j=s.length()-1;
while(i<j){
while(1){
if((s[i]>='0'&&s[i]<='9')||(s[i]>='a'&&s[i]<='z')||(s[i]>='A'&&s[i]<='Z')||i==j) break;
i++;
}
while(1){
if((s[j]>='0'&&s[j]<='9')||(s[j]>='a'&&s[j]<='z')||(s[j]>='A'&&s[j]<='Z')||i==j) break;
j--;
}
if(i==j) break;
char p=s[i],q=s[j];
if(p>='A'&&p<='Z') p+=32;
if(q>='A'&&q<='Z') q+=32;
if(p!=q) return false;
i++;
j--;
}
return true;
}
};
|
- 字符串转换整数 (atoi)
还是属于比较简单的medium主要考察一个细心把。。
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 myAtoi(string str) {
long long res=0;
if(str.empty()) return 0;
int i;
for(i=0;i<str.length();i++)
if(str[i]!=' ') break;
if(i==str.length()||(str[i]<'0'&&str[i]!='-'&&str[i]!='+')||str[i]>'9') return 0;
char temp=str[i];
if(str[i]=='-'||str[i]=='+') i++;
while(i<str.length()){
if(str[i]>='0'&&str[i]<='9')
{
if(res>pow(2,31)-1) return temp=='-'?INT_MIN:INT_MAX;
res=res*10+(int)(str[i]-'0');
i++;
}
else break;
}
if(temp=='-') res=res*(-1);
if(res>pow(2,31)-1) return INT_MAX;
if(res<pow(2,31)*(-1)) return INT_MIN;
return res;
}
};
|
实现strStr()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| // 我枯了，明明是道ez题，居然随便写写过不了。。。还要剪枝。。
class Solution {
public:
int strStr(string haystack, string needle) {
if(needle.empty()) return 0;
int n1=haystack.length(),n2=needle.length();
if(n2>n1) return -1;
int i=0;
while(i+n2<=haystack.length()){
int t=i;
int j=0;
for( j=0;j<needle.length();j++)
{
if(haystack[t]!=needle[j]) break;
t++;
}
if(j==needle.length()) return i;
i++;
}
return -1;
}
};
|
