LeetCode刷题记录02——新手村专辑(一)

题目

1480一维数组的动态和

1480一维数组的动态和

给你一个数组 nums 。数组「动态和」的计算公式为：runningSum[i] = sum(nums[0]…nums[i]) 。
请返回 nums 的动态和。

示例1：
输入：nums = [1,2,3,4]
输出：[1,3,6,10]
解释：动态和计算过程为 [1, 1+2, 1+2+3, 1+2+3+4] 。

示例 2：
输入：nums = [1,1,1,1,1]
输出：[1,2,3,4,5]
解释：动态和计算过程为 [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1] 。

示例 3：
输入：nums = [3,1,2,10,1]
输出：[3,4,6,16,17]

我的思路

根据给出的数组动态和计算公式以及示例的解释，可以知道：第 i 个数值是前面数据的累积和，刚好前一项已经保存了该项前面所有的数据和。

有点绕，像废话文学，直接上代码看吧

我的代码

class Solution {
    public int[] runningSum(int[] nums) {
    	//定义一个数组来储存动态和的结果
        int[] sums = new int[nums.length];
        //定义一个变量计算累加和
        int sum = 0;
        //遍历目标数组
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            //将前面i项的累加和赋值给动态和数组
            sums[i]=sum;
        }
        //返回动态和数组
        return sums;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

提交结果

从提交结果就可以看出这样子的想法消耗内存过大，还另外开了一个数组来储存数据，于是就可以想到利用本地目标数组直接计算，代码就可以更新为如下形式：

代码优化

class Solution {
    public int[] runningSum(int[] nums) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            //累加完直接赋值给当前下标的数组元素
            nums[i]=sum;
        }
        return nums;
    }
}
1
2
3
4
5
6
7
8
9
10
11

这样就可以省掉一个O(n)的内存消耗啦，也可以直接省掉变量的定义，直接用动态规划，注意：此时遍历是从数组下标1开始的。

class Solution {
    public int[] runningSum(int[] nums) {
    	//数组从下标1开始遍历，第一项就是其本身，从第二项开始，每一项更新为  当前值与上一项的值  的和
        for (int i = 1; i < nums.length; i++) {
            nums[i] += nums[i-1];
        }
        return nums;
    }
}
1
2
3
4
5
6
7
8
9

但这个内存消耗要比上一个优化代码要大一点，应该是因为每一次求和都访问了两次数组中的值。

总结

可能一开始并不会想到最优解，但可以试着进一步优化，通过力扣平台所反馈的执行时间与内存消耗的参考值来评判算法的优劣。而这个优劣并不是永恒的，而是相对不同问题有不同的用处。比如说在实际中，可能需要消耗空间换时间，同理，也可能需要用时间来换空间。

383赎金信

383赎金信

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。

示例 1：
输入：ransomNote = “a”, magazine = “b”
输出：false

示例 2：
输入：ransomNote = “aa”, magazine = “ab”
输出：false

示例 3：
输入：ransomNote = “aa”, magazine = “aab”
输出：true

我的思路

关键：根据题意，ransomNote由magazine的字符构成，且只能使用一次，因此就可以转换为求两个字符的字符数目比较了。显然，ransomNote的字符串长度不能大于magazine的字符串长度，即ransonNote.length()>magazine/length()时可以直接跳过比较返回false。

想是想到了要比较俩字符串各字符的数目，可不知道怎么着手写代码。我起先想到用Map类型来存储字符及其对应个数，但是很麻烦，存在字母差异（即只有其中一个字符串包含该字母）的时候要怎么比较。
我百度了一下“统计字符串各字母数目”，看到代码中的26和'a'，我就想明白了。

结论：直接定义一个int类型的数组int[] chars = new int[26]来存储各个字母出现的次数，存储的位置由遍历的字母-‘a’(s.charAt(i)-'a')来决定（char类型可以用int类型的ASCII码来表示），提示已经说明都是小写英文字母，所以不必考虑大小写问题。因此计算出两个字符串的各字母数量返回的数组后，就可以进行比较了，只要ransomNote中对应的字母数量大于magazine中的，就返回false。

我的代码

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
    	//被组成的数组长度都大于源数组长度，还比什么，可以直接跳了
        if(ransomNote.length()>magazine.length()){
            return false;
        }
        //计算ransomNote的字符数量数组
        int countR[] = count(ransomNote);
        //计算magazine的字符数量数组
        int countM[] = count(magazine);
        boolean flag =true;
        for (int i =0;i< 26;i++) {
        	//只要ransomNote中的字符数量大于magazine的,就已经无法由后者组成了,所以可以停止循环返回false
            if (countR[i]>countM[i]){
                flag =false;
                break;
            }
        }
        return flag;
    }
    //自定义的计算字符数目的方法，返回值int[]
    public static int[] count(String s){
        int[] chars = new int[26];
        for (int i = 0; i < s.length(); i++) {
        	//例如字母a，存储在char[0]中，b--->char[1],c--->char[2]...
            chars[s.charAt(i)-'a']++;
        }
        return chars;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

提交结果

根据代码与提交结果来看，内存消耗很大，可以考虑对代码进一步优化。

代码优化

可以试着只用一个int[]数组来存储字母数量，比如说统计ransomNote中的字母数量时++，而统计magazine时数量--，最后循环遍历int[]数组，只要有一个值>0(即说明magazine中的字符数目不够组成ransomNote)，就可以返回false

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        if(ransomNote.length()>magazine.length()){
            return false;
        }
        boolean flag =true;
        //只定义了一个int类型的数组
        int[] chars = new int[26];
        //分别对两个字符串循环遍历
        for (int i = 0; i < ransomNote.length(); i++) {
            chars[ransomNote.charAt(i)-'a']++;
        }
        for (int i = 0; i < magazine.length(); i++) {
            chars[magazine.charAt(i)-'a']--;
        }
        for (int i =0;i< 26;i++) {
        	//char[i]>0表示ransomNote的某个字母数大于magazine
            if (chars[i]>0){
                flag =false;
                break;
            }
        }
        return flag;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

虽然遍历了三次，但是要比数组操作少一些内存消耗。
当然还可以反过来想，就可以再少一次循环遍历。

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        if(ransomNote.length()>magazine.length()){
            return false;
        }
        int[] chars = new int[26];
        //先计算准备赎金中的字符数量
        for (int i = 0; i < magazine.length(); i++) {
            chars[magazine.charAt(i)-'a']++;
        }
        for (int i = 0; i < ransomNote.length(); i++) {
        	//扣除花掉的赎金字符数量
            chars[ransomNote.charAt(i)-'a']--;
            //小于0则说明magazine中的赎金(字符)不够
            if(chars[ransomNote.charAt(i)-'a']<0){
                return false;
            }
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

不过内存消耗好像还是蛮大，应该也是访问数组的锅。

总结

这个题的关键在于只使用一次和比较字符数目的转换，而我最大的收获是：通过char类型与int类型之间的联系，就可以很轻松的用数组下标来代表字母，而数组元素的值可以用来存储字母出现的次数。这种思维还需要更多实践来形成自己的DNA记忆。