- 单调递增的数字
- 学习文章链接：https://www.programmercarl.com/0738.%E5%8D%95%E8%B0%83%E9%80%92%E5%A2%9E%E7%9A%84%E6%95%B0%E5%AD%97.html
- 思路：这题主要在于思想，一旦某位置的数字破坏了单调递增的规则，那么就要将位置数字减小，并从下一个位置之后的数字均变为9。
- 代码：
class Solution {
public int monotoneIncreasingDigits(int n) {
// 例如此题的遍历顺序是从后往前，因为从前往后的话，会改变已经确定的结果。
// 局部最优：遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]–
// 然后strNum[i]给为9，可以保证这两位变成最大单调递增整数。
// 全局最优：得到小于等于N的最大单调递增的整数。
String s = String.valueOf(n);
char[] c = s.toCharArray();
int start = s.length();
for (int i = s.length() - 2; i >= 0; i–) {
// 一旦找到前面的元素大于后面的元素，此位置开始之后都是9。
if (c[i] > c[i + 1]) {
c[i]–;
start = i + 1;
}
}
// 从start的位置开始，变9，才能保证最大。
for (int i = start; i < s.length(); i++) {
c[i] = ‘9’;
}
// 字符数组 -> 字符串 -> 数字
return Integer.parseInt(String.valueOf©);
}
} - 买卖股票的最佳时机含手续费
- 学习文章链接：https://www.programmercarl.com/0714.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BA%E5%90%AB%E6%89%8B%E7%BB%AD%E8%B4%B9.html#%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95
- 思路：有手续费之后，就要考虑交易的次数了。
- 代码：
class Solution {
public int maxProfit(int[] prices, int fee) {
// 初始买入价格
// 注意买入时已支付了手续费，买入卖出算是一次交易，花费一次手续费。
int buy = prices[0] + fee;
// 利润总和
int sum = 0;
for (int p : prices) {
if (p + fee < buy) { //如果之后的价格与手续费总和小于买入价格，那么就是更改买入的价格。
buy = p + fee;
} else if (p > buy){
sum += p - buy; //可以出售了，出售时不考虑手续费。
buy = p; //更新买入价格。
}
}
return sum;
}
}
968.监控二叉树 - 学习文章链接：
- 思路：想清楚三种情况和012的定义这题就好理解多了。
- 代码：
/**
-
Definition for a binary tree node.
-
public class TreeNode {
-
int val; -
TreeNode left; -
TreeNode right; -
TreeNode() {} -
TreeNode(int val) { this.val = val; } -
TreeNode(int val, TreeNode left, TreeNode right) { -
this.val = val; -
this.left = left; -
this.right = right; -
} -
}
*/
class Solution {
int res = 0;
public int minCameraCover(TreeNode root) {
// 摄像头都没有放在叶子节点上
// 后续遍历是从下向上遍历
// 0：该节点无覆盖
// 1：本节点有摄像头
// 2：本节点有覆盖
res = 0;
if (traversal(root) == 0) res++;
return res;
}
public int traversal(TreeNode root) {
// 空节点，该节点有覆盖
if (root == null) return 2;int left = traversal(root.left);int right = traversal(root.right);// case 1 ：左右节点都有覆盖if (left == 2 && right == 2) return 0;// case 2 ：左节点或者右节点无覆盖if (left == 0 || right == 0) {res++;return 1;}// case 3 : 左节点或者右节点有摄像头if (left == 1 || right == 1) {return 2;}return -1;}
}
