Question

A decimal number is called deci-binary if each of its digits is either 0 or 1 without any leading zeros. For example, 101 and 1100 are deci-binary, while 112 and 3001 are not.

Given a string n that represents a positive decimal integer, return the minimum number of positive deci-binary numbers needed so that they sum up to n.

Solution

遍历所有字符，返回字符串中的最大整数。

Code

1
2
3
4
5
6
7
8
9

class Solution {
    public int minPartitions(String n) {
        char max = '0';
        for(char s : n.toCharArray()){
            if(s > max) max = s;
        }
        return max - '0';
    }
}

Question

You are given two 0-indexed integer arrays nums1 and nums2, both of length n.

You can choose two integers left and right where 0 <= left <= right < n and swap the subarray nums1[left...right] with the subarray nums2[left...right].

• For example, if nums1 = [1,2,3,4,5] and nums2 = [11,12,13,14,15] and you choose left = 1 and right = 2, nums1 becomes [1,<strong><u>12,13</u></strong>,4,5] and nums2 becomes [11,<strong><u>2,3</u></strong>,14,15].

You may choose to apply the mentioned operation once or not do anything.

The score of the arrays is the maximum of sum(nums1) and sum(nums2), where sum(arr) is the sum of all the elements in the array arr.

Return the maximum possible score.

A subarray is a contiguous sequence of elements within an array. arr[left...right] denotes the subarray that contains the elements of nums between indices left and right (inclusive).

Solution

滑动窗口。一开始想用dp解决的。
后来发现可以优化到直接记录连续的最大差值即可。
以后有提到连续的一定要想到滑动窗口实现。

辅助方法getMinContigouousDiff()用来计算两个数组间连续的最小的差值和。
当sum为负数时，窗口向右侧扩展，将新的位置加入sum，并更新最小值min。
当扩展后sum大于0时，则放弃之前的所有元素，将sum归零。
最后返回最小值min。

计算两个数组的所有数字之和t1和t2。分别计算nums1[]和nums2[]的差min1和nums2[]和nums1[]的差min2。
在其中替换连续的部分则为t1-min1，t2-min2。取两者中较大的数字返回即可。

Code

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

class Solution {
    public int maximumsSplicedArray(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int t1 = 0, t2 = 0;
        for(int i = 0; i < n ;i++){ //计算两个数组未替换前的和
            t1 += nums1[i];
            t2 += nums2[i];
        }
        int min1 = getMinContiguousDiff(nums2, nums1);
        int min2 = getMinContiguousDiff(nums1, nums2);
        return Math.max(t1 - min1, t2 - min2);  //替换连续的部分，两者中取最大值
    }
    
    private int getMinContiguousDiff(int[] nums1, int[] nums2){ //滑动窗口，求连续元素间的最小差值
        int sum = 0, min = 0;
        for(int i = 0; i < nums1.length; i++){
            if(sum <= 0){   //当sum为负数时，窗口向右侧扩展，将新的位置加入sum
                int diff = nums2[i] - nums1[i];
                sum += diff;
                if(diff < 0) min = Math.min(min, sum);  //更新最小值
                if(sum > 0) sum = 0;    //当sum为正数时，抛弃前面的元素，重新开始计算sum
            }
        }
        return min;
    }
}

Question

There is a street with n * 2 plots, where there are n plots on each side of the street. The plots on each side are numbered from 1 to n. On each plot, a house can be placed.

Return the number of ways houses can be placed such that no two houses are adjacent to each other on the same side of the street. Since the answer may be very large, return it modulo 10<sup>9</sup><span> </span>+ 7.

Note that if a house is placed on the i<sup>th</sup> plot on one side of the street, a house can also be placed on the i<sup>th</sup> plot on the other side of the street.

Solution

计算单侧河道可以放置的种类。
一开始用的是DFS搜素来计算可以放置的种类。
计算后发现是以（2，3）开始的斐波那契数列。

因此直接计算n位置的斐波那契数列值即可。
然后两边可以匹配的种类就是其平方。

记忆化搜索

在计算斐波那契数列时，由于要多次重复计算前面的位置，因此可以采用记忆化搜索记录对应的斐波那契额值。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
    long[] memo;
    public int countHousePlacements(int n) {
        memo = new long[n+1];
        long res = fibo(n);
        res *= res;
        res %= 1000000007;
        return (int) res;
    }
    
    private long fibo(int n){
        if(n == 1) return 2;
        else if(n == 2) return 3;
        if(memo[n] != 0) return memo[n];
        memo[n] = fibo(n-1) % 1000000007 + fibo(n-2) % 1000000007;

        return memo[n];
    }
}

Question

A square matrix is said to be an X-Matrix if both of the following conditions hold:

1. All the elements in the diagonals of the matrix are non-zero.
2. All other elements are 0.

Given a 2D integer array grid of size n x n representing a square matrix, return true* if grid is an X-Matrix*. Otherwise, return false.

Solution

遍历，直接判断是否在对角线上，如果在且位置为0，则返回false。
如果不在对角线上，且位置部位0，则返回false。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
    public boolean checkXMatrix(int[][] grid) {
        int n = grid.length;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(i == j || i + j == n - 1){
                    if(grid[i][j] == 0) return false;
                }
                else if(grid[i][j] != 0) return false;
            }
        }
        return true;
    }
}

Question

There are several cards arranged in a row, and each card has an associated number of points. The points are given in the integer array cardPoints.

In one step, you can take one card from the beginning or from the end of the row. You have to take exactly k cards.

Your score is the sum of the points of the cards you have taken.

Given the integer array cardPoints and the integer k, return the maximum score you can obtain.

Solution 1

这种取两端的问题可以转化为取中间连续k个元素之和最小。

计算所有数字的和sum。
然后用维护一个宽度为k的窗口内的加和temp，并记录其最小值min。

返回sum - min，结果即是取两侧时可以取的最大值。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length, sum = 0;
        for(int point : cardPoints) sum += point; //求所有数值的和
        if(k == n) return sum;
        int left = 0, right = n-k, temp = 0, min = 0;
        
        for(int i = 0; i < n-k; i++){
            temp += cardPoints[i];
            min = temp;
        }
        while(right < n){   //维护窗口内的temp，并更新min
            temp += cardPoints[right] - cardPoints[left];; 
            min = Math.min(min, temp);
            right++;
            left++;
        }
        return sum - min;
    }
}

Solution 2

分别计算从两侧开始的加和并记录在两个数组left[]和right[]上。

然后分别取两个指针，左侧指针l从0开始遍历到k，右侧指针对应的位置为l+n-k。计算并更新最大值max。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length, max = 0;
        int[] left = new int[n+1], right = new int[n+1];
        
        for(int i = 0; i < n; i++){
            left[i+1] = left[i] + cardPoints[i];
            right[n-i-1] = right[n-i] + cardPoints[n-i-1];
        }
        
        for(int l = 0; l <= k; l++){
            max = Math.max(max, left[l] + right[n-k+l]);
        }
        
        return max;
    }
}