Dbettkk-Blog
0%

算法记录

Posted on Edited on In Views: Valine:

20/05/27

LeetCode 974

题目描述

给定一个整数数组 A，返回其中元素之和可被 K 整除的（连续、非空）子数组的数目。

类别

前缀和

示例：
1
2
3
4
5
输入：A = [4,5,0,-2,-3,1], K = 5
输出：7
解释：
有 7 个子数组满足其元素之和可被 K = 5 整除：
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
数据范围

  • 1 <= A.length <= 30000

  • -10000 <= A[i] <= 10000

  • 2 <= K <= 10000

分析

首先肯定先暴力想一波，直接两层for循环，sum保存和，然后依次模K进行判断。但是时间复杂度肯定O(N^2)，看范围肯定是过不了了，然后再想想其他办法。分析题目，对于子数组求和的问题，肯定先前缀和一波，前缀和存在数组P[]中，注意P[0]=0初始化别忘了(后面会有坑)，即前0个元素和为0。然后再解析题目，要求元素之和能被K整除，即(P[j]-P[i])%K==0，到这里还是没有什么突破口，因为这样还是得遍历，时间复杂度肯定上去了。所以就很关键的数学定理出现了，同余定理。即保证P[i]%K==P[j]%K就肯定能保证(P[j]-P[i])%K==0了。接下来就是遍历了，计算每个P[i]%K的值，然后相同的值之间肯定存在子数组符合条件。如果存在多个相同的值，那就可以组合出很多情况，比如如果存在四个P[i]%K的值相同，那肯定就存在6种组合方式组成的子数组，这肯定不难相到排列组合问题。然后就针对这个进行下一步优化，因为要求相同的值的个数，所以可以用Map实现，遍历P数组，P[i]%K的值以及该值的出现次数存入Map中，然后最后遍历Map的value，进行相应的排列组合运算再相加就解决了。

需要注意的地方就是，如果我们最开始没有初始化的话，如果遇到P[i]%K==0的时候，该子数组肯定是满足的，不需要另一个P[j]与其配对，如果没有这个初始化的0，我们算法在统计的时候就会少，这个bug还很难找到。如果不太理解，可以看这个例子：[2,2,1] K=5，我们按照算法来，没有初始化，P数组就为[2,4,5]，然后依次%K，得到[2,4,0]，然后放入Map中，每个都是1，即最后得到结果为0，但实际上的结果应该是1，子数组[2,2,1]是满足的，所以这就是需要初始化的原因了。还有需要注意的地方就是P[i]是会出现负数的情况的，所以在%K的时候应该加上一部分值使其为正值再取模。

优化

可以用数组代替Map来提高效率降低空间利用率，即因为%K的结果就在0-K-1之间，则可以设定数组times[MAX]，初始化为0，MAX取K值，然后每次得到P[i]%K时，就times[P[i]%K]++即可，这样就免去了Map的复杂操作，但是空间复杂度就会高一些，后面的遍历也是一样的道理了。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.*;
class Solution {
    public int subarraysDivByK(int[] A, int K) {
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        int[] p = new int[30005];
        int sum=0;
        p[0]=0; // 初始化
        for(int i=0;i<A.length;i++){
            sum+=A[i];
            p[i+1]=sum;
        }
        sum = 0;
        for(int i=0;i<A.length+1;i++){
            int temp = (p[i]+15000*K)%K;
            if(map.containsKey(temp)) map.put(temp,map.get(temp)+1);
            else map.put(temp,1);
        }
        for(int v:map.values()){
            sum+=v*(v-1)/2;
        }
        return sum;
    }
}

LeetCode 1

题目描述

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

分析

简单题，就不放代码了，就是依次存入hash表中，也就是存入Map中，value作为键，下标作为值，然后再进行遍历并判断即可。写到这里肯定会问如果有重复的value怎么办，如果重复，那肯定要么这个value的是target的1/2，要么不是组成target的一部分，因为题目保证只有一个解。所以我们考虑这个value的是target的1/2的情况，那hash表内就只存了一个value及其下标，但其实并不影响，因为当遍历到没有存进Map的那个value对应的nums[i]时，进行判断，如果成功就输出当前元素的下标和对应存进Map那个value的下标即可，也同样可以完成题目要求，并不影响。

