Leetcode刷题61-70

LeetCode刷题
Word count: 4k   |   Reading time≈ 18 min

①169.多数元素

2024.1.8
题目：给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊n/2⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。

思路1：
在数组排序后，众数一定会出现在数组的中间位置

排序Arrays.sort

1
2
3
4
public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }

思路2：
哈希表:使用 HashMap 存储没个元素及其出现的次数
键 – 元素
值 – 元素出现的次数
查找值最大的键

哈希表

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 int majorityElement(int[] nums) {
        Map<Integer,Integer> counts = getCounts(nums);
        //存储最大值的键值对
        Map.Entry<Integer,Integer> major = null;
        //遍历counts找到值最大的键(打擂台的方法)
        for(Map.Entry<Integer,Integer> count:counts.entrySet()){
            if(major == null || major.getValue() < count.getValue()){
                major = count;
            }
        }
        return major.getKey();
    }
    //获取所有的映射关系
    public Map<Integer,Integer> getCounts(int[] nums){
        Map<Integer,Integer> counts = new HashMap<Integer,Integer>();
        for(int num:nums){
            if(!counts.containsKey(num)){
                //不包含该键就加入
                counts.put(num,1);
            }else{
                //包含就值加一,覆盖
                counts.put(num,counts.get(num) + 1);
            }
        }
        return counts;
    }
}

思路3：
如果我们把众数记为 +1+1+1，把其他数记为 −1-1−1，将它们全部加起来，显然和大于 0，
从结果本身我们可以看出众数比其他数多。

摩尔投票算法（Boyer-Moore Voting Algorithm）
该算法的基本思想是：遍历数组，对每个元素进行投票，当count为0时，将当前元素设置为候选元素，然后根据当前元素与候选元素是否相等来增加或减少count的值。最终获胜的候选元素即为主要元素。

最好 摩尔投票算法（Boyer-Moore Voting Algorithm

1
2
3
4
5
6
7
8
9
10
11
public int majorityElement(int[] nums) {
        int count = 0;
        int result = 0;
        for(int num : nums){
            if(count == 0){
                result = num;
            }
            count += (result == num) ? 1 : -1;
        }
        return result;
    }

②217.存在重复元素

2024.1.9
题目：给你一个整数数组 nums 。如果任一值在数组中出现至少两次 ，返回 true ；
如果数组中每个元素互不相同，返回 false 。

思路：
直接用哈希表，加不进去了就是多次出现直接 return true

1
2
3
4
5
6
7
8
9
public boolean containsDuplicate(int[] nums) {
        Set<Integer> hash = new HashSet<Integer>();
        for(int num:nums){
            if(!hash.add(num)){
                return true;
            }
        }
        return false;
    }

③219.存在重复元素Ⅱ

2024.1.10
题目：给你一个整数数组 nums 和一个整数 k ，
判断数组中是否存在两个不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。
如果存在，返回 true ；否则，返回 false 。

思路1：
当遍历到下标 i 时，如果在 i 之前存在与 num[i] 相等的元素，应该在这些元素中找下标最大的值 j ，判断 i - j ≤ k是否成立
用 HashMap 存储数组值，及该值对应的数组下标

哈希表

1
2
3
4
5
6
7
8
9
10
11
12
public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        for(int i = 0; i < nums.length; i++){
            int num = nums[i];
            if(map.containsKey(num) && i - map.get(num) <= k){
                return true;
            }
            map.put(num,i);
        }
        return false;

    }

思路2：
滑动窗口算法，滑动窗口长度不超过 k+1 ,同一个滑动窗口中任意两个下标的绝对值不超过 k 。
如果在同一个滑动窗口中，其中有重复元素，则满足nums[i] == nums[j] 且 abs(i - j) <= k 的要求

是否重复用哈希表 HashSet
如果 i>ki > ki>k，则下标 i−k−1 处的元素被移出滑动窗口，因此将 nums[i−k−1] 从哈希集合中删除

