力扣刷题记录（Java）（六）

跳跃游戏||

个人版本一

class Solution {
// 思路是在i后nums[i]范围内寻找跨度最大的点，然后一路到最后
    public static int jump(int[] nums) {
        if(nums.length == 1||nums.length == 2){
            return nums.length-1;
        }
        // count用来记录跳跃的步数
        int count = 1, i = 0, j, max, index = -1, len = nums.length;
        // 开始就可以直接跳到最后
        if(nums[0] >= len-1){
            return count;
        }
        while (i<len){
            max = -1;
            for(j=i+1; j<=i+nums[i]&&j<len; j++){
                if (nums[j] >= (len - 1 - j)) {
                    // 通过设置index=len，可以在离开循环后直接跳出while循环
                    index = len;
                    break;
                }
                // 记录范围内最大跨度的点
                if(nums[j]+j>=max){
                    max = nums[j]+j;
                    index = j;
                }
            }
            i = index;
            count++;
        }
        return count;
    }
}
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
31
32

官方版本一（反向查找）

class Solution {
    public int jump(int[] nums) {
        int position = nums.length - 1;
        int steps = 0;
        while (position > 0) {
            for (int i = 0; i < position; i++) {
                if (i + nums[i] >= position) {
                    position = i;
                    steps++;
                    break;
                }
            }
        }
        return steps;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

官方版本二（正向查找）

// 思想与个人版本一相同
class Solution {
    public int jump(int[] nums) {
        int length = nums.length;
        int end = 0;
        int maxPosition = 0; 
        int steps = 0;
        for (int i = 0; i < length - 1; i++) {
            maxPosition = Math.max(maxPosition, i + nums[i]); 
            if (i == end) {
                end = maxPosition;
                steps++;
            }
        }
        return steps;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

缺失的第一个整数

题目链接：缺失的正整数

个人版本一

class Solution {
    // 缺失的第一个整数，例如[1,2,4,5]，缺少了个3，那么答案就是3
    // 例如[2,3,4]，缺失的就是1，也就是说在数组中，如果正整数部分都比1大，那么缺失的就是1
    // 例如[1,2,3]，这个时候缺失的就是4
    // 对于[1,2,3]，缺失的是4,4是数组长度+1，这种情况数组中元素是连续的，并且是[1,len]范围内的，如[2,3,1]也是一样
    // 这种情况是[1,len]范围内，将他们的值都减1，例如[2,3,1]，减1后是[1,2,0]，减1后的数明显是nums中所有的下标
    // 也就是说，我们可以通过下标去表示这些数的存在，这里我们可以做取负处理，例如[2,3,1]，对于2表示他的存在
    // 可以将2-1=1,也就是下标1的元素取负数，得[2,-3,1]，而对于是负数的元素，我们要取绝对值，再处理对应下标的元素
    // 例如到-3,取绝对值，下标为2的取负，就得到[2,-3,-1]，整个时候在数组中只要是负数，那么对应的下标+1就是表示数i+1存在
    // 那么对于大于数组的数我们不做处理，例如[1,2,4]，处理后是[-1,-2,4]，前两个为负数，说明对应下标+1是存在的
    // 4位置为正数，那么对应下标2,2+1=3，说明答案是3，而对于数组nums是全负数的情况，那答案就是len+1
    // 这种思想是模拟哈希表，以下标为键，同时下标+1为值，这是因为完整存在数组Nums中的数必然是在[1,len]之中
    // 因为我们是通过判断最终处理后的是正数，从而得到我们想要的，但是数组中可以有负数和0并且是不符合要求的
    // 所以需要将负数和0处理成正整数，同时这个正整数不影响判断，因为在[1,len]之间的数才会被数组赋值为负数
    // 所以我们只需要处理成len+1即可
    // 同时可能存在重复的情况,例如[1,1,2]，第一个1已经处理为-1，如果第二个1同样处理，显然不符合，因为被处理成
    // 负数的元素就表示已经存在，在处理成正数就又不存在了，所以当目标位置的数是负数的时候选择跳过
    public static int firstMissingPositive(int[] nums) {
        int len = nums.length, i, index;
        // 将负数都处理成0
        for(i=0; i<len; i++){
            if(nums[i]<=0){
                nums[i] = len+1;
            }
        }
        for(i=0; i<len; i++){
            index = Math.abs(nums[i])-1;
            if(index < len && index >= 0 && nums[index]>0){
                nums[index] = -nums[index];
            }
        }
        for(i=0; i<len; i++){
            if(nums[i] > 0){
                break;
            }
        }
        return i+1;
    }
}
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
31
32
33
34
35
36
37
38
39

官方版本一（置换）

// 方法类似个人版本一，但是不是进行打标记，而是直接交换两个数，例如[2,1]
// 2-1=1，得到其下标1，下标1在[2,1]中，那么该位置的数就与下标1的元素进行交换，、
// 因为这样交换有可能是nums[i]=i+1，例如[1,2,3]，如果不加判断，那么就会陷入死循环所以需要加上
// nums[nums[i] - 1] != nums[i]
class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
           // 通过while循环，处理被交换而来的数是否在[1,len]范围内，因为下标是一直往后的，而交换回来的数
           // 如果在[1,len]范围内，那么就会被忽略而导致错误
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }
}


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

全排列

题目链接：全排列

个人版本一（回溯）

class Solution {
    // 使用回溯的思想，并通过布尔型数组记录数据添加情况，从而得到全排列
    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        boolean[] used = new boolean[nums.length];
        Stack<Integer> stack = new Stack<>();
        getPermute(nums, used, stack);
        return list;
    }
    public void getPermute(int[] nums, boolean[] used, Stack<Integer> stack){
        if(stack.size() == nums.length){
            list.add(new ArrayList<>(stack));
            return;
        }
        for(int i=0; i< nums.length; i++){
            // 没被添加的元素才能被操作
            if(used[i]) continue;
            used[i] = true;
            stack.push(nums[i]);
            getPermute(nums, used, stack);
            // 数已经使用完毕了，设置为初始状态，留给下次用
            used[i] = false;
            stack.pop();
        }
    }
}
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

官方版本一（回溯）

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();

