题目序号 418、416、413、392、377、376、375、368、361、357¶
418. Sentence Screen Fitting¶
Given a rows x cols screen and a sentence represented by a list of words, find how many times the given sentence can be fitted on the screen.
Note:
A word cannot be split into two lines. The order of words in the sentence must remain unchanged. Two consecutive words in a line must be separated by a single space. Total words in the sentence won’t exceed 100. Length of each word won’t exceed 10. 1 ≤ rows, cols ≤ 20,000.
Example 1:
Input: rows = 2, cols = 8, sentence = [“hello”, “world”]
Output: 1
Explanation: hello— world—
The character ‘-‘ signifies an empty space on the screen.
Example 2:
Input: rows = 3, cols = 6, sentence = [“a”, “bcd”, “e”]
Output: 2
Explanation: a-bcd- e-a— bcd-e-
The character ‘-‘ signifies an empty space on the screen.
Example 3:
Input: rows = 4, cols = 5, sentence = [“I”, “had”, “apple”, “pie”]
Output: 1
Explanation: I-had apple pie-I had–
The character ‘-‘ signifies an empty space on the screen.
题目大意：
给定一个rows x cols屏幕与一列单词表示的句子，计算屏幕中可以展示多少次完整的句子。
注意：
单词不能拆成两行 单词在句子中的顺序不能调换 两个相邻单词之间必须有一个空格隔开 句子的总单词数不超过100 每个单词的长度不超过10 1 ≤ rows, cols ≤ 20,000.
解题思路：
由于rows和cols的规模可以达到20000，因此朴素的解法会超时（Time Limit Exceeded）
观察测试用例3可以发现，当句子在屏幕上重复展现时，会呈现周期性的规律：
I-had apple pie-I had– apple pie-I had– apple
上例中apple单词的相对位置从第二行开始循环，因此只需要找到单词相对位置的“循环节”，即可将问题简化。
利用字典dp记录循环节的起始位置，具体记录方式为：dp[(pc, pw)] = pr, ans
以数对(pc, pw)为键，其中pw为单词在句子中出现时的下标，pc为单词出现在屏幕上的列数
以数对(pr, ans)为值，其中pr为单词出现在屏幕上的行数，ans为此时已经出现过的完整句子数
416. Partition Equal Subset Sum¶
Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.
Note:
Each of the array element will not exceed 100. The array size will not exceed 200.
Example 1:
Input: [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
Example 2:
Input: [1, 2, 3, 5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.
413. Arithmetic Slices¶
A sequence of number is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.
For example, these are arithmetic sequence:
1, 3, 5, 7, 9 7, 7, 7, 7 3, -1, -5, -9
The following sequence is not arithmetic.
1, 1, 2, 5, 7
A zero-indexed array A consisting of N numbers is given. A slice of that array is any pair of integers (P, Q) such that 0 <= P < Q < N.
A slice (P, Q) of array A is called arithmetic if the sequence: A[P], A[p + 1], …, A[Q - 1], A[Q] is arithmetic. In particular, this means that P + 1 < Q.
The function should return the number of arithmetic slices in the array A.
Example:
A = [1, 2, 3, 4]
return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.
392. Is Subsequence¶
Given a string s and a string t, check if s is subsequence of t.
You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and s is a short string (<=100).
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ace” is a subsequence of “abcde” while “aec” is not).
Example 1: s = “abc”, t = “ahbgdc”
Return true.
Example 2: s = “axc”, t = “ahbgdc”
Return false.
Follow up: If there are lots of incoming S, say S1, S2, … , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?
Credits: Special thanks to @pbrother for adding this problem and creating all test cases.
377. Combination Sum IV¶
Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.
Example:
nums = [1, 2, 3] target = 4
The possible combination ways are: (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1)
Note that different sequences are counted as different combinations.
Therefore the output is 7.
Follow up: What if negative numbers are allowed in the given array? How does it change the problem? What limitation we need to add to the question to allow negative numbers?
Credits: Special thanks to @pbrother for adding this problem and creating all test cases.
376. Wiggle Subsequence¶
A sequence of numbers is called a wiggle sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence.
For example, [1,7,4,9,2,5] is a wiggle sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, [1,4,7,2,5] and [1,7,4,5,5] are not wiggle sequences, the first because its first two differences are positive and the second because its last difference is zero.
Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence. A subsequence is obtained by deleting some number of elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.
Examples:
Input: [1,7,4,9,2,5] Output: 6 The entire sequence is a wiggle sequence.
Input: [1,17,5,10,13,15,10,5,16,8] Output: 7 There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].
Input: [1,2,3,4,5,6,7,8,9] Output: 2
Follow up: Can you do it in O(n) time?
Credits: Special thanks to @agave and @StefanPochmann for adding this problem and creating all test cases.
375. Guess Number Higher or Lower II¶
We are playing the Guess Game. The game is as follows:
I pick a number from 1 to n. You have to guess which number I picked.
Every time you guess wrong, I’ll tell you whether the number I picked is higher or lower.
However, when you guess a particular number x, and you guess wrong, you pay $x. You win the game when you guess the number I picked.
Example:
n = 10, I pick 8.
First round: You guess 5, I tell you that it’s higher. You pay $5. Second round: You guess 7, I tell you that it’s higher. You pay $7. Third round: You guess 9, I tell you that it’s lower. You pay $9.
Game over. 8 is the number I picked.
You end up paying $5 + $7 + $9 = $21.
Given a particular n ≥ 1, find out how much money you need to have to guarantee a win.
Credits: Special thanks to @agave and @StefanPochmann for adding this problem and creating all test cases.
368. Largest Divisible Subset¶
Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0.
If there are multiple solutions, return any subset is fine.
Example 1:
nums: [1,2,3]
Result: [1,2] (of course, [1,3] will also be ok)
Example 2:
nums: [1,2,4,8]
Result: [1,2,4,8]
Credits: Special thanks to @Stomach_ache for adding this problem and creating all test cases.
361. Bomb Enemy¶
Given a 2D grid, each cell is either a wall ‘W’, an enemy ‘E’ or empty ‘0’ (the number zero), return the maximum enemies you can kill using one bomb. The bomb kills all the enemies in the same row and column from the planted point until it hits the wall since the wall is too strong to be destroyed. Note that you can only put the bomb at an empty cell.
Example:
For the given grid
0 E 0 0 E 0 W E 0 E 0 0
return 3. (Placing a bomb at (1,1) kills 3 enemies)
Credits: Special thanks to @memoryless for adding this problem and creating all test cases.
357. Count Numbers with Unique Digits¶
Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10n.
Example: Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding [11,22,33,44,55,66,77,88,99])
Credits: Special thanks to @memoryless for adding this problem and creating all test cases.