滑动窗口(最好)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Set<Integer> hash = new HashSet<Integer>();
        for(int i = 0; i < nums.length; i++){
            //将前一个元素从窗口中移除
            if(i > k){
                hash.remove(nums[i - k - 1]);
            }
            //在窗口中已经存在
            if(!hash.add(nums[i])){
                return true;
            }
        }
        return false;

    }
}

暴力解法 超时

1
2
3
4
5
6
7
8
9
10
public boolean containsNearbyDuplicate(int[] nums, int k) {
        for(int i = 0; i < nums.length; i++){
            for(int j = i + 1; j < nums.length; j++){
                if(nums[i] == nums[j] && Math.abs(i - j) <= k){
                    return true;
                }
            }
        }
        return false;
    }

④228.汇总区间

2024.1.11
题目：给定一个无重复元素的有序整数数组 nums 。
返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。
也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。
列表中的每个区间范围 [a,b] 应该按如下格式输出：
“a->b” ，如果 a != b
“a” ，如果 a == b

emmm 也就是说连续就放在一个区间，输出这种格式 “a->b”，”a”
不连续就断开，另起一个区间
输入：nums = [0,1,2,4,5,7]
输出：[“0->2”,”4->5”,”7”]

思路1：
运用双指针，i 和 j ，j 从 i 开始，如果 nums[j+1] = nums.length 或者 nums[j]+1 != nums[j+1] 则当前区间结束
i 更新为 j + 1 , j 继续向后遍历，直到数组结束
(需要运用字符串拼接)

双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public List<String> summaryRanges(int[] nums) {
        List<String> res = new ArrayList<String>();
        int i = 0;
        for(int j = i; j < nums.length; j++){
            //区间截止条件
            if( j + 1 == nums.length || nums[j]+1 != nums[j + 1]){
                //分两种情况进行字符串拼接
                StringBuilder sb = new StringBuilder();
                sb.append(nums[i]);
                if(i != j){
                    sb.append("->").append(nums[j]);
                }
                res.add(sb.toString());
                //另辟一个区间，进行下一次循环
                i = j+1;
            }
        }
        return res;
    }

⑤268.丢失的数字

2024.1.12
题目：
给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
输入：nums = [3,0,1]
输出：2
有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。

思路1：
可以运用**按位异或(^)**运算，将nums数组后面拼接 n+1 个 从 0 到 n 的数字，这样就是只有缺失的数组只出现一次，其余数字都出现两次
可以运用异或运算的三个性质：
①任何数和 0 做异或运算，结果仍然是原来的数，即 a^0=a
②任何数和其自身做异或运算，结果是 0，即 a^a=0
③异或运算满足交换律和结合律，即 a^b^a = b
a^b^a = b
将这一串数字进行按位异或运算就可以最后得到丢失的数字

按位异或(效率最高)

1
2
3
4
5
6
7
8
9
10
public int missingNumber(int[] nums) {
       int result = 0;
       for(int i = 0; i < nums.length; i++){
           result ^= nums[i];
       }
       for(int i = 0; i <= nums.length;i++){
           result ^= i;
       }
       return result;
   }

思路2：
从 0 到 n 的数字和，与数组 nums 的数字和 之差就是缺失数字

数学方法(巧妙效率高)

1
2
3
4
5
6
7
8
9
public int missingNumber(int[] nums) {
        int n = nums.length;
        int all = n * (n + 1) / 2;
        int sum = 0;
        for(int i = 0; i < n; i++){
            sum += nums[i];
        }
        return all - sum;
    }

排序(Arrays.sort())

1
2
3
4
5
6
7
8
9
10
public int missingNumber(int[] nums) {
        int length = nums.length;
        Arrays.sort(nums);
        for(int i = 0; i < length; i++){
            if(nums[i] != i){
                return i;
            }
        }
        return length;
    }

哈希集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int missingNumber(int[] nums) {
        Set<Integer> set = new HashSet<Integer>();
        for(int i = 0; i < nums.length; i++){
            set.add(nums[i]);
        }
        int missing = -1;
        for(int i = 0; i < nums.length + 1; i++){
            if(!set.contains(i)){
                missing = i;
                break;
            }
        }
        return missing;
    }

⑥283.移动零

