发表于 | 分类于

Given an array with n integers, you need to find if there are triplets (i, j, k) which satisfies following conditions:

0 < i, i + 1 < j, j + 1 < k < n - 1
Sum of subarrays (0, i - 1), (i + 1, j - 1), (j + 1, k - 1) and (k + 1, n - 1) should be equal.

where we define that subarray (L, R) represents a slice of the original array starting from the element indexed L to the element indexed R.

Example:

1
2
3
4
5
6
7
8
Input: [1,2,1,2,1,2,1]
Output: True
Explanation:
i = 1, j = 3, k = 5.
sum(0, i - 1) = sum(0, 0) = 1
sum(i + 1, j - 1) = sum(2, 2) = 1
sum(j + 1, k - 1) = sum(4, 4) = 1
sum(k + 1, n - 1) = sum(6, 6) = 1

Note:

1 <= n <= 2000.
Elements in the given array will be in range [-1,000,000, 1,000,000].

解法1：

这题又是2sum的一个变种。把一个数组分成加和相等的4份。trick在于如果遍历中间的点，那么左右那边变成找出是否存在切割点使得切割之后的两份的加和相等。
那么这一部分就可以用hashset来解决。存储可以等分的sum，然后在右边的部分寻找等分的时候看是否在左面出现过。
C++

1

Java

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
public class Solution {
    public boolean splitArray(int[] nums) {
        if (nums.length <= 6) {
            return false;
        }
        int[] sum = new int[nums.length];
        sum[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            sum[i] = sum[i - 1] + nums[i];
        }
        for (int j = 3; j < nums.length - 3; j++) {
            HashSet<Integer> set = new HashSet<Integer>();
            for (int i = 1; i < j - 1; i++) {
                if (sum[i - 1] == sum[j - 1] - sum[i]) {
                    set.add(sum[i - 1]);
                }
            }
            for (int k = j + 2; k < nums.length - 1; k++) {
                if (sum[k - 1] - sum[j] == sum[nums.length - 1] - sum[k] && set.contains(sum[k - 1] - sum[j])) {
                    return true;
            }
        }
        }
        return false;
    }
}

发表于 | 分类于

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1:

Input:nums = [1,1,1], k = 2
Output: 2

Note:

The length of the array is in range [1, 20,000].
The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

解法1：O(N) Time + O(N) Space

这题和2Sum的思路有点像。首先是一道continuous sum的题，可以考虑用prefix sum的办法。
每次计算一个累加和，假设为sum，sum-presum=k也就意味着，sum-k=presum,如果我们用一个hashtable存储每一个presum出现的次数，那就可以指导对于任意一个sum，其满足要求的presum是否出现过，并且出现过几次。这一点和2sum是一样的，只是一个用加法一个用减法。
C++

1

Java

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
public class Solution {
    public int subarraySum(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int sum = 0;
        int cnt = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (sum == k) {
                cnt++;
            }
            if (map.containsKey(sum - k)) {
                cnt += map.get(sum - k);
            }
            if (map.containsKey(sum)) {
                map.put(sum, map.get(sum) + 1);
            } else {
                map.put(sum, 1);
            }
        }
        return cnt;
    }
}

发表于 | 分类于

Given an integer array, find three numbers whose product is maximum and output the maximum product.

Example 1:

1
2
Input: [1,2,3]
Output: 6

Example 2:

1
2
Input: [1,2,3,4]
Output: 24

Note:

The length of the given array will be in range [3,104] and all elements are in the range [-1000, 1000].
Multiplication of any three numbers in the input won't exceed the range of 32-bit signed integer.

解法1：

