标签： easy

目标

给你一个下标从 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表开销。

目标

给你一个下标从 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];
    }
}

性能