class Solution {
    public int sumOfTheDigitsOfHarshadNumber(int x) {
        int s = 0;
        for(int v = x;v>0;v/=10){
            s += v % 10;
        }
        return x%s>0?-1:s;
    }
}

Java邓哈哈

class Solution {
    public int sumOfTheDigitsOfHarshadNumber(int x) {
        int s = 0;
        int y = x;
        while(x>0){
            s += (x % 10);
            x/= 10;
        }
        return y%s > 0?-1:s;
    }
}

需要注意的是：

1 Java的话，两个整数相除，默认是向下去余数的。

2 向上取整⌈⌉和向下取整⌊⌋符号.

3115. 质数的最大距离（20240701）

给你一个整数数组nums，返回两个（不一定不同的）质数在nums中下标的最大距离

判断是否是质数，因为求最大的距离，就可以从过头往后找第一质数，从后往前找倒数第一个质数，求下标的差值。

Java

class Solution {
    public int maximumPrimeDifference(int[] nums) {
        int i = 0;
        while(!isPrime(nums[i])){
            i++;
        }
        int j = nums.length-1;
        while(!isPrime(nums[j])){
            j--;
        }
        return j - i;
    }

    public boolean isPrime(int n){
        for(int i = 2;i * i <= n;i++){ // 判断质数 i*i <= n
            if(n % i == 0){
                return false;
            }
        }
        return n >= 2;  // 返回 n >= 2
    }
}

Python

Code...

Code...

2024-06

2806. 取整购买后的账户余额（20240612更新）

题目意思就是把purchaseAmount的个位数四舍五入，例如12四舍五入就是10， 15四舍五入就是20，也就是：

当个位数<=4时，把个位数变成0
当个位数>=5时，把个位数变成0，然后增加10

所以就得到一个通用的公式：(purchaseAmount+5)/10 向下取整

⌊\frac{(purchaseAmount+5)}{10}⌋ * 10

881. 救生艇（20240610更新）

题目给定数组people， people[i]表示第i个人的体重，船的数量不限，每条船可以承受的最大重量为limit。没搜穿最多可以同时载两个人，重量之和最多为limit，返回承载所有人所需要的最小船只数。

排序people然后使用双指针，分别指向第一个和最后一个元素，如果两个指针对应的元素小于等于limit，表示这两个人可以使用一条船，如果两个指针对应元素大于limit，那么就让重的人乘坐一条船，重复次操作。

Java

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        int ans = 0;
        Arrays.sort(people);
        int left = 0;
        int right = people.length -1;
        while(left <= right){
            if(people[left] + people[right] <= limit){
                left++;
            }
            right--;
            ans++;
        }
        return ans;
    }
}

Python

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        ans = 0
        left, right = 0, len(people)-1
        while left <= right:
            if people[left] + people[right] <= limit:
                left+=1
            right -= 1
            ans+=1
        return ans

var numRescueBoats = function(people, limit) {
    let ans = 0;
    people.sort((a,b)=>a-b);
    let left=0, right=people.length-1;
    while(left<=right){
        if(people[left] + people[right] <= limit){
            left++;
        }
        right--;
        ans++;
    }
    return ans;
};

2938. 区分黑球与白球（20240606更新）

题目给出一个s，仅包含0和1，将相邻的两个字符进行相比，把所有的1都移动到右侧。

遍历s的统计，统计1的个数cnt1，遇到0的时候，这个0和它左边的cnt1个1都要交换，把cnt1加入答案

Java

class Solution {
    public long minimumSteps(String s) {
        // 遍历s的统计，统计1的个数cnt1，遇到0的时候，这个0和它左边的cnt1个1都要交换，把cnt1加入答案
        long ans = 0;
        int cnt1 = 0;
        for(char c: s.toCharArray()){
            if(c == '1'){
                cnt1++;
            }else{
                ans += cnt1;
            }
        }
        return ans;
    }
}

Python

class Solution:
    def minimumSteps(self, s: str) -> int:
        ans, cnt1 = 0, 0
        for ch in s:
            if ch == '1':
                cnt1 += 1
            else:
                ans += cnt1
        return ans

var minimumSteps = function(s) {
    let ans = 0;
    let cnt1 = 0;
    for(const ch of s){
        if(ch == '1'){
            cnt1++;
        }else{
            ans += cnt1;
        }
    }
    return ans;
};

1103. 分糖果 II（20240603更新）

题目给出糖果的数量candies和需要分给几位小朋友num_people，从1开始一次给小朋友分糖，每次加1；

例如：candies = 10, num_people=3, 那么需要返回的结果就是 [5, 2, 3], 具体的过程如下：

ans = [1, 0, 0]
ans = [1, 2, 0]
ans = [1, 2, 3]
ans = [5, 2, 3]

大概得解题思路就是，只要candies大于0，我们就循环，每次循环完了将分配的糖果加1，将糖果值赋值到i%n的位置上。

class Solution {
    public int[] distributeCandies(int candies, int num_people) {
        int n = num_people;
        int[] ans = new int[n];
        for(int i=1;candies > 0;i++){
            ans[(i-1) % n] += Math.min(i, candies);  // 求i和candies的最小值
            candies -= i;
        }
        return ans;
    }
}

