devbox
运维做开发
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

leetcode(Hot100)——数组篇_leetcode数组汇总

作者：运维做开发 | 2024-08-11 22:38:00

赞

踩

leetcode数组汇总

1、两数之和

        本题使用哈希法，用一个哈希Map保存数组的值以及对应下标，代码如下：

  1. class Solution {
  2.     public int[] twoSum(int[] nums, int target) {
  3.         HashMap<Integer,Integer> map = new HashMap<>();
  4.         for(int i=0; i<nums.length; i++){
  5.             if(map.containsKey(target-nums[i])){
  6.                 return new int[] {i,map.get(target-nums[i])};
  7.             }
  8.             map.put(nums[i],i);
  9.         }
  10.         return new int[] {-1,-1};
  11.     }
  12. }

2、字母异位词分组

        本题使用哈希法，使用哈希表存储每一组字母异位词，键为这组异位词的标志(将字符串排序后的字符串作为键)，值为这组字母异位词形成的列表。

        代码如下：

  1. class Solution {
  2.     public List<List<String>> groupAnagrams(String[] strs) {
  3.         Map<String,List<String>> map = new HashMap<>();
  4.         for(String str : strs){
  5.             char[] array = str.toCharArray();//将字符串转化成字符数组，方便排序
  6.             Arrays.sort(array);
  7.             String key = new String(array);//将排序后的字符数组转回字符串，当作哈希表的键
  8.             List<String> list = map.getOrDefault(key,new ArrayList<String>());//从哈希表取出当前键对应的值，若无则默认返回一个数组列表
  9.             list.add(str);//将当前字符串加入数组列表
  10.             map.put(key,list);
  11.         }
  12.         return new ArrayList<>(map.values());
  13.     }
  14. }

3、最长连续序列

         考虑到数组中可能有重复元素需要去重，并且有查找操作，可以使用HashSet集合，既可以去除重复元素，又方便进行查找操作。

        遍历集合，如果有当前元素的后继元素，则序列长度++。 代码如下：

  1. class Solution {
  2.     public int longestConsecutive(int[] nums) {
  3.         Set<Integer> hashSet = new HashSet<>();
  4.         int ans = 0;
  5.         for(int num : nums){
  6.             hashSet.add(num);
  7.         }
  8.         for(int num : hashSet){
  9.             //有前驱元素直接跳过，因为此时肯定不是最长序列。
  10.             if(!hashSet.contains(num-1)){
  11.                 int local_max = 1;
  12.                 while(hashSet.contains(num+1)){
  13.                     local_max += 1;
  14.                     num += 1;
  15.                 }
  16.                 ans = Math.max(ans , local_max); 
  17.             }
  18.         }
  19.         return ans;
  20.     }
  21. }

4、移动零

        本题需要原地操作，使用双指针解决，快指针用于遍历旧数组，慢指针用于维护新数组。代码如下：

  1. class Solution {
  2.     public void moveZeroes(int[] nums) {
  3.         int fast = 0;
  4.         int slow = 0;
  5.         while(fast < nums.length){
  6.             if(nums[fast] == 0){
  7.                 fast++;
  8.             }
  9.             else{
  10.                 nums[slow] = nums[fast];
  11.                 slow++;
  12.                 fast++;
  13.             }
  14.         }
  15.         for(int i=slow; i<nums.length; i++){
  16.             nums[i] = 0;
  17.         }
  18.     }
  19. }

 5、盛最多水的容器

        本题利用双指针分别指向数组头和尾，然后用一个变量保存最大面积，每记录一次，让指针移动一格，这里比较关键的点就是要让height值比较低的那个指针移动，最后当两个指针相碰时，结束循环 。

        代码如下：

  1. class Solution {
  2.     public int maxArea(int[] height) {
  3.         int left = 0;
  4.         int right = height.length-1;
  5.         int ans = 0;
  6.         while(left < right){
  7.             ans = Math.max(ans , (right-left)*Math.min(height[left],height[right]));
  8.             if(height[left] < height[right]){
  9.                 left++;
  10.             }
  11.             else{
  12.                 right--;
  13.             }
  14.         }
  15.         return ans;
  16.     }
  17. }

6、三数之和

        本题采用排序+双指针的解法，关键点是需要去重，代码如下：

  1. class Solution {
  2.     public List<List<Integer>> threeSum(int[] nums) {
  3.         List<List<Integer>> ans = new ArrayList<>();
  4.         Arrays.sort(nums);
  5.         for(int i=0; i<nums.length; i++){
  6.             if(i>0 && nums[i]==nums[i-1]) continue;
  7.             int left = i+1;
  8.             int right = nums.length-1;
  9.             while(left < right){
  10.                 if(left>i+1 && nums[left]==nums[left-1]){
  11.                     left++;
  12.                     continue;
  13.                 }
  14.                 if(right<nums.length-1 && nums[right]==nums[right+1]){
  15.                     right--;
  16.                     continue;
  17.                 }
  18.                 if(nums[i]+nums[left]+nums[right] < 0) left++;
  19.                 else if(nums[i]+nums[left]+nums[right] > 0) right--;
  20.                 else{
  21.                     List<Integer> list = new ArrayList<>();
  22.                     list.add(nums[i]);
  23.                     list.add(nums[left]);
  24.                     list.add(nums[right]);
  25.                     ans.add(list);
  26.                     left++;
  27.                     right--;
  28.                 }
  29.             }    
  30.         }
  31.         return ans;
  32.     }
  33. }

