矩形区域不超过K的最大数值和
题目：给你一个 m x n 的矩阵 matrix 和一个整数 k ，找出并返回矩阵内部矩形区域的不超过 k 的最大数值和。题目数据保证总会存在一个数值和不超过 k 的矩形区域。
题目截图
思路：这个题是2021/4/22的每日一题。然后题目乍一看比较简单。其实叔祖父范围才10000（横竖100）。最暴力的办法就是每一个点都作为左上角的顶点计算一遍。但是这个问题就是1w个点。每个点都要算到底。所以盲猜这个题可以用dp。。。刚看了眼题目标签，猜对了。。哈哈，然后问题就来了，dp的公式是什么。。我去好好琢琢磨这个题。
算了，dp怎么也想不出来。但是这个题的思路还是有的，那就是暴力法:毕竟这个题目肯定是一个矩形：也就是分上下左右四个边的。我打算用穷举法挨个试一下。我去试试。
附上第一版本代码：
class Solution {
public int maxSumSubmatrix(int[][] matrix, int k) {
int ans = Integer.MIN_VALUE;
int l = matrix.length;
int c = matrix[0].length;
for(int i = 0;i<l;i++){//矩形上边
int[] sum = new int[c];
for(int j = i;j<l;j++){//矩形下边
//每一列递加。
for(int m = 0;m<c;m++) sum[m] += matrix[j][m];
for(int s = 0;s<c;s++){//左边
int cur = 0;
for(int e = s;e<c;e++){//右边
cur += sum[e];
if(cur == k) return k;
if(cur<k && cur>ans) ans = cur;
}
}
}
}
return ans;
}
}
讲真这个题我自己都觉得过了是奇迹，而且性能还不错的过了，简直让我amazing~~哈哈，思路就是单纯的暴力法：这个题目本身虽然我用了四层for循环但是其实性能也还好。首先因为上下边界的定义，并且中间用sum压缩，使得这个题的题目可以被简化成：给定一维数组，找出连续子序列的和小于等于k且值最大的和。然后这个题目又可以变成去找左右边界。也就是有一个双层for循环定位左右边界。如此，这个题就解出来了。至于优化我也没啥思路，我去看看性能第一的代码：
class Solution {
public int maxSumSubmatrix(int[][] matrix, int k) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
return 0;
int row = matrix.length;
int col = matrix[0].length;
int res = Integer.MIN_VALUE;
for (int i = 0; i < col; i++) {
int[] sum = new int[row];
for (int j = i; j < col; j++) {
for (int r = 0; r < row; r++) {
sum[r] += matrix[r][j];
}
int curr = 0;
int max = sum[0];
for (int n : sum) {
curr = Math.max(n, curr + n);
max = Math.max(curr, max);
if (max == k) return max;
}
if (max < k) {
res = Math.max(max, res);
} else {
for (int a = 0; a < row; a++) {
int currSum = 0;
for (int b = a; b < row; b++) {
currSum += sum[b];
if (currSum <= k) res = Math.max(currSum, res);
}
}
if (res == k) return res;
}
}
}
return res;
}
}
咳咳，性能第一的代码是把所有测试案例穷举出来了，所有继续往下顺延性能第二的代码：
class Solution {
public int maxSumSubmatrix(int[][] matrix, int k) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
return 0;
int row = matrix.length;
int col = matrix[0].length;
int res = Integer.MIN_VALUE;
for (int i = 0; i < col; i++) {
int[] sum = new int[row];
for (int j = i; j < col; j++) {
for (int r = 0; r < row; r++) {
sum[r] += matrix[r][j];
}
int curr = 0;
int max = sum[0];
for (int n : sum) {
curr = Math.max(n, curr + n);
max = Math.max(curr, max);
if (max == k) return max;
}
if (max < k) {
res = Math.max(max, res);
} else {
for (int a = 0; a < row; a++) {
int currSum = 0;
for (int b = a; b < row; b++) {
currSum += sum[b];
if (currSum <= k) res = Math.max(currSum, res);
}
}
if (res == k) return res;
}
}
}
return res;
}
}
我是上下压缩，人家是左右压缩。而且这个题还有一点是在判断上下边界的时候添加了额外的判断。也没啥好说的，这个题过了，下一题。
括号的分数
题目：给定一个平衡括号字符串 S，按下述规则计算该字符串的分数：
() 得 1 分。
AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。
(A) 得 2 * A 分，其中 A 是平衡括号字符串。
示例 1：
输入： "()"
输出： 1
示例 2：
输入： "(())"
输出： 2
示例 3：
输入： "()()"
输出： 2
示例 4：
输入： "(()(()))"
输出： 6
提示：
S 是平衡括号字符串，且只含有 ( 和 ) 。
2 <= S.length <= 50
思路：这个题怎么说呢，感觉上就是一个简单的字符串拆分的题，目前的想法是递归实现。遇到起始括号一定要算出这个括号的结果才算完。反正思路是有的，我去代码实现下试试。
第一版本代码：
class Solution {
public int scoreOfParentheses(String S) {
int left = 0;
int start = 0;
int ans = 0;
char[] c = S.toCharArray();
for(int i = 0;i<c.length;i++){
if(c[i] == '('){
left++;
}else {
left--;
}
if(left == 0){//前面的是单独一个组
//说明就是一个空（）
if(i-start == 1) {
ans+= 1;
start = i+1;
}else{
ans += 2*scoreOfParentheses(S.substring(start+1,i));
start = i+1;
}
}
}
return ans;
}
}
思路挺清晰的，代码耗时1ms，超过百分之六十的人。总而言之这个题其实单纯的用递归一层一层从里往外计算就可以了。然后我觉得我这个性能不好应该是细节处理上的。我直接去看性能第一的代码了：
class Solution {
public int scoreOfParentheses(String S) {
int res = 0;
int lcount = 0;// 左括号数量
for(int i=0;i<S.length();i++){
char c = S.charAt(i);
if(c == '('){
// 左括号数量+1
lcount ++;
}else{
// 遇到右括号 左括号数量-1
lcount --;
// 判断前一位是不是左括号
if(i>0 && S.charAt(i-1) == '('){
// 左边也是左括号 需要累乘左括号数量个的2
res += 1 << lcount;
}
}
}
return res;
}
}
好叭，完全猜错了，人家性能第一的代码没有用递归，就是直接算的。事实上，我们可以发现，只有 () 会对字符串 S 贡献实质的分数，其它的括号只会将分数乘二或者将分数累加。因此，我们可以找到每一个 () 对应的深度 x，那么答案就是 2^x 的累加和。这个代码的注释写的挺清楚了，因为这个题比较简单，所以不多说了，下一题吧。
在D天内送达包裹的能力
题目:传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。
示例 1：
输入：weights = [1,2,3,4,5,6,7,8,9,10], D = 5
输出：15
解释：
船舶最低载重 15 就能够在 5 天内送达所有包裹，如下所示：
第 1 天：1, 2, 3, 4, 5
第 2 天：6, 7
第 3 天：8
第 4 天：9
第 5 天：10
请注意，货物必须按照给定的顺序装运，因此使用载重能力为 14 的船舶并将包装分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。
示例 2：
输入：weights = [3,2,2,4,1,4], D = 3
输出：6
解释：
船舶最低载重 6 就能够在 3 天内送达所有包裹，如下所示：
第 1 天：3, 2
第 2 天：2, 4
第 3 天：1, 4
示例 3：
输入：weights = [1,2,3,1,1], D = 4
输出：3
解释：
第 1 天：1
第 2 天：2
第 3 天：3
第 4 天：1, 1
提示：
1 <= D <= weights.length <= 50000
1 <= weights[i] <= 500
思路：这个题怎么说呢。盲猜dp。怎么把weights这些数划分为D组，使得每组的和的最大值最小。简单来说这个题就是这个意思。。好吧，看了标签是二分查找，没有dp。。有点点打脸。但是我觉得我思路是没问题的。总和/D。就是可能的最小量。然後还有要算出单次的最大值。如果平均值小于最大值，那么以最大值为基础。反正思路有点乱，我去捋捋思路。
第一版代码出来了，死扣二分扣出来的：
class Solution {
public int shipWithinDays(int[] weights, int D) {
int sum = 0;
int max = 0;
for(int i : weights) {
sum += i;
max = Math.max(max, i);
}
if(D==1) return sum;
if(D==weights.length) return max;
//到这说明最小值是平均值/max中较大的哪个。最大值就是sum-1
//因为都不为0.所以最极端的可能就是分俩数：一个巨大，一个是1.那么最大的分组就是sum-1
int left = Math.max(sum/D+(sum%D==0?0:1), max);
int right = sum-1;
//left和right分别是最小值和最大值，接下来二分查找这个值。
while(left<right) {
int mid = (right+left)/2;
int n = 1;
int temp = 0;
for(int i : weights) {
if(temp+i>mid) {
n++;
temp = i;
}else {
temp += i;
}
}
if(n>D) {//超了，说明要往大了定
left = mid+1;
}else {//往小了定
right = mid;
}
}
return left;
}
}
其实这个代码还挺有意思的，需要注意的点也比较多：
- 首先上面思路中的平均数，最大数啥的都用上了，作为最小运输力的量。
- 其次我上面的代码调试了n次，中间有很多忽略的点：首先这个n一开始我写的是0.后来发现如果从0开始的话那么到最后和D比较是有问题的。因为从0到D说明多了一天的。（因为最后一天肯定不应该超。不应该加1）.
- 然後还有一点要注意的就是二分的变化量：超了往大。left = mid+1没啥问题。但是我之前第一版代码right = mid-1问题就大了。因为这个不是常规的二分。不是说mid的值正合适一定是大。可能是正好，所以如果这里right的值 是mid-1反而是错过了正确值。
第一点是我觉得有必要直接把极端值算出来防止很多重复计算的。而后两点都是我自己写错了，踩得坑。总而言之这个题是个比较有难度的题吧。我上面代码性能也挺不错，我去看看性能第一的代码:
class Solution {
public int shipWithinDays(int[] weights, int D) {
// 载重范围，最小应该是货物中最大重量（否则就没办法装船了）
int left = 0;
for (int weight : weights) {
if (weight > left) {
left = weight;
}
}
// 最大应该是假设每个货物都为最大，平均每天能带多少
// 注：当D > weights.length 时, right < left 即 此时会直接返回 left。而背后的逻辑是，当天数大于货物数量，那么只要每天至少搬一个货物上船即可，此时可以达到区间的最小，即货物的最大重量
int right = left * weights.length / D + 1;
// 取值区间使用左右闭合
while (left <= right) {
int mid = (left + right) >>> 1;
if (canFinish(weights, D, mid)) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
private boolean canFinish(int[] weights, int D, int cap) {
int day = 1, cur = cap;
for (int weight : weights) {
if (weight > cur) {
day++;
cur = cap;
}
cur -= weight;
}
return day <= D;
}
}
差不多的思路，所以就不多说了，下一题了。
二叉树中所有距离为K的节点
题目：给定一个二叉树（具有根结点 root）， 一个目标结点 target ，和一个整数值 K 。返回到目标结点 target 距离为 K 的所有结点的值的列表。 答案可以以任何顺序返回。
示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2
输出：[7,4,1]
解释：
所求结点为与目标结点（值为 5）距离为 2 的结点，
值分别为 7，4，以及 1
注意，输入的 "root" 和 "target" 实际上是树上的结点。
上面的输入仅仅是对这些对象进行了序列化描述。
提示：
给定的树是非空的。
树上的每个结点都具有唯一的值 0 <= node.val <= 500 。
目标结点 target 是树上的结点。
0 <= K <= 1000.
题目截图
思路：这个题首先每个节点最多同时存在3个直接关联的节点（上节点。左右两个子节点）。所以这个题我觉得可以用深搜来做。先找到给定的target节点。然後与其直接相连的三个节点（最多三个，也可能没有）。然後找到这三个节点的k-1距离的节点。这里需要注意下判重就好了。也就是A穿给B以后，再找B的相关节点要把A排除掉。不过这样可能要一直遍历树。但是因为节点值是唯一的。而且最毒只有500个节点。所以我的想法是每个节点单独存起来。大概思路是这样的，我去代码实现下试试。
第一版代码:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
Map<TreeNode, TreeNode> parent;
public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
parent = new HashMap();
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while(!queue.isEmpty()) {
int size = queue.size();
for(int i = 0;i<size;i++) {
TreeNode cur = queue.poll();
if(cur.left != null) {
parent.put(cur.left, cur);
queue.add(cur.left);
}
if(cur.right != null) {
parent.put(cur.right, cur);
queue.add(cur.right);
}
}
}
queue.add(null);
queue.add(target);
//记忆化，省的重复计算路径
Set<TreeNode> seen = new HashSet();
seen.add(target);
seen.add(null);
int dist = 0;
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node == null) {
if (dist == K) {
List<Integer> ans = new ArrayList();
for (TreeNode n: queue)
ans.add(n.val);
return ans;
}
queue.offer(null);
dist++;
} else {
if (!seen.contains(node.left)) {
seen.add(node.left);
queue.offer(node.left);
}
if (!seen.contains(node.right)) {
seen.add(node.right);
queue.offer(node.right);
}
TreeNode par = parent.get(node);
if (!seen.contains(par)) {
seen.add(par);
queue.offer(par);
}
}
}
return new ArrayList<Integer>();
}
}
这个题我上面代码勉强过了，但是性能问题比较大。总而言之这个题比较复杂。首先给定的target是个节点，一开始我以为是节点的值。然後做了很多无用功，其次这个map我一开始是存值和树，后来发现需要上一层的值。总而言之挺麻烦的。后来发现存当前树和上一层树比较好。
最后就是记忆化了，这个是必要的。我之前思路的时候就说了，这里用的set来存储没啥 说的。思路上我也想不出什么好办法了，我去看看性能第一的代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
List<Integer> ans;
TreeNode target;
int K;
public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
ans = new LinkedList();
this.target = target;
this.K = K;
dfs(root);
return ans;
}
// Return vertex distance from node to target if exists, else -1
// Vertex distance: the number of vertices on the path from node to target
public int dfs(TreeNode node) {
if (node == null)
return -1;
else if (node == target) {
subtree_add(node, 0);
return 1;
} else {
int L = dfs(node.left), R = dfs(node.right);
if (L != -1) {
if (L == K) ans.add(node.val);
subtree_add(node.right, L + 1);
return L + 1;
} else if (R != -1) {
if (R == K) ans.add(node.val);
subtree_add(node.left, R + 1);
return R + 1;
} else {
return -1;
}
}
}
// Add all nodes 'K - dist' from the node to answer.
public void subtree_add(TreeNode node, int dist) {
if (node == null) return;
if (dist == K)
ans.add(node.val);
else {
subtree_add(node.left, dist + 1);
subtree_add(node.right, dist + 1);
}
}
}
递归+递归，也是神奇了，其实我一开始思路确实是这样的。就是递归一层一层往下找，但是写的时候换了写法。而且这个执行时间15ms，我的代码22ms。其实差别也不是很大。这个题就这样吧，没什么好说的，下一题了。
具有所有最深节点的最小子树
题目：给定一个根为 root 的二叉树，每个节点的深度是 该节点到根的最短距离 。如果一个节点在 整个树 的任意节点之间具有最大的深度，则该节点是 最深的 。一个节点的 子树 是该节点加上它的所有后代的集合。返回能满足 以该节点为根的子树中包含所有最深的节点 这一条件的具有最大深度的节点。
题目截图
输入：root = [3,5,1,6,2,0,8,null,null,7,4]
输出：[2,7,4]
解释：
我们返回值为 2 的节点，在图中用黄色标记。
在图中用蓝色标记的是树的最深的节点。
注意，节点 5、3 和 2 包含树中最深的节点，但节点 2 的子树最小，因此我们返回它。
示例 2：
输入：root = [1]
输出：[1]
解释：根节点是树中最深的节点。
示例 3：
输入：root = [0,1,3,null,2]
输出：[2]
解释：树中最深的节点为 2 ，有效子树为节点 2、1 和 0 的子树，但节点 2 的子树最小。
提示：
树中节点的数量介于 1 和 500 之间。
0 <= Node.val <= 500
每个节点的值都是独一无二的。
思路：讲真，死去活来的看了半天题目才明白这个题的意思：应该是最深的节点的公共先祖。比如一个树左右两边深度一样，那这个树的根节点就是最小公共先祖。否则找深度较深的那个子树继续遍历。依次类推。这个题主要是明白题意，单纯的实现是比较容易的。我去代码实现了。
第一版代码：
/**
* 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 {
public TreeNode subtreeWithAllDeepest(TreeNode root) {
int[] res = dfs(root);
if(res[0] == res[1]) return root;
if(res[0]>res[1]) {
return subtreeWithAllDeepest(root.left);
}else {
return subtreeWithAllDeepest(root.right);
}
}
public int[] dfs(TreeNode root) {
if(root == null) return new int[] {0,0};
int[] left = dfs(root.left);
int l = Math.max(left[0],left[1])+1;
int[] right = dfs(root.right);
int r = Math.max(right[0], right[1])+1;
return new int[] {l,r};
}
}
这个题像我上面说的，只要能读懂题意还是挺顺的。然后代码也符合树类题目的一贯做法：递归。上面代码用了两个递归，都比较好理解。但是我写完觉得中间设计了很多没必要的计算，我去看看别人的代码看有没有更好的实现：
没有什么亮点，我直接贴出来大家看下这个题就过了：
/**
* 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 {
public TreeNode subtreeWithAllDeepest(TreeNode root) {
if(root==null) return root;
int left=depth(root.left);
int right=depth(root.right);
if(left==right) return root;
if(left>right) return subtreeWithAllDeepest(root.left);
return subtreeWithAllDeepest(root.right);
}
int depth(TreeNode root){
if(root==null) return 0;
return 1+Math.max(depth(root.left),depth(root.right));
}
}
本篇笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注，也祝大家工作顺顺利利！愿所有的努力都不会被辜负~！
网友评论