记录2025年每日一题刷题过程。

2025-08

342. 4的幂（20250815）

Details

给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 4 的幂次方需满足：存在整数 x 使得 n == 4x

示例 1：

输入：n = 16
输出：true

示例 2：

输入：n = 5
输出：false

示例 3：

输入：n = 1
输出：true

提示：

• -231 <= n <= 231 - 1

**进阶：**你能不使用循环或者递归来完成本题吗？

原本以为使用之前3的幂就能解，确实能解，但是耗时比较长，就来学习学习其他题解的解题方式。

是4的次幂，那么一定是2的次幂，就需要用到2的次幂的知识点来判断，就是2的次幂的二进制表示中，只有一个1 ， 使用 n & (n-1)一定等于0，然后才是判断是否是4的次幂

1 = 1

4 = 100

16 = 10000

参考灵神的题解；两种方法：位运算 / 数学（Python/Java/C++/C/Go/JS/Rust）

1780. 判断一个数字是否可以表示成三的幂的和（20250814）

Details

给你一个整数 n ，如果你可以将 n 表示成若干个不同的三的幂之和，请你返回 true ，否则请返回 false 。

对于一个整数 y ，如果存在整数 x 满足 y == 3x ，我们称这个整数 y 是三的幂。

示例 1：

输入：n = 12
输出：true
解释：12 = 31 + 32

示例 2：

输入：n = 91
输出：true
解释：91 = 30 + 32 + 34

示例 3：

输入：n = 21
输出：false

提示：

• 1 <= n <= 107

看到这个问题，最开始想到的是使用动态规划来处理，但是没写出来，可以后面尝试一下。

还是需要参考灵神的题解：三进制分解

大概的意思就是，将n用3进制形式表示，比如12 = 110, 21=210，然后对三进制判断，如果3进制中有数字2, 那么就没办法满足条件情况，返回false，否则返回true。

想想我们在取10进制数的每一位的时候，是怎么处理的，首先是取余数， n % 10， 然后在将 n /= 10，进入到下一位的运算，我们也可以这样弄。

遍历3进制的每一位，先对3取余数，n % 3， 然后在 n /= 3。

因为对3取余数的话，结果只可能是0, 1, 2 ，不会有在大的结果了。

Java

class Solution {
    public boolean checkPowersOfThree(int n) {
        while (n > 0) {
            if (n % 3 == 2) {
                return false;
            }
            n /= 3;
        }
        return true;
    }
}

326. 3 的幂（20250813）

Details

给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3x

示例 1：

输入：n = 27
输出：true

示例 2：

输入：n = 0
输出：false

示例 3：

输入：n = 9
输出：true

示例 4：

输入：n = 45
输出：false

提示：

• -231 <= n <= 231 - 1

题目给出一个n，判断n是否是3的幂次方。

第一种解题方式就是使用试除法，因为是3的幂次方，每次除以，相当于幂次方-1.

第二种方式是通过条件边界来处理，因为n是2³¹-1， 最大的n就是3⁹，所以如果是3的幂次方的话， n一定是3⁹的因子。

试除法

class Solution {
    public boolean isPowerOfThree(int n) {
        while (n != 0 && n % 3 == 0) {
            n /= 3;
        }
        return n == 1;
    }
}

最大幂的约数

class Solution {
    public boolean isPowerOfThree(int n) {
        return n > 0 && Math.pow(3, 9) % n == 0;
    }
}

相似的题目还有：

• 231. 2 的幂
• 342. 4的幂

2787. 将一个数字表示成幂的和的方案数（20250812）

Details

请你返回将 n 表示成一些 互不相同 正整数的 x 次幂之和的方案数。换句话说，你需要返回互不相同整数 [n1, n2, ..., nk] 的集合数目，满足 n = n1x + n2x + ... + nkx 。

由于答案可能非常大，请你将它对 109 + 7 取余后返回。

比方说，n = 160 且 x = 3 ，一个表示 n 的方法是 n = 23 + 33 + 53 。

示例 1：

输入：n = 10, x = 2
输出：1
解释：我们可以将 n 表示为：n = 32 + 12 = 10 。
这是唯一将 10 表达成不同整数 2 次方之和的方案。

示例 2：

