标签： easy

目标

给你两棵二叉树，原始树 original 和克隆树 cloned，以及一个位于原始树 original 中的目标节点 target。

其中，克隆树 cloned 是原始树 original 的一个 副本 。

请找出在树 cloned 中，与 target 相同 的节点，并返回对该节点的引用（在 C/C++ 等有指针的语言中返回 节点指针，其他语言返回节点本身）。

注意：你 不能 对两棵二叉树，以及 target 节点进行更改。只能 返回对克隆树 cloned 中已有的节点的引用。

说明：

• 树中节点的数量范围为 [1, 10^4] 。
• 同一棵树中，没有值相同的节点。
• target 节点是树 original 中的一个节点，并且不会是 null 。

进阶：如果树中允许出现值相同的节点，将如何解答？

思路

这道题挺简单的，这让我想起 100.相同的树 这道题，都是两棵树的同步遍历。

代码

/**
 * @date 2024-04-03 0:01
 */
public class GetTargetCopy1379 {
    public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
        if (original == null) {
            return null;
        } else if (target.equals(original)) {
            return cloned;
        } else {
            TreeNode res = getTargetCopy(original.left, cloned.left, target);
            if (res == null) {
                res = getTargetCopy(original.right, cloned.right, target);
            }
            return res;
        }
    }
}

性能

目标

你的笔记本键盘存在故障，每当你在上面输入字符 'i' 时，它会反转你所写的字符串。而输入其他字符则可以正常工作。

给你一个下标从 0 开始的字符串 s ，请你用故障键盘依次输入每个字符。

返回最终笔记本屏幕上输出的字符串。

示例 1：

输入：s = "string"
输出："rtsng"
解释：
输入第 1 个字符后，屏幕上的文本是："s" 。
输入第 2 个字符后，屏幕上的文本是："st" 。
输入第 3 个字符后，屏幕上的文本是："str" 。
因为第 4 个字符是 'i' ，屏幕上的文本被反转，变成 "rts" 。
输入第 5 个字符后，屏幕上的文本是："rtsn" 。
输入第 6 个字符后，屏幕上的文本是： "rtsng" 。
因此，返回 "rtsng" 。

示例 2：

输入：s = "poiinter"
输出："ponter"
解释：
输入第 1 个字符后，屏幕上的文本是："p" 。
输入第 2 个字符后，屏幕上的文本是："po" 。
因为第 3 个字符是 'i' ，屏幕上的文本被反转，变成 "op" 。
因为第 4 个字符是 'i' ，屏幕上的文本被反转，变成 "po" 。
输入第 5 个字符后，屏幕上的文本是："pon" 。
输入第 6 个字符后，屏幕上的文本是："pont" 。
输入第 7 个字符后，屏幕上的文本是："ponte" 。
输入第 8 个字符后，屏幕上的文本是："ponter" 。
因此，返回 "ponter" 。

说明：

• 1 <= s.length <= 100
• s 由小写英文字母组成
• s[0] != 'i'

思路

当输入i的时候，之前所有的输入都需要反转，i字符本身不显示。使用split无法处理连续为i以及结尾为i的情况。

最直接的做法就是模拟操作，但是反转字符串的复杂度较高。考虑使用双端队列，当反转时，相当于从队首加入字符，从队尾开始读取。

代码

/**
 * @date 2024-04-01 8:42
 */
public class FinalString2810 {
    public String finalString_v1(String s) {
        StringBuilder res = new StringBuilder();
        Deque<Character> q = new ArrayDeque<>();
        boolean reverse = false;
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if ('i' == ch) {
                reverse = !reverse;
            } else if (reverse) {
                q.push(ch);
            } else {
                q.offer(ch);
            }
        }
        Iterator<Character> it;
        if (reverse) {
            it = q.descendingIterator();
        } else {
            it = q.iterator();
        }
        while (it.hasNext()) {
            res.append(it.next());
        }
        return res.toString();
    }

    public String finalString(String s) {
        StringBuilder res = new StringBuilder();
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if ('i' == chars[i]) {
                res.reverse();
            } else {
                res.append(chars[i]);
            }
        }
        return res.toString();
    }
}

性能

按道理来说应该是finalString_v1更快一些，res.reverse()时间复杂度是 O(n/2)，会将元素左右互换。但是leetcode显示的用时分布反而finalString更快，耗时是finalString_v1的一半2ms，应该与数据规模有关吧，字符串长度最大才100。finalString_v1有更多的流程控制，还体现不出性能。

目标

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

说明：

• 2 <= nums.length <= 10^4
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9
• 只会存在一个有效答案

进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

思路

除了每日一题还开了一个进度，今天找个简单的来做吧。这题是leetcode的abandon，应该所有人都会遇到。

这道题我首先想到的还是暴力解法。本来是很抗拒的，但是如果可以先排序，然后找到大于target的下标来缩小范围，是不是会好一些。

但是这样会改变原数组元素的下标，还是暴力解吧。

