前言

寒假刚刚过去，暑假正式开始！

开始刷 LeetCode 的第一天，计划每天两小时，从简单题开始，到刷完为止（刷不完就一直刷~~~）

1. 一维数组的动态和

2. 拥有最多糖果的孩子

3. 重新排列数组

image-20200621151446703
我的思路：
  1. 引入一个空数组用于存放结果，使用两个指针分别指向原数组和新数组
  2. 指向原数组的指针每次加2，指向新数组的指针每次加1
我的代码：
1
2
3
4
5
6
7
8
9
10
class Solution {
    public int[] shuffle(int[] nums, int n) {
        int[] res = new int[nums.length];
        for(int i = 0, j = 0; j < n; i = i + 2, j++){
            res[i] = nums[j];
            res[i + 1] = nums[j + n];
        }
        return res;
    }
}
执行结果：
image-20200621151957545

时间复杂度为 O(n) ，然而只击败26%，有改进空间！

更好的方法：
1
2
3
4
5
6
7
8
9
10
class Solution {
    public int[] shuffle(int[] nums, int n) {
        int[] res = new int[nums.length];
        for(int i = 0; i < n; i++){
            res[i * 2] = nums[i];
            res[i * 2 + 1] = nums[i+n];
        }
        return res;
    }
}

两个指针是二倍的关系，完全可以用一个指针代替两个指针！

4. 1比特与2比特字符

image-20200621162935088
我的思路：

  1. 设置布尔型变量 flag 来标记最后一个字符是否为一个比特，动态的进行判断

  2. 若字符数组长度为 1 则直接返回 true

  3. 否则进行判断：

    • 若上一次判断的结果是 false （两比特） ，则当前字符必定为一比特
    • 若上一次判断结果为true （一比特）：
      • 若上一个字符为 0 ，则当前字符必定为一比特
      • 若上一个字符为 1 ，则当前字符必定为两比特

  4. 返回 flag

我的代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean isOneBitCharacter(int[] bits) {
        boolean flag = true;
        if (bits.length == 1) {
            return flag;
        }
        for (int i = 1; i < bits.length; i++) {
            if (!flag) {
                flag = true;
            } else {
                if (bits[i-1] == 0) {
                    flag = true;
                } else{
                    flag = false;
                }
            }
        }
        return flag;
    }
}
执行结果：
image-20200621163608741

显然，在运行时间和内存消耗上都仍有较大改进空间！

康康大佬们是怎么做的

更好的方法：

我们可以对 bits 数组从左到右扫描来判断最后一位是否为一比特字符。当扫描到第 i 位时，如果 bits[i] = 1，那么说明这是一个两比特字符，将 i 的值增加 2。如果 bits[i] = 0，那么说明这是一个一比特字符，将 i 的值增加 1。

如果 i 最终落在了 bits.length − 1 的位置，那么说明最后一位一定是一比特字符。

作者：LeetCode
链接：https://leetcode-cn.com/problems/1-bit-and-2-bit-characters/solution/1bi-te-yu-2bi-te-zi-fu-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

1
2
3
4
5
6
7
8
9
class Solution {
    public boolean isOneBitCharacter(int[] bits) {
        int i = 0;
        while (i < bits.length - 1) {
            i += bits[i] + 1;
        }
        return i == bits.length - 1;
    }
}

妙啊！