这题用3Sum smaller的思路，不过是简化了的版本。每对应一个数字，只需要考虑如果是负数时最小的乘积和如果是正数时最大的乘积。
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    public int maximumProduct(int[] nums) {
        if (nums.length == 0 ) {
            return 0;
        }
        Arrays.sort(nums);  // sort ascending
        int res = Integer.MIN_VALUE;
        int n = nums.length;
        for (int i = 0; i < nums.length - 2; i++) {
            if (nums[i] < 0) {
                res = Math.max(res, nums[i] * nums[i + 1] * nums[n - 1]);
            } else if (nums[i] > 0) {
                res = Math.max(res, nums[n - 1] * nums[n - 2] * nums[i]);
            } else {
                res = Math.max(res, 0);
            }
        }
        return res;
    }
}

发表于 | 分类于

Given a 01 matrix M, find the longest line of consecutive one in the matrix. The line could be horizontal, vertical, diagonal or anti-diagonal.

Example:

Input:
[[0,1,1,0],
[0,1,1,0],
[0,0,0,1]]
Output: 3

Hint: The number of elements in the given matrix will not exceed 10,000.

解法1：DP, O(nm)

用一个三维数组记录每一个格子上4个方向的最长的个数。同时更新一下最长的值即可。
C++

1

Java

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
39
40
41
42
43
44
45
46
47
48
49
50
51
public class Solution {
    public int longestLine(int[][] M) {
        if (M.length == 0 || M[0].length == 0) {
            return 0;
        }
        int[][][] dp = new int[M.length][M[0].length][4];
        if (M[0][0] == 1) {
            for (int i = 0; i < 4; i++) {
                dp[0][0][i] = 1;
            }
        }
        int res = 0;
        for (int i = 0; i < M.length; i++) {
            for (int j = 0; j < M[0].length; j++) {
                if (M[i][j] == 0) {
                    continue;
                }
                for (int k = 0; k < 4; k++) {
                    dp[i][j][k] = 1;
                }
                // vertical line
                if (i > 0) {
                    dp[i][j][0] = dp[i - 1][j][0] + 1;
                }
                // horizontal line
                if (j > 0) {
                    dp[i][j][1] = dp[i][j - 1][1] + 1;
                }
                // diagonal line
                if (i > 0 && j < M[0].length - 1) {
                    dp[i][j][3] = dp[i - 1][j + 1][3] + 1;
                }
                // anti diagonal line
                if (i > 0 && j > 0) {
                    dp[i][j][2] = dp[i - 1][j - 1][2] + 1;
                }
                res = Math.max(res, Math.max(dp[i][j][0], dp[i][j][1]));
                res = Math.max(res, Math.max(dp[i][j][2], dp[i][j][3]));
            }
        }
        return res;
    }
}

发表于 | 分类于

A zero-indexed array A consisting of N different integers is given. The array contains all integers in the range [0, N - 1].

Sets S[K] for 0 <= K < N are defined as follows:

S[K] = { A[K], A[A[K]], A[A[A[K]]], … }.

Sets S[K] are finite for each K and should NOT contain duplicates.

Write a function that given an array A consisting of N integers, return the size of the largest set S[K] for this array.

Example 1:

1
2
3
4
5
6
7
Input: A = [5,4,0,3,1,6,2]
Output: 4
Explanation:
A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.
One of the longest S[K]:
S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}

Note:

N is an integer within the range [1, 20,000].
The elements of A are all distinct.
Each element of array A is an integer within the range [0, N-1].

解法1： O(N) Time + O(N) Space

用DFS的思想，同时记录所访问过的元素。对于每一个未被访问过的元素跑一遍DFS，直到碰到已经访问过的元素位置，同时更新一下最大的值。
C++

1

Java

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
public class Solution {
    public int arrayNesting(int[] nums) {
        // union find
        if (nums == null || nums.length == 0) {
            return 0;
        }
        boolean[] visited = new boolean[nums.length];
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int cnt = 0;
            int current = i;
            while (!visited[current]) {
                cnt++;
                visited[current] = true;
                current = nums[current];
            }
            res = Math.max(res, cnt);
        }
        return res;
    }
}

发表于 | 分类于

Given an array consists of non-negative integers, your task is to count the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.

Example 1:

1
2
3
4
5
6
7
Input: [2,2,3,4]
Output: 3
Explanation:
Valid combinations are:
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3

Note:

The length of the given array won't exceed 1000.
The integers in the given array are in the range of [0, 1000].

解法1：O(N^2)

这题的思路和3SUM smaller很像，也可以用O(N^2)解决。
首先要确定，满足一个三角形的条件是任意两条边之和要大于第三条边。那么如果先对数组排序。
如果AC, 另外两个条件一定也满足。
用3sum smaller的算法是先固定一个点。这题里面我们固定住最大的边比较好想
从后往前扫描，用双指针指向最小的两条边。如果left + right > 第三边,那么从left 到right的所有边都可以满足[right, last]这个组合。

C++

1

Java

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
public class Solution {
    public int triangleNumber(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        Arrays.sort(nums);
        int res = 0;
        if (nums.length < 3) {
            return res;
        }
        int n = nums.length;
        for (int i = n - 1; i >= 2; i--) {
            int left = 0, right = i - 1;
            while (left < right) {
                if (nums[left] + nums[right] > nums[i]) {
                    res += right - left;
                    right--;
                } else {
                    left++;
                }
            }
        }
        return res;
    }
}

发表于 | 分类于

Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks.Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle.

However, there is a non-negative cooling interval n that means between two same tasks, there must be at least n intervals that CPU are doing different tasks or just be idle.

You need to return the least number of intervals the CPU will take to finish all the given tasks.

Example 1:

Input: tasks = [‘A’,’A’,’A’,’B’,’B’,’B’], n = 2
Output: 8
Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.

Note:

The number of tasks is in the range [1, 10000].
The integer n is in the range [0, 100].

解法1：

先找出出现频率最大的数字，假设频率为k。然后分开每一个数字使得两个数字之间间隔为n。
这样，会有k-1个间隔出现。所有频率小于k的数字都可以完全填充在这k-1个间隔里面。
那么，这个时候总长度就是：(k - 1) * (n + 1) + 频率为k的数字的个数。
（n+1)是因为每一个分段都是一个最高频的数字加上剩下的空， i.e. AXXXXXXXXX
C++

1

Java

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
public class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] map = new int[26];
        for (char task: tasks) {
            map[task - 'A']++;
        }
        Arrays.sort(map);
        int maxFreq = map[25];
        int t = 0;
        for (int i = map.length - 1; i >= 0; i--) {
            if (map[i] == maxFreq) {
                t++;
            } else {
                break;
            }
        }
        return Math.max(tasks.length, (maxFreq - 1) * (n + 1) + t);
    }
}

发表于 | 分类于

In LLP world, there is a hero called Teemo and his attacking can make his enemy Ashe be in poisoned condition. Now, given the Teemo’s attacking ascending time series towards Ashe and the poisoning time duration per Teemo’s attacking, you need to output the total time that Ashe is in poisoned condition.

You may assume that Teemo attacks at the very beginning of a specific time point, and makes Ashe be in poisoned condition immediately.

Example 1:

1
2
3
4
5
6
Input: [1,4], 2
Output: 4
Explanation: At time point 1, Teemo starts attacking Ashe and makes Ashe be poisoned immediately.
This poisoned status will last 2 seconds until the end of time point 2.
And at time point 4, Teemo attacks Ashe again, and causes Ashe to be in poisoned status for another 2 seconds.
So you finally need to output 4.

Example 2:

1
2
3
4
5
6
7
Input: [1,2], 2
Output: 3
Explanation: At time point 1, Teemo starts attacking Ashe and makes Ashe be poisoned.
This poisoned status will last 2 seconds until the end of time point 2.
However, at the beginning of time point 2, Teemo attacks Ashe again who is already in poisoned status.
Since the poisoned status won't add up together, though the second poisoning attack will still work at time point 2, it will stop at the end of time point 3.
So you finally need to output 3.

Note:

You may assume the length of given time series array won’t exceed 10000.
You may assume the numbers in the Teemo’s attacking time series and his poisoning time duration per attacking are non-negative integers, which won’t exceed 10,000,000.

解法1： Greedy

关键点在于： 两次攻击的间隔如果小于duration，那么上一次攻击的有效时间就是间隔时间。
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public int findPoisonedDuration(int[] timeSeries, int duration) {
       int res = 0;
       if (timeSeries.length == 0 || duration == 0) {
           return res;
       }
       for (int i = 1; i < timeSeries.length; i++) {
           int diff = timeSeries[i] - timeSeries[i - 1];
           if (diff < duration) {
               res += diff;
           } else {
               res += duration;
           }
       }
       // Add the last piece
       res += duration;
       return res;
    }
}

发表于 | 分类于

Assume you have an array of length n initialized with all 0’s and are given k update operations.

Each operation is represented as a triplet: [startIndex, endIndex, inc] which increments each element of subarray A[startIndex … endIndex] (startIndex and endIndex inclusive) with inc.

Return the modified array after all k operations were executed.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
Given:
    length = 5,
    updates = [
        [1,  3,  2],
        [2,  4,  3],
        [0,  2, -2]
    ]
Output:
    [-2, 0, 3, 5, 3]

Explanation:

1
2
3
4
5
6
7
8
9
10
11
Initial state:
[ 0, 0, 0, 0, 0 ]
After applying operation [1, 3, 2]:
[ 0, 2, 2, 2, 0 ]
After applying operation [2, 4, 3]:
[ 0, 2, 5, 5, 3 ]
After applying operation [0, 2, -2]:
[-2, 0, 3, 5, 3 ]

解法1： O(n) + O(k)

这题如果用一般的办法会TLE。关键的点在于不用更新start和end之间所有的数。那么我们只更新start的数，意思是从这往后所有的数都要加上start对应的数字。同时需要在end+1的地方减去increment，意思是从这里往后所有的数要减去start对应的数字，以此来抵消多加的那一份。
最后我们在遍历一遍数组，做一个累加就得到了结果。
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public int[] getModifiedArray(int length, int[][] updates) {
        if (length <= 0) {
            return new int[0];
        }
        int[] res = new int[length];
        for (int i = 0; i < updates.length; i++) {
            res[updates[i][0]] += updates[i][2];
            if (updates[i][1] < res.length - 1) {
                res[updates[i][1] + 1] -= updates[i][2];
            }
        }
        for (int i = 1; i < res.length; i++) {
            res[i] += res[i - 1];
        }
        return res;
    }
}

发表于 | 分类于

This is a follow up of Shortest Word Distance. The only difference is now word1 could be the same as word2.

Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

word1 and word2 may be the same and they represent two individual words in the list.

For example,
Assume that words = [“practice”, “makes”, “perfect”, “coding”, “makes”].

Given word1 = “makes”, word2 = “coding”, return 1.
Given word1 = “makes”, word2 = “makes”, return 3.

Note:
You may assume word1 and word2 are both in the list.

解法1：双指针

区别就是当word1和word2相同的时候，退化成只需要一个指针就可以了。在这种情况下，先判断之前是否出现过这个单词，如果出现过计算下当前的距离，然后更新上一次出现的位置。
C++

1

Java

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
public class Solution {
    public int shortestWordDistance(String[] words, String word1, String word2) {
        if (words.length == 0) {
            return 0;
        }
        int left = -1, right = -1;
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < words.length; i++) {
            if (words[i].equals(word1) && word1.equals(word2)) {
                if (left != -1) {
                    res = Math.min(res, i - left);    
                }
                left = i;
            } else if (words[i].equals(word1)) {
                left = i;
                if (right != -1) {
                    res = Math.min(res, left - right);
                }
            } else if (words[i].equals(word2)) {
                right = i;
                if (left != -1) {
                    res = Math.min(res, right - left);
                }
            }
        }
        return res;
    }
}