hi,你好!欢迎访问本站!登录
本站由网站地图腾讯云宝塔系统阿里云强势驱动
当前位置:首页 - 教程 - 杂谈 - 正文 君子好学,自强不息!

LeetCode刷题总结-数组篇(上)

2019-11-18杂谈搜奇网23°c
A+ A-

       数组是算法中最经常运用的一种数据结构,也是口试中最常考的考点。在LeetCode题库中,标记为数组范例的习题到目前为止,已累计到了202题。然则,这202道习题并非每道题只标记为数组一个考点,大部分习题都有两到三个考点。比方,考核数组+哈希表、数组+动态设计+数学、数组+回溯等。

       看到云云多考点标签,假如盲目地根据一个标签内部一切习题的递次去刷题,会让人有点紊乱感。关于时刻比较紧凑的同砚来讲,题目的数目比较多,想在较短时刻内刷完是一个很大的应战。因而,本文针对时刻较紧凑的同砚精选一些数组范例的代表性题目,举行分类总结,愿望能够起到一点协助(PS:实际上是作者愿望借此进一步加深本身对考点的认知,竖立一个有用的学问系统… …)。

       标记为数组范例的题目有200多道题,本文的重点关注那些重要考核数组的题目。关于考核点重要放在别的考点(比方:二分查找、双指针、哈希表等)上的题目,作者设计把这些题目放在后序总结篇章中。根据作者刷题的状况,在属于数组考点系列的题目中,分别为四个常考题目:子数组题目、矩阵题目、O(n)范例题目和头脑转换范例题目。

  • 子数组题目:就是给定一个数组,缭绕该数组的子数组列出诸多难题,守候我们来解答。
  • 矩阵题目:给定一个矩阵(或许称为二维数组),缭绕该矩阵列出差别体式格局遍历矩阵中元素等难题,守候我们来解答。
  • O(n)范例题目:O(n)是指时刻复杂度为O(n),给定的题目题意平常很轻易明白,其平常解法(俗称暴力解法,时刻复杂度平常为O(n^2),以至更高)也很简朴,然则题目请求你的解法时刻复杂度为O(n)。看到这些题目的某些解答后,会让我们不由得夸奖:真乃神人、好厉害、奇特特解、奇妙、强、文雅。
  • 头脑转换范例题目:其解答不属于上述三种范例题目,然则解答体式格局有点奇妙,或许说该范例题目较为基本,极可能考核你的疾速运用代码才能的题目。(PS: 实际上是作者本身也不好分别,然则以为有点代价的题目… …)

       本文是《LeetCode刷题总结-数组篇(上)》,总结归结有关子数组题目的题目。本期题目数目共17题,个中难度为简朴有1题,难度为中等的有12题,难度为难题的有4题。详细题目信息及解答见下文。

 

例1 最大子序和

题号:53,难度:简朴

题目形貌:

 

解题思绪:

本题最为典范和普遍的解法是运用动态设计的头脑来解答,其时刻复杂度为O(n)。题目中勉励尝试运用更加精巧的分治法求解,经由过程翻阅相干解答和批评发明,分治法并没有动态设计解答的文雅,其时刻复杂度为O(nlogn),也并非最优。所以,引见一下运用动态设计解题的思绪。

从数组第一个元素最先遍历,用一个一维数组存储遍历到当前元素的最大一连子数组的和。

当遍历到第i个元素时,假如前i-1和元素中一连子数组和加上第i个元素时比第i个元素的值要大,那末就更新dp[i] = dp[i-1] + nums[i],不然dp[i] = nums[i]。

详细代码:

class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length + 1];
        int result = nums[0];
        for(int i = 0;i < nums.length;i++) {
            dp[i+1] = Math.max(dp[i]+nums[i], nums[i]);
            result = Math.max(dp[i+1], result);
        }
        
        return result;
    }
}

实行结果:

 

例2 乘积最大子序列

题号:152,难度:中等

题目形貌:

 

解题思绪:

这题实际上是例1 最大子序和一个变例,由加法变更成了乘法操纵(依旧是运用动态设计的思绪)。此时须要做的转变是定义两个变量来存储当前子序列的乘积,一个是保留最大值,一个是保留最小值(包括负数的子序列)。