官网的解使用了Hash表，但是我首先就把使用hash表来存储排除了，也许是觉得就是查两个下标就要存10^9个数据会不会太浪费了。这样不好，感觉思维被限制了。

再给自己强调一下，如果需要降低查询的时间复杂度，首先要考虑hash表！hash表结合了数组与链表的优点，理想情况下操作的时间复杂度为O(1)，但是空间利用率不高，下标由值的hash函数来决定。

代码

随便贴一下官网的解吧。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; ++i) {
            if (hashtable.containsKey(target - nums[i])) {
                return new int[]{hashtable.get(target - nums[i]), i};
            }
            hashtable.put(nums[i], i);
        }
        return new int[0];
    }
}

性能

时间复杂度O(n)最多一次遍历，空间复杂度O(n)用于hash表开销。

目标

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

如果下标三元组 (i, j, k) 满足下述全部条件，则认为它是一个 山形三元组 ：

• i < j < k
• nums[i] < nums[j] 且 nums[k] < nums[j]

请你找出 nums 中 元素和最小 的山形三元组，并返回其 元素和 。如果不存在满足条件的三元组，返回 -1 。

示例 1：

输入：nums = [8,6,1,5,3]
输出：9
解释：三元组 (2, 3, 4) 是一个元素和等于 9 的山形三元组，因为： 
- 2 < 3 < 4
- nums[2] < nums[3] 且 nums[4] < nums[3]
这个三元组的元素和等于 nums[2] + nums[3] + nums[4] = 9 。可以证明不存在元素和小于 9 的山形三元组。

示例 2：

输入：nums = [5,4,8,7,10,2]
输出：13
解释：三元组 (1, 3, 5) 是一个元素和等于 13 的山形三元组，因为： 
- 1 < 3 < 5 
- nums[1] < nums[3] 且 nums[5] < nums[3]
这个三元组的元素和等于 nums[1] + nums[3] + nums[5] = 13 。可以证明不存在元素和小于 13 的山形三元组。

示例 3：

输入：nums = [6,5,4,3,4,5]
输出：-1
解释：可以证明 nums 中不存在山形三元组。

提示：

• 3 <= nums.length <= 50
• 1 <= nums[i] <= 50

思路

它标的是一道简单题，但是在我思考的过程中甚至产生了自我怀疑。以至于后面有些抓狂，直接暴力求解，不考虑性能，不考虑优雅，什么都不顾，只要能做出来。好以此来证明自己不是那么傻。

这道题让我们求数组中满足某些条件的三元组之中和最小的那一个，满足的条件就是 小 大 小，可以不连续。

暴力解法上来直接就排除了，什么动态规划直接pass。简单题需要这些吗？然后我就被上了一课，不用这些真想不出来。方法没有高低之分。

代码

/**
 * @date 2024-03-29 0:52
 */
public class MinimumSum2908 {

    public int minimumSum(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = Integer.MAX_VALUE;
        dp[nums.length - 1] = Integer.MAX_VALUE;
        for (int i = 1; i < nums.length; i++) {
            int tmp = i;
            int left = Integer.MAX_VALUE;
            while (i >= 1) {
                if (nums[tmp] > nums[i - 1]) {
                    left = Math.min(left, nums[i - 1]);
                }
                i--;
            }
            if (left == Integer.MAX_VALUE) {
                dp[tmp] = Integer.MAX_VALUE;
                i = tmp;
                continue;
            }
            int right = Integer.MAX_VALUE;
            i = tmp;
            while (i < nums.length - 1) {
                if (nums[tmp] > nums[i + 1]) {
                    right = Math.min(right, nums[i + 1]);
                }
                i++;
            }
            if (right != Integer.MAX_VALUE) {
                dp[tmp] = left + nums[tmp] + right;
            } else {
                dp[tmp] = Integer.MAX_VALUE;
            }
            i = tmp;
        }
        Arrays.sort(dp);
        return dp[0] == Integer.MAX_VALUE ? -1 : dp[0];
    }
}

性能

目标

给你一个正整数 n ，开始时，它放在桌面上。在 10^9 天内，每天都要执行下述步骤：

• 对于出现在桌面上的每个数字 x ，找出符合 1 <= i <= n 且满足 x % i == 1 的所有数字 i 。
• 然后，将这些数字放在桌面上。

返回在 10^9 天之后，出现在桌面上的 不同 整数的数目。

注意：

• 一旦数字放在桌面上，则会一直保留直到结束。
• % 表示取余运算。例如，14 % 3 等于 2 。

示例 1：

输入：n = 5
输出：4
解释：最开始，5 在桌面上。 
第二天，2 和 4 也出现在桌面上，因为 5 % 2 == 1 且 5 % 4 == 1 。 
再过一天 3 也出现在桌面上，因为 4 % 3 == 1 。 
在十亿天结束时，桌面上的不同数字有 2 、3 、4 、5 。

示例 2：

输入：n = 3 
输出：2
解释： 
因为 3 % 2 == 1 ，2 也出现在桌面上。 
在十亿天结束时，桌面上的不同数字只有两个：2 和 3 。 

