738. 单调递增的数字 - 力扣（LeetCode）
思路:
- 先将给定数字转换成字符串，然后从后往前遍历给定数字，若前一位比后一位大，那么就将后一位置为9，前一位减1
- 注意要将
flag标记的位置往后的所有数字都变为9，flag记录的是最后一个i比i - 1小的位置
我的AC代码
//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
int monotoneIncreasingDigits(int n) {
string ans = to_string(n);
int flag = ans.size();
for(int i = ans.size() - 1; i >= 1; --i) {
if(ans[i] < ans[i - 1]) {
ans[i - 1]--;
flag = i;
}
}
for(int i = flag; i < ans.size(); ++i) {
ans[i] = '9';
}
return stoi(ans);
}
};标准答案
//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
int monotoneIncreasingDigits(int N) {
string strNum = to_string(N);
// flag用来标记赋值9从哪里开始
// 设置为这个默认值，为了防止第二个for循环在flag没有被赋值的情况下执行
int flag = strNum.size();
for (int i = strNum.size() - 1; i > 0; i--) {
if (strNum[i - 1] > strNum[i] ) {
flag = i;
strNum[i - 1]--;
}
}
for (int i = flag; i < strNum.size(); i++) {
strNum[i] = '9';
}
return stoi(strNum);
}
};714. 买卖股票的最佳时机含手续费 - 力扣（LeetCode）
思路:
- 这道题与122. 买卖股票的最佳时机 II - 力扣（LeetCode）不同的是增加了手续费，这就使得我们不得不考虑卖出股票的合适时机，而不是像122. 买卖股票的最佳时机 II - 力扣（LeetCode）一样无限交易
- 我们需要找出最低价格和能够盈利的日子(需要在能盈利的最后一天卖出)，但实际上我们并不需要知道什么时候卖出，只需要计算能获取多少利润即可
- 有三种情况需要考虑
- 情况一：当前价格比最低价格要低，那么我们就更新最低价格
- 情况二：当前价格高于最低价格但是如果此时卖出，算上手续费还是亏损，那么我们什么都不做。换言之，这段代码实际上可以忽略
- 情况三：当前价格高于最低价格且即使算上手续费，卖出也能获得利润。那么我们将利润加入总利润中，记得要减去手续费，但有一点十分关键，那就是我们需要更新最低价格为
prices[i] - fee，这是因为此时的卖出不一定是真正的卖出，我们在计算利润的时候先减去手续费，但我们记录的最低价格也减去了这个手续费，这就意味着如果此时是真正卖出的时候，那么接下来此时的最低价格就被抛弃了，不会再用到，即手续费真的被减去了；如果此时并没有真正卖出，还没到达利润最顶峰，那么我们在下一次计算利润的时候会把上一次被减去的手续费通过最低价格这个变量被加回来，即相当于此时并没有减去这个手续费，这是一个相当巧妙的设计
我的AC代码
贪心
//时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int result = 0;
int minPrice = prices[0];
for(int i = 1; i < prices.size(); ++i) {
if(minPrice > prices[i]) {
minPrice = prices[i];
}
if(prices[i] > minPrice + fee) {
result += prices[i] - minPrice - fee;
minPrice = prices[i] - fee;
}
}
return result;
}
};标准答案
贪心
//时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int result = 0;
int minPrice = prices[0]; // 记录最低价格
for (int i = 1; i < prices.size(); i++) {
// 情况二：相当于买入
if (prices[i] < minPrice) minPrice = prices[i];
// 情况三：保持原有状态（因为此时买则不便宜，卖则亏本）
if (prices[i] >= minPrice && prices[i] <= minPrice + fee) {
continue;
}
// 计算利润，可能有多次计算利润，最后一次计算利润才是真正意义的卖出
if (prices[i] > minPrice + fee) {
result += prices[i] - minPrice - fee;
minPrice = prices[i] - fee; // 情况一，这一步很关键
}
}
return result;
}
};动态规划
//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
// dp[i][1]第i天持有的最多现金
// dp[i][0]第i天持有股票所剩的最多现金
int n = prices.size();
vector<vector<int>> dp(n, vector<int>(2, 0));
dp[0][0] -= prices[0]; // 持股票
for (int i = 1; i < n; i++) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
}
return max(dp[n - 1][0], dp[n - 1][1]);
}
};动态规划(优化空间复杂度)
//时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int n = prices.size();
int holdStock = (-1) * prices[0]; // 持股票
int saleStock = 0; // 卖出股票
for (int i = 1; i < n; i++) {
int previousHoldStock = holdStock;
holdStock = max(holdStock, saleStock - prices[i]);
saleStock = max(saleStock, previousHoldStock + prices[i] - fee);
}
return saleStock;
}
};968. 监控二叉树 - 力扣（LeetCode）
思路:
- 从叶子节点往根节点看，让叶子节点的父节点安摄像头，这样所用摄像头最少
- 我们采用后序遍历来遍历整个二叉树，这样方便我们从下到上进行推导
- 有三种情况需要讨论，在代码中分别用三个数字表示
- 0：该节点无覆盖
- 1：本节点有摄像头
- 2：本节点有覆盖
- 通过对每个节点分析这三种情况来计算监控数量
- 最后要进行一个特判，即根节点是否已经被覆盖，如果没有则要增加一个摄像头数量，此时得到的答案即为最终答案
我的AC代码
复刻标准答案
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int result = 0;
int traversal(TreeNode* cur) {
if(cur == NULL) {
return 2;
}
int left = traversal(cur->left);
int right = traversal(cur->right);
if(left == 2 && right == 2) {
return 0;
}
else if (left == 0 || right == 0) {
result++;
return 1;
}
else {
return 2;
}
}
int minCameraCover(TreeNode* root) {
if(traversal(root) == 0) {
result++;
}
return result;
}
};标准答案
详细版本
// 版本一
class Solution {
private:
int result;
int traversal(TreeNode* cur) {
// 空节点，该节点有覆盖
if (cur == NULL) return 2;
int left = traversal(cur->left); // 左
int right = traversal(cur->right); // 右
// 情况1
// 左右节点都有覆盖
if (left == 2 && right == 2) return 0;
// 情况2
// left == 0 && right == 0 左右节点无覆盖
// left == 1 && right == 0 左节点有摄像头，右节点无覆盖
// left == 0 && right == 1 左节点有无覆盖，右节点摄像头
// left == 0 && right == 2 左节点无覆盖，右节点覆盖
// left == 2 && right == 0 左节点覆盖，右节点无覆盖
if (left == 0 || right == 0) {
result++;
return 1;
}
// 情况3
// left == 1 && right == 2 左节点有摄像头，右节点有覆盖
// left == 2 && right == 1 左节点有覆盖，右节点有摄像头
// left == 1 && right == 1 左右节点都有摄像头
// 其他情况前段代码均已覆盖
if (left == 1 || right == 1) return 2;
// 以上代码我没有使用else，主要是为了把各个分支条件展现出来，这样代码有助于读者理解
// 这个 return -1 逻辑不会走到这里。
return -1;
}
public:
int minCameraCover(TreeNode* root) {
result = 0;
// 情况4
if (traversal(root) == 0) { // root 无覆盖
result++;
}
return result;
}
};精简版本
// 版本二
class Solution {
private:
int result;
int traversal(TreeNode* cur) {
if (cur == NULL) return 2;
int left = traversal(cur->left); // 左
int right = traversal(cur->right); // 右
if (left == 2 && right == 2) return 0;
else if (left == 0 || right == 0) {
result++;
return 1;
} else return 2;
}
public:
int minCameraCover(TreeNode* root) {
result = 0;
if (traversal(root) == 0) { // root 无覆盖
result++;
}
return result;
}
};
Comments NOTHING