详细代码:

class Solution {
    public int maxProduct(int[] nums) {
        int result = nums[0], n_max = 1, n_min = 1;
        for(Integer n: nums) {
            if(n < 0) {
                int temp = n_max;
                n_max = Math.max(n_min * n, n);
                n_min = Math.min(temp * n, n);
            } else {
                n_max = Math.max(n_max * n, n);
                n_min = Math.min(n_min * n, n);
            }
               
            result = Math.max(n_max, result);
        }
        
        return result;
    }
}

实行结果:

 

例3 子集

题号:78,难度:中等。(可参考子集II, 题号90,难度:中等)

题目形貌:

 

解题思绪:

本题考核我们运用回溯来求解一切子集的题目,在一些算法课本中最典范的题目时求解全分列的题目,解法和这道题相似。

此题须要特别注重的是,起首采纳链表在递归过程当中增加元素,在回溯时删除元素,能够有用进步时刻效力。其次,给递归挪用程序设计一个start参数,能够防止同一个元素被反复递归挪用,达到了剪枝结果。

末了,在结果列表中采纳从新建立一个列表存储子集的结果,是由于在递归函数中列表参数只对应一个地点,采纳从新建立相当于运用了深拷贝的头脑,防止了结果均为空集的状况。

详细代码:

class Solution {
    private List<List<Integer>> result;
    
    public List<List<Integer>> subsets(int[] nums) {
        result = new ArrayList<>();
        if(nums.length <= 0)
            return result;
        dfs(nums, 0, new LinkedList<Integer>());
        
        return result;
    }
    
    public void dfs(int[] nums, int start, LinkedList<Integer> list) {
        result.add(new ArrayList<Integer>(list));
        for(int i = start;i < nums.length;i++) {
            list.addLast(nums[i]);
            dfs(nums, i + 1, list);
            list.removeLast();
        }
    }
}

实行结果:

 

例4 最长一连序列

题号:128,难度:难题

题目形貌:

 

解题思绪:

采纳哈希表存储数组中一切元素,然后运用哈希表查询当前元素的摆布双方序列数字是不是存在,查询操纵的时刻复杂度为O(1),所以团体的时刻复杂度为O(n)。

详细代码:

class Solution {
    public int longestConsecutive(int[] nums) {
        int result = 0;
        Set<Integer> set = new HashSet<>();
        for(Integer n: nums)
            set.add(n);
        for(Integer n: nums) {
            if(set.contains(n)) {
                int len = 1;
                int temp = n;
                while(set.contains(--temp)) {
                    len++;
                    set.remove(temp);
                }
                temp = n;
                while(set.contains(++temp)) {
                    len++;
                    set.remove(temp);
                }
                result = Math.max(result, len);
            } 
        }
        
        return result;
    }
}

实行结果:

 

例5 乘积小于K的子数组

题号:713,难度:中等

题目形貌:

 

解题思绪:

本题考核运用双指针的头脑,一前一后同时今后遍历。

详细代码:

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int result = 0, left = 0, right = 0;
        int target = 1;
        while(right < nums.length) {
            target *= nums[right++];
            while(left < right && target >= k)
                target = target / nums[left++];
            result += (right - left);     
        }
      
        return result;
    }
}

实行结果:

 

例6 和为K的子数组

题号:560,难度:中等

题目形貌:

 

解题思绪:

本题采纳哈希表存储从数组第一个元素不停今后的子序列和,然后推断到当前元素的序列总和减去K的值在哈希表中有多少个,即为包括当前元素的子序列能够获得目的结果,应用前后子序列的差能够获得目的子序列和为K。

详细代码:

class Solution {
    public int subarraySum(int[] nums, int k) {     
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int sum = 0, result = 0;

        for(int i = 0; i < nums.length; ++i) {
            sum += nums[i];
            if(map.containsKey(sum-k))
                result += map.get(sum-k);
            map.put(sum, map.getOrDefault(sum, 0)+1);
        }
        
        return result;
    }
}