LeetCode 2

题目描述

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例
1
2
3
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
分析

首先，第一个思路肯定是每一位挨着挨着求和存数组，然后再把数组每一个元素乘以10相应的幂再相加，就得到了最终需要的数字sum，再把这个数每一位放在另一个链表上，就ok了。这样肯定能做，但需要注意的是sum的范围，可能是很大很大的，所以这里是第一个可以进行改进的地方，我们可以不对其求和，每次得到两个链表某一位上相加得到的数后，直接对其进行处理，即放在链表上。比如num[cnt]+=l1.val+l2.val，然后判断num[cnt]是否>=10，如果>=10，则num[cnt+1]=1；这也是为什么前面使用+=的原因了。这样得到num[cnt]后，再通过new ListNode(num[cnt]%10)来构建当前数的链表。细心的朋友应该发现了，其实根本不必使用num数组，直接用num就可以了，只需要添加一句else num=0，这样就形成了第二个优化。

需要注意的地方就是，l1和l2可能不一样长，所以需要补0.还有就是特殊情况的处理，可能l1和l2的最后一位进位了，同时又退出了循环，所以需要判断一下。

代码
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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int num=0;
        ListNode l3 = new ListNode(0);
        ListNode temp = l3;
        int cnt=0;
        while(l1!=null||l2!=null){
            if(l1==null) l1=new ListNode(0);
            if(l2==null) l2=new ListNode(0);
            num+=(l1.val+l2.val);
            temp.next = new ListNode(num%10);
            temp = temp.next;
            if(num>=10) num=1;
            else num=0; 
            l1=l1.next;
            l2=l2.next;  
        }
        if(num==1) temp.next=new ListNode(1);
        return l3.next;
    }
}

20/05/30

LeetCode 84

题目描述

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。

类别

单调栈

示例
1
2
输入: [2,1,5,6,2,3]
输出: 10
分析

首先可以想到暴力算法，即固定每个柱子高度，然后枚举矩形的宽度。这样时间复杂度就O(N^2)，肯定不是我们所希望的。然后我们考虑优化，因为要找最大的面积，而且柱子的高度是有高有低的，我们可以想到单调栈来完成，如果对单调栈没什么了解的，可以看看这道题后面的一个小题，帮助理解单调栈的用法和好处。然后言归正传，我们就考虑维护一个单调栈，如果遇到比当前栈顶的柱子更高的柱子，就将该柱子入栈，如果遇到了比当前栈顶矮的柱子，那就出栈，直到遇到比当前柱子矮的栈顶，然后再将该柱子入栈，同时在其他柱子出栈的时候需要注意更新相应的最大矩形面积，这里是比较难理解的。比如，当前柱子比栈顶矮，然后需要出栈，然后因为出栈的这个柱子是栈中柱子最高的，所以以这个柱子为顶的矩形面积可以求出，并比较更新相应的最大矩形面积。用一句能够帮助理解的话就是每个柱子出栈的时候，我们都已经计算了以它为顶的矩形的面积的最大值，并对最后结果进行了更新，即不会导致出栈后得到的面积不是最大面积。可以通过看代码来帮助理解。

需要注意的地方是，我们在具体实现的时候，需要在高度数组最后插入一个高度为0或者-1的元素，保证栈中所有元素都能出栈。还有我们栈中保存的实质是柱子对应的下标。然后因为需要对给的高度数组进行操作，我们采用c++来描述。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int largestRectangleArea(vector<int>& height) {
        int ret = 0;
        height.push_back(0);
        vector<int> index;
        for(int i = 0; i < height.size(); i++) {
            while(index.size() > 0 && height[index.back()] >= height[i]) {
                int h = height[index.back()];
                index.pop_back();
                int sidx = index.size() > 0 ? index.back() : -1;
                ret = max(ret, h * (i-sidx-1));
            }
            index.push_back(i);
        }
        return ret;
    }

帮助理解单调栈，[click here][https://zhuanlan.zhihu.com/p/26465701]