5 月

2982. 找出出现至少三次的最长特殊子字符串 II（20240530 更新）

今天的题目和昨天是一样的，按照相同的思路就可以解答，最后需要注意的就是需要判断，如果没有的话，是需要返回-1 的，而不是 0；

2981. 找出出现至少三次的最长特殊子字符串 I（20240529 更新）

给你一个仅由小写英文字母组成的字符串 s 。如果一个字符串仅由单一字符组成，那么它被称为特殊字符串。例如，字符串 "abc" 不是特殊字符串，而字符串 "ddd"、"zz" 和 "f" 是特殊字符串。
返回在 s 中出现 至少三次 的 最长特殊子字符串 的长度，如果不存在，则返回 -1 。

题目的大概意思就是，求字符串至少出现三次的特殊字符串ch的长度。三种情况：

s='aaa' 那么最长的特殊子串就是len(第一长)-2
s='aaabaa'，那么最长的特殊子串的长度就是min(len(第一长)-1， len(第二长))
s='aaabaabaa'，那么最长的特殊子串就是 第三长的子串的长度 len(aa)

参考：非暴力做法，分类讨论（Python/Java/C++/Go/JS/Rust）

2951. 找出峰值（20240528 更新）

今天是一道简单题，题目的意思大概就是找到严格大于左右两侧的数的下标，这个直接遍历判断是否严格大于两侧数据就可以了。

Python 的话就一行遍历的时候判断，其他语言按照思路装换就可以。

class Solution:
    def findPeaks(self, mountain: List[int]) -> List[int]:
        return [i for i in range(1, len(mountain) - 1)
                if mountain[i - 1] < mountain[i] > mountain[i + 1]]

2028. 找出缺失的观测数据（20240527 更新）

题目大概的意思就是，给出一个长度为 m 的数组 rolls, 一个整数 n 和一个m+n的均值 mean，求长度为 n 的数组的一种可能，如果求不出来的话返回空数组。

大概得思路就是，我们知道了长度是m+n，那么总和我们就知道，是total = mean*(m+n)，所以 n 个数的总和就是 rem = total - sum(rolls)，然后把 rem 分到长度为 n 的数组上；因为rem / n可能有余数，所以需要将余数分配到数组里面。

参考：灵神数学+构造（Python/Java/C++/C/Go/JS/Rust）

1738. 找出第 K 大的异或坐标值（20240526 更新）

标签：二维前缀和

题目大概得意思就是，给出一个 martix 的二维数据和一个 k 值，设 x 表示martix[i][j]到martix[0][0]的所有异或值的和，求第 k 大的 x 的下标。

题目看了很久才看懂，参考：二维前缀异或和这个题解。

主要的思路就是s[i+1][j+1] = s[i+1][j] xor s[i][j+1] xor s[i][j] xor martix[i][j]

2903. 找出满足差值条件的下标 I（20240525 更新）

题目的大概意思就是，给定 indexDifference 和 valueDifference，从数组中找到 abs(i - j) >= indexDifference 且满足 abs(nums[i] - nums[j]) >= valueDifference 的[i, j]下标值。

暴力求解 $O(n^2)$ 的复杂度，直接两层遍历做判断。

灵神给出了一个 $O(n)$ 复杂度的方式，现在还没有看懂，链接如下：O(n) 做法：双指针+维护最大最小（Python/Java/C++/C/Go/JS/Rust）

2 月

107. 二叉树的层序遍历 II （20240215 更新）

二叉树的层级遍历，使用 BFS 来处理，只不过这个题目返回从底向上的节点，这点与普通的层级遍历有一点不一样。

我们在遍历每一层的时候，可以使用 api 把每一层值放到最前面。

如果不清楚具体使用的 api，也可以正常存放，最后的时候将结果位置交换一下也是可以的。

Java