实行结果:

 

例7 可被K整除的子数组

题号:974,难度:中等

题目形貌:

 

解题思绪:

从第一个元素最先,求取一连子数组的余数(sum % k),采纳Map存储每一个余数的个数。

雷同余数的子数组个数大于即是2时,恣意拔取个中两个子数组余数相减,即余数抵消,可获得一个相符题目请求的sum。(此处的个数盘算体式格局为:n*(n-1) / 2)

然则,此处有两个须要注重的点:

(1) 假如余数为0,终究0的余数个数只要一个时(1*(1-1)/2 = 0),如许盘算会脱漏(假如为多个,也会有脱漏,能够本身盘算,能够本身轻微揣摩)。所以,在初始化Map时,增加以下代码:

map.put(0, 1); 

(2) 假如余数为负数,就不能实行雷同余数相减抵消的操纵。此时,须要做以下处置惩罚:

// sum % K 一般盘算方法

((sum % K) + K) % K   // 假如为负数时,须要转换为正数,这个转换原

详细代码:

class Solution {
    public int subarraysDivByK(int[] A, int K) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int result = 0;
        int sum = 0;
        
        for(Integer a: A) {
            sum += a;
            map.put(((sum % K) + K) % K , map.getOrDefault(((sum % K) + K) % K, 0)+1);
        }      
        // System.out.println("map = "+map);
        for(Integer key: map.keySet())
            result += map.get(key) * (map.get(key) - 1) / 2;
        
        return result;
    }
}

实行结果:

 

例8 三个无堆叠子数组的最大和

题号:689,难度:难题

题目形貌:

 

解题思绪:

采纳动态设计求解,状况转移方程:dp[2][n] = max(dp[2][n-1], dp[1][n-k] + sumRange(n, n -k+1))。个中一维长度为3,示意三个子数组。

详细代码(代码援用自LeetCode的一个题解):

class Solution {
     public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        int[][] dp = new int[3][nums.length];
        int[] cummulative = new int[nums.length];
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            cummulative[i] = sum;
        }
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < nums.length; j++) {
                if (j < (i + 1) * k - 1) {
                    dp[i][j] = 0;
                } else {
                    if (i == 0) {
                        // 易错点: 当k=1的时刻,边界条件须要处置惩罚一下。
                        dp[i][j] = Math.max(j > 0 ? dp[i][j - 1] : 0, rangeSum(cummulative, j - k + 1, j));
                    } else {
                        dp[i][j] = Math.max(j > 0 ? dp[i][j - 1]: 0, rangeSum(cummulative, j - k + 1, j) + dp[i - 1][j - k]);
                    }
                }

            }
        }
        int[] ans = new int[3];
        int length = dp[2].length - 1;
        for (int i = 2; i >= 0; i--) {
            int[] row = dp[i];
            for (int j = length - 1; j >= 0; j--) {
                if (row[j] != row[length]) {
                    ans[i] = j - k + 2;
                    length = j - k + 1;
                    break;
                }
            }
        }
        return ans;
    }

    private int rangeSum(int[] cummulative, int left, int right) {
        if (left == 0) {
            return cummulative[right];
        } else {
            return cummulative[right] - cummulative[left - 1];
        }
    }

}

实行结果:

 

例9 最长反复子数组

题号:718,难度:中等

题目形貌:

 

解题思绪:

本题既能够用哈希表来解答,也能够用动态设计的头脑来解答。运用动态设计的思绪解答的时刻效力最高。此处引见一下动态设计的解题思绪。dp[i][j]示意A [i-1]为尽头,B[j-1]为尽头时二者的最长大众子数组。详细更新战略见代码。

详细代码:

class Solution {
      public int findLength(int[] A, int[] B) {
        
        int[][] dp = new int[A.length + 1][B.length + 1];
        int res = 0;
        for (int i = 1; i <= A.length; i++)
            for (int j = 1; j <= B.length; j++) {
                
                if (A[i - 1] == B[j - 1])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                
                res = Math.max(res, dp[i][j]);
            }
        
        return res;
    }
}

实行结果:

 