2024.1.13
题目：给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

思路：
运用双指针，只有当 nums[i] != 0 时交换两个数字的位置
每次交换都是将左指针的 0 和右指针的 非0 交换的，或者指向的同一个数字原地交换

1 0 5 6 0
1 1 10560
0 0 10560
0 5 15060
0 6 15600

1 2 3 0 5
1 1 12305
2 2 12305
3 3 12305
0 0 12305
0 5 12350

双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
   public void moveZeroes(int[] nums) {
        int n = nums.length;
        int left = 0;
        int right = 0;
        while(right < n){
            if(nums[right]!=0 ){
                exchange(nums,left,right);
                left++;
            }
            right ++;
        }
    }
    //数组中相邻左右两个数字交换位置
    public void exchange(int[] nums,int left,int right){
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}

双指针优化(更好)

1
2
3
4
5
6
7
8
9
10
11
public void moveZeroes(int[] nums) {
        int l = 0;
        for(int r = 0; r < nums.length;r++){
            if(nums[r] != 0){
                int temp = nums[l];
                nums[l ++] = nums[r];
                nums[r] = temp;
            }
        }

    }

⑦303.区域和检索-数组不可变

2024.1.14
题目：
给定一个整数数组 nums，处理以下类型的多个查询:
计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的 和 ，其中 left <= right
实现 NumArray 类：
NumArray(int[] nums) 使用数组 nums 初始化对象
int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的 总和 ，包含 left 和 right 两点（也就是 nums[left] + nums[left + 1] + … + nums[right] )

前缀和是一个数组中某一段连续子数组的和。
在计算前缀和时，我们可以先将数组中的元素依次累加，得到一个新的数组，新数组中的每个元素表示原数组中从起始位置到当前位置的累加和。
通过预先计算前缀和，可以在O(1)的时间内得到任意子数组的和，从而优化一些需要频繁计算子数组和的算法。
前缀和在解决数组和矩阵相关的问题时非常有用。

思路：
由于会进行多次检索，即多次调用 sumRange，因此为了降低检索的总时间，应该降低 sumRange的时间复杂度，最理想的情况是时间复杂度 O(1)。为了将检索的时间复杂度降到 O(1)，需要在初始化的时候进行预处理。

前缀和示意图.png
前缀和数组第一个位置空出来

0 1 2 3 4
计算1-3 ——> 0-3 - 0-1
计算3-4 ——> 0-4 - 0-2
sumRange(left,right) = sumRange(0,right) - sumRange(0,left-1)

前缀和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class NumArray {
    int[] sums;
    //构造方法
    public NumArray(int[] nums) {
        int n = nums.length;
        sums = new int [n+1];
        for(int i = 0; i < n; i++){
            sums[i+1] = sums[i] + nums[i];
        }
    }
    
    public int sumRange(int left, int right) {
        return sums[right+1] - sums[left];

    }
}

⑧349.两个数组的交集

2024.1.15
题目：
给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的

思路：
用哈希表，将num1中的数字全部加到哈希集合中，如果哈希表中存在num2中的数字，就将其添加到一个新的哈希表(确保结果中的数字唯一)中

涉及将哈希表转换为一个int类型的数组：
int[] array = res.stream().mapToInt(Integer::intValue).toArray(); 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set = new HashSet<Integer>();
        Set<Integer> res = new HashSet<Integer>();
        for(int num1:nums1){
            set.add(num1);
        }
        for(int num2 : nums2){
            if(set.contains(num2)){
                res.add(num2);
            }
        }
        int[] array = res.stream().mapToInt(Integer::intValue).toArray();
        return array;
    }
}

或者

1
2
3
4
5
6
int[] array = new int[res.size()];
        int index = 0;
        for(int value:res){
            array[index++] = value;
        }
        return array;

⑨350.两个数组的交集Ⅱ

2024.1.16
题目：
给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。
返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]

思路1：
哈希表(键值对)
出现交集的次数 = 该数字在两个集合中出现次数的最小值
遍历第一个数组，得到数组中每一个数字对应出现的次数
遍历第二个数组，对于第二个数组中的每一个数字，如果在哈希表中存在这个数字，则将其添加到答案中，并减少哈希表中该数字存在的次数，直到为0