/**
 * 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 List<List<Integer>> levelOrderBottom(TreeNode root) {
        // 上一题是从上往下，这题是从下往上
        // 从上往下 然后倒序输出？
        List<List<Integer>> res = new LinkedList<>();
        if(root == null){
            return res;
        }

        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);

        while(!q.isEmpty()){
            // 每层的元素
            List<Integer> level = new LinkedList<>();
            int size = q.size();
            for(int i=0;i<size;i++){
                TreeNode node = q.poll();
                level.add(node.val);

                if(node.left != null){
                    q.offer(node.left);
                }
                if(node.right != null){
                    q.offer(node.right);
                }
            }
            // res.add(level);
            res.addFirst(level);
        }
        // 将元素进行交换
        // int len = res.size();
        // int left=0, right=len-1;
        // while(left<right){
        //     Collections.swap(res, left, right);
        //     left++;
        //     right--;
        // }
        // return res;
    }
}

var levelOrderBottom = function (root) {
  let res = [];
  if (root == null) {
    return res;
  }
  let q = [];
  q.push(root);
  while (q.length > 0) {
    let sz = q.length;
    let level = [];
    for (let i = 0; i < sz; i++) {
      let cur = q.shift();
      level.push(cur.val);
      if (cur.left != null) {
        q.push(cur.left);
      }
      if (cur.right != null) {
        q.push(cur.right);
      }
    }
    res.unshift(level); // 在数组开头添加元素
  }
  return res;
};

简单知识点

1、java 中向数组第一个位置插入元素nums.addFirst(val);

2、java 中队列的 api

Queue<Integre> q = new LinkedList<>();
q.offer(val);  // 添加元素
q.poll(); // 获取队列第一个元素，并删除
q.isEmpty(); // 判断队列是否为空

3、java 中获取 list 的长度用 size()方法，获取数组的长度用 length 属性

4、js 中数组操作 api

let nums = [2, 9, 5];
nums.pop(); // 删除最后一个元素
nums.unshift(val); // 将一个或多个元素添加到数组开头，并返回新数组的长度。
nums.shift(); // 删除数组第一个元素，并返回该元素的值，改变数组的长度

103. 二叉树的锯齿形层序遍历（20240216 更新）

给你二叉树的根节点 root，返回节点值的锯齿型层序遍历。（即先从往右，下一层在从优往左）

这个还是基于 BFS 来，我们只需要新建一个变量，来表示方向。

Java

class Solution {
    boolean direct = true;  // 为true是向右， false向左
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new LinkedList<>();
        if(root == null){
            return res;
        }
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while(!q.isEmpty()){
            int size = q.size();
            List<Integer> level = new LinkedList<>();
            // 判断方向
            for(int i=0;i<size;i++){
                TreeNode node = q.poll();
                // 实现 z 字形遍历
                if(direct){
                    level.addLast(node.val);
                }
                else{
                    level.addFirst(node.val);
                }
                if(node.left !=null){
                    q.offer(node.left);
                }
                if(node.right!=null){
                    q.offer(node.right);
                }
            }
            res.add(level);
            direct = !direct;  // 切换方向
        }
        return res;
    }
}

429. N 叉树的层序遍历（20240217 更新）

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）
树的序列输入使用层序遍历，每组子节点都由 null 值分割

层序遍历的话，我们还是需要再 BFS 的基础上来实现，我们需要再 push 到队列的时候循环节点的所有的子节点。

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> res = new LinkedList<>();
        if(root == null){
            return res;
        }

        Queue<Node> q = new LinkedList<>();
        q.offer(root);

        while(!q.isEmpty()){
            List<Integer> level = new LinkedList<>();
            int size = q.size();
            for(int i=0;i<size;i++){
                Node node = q.poll();  // 先从队列中取出节点，放入到List中
                level.add(node.val);

                List<Node> children = node.children;
                for(Node t: children){
                    q.offer(t);
                }
            }
            res.add(level);
        }
        return res;
    }
}

589. N 叉树的前序遍历（20240218 更新）

给定一个 n 叉树的根节点 root，返回其节点的前序遍历

我们参考二叉树的前序遍历方式，定义 traverse 函数用来递归，在遍历左右子节点的时候换成遍历 root 的所有子节点。

class Solution {
    List<Integer> res = new LinkedList<>();
    public List<Integer> preorder(Node root) {
        traverse(root);
        return res;
    }
    public void traverse(Node root){
        if(root == null){
            return;
        }
        res.add(root.val);
        for(Node node: root.children){
            traverse(node);
        }
    }
}

590. N 叉树的后序遍历（20240219 更新）

今天还是 n 叉树的遍历，还是利用二叉树的后序遍历来解这个题。

定义一个 traverse 的递归函数，先遍历子节点，最后在把当前节点的值存下来。

关于树的问题，需要思考了两个问题，一个就是每个节点需要做什么工作？二就是在什么时候做？

比如这道题，1 就是每个节点需要将值放到对应的容器里面，2 就是在遍历完之后，最后才放到容器里面。

class Solution {
    List<Integer> res = new LinkedList<>();

    public List<Integer> postorder(Node root) {
        traverse(root);
        return res;
    }

    public void traverse(Node root){
        if(root == null){
            return;
        }
        List<Node> children = root.children;
        for(Node node: children){
            traverse(node);
        }
        res.add(root.val);
    }
}

105. 从前序与中序遍历序列构造二叉树（20240220 更新）

题目给出一个前序遍历的数组 preorder 和一个中序遍历的数组 inorder，就二叉树。

我们知道前序遍历的第一个元素就是根节点，在中序遍历中，根节点左边的是左子树数据，右边的是有子树数据。

比如题目中给出 preorder=[3,9,20,15,7], inorder = [9,3,15,20,7]，可以看出元素 3 所对应的节点就是二叉树的根节点。

在中序遍历中根节点左边的就是左子树数据，右边的就是右子树数据，所有[9]是左子树元素 3 的左子树序列，[15, 20, 7]是元素 3 的右子树序列。

以此类推，我们对左子树维护新的前序中序序列，构建出来左树，对右子树维护新的前序中序序列，构建出来右树。

class Solution {
    HashMap<Integer, Integer> valToIndex = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // init
        for(int i=0;i<inorder.length;i++){  // 为什么要用中序的数组，不可以用前序的？ 因为需要再从中序遍历里面分割出来左子树数据和右子树数据
            valToIndex.put(inorder[i], i);
        }
        return build(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1);

    }
    public TreeNode build(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd){
        if(preStart > preEnd){
            return null;
        }
        int rootVal = preorder[preStart];
        int index = valToIndex.get(rootVal);

        int leftSize = index - inStart;
        TreeNode root = new TreeNode(rootVal);
        root.left = build(preorder, preStart+1, preStart+leftSize, inorder, inStart, index-1);
        root.right = build(preorder, preStart+leftSize+1, preEnd, inorder, index+1, inEnd);
        return root;
    }
}

106. 从中序与后序遍历序列构造二叉树（20240221 更新）

我们昨天了一个一道类似的题目，根据前序和中序构造二叉树，当前题目也是类似的思路。构建一个 build 函数来动态的构建二叉树。

inorder=[9, 3, 15, 20, 7]

Postorder = [9, 15, 7, 20, 3]

class Solution {
    HashMap<Integer, Integer> valToIndex = new HashMap<>();  // 我们需要分割出来左子树和右子树的数据，这里定义个map，用来保存中序遍历元素的下标

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        // inorder
        for(int i=0;i<inorder.length;i++){  // 为什么是中序遍历序列？后序可以吗？后序不行，因为我们要区分左右子树的序列，根据中序遍历，根节点左边是左子树数据，右边是右子树数据
            valToIndex.put(inorder[i], i);
        }
        return build(inorder, 0, inorder.length-1,postorder, 0, postorder.length-1);
    }

    public TreeNode build(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd){
        if(inStart>inEnd){
            return null;
        }
        int rootVal = postorder[postEnd];  //
        int index = valToIndex.get(rootVal);
        int leftSize = index - inStart;  // 找到左子树的长度
        TreeNode root = new TreeNode(rootVal);
        root.left = build(inorder, inStart, index-1, postorder, postStart, postStart+leftSize-1);  // 为啥-1?昨边size个,postStart下标是从0开始的postStart+leftSize-1就表示右边的下标
        root.right = build(inorder, index+1, inEnd,postorder, postStart+leftSize, postEnd-1);  // 为什么是postEnd-1？因为我们要去掉最后一个根节点数据
        return root;
    }
}

2583. 二叉树中的第 K 大层和（20240223 更新）

好几天没没写题解了，但是力扣上面的每日一题我还是在做的，最近是关于树的，自己恰好有一点理解，正好能解，今天说的是二叉树中的第 K 大层和。

给你一棵二叉树的根节点和一个正整数 k，树中的层和是指同一层上节点值的和。
返回树中第 k 大的层和(不一定不同)，如果树中少于 k 层，则返回-1。

简单来理解就是求二叉树的每层的和，看第 k 大的是和是多少。每层的和，这个我们能立马想到 bfs，我们就把每层的节点 val 加起来，存到列表 ans 里面，最后返回 ans 的第 ans.size()-k 个元素。

这里需要注意，题目给出的返回值是long型，第二点就是最后题目说的小于 k 层的话，直接返回-1。

第三点就是排序后为什么 ans.size()-k 表示第几大元素？

比如 ans = [1,2,3,4,5]，size = 5, k=2, 最后返回的最表示 3， size=5， k=4 的话，最后返回的是 1。

class Solution {
    public long kthLargestLevelSum(TreeNode root, int k) {
        // bfs 求解
        List<Long> ans = new LinkedList<>();
        if(root == null){
            return -1;
        }
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while(!q.isEmpty()){
            int sz = q.size();
            long level = 0;
            for(int i=0;i<sz;i++){
                TreeNode node = q.poll();
                level += node.val;
                if(node.left!=null){
                    q.offer(node.left);
                }
                if(node.right!=null){
                    q.offer(node.right);
                }
            }
            ans.add(level);
        }
        int n = ans.size();
        if(n<k){
            return -1;
        }
        // sort
        Collections.sort(ans);
        return ans.get(n-k); // 为什么n-k能表示最大第几个？
    }
}

这里补充一下 java 中数组、列表的排序实现，因为间隔了很久开始写 java，有一些 api 不是很熟悉，在做题的过程中遇到就把他总结下来。

1、对数组进行排序，这里需要区分是原子类型还是包装类型，Arrays 里面提供了一个 sort 的方法，可以用来排序，如果是原子类型的话，正序排序的话直接使用Arrays.sort(ans), 如果需要逆序排序的话，那么就只能进行转化了，1 是将原子类型转成包装类型在排序，或者是正序排序了之后创建新的容器逆序遍历。如果是包装类型，可以在 sort 函数里面传入自定义的比较器来实现正序或者是逆序排序

2、对列表进行排序，这里也提供了一个 Collections 的 util，里面也有一个 sort 的方法，也可以传入比较器来进行比较。一般列表都是有包装类型的泛型的。

List<Integer> res = new ArrayList<>();
Collections.sort(res, (a,b)->{
  return b-a;
});

2476. 二叉搜索树最近节点查询（20240224 更新）

今天早上一大早起来做算法题，结果 tle 超时了。

这道题的题目可以跳转到链接里面看，大概得意思就是给出一个二叉搜索树，和一个正整数数组，其中 ans[i] = [minx,max]，minx 表示树中小于等于数组 i 的最大值，如果不存在就返回-1.

这个题做过一版就是先遍中序遍历树，这样子就得到了一个升序的数组，然后在遍历 queries，找到其中最大最小值的下标，但是不出意外的超时了。然后看了题解，给出的题解里面使用到了二分查找回去对应元素的下标，其中还用到了 ArraysList，我用的是 LinkedList，这个也是导致超时的一个问题，后面需要去了解两者的差别。


class Solution {

    public List<List<Integer>> closestNodes(TreeNode root, List<Integer> queries) {

        List<Integer> ans = new ArrayList<>();
        dfs(root, ans);

        List<List<Integer>> res = new ArrayList<>();
        for(int val: queries){
            int maxval = -1, minval = -1;
            int idx = binarySearch(ans, val);
            if(idx !=ans.size()){
                maxval = ans.get(idx);
                if(ans.get(idx) == val){
                    minval = val;
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(minval);
                    list.add(maxval);
                    res.add(list);
                    continue;
                }
            }
            if(idx>0){
                minval = ans.get(idx-1);
            }
            List<Integer> list2 = new ArrayList<>();
            list2.add(minval);
            list2.add(maxval);
            res.add(list2);
        }
        return res;
    }

    public void dfs(TreeNode root, List<Integer> ans){
        if(root == null){
            return;
        }
        dfs(root.left, ans);
        ans.add(root.val);
        dfs(root.right, ans);
    }
   public int binarySearch(List<Integer> arr, int target) {
        int low = 0, high = arr.size();
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (arr.get(mid) >= target) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }
}

938. 二叉搜索树的范围和

给定二叉搜索树的根节点 root，返回值位于范围 $[low, high]$ 之间的所有节点的值的和

就是遍历一次二叉树，判断如果在区间里面就加上，如果不在就继续遍历；这里可以用上二叉搜索的特点，就是根节点的左子树的所有节点都小于根节点，根节点的右子树的所有节点都大于根节点，所以，我们可以判断节点的值所处的范围，指定遍历节点，和二分查找的思路类似。

class Solution:
    # BST的特性来做题
    ans = 0

    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        self.dfs(root, low, high)
        return self.ans

    def dfs(self, root, low, high):
        if not root:
            return
        if root.val < low:
            self.dfs(root.right, low, high)
        elif root.val > high:
            self.dfs(root.left, low, high)
        else:
            self.ans += root.val
            self.dfs(root.left, low, high)
            self.dfs(root.right, low, high)

2673. 使二叉树所有路径值相等的最小代价（20240228 更新）

满二叉树：满足除了叶子结点的所有节点都恰好有两个子节点，且所有叶子节点到根节点的距离相同

这道题我看了很久都没看懂，看了题解才有一点点的理解。

题目给出的 n 表示是节点的个数，cost 才表示每个节点的值。

考虑两种情况，一种是修改两个叶子结点的值， |x-y|，另一种情况就是操作叶子节点的上一层，我们把当前节点最大子节点的值加到当前节点上，这样我们就可以把它看做是子节点，进行相同的操作。

n // 2 表示 n 除以 2 并进行向下取整

class Solution:
    def minIncrements(self, n: int, cost: List[int]) -> int:
        # 1 叶子结点 x y 只能增加x或者y
        ans = 0
        for i in range(n-2, 0, -2):
            ans += abs(cost[i] - cost[i+1])  # 先处理两两叶子节点
            # 叶子结点i和i+1的双亲节点下标为i/2（整数除法）
            cost[i//2] += max(cost[i], cost[i+1])
        return ans

225. 用队列实现栈

Python

class MyStack:

    def __init__(self):
        self.arr = []

    def push(self, x: int) -> None:
        self.arr.append(x)

    def pop(self) -> int:
        return self.arr.pop()

    def top(self) -> int:
        return self.arr[-1]

    def empty(self) -> bool:
        return True if not self.arr else False

Java

class MyStack {
    Queue<Integer> q = new LinkedList<>();
    int top_elem = 0;

    public MyStack() {

    }

    public void push(int x) {
        q.offer(x);
        top_elem = x;
    }

    public int pop() {
        int size = q.size();
        while(size > 2){
            q.offer(q.poll());
            size--;
        }
        top_elem = q.peek();
        q.offer(q.poll());
        return q.poll();
    }

    public int top() {
        return top_elem;
    }

    public boolean empty() {
        return q.isEmpty();
    }
}

3 月

2917. 找出数组中的 K-or 值（20240306 更新）

说实话这个题我到现在都没有看懂，只能努力看懂题解了。

实际上，题目要我们统计每一位上出现的 1 的数量，如果达到了 k 这一位的结果就是 1 否则是 0
为了得到 x 的第 k 位，我们可以使用 x>>k&1，统计数量进行判断即可。时间复杂度为 O(31n)，枚举每一个为并遍历数组

class Solution:
    def findKOr(self, nums: List[int], k: int) -> int:
        res =  0
        for i in range(31):   # 为什么是31位 因为是非负整数
            ans = 0
            for num in nums:
                t1 = num >> i  # 表示右移i位的话
                if t1 & 1:  # 判断最后一位是不是1，如果是1，ans + 1
                    ans += 1
            if ans >= k:  # 最后判断ans的个数是否大于等于1， 如果大于等于1的话
                res = res | (1 << i)  # res的第i位设置成1
        return res

这里有许多的疑问，什么是 k&1， >= 又是啥， |=， <<这些操作符是什么？

Python 运算符

无论是什么编程语言都存在着许多种类的运算符，像是 +-_/% 这些属于算术运算符，像是>,<,>=, <= 这些属于比较运算符，=,+=, -+, _=, //=属于赋值运算符， &|属于为运算符。

通过上面的题解，我们来看一下按位与和右移的逻辑：&按位与运算符：参与运算的两个值，如果两个相应位都是 1，则该位的结果为 1，否则为 0；

num >> i & 1 是什么含义呢？

>> 表示右移 i 位，这样的话在按位与上 1 的话，就可以判断第 i 位是 1 还是 0。

这里有一个优先级的问题，就是 >>的优先级高于 & 的优先级。

>>右移的话，还有一个作用，就是用来除 2，比如 n>>i 的话就表示 n /= 2^i

ans |= 1 << i 是什么含义？

|= 叫做按位或且赋值运算符， ans |= i 等价于 ans = ans |i。

这个语句的含义就是把 ans 的第 i 位设置成 1

2575. 找出字符串的可整除数组（20240307 更新）

给你一个下标从 0 开始的字符串 word，长度为 n，由 0 到 9 的数字组成，另给你一个正整数 m。
word 的可整除数组 div 是一个长度为 n 的整数数组，并满足：
如果 word0[0...i]所表示的数值能被 m 整除，div[i] = 1
否则 div[i] = 0
返回 word 的可整除数组。
实例 1：
输入：word = "998244353", m = 3
输出：[1,1,0,0,0,1,1,0,0]
解释：仅有 4 个前缀可以被 3 整除："9"、"99"、"998244" 和 "9982443" 。

简单来理解题目就是 word[0...i]能不能被 m 整除，如果能的 div[i]就是 1。

解决这个题的话，我们是不能用暴力来接的，因为这个数字很大，会超过范围。

我们从左到右遍历 word，初始化 x=0，没遇到一个数字 d，就把 x 更新为 $(10x + d) mod m$ 。

class Solution:
    def divisibilityArray(self, word: str, m: int) -> List[int]:
        ans = []
        x = 0
        for d in map(int, word):
            x = (x * 10 + d) % m  # 最后的结果x是不会超过m的
            ans.append(0 if x else 1)  # 最后判断x的结果，如果是非0的话，就表示不能整除，值为0，如果是0的话表示能整除，结果是1
        return ans

python 里面的 map(func, iterable) 会将可迭代对向 iterable 里面的每一个值用 func 函数执行一次。

class Solution:
    def div1(self, word: str):  # 9982
        x = 0
        for d in map(int, word):
            x = 10 * x + d
            print(x)  # 9， 99， 998， 9982

这个方法的话就会从第 0 位开始每次累加后面的数字，输出 word[i]的数值。

2129. 将标题首字母大写（20240311 更新）

很久没有认真做力扣的每日一题了，不是不做，感觉都太难了，我这个菜鸡表示不会做，每天就是做一些简单题，哈哈。

通过昨天的力扣的周赛，大概有了一些体会，就是说第一简单题，利用模拟的方式就能够解决，但是后面的两道中等题的话，就需要一定的技巧，暴力解是通过不了的。

今天要做的是 2129 题，将标题首字母大写，这个通过模拟就能够解决。

说实话，编程语言的特性还是具有很大的差别， python 的话，通过一个 map + func 就能够解决，java 就不能，所以说用什么语言思路也具有差别。

我是通过模拟的思路来求解的，就是分割，然后判断字符串的长度来调用 python 的 title 还是 lower，下面是灵神的题解，真的是太巧了，写了两年的 python 自己都没有这样子的能力。

用 lambda 定义一个函数，判断 s 的长度来调用方法，最后通过 map 函数加上 join 来返回。

class Solution:
    def capitalizeTitle(self, title: str) -> str:
        f = lambda s: s.title() if len(s) > 2 else s.lower()
        return ' '.join(map(f, title.split()))

用 java 解的话，思路还是一样。

定义了一个 StringBuilder 的对象，当 ans 不为空的时候，先往里面添加一个空格，然后先把第一个字母放进去，然后把后面的字符放进去。

class Solution {
    public String capitalizeTitle(String title) {
        StringBuilder ans = new StringBuilder();
        for(String s: title.split(" ")){
            boolean equals = "".equals(ans.toString());
            if(!equals){  // 开始第一次循环是不会进来，因为ans为空
                ans.append(" ");
            }
            if(s.length() > 2){
                ans.append(s.substring(0, 1).toUpperCase());  // substring(startIndex, endIndex)
                s = s.substring(1);  // substring(startIndex, endest) 到最后
            }
            ans.append(s.toLowerCase());  // 转小写
        }
        return ans.toString();  // 返回str
    }
}

1261. 在受污染的二叉树中查找元素（20240312 更新）

如果需要看题目的话，可以点进到这个题目的链接进行查看。

题目的主要含义就是，给出一个被污染的二叉树，里面的值全是-1，需要我们用 FindElements 还原这个二叉树，规则是，节点不为空的话，是左节点值就等于 root.val _ 2 + 1, 如果是有节点的话就是 root.val _ 2 + 2，很像是二叉树的顺序存储的结构。

还有一个 find 方法我们需要完善，就是判断 target 是否在二叉树里面，我们在还原二叉树的时候，可以定义一个数据结构来存这些值，直接在里面查找，就不用再遍历二叉树了。

class FindElements {
    List<Integer> vals = new LinkedList<>();

    public FindElements(TreeNode root) {
        // 用来还原root
        // 2x+1, 2x+2 好像是顺序存储二叉树？
        // 前序遍历
        root.val = 0;
        this.vals.add(root.val);
        traverse(root);
    }
    public void traverse(TreeNode root){
        if(root==null){
            return;
        }
        if(root.left != null){
            root.left.val = 2 * root.val + 1;
            this.vals.add(root.left.val);
        }
        if(root.right != null){
            root.right.val = 2 * root.val + 2;
            this.vals.add(root.right.val);
        }
        traverse(root.left);
        traverse(root.right);
    }
    public boolean find(int target) {
        // 用来查找target
        return this.vals.contains(target);
    }
}

我们顺便简单看一下灵神的解法，

class FindElements {
    private final Set<Integer> s = new HashSet<>();

    public FindElements(TreeNode root) {
        dfs(root, 0);
    }

    public boolean find(int target) {
        return s.contains(target);
    }
    private void dfs(TreeNode root, int val){
        if(root == null){
            return;
        }
        s.add(val);
        dfs(root.left, val * 2 + 1);
        dfs(root.right, val * 2 + 2);
    }
}

灵神所用时间为 21ms，定义的是一个 set，我上面定义的是一个 list，耗时 380ms，后面研究一下这些数据结构的优缺点，全都忘记了都。

List<Integer> vals = new LinkedList<>();
Set<Integer> vals = new HashSet<>()

二叉树知识点最详细最全讲解

2864. 最大二进制奇数（20240313 更新）

给你一个二进制字符串 s，其中至少包含一个'1'.
你必须按某种方式重新排列字符串中的位，使得二进制数字式可以有该组合生成的最大的二进制奇数。
实例一、
输入：s = "010"
输出："001"
解释：因为字符串 s 中仅有一个 '1' ，其必须出现在最后一位上。所以答案是 "001" 。

很愉快，今天是一道简单题。

因为二进制除了最后一位是奇数 1 的话，前面的数字都是表示偶数，所以我们只需要那一个 1 放到最后一位，然后把其他的 1 放在前面，把剩下的的 0 放在中间就可以了。

这里直接拿灵神的题解来说，因为思路都是一样的，但是写出来的代码效率，以及代码的简洁度还是有差别的。

Python 题解：

class Solution:
    def maximumOddBinaryNumber(self, s: str) -> str:
        cnt1 = s.count('1')
        return '1' * (cnt1-1) + '0' * (len(s)-cnt1) + '1'

他这里使用 count()函数来计算 1 的个数，我是直接遍历求的 1 的个数和 0 的个数，然后把返回的字符串拼接起来，我这里用的是数组最后在 join 起来，感觉走了很多弯路，不够直接。

Java 题解：

class Solution {
    public String maximumOddBinaryNumber(String s) {
        int cnt1 = (int)s.chars().filter(c->c=='1').count();  // 把s字符串转成char数组，然后用filter过滤求值
        return "1".repeat(cnt1-1) + "0".repeat(s.length()-cnt1) + "1";
    }
}

java 也是一样的，s.chars()将字符串转化成一个 IntStream，用 filter 来判断过滤出来 1 的个数，最后用 repeat 来构建出来重复的部分。

2789. 合并后数组中的最大元素（20240314 更新）

给你一个下标从 0 开始、由正整数组成的数组 nums
你可以在数组上执行下面操作任意次：
选中一个同时满足 0<=i<num.length-1 和 nums[i] <= nums[i+1]的整数 i，将元素 nums[i+1]替换为 nums[i] + nums[i+1]，并从数组中删除元素 nums[i]

简单理解就是从后往前遍历，如果 nums[i-1] <= nums[i]，就更新 nums[i]

class Solution:
    def maxArrayValue(self, nums: List[int]) -> int:
        s = nums[-1]

        for idx in range(len(nums) - 2, -1, -1):
            s = s +  nums[idx] if nums[idx] <= s else nums[idx]
        return s

4 月

2810. 故障键盘（202404-1 更新）

好久都没有写每日一题了，今天在写写。

你的笔记本键盘存在故障，每当你在上面输入字符 i 的时候，他会反转你所写的字符串。而输入其他字符则可以正常工作。给你一个下标从 0 开始的字符串 s，请你用故障键盘一次输入每个字符。返回最终笔记本屏幕上输出的字符串。

这个题的话是一个简单题，直接使用模拟就能够解决。但是还有其他的更好的办法，使用双端队列。把反转看成是往字符串的头部添加字符。

如果当前处于【在字符串尾部添加字符】的状态，那么遇到 i 后，改成【往字符串头部添加字符】的状态。
如果当前处于【在字符串头部添加字符】的状态，那么遇到 i 后，改成【往字符串尾部添加字符】的状态。

class Solution {
    public String finalString(String s) {
        Deque<Character> q = new ArrayDeque<>();  // 双端队列
        boolean tail = true;

        for(char c: s.toCharArray()){
            if(c == 'i'){
                tail = !tail;
            }
            else if(tail){
                q.addLast(c);
            }
            else{
                q.addFirst(c);
            }
        }
        StringBuilder ans = new StringBuilder();
        for(char c: q){
            ans.append(c);
        }
        if(!tail){ // 表示倒着输出
            ans.reverse();
        }
        return ans.toString();
    }
}

Deque 表示双端队列，有 addLast、addFirst()等方法。在最后判断 tail 是否为 false，如果为 false 就表示需要在反转一次。

Python 中也有双端队列，在 collections 里面，简单操作如下：

In [1]: from collections import deque
In [2]: q = deque()
In [3]: q.append(5)
In [4]: q
Out[4]: deque([5])
In [5]: q.appendleft(2)
In [6]: q
Out[6]: deque([2, 5])

80. 删除有序数组中的重复项 II（20240409 更新）

给你一个有序数组 nums，请你原地删除重复出现的元素，使得出现次数超过两次的元素只出现两次，返回删除后的数组的长度。
不要使用额外的数组空间，你必须在原地修改输入数组，并在使用 O(1)额外空间的条件下完成。

这里要求重复的元素只出现 2 次，其他的题目可能会要求只出现 1 次，所以这里可以写成通用的方法。

我们使用两个指针，一个遍历，一个指向存放位置。

class Solution {
    public int removeDuplicates(int[] nums) {
        return process(nums, 2);  // 指定k为2
    }
    public int process(int[] nums, int k){
        int idx = 0;
        for(int x: nums){
            if(idx<k || nums[idx-k] != x){  // 下标idx-k就是这个元素出现在返回数组的最开始的位置。
                nums[idx++] = x;
            }
        }
        return idx;
    }
}

相同题目：26. 删除有序数组中的重复项

2739. 总行驶距离（20240424 更新）

现在脑子里面都是浆糊，转不过弯。

题目在上面。我们只需要使用题目给出的题意进行简单模拟，就能够解决这道题。

比如我们 mainTank 减 5，我们就从 addtionTank 拿一升油，知道 mainTank 小于 5.

class Solution:
    def distanceTraveled(self, mainTank: int, additionalTank: int) -> int:
        ans = 0
        while mainTank >= 5:  # 模拟
            mainTank -= 5
            ans += 50

            if additionalTank:
                additionalTank -= 1
                mainTank += 1
        return ans + mainTank * 10

Changelog

Last Updated: View All Changelog

3d2e0-
feat(wiki): algo: 算法总结
On 3/30/25

力扣2024每日一题题解

3099. 哈沙德数（20240703）

3115. 质数的最大距离（20240701）

2806. 取整购买后的账户余额（20240612更新）

881. 救生艇（20240610更新）

2938. 区分黑球与白球（20240606更新）

1103. 分糖果 II（20240603更新）

2982. 找出出现至少三次的最长特殊子字符串 II（20240530 更新）

2981. 找出出现至少三次的最长特殊子字符串 I（20240529 更新）

2951. 找出峰值（20240528 更新）

2028. 找出缺失的观测数据（20240527 更新）

1738. 找出第 K 大的异或坐标值（20240526 更新）

2903. 找出满足差值条件的下标 I（20240525 更新）

107. 二叉树的层序遍历 II （20240215 更新）

103. 二叉树的锯齿形层序遍历（20240216 更新）

429. N 叉树的层序遍历（20240217 更新）

589. N 叉树的前序遍历（20240218 更新）

590. N 叉树的后序遍历（20240219 更新）

105. 从前序与中序遍历序列构造二叉树（20240220 更新）

106. 从中序与后序遍历序列构造二叉树（20240221 更新）

2583. 二叉树中的第 K 大层和（20240223 更新）

2476. 二叉搜索树最近节点查询（20240224 更新）

2673. 使二叉树所有路径值相等的最小代价（20240228 更新）

2917. 找出数组中的 K-or 值（20240306 更新）

2575. 找出字符串的可整除数组（20240307 更新）

2129. 将标题首字母大写（20240311 更新）

1261. 在受污染的二叉树中查找元素（20240312 更新）

2864. 最大二进制奇数（20240313 更新）

2789. 合并后数组中的最大元素（20240314 更新）

2810. 故障键盘 （202404-1 更新）

80. 删除有序数组中的重复项 II（20240409 更新）

2739. 总行驶距离（20240424 更新）

求求了，快滚去学习！！！

2810. 故障键盘（202404-1 更新）