标签： easy

目标

给你一个长度为 n 、下标从 0 开始的整数数组 batteryPercentages ，表示 n 个设备的电池百分比。

你的任务是按照顺序测试每个设备 i，执行以下测试操作：

• 如果 batteryPercentages[i] 大于 0：
  • 增加 已测试设备的计数。
  • 将下标在 [i + 1, n - 1] 的所有设备的电池百分比减少 1，确保它们的电池百分比 不会低于 0 ，即 batteryPercentages[j] = max(0, batteryPercentages[j] - 1)。
  • 移动到下一个设备。
• 否则，移动到下一个设备而不执行任何测试。

返回一个整数，表示按顺序执行测试操作后 已测试设备 的数量。

示例 1：

输入：batteryPercentages = [1,1,2,1,3]
输出：3
解释：按顺序从设备 0 开始执行测试操作：
在设备 0 上，batteryPercentages[0] > 0 ，现在有 1 个已测试设备，batteryPercentages 变为 [1,0,1,0,2] 。
在设备 1 上，batteryPercentages[1] == 0 ，移动到下一个设备而不进行测试。
在设备 2 上，batteryPercentages[2] > 0 ，现在有 2 个已测试设备，batteryPercentages 变为 [1,0,1,0,1] 。
在设备 3 上，batteryPercentages[3] == 0 ，移动到下一个设备而不进行测试。
在设备 4 上，batteryPercentages[4] > 0 ，现在有 3 个已测试设备，batteryPercentages 保持不变。
因此，答案是 3 。

示例 2：

输入：batteryPercentages = [0,1,2]
输出：2
解释：按顺序从设备 0 开始执行测试操作：
在设备 0 上，batteryPercentages[0] == 0 ，移动到下一个设备而不进行测试。
在设备 1 上，batteryPercentages[1] > 0 ，现在有 1 个已测试设备，batteryPercentages 变为 [0,1,1] 。
在设备 2 上，batteryPercentages[2] > 0 ，现在有 2 个已测试设备，batteryPercentages 保持不变。
因此，答案是 2 。

说明：

• 1 <= n == batteryPercentages.length <= 100
• 0 <= batteryPercentages[i] <= 100

思路

如果设备的剩余电量大于0，已测试设备加1且后续设备的所有电量减1。

简而言之，后续设备需要减去的电量为已检测的设备数。

题解上说这是差分的思想。我们没必要检测一个设备就向后循环并将电量减1，当前设备需要减去的电量等于上一个设备需要减去的电量+1。

代码

/**
 * @date 2024-05-10 8:43
 */
public class CountTestedDevices2960 {
    public int countTestedDevices(int[] batteryPercentages) {
        int res = 0;
        for (int i = 0; i < batteryPercentages.length; i++) {
            if (batteryPercentages[i] > res) {
                res++;
            }
        }
        return res;
    }
}

性能

目标

给你一个下标从 0 开始的 m * n 整数矩阵 grid 。矩阵中某一列的宽度是这一列数字的最大 字符串长度 。

• 比方说，如果 grid = [[-10], [3], [12]] ，那么唯一一列的宽度是 3 ，因为 -10 的字符串长度为 3 。

请你返回一个大小为 n 的整数数组 ans ，其中 ans[i] 是第 i 列的宽度。

一个有 len 个数位的整数 x ，如果是非负数，那么 字符串长度 为 len ，否则为 len + 1 。

示例 1：

输入：grid = [[1],[22],[333]]
输出：[3]
解释：第 0 列中，333 字符串长度为 3 。

示例 2：

输入：grid = [[-15,1,3],[15,7,12],[5,6,-2]]
输出：[3,1,2]
解释：
第 0 列中，只有 -15 字符串长度为 3 。
第 1 列中，所有整数的字符串长度都是 1 。
第 2 列中，12 和 -2 的字符串长度都为 2 。

说明：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 100
• -10^9 <= grid[r][c] <= 10^9

思路

这个题核心就是如何计算数字的长度。我们可以枚举 9, 99, 999, 9999, 99999, 999999, 9999999, 99999999, 999999999, Integer.MAX_VALUE，分别与这些值比较，Integer.stringSize就是如此实现的。对于负数需要将长度加1 int size = (i < 0) ? stringSize(-i) + 1 : stringSize(i);。

也可以循环除以10直到0来计算长度。一个优化的点是不必求每一个数的长度，只需要求出最大值 max 与 最小值 min的长度即可。网友还提供了一个小技巧可以减少对较小值的长度计算。选取 max/10 和 -min 中的较大值来计算长度 l，取 l+1。解释如下：如果 min > 0 那么 -min < 0，我们取到 max/10 的长度，所以长度为 l+1。如果 min < 0，并且 -min > max/10，我们取到 -min，长度需要加上负号，即 l+1。这里需要解释一下 -min < max && -min > max/10 的情况，这时 max 的长度与 -min 的长度加1 是相同的。而如果 min < 0，且 -min < max/10，取 max/10 长度减小了1，所以取 l+1。

代码

/**
 * @date 2024-04-27 18:39
 */
public class FindColumnWidth2639 {

    int[] sizeTable = {9, 99, 999, 9999, 99999, 999999, 9999999,
            99999999, 999999999, Integer.MAX_VALUE};

    int stringSize(int x) {
        int j;
        if (x < 0) {
            x = -x;
            j = 2;
        } else {
            j = 1;
        }
        for (int i = 0; ; i++) {
            if (x <= sizeTable[i]) {
                return i + j;
            }
        }
    }

    public int[] findColumnWidth(int[][] grid) {
        int n = grid[0].length;
        int[] res = new int[n];
        int[] negative = new int[n];
        for (int[] ints : grid) {
            for (int i = 0; i < n; i++) {
                if (ints[i] < negative[i]) {
                    negative[i] = ints[i];
                } else if (ints[i] > res[i]) {
                    res[i] = ints[i];
                }
            }
        }
        for (int i = 0; i < n; i++) {
            res[i] = Math.max(stringSize(res[i]), stringSize(negative[i]));
        }
        return res;
    }

}

性能

目标

给你两棵二叉树，原始树 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表开销。