84. 求1+2+…+n
代码2:
class Solution {
public:
int getSum(int n) {
int res = n;
(n>0) && (res += getSum(n-1));//利用短路运算终止递归
return res;
}
};
代码1:
class Solution {
public:
int getSum(int n) {
char a[n][n+1];
return sizeof(a)>>1;
}
};
83. 股票的最大利润
思路
代码:
class Solution {
public:
int maxDiff(vector<int>& nums) {
if(nums.empty()) return 0;
int res = 0;
for(int i = 1, minv = nums[0]; i < nums.size(); i ++)
{
// 如果在第i天卖出,则最大收益:
res = max(res, nums[i] - minv);
minv = min(minv, nums[i]); // 更新最小值
}
return res;
}
};
82. 圆圈中最后剩下的数字
思路
新旧编号推导参考
1. 新编号与旧编号的关系 : (新+m) %n f(n, m) = (f(n - 1, m) + m) %n
代码 递推
class Solution {
public:
int lastRemaining(int n, int m){
if(n == 1) return 0; // 只剩下一个人
return (lastRemaining(n - 1,m) + m)%n;
}
};
81. 扑克牌的顺子
思路
- 删除0(大小王)
- 判断是否有重复元素, 有的话则肯定不是顺子
- 最大值与最小值的差是否小于等于4.
3.1 小于4: 有0(大小王)的存在
3.2 等于4: 正常的顺子
代码
class Solution {
public:
bool isContinuous( vector<int> nums ) {
if (nums.empty()) return false;
// 对数组排序
sort(nums.begin(), nums.end());
int k = 0;
while(!nums[k]) k++; // 如果是数组中有0 则删。 结束后,数组下标在k位置。
for(int i = k +1; i < nums.size(); i++)
if(nums[i] == nums[i - 1]) // 如果有相同元素
return false;
return nums.back() - nums[k] <= 4; // 值差小于等于4
}
};
80. 骰子的点数(不懂)
代码 dfs
class Solution {
public:
vector<int> numberOfDice(int n) {
// 状态表示含义是什么 顺序 投了n次筛子,总和是s的情况下啊,方案是?
vector<int> res;
for(int i = n; i <= n*6; i++) res.push_back(dfs(n,i));
return res;
}
int dfs(int n, int sum)
{
// 边界情况:
if(sum < 0) return 0; // 无解
// 最后一个骰子的方案
if(n == 0) return !sum;
int res = 0;
for(int i = 1; i <= 6; i++)
res += dfs(n - 1,sum - i);
return res;
}
};
代码 dp
class Solution {
public:
vector<int> numberOfDice(int n) {
// dp的状态表示:
vector<vector<int>> f(n+1, vector<int>(n*6 + 1));
f[0][0] = 1;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= i*6; j++ )
for(int k =1 ; k<= min(j,6); k++ )
f[i][j] += f[i -1][j - k];
vector<int> res;
for(int i = n; i <= n*6; i++) res.push_back(f[n][i]);
return res;
}
};
79. 滑动窗口的最大值
思路
deque<int> q
是 双头队列,先入队列的是front, 后入队列的是back,
1.1. 操作有:q.pop_front()
弹出队头q.pop_front()
- 优化本质: 队列队首到队尾,单调递减。新插入的数和q的队尾的值做对比,如果队尾的值<插入值, 则把队尾删去。
代码
class Solution {
public:
vector<int> maxInWindows(vector<int>& nums, int k) {
vector<int> res; // 所有数组
deque<int> q; // 队列,支持两端插入删除
for(int i = 0; i < nums.size(); i++)
{
// 把划出窗口元素踢掉
while(q.size() && q.front() <= i-k) q.pop_front();
// 对于比新插入值小的,踢出
while(q.size() && nums[q.back()] <= nums[i]) q.pop_back();
// 队尾插入该值
q.push_back(i);
// 存储结果,队头是最大值。
if(i >= k - 1) res.push_back(nums[q.front()]);
}
return res;
}
};