LeetCodeDay1

初见LeetCode，题目整理

由于之前鸽了，本次整理包括的内容题目较多，虽然普遍不算难

内含：1480、383、412、876、1342、1672、1403、623、1

1480. 一维数组的动态和

当时我的第一想法是再新建一个大小相同的数组，然后数组的每一项等于其上一项加上原数组的该项，后来发现标准答案里演示的，可以直接操作原数组，原项等于该项加前一项（首项除外），倒是相当精妙。题目过简单，不多赘述。操作原数组的思想可以参考。

383. 赎金信

自己的解法是先设一个函数，输入字符串与字母，返回字母在字符串中出现的次数（此处用到了个新函数叫str.char(i)，算是个新知识),然后遍历原字符串1，判断每个字母在字符串1中出现的次数是否会大于字符串2。但是这样的方法复杂度为n+m，题解里的操作类似，但是新建了个数组存储每种字母的出现次数。遍历字符串1，加上出现次数，遍历字符串2，减去出现次数，出现正数时结束。这样的复杂度是n+m，也是比较巧妙的方法。官方解法代码如下：

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        if (ransomNote.length() > magazine.length()) {
            return false;
        }
        int[] cnt = new int[26];
        for (char c : magazine.toCharArray()) {
            cnt[c - 'a']++;
        }
        for (char c : ransomNote.toCharArray()) {
            cnt[c - 'a']--;
            if(cnt[c - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
}

主要还是学习这种能降低复杂度的思想吧，题目过简单，不多赘述。

412. Fizz Buzz

这题就是简单的if判断处理一下。只是新增了个知识就是if判断对运行时间的影响不大，放心用就好。

876. 链表的中间节点

简单的题目，就是得回顾一下链表类的基本操作。自己的解法是遍历记下总节点数后一路next到一半节点数的位置。官方的解法还有一种叫做快慢指针的操作，原理就是设置两个指针，一个一次next一节，一个一次next两节，第一个到结尾时第二个就在中点，还是颇为有趣的。快慢指针代码如下：

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

1342. 将数字变成 0 的操作次数

没什么难度，把处理操作封装一下，然后在主函数统计操作次数就好，但是官方答案好像颇为看不懂，代码如下:

class Solution {
    public int numberOfSteps(int num) {
        int ret = 0;
        while (num > 0) {
            ret += (num > 1 ? 1 : 0) + (num & 0x01);//前半是是否除2，后半是是否减1
            num >>= 1;
        }
        return ret;
    }
}。

其中num & 0x01 是求num的二进制的最后一位，即num为奇数时为1，偶数时为0。

num >>= 1是把num二进制右移一位，即除2后向下取整。

这两个操作可以让代码更优雅且效率更快（？ 以后可以学着用一用。

1672. 最富有客户的资产总量

这题也简单，自己的解法是遍历每个用户，再遍历每人的资产求和。官方答案复杂度也一样，就是有个操作是Arrays.stream(account).sum()可以用于求和，虽然不能降低复杂度，但可以让代码优雅一点。

1403. 非递增顺序的最小子序列

这题看着很长，但实际上很简单，就是排序后由大到小求和直到大于二分之一的总和。和官方解法的区别就是它用了更简便的int total = Arrays.stream(nums).sum();和Arrays.sort(nums);来实现求和以及排序。以后也可以学着用一用。

623. 在二叉树中增加一行

终于第一次碰到中等难度的题目了啊…带来的压迫感果然也是简单难度所不能比拟的。最后也是参考了一下题解才通过的。粗略的解法说明就是，对原树执行深度为d的增行操作，等同于对其root的左右分支执行深度为d-1的增行操作，同理递归。只要再加上输入root为0的特判、depth为1的特判和depth为1的最终处理（在左右分支前新增一项并接上root）即可。代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode addOneRow(TreeNode root, int val, int depth) {
        if(root == null){
            return null;
        }
        if(depth == 1){
            TreeNode t = new TreeNode(val, root, null);
            return t;
        }else if(depth == 2){
            root.left = new TreeNode(val, root.left, null);
            root.right = new TreeNode(val, null, root.right);
        }else{
            addOneRow(root.left, val, depth-1);
            addOneRow(root.right, val, depth-1);
        }
        return root;
    }
}

1. 两数之和

这题不愧是第一题，确实从逻辑上毫无难度。自己的解法就是用for循环遍历一遍所有的组合。但是这样做复杂度比较高。官方给出的解法是使用哈希表，代码如下：

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];
    }
}

感觉从原理上就是用哈希表自带的内部查询取代了一层for循环（？不知道这个containsKey是怎么做到降低复杂度的，但以后也可以试试。

总而言之，以上9题就是初次接触leetcode的整理与反思。

其中有7题是新手村的题目，所以普遍难度不高，算是新人福利吧。

以后尽可能做到当天做题当天整理。

2022-8-5 23:12

---