分类： 未分类

633.平方数之和

目标

给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a^2 + b^2 = c 。

示例 1：

输入：c = 5
输出：true
解释：1 * 1 + 2 * 2 = 5

示例 2：

输入：c = 3
输出：false

说明：

  • 0 <= c <= 2^31 - 1

思路

判断给定的整数是否是两个整数的平方和。

我们可以先从 0 开始计算每一个整数的平方和，直到平方和小于 Integer.MAX_VALUE, 不超过 10^5 个，将它保存到集合中，这一部分计算可以预处理。

然后我们还是同样的方法计算平方和 square，然后判断 c - square 是否在集合中，直到 square > c。

代码


/**
 * @date 2024-11-04 0:17
 */
public class JudgeSquareSum633 {

    public static Set<Integer> set = new HashSet<>(100000);

    static {
        long i = 0;
        long square = 0;
        while (true) {
            square = i * i;
            if (square > Integer.MAX_VALUE) {
                break;
            }
            set.add((int) square);
            i++;
        }
    }

    public boolean judgeSquareSum(int c) {
        long i = 0;
        long square = 0;
        while (true) {
            square = i * i;
            if (square > c) {
                break;
            } else if (set.contains((int) (c - square))) {
                return true;
            }
            i++;
        }
        return false;
    }

}

性能

2552.统计上升四元组

目标

给你一个长度为 n 下标从 0 开始的整数数组 nums ，它包含 1 到 n 的所有数字，请你返回上升四元组的数目。

如果一个四元组 (i, j, k, l) 满足以下条件，我们称它是上升的：

  • 0 <= i < j < k < l < n 且
  • nums[i] < nums[k] < nums[j] < nums[l] 。

示例 1：

输入：nums = [1,3,2,4,5]
输出：2
解释：
- 当 i = 0 ，j = 1 ，k = 2 且 l = 3 时，有 nums[i] < nums[k] < nums[j] < nums[l] 。
- 当 i = 0 ，j = 1 ，k = 2 且 l = 4 时，有 nums[i] < nums[k] < nums[j] < nums[l] 。
没有其他的四元组，所以我们返回 2 。

示例 2：

输入：nums = [1,2,3,4]
输出：0
解释：只存在一个四元组 i = 0 ，j = 1 ，k = 2 ，l = 3 ，但是 nums[j] < nums[k] ，所以我们返回 0 。

说明：

  • 4 <= nums.length <= 4000
  • 1 <= nums[i] <= nums.length
  • nums 中所有数字 互不相同 ，nums 是一个排列。

思路

题目看错了，并非是严格递增子序列，而是要求小1 大1 小2 大2，并且 小2 大于 小1， 大2 大于 大1。

// todo

代码

性能

3176.求出最长好子序列I

目标

给你一个整数数组 nums 和一个 非负 整数 k 。如果一个整数序列 seq 满足在范围下标范围 [0, seq.length - 2] 中存在 不超过 k 个下标 i 满足 seq[i] != seq[i + 1] ，那么我们称这个整数序列为 好 序列。

请你返回 nums 中 好 子序列 的最长长度

示例 1：

输入：nums = [1,2,1,1,3], k = 2
输出：4
解释：
最长好子序列为 [1,2,1,1] 。

示例 2：

输入：nums = [1,2,3,4,5,1], k = 0
输出：2
解释：
最长好子序列为 [1,1] 。

说明：

  • 1 <= nums.length <= 500
  • 1 <= nums[i] <= 10^9
  • 0 <= k <= min(nums.length, 25)

提示：

  • The absolute values in nums don’t really matter. So we can remap the set of values to the range [0, n - 1].
  • Let dp[i][j] be the length of the longest subsequence till index j with at most i positions such that seq[i] != seq[i + 1].
  • For each value x from left to right, update dp[i][x] = max(dp[i][x] + 1, dp[i - 1][y] + 1), where y != x.

思路

求整数数组 nums 的子序列，要求子序列中最多存在 k 个下标 i 满足 seq[i] != seq[i + 1]，即至多 k 对相邻元素 不同。

只要选出了子序列，那么相邻元素 不同 的对数就已经确定。

记忆化搜索超时了 // todo

代码

性能