Problems
- Number of Lines To Write String
- Unique Morse Code Words
- Max Increase to Keep City Skyline
- Split Array With Same Average
Ranking
Huahua's Tech Road
Problem
题目大意：给你每个字母的宽度，以及一个字符串。问一共需要多少行和多少列才能把这个字符串打印出来。将设每行的宽度是100。
We are to write the letters of a given string S, from left to right into lines. Each line has maximum width 100 units, and if writing a letter would cause the width of the line to exceed 100 units, it is written on the next line. We are given an array widths, an array where widths[0] is the width of ‘a’, widths[1] is the width of ‘b’, …, and widths[25] is the width of ‘z’.
Now answer two questions: how many lines have at least one character from S, and what is the width used by the last such line? Return your answer as an integer list of length 2.
Example : Input: widths = [10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10] S = "abcdefghijklmnopqrstuvwxyz" Output: [3, 60] Explanation: All letters have the same length of 10. To write all 26 letters, we need two full lines and one line with 60 units.
Example : Input: widths = [4,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10] S = "bbbcccdddaaa" Output: [2, 4] Explanation: All letters except 'a' have the same length of 10, and "bbbcccdddaa" will cover 9 * 10 + 2 * 4 = 98 units. For the last 'a', it is written on the second line because there is only 2 units left in the first line. So the answer is 2 lines, plus 4 units in the second line.
Note:
- The length of
Swill be in the range [1, 1000]. Swill only contain lowercase letters.widthsis an array of length26.widths[i]will be in the range of[2, 10].
Solution: Simulation
Time Complexity: O(n)
Space Complexity: O(1)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua class Solution { public: vector<int> numberOfLines(vector<int>& widths, string S) { int lines = 1; int units = 0; for (char c : S) { if (units + widths[c - 'a'] > 100) { ++lines; units = 0; } units += widths[c - 'a']; } return {lines, units}; } }; |
Problem
题目大意：给你一些单词，问这些单词的莫斯密码共有几种形式。
International Morse Code defines a standard encoding where each letter is mapped to a series of dots and dashes, as follows: "a" maps to ".-", "b" maps to "-...", "c" maps to "-.-.", and so on.
For convenience, the full table for the 26 letters of the English alphabet is given below:
[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]
Now, given a list of words, each word can be written as a concatenation of the Morse code of each letter. For example, “cab” can be written as “-.-.-….-“, (which is the concatenation “-.-.” + “-…” + “.-“). We’ll call such a concatenation, the transformation of a word.
Return the number of different transformations among all words we have.
Example: Input: words = ["gin", "zen", "gig", "msg"] Output: 2 Explanation: The transformation of each word is: "gin" -> "--...-." "zen" -> "--...-." "gig" -> "--...--." "msg" -> "--...--." There are 2 different transformations, "--...-." and "--...--.".
Note:
- The length of
wordswill be at most100. - Each
words[i]will have length in range[1, 12]. words[i]will only consist of lowercase letters.
Solution: HashTable
Time Complexity: O(n)
Space Complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// Author: Huahua class Solution { public: int uniqueMorseRepresentations(vector<string>& words) { vector<string> m{".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."}; unordered_set<string> s; for (const string& word : words) { string code; for (char c : word) code += m[c - 'a']; s.insert(code); } return s.size(); } }; |
Problem
题目大意：给你一个二维地图和每个坐标的大楼高度，求出总增高的最大值使得城市的天际线（投影）保持不变。
In a 2 dimensional array grid, each value grid[i][j] represents the height of a building located there. We are allowed to increase the height of any number of buildings, by any amount (the amounts can be different for different buildings). Height 0 is considered to be a building as well.
At the end, the “skyline” when viewed from all four directions of the grid, i.e. top, bottom, left, and right, must be the same as the skyline of the original grid. A city’s skyline is the outer contour of the rectangles formed by all the buildings when viewed from a distance. See the following example.
What is the maximum total sum that the height of the buildings can be increased?
Example:
Input: grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
Output: 35
Explanation:
The grid is:
[ [3, 0, 8, 4],
[2, 4, 5, 7],
[9, 2, 6, 3],
[0, 3, 1, 0] ]
The skyline viewed from top or bottom is: [9, 4, 8, 7]
The skyline viewed from left or right is: [8, 7, 9, 3]
The grid after increasing the height of buildings without affecting skylines is:
gridNew = [ [8, 4, 8, 7],
[7, 4, 7, 7],
[9, 4, 8, 7],
[3, 3, 3, 3] ]
Notes:
1 < grid.length = grid[0].length <= 50.- All heights
grid[i][j]are in the range[0, 100]. - All buildings in
grid[i][j]occupy the entire grid cell: that is, they are a1 x 1 x grid[i][j]rectangular prism.
Solution: Greedy
Find the max of each row and column, increase the height of building at i,j to min(max_row[i], max_col[j]).
Time Complexity: O(m*n)
Space complexity: O(m+n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua class Solution { public: int maxIncreaseKeepingSkyline(vector<vector<int>>& grid) { int m = grid.size(); int n = grid[0].size(); vector<int> x(n, 0); vector<int> y(n, 0); for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) { x[j] = max(x[j], grid[i][j]); y[i] = max(y[i], grid[i][j]); } int ans = 0; for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) ans += min(x[i], y[j]) - grid[i][j]; return ans; } }; |
Problem
题目大意：问能否将一个数组分成两部分，每部分的平均值相同。
In a given integer array A, we must move every element of A to either list B or list C. (B and C initially start empty.)
Return true if and only if after such a move, it is possible that the average value of B is equal to the average value of C, and B and C are both non-empty.
Example : Input: [1,2,3,4,5,6,7,8] Output: true Explanation: We can split the array into [1,4,5,8] and [2,3,6,7], and both of them have the average of 4.5.
Note:
- The length of
Awill be in the range [1, 30]. A[i]will be in the range of[0, 10000].
Solution: Search
Time complexity: O(2^n)
Space complexity: O(n)
|
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 |
// Author: Huahua // Running time: 771 ms class Solution { public: bool splitArraySameAverage(vector<int>& A) { std::sort(A.begin(), A.end()); sum = std::accumulate(A.begin(), A.end(), 0); n = A.size(); return dfs(A, 1, 0, 0); } private: int sum; int n; bool dfs(const vector<int>& A, int c, int s, int cur) { if (c > A.size() / 2) return false; for (int i = s; i < A.size(); ++i) { cur += A[i]; if (cur * (n - c) == (sum - cur) * c) return true; if (cur * (n - c) > (sum - cur) * c) break; if (dfs(A, c + 1, i + 1, cur)) return true; cur -= A[i]; } return false; } }; |