Others - nihaogxx/AlgorithmNotes GitHub Wiki
418. Sentence Screen Fitting Medium
Given a rows x cols screen and a sentence represented by a list of non-empty 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 is greater than 0 and 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.
Method1: Time O(rows * lenOfLongestWord) - Space O(number of characters in the reformatted sentence) = O(number of words * lenOfLongestWord)
1- keep track of the number of characters so far fitted on the screen
2- for each row, assume filling the entire row.
3- get the index in the reformatted sentence at which the current row ends at
4- if it ends in the middle of a word, recede till it reaches a space.
5- if ends at the end of a word, advance by one to take in the following space, which doesn't take space if it's at the end of the row.
Code:
public int wordsTyping(String[] sentence, int rows, int cols) {
String str = "";
for (String s : sentence){
str += s;
str += " ";
}
int len = str.length();
int count = 0; // how many characters are there in the screen so far
for (int i = 0; i < rows; i++){
count += cols; // fill the entire row first
int nextIndex = count % len;
if (str.charAt(nextIndex) == ' ') {
count++;
} else {
while (count > 0 && str.charAt((count-1)%len) != ' ') {
count--;
}
}
}
return count/len; // total number of characters/length of the built sentence (string with spaces).
}
Method2: dp Time O(numberOfWord * cols) - Space O(numberOfWords)
先算出来句子中每一个单词作为开头的时候，每行能装几个单词。因为不管怎么变，总有一个单词会顶头。然后遍历每一行算出来总共能塞多少个单词进去，除以句子的单词数就是一共能塞下多少个句子了。
Code:
class Solution { public int wordsTyping(String[] sentence, int rows, int cols) {
int n = sentence.length;
int[] wordLens = new int[n];// the length of each word
int[] dp = new int[n]; //how many words can fit in one row starting at each word
for (int i = 0; i < n; i++){ //O(n)
wordLens[i] = sentence[i].length();
}
for (int i = 0; i < n; i++){ // O(n)
dp[i] = wordCountForRow(wordLens, i, cols);
}
int count = 0;
int startIndex = 0;
for (int i = 0; i < rows; i++){ // O(rows)
count += dp[startIndex];
startIndex += dp[startIndex];
startIndex %= n;
}
return count/n; // total number of words/length of the String[]
}
public int wordCountForRow(int[] wordLens, int start, int cols){ // O(cols/lenOfShortestWord) = O(cols)
int curLen = 0;
int i = start;
int res = 0; // number of words
while (curLen < cols){
curLen += wordLens[i];
if (curLen > cols){
return res;
}
curLen++; // space
i++;
res++;
if (i == wordLens.length) {
i = 0;
}
}
return res;
}
}
54. Spiral Matrix Medium
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
Example 1:
Input:
[ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ]
Output: [1,2,3,6,9,8,7,4,5] Example 2:
Input:
[ [1, 2, 3, 4], [5, 6, 7, 8], [9,10,11,12] ]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]
Method:
Time Complexity: O(N), where N is the total number of elements in the input matrix. We add every element in the matrix to our final answer.
Space Complexity: O(N), the information stored in seen and in ans.
Intuition
Draw the path that the spiral makes. We know that the path should turn clockwise whenever it would go out of bounds or into a cell that was previously visited.
Algorithm
Let the array have \text{R}R rows and \text{C}C columns. \text{seen[r][c]}seen[r][c] denotes that the cell on the\text{r}r-th row and \text{c}c-th column was previously visited. Our current position is \text{(r, c)}(r, c), facing direction \text{di}di, and we want to visit \text{R}R x \text{C}C total cells.
As we move through the matrix, our candidate next position is \text{(cr, cc)}(cr, cc). If the candidate is in the bounds of the matrix and unseen, then it becomes our next position; otherwise, our next position is the one after performing a clockwise turn.
Code:
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> res = new ArrayList<>();
if (matrix == null || matrix.length == 0) return res;
int R = matrix.length;
int C = matrix[0].length;
boolean[][] visited = new boolean[R][C];
int[] dirR = {0, 1, 0, -1}; // right, down, left, up
int[] dirC = {1, 0, -1, 0}; // right, down, left, up
int r = 0, c = 0, dir = 0; // dir = 0,1,2,3 which are the indexes in dirR and dirC
for (int i = 0; i < R * C; i++){ // O(R*C) break when every node is visited
visited[r][c] = true;
res.add(matrix[r][c]);
int canR = r + dirR[dir]; // candidate
int canC = c + dirC[dir]; // camdidate
if (canR >=0 && canR < R && canC >= 0 && canC < C && !visited[canR][canC]){
r = canR;
c = canC;
}
else {
dir = (dir+1)%4; // turn clockwise
r += dirR[dir];
c += dirC[dir];
}
}
return res;
}
59. Spiral Matrix II Medium
Given a positive integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
Example:
Input: 3 Output: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]
Code:
public int[][] generateMatrix(int n) {
if (n == 1) return new int[][] {{1}};
int[][] res = new int[n][n];
int[] dirR = {0, 1, 0, -1};
int[] dirC = {1, 0, -1, 0};
int r = 0, c = 0, dir = 0;
for (int i = 1; i <= Math.pow(n, 2); i++){
res[r][c] = i;
int candR = r + dirR[dir];
int candC = c + dirC[dir];
if (candR >= 0 && candR < n && candC >= 0 && candC < n && res[candR][candC] == 0){
r = candR;
c = candC;
}
else {
dir = (dir + 1) % 4;
r += dirR[dir];
c += dirC[dir];
}
}
return res;
}
- Partition to K Equal Sum Subsets Medium
Given an array of integers nums and a positive integer k, find whether it's possible to divide this array into k non-empty subsets whose sums are all equal.
Example 1:
Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4 Output: True Explanation: It's possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.
Note:
1 <= k <= len(nums) <= 16. 0 < nums[i] < 10000.
Code: Time O(k^n) cuz for each number there are k buckets to try. Space O(k) if not consider space for stack on recursive calls, otherwise O(n+k)
class Solution {
public boolean canPartitionKSubsets(int[] nums, int k) {
int sum = getSum(nums);
if (sum % k != 0){
return false;
}
int target = sum / k;
Arrays.sort(nums);
int begin = nums.length - 1;
if (nums[begin] > target) return false;
while (nums[begin] == target){ // itself alone is a subset
begin--;
k--;
}
return partition(nums, new int[k], begin, target);
}
public boolean partition(int[] nums, int[] buckets, int begin, int target){
// every number has fit in
if (begin < 0) return true;
int cur = nums[begin];
for (int i = 0; i < buckets.length; i++){
if (buckets[i] + cur <= target){
buckets[i] += cur;
// check if the rest elements can fit in with the cur number in cur bucket
if (partition(nums, buckets, begin-1, target)) {
return true;
}
buckets[i] -= cur;// backtrack to the prev state
}
}
return false;
}
public int getSum(int[] nums){
int res = 0;
for (int i : nums){
res += i;
}
return res;
}
}