leetcode牛客进阶班

发表于 | 分类于

9. 回文数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public boolean isPalindrome(int x) {
    if(x<0){
        return false;
    }
    //计算x的最高位数,12321 计算出10000
    int help = 1;
    while(x/help>=10){
        help*=10;
    }
    while(x!=0) {
        //x/help计算第一个位置 x%10计算最后一个位置
        if (x / help != x % 10) {
            return false;
        }
        //x%help/10 12321->232，因为少了两位，所以help/100
        x = x%help/10;
        help/=100;
    }
    return true;
}

未排序正数数组中累加和为定值的最长子数组长度

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
37
38
/**
     * 未排序正数数组中累加和为定值的最长子数组长度
     * 准备两个指针，left以及right，以sum表示left以及right之间的数值和。
     * 假如sum<k，则right后移；
     * sum==k，记录下长度，并将left左移；
     * sum>k，left直接左移
     * */

public int getMaxLength(int[] nums,int k) {
    if (nums == null || nums.length == 0 || k <= 0) {
        return 0;
    }
    int left = 0;
    int right = 0;
    int sum = 0;
    int maxLength = 0;
    while (right < nums.length) {
        //假如sum<k，说明不够长，还需要加元素，right往右移
        if (sum < k) {
            right++;
            //注意下标越界判断
            if(right==nums.length){
                break;
            }
            sum += nums[right];
            //sum==k，记录长度，太满了，缩小长度，将left右移
        } else if (sum == k) {
            maxLength = Math.max(maxLength, right - left + 1);
            sum -= nums[left];
            left++;
            //sum>k，太满了，left右移
        } else {
            sum -= nums[left];
            left++;
        }
    }
    return maxLength;
}

未排序整数数组中累加和为定值的最长子数组长度

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
/**
     * 未排序整数数组中累加和为定值的最长子数组长度，可为正，负，0
     * sum用来记录从0到i的子数组之和，使用map存储所有出现的sum值以及位置
     * 在map中查找sum-k，假如存在，那么i与该位置之间就是满足的子数组，与最值比较
     * 假如sum-k不存在，那么以nums[i]结尾的情况下没有累加和为k的子数组
     * */
public int subarraySum(int[] nums, int k) {
    if(nums==null||nums.length==0){
        return 0;
    }
    int sum = 0;
    int max = 0;
    int count = 0;
    //存储sum值以及他第一次出现的位置
    Map<Integer,Integer> map = new HashMap<>();
    map.put(0,-1);
    for(int index=0;index<nums.length;index++){
        sum+=nums[index];
        if(map.containsKey(sum-k)){
            max = Math.max(max,index-map.get(sum-k));
        }
        if(!map.containsKey(sum)){
            map.put(sum,index);
        }
    }
    return max;
}

525. 连续数组

给定一个二进制数组, 找到含有相同数量的 0 和 1 的最长连续子数组（的长度）。

该题与上题类似，可以将0转化为-1，这样求解累加和是0的最长子数组长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int findMaxLength(int[] nums) {
       if(nums==null||nums.length==0){
           return 0;
       }
       //存储某个sum值以及第一次出现的位置
       Map<Integer,Integer> map = new HashMap<>();
       int sum = 0;
       int max = 0;
       map.put(0,-1);
       for(int i=0;i<nums.length;i++){
           sum+=nums[i]==0?-1:nums[i];
           if(map.containsKey(sum-0)){
               max = Math.max(max,i-map.get(sum-0));
           }
           if(!map.containsKey(sum)){
               map.put(sum,i);
           }
       }
       return max;
}

560. 和为K的子数组

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
     * 整数数组，依旧使用sum-k的方式
     * */
public int subarraySum2(int[] nums, int k) {
    if(nums==null||nums.length==0){
        return 0;
    }
    int sum = 0;
    int count = 0;
    //map中存储的是某个sum值出现的次数
    Map<Integer,Integer> map = new HashMap<>();
    //初始0值出现了一次
    map.put(0,1);
    for(int index=0;index<nums.length;index++){
        sum+=nums[index];
        if(map.containsKey(sum-k)){
            count+=map.get(sum-k);
        }
        //存储sum出现的次数，假如map中已经存在，直接++，未存在，直接存储1
        map.put(sum,map.getOrDefault(sum,0)+1);
    }
    return count;
}

未排序数组中累加和小于或等于给定值的最长子数组长度

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
public int maxLength(int[] arr,int k){
    //计算以i结尾的最小子数组长度
    int[] minSums = new int[arr.length];
    int[] minEnds = new int[arr.length];
    minSums[arr.length-1] = minSums[arr.length-1];
    minEnds[arr.length-1] = arr.length-1;
    for(int i=arr.length-2;i>=0;i--){
        if(minSums[i+1]<0){
            minSums[i] = minSums[i+1]+arr[i];
            minEnds[i] = minEnds[i+1];
        }else{
            minSums[i] = arr[i];
            minEnds[i] = i;
        }
    }
    //扩展窗口,end是窗口最右位置的下一个位置，i是窗口的左侧
    int sum = 0;
    int end = 0;
    int max = 0;
    for(int i=0;i<arr.length;i++){
        //将窗口向右扩，直到>k
        while(end<arr.length&&sum+minSums[end]<=k){
            sum+=minSums[end];
            end = minEnds[end]+1;
        }
        //扩充到不能再扩了，形成了一个结果
        max = Math.max(max,end-i);
        //移动左侧位置
        if(end>i){
            sum-=arr[i];
        }else{
            end = i+1;
        }
    }
    return max;
}

约瑟夫环问题