        List<Integer> output = new ArrayList<Integer>();
        for (int num : nums) {
            output.add(num);
        }

        int n = nums.length;
        backtrack(n, output, res, 0);
        return res;
    }

    public void backtrack(int n, List<Integer> output, List<List<Integer>> res, int first) {
        // 所有数都填完了
        if (first == n) {
            res.add(new ArrayList<Integer>(output));
        }
        for (int i = first; i < n; i++) {
            // 动态维护数组
            Collections.swap(output, first, i);
            // 继续递归填下一个数
            backtrack(n, output, res, first + 1);
            // 撤销操作，最终返回到first=0时，是原来的顺序
            Collections.swap(output, first, i);
        }
    }
}

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

全排列二

个人版本一（HashSet处理）

class Solution {
    public static List<List<Integer>> permuteUnique(int[] nums) {
        HashSet<List<Integer>> set = new HashSet<>();
        List<Integer> output = new ArrayList<Integer>();
        for (int num : nums) {
            output.add(num);
        }

        int n = nums.length;
        backtrack(n, output,set, 0);
        return new ArrayList<>(set);
    }

    public static void backtrack(int n, List<Integer> output,HashSet<List<Integer>> set, int first) {
        // 所有数都填完了
        if (first == n) {
            set.add(new ArrayList<Integer>(output));
        }
        for (int i = first; i < n; i++) {
            if(first != i && output.get(first) == output.get(i)) continue;
            // 动态维护数组
            Collections.swap(output, first, i);
            // 继续递归填下一个数
            backtrack(n, output, set, first + 1);
            // 撤销操作
            Collections.swap(output, first, i);
        }
    }
}
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

个人版本二

class Solution {
    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        boolean[] used = new boolean[nums.length];
        Stack<Integer> stack = new Stack<>();
        Arrays.sort(nums);
        getPermute(nums, used, stack);
        return list;
    }
    public void getPermute(int[] nums, boolean[] used, Stack<Integer> stack){
        if(stack.size() == nums.length){
            list.add(new ArrayList<>(stack));
            return;
        }
        for(int i=0; i< nums.length; i++){
            // nums[i] == nums[i - 1]是针对与前一个元素相等的，因为通过used列表进行操作，深度遍历回退
        	// 会回到上一个符合条件的元素，如果当前元素跟上一个元素是一样的，那么就可能是造成重复的，
        	// 例如1,1,2，当深度遍历组成树状结构时，第一个层是第一个1，当产生一系列数以后回溯到第一层变成了
        	// 第二个1，那么就会重复产生第一层是第一个1的结果，所以就产生了重复，因而有nums[i] == nums[i - 1]
        	// 但是并不是每个nums[i] == nums[i - 1]都是产生重复的条件，例如产生1,1,2，当第二层是第二个1的时候
        	// 是符合条件的，所以根本产生问题的是从上次深度遍历不断回退导致的重复，例如深度遍历产生了1,1,2、1,2,1以后，回退到第0层，也就是根节点，下一次就是深度遍历到第二个1，也就第1层变成了第二个1，这样跟开始第一层是
        	// 第一个一的结果是一样的，所以排除重复还需要used[i - 1] == false，也就是从上次结果回退产生的
        	// 就会产生重复，而保证了例如1,1,2这样的组合的生成
            if(used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) continue;
            used[i] = true;
            stack.push(nums[i]);
            getPermute(nums, used, stack);
            // 数已经使用完毕了，设置为初始状态，留给下次用
            used[i] = false;
            stack.pop();
        }
    }
}
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
31
32
33

旋转图像

题目链接：旋转图像

个人版本一