输入：n = 4, x = 1
输出：2
解释：我们可以将 n 按以下方案表示：
- n = 41 = 4 。
- n = 31 + 11 = 4 。

提示：

• 1 <= n <= 300
• 1 <= x <= 5

终于是把这道题磨出来了，还是在看了题解的情况下，才把记忆化搜索的代码写出来了。

题目要求求出互不相同的正整数的x次幂的和等于n的方案数，所以可以把n看作是背包的总量，每个正整数的x次幂看作是物品，这样的话，我们就可以使用01背包的思路来解了。

这里的x大于等于1, 小于等于5, 所以最大的正整数就是当x等于1时，正整数等于n。

Java

class Solution {
    int[][] memo;
    int x;

    public int numberOfWays(int n, int x) {
        memo = new int[n + 1][n + 1];
        for (int[] m : memo) {
            Arrays.fill(m, -1);
        }
        this.x = x;
        return dp(n, n);
    }

    private int dp(int i, int n) {
        if (i == 0) {
            return n == 0 ? 1 : 0;
        }
        if (memo[i][n] != -1) {
            return memo[i][n];
        }
        int t = (int) Math.pow(i, x);

        // not choice
        int res = dp(i - 1, n);
        if (n >= t) {
            // choice
            res += dp(i - 1, n - t);
        }
        // 因为结果比较大，需要对结果取余
        return memo[i][n] = res % 1_000_000_007;
    }
}

118. 杨辉三角（20250801）

Details

给定一个非负整数 *numRows，*生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1:

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2:

输入: numRows = 1
输出: [[1]]

提示:

• 1 <= numRows <= 30

题目就是要求我们输出高度为numRows的杨辉三角的所有值。

把杨辉三角的每一排对齐：

[1]
[1,1]
[1,2,1]
[1,3,3,1]
[1,4,6,4,1]

设要计算的二维数组是c，计算方法如下：

• 每一排的第一个数和最后一个数都是1，即$c[i][0]=c[i][i] =1$
• 其余数字，等于左上方的数，加上正上方的数，即$c[i][j]=c[i-1][j-1] + c[i-1][j]$

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> c = new ArrayList<>();
        c.add(List.of(1));
        for (int i = 1; i < numRows; i++) {
            List<Integer> row = new ArrayList<>();
            row.add(1);
            // i 就是每一行的个数
            for (int j = 1; j < i; j++) {
                int t = c.get(i - 1).get(j - 1) + c.get(i - 1).get(j);
                row.add(t);
            }
            row.add(1);
            c.add(row);
        }
        return c;
    }
}

还有一种方法就是使用动态规划来求解，就是使用动态规划来做，现在还不会，带我学习一下。

2025-07

2683. 相邻值的按位异或（20250731）

Details

下标从 0 开始、长度为 n 的数组 derived 是由同样长度为 n 的原始 二进制数组 original 通过计算相邻值的 **按位异或（⊕）**派生而来。

特别地，对于范围 [0, n - 1] 内的每个下标 i ：

• 如果 i = n - 1 ，那么 derived[i] = original[i] ⊕ original[0]
• 否则 derived[i] = original[i] ⊕ original[i + 1]

给你一个数组 derived ，请判断是否存在一个能够派生得到 derived 的 有效原始二进制数组 original 。

如果存在满足要求的原始二进制数组，返回 true ；否则，返回 false 。

• 二进制数组是仅由 0 和 1 组成的数组。

示例 1：

输入：derived = [1,1,0]
输出：true
解释：能够派生得到 [1,1,0] 的有效原始二进制数组是 [0,1,0] ：
derived[0] = original[0] ⊕ original[1] = 0 ⊕ 1 = 1 
derived[1] = original[1] ⊕ original[2] = 1 ⊕ 0 = 1
derived[2] = original[2] ⊕ original[0] = 0 ⊕ 0 = 0

示例 2：

输入：derived = [1,1]
输出：true
解释：能够派生得到 [1,1] 的有效原始二进制数组是 [0,1] ：
derived[0] = original[0] ⊕ original[1] = 1
derived[1] = original[1] ⊕ original[0] = 1

示例 3：

输入：derived = [1,0]
输出：false
解释：不存在能够派生得到 [1,0] 的有效原始二进制数组。

提示：

• n == derived.length
• 1 <= n <= 105
• derived 中的值不是 0 就是 1 。

