【LeetCode每日一题】2024年8月第一周（下）

2024.8.03 中等

链接：3143. 正方形中的最多点数

（1）题目描述：

（2）示例

（3）分析

题目中以s字符串中：相同的字母为限制，要求方格内只包含不同字母对应的点位。

由此推论：==>

① 方格大小由相同元素中最近的决定，但注意：不是直接取得点位最小值，而是正好去除包含2个时的边界情况，即为：取第二小点位的值

② 点位(x,y)的坐标绝对值，决定方格大小，取值的时候需要对(x,y)的绝对值取max最大

③ 结合以上内容，得出采取数组+集合的方式，使用它的方法来完成。

（4）代码

import static java.lang.Math.*;class Solution {public int maxPointsInsideSquare(int[][] points, String s) {//对题目进行分析，如果有2个相同位：返回最大值-1；2个以上的：返回第二小-1即可。--> 满足只有一个得要求//所以接下来难的就是，如何存和排序了，采用数组+集合形式int[] str = new int[26]; // 统计哪一个位置出现次数超过2次int min = Integer.MAX_VALUE;int sum = 0;List<Integer>[] array = new List[27];//记录，每一个字母出现位置对应的值，因为for (int i = 0; i < 27; i++) {array[i] = new ArrayList<>(); // 初始化每个List}if (s.length() == 1)  return 1;for (int i = 0; i < s.length(); i++) {// i:第几位数字int num = s.charAt(i) - 'a';str[num] += 1; // 更新出现次数array[num].add(max(abs(points[i][0]), abs(points[i][1])));//记录当前值}for (int i = 0; i < 26; i++) {array[26].add(cheek(array, i, str[i]));// 获取所有去到的}min = array[26].stream().sorted().collect(Collectors.toList()).get(0);for (int[] p : points) {if (max(abs(p[0]), abs(p[1])) <= min) {sum++;}}return sum;}public int cheek(List<Integer>[] array, int num, int temp) {List<Integer> min = array[num].stream().sorted((a, b) -> b - a).collect(Collectors.toList());if (temp > 1)return min.get(temp - 2) - 1;return Integer.MAX_VALUE;}
}

（5）碎碎念

这是昨天（8.3）写的，这两天热感冒，状态不佳。写的时间很长，而且写的时候，基本是根据卡的用例来一步步完善的，所以代码整体不是那么连贯。

2024.8.04 简单

链接：572. 另一棵树的子树

（1）题目描述：

（2）示例

（3）分析

思路1：题目当中，让我们判断是否位子树，那么我首先想到的是字符串比较。只要包含在内即可，那么就引出一个问题，如何得到字符串？

==> 遍历，用中序遍历，这样左右分支皆可分开进行比对。

当然，不能单纯的比对，需要按照完全二叉树的形式来，空的部分以null填充，从而真正满足：字符串比对即为是否为子树的判断。

思路2：比对时，很明显，必须是大树的左子树或右子树与子树相同，或者直接两者一样！。那么只要递归比较一下是否相等就行了。

（4）代码

//这是思路1：字符串比对/*** 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 boolean isSubtree(TreeNode root, TreeNode subRoot) {String sbR =',' + getTreeToString(root, new StringBuilder()).toString();String sbT =',' + getTreeToString(subRoot, new StringBuilder()).toString();// *** ','很重要！*** 可防止判断时仅仅是位数上存在相同，如12 2这种if (sbR.contains(sbT))return true;return false;}public StringBuilder getTreeToString(TreeNode tree, StringBuilder sb) {//按照的类似是完全二叉树补全，空的填null，直接比对即可if (tree == null) {sb.append("null").append(',');} else {sb.append(tree.val).append(',');getTreeToString(tree.left, sb);// 先左，而中间，后右getTreeToString(tree.right, sb);}return sb;}}

//这是思路2：直接子树比较class Solution {public boolean isSubtree(TreeNode root, TreeNode subRoot) {if (root == null) {return subRoot == null;}if (isSameTree(root, subRoot)) {return true;}return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);}private boolean isSameTree(TreeNode s, TreeNode t) {if (s == null && t == null) {return true;}if (s == null || t == null) {return false;}if (s.val != t.val) {return false;}return isSameTree(s.left, t.left) && isSameTree(s.right, t.right);}}

两者比较：（左思路1，右思路2）