说明：

1 <= n <= 100

思路

这虽然是个简单题，但也不是一眼就能看出答案的。甚至条件稍微改一下就变得麻烦了，比如将10^9天改为有限的几天。

说回这道题，开始向桌面上放一个数字，然后需要找到对桌面数字取模余1的数，第二天将其也放在桌面上，如此循环。

对于数字n来说，n-1与1肯定是满足条件的，然后n-1的约数也符合条件。

考虑到是经过10^9天，每一天都可以减1，那么最终桌面上肯定有n-1个数字（除非桌面上一开始就一个数字1）。

代码

直接返回 n == 1 ? 1 : n - 1 即可。

目标

给定一个整数数组 nums，处理以下类型的多个查询:

计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的 和 ，其中 left <= right

实现 NumArray 类：

• NumArray(int[] nums) 使用数组 nums 初始化对象
• int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的 总和 ，包含 left 和 right 两点（也就是 nums[left] + nums[left + 1] + ... + nums[right] )

示例 1：

输入：
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
输出：
[null, 1, -1, -3]

解释：
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1)) 
numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))

说明：

• 1 <= nums.length <= 10^4
• -10^5 <= nums[i] <= 10^5
• 0 <= i <= j < nums.length
• 最多调用 104 次 sumRange 方法

思路

这个题看到之后没多想，提交之后发现和别人的性能差了10倍。这里的技巧就是提前将和计算的结果保存起来，用的时候直接用 prefix[right+1] - prefix[left] 即可。因为数组不可变所以这样是可行的。

这里没有使用 prefix[right] - prefix[left-1] 因为可以省去left为0的判断，不过多占用了4字节。其实没有必要纠结这些，真要计较的话，当left为0时还少了两次减法呢，并且cpu指令执行也有分支预测，无需关注这些细节。

代码

/**
 * @date 2024-03-18 8:36
 */
public class NumArray {

    private final int[] prefixSum;

    public NumArray(int[] nums) {
        prefixSum = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }
    }

    public int sumRange(int left, int right) {
        return prefixSum[right + 1] - prefixSum[left];
    }

    public static void main(String[] args) {
        NumArray main = new NumArray(new int[]{-2, 0, 3, -5, 2, -1});
        System.out.println(main.sumRange(0, 2));
        System.out.println(main.sumRange(2, 5));
        System.out.println(main.sumRange(0, 5));
    }
}

性能

目标

给你一个字符串 title ，它由单个空格连接一个或多个单词组成，每个单词都只包含英文字母。请你按以下规则将每个单词的首字母 大写 ：

• 如果单词的长度为 1 或者 2 ，所有字母变成小写。
• 否则，将单词首字母大写，剩余字母变成小写。

请你返回 大写后 的 title 。

示例 1：

输入：title = "capiTalIze tHe titLe"
输出："Capitalize The Title"
解释：
由于所有单词的长度都至少为 3 ，将每个单词首字母大写，剩余字母变为小写。

示例 2：

输入：title = "First leTTeR of EACH Word"
输出："First Letter of Each Word"
解释：
单词 "of" 长度为 2 ，所以它保持完全小写。
其他单词长度都至少为 3 ，所以其他单词首字母大写，剩余字母小写。

示例 3：

输入：title = "i lOve leetcode"
输出："i Love Leetcode"
解释：
单词 "i" 长度为 1 ，所以它保留小写。
其他单词长度都至少为 3 ，所以其他单词首字母大写，剩余字母小写。

说明：

• 1 <= title.length <= 100
• title 由单个空格隔开的单词组成，且不含有任何前导或后缀空格。
• 每个单词由大写和小写英文字母组成，且都是 非空 的。

思路

这个要看清题目，单词的长度为 1 或者 2 ，所有字母变成小写。并不是指传入的title长度，而是title中的单词。此外要熟悉字符对应的ASCII码：

Character	ASCII
A-Z	65-90
a-z	97-122
空格	32

读取字符数组中的字符，记录第一个字符的index，跳过，将后续的字符均转为小写，直到遇到空格，记录单词字符个数。如果字符个数大于2，将first对应的字符转为大写，否则转为小写。

代码

/**
 * @date 2024-03-11 0:16
 */
public class CapitalizeTitle {

    public String capitalizeTitle(String title) {
        // 使用System.arraycopy复制的数组，可以直接操作
        char[] chars = title.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            char first = (char) i++;
            int counter = 1;
            while (i < chars.length && chars[i] != 32) {
                if (chars[i] < 97) {
                    chars[i] = (char) (chars[i] + 32);
                }
                i++;
                counter++;
            }
            if (counter > 2) {
                if (chars[first] >= 97) {
                    chars[first] = (char) (chars[first] - 32);
                }
            } else {
                if (chars[first] < 97) {
                    chars[first] = (char) (chars[first] + 32);
                }
            }
        }
        return new String(chars);
    }
}

性能