没想到今天就是7月的最后一天了，也是真的过的快，已经快3个月没有做算法题了。

今天这道题，就是通过递推出来公式，然后求解。

我们就用实例1，给出来的解释来做：

$derived[0] = original[0] ⊕ original[1]$

$derived[1] = original[1] ⊕ original[2]$

$derived[2] = original[2] ⊕ original[0]$

然后我们把两边同时都异或上，就会得到下面的公式：

$derived[0] ⊕ derived[1] ⊕ derived[2]= original[0] ⊕ original[1] ⊕ original[1] ⊕ original[2] ⊕ original[2] ⊕ original[0]$

然后就有，判断$derived[0] ⊕ derived[1] ⊕ derived[2] $是否等于0，来判断是否有这样一个数组，通过题目给出的算法，计算出来derived。

class Solution {
    public boolean doesValidArrayExist(int[] derived) {
        int xor  =0;
        for(int x: derived){
            xor ^= x;
        }
        return xor == 0;
    }
}

我们还需要知道一些疑惑的小技巧：

• 两个相同的数xor结果为0

2025-04

2874. 有序三元组中的最大值 II（20250402更新）

这里还有一道相同题目的简单题：2873. 有序三元组中的最大值 I

这两道题是第 365 场周赛题目，感兴趣的可以看下。

给你一个下标从 0 开始的整数数组 nums 。

请你从所有满足 i < j < k 的下标三元组 (i, j, k) 中，找出并返回下标三元组的最大值。如果所有满足条件的三元组的值都是负数，则返回 0 。

下标三元组 (i, j, k) 的值等于 (nums[i] - nums[j]) * nums[k] 。

开始想到的就是确定j的位置，然后在前面取最大值，和后面取最大值，这样的话，算数值就是最大的。

题目一和题目二的区别就是在于测试用例的范围上。

枚举 J

class Solution {
    public long maximumTripletValue(int[] nums) {
        // 计算前缀最大值和后缀最大值
        int n = nums.length;
      
      	// 计算后缀最大值，需要从右往左遍历，因为是求的[j+1, n-1]的最大值
        int[] sufMax = new int[n];
        sufMax[n - 1] = nums[n - 1];
        for (int j = n - 2; j >= 0; j--) {
            sufMax[j] = Math.max(sufMax[j + 1], nums[j]);
        }
      
      	// 计算前缀还好，就是从前往后遍历，通过preMax[i] = max(preMax[i-1], nums[i])
        int[] preMax = new int[n];
        preMax[0] = nums[0];
        for (int j = 1; j < n; j++) {
            preMax[j] = Math.max(preMax[j - 1], nums[j]);
        }
      	// 根据题目意思计算方程式的值
        long mx = 0;
        for (int j = 1; j < n - 1; j++) {
            long sum = (long) (preMax[j - 1] - nums[j]) * sufMax[j + 1];
            mx = Math.max(mx, sum);
        }
        return mx;
    }
}

枚举 K

class Solution {
    public long maximumTripletValue(int[] nums) {
        long ans = 0;
        long maxDiff = 0;
        long preMax = 0;

        for (int x : nums) {
            // 先把x当作nums[k]
            ans = Math.max(ans, maxDiff * x);
            // 在把x当作nums[j]
            maxDiff = Math.max(maxDiff, preMax - x);
            // 在把x当作nums[i]
            preMax = Math.max(preMax, x);
        }
        return ans;
    }
}

121. 买卖股票的最佳时机（20250403更新）

今天的每日一题是有序三元组II，昨天已经做过了，今天把买卖股票作为每日一题题目。

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

根据题意我们知道，想要获取的利润最大的话，我们就需要买的时候尽可能的小， 买的时候尽可能的大，所以就可以通过维护前缀最小值，或者维护后缀最大值的方式来求解。

维护前缀最小值

