Given an array A of integers, return the number of (contiguous, non-empty) subarrays that have a sum divisible by K.
Example 1:
Input: A = [4,5,0,-2,-3,1], K = 5 Output: 7 Explanation: There are 7 subarrays with a sum divisible by K = 5: [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
Note:
1 <= A.length <= 30000
-10000 <= A[i] <= 10000
2 <= K <= 10000
Solution: Count prefix sums
let c[i] denotes the counts of prefix_sum % K init: c[0] = 1 Whenever we end up with the same prefix sum (after modulo), which means there are subarrys end with current element that is divisible by K (0 modulo).
e.g. A = [4,5,0,-2,-3,1], K = 5 [4,5] has prefix sum of 4, which happens at index 0 [4], and index 1, [4,5] [4,5,0] also has a prefix sum of 4, which means [4, {5,0}], [4,5, {0}] are divisible by K.
ans += (c[prefix_sum] – 1) i = 0, prefix_sum = 0, c[(0+4)%5] = c[4] = 1, ans = 0 i = 1, prefix_sum = 4+5, c[(4+5)%5] = c[4] = 2, ans = 0+2-1=0 => [5] i = 2, prefix_sum = 4+0, c[(4+0)%5] = c[4] = 3, ans = 1+3-1=3 => [5], [5,0], [0] i = 3, prefix_sum = 4-2, c[(4-2)%5] = c[2] = 1, ans = 3 i = 4, prefix_sum = 2-3, c[(2-3+5)%5] = c[4] = 4, ans = 3+4-1=6 => [5],[5,0],[0],[5,0,-2,-3], [0,-2,-3],[-2,-3] i = 5, prefix_sum = 4+1, c[(4+1)%5] = c[0] = 2, ans = 6 + 2 – 1 => [5],[5,0],[0],[5,0,-2,-3], [0,-2,-3],[-2,-3], [4,5,0,-2,-3,1]
You are given an integer array A. From some starting index, you can make a series of jumps. The (1st, 3rd, 5th, …) jumps in the series are called odd numbered jumps, and the (2nd, 4th, 6th, …) jumps in the series are called even numbered jumps.
You may from index i jump forward to index j (with i < j) in the following way:
During odd numbered jumps (ie. jumps 1, 3, 5, …), you jump to the index j such that A[i] <= A[j] and A[j] is the smallest possible value. If there are multiple such indexes j, you can only jump to the smallest such index j.
During even numbered jumps (ie. jumps 2, 4, 6, …), you jump to the index j such that A[i] >= A[j] and A[j] is the largest possible value. If there are multiple such indexes j, you can only jump to the smallest such index j.
(It may be the case that for some index i, there are no legal jumps.)
A starting index is good if, starting from that index, you can reach the end of the array (index A.length - 1) by jumping some number of times (possibly 0 or more than once.)
We are given an array A of N lowercase letter strings, all of the same length.
Now, we may choose any set of deletion indices, and for each string, we delete all the characters in those indices.
For example, if we have an array A = ["babca","bbazb"] and deletion indices {0, 1, 4}, then the final array after deletions is ["bc","az"].
Suppose we chose a set of deletion indices D such that after deletions, the final array has every element (row) in lexicographic order.
For clarity, A[0] is in lexicographic order (ie. A[0][0] <= A[0][1] <= ... <= A[0][A[0].length - 1]), A[1] is in lexicographic order (ie. A[1][0] <= A[1][1] <= ... <= A[1][A[1].length - 1]), and so on.
Return the minimum possible value of D.length.
Example 1:
Input: ["babca","bbazb"]
Output: 3
Explanation: After deleting columns 0, 1, and 4, the final array is A = ["bc", "az"].
Both these rows are individually in lexicographic order (ie. A[0][0] <= A[0][1] and A[1][0] <= A[1][1]).
Note that A[0] > A[1] - the array A isn't necessarily in lexicographic order.
Example 2:
Input: ["edcba"]
Output: 4
Explanation: If we delete less than 4 columns, the only row won't be lexicographically sorted.
Example 3:
Input: ["ghi","def","abc"]
Output: 0
Explanation: All rows are already lexicographically sorted.
Note:
1 <= A.length <= 100
1 <= A[i].length <= 100
Solution: DP
dp[i] := max length of increasing sub-sequence (of all strings) ends with i-th letter. dp[i] = max(dp[j] + 1) if all A[*][j] <= A[*][i], j < i Time complexity: (n*L^2) Space complexity: O(L)
You are installing a billboard and want it to have the largest height. The billboard will have two steel supports, one on each side. Each steel support must be an equal height.
You have a collection of rods which can be welded together. For example, if you have rods of lengths 1, 2, and 3, you can weld them together to make a support of length 6.
Return the largest possible height of your billboard installation. If you cannot support the billboard, return 0.
Example 1:
Input: [1,2,3,6]Output: 6Explanation: We have two disjoint subsets {1,2,3} and {6}, which have the same sum = 6.
Example 2:
Input: [1,2,3,4,5,6]Output: 10Explanation: We have two disjoint subsets {2,3,5} and {4,6}, which have the same sum = 10.
Example 3:
Input: [1,2]Output: 0Explanation: The billboard cannot be supported, so we return 0.
g[i][j] is the cost of appending word[j] after word[i], or weight of edge[i][j].
We would like find the shortest path to visit each node from 0 to n – 1 once and only once this is called the Travelling sells man’s problem which is NP-Complete.
We can solve it with DP that uses exponential time.
dp[s][i] := min distance to visit nodes (represented as a binary state s) once and only once and the path ends with node i.
e.g. dp[7][1] is the min distance to visit nodes (0, 1, 2) and ends with node 1, the possible paths could be (0, 2, 1), (2, 0, 1).