哈希表HashMap

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
public int[] intersect(int[] nums1, int[] nums2) {
       //先遍历短的更省空间(结果数组长度用较短一个的大小)
       if(nums1.length > nums2.length){
           return intersect(nums2,nums1);
       }
       Map<Integer,Integer> map = new HashMap<>();
       for(int num:nums1){
           int count = map.getOrDefault(num,0) + 1;
           map.put(num,count);
       }
       int[] result = new int [nums1.length];
       int index = 0;
       for(int num:nums2){
           int count = map.getOrDefault(num,0);
           if(count > 0){
               //存在该数字,加入结果数组中
               result[index ++] = num;
               //在Map中-1
               count--;
               if(count > 0){
                   //-1之后如果还大于0则更新Map
                   map.put(num,count);
               }else{
                   //否则将该数字从Map中删除
                   map.remove(num);
               }
           }
       }
       return Arrays.copyOfRange(result,0,index);
   }

思路2：
双指针，对两个数组先进行排序
用两个指针分别指向两个数组的头部
比较两个数字的大小，如果相同则将该数字加入到结果中，并都向右移动一位，
如果不相同，则将指向较小的数字的指针向右移动一位，
直到有任意一个指针超出数组范围为止。

1 2 2 3 4
0 1 2 2 5 9

双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int n1 = nums1.length;
        int n2 = nums2.length;
        int[] result = new int[Math.min(n1,n2)];
        int index1 = 0;
        int index2 = 0;
        int index = 0;
        while(index1 < n1 && index2 < n2){
            if(nums1[index1] < nums2[index2]){
                index1++;
            }else if(nums1[index1] > nums2[index2]){
                index2++;
            }else{
                result[index++] = nums1[index1];
                index1++;
                index2++;
            }
        }
        return Arrays.copyOfRange(result,0,index);
    }

⑩414.第三大的数

2024.1.17
题目：
给你一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。

思路3：
用三个数字维护数组中最大、次大、第三大的元素，初始值为长整形最小值Long.MIN_VALUE

一次遍历 100%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int thirdMax(int[] nums) {
        long a = Long.MIN_VALUE,b = Long.MIN_VALUE,c = Long.MIN_VALUE;
        for(long num:nums){
            if(num > a){
                c = b;
                b = a;
                a = num;
            }else if(a > num && num >b){
                c = b;
                b = num;
            }else if(b > num && num > c){
                c = num;
            }
        }
        return c == Long.MIN_VALUE ? (int)a : (int)c;
    }

思路2：
使用有序集合TreeSet(元素唯一且有序，无索引)，
遍历数组，将数组中的元素插入到有序TreeSet集合中，且维持TreeSet集合的大小<=3的状态，
(加入新元素后如果大小超过3则移除第一个元素)
最后如果size=3,则用first返回第一个数字，否则用last返回最后一个数字。

TreeSet 40%

1
2
3
4
5
6
7
8
9
10
11
public int thirdMax(int[] nums) {
        TreeSet<Integer> set = new TreeSet<>();
        for(int num:nums){
            set.add(num);
            if(set.size() > 3){
                set.remove(set.first());
            }
        }
        return set.size() == 3 ? set.first() : set.last();

    }

思路1：
将数组中的数字加入到哈希表中，将哈希表中的数字加入到一个新的数组中，将数组排序，
判断数组的长度，如果长度<=3，则返回数组最后一个位置的数字，否则返回倒数第3位置的数字。

0 1 2 3 4 5 6
size = 7

HashSet哈希表(self)25%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int thirdMax(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        int size = set.size();
        int[] array = new int[size];
        int index = 0;
        for (int num : set) {
            array[index++] = num;
        }
        Arrays.sort(array);
        if (size < 3) {
            return array[size - 1];
        }
        return array[size - 3];
    }
Donate
  • Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.
  • Copyrights © 2023-2025 Annie
  • Visitors: | Views:

嘿嘿 请我吃小蛋糕吧~

支付宝
微信