class Solution {
  	// 维护前缀最小值 方法一
  	// 通过使用数组，将每一个prices[i]的前缀最小值都维护起来, 空间复杂度O(n)
  	public int maxProfit(int[] prices) {
        // 对每一个prices[i]维护最小前缀值
        int n = prices.length;
        int[] preMin = new int[n];

        preMin[0] = prices[0];
        for (int i = 1; i < n; i++) {
            preMin[i] = Math.min(preMin[i - 1], prices[i]);
        }
        // 枚举卖出价格，计算最终结果
        int ans = 0;
        for (int i = 1; i < n; i++) {
            ans = Math.max(ans, prices[i] - preMin[i - 1]);
        }
        return ans;
    }
  	// 维护前缀最小值 方法二
  	// 通过变量，值维护当前prices[i]的前缀最小值，优化空间复杂度为O(1)
    public int maxProfit(int[] prices) {
        // 从左到右遍历的时候，同时维护前缀最小值minPrice
        int ans = 0, minPrice = prices[0];
        for (int p : prices) {
            ans = Math.max(ans, p - minPrice);
            minPrice = Math.min(minPrice, p);
        }
        return ans;
    }
}

维护后缀最大值

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[] sufMax = new int[n];
        sufMax[n - 1] = prices[n - 1];
      	// 计算最大后缀数组
        for (int i = n - 2; i >= 0; i--) {
            sufMax[i] = Math.max(sufMax[i + 1], prices[i]);
        }
      	// 计算最终结果
        int ans = 0;
        for (int i = 0; i < n - 1; i++) {
            ans = Math.max(ans, sufMax[i + 1] - prices[i]);
        }
        return ans;
    }
}

1123. 最深叶节点的最近公共祖先（20250404更新）

给你一个有根节点 root 的二叉树，返回它 最深的叶节点的最近公共祖先 。

回想一下：

• 叶节点 是二叉树中没有子节点的节点
• 树的根节点的 深度 为 0，如果某一节点的深度为 d，那它的子节点的深度就是 d+1
• 如果我们假定 A 是一组节点 S 的 最近公共祖先，S 中的每个节点都在以 A 为根节点的子树中，且 A 的深度达到此条件下可能的最大值。

Java

class Solution {
    private TreeNode ans;
    private int maxDepth = -1;

    public TreeNode lcaDeepestLeaves(TreeNode root) {
        dfs(root, 0);
        return ans;
    }

    int dfs(TreeNode node, int depth) {
        if (node == null) {
            maxDepth = Math.max(maxDepth, depth);
            return depth;
        }
        int leftMaxDepth = dfs(node.left, depth + 1);
        int rightMaxDepth = dfs(node.right, depth + 1);

        if (leftMaxDepth == rightMaxDepth && leftMaxDepth == maxDepth) {
            ans = node;
        }
        return Math.max(leftMaxDepth, rightMaxDepth);
    }
}

416. 分割等和子集（20250407更新）

标签：数组、动态规划

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

统计数组总和；如果和为奇数，直接返回false；加入记忆化搜索数组。

设数组总和为s，求能否从nums中选出一个子序列，其元素的和恰好等于s/2。

开始定义dfs(target)，表示求和为target的答案，但是和nums的元素关联不上，后面看了题解，将dfs修改成dfs(i, j)，表示从nums[0]到nums[i]中，是否存在和为j的子序列。

考虑选或者不选nums[i]的情况，就得到递推公式：

• 选： dfs(i-1, j-nums[i])
• 不选：dfs(i-1, j)

求两者是否有一个满足条件。

Java

class Solution {
    public boolean canPartition(int[] nums) {
        // 计算数组和
        int s = 0;
        for (int x : nums) {
            s += x;
        }
        // 如果和为奇数直接返回false
        if (s % 2 != 0) {
            return false;
        }
        // 初始化记忆化搜索数组
        int n = nums.length;
        int[][] memo = new int[n][s / 2 + 1];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        // 
        return dfs(n - 1, s / 2, nums, memo);
    }

    boolean dfs(int i, int j, int[] nums, int[][] memo) {
        if (i < 0) {
            return j == 0;
        }
        if (memo[i][j] != -1) {
            return memo[i][j] == 1;
        }
        // 选或者不选
        boolean res = j >= nums[i] && dfs(i - 1, j - nums[i], nums, memo) || dfs(i - 1, j, nums, memo);
        memo[i][j] = res ? 1 : 0;
        return res;

    }
}

编码过程中的困难点：

• 1、记忆化搜索数组memo是定义成int还是boolean类型？如何初始化？
  • 定义成int，初始化的时候默认-1， 这样在时候是就可以判断memo[i][j]是否等于-1；boolean不好判断。
  • 初始化只能每一层Arrays.fill(row, -1)来初始化。