class Solution {
    public static void rotate(int[][] matrix) {
        int n = matrix.length;
        int[][] m = new int[n][n];
        for(int i=0; i<n; i++){
            for (int j=0; j<n; j++){
                m[i][j] = matrix[i][j];
            }
        }
        rotateThem(matrix, m);
    }
    public static void rotateThem(int[][] matrix, int[][] m){
        // 规律是，例如4*4的图像，对于位置1,2的数，他会变换到2,2位置，2,3位置的由来：行位置2是1,2中的列2
        // 列位置的2是1,2中3-1=2，也就是n-1-2
        int n = matrix.length;
        int k = n-1;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                matrix[j][k-i] = m[i][j];
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

官方版本一（原地旋转）（优化个人版本一）

// 个人版本一需要额外的空间，而这里就是优化具体的空间
class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        // 原地旋转操作的范围并不需要全部操作，n等于偶数以及奇数的范围如下单色块
        // 例如n是4，那么他的操作空间就是左上角的四个，如下蓝色部分
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < (n + 1) / 2; ++j) {
                // 个人版本一种关键是：matrix[j][k-i] = m[i][j]，表示m[i][j]的元素
                // 旋转后会来到：matrix[j][k-i]，m是原来的矩阵，因为上述的句子
                // 会覆盖matrix[j][k-i]的元素，导致拿不到原来的元素，所以需要复制
                // 但是我们可以通过保存matrix[j][k-i]位置的元素然后再进行计算matrix[j][k-i]位置的元素
                // 又移动到哪，然后又保存新位置的数并将上一次保存的数跳入
                // 推到发现经过四轮的覆盖，从matrix[i][j]开始操作，最终还是会回到
                // matrix[i][j]，也就是会产生一个循环，所以有以下的四个复制操作以及一个保存操作
                // 下边matrix赋值操作从下往上就是推到的过程，代码执行是倒序，因为这样就可以获得前一个元素的值，而我们只需要保存 matrix[i][j]即可
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - j - 1][i];
                matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
                matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
                matrix[j][n - i - 1] = temp;
            }
        }
    }
}
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 void rotate(int[][] matrix) {
        int n = matrix.length;
        // 水平翻转
        // 按水平轴翻转，只需要处理上半部分
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < n; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - i - 1][j];
                matrix[n - i - 1][j] = temp;
            }
        }
        // 主对角线翻转
        // 按主对角线翻转只需要处理对角线的一边，这里处理左下半部分
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
    }
}

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 static List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> list = new ArrayList<>();
        Map<String, List<String>> map = new HashMap<>();
        for(int i=0; i<strs.length; i++){
            char[] cArr = strs[i].toCharArray();
            Arrays.sort(cArr);
            String key = new String(cArr);
            List<String> l = map.get(key);
            if(l == null){
                List<String> tempList= new ArrayList<>();
                tempList.add(strs[i]);
                list.add(tempList);
                map.put(key, tempList);
            }else{
                l.add(strs[i]);
            }
        }
        return list;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

官方版本一（计数）

// 利用异位词每个字母出现的次数相等，用字母和次数组成哈希表的键从而判断是否异位词
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String str : strs) {
            int[] counts = new int[26];
            int length = str.length();
            for (int i = 0; i < length; i++) {
                counts[str.charAt(i) - 'a']++;
            }
            // 将每个出现次数大于 0 的字母和出现次数按顺序拼接成字符串，作为哈希表的键
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < 26; i++) {
                if (counts[i] != 0) {
                    sb.append((char) ('a' + i));
                    sb.append(counts[i]);
                }
            }
            String key = sb.toString();
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values());
    }
}


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

个人版本一

class Solution {
    public double myPow(double x, int n) {
        if(n == 0 || x == 1) return 1;
        if(n == 1) return x;
        long p = 1;
        double result = x;
        boolean d = false;
        long pp = n, sumP;
        int i;
        if(pp < 0){
            pp = -pp;
            d = true;
        }
        List<Long> pow = new ArrayList<>();
        List<Double> value = new ArrayList<>();
        pow.add(p);value.add(result);
        i = Integer.MAX_VALUE/2;
        while (p < i && (p+p) <= pp){
            sumP = p+p;
            pow.add(sumP);
            p = sumP;
            result = result*result;
            value.add(result);
        }
        int pSize = pow.size();
        sumP =  pp - pow.get(pSize-1);
        while (sumP > 0){
            i = 0;
            while (i < pSize-1 && pow.get(i+1) <= sumP){
                i++;
            }
            result = result*value.get(i);
            sumP = sumP-pow.get(i);
        }
        return d? 1/result:result;
    }
}
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
31
32
33
34
35
36
37

官方版本一（快速幂+递归）

class Solution {
    public double myPow(double x, int n) {
        long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }

    public double quickMul(double x, long N) {
        if (N == 0) {
            return 1.0;
        }
        double y = quickMul(x, N / 2);
        return N % 2 == 0 ? y * y : y * y * x;
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

官方版本二（快速幂+迭代）

class Solution {
    public double myPow(double x, int n) {
        long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }

    public double quickMul(double x, long N) {
        double ans = 1.0;
        // 贡献的初始值为 x
        double x_contribute = x;
        // 在对 N 进行二进制拆分的同时计算答案
        while (N > 0) {
            if (N % 2 == 1) {
                // 如果 N 二进制表示的最低位为 1，那么需要计入贡献
                ans *= x_contribute;
            }
            // 将贡献不断地平方
            x_contribute *= x_contribute;
            // 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
            N /= 2;
        }
        return ans;
    }
}

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

详细解析：详细解析