前言 📢

本日记为个人的刷题学习日记，内容非原创，仅为自己复习知识时，能够看得懂自己写的CV的代码，快速理解题意。另外，👍力扣官方的题解很好用，三叶姐🍭nb！！！！！


448 找到数组中消失的数字📝

题意

  • 给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。
  • 输入: nums = [4, 3, 2, 7, 8, 2, 3, 1] 输出: [5, 6]

思路

  • 暴力统计已有的数字，再遍历数组，输出未统计的数字
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        int len = nums.length;
        // 数组中 每个数字的值 作为已出现数字的索引 无论出现多少次 均记为1
        int[] newNums = new int[len+1];
        for(int i=0; i<len; i++) {
            newNums[nums[i]] = 1;
        }
		// 新建列表 遍历用于统计的数组 输出出现次数为0的索引值
        List<Integer> list = new ArrayList<>();
        for(int i=1; i<len+1; i++) {
            if(newNums[i] == 0) {
                list.add(i);
            }
        }
        return list;
    }
}

time

  • 排序、验证递增关系。若数字均出现，则为单调递增的序列，即[1, 2, 3, ,4, 5, …]
  • 只遍历了一遍数组，也没有新建任何其他项，只要要求返回的list
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
class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        Arrays.sort(nums);
        int len = nums.length;
		// 首、尾、中间段 均要考虑 就是时间变得好长
        List<Integer> list = new ArrayList<>();
        int start = 1, end = len;
        // [4, 4, 4, 4]
        if(nums[0] != 1) {
            while(start < nums[0]) {
                list.add(start);
                start++;
            }
        }
        // [1, 1, 1, 1]
        if(nums[len - 1] < len) {
            while(nums[len-1] < end) {
                list.add(end);
                end--;
            }
        }

        // [1, 2, 2, 2, 4, 6]
        for(int i=1; i<len; i++) {
            if(nums[i] == nums[i-1] || nums[i] == nums[i-1] + 1) {
                continue;
            } else {
                while(nums[i-1] + 1 < nums[i]) {
                    list.add(nums[i-1] + 1);
                    nums[i-1]++;
                }
            }
        }
        return list;
    }
}

space

179 最大数📝

题意

  • 给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
  • 输出结果可能非常大，所以你需要返回一个字符串而不是整数。 return String

思路

  • 贪心、字符串拼接
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 String largestNumber(int[] nums) {
        int len = nums.length;
        String[] str = new String[len];
        // 转换为字符串数组
        for(int i=0; i<len; i++) {
            str[i] = "" + nums[i];
        }
        // 比较两个字符串拼接后的大小排序 a + b和 b + a
        Arrays.sort(str, (a, b) -> {
            String sa = a + b, sb = b + a;
            return sb.compareTo(sa);
        });
        // StringBUilder拼接 会更快
        StringBuilder sb = new StringBuilder();
        for(String aStr : str) {
            sb.append(aStr);
        }
        int len2 = sb.length();
        int k = 0;
        // 注意 避免 零开头项
        while(k < len - 1 && sb.charAt(k) == '0') k++;
        return sb.substring(k);
    }
}