7、接雨水

        经典题目接雨水，思路就是用两个数组 left 和 right 分别保存当前柱子左侧和右侧的最高柱子(第一个和最后一个柱子不需要保存)， 再分别求出每一列柱子能存储的水量。 代码如下：

  1. class Solution {
  2.     public int trap(int[] height) {
  3.         int left[] = new int[height.length];
  4.         int right[] = new int[height.length];
  5.         int left_max = height[0];
  6.         int right_max = height[height.length-1];
  7.         int ans = 0;
  8.         //当前柱子左侧的最高柱子
  9.         for(int i=1; i<height.length-1; i++){
  10.             left[i] = left_max;
  11.             left_max = Math.max(left_max , height[i]);
  12.         }
  13.         //当前柱子右侧的最高柱子
  14.         for(int i=height.length-2; i>=1; i--){
  15.             right[i] = right_max;
  16.             right_max = Math.max(right_max,height[i]);
  17.         }
  18.         for(int i=1; i<height.length-1; i++){
  19.             int area = Math.max(0 , Math.min(left[i],right[i])-height[i]);
  20.             ans += area;
  21.         }
  22.         return ans;
  23.     }
  24. }

8、和为 K 的子数组

        暴力双层for循环：

  1. class Solution {
  2.     public int subarraySum(int[] nums, int k) {
  3.         int ans = 0;
  4.         for(int i=0; i<nums.length; i++){
  5.             int sum = 0;
  6.             for(int j=i; j<nums.length; j++){
  7.                 sum += nums[j];
  8.                 if(sum == k){
  9.                     ans++;
  10.                 }
  11.             }
  12.         }
  13.         return ans;
  14.     }
  15. }

9、合并区间

        本题需要先对数组进行排序，以数组的第一个元素进行从小到大的排序。然后遍历各子数组看是否有重叠部分，有的话则合并。 代码如下：

  1. class Solution {
  2.     public int[][] merge(int[][] intervals) {
  3.         List<int[]> ans = new ArrayList<>();
  4.         Arrays.sort(intervals,new Comparator<int[]>(){
  5.             public int compare(int[] a, int[] b){
  6.                 return a[0] - b[0];
  7.             }
  8.         });
  9.         ans.add(intervals[0]);
  10.         for(int i=1; i<intervals.length; i++){
  11.             //有重叠区间
  12.             if(ans.get(ans.size()-1)[1] >= intervals[i][0]){
  13.                 ans.get(ans.size()-1)[1] = Math.max(ans.get(ans.size()-1)[1] , intervals[i][1]);
  14.             }
  15.             else{
  16.                 ans.add(intervals[i]);
  17.             }
  18.         }
  19.         return ans.toArray(new int[ans.size()][]);
  20.     }
  21. }

10、轮转数组

       思路是new一个新数组，将轮转之后的元素加入新数组中，然后再将新数组赋值给旧数组。

        这里赋值需要注意不能直接使用等于号，这里我使用System.arraycopy()方法，其中有五个参数，分别为：源数组、赋值的起始位置、目的数组、赋值的起始位置、需要赋值的长度。 代码如下：

  1. class Solution {
  2.     public void rotate(int[] nums, int k) {
  3.         int[] ans = new int[nums.length];
  4.         if(k % nums.length == 0) return;
  5.         if(k > nums.length){
  6.             k = k % nums.length;
  7.         }
  8.         int t = k;
  9.         for(int i=nums.length-1; i>=nums.length-k; i--){
  10.             ans[t-1] = nums[i];
  11.             t--;
  12.         }
  13.         int j = k;
  14.         for(int i=0; i<nums.length-k; i++){
  15.             ans[j] = nums[i];
  16.             j++;
  17.         }
  18.         System.arraycopy(ans,0,nums,0,nums.length);
  19.     }
  20. }

11、除自身以外数组的乘积 

        定义两个数组left和right，left[i]和right[i]分别记录当前元素 i 左边和右边的乘积。 特别的，left第一个元素需初始化为1，right最后一个元素也需初始化为1。 代码如下：

  1. class Solution {
  2.     public int[] productExceptSelf(int[] nums) {
  3.         int[] ans = new int[nums.length];
  4.         int[] left = new int[nums.length];
  5.         int[] right = new int[nums.length];
  6.         left[0] = 1;
  7.         right[nums.length-1] = 1;
  8.         for(int i=1; i<nums.length; i++){
  9.             left[i] = left[i-1] * nums[i-1];
  10.         }
  11.         for(int i=nums.length-2; i>=0; i--){
  12.             right[i] = right[i+1] * nums[i+1];
  13.         }
  14.         for(int i=0; i<nums.length; i++){
  15.             ans[i] = left[i] * right[i];
  16.         }
  17.         return ans;
  18.     }
  19. }

 

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号