例10 婚配子序列的单词数

题号:792,难度:中等

题目形貌:

 

解题思绪:

要特别注重子序列的寄义,子序列是根据夙昔今后的递次恣意多个元素构成的序列,个中的递次不能变动。因而,不能运用哈希表统计字母的个数来推断是不是包括某个单词。此处可采纳暴力法直接婚配查找,时刻效力较低。此处可采纳二分查找来优化婚配结果,能进步时刻效力。

详细代码(贴一个LeetCode上批评的代码):

class Solution {
    List<Integer> index[]=new ArrayList[26];
    
    public int numMatchingSubseq(String S, String[] words) {
         for(int i=0;i<S.length();i++){
            char ch=S.charAt(i);
            if(index[ch-'a']==null)
                index[ch-'a']=new ArrayList();
            index[ch-'a'].add(i);
         }
         int res=0,pre;
         for(String str:words){
            pre=-1;
            for(int i=0;i<str.length();i++){
                pre=helper(str.charAt(i)-'a',pre);
                if(pre==-1)
                    break;
            }
            if(pre!=-1)
                res++;
         }
         return res;
    }
    
    private int helper(int i,int pre){
        if(index[i]==null)
            return -1;
        
        int l=0,r=index[i].size()-1;
        if(pre==-1)
            return index[i].get(0);
        if(index[i].get(r)<=pre)
            return -1;
        
        while(l<r){
            int mid=(l+r)/2;
            if(index[i].get(mid)<=pre)
                l=mid+1;
            else
                r=mid;
        }
        
        return index[i].get(l);
   }
}

实行结果:

 

例11 区间子数组个数

题号:795, 难度:中等

题目形貌:

 

解题思绪:

最大元素满足大于即是L小于即是R的子数组个数 = 最大元素小于即是R的子数组个数 - 最大元素小于L的子数组个数。

详细代码:

class Solution {
    public int numSubarrayBoundedMax(int[] A, int L, int R) {
        return numSubarrayBoundedMax(A, R) - numSubarrayBoundedMax(A, L - 1);
    }

    private int numSubarrayBoundedMax(int[] A, int Max) {
        int res = 0;
        int numSubarry = 0;
        for (int num : A) {
            if (num <= Max) {
                numSubarry++;
                res += numSubarry;
            } else {
                numSubarry = 0;
            }
        }
        return res;
    }
}

实行结果:

 

例12 子数组的最小值之和

题号:907,难度:中等

题目形貌:

 

解题思绪:

参考自LeetCode的批评解答:盘算每一个数在子数组中最小的次数。

详细代码:

class Solution {
    public int sumSubarrayMins(int[] A) { long res = 0; long mod = 1000000007; for (int i = 0; i<A.length; i++) { int l = i-1; for (; l>=0 && A[i] < A[l]; l--) ; int r = i+1; for (; r<A.length && A[i] <= A[r]; r++) ; res += (i-l)*(r-i)*A[i]; } return (int)(res % mod); } }

实行结果:

 

例13 子序列宽度之和

题号:891,难度:难题

题目形貌:

 

解题思绪:

详细可参考LeetCode的一篇题解。

详细代码:

class Solution {
    public int sumSubseqWidths(int[] A) {
        final int MOD = (int) (1e9 + 7);
        Arrays.sort(A);
        int n = A.length;
        long res = 0;
        long p = 1;
        for (int i = 0; i < n; ++i) {
            res = (res + (A[i] - A[n - 1 - i]) * p) % MOD;
            p = (p << 1) % MOD;
        }
        return (int) ((res + MOD) % MOD);
    }
}

实行结果:

 

例14 环形子数组的最大和

题号:918, 难度:中等

题目形貌:

 

解题思绪:

由于题目请求有环形,所以须要定义两个变量。一个变量存储当前无环形是的一连最大子数组和,一个存储无环形一连最小子数组和。末了采纳数组的总和减去最小和,和已保留的最大和举行比较。别的,须要注重一点假如数组悉数为负数时,此时直接返回子数组的最大值(由于此时,最小子数组和就是数组的和)。

详细代码:

class Solution {
    public int maxSubarraySumCircular(int[] A) {
        int max = A[0];
        int min = A[0];
        int maxSoFar = A[0];
        int minSoFar = A[0];
        int sum = A[0];
        for (int i=1;i<A.length;i++) {
          sum += A[i];
          maxSoFar = Math.max(A[i],maxSoFar+A[i]);
          minSoFar = Math.min(A[i],minSoFar+A[i]);
          max = Math.max(max,maxSoFar);
          min = Math.min(min,minSoFar);
        }
        if (max < 0) 
            return max;
        return Math.max(max,sum-min);
    }
}

实行结果:

 

例15 最长湍流子数组

题号:978,难度:中等

题目形貌:

 

解题思绪:

采纳一连三个位置数据是不是相符湍流特性来推断,时刻复杂度为O(n)。

详细代码(援用自LeetCode一个批评代码):

class Solution {
    public int maxTurbulenceSize(int[] A) {
        int N = A.length;
        int ans = 1;
        int anchor = 0;

        for (int i = 1; i < N; ++i) {
            int c = Integer.compare(A[i-1], A[i]);
            if (i == N-1 || c * Integer.compare(A[i], A[i+1]) != -1) {
                if (c != 0) ans = Math.max(ans, i - anchor + 1);
                anchor = i;
            }
        }

        return ans;
    }
}

实行结果:

 

例16 两个非堆叠子数组的最大和

题号:1031,难度:中等

题目形貌:

 

解题思绪:

采纳滑动窗口的思绪来解答,对长度为L的数组,采纳大小为L的滑动窗口,关于长度为M的数组采纳大小为M的窗口。然后,经由过程两个窗口之间的间隔来遍历。

详细代码:

class Solution {
    public  int maxSumTwoNoOverlap(int[] A, int L, int M) {
        int len = A.length, dpL[] = new int[len - L + 1], dpM[] = new int[len - M + 1], max = 0;
        for (int i = 0; i < L; i++)
            dpL[0] += A[i];
        for (int i = 0; i < M; i++)
            dpM[0] += A[i];
        for (int i = 1; i < len - L + 1; i++)
            dpL[i] = dpL[i - 1] + A[i + L - 1] - A[i - 1];
        for (int i = 1; i < len - M + 1; i++)
            dpM[i] = dpM[i - 1] + A[i + M - 1] - A[i - 1];
        for (int i = 0; i < len - L - M + 1; i++) {
            int count = len - i - L - M;
            while (count >= 0) {
                max = Math.max(max, Math.max(dpL[i] + dpM[i + L + count], dpM[i] + dpL[i + M + count]));
                count--;
            }
        }
        return max;
    }
}

实行结果:

 

例17 子数组中占绝大多数的元素

题号:1157,难度:难题

题目形貌:

 

解题思绪:

采纳哈希数组来解答,一旦哈希数组中目的元素值大于即是threshold,就返回目的数字,不然返回-1。

详细代码:

class MajorityChecker {

    private int[] nums;
    private int[] ans;
    private int max;
    
    public MajorityChecker(int[] arr) {
        nums = arr;
        max = arr[0];
        for(int x : arr)
            if(x > max)
                max = x;
        
    }
    
    public int query(int left, int right, int threshold) {
        ans = new int[max + 5];
        for(int i = left;i <= right;i++){
            if(++ans[nums[i]] >= threshold)
                return nums[i];
        }
        return -1;
    }
}

实行结果:

 

 

  选择打赏方式
微信赞助

打赏

QQ钱包

打赏

支付宝赞助

打赏

  移步手机端
LeetCode刷题总结-数组篇(上)

1、打开你手机的二维码扫描APP
2、扫描左则的二维码
3、点击扫描获得的网址
4、可以在手机端阅读此文章
未定义标签

本文来源:搜奇网

本文地址:https://www.sou7.cn/282205.html

关注我们:微信搜索“搜奇网”添加我为好友

版权声明: 本文仅代表作者个人观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。请记住本站网址https://www.sou7.cn/搜奇网。

发表评论

选填

必填

必填

选填

请拖动滑块解锁
>>