3396. 使数组元素互不相同所需的最少操作次数（20250408更新）

标签：数组、哈希表

给你一个整数数组 nums，你需要确保数组中的元素 互不相同 。为此，你可以执行以下操作任意次：

• 从数组的开头移除 3 个元素。如果数组中元素少于 3 个，则移除所有剩余元素。

**注意：**空数组也视作为数组元素互不相同。返回使数组元素互不相同所需的 最少操作次数 。

如果存在重复的值，每次移除前面三个元素，也就是移除数组的前缀，那么剩下的一定是nums的后缀，那么问题就变成了，求最长不重复的nums的后缀元素。

当第i个元素重复，那么前面下标从0到i的话就有i+1个元素，除以3上取整的话，通过转化就得到了结果：i/3 + 1

上取整下取整转换公式的证明

Java

class Solution {
    public int minimumOperations(int[] nums) {
        // 求nums的最长无重复元素后缀
        Set<Integer> seen = new HashSet<>();
        for (int i = nums.length - 1; i >= 0; i--) {
            // set.add 添加成功之后返回true， 添加失败返回false
            if (!seen.add(nums[i])) {
                // (i+1)/3上取整 = i/3下去整+1
                return i / 3 + 1;
            }
        }
        return 0;
    }
}

3375. 使数组的值全部为 K 的最少操作次数（20250409更新）

标签：数组、哈希表

给你一个整数数组 nums 和一个整数 k 。

如果一个数组中所有 严格大于 h 的整数值都 相等 ，那么我们称整数 h 是 合法的 。

比方说，如果 nums = [10, 8, 10, 8] ，那么 h = 9 是一个 合法 整数，因为所有满足 nums[i] > 9 的数都等于 10 ，但是 5 不是 合法 整数。

你可以对 nums 执行以下操作：

• 选择一个整数 h ，它对于 当前 nums 中的值是合法的。
• 对于每个下标 i ，如果它满足 nums[i] > h ，那么将 nums[i] 变为 h 。

你的目标是将 nums 中的所有元素都变为 k ，请你返回 最少 操作次数。如果无法将所有元素都变 k ，那么返回 -1 。

真心觉得自己做题看到的就是题，灵神做题真的是连题目的裤衩都看透了😂。

题目的本质就是统计次大值的个数min(nums)和k的之间的关系， distinctCount表示数组中不同的元素个数

• k > min(nums)，无法满足直接返回-1
• k == min(nums) ，返回dictinctCount - 1
• k < min(nums), 返回distinctCount

自己写的代码

class Solution {
    public int minOperations(int[] nums, int k) {
        // 如果数组中有小于k的值，就没办法
        Arrays.sort(nums);

        for (int x : nums) {
            if (x < k) {
                return -1;
            }
        }
        // 每次取次大值，然后把最大值修改成次大值
        int n = nums.length;
        int cnt = 0;
        int mx = nums[n - 1];

        for (int i = n - 1; i >= 0; i--) {
            if (nums[i] < mx) {
                mx = nums[i];
                cnt++;
            }
            // 最后判断当i=0时，nums[i]是否大于k，大于k时还需要增加一次操作。
            if (i == 0 && nums[i] > k) {
                cnt++;
            }
        }
        return cnt;

    }
}

灵神写的代码

class Solution {
    public int minOperations(int[] nums, int k) {
        // 如果 k>min(nums)，无法满足要求，返回 −1。
        int min = Arrays.stream(nums).min().getAsInt();
        if (min < k) {
            return -1;
        }
        // 如果 k=min(nums)，操作次数为 nums 中的不同元素个数减一。比如 [5,2,5,4,5]→[4,2,4,4,4]→[2,2,2,2,2]，最大值 5→4→2，用了 2 次操作。
        // 如果 k<min(nums)，操作次数为 nums 中的不同元素个数。因为都变成 min(nums) 后，还需要再操作一次，才能都变成 k。
        int distinceCount = (int) Arrays.stream(nums).distinct().count();
        // return k == min? distinceCount - 1: distinceCount;
        return distinceCount - (k == min ? 1 : 0);
    }
}

Changelog

8/20/25, 11:06 AM

View All Changelog

• 4c155-Merge branch 'dev1'on 8/20/25