lihe / leetcode Goto Github PK
View Code? Open in Web Editor NEWRecord the process of Leetcode by GitHub
Record the process of Leetcode by GitHub
Given a m * n
grid, where each cell is either 0
(empty) or 1
(obstacle). In one step, you can move up, down, left or right from and to an empty cell.
Return the minimum number of steps to walk from the upper left corner (0, 0)
to the lower right corner (m-1, n-1)
given that you can eliminate at most k
obstacles. If it is not possible to find such walk return -1.
Example 1:
Input:
grid =
[[0,0,0],
[1,1,0],
[0,0,0],
[0,1,1],
[0,0,0]],
k = 1
Output: 6
Explanation:
The shortest path without eliminating any obstacle is 10.
The shortest path with one obstacle elimination at position (3,2) is 6. Such path is (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2).
Example 2:
Input:
grid =
[[0,1,1],
[1,1,1],
[1,0,0]],
k = 1
Output: -1
Explanation:
We need to eliminate at least two obstacles to find such a walk.
Constraints:
grid.length == m
grid[0].length == n
1 <= m, n <= 40
1 <= k <= m*n
grid[i][j] == 0 **or** 1
grid[0][0] == grid[m-1][n-1] == 0
算法思路:利用BFS
解题,将二维矩阵扩充为三维,z代表当前消除的障碍物数量;visited[x][y][z]
,代表消除z个障碍是否到达[x, y]
处。
class Solution {
private int[][] dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
public int shortestPath(int[][] grid, int k) {
int m = grid.length;
int n = grid[0].length;
boolean[][][] visited = new boolean[m][n][k + 1];
Queue<Point> queue = new LinkedList<>();
queue.add(new Point(0, 0, 0));
visited[0][0][0] = true;
int distance = 0;
while (!queue.isEmpty()){
distance++;
int size = queue.size();
for(int i = 0; i < size; i++){
Point point = queue.poll();
int x = point.x;
int y = point.y;
int z = point.z;
if(x == m - 1 && y == n - 1){ // 达到目的地
return distance - 1;
}
for(int j = 0; j < 4; j++){ // 四个方向
int new_x = x + dir[j][0];
int new_y = y + dir[j][1];
int new_z = z;
if(new_x < 0 || new_x >= m || new_y < 0 || new_y >= n){ // 超出矩阵范围
continue;
}
if(grid[new_x][new_y] == 1){
if ( z < k){ // 可以继续消除障碍物
new_z = z + 1;
}
else{
continue; // 已经到达上限
}
}
if(!visited[new_x][new_y][new_z]){ // 判断是否访问过
queue.add(new Point(new_x, new_y, new_z));
visited[new_x][new_y][new_z] = true;
}
}
}
}
return -1;
}
class Point{
int x;
int y;
int z;
public Point(int x, int y, int z){
this.x = x;
this.y = y;
this.z = z;
}
}
}
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
Example:
Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"
Note:
""
.题意:已知字符串S
和字符串T
,求在S
中的最小窗口,使得这个窗口包含了T
中的所有字符。
算法思路:
map_s
与map_t
,map_s
代表当前处理的窗口区间中的字符数量,map_t
代表了字符串T
的字符数量;i
和begin
指向字符串S
的第一个字符;i
指针向后逐个扫描字符串中的字符,这个过程中循环检查begin
指针是否可以向前移动;
begin
指向的字符,T
中没有出现,直接向前移动begin
;begin
指向的字符,T
中出现了,但是当前区间窗口中该字符的数量足够,直接向前移动begin
,并跟新map_s
;i
没向前扫描一个字符,即检查是否可以跟新最终的结果;在整个过程中,使用begin
和i
维护一个窗口,该窗口中的子串满足题目条件,窗口线性向前滑动,整体时间复杂度为O(n)
。
class Solution{
private:
bool is_window_ok(int map_s[], int map_t[], std::vector<int> &vec_t){
for(int i = 0; i < vec_t.size(); i++){
if(map_s[vec_t[i]] < map_t[vec_t[i]]){
return false;
}
}
return true;
}
public:
std::string minWindow(std::string s, std::string t){
const int MAX_ARRAY_LEN = 128;
int map_t[MAX_ARRAY_LEN] = {0};
int map_s[MAX_ARRAY_LEN] = {0};
std::vector<int> vec_t;
for(int i = 0; i < t.length(); i++){
map_t[t[i]]++;
}
for(int i = 0; i < MAX_ARRAY_LEN; i++){
if(map_t[i] > 0){
vec_t.push_back(i);
}
}
int window_begin = 0;
std::string result;
for(int i = 0; i < s.length(); i++){
map_s[s[i]]++;
while(window_begin < i){
char begin_ch = s[window_begin];
if(map_t[begin_ch] == 0){
window_begin++;
}
else if(map_s[begin_ch] > map_t[begin_ch]){
map_s[begin_ch]--;
window_begin++;
}
else{
break;
}
}
if(is_window_ok(map_s, map_t, vec_t)){
int new_window_len = i - window_begin + 1;
if(result == "" || result.length() > new_window_len){
result = s.substr(window_begin, new_window_len);
}
}
}
return result;
}
};
Easy
Given an integer number n
, return the difference between the product of its digits and the sum of its digits.
Example 1:
Input: n = 234
Output: 15
Explanation:
Product of digits = 2 * 3 * 4 = 24
Sum of digits = 2 + 3 + 4 = 9
Result = 24 - 9 = 15
Example 2:
Input: n = 4421
Output: 21
Explanation:
Product of digits = 4 * 4 * 2 * 1 = 32
Sum of digits = 4 + 4 + 2 + 1 = 11
Result = 32 - 11 = 21
Constraints:
1 <= n <= 10^5
class Solution {
public int subtractProductAndSum(int n) {
int sum = 0, mum = 1;
while(n != 0){
sum += n % 10;
mum *= n % 10;
n /= 10;
}
return mum - sum;
}
}
Medium
There are n
people whose IDs go from 0
to n - 1
and each person belongs exactly to one group. Given the array groupSizes
of length n
telling the group size each person belongs to, return the groups there are and the people's IDs each group includes.
You can return any solution in any order and the same applies for IDs. Also, it is guaranteed that there exists at least one solution.
Example 1:
Input: groupSizes = [3,3,3,3,3,1,3]
Output: [[5],[0,1,2],[3,4,6]]
Explanation:
Other possible solutions are [[2,1,6],[5],[0,4,3]] and [[5],[0,6,2],[4,3,1]].
Example 2:
Input: groupSizes = [2,1,3,3,3,2]
Output: [[1],[0,5],[2,3,4]]
Constraints:
groupSizes.length == n
1 <= n <= 500
1 <= groupSizes[i] <= n
class Solution{
public List<List<Integer>> groupThePeople(int[] groupSizes){
Map<Integer, List<Integer>> map = new HashMap<>();
List<List<Integer>> result = new ArrayList<>();
for(int i = 0; i < groupSizes.length; i++){
int flag = groupSizes[i];
if(! map.containsKey(flag))
map.put(flag, new ArrayList<>());
map.get(flag).add(i);
if(map.get(flag).size() == flag){
result.add(map.get(flag));
map.remove(flag);
}
}
return result;
}
}
Medium
Given an array of integers nums
and an integer threshold
, we will choose a positive integer divisor and divide all the array by it and sum the result of the division. Find the smallest divisor such that the result mentioned above is less than or equal to threshold
.
Each result of division is rounded to the nearest integer greater than or equal to that element. (For example: 7/3 = 3 and 10/2 = 5).
It is guaranteed that there will be an answer.
Example 1:
Input: nums = [1,2,5,9], threshold = 6
Output: 5
Explanation: We can get a sum to 17 (1+2+5+9) if the divisor is 1.
If the divisor is 4 we can get a sum to 7 (1+1+2+3) and if the divisor is 5 the sum will be 5 (1+1+1+2).
Example 2:
Input: nums = [2,3,5,7,11], threshold = 11
Output: 3
Example 3:
Input: nums = [19], threshold = 5
Output: 4
Constraints:
1 <= nums.length <= 5 * 10^4
1 <= nums[i] <= 10^6
nums.length <= threshold <= 10^6
class Solution{
public int smallestDivisor(int[] nums, int threshold){
int lo = 1, hi = 1000000;
while (lo < hi){
int mid = (lo + hi) / 2;
int result = cal(nums, mid);
if(result > threshold)
lo = mid + 1;
else
hi = mid;
}
return lo;
}
private int cal(int[] nums, int div){
int sum = 0;
for(int n : nums){
sum += Math.ceil((double)n / (double)div);
//if(n % div != 0) sum += 1;
}
return (int)sum;
}
}
Hard
Given a m x n
binary matrix mat
. In one step, you can choose one cell and flip it and all the four neighbours of it if they exist (Flip is changing 1 to 0 and 0 to 1). A pair of cells are called neighboors if they share one edge.
Return the minimum number of steps required to convert mat
to a zero matrix or -1 if you cannot.
Binary matrix is a matrix with all cells equal to 0 or 1 only.
Zero matrix is a matrix with all cells equal to 0.
Example 1:
Input: mat = [[0,0],[0,1]]
Output: 3
Explanation: One possible solution is to flip (1, 0) then (0, 1) and finally (1, 1) as shown.
Example 2:
Input: mat = [[0]]
Output: 0
Explanation: Given matrix is a zero matrix. We don't need to change it.
Example 3:
Input: mat = [[1,1,1],[1,0,1],[0,0,0]]
Output: 6
Example 4:
Input: mat = [[1,0,0],[1,0,0]]
Output: -1
Explanation: Given matrix can't be a zero matrix
Constraints:
m == mat.length
n == mat[0].length
1 <= m <= 3
1 <= n <= 3
mat[i][j]
is 0 or 1.Given a list of intervals, remove all intervals that are covered by another interval in the list. Interval [a,b)
is covered by interval [c,d)
if and only if c <= a
and b <= d
.
After doing so, return the number of remaining intervals.
Example 1:
Input: intervals = [[1,4],[3,6],[2,8]]
Output: 2
Explanation: Interval [3,6] is covered by [2,8], therefore it is removed.
Constraints:
1 <= intervals.length <= 1000
0 <= intervals[i][0] < intervals[i][1] <= 10^5
intervals[i] != intervals[j] for all i != j
算法思路:
result = intervals.lenght
,进行一遍遍历,定义max = intervals[0][1]
,如果intervals[i][1]
于max,result --,如果intervals[i][1]> max
,max = intervals[i][1]
。class Solution {
public int removeCoveredIntervals(int[][] intervals) {
Arrays.sort(intervals, (x, y) -> {
if (x[0] < y[0])
return -1;
else if (x[0] == y[0]) {
if (x[1] > y[1])
return -1;
}
return 1;
});
int len = intervals.length;
int max = intervals[0][1];
for(int i = 1; i < intervals.length; i++){
if(intervals[i][1] <= max){
len--;
continue;
}
else if(intervals[i][1] > max){
max = intervals[i][1];
}
}
return len;
}
}
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Note: Given n will be a positive integer.
Example 1:
Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Example 2:
Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
算法思路:
dp[0...n], dp[i]
,dp[i]
代表到达第i
阶有多少种走法,初始化为0
;dp[1] = 1,dp[2] = 2
;dp[i] = dp[i - 1] + dp[i - 2]
从第三阶推至第n
阶。class Solution {
public:
int climbStairs(int n) {
std::vector<int> dp(n + 3, 0);
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
};
Given an integer array sorted in non-decreasing order, there is exactly one integer in the array that occurs more than 25% of the time.
Return that integer.
Example 1:
Input: arr = [1,2,2,6,6,6,6,7,10]
Output: 6
Constraints:
// 1ms 39.3MB
class Solution {
public int findSpecialInteger(int[] arr) {
int result = arr[0];
int i = 0;
int cnt = 0;
while (i < arr.length){
cnt = 0;
while (arr[i] == result){
cnt ++;
if(cnt >= arr.length / 4 + 1){
return result;
}
i++;
}
result = arr[i];
}
return result;
}
}
// 11ms 39.2MB
class Solution {
public int findSpecialInteger(int[] arr) {
int[] list = new int[100000];
int result = 0;
for(int i = 0; i < arr.length; i++){
list[arr[i]]++;
}
for(int i = 0; i < list.length; i++){
if(list[i] >= (int)Math.ceil((double)arr.length / 4)){
result = i;
}
}
return result;
}
}
Design an Iterator class, which has:
characters
of sorted distinct lowercase English letters and a number combinationLength
as arguments.combinationLength
in lexicographical order.True
if and only if there exists a next combination.Example:
CombinationIterator iterator = new CombinationIterator("abc", 2); // creates the iterator.
iterator.next(); // returns "ab"
iterator.hasNext(); // returns true
iterator.next(); // returns "ac"
iterator.hasNext(); // returns true
iterator.next(); // returns "bc"
iterator.hasNext(); // returns false
Constraints:
1 <= combinationLength <= characters.length <= 15
10^4
function calls per test.next
are valid.import java.util.*;
class CombinationIterator {
List<String> ans;
String str;
int len;
public CombinationIterator(String characters, int combinationLength) {
ans = new ArrayList<>();
str = characters;
len = combinationLength;
backtrack(new StringBuilder(), 0);
}
public void backtrack(StringBuilder sb, int index){
if(sb.length() == len){
ans.add(sb.toString());
return;
}
for(int i = index; i < str.length(); i++){
sb.append(str.charAt(i));
backtrack(sb, i + 1);
sb.deleteCharAt(sb.length() - 1);
}
}
public String next() {
return ans.remove(0);
}
public boolean hasNext() {
return !ans.isEmpty();
}
}
/**
* Your CombinationIterator object will be instantiated and called as such:
* CombinationIterator obj = new CombinationIterator(characters, combinationLength);
* String param_1 = obj.next();
* boolean param_2 = obj.hasNext();
*/
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
The minimum path sum from top to bottom is 11
(2 + 3 + 5 + 1 = 11).
Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.
算法思路:
dp[][]
,并初始化数组为0
。dp[][]
从底向上递推时,走到三角形第i
行第j
列时的最优解;i
循环,从第二层递推至第一层,对每层的各列进行动态规划递推:第i
行,第j
列的最优解为dp[i][j]
,可达到(i,j)
的两个位置的最优解为dp[i + 1][j]
和dp[i + 1][j + 1]
,dp[i][j] = min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j]
。dp[0][0]
。class Solution{
public:
int minimumTotal(std::vector<std::vector<int>> &triangle){
if(triangle.size() == 0){
return 0;
}
std::vector<std::vector<int>> dp;
for(int i = 0; i < triangle.size(); i++){
dp.push_back(std::vector<int> ());
for(int j = 0; j < triangle[i].size(); j++){
dp[i].push_back(0);
}
}
for(int i = 0; i < dp.size(); i++){
dp[dp.size() - 1][i] = triangle[dp.size() - 1][i];
}
for(int i = dp.size() - 2; i >= 0; i--){
for(int j = 0; j < dp[i].size(); j++){
dp[i][j] = std::min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j];
}
}
return dp[0][0];
}
};
An integer has sequential digits if and only if each digit in the number is one more than the previous digit.
Return a sorted list of all the integers in the range [low, high]
inclusive that have sequential digits.
Example 1:
Input: low = 100, high = 300
Output: [123,234]
Example 2:
Input: low = 1000, high = 13000
Output: [1234,2345,3456,4567,5678,6789,12345]
Constraints:
10 <= low <= high <= 10^9
算法思路:一共36个数,通过打表即可解决。
class Solution {
public List<Integer> sequentialDigits(int low, int high) {
int[] list = {12, 23, 34, 45, 56, 67, 78, 89,
123, 234, 345, 456, 567, 678, 789,
1234, 2345, 3456, 4567, 5678, 6789,
12345, 23456, 34567, 45678, 56789,
123456, 234567, 345678, 456789,
1234567, 2345678, 3456789,
12345678, 23456789,
123456789};
List result = new LinkedList();
for(int i = 0; i < list.length; i++){
if(list[i] <= high && list[i] >= low){
result.add(list[i]);
}
}
return result;
}
}
Given a m x n
grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
Example:
Input:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.
解题思路:
dp[i][j]
是到达(i,j)
时的最优解;dp[i, j] = min(dp[i-1][j], dp[i][j-1]) + grid(i,j)
class Solution{
public:
int minPathSum(std::vector<std::vector<int>> &grid){
if(grid.size() == 0){
return 0;
}
int row = grid.size();
int column = grid[0].size();
std::vector<std::vector<int>> dp(row, std::vector<int>(column, 0));
dp[0][0] = grid[0][0];
for(int i = 1; i < column; i++){
dp[0][i] = dp[0][i - 1] + grid[0][i];
}
for(int i = 1; i < row; i++){
dp[i][0] = dp[i - 1][0] + grid[i][0];
for(int j = 1; j < column; j++){
dp[i][j] = std::min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[row - 1][column - 1];
}
};
All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.
Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.
Example:
Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output: ["AAAAACCCCC", "CCCCCAAAAA"]
题意:将DNA序列看成一个只包含[A,B,C,D]
四个字符的字符串,给一个DNA字符串,找出所有长度为10的且出现次数超过一次的字符串。
算法思路:
方法一:
算法复杂度为O(n)
class Solution{
public:
std::vector<std::string> findRepeatedDnaSequences(std::string s){
std::map<std::string, int> word_map;
std::vector<std::string> result;
for(int i = 0; i < s.length(); i++){
std::string word = s.substr(i, 10);
if(word_map.find(word) != word_map.end()){
word_map[word] += 1;
}
else{
word_map[word] = 1;
}
}
std::map<std::string, int> :: iterator it;
for(it = word_map.begin(); it != word_map.end(); it++){
if(it -> second > 1){
result.push_back(it -> first);
}
}
return result;
}
};
方法二:
int g_hash_map[1028576]
1048576 = 2^20,表示所有的长度为10的DNA序列;key
,g_hash_map[key]++
;key
右移二位(去掉最低位),并将新的DNA字符s[i]
转化为整数后,或到最后两位,g_hash_map[key]++
;g_hash_map
,若g_hash_map[i] > 1
,将i
从低到高位转化为10个DNA序列,push
到结果数组。int g_hash_map[1048576] = {0};
std::string change_int_to_DNA(int DNA){
static const char DNA_CHAR[] = {'A', 'C', 'G', 'T'};
std::string str;
for(int i = 0; i < 10; i++){
str += DNA_CHAR[DNA & 3];
DNA = DNA >> 2;
}
return str;
}
class Solution{
public:
std::vector<std::string> findRepeatedDnaSequences(std::string s){
std::vector<std::string> result;
if(s.length() < 10){
return result;
}
for(int i = 0; i < 1048576; i++){
g_hash_map[i] = 0;
}
int char_map[128] = {0};
char_map['A'] = 0;
char_map['C'] = 1;
char_map['G'] = 2;
char_map['T'] = 3;
int key = 0;
for(int i = 9; i >= 0; i--){
key = (key << 2) + char_map[s[i]];
}
g_hash_map[key] = 1;
for(int i = 10; i < s.length(); i++){
key = key >> 2;
key = key | (char_map[s[i]] << 18);
g_hash_map[key]++;
}
for(int i = 0; i < 1048576; i++){
if(g_hash_map[i] > 1){
result.push_back(change_int_to_DNA(i));
}
}
return result;
}
};
You are given a map of a server center, represented as a m * n
integer matrix grid
, where 1 means that on that cell there is a server and 0 means that it is no server. Two servers are said to communicate if they are on the same row or on the same column.
Return the number of servers that communicate with any other server.
Example 1:
Input: grid = [[1,0],[0,1]]
Output: 0
Explanation: No servers can communicate with others.
Example 2:
Input: grid = [[1,0],[1,1]]
Output: 3
Explanation: All three servers can communicate with at least one other server.
Example 3:
Input: grid = [[1,1,0,0],[0,0,1,0],[0,0,1,0],[0,0,0,1]]
Output: 4
Explanation: The two servers in the first row can communicate with each other. The two servers in the third column can communicate with each other. The server at right bottom corner can't communicate with any other server.
Constraints:
m == grid.length
n == grid[i].length
1 <= m <= 250
1 <= n <= 250
grid[i][j] == 0 or 1
算法思路:首先遍历一遍,记录每行每列分别有多少台服务器;然后再便利一遍,如果grid[i, j] = 1
,count_row[i] > 1
或 count_col[j] > 1
,则result++
。
class Solution {
public int countServers(int[][] grid) {
int row_n = grid.length;
int col_n = grid[0].length;
int[] count_row = new int[row_n];
int[] count_col = new int[col_n];
for(int i = 0; i < row_n; i++){
for(int j = 0; j < col_n; j++){
if(grid[i][j] == 1){
count_row[i]++;
count_col[j]++;
}
}
}
int result= 0;
for(int i = 0; i < row_n; i++){
for(int j = 0; j < col_n; j++){
if(grid[i][j] == 1 && (count_row[i] > 1 || count_col[j] > 1)){
result++;
}
}
}
return result;
}
}
第一次参加Leetcode
周赛,做出来两题,感觉排名前十的都是神仙。
Easy
Given n
and m
which are the dimensions of a matrix initialized by zeros and given an array indices
where indices[i] = [ri, ci]
. For each pair of [ri, ci]
you have to increment all cells in row ri
and column ci
by 1.
Return the number of cells with odd values in the matrix after applying the increment to all indices
.
Example 1:
Input: n = 2, m = 3, indices = [[0,1],[1,1]]
Output: 6
Explanation: Initial matrix = [[0,0,0],[0,0,0]].
After applying first increment it becomes [[1,2,1],[0,1,0]].
The final matrix will be [[1,3,1],[1,3,1]] which contains 6 odd numbers.
Example 2:
Input: n = 2, m = 2, indices = [[1,1],[0,0]]
Output: 0
Explanation: Final matrix = [[2,2],[2,2]]. There is no odd number in the final matrix.
Constraints:
1 <= n <= 50
1 <= m <= 50
1 <= indices.length <= 100
0 <= indices[i][0] < n
0 <= indices[i][1] < m
class Solution {
public:
int oddCells(int n, int m, vector<vector<int>>& indices) {
if(indices.size() == 0)
return 0;
vector<vector<int>> girl(n, vector<int>(m, 0));
for(int i = 0; i < indices.size(); i++){
int row = indices[i][0];
int col = indices[i][1];
for(int j = 0; j < m; j++){
girl[row][j]++;
}
for(int j = 0; j < n; j++){
girl[j][col]++;
}
}
int result = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(girl[i][j] % 2){
result++;
}
}
}
return result;
}
};
Medium
Given the following details of a matrix with n
columns and 2
rows :
0
or 1
.upper
.lower
.colsum[i]
, where colsum
is given as an integer array with length n
.Your task is to reconstruct the matrix with upper
, lower
and colsum
.
Return it as a 2-D integer array.
If there are more than one valid solution, any of them will be accepted.
If no valid solution exists, return an empty 2-D array.
Example 1:
Input: upper = 2, lower = 1, colsum = [1,1,1]
Output: [[1,1,0],[0,0,1]]
Explanation: [[1,0,1],[0,1,0]], and [[0,1,1],[1,0,0]] are also correct answers.
Example 2:
Input: upper = 2, lower = 3, colsum = [2,2,1,1]
Output: []
Example 3:
Input: upper = 5, lower = 5, colsum = [2,1,2,0,1,0,1,2,0,1]
Output: [[1,1,1,0,1,0,0,1,0,0],[1,0,1,0,0,0,1,1,0,1]]
Constraints:
1 <= colsum.length <= 10^5
0 <= upper, lower <= colsum.length
0 <= colsum[i] <= 2
class Solution {
public:
vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {
int sum = 0;
for(int i = 0; i < colsum.size(); i++){
sum += colsum[i];
}
int all = upper + lower;
if(all != sum)
return vector<vector<int>>();
vector<vector<int>> girl(2, vector<int>(colsum.size(), 0));
for(int i = 0; i < colsum.size(); i++){
girl[0][i] = colsum[i];
}
for(int i = 0; i < colsum.size(); i++){
if(lower !=0 && girl[0][i] != 0){
girl[0][i]--;
girl[1][i]++;
lower--;
}
}
return girl;
}
};
Medium
Given a 2D grid
consists of 0s
(land) and 1s
(water). An island is a maximal 4-directionally connected group of 0s
and a closed island is an island totally (all left, top, right, bottom) surrounded by 1s.
Return the number of closed islands.
Example 1:
Input: grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
Output: 2
Explanation:
Islands in gray are closed because they are completely surrounded by water (group of 1s).
Example 2:
Input: grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
Output: 1
Example 3:
Input: grid = [[1,1,1,1,1,1,1],
[1,0,0,0,0,0,1],
[1,0,1,1,1,0,1],
[1,0,1,0,1,0,1],
[1,0,1,1,1,0,1],
[1,0,0,0,0,0,1],
[1,1,1,1,1,1,1]]
Output: 2
Constraints:
1 <= grid.length, grid[0].length <= 100
0 <= grid[i][j] <=1
class Solution{
public:
void dfs(std::vector<std::vector<int>> &grid, int i, int j, int &val){
if(i < 0 || i == grid.size()|| j < 0 || j == grid[0].size()){ // 边界条件
val = 0;
return;
}
if(grid[i][j] == 1)
return;
grid[i][j] = 1; // 标记已访问过的方块
dfs(grid, i + 1, j, val);
dfs(grid, i - 1, j, val);
dfs(grid, i, j - 1, val);
dfs(grid, i, j + 1, val);
}
int closedIsland(std::vector<std::vector<int>> &grid){
int result = 0;
for(int i = 0; i < grid.size(); i++){
for(int j = 0; j < grid[i].size(); j++){
if(grid[i][j] == 0){
int val = 1;
dfs(grid, i, j, val);
result += val;
}
}
}
return result;
}
};
Hard
Given a list of words
, list of single letters
(might be repeating) and score
of every character.
Return the maximum score of any valid set of words formed by using the given letters (words[i]
cannot be used two or more times).
It is not necessary to use all characters in letters
and each letter can only be used once. Score of letters 'a'
, 'b'
, 'c'
, ... ,'z'
is given by score[0]
, score[1]
, ... , score[25]
respectively.
Example 1:
Input: words = ["dog","cat","dad","good"], letters = ["a","a","c","d","d","d","g","o","o"], score = [1,0,9,5,0,0,3,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0]
Output: 23
Explanation:
Score a=1, c=9, d=5, g=3, o=2
Given letters, we can form the words "dad" (5+1+5) and "good" (3+2+2+5) with a score of 23.
Words "dad" and "dog" only get a score of 21.
Example 2:
Input: words = ["xxxz","ax","bx","cx"], letters = ["z","a","b","c","x","x","x"], score = [4,4,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,5,0,10]
Output: 27
Explanation:
Score a=4, b=4, c=4, x=5, z=10
Given letters, we can form the words "ax" (4+5), "bx" (4+5) and "cx" (4+5) with a score of 27.
Word "xxxz" only get a score of 25.
Example 3:
Input: words = ["leetcode"], letters = ["l","e","t","c","o","d"], score = [0,0,1,1,1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0]
Output: 0
Explanation:
Letter "e" can only be used once.
Constraints:
1 <= words.length <= 14
1 <= words[i].length <= 15
1 <= letters.length <= 100
letters[i].length == 1
score.length == 26
0 <= score[i] <= 10
words[i]
, letters[i]
contains only lower case English letters.class Solution{
public:
vector<int> group(vector<string> &words, int bit){
vector<int> g(26, 0);
for(int i = 0; i < words.size(); i++){
if(bit & (1 << i)){
for(auto c : words[i]){
g[c - 'a']++;
}
}
}
return g;
}
int maxScoreWords(vector<string> &words, vector<char> &letters, vector<int> &score){
vector<int> l(26, 0);
for(auto c : letters){
l[c - 'a']++;
}
int result = 0;
for(int i = 0; i < (1 << words.size()); i++){
auto g = group(words, i);
int temp = 0;
for(int j = 0; j < 26; j++){
if(l[j] < g[j]){
temp = 0;
break;
}
else{
temp += g[j] * score[j];
}
}
result = max(result, temp);
}
return result;
}
};
Given a m x n matrix mat and an integer threshold. Return the maximum side-length of a square with a sum less than or equal to threshold or return 0 if there is no such square.
Example 1:
Input: mat = [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]], threshold = 4
Output: 2
Explanation: The maximum side length of square with sum less than 4 is 2 as shown.
Example 2:
Input: mat = [[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2]], threshold = 1
Output: 0
Example 3:
Input: mat = [[1,1,1,1],[1,0,0,0],[1,0,0,0],[1,0,0,0]], threshold = 6
Output: 3
Example 4:
Input: mat = [[18,70],[61,1],[25,85],[14,40],[11,96],[97,96],[63,45]], threshold = 40184
Output: 2
Constraints:
1 <= m, n <= 300
m == mat.length
n == mat[i].length
0 <= mat[i][j] <= 10000
0 <= threshold <= 10^5
class Solution {
public int maxSideLength(int[][] mat, int threshold) {
int result = 0;
for(int i = 0; i < mat.length; i++){
for(int j = 0; j < mat[0].length; j++){
if(j != 0){
mat[i][j] += mat[i][j - 1];
}
int len = 0;
int maxlen = Math.min(i, j) + 1;
while (len < maxlen){
int area = 0;
for(int k = 0; k < len + 1; k++){
int prefix = j - len - 1 < 0 ? 0 : mat[i - k][j - len - 1];
area += mat[i - k][j] - prefix;
}
if(area > threshold) {
break;
}
len++;
}
result = len > result ? len : result;
}
}
return result;
}
}
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
Example 1:
Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
Example 2:
Input: [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.
分析:由于同时从相邻的两个房屋中盗取财宝就会触发报警器,所以若选择盗取第i
个房间的财宝就一定不能选择第i-1
个房间的财宝,若不从第i
个房间盗取财宝则相当于只考虑从前i-1
个房间盗取财宝。
解题思路:
n
个房间的最优解,子问题为求前1
个房间,前2
个房间...前n-1
个房间的最优解。i
个状态为前i
个房间能获得的最大财宝。1
个房间的最优解是第一个房间的财宝;2
个房间的最优解是第1、2
个房间中较大财宝的;i
个房间:第i
个房间和前i-2
个房间的最优解;i
个房间:前i-1
个房间的最优解;dp[i] = max(dp[i-1], dp[i-2] + nums[i]) (i >= 3)
。class Solution{
public:
int rob(std::vector<int> &nums){
if(nums.size() == 0){
return 0;
}
if(nums.size() == 1){
return nums[0];
}
std::vector<int> dp(nums.size(), 0);
dp[0] = nums[0];
dp[1] = std::max(nums[0], nums[1]);
for(int i = 2; i < nums.size(); i++){
dp[i] = std::max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[nums.size() - 1];
}
};
You are given a string representing an attendance record for a student. The record only contains the following three characters:
A student could be rewarded if his attendance record doesn't contain more than one 'A' (absent) or more than two continuous 'L' (late).
You need to return whether the student could be rewarded according to his attendance record.
Example 1:
Input: "PPALLP"
Output: True
Example 2:
Input: "PPALLL"
Output: False
class Solution {
public boolean checkRecord(String s) {
int count = 0;
for(int i = 0; i < s.length() && count < 2; i++){
if(s.charAt(i) == 'A')
count++;
}
return count < 2 && s.indexOf("LLL") < 0;
}
}
On a plane there are n
points with integer coordinates points[i] = [xi, yi]
. Your task is to find the minimum time in seconds to visit all points.
You can move according to the next rules:
Example 1:
Input: points = [[1,1],[3,4],[-1,0]]
Output: 7
Explanation: One optimal path is [1,1] -> [2,2] -> [3,3] -> [3,4] -> [2,3] -> [1,2] -> [0,1] -> [-1,0]
Time from [1,1] to [3,4] = 3 seconds
Time from [3,4] to [-1,0] = 4 seconds
Total time = 7 seconds
Example 2:
Input: points = [[3,2],[-2,2]]
Output: 5
Constraints:
points.length == n
1 <= n <= 100
points[i].length == 2
-1000 <= points[i][0], points[i][1] <= 1000
算法思路:两个点之间移动所需的最短时间,取决于横纵坐标中相差较大的。
class Solution {
public int minTimeToVisitAllPoints(int[][] points) {
int result = 0;
for(int i = 0; i < points.length - 1; i++){
int x = Math.abs(points[i][0] - points[i + 1][0]);
int y = Math.abs(points[i][1] - points[i + 1][1]);
if(x >= y)
result += x;
else
result += y;
}
return result;
}
}
Given a 2D grid
consists of 0s
(land) and 1s
(water). An island is a maximal 4-directionally connected group of 0s
and a closed island is an island totally (all left, top, right, bottom) surrounded by 1s.
Return the number of closed islands.
Example 1:
Input: grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
Output: 2
Explanation:
Islands in gray are closed because they are completely surrounded by water (group of 1s).
Example 2:
Input: grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
Output: 1
Example 3:
Input: grid = [[1,1,1,1,1,1,1],
[1,0,0,0,0,0,1],
[1,0,1,1,1,0,1],
[1,0,1,0,1,0,1],
[1,0,1,1,1,0,1],
[1,0,0,0,0,0,1],
[1,1,1,1,1,1,1]]
Output: 2
Constraints:
1 <= grid.length, grid[0].length <= 100
0 <= grid[i][j] <=1
class Solution{
public:
void dfs(std::vector<std::vector<int>> &grid, int i, int j, int &val){
if(i < 0 || i == grid.size()|| j < 0 || j == grid[0].size()){
val = 0;
return;
}
if(grid[i][j] == 1)
return;
grid[i][j] = 1;
dfs(grid, i + 1, j, val);
dfs(grid, i - 1, j, val);
dfs(grid, i, j - 1, val);
dfs(grid, i, j + 1, val);
}
int closedIsland(std::vector<std::vector<int>> &grid){
int result = 0;
for(int i = 0; i < grid.size(); i++){
for(int j = 0; j < grid[i].size(); j++){
if(grid[i][j] == 0){
int val = 1;
dfs(grid, i, j, val);
result += val;
}
}
}
return result;
}
};
Given an array of strings products
and a string searchWord
. We want to design a system that suggests at most three product names from products
after each character of searchWord
is typed. Suggested products should have common prefix with the searchWord. If there are more than three products with a common prefix return the three lexicographically minimums products.
Return list of lists of the suggested products
after each character of searchWord
is typed.
Example 1:
Input: products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
Output: [
["mobile","moneypot","monitor"],
["mobile","moneypot","monitor"],
["mouse","mousepad"],
["mouse","mousepad"],
["mouse","mousepad"]
]
Explanation: products sorted lexicographically = ["mobile","moneypot","monitor","mouse","mousepad"]
After typing m and mo all products match and we show user ["mobile","moneypot","monitor"]
After typing mou, mous and mouse the system suggests ["mouse","mousepad"]
Example 2:
Input: products = ["havana"], searchWord = "havana"
Output: [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]
Example 3:
Input: products = ["bags","baggage","banner","box","cloths"], searchWord = "bags"
Output: [["baggage","bags","banner"],["baggage","bags","banner"],["baggage","bags"],["bags"]]
Example 4:
Input: products = ["havana"], searchWord = "tatiana"
Output: [[],[],[],[],[],[],[]]
Constraints:
1 <= products.length <= 1000
products
.1 <= Σ products[i].length <= 2 * 10^4
products[i]
are lower-case English letters.1 <= searchWord.length <= 1000
searchWord
are lower-case English letters.算法思路:对products排序后暴力解决。
class Solution {
public List<List<String>> suggestedProducts(String[] products, String searchWord) {
Arrays.sort(products);
List<List<String>> result = new ArrayList<>();
for(int i = 1; i <= searchWord.length(); i++){
String substr = searchWord.substring(0, i); // 生成子串
List<String> collector = new ArrayList<>();
for(String x: products){
if(x.startsWith(substr)){ // x是否以substr为前缀
collector.add(x);
if(collector.size() == 3)
break;
}
}
result.add(collector);
}
return result;
}
}
You are given two strings s1
and s2
of equal length consisting of letters "x"
and "y"
only. Your task is to make these two strings equal to each other. You can swap any two characters that belong to different strings, which means: swap s1[i]
and s2[j]
.
Return the minimum number of swaps required to make s1
and s2
equal, or return -1
if it is impossible to do so.
Example 1:
Input: s1 = "xx", s2 = "yy"
Output: 1
Explanation:
Swap s1[0] and s2[1], s1 = "yx", s2 = "yx".
Example 2:
Input: s1 = "xy", s2 = "yx"
Output: 2
Explanation:
Swap s1[0] and s2[0], s1 = "yy", s2 = "xx".
Swap s1[0] and s2[1], s1 = "xy", s2 = "xy".
Note that you can't swap s1[0] and s1[1] to make s1 equal to "yx", cause we can only swap chars in different strings.
Example 3:
Input: s1 = "xx", s2 = "xy"
Output: -1
Example 4:
Input: s1 = "xxyyxyxyxx", s2 = "xyyxyxxxyx"
Output: 4
Constraints:
1 <= s1.length, s2.length <= 1000
s1, s2
only contain 'x'
or 'y'
.class Solution {
public int minimumSwap(String s1, String s2) {
int xy = 0;
int yx = 0;
for(int i = 0; i < s1.length(); i ++){
if(s1.charAt(i) == s2.charAt(i)){
continue;
}
else if(s1.charAt(i) == 'x') xy++;
else yx++;
}
return ((xy + yx) & 1) == 1 ? -1 : (xy + 1) / 2 + (yx + 1) / 2;
}
}
Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke"
is a subsequence and not a substring.
题意:已知一个字符串,求该字符串的无重复字符的最长子串长度。
算法思路:
char_map
;word
;i
和指针begin
)指向字符串的第一个字符;result
;char_map
,记录字符数量;
word
中没有出现过该字符:对word
尾部添加字符并检查result
是否需要更新;begin
指针向前移动,更新char_map
中的字符数量,直到字符s[i]
数量为1,更新word
,将word
赋值为begin
和i
之间的 子串。在整个过程之间,使用begin
和i
维护一个窗口,该窗口中的子串满足题目中的条件,窗口线性向前滑动,时间复杂度为O(n)
。
class Solution{
public:
int lengthOfLongestSubstring(std::string s){
int begin = 0;
int result = 0;
std::string word = "";
int char_map[128] = {0};
for(int i = 0; i < s.length(); i++){
char_map[s[i]]++;
if(char_map[s[i]] == 1){
word += s[i];
if(result < word.length()){
result = word.length();
}
}
else{
while(begin < i && char_map[s[i]] > 1){
char_map[s[begin]]--;
begin++;
}
word = "";
for(int j = begin;j <= i; j++){
word += s[j];
}
}
}
return result;
}
};
Given a pattern and a string str, find if str follows the same pattern.
Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.
Example 1:
Input: pattern = "abba", str = "dog cat cat dog"
Output: true
Example 2:
Input:pattern = "abba", str = "dog cat cat fish"
Output: false
Example 3:
Input: pattern = "aaaa", str = "dog cat cat dog"
Output: false
Example 4:
Input: pattern = "abba", str = "dog dog dog dog"
Output: false
Notes:
You may assume pattern contains only lowercase letters, and str contains lowercase letters that may be separated by a single space.
题意:一直str
和pattern
,判断str
和pattern
是否匹配。(匹配代表字符创str
和pattern
中的字符一一对应)
解题思路:
use[128]
记录pattern
字符是否使用。false
pattern
字符做映射pattern
字符已被使用pattern
字符,则返回false
pattern
字数不匹配,则返回false
。class Solution {
public:
bool wordPattern(std::string pattern, std::string str) {
std::map<std::string, char> word_map;
char used[128] = {0};
std::string word;
int pos = 0;
str.push_back(' ');
for (int i = 0; i < str.length(); i++){
if (str[i] == ' '){
if (pos == pattern.length()){
return false;
}
if (word_map.find(word) == word_map.end()){
if (used[pattern[pos]]){
return false;
}
word_map[word] = pattern[pos];
used[pattern[pos]] = 1;
}
else{
if (word_map[word] != pattern[pos]){
return false;
}
}
word = "";
pos++;
}
else{
word += str[i];
}
}
if (pos != pattern.length()){
return false;
}
return true;
}
};
You have a pointer at index 0
in an array of size arrLen
. At each step, you can move 1 position to the left, 1 position to the right in the array or stay in the same place (The pointer should not be placed outside the array at any time).
Given two integers steps
and arrLen
, return the number of ways such that your pointer still at index 0
after exactly steps
steps.
Since the answer may be too large, return it modulo 10^9 + 7
.
Example 1:
Input: steps = 3, arrLen = 2
Output: 4
Explanation: There are 4 differents ways to stay at index 0 after 3 steps.
Right, Left, Stay
Stay, Right, Left
Right, Stay, Left
Stay, Stay, Stay
Example 2:
Input: steps = 2, arrLen = 4
Output: 2
Explanation: There are 2 differents ways to stay at index 0 after 2 steps
Right, Left
Stay, Stay
Example 3:
Input: steps = 4, arrLen = 2
Output: 8
Constraints:
1 <= steps <= 500
1 <= arrLen <= 10^6
算法思路:利用动态规划的**,设dp[steps][len]
表示经过steps
步到达len
位置的方法的数量,dp[i][j] = dp[i - 1][j - 1] + dp[i -1][j] + dp[i + 1][j - 1]
,且len <= steps + 1
,所以len
取steps + 1
和arrLen
中的较小值。
class Solution {
private static int MOD = 1_000_000_007;
public int numWays(int steps, int arrLen) {
int len = Math.min(steps + 1, arrLen);
int[][] dp = new int[steps+1][len];
dp[0][0] = 1;
for (int i = 1; i <= steps; i++) {
for (int j = 0; j < len; j++) {
dp[i][j] = dp[i-1][j];
if (j - 1 >= 0){
dp[i][j] += dp[i-1][j-1];
dp[i][j] %= MOD;
}
if (j + 1 < len){
dp[i][j] += dp[i-1][j+1];
dp[i][j] %= MOD;
}
}
}
return dp[steps][0];
}
}
Given an array of integers nums
and an integer threshold
, we will choose a positive integer divisor and divide all the array by it and sum the result of the division. Find the smallest divisor such that the result mentioned above is less than or equal to threshold
.
Each result of division is rounded to the nearest integer greater than or equal to that element. (For example: 7/3 = 3 and 10/2 = 5).
It is guaranteed that there will be an answer.
Example 1:
Input: nums = [1,2,5,9], threshold = 6
Output: 5
Explanation: We can get a sum to 17 (1+2+5+9) if the divisor is 1.
If the divisor is 4 we can get a sum to 7 (1+1+2+3) and if the divisor is 5 the sum will be 5 (1+1+1+2).
Example 2:
Input: nums = [2,3,5,7,11], threshold = 11
Output: 3
Example 3:
Input: nums = [19], threshold = 5
Output: 4
Constraints:
1 <= nums.length <= 5 * 10^4
1 <= nums[i] <= 10^6
nums.length <= threshold <= 10^6
算法思路:
记cal(x)
为以x为除数,数组里每个数除以x
的累加和,易知cal(x)
是一个单调递减函数,可以利用函数的单调性,用二分法快速定位x
大小。
class Solution{
public int smallestDivisor(int[] nums, int threshold){
int lo = 1, hi = 1000000;
while (lo < hi){
int mid = (lo + hi) >> 1;
int result = cal(nums, mid);
if(result > threshold)
lo = mid + 1;
else
hi = mid;
}
return lo;
}
private int cal(int[] nums, int div){
int sum = 0;
for(int n : nums){
sum += Math.ceil((double)n / (double)div); // 向上取整
//if(n % div != 0) sum += 1;
}
return (int)sum;
}
}
Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.
This is case sensitive, for example "Aa" is not considered a palindrome here.
Note:
Assume the length of given string will not exceed 1,010.
Example:
Input:
"abccccdd"
Output:
7
Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.
题意:用题目中所给字符串中的字符,求可以生成的最长回文串的长度。
算法思路:
max_length = 0
flag = 0
count
,若count
为偶数max_length += count
,若count
为奇数,max_length += count - 1
, f1ag = 1
max_length + flag
class Solution {
public:
int longestPalindrome(std::string s) {
int char_map[128] = {0};
int max_length = 0;
int flag = 0;
for (int i = 0; i < s.length(); i++){
char_map[s[i]]++;
}
for (int i = 0; i < 128; i++){
if (char_map[i] % 2 == 0){
max_length += char_map[i];
}
else{
max_length += char_map[i] - 1;
flag = 1;
}
}
return max_length + flag;
}
};
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
Note: A leaf is a node with no children.
Example:
Given the below binary tree and sum = 22
,
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
Return:
[
[5,4,11,2],
[5,8,4,5]
]
题意:给定一个二叉树与整数sum
,找出所有的从根节点到野子节点的路径,这些路径上的节点的和为sum
。
解题思路:
path
栈中,使用path_value
累加节点值;path_value
的值是否为sum
,若为sum
,将path
push进入result
中;path
栈中弹出,path_valut
减去节点值。class Solution{
public:
std::vector<std::vector<int>> pathSum(TreeNode* root, int sum){
std::vector<std::vector<int>> result;
std::vector<int> path;
int path_value = 0;
preorder(root, path_value, sum, path, result);
return result;
}
private:
void preorder(TreeNode* node, int &path_value,
int sum, std::vector<int> &path, std::vector<std::vector<int>> &result){
if(!node){
return;
}
path_value += node -> val;
path.push_back(node -> val);
if(!node -> left && !node -> right && path_value == sum){
result.push_back(path);
}
preorder(node -> left, path_value, sum, path, result);
preorder(node -> right, path_value, sum, path, result);
path_value -= node -> val;
path.pop_back();
}
};
Given a function f(x, y)
and a value z
, return all positive integer pairs x
and y
where f(x,y) == z
.
The function is constantly increasing, i.e.:
f(x, y) < f(x + 1, y)
f(x, y) < f(x, y + 1)
The function interface is defined like this:
interface CustomFunction {
public:
// Returns positive integer f(x, y) for any given positive integer x and y.
int f(int x, int y);
};
For custom testing purposes you're given an integer function_id
and a target z
as input, where function_id
represent one function from an secret internal list, on the examples you'll know only two functions from the list.
You may return the solutions in any order.
Example 1:
Input: function_id = 1, z = 5
Output: [[1,4],[2,3],[3,2],[4,1]]
Explanation: function_id = 1 means that f(x, y) = x + y
Example 2:
Input: function_id = 2, z = 5
Output: [[1,5],[5,1]]
Explanation: function_id = 2 means that f(x, y) = x * y
Constraints:
1 <= function_id <= 9
1 <= z <= 100
f(x, y) == z
will be on the range 1 <= x, y <= 1000
f(x, y)
will fit in 32 bit signed integer if 1 <= x, y <= 1000
题意:找出所有符合f(x, y) = z
的[x, y]
算法思路:
left
和右指针right
,左指针指向1
,右指针指向1000
;f(left, right)
是否等于z
;
[left, right]
push进最终的结果中;f(left, right) > z
则right--
;
f(left, right) < z
则left++
;利用双指针遍历一遍即可找出所有符合条件的[x, y]
,时间复杂度为O(n)
。
/*
* // This is the custom function interface.
* // You should not implement it, or speculate about its implementation
* class CustomFunction {
* public:
* // Returns f(x, y) for any given positive integers x and y.
* // Note that f(x, y) is increasing with respect to both x and y.
* // i.e. f(x, y) < f(x + 1, y), f(x, y) < f(x, y + 1)
* int f(int x, int y);
* };
*/
class Solution {
public:
vector<vector<int>> findSolution(CustomFunction& customfunction, int z) {
std::vector<std::vector<int>> result;
int left = 1, right = 1000;
while(left <= 1000 && right >= 1){
int ans = customfunction.f(left, right);
if(ans == z){
std::vector<int> temp;
temp.push_back(left);
temp.push_back(right);
result.push_back(temp);
left++;
}
else if(ans > z){
right--;
}
else{
left++;
}
}
return result;
}
};
Given two words (beginWord
and endWord
), and a dictionary's word list, find the length of shortest transformation sequence from beginWord
to endWord
, such that:
beginWord
is not a transformed word.Note:
beginWord
and endWord
are non-empty and are not the same.Example 1:
Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Example 2:
Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.
算法思路:
beginword
到endword
的最短路径;map
构造邻接表所表示的图,map
定义为以string
为key
,vector<string>
为value
,将beginword
push进wordlist
,遍历wordlist
,对任意两个单词,若它们只差一个字母,则将其相连;bool connect(const std::string &word1, const std::string &word2){
int cnt = 0;
for(int i = 0; i < word1.size(); i++){
if(word1[i] != word2[i]){
cnt++;
}
}
return cnt == 1;
}
void construct_graph(std::string &beginWord, std::vector<std::string> &wordList,
std::map<std::string, std::vector<std::string>> &graph){
wordList.push_back(beginWord);
for(int i = 0; i < wordList.size(); i++){
graph[wordList] = std::vector<std::string>();
}
for(int i = 0; i < wordList.size(); i++){
for(int j = i + 1; j < wordList.size(); j++){
if(connect(wordList[i], wordList[j])){
graph[wordList[i]].push_back(wordList[j]);
graph[wordList[j]].push_back(wordList[i]);
}
}
}
}
Q
,队列节点为pair<定点,步数>
;设置集合visit
,记录搜索过的节点;将<beginWord, 1>
添加至队列;endword
,返回到达当前节点的步数;visit
中的节点与步数同时添加的到队列Q
,并将拓展节点加入viist
;endword
则返回0;int BFS_graph(std::string &beginWord, std::string &endWord,
std::map<std::string, std::vector<std::string>> &graph){
std::queue<std::pair<std::string, int>> Q;
std::set<std::string> visit;
Q.push(std::make_pair(beginWord, 1));
visit.insert(beginWord);
while(!Q.empty()){
std::string node = Q.front().first;
int step = Q.front().second;
Q.pop();
if(node == endWord){
return step;
}
const std::vector<std::string> &neighbors = graph[node];
for(int i = 0; i < neighbors.size(); i++){
if(visit.find(neighbors[i]) == visit.end()){
Q.push(std::make_pair(neighbors[i], step + 1));
visit.insert(neighbors[i]);
}
}
}
return 0;
}
class Solution{
public:
int ladderLength(std::string beginWord, std::string endWord, std::vector<std::string>& wordList) {
std::map<std::string, std::vector<std::string>> graph;
construct_graph(beginWord, wordList, graph);
return BFS_graph(beginWord, endWord, graph);
}
};
The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D
grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.
The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.
Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0's
) or contain magic orbs that increase the knight's health (positive integers).
In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.
Write a function to determine the knight's minimum initial health so that he is able to rescue the princess.
For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path RIGHT-> RIGHT -> DOWN -> DOWN.
-2 (K) | -3 | 3 |
---|---|---|
-5 | -10 | 1 |
10 | 30 | -5 (P) |
Note:
算法思路:
dp[i][j]
代表至少要有多少血生命才能到达[i,j]
还活着.dp_min = min(dp[i-1][j], dp[i][j-1])
,dp[i][j] = max(1, dp_min - dungeon[i][j])
class Solution{
public:
int calculateMinimumHP(std::vector<std::vector<int>> &dungeon){
if(dungeon.size() == 0){
return 0;
}
std::vector<std::vector<int>> dp(dungeon.size(), std::vector<int>(dungeon[0].size(), 0));
int row = dungeon.size();
int column = dungeon[0].size();
dp[row - 1][column - 1] = std::max(1, 1 - dungeon[row - 1][column - 1]);
for(int i = column - 2; i >= 0; i--){
dp[row - 1][i] = std::max(1, dp[row - 1][i + 1] - dungeon[row - 1][i]);
}
for(int i = row - 2; i >= 0; i--){
dp[i][column - 1] = std::max(1, dp[i + 1][column - 1] - dungeon[i][column - 1]);
}
for(int i = row - 2; i >= 0; i--){
for(int j = column - 2; j >= 0; j--){
int dp_min = std::min(dp[i + 1][j], dp[i][j + 1]);
dp[i][j] = std::max(1, dp_min - dungeon[i][j]);
}
}
return dp[0][0];
}
};
Given a m * n
matrix of ones and zeros, return how many square submatrices have all ones.
Example 1:
Input: matrix =
[
[0,1,1,1],
[1,1,1,1],
[0,1,1,1]
]
Output: 15
Explanation:
There are 10 squares of side 1.
There are 4 squares of side 2.
There is 1 square of side 3.
Total number of squares = 10 + 4 + 1 = 15.
Example 2:
Input: matrix =
[
[1,0,1],
[1,1,0],
[1,1,0]
]
Output: 7
Explanation:
There are 6 squares of side 1.
There is 1 square of side 2.
Total number of squares = 6 + 1 = 7.
Constraints:
1 <= arr.length <= 300
1 <= arr[0].length <= 300
0 <= arr[i][j] <= 1
class Solution{
public int countSquares(int[][] matrix){
int m = matrix.length;
int n = matrix[0].length;
int ans = 0;
int[][] dp = new int[m][n];
for(int i = 0; i < m; i++){
ans += dp[i][0] = matrix[i][0];
}
for(int i = 0; i < n; i++){
ans += dp[0][i] = matrix[0][i];
}
if(matrix[0][0] == 1){
ans--;
}
for(int i = 1; i < m; i++){
for(int j = 1; j < n; j++){
if(matrix[i][j] == 1) {
dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
ans += dp[i][j];
}
}
}
return ans;
}
}
Easy
Given a 2D grid
of size n
* m
and an integer k
. You need to shift the grid
k
times.
In one shift operation:
grid[i][j]
becomes at grid[i][j + 1]
.grid[i][m - 1]
becomes at grid[i + 1][0]
.grid[n - 1][m - 1]
becomes at grid[0][0]
.Return the 2D
grid after applying shift operation k
times.
Example 1:
Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1
Output: [[9,1,2],[3,4,5],[6,7,8]]
Example 2:
Input: grid = [[3,8,1,9],[19,7,2,5],[4,6,11,10],[12,0,21,13]], k = 4
Output: [[12,0,21,13],[3,8,1,9],[19,7,2,5],[4,6,11,10]]
Example 3:
Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 9
Output: [[1,2,3],[4,5,6],[7,8,9]]
Constraints:
1 <= grid.length <= 50
1 <= grid[i].length <= 50
-1000 <= grid[i][j] <= 1000
0 <= k <= 100
class Solution {
public:
vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
if(k == 0){
return grid;
}
int n = grid.size();
int m = grid[0].size();
vector<vector<int>> result(n, vector<int>(m, 0));
for(int cnt = 0; cnt < k; cnt++){
for(int i = 0; i < n; i++){
for(int j = 1; j < m; j++){
result[i][j] = grid[i][j - 1];
}
}
for(int i = 1; i < n; i++){
result[i][0] = grid[i - 1][m - 1];
}
result[0][0] = grid[n - 1][m - 1];
grid = result;
}
return result;
}
};
Medium
Given a binary tree with the following rules:
root.val == 0
treeNode.val == x
and treeNode.left != null
, then treeNode.left.val == 2 * x + 1
treeNode.val == x
and treeNode.right != null
, then treeNode.right.val == 2 * x + 2
Now the binary tree is contaminated, which means all treeNode.val
have been changed to -1
.
You need to first recover the binary tree and then implement the FindElements
class:
FindElements(TreeNode* root)
Initializes the object with a contamined binary tree, you need to recover it first.bool find(int target)
Return if the target
value exists in the recovered binary tree.Example 1:
Input
["FindElements","find","find"]
[[[-1,null,-1]],[1],[2]]
Output
[null,false,true]
Explanation
FindElements findElements = new FindElements([-1,null,-1]);
findElements.find(1); // return False
findElements.find(2); // return True
Example 2:
Input
["FindElements","find","find","find"]
[[[-1,-1,-1,-1,-1]],[1],[3],[5]]
Output
[null,true,true,false]
Explanation
FindElements findElements = new FindElements([-1,-1,-1,-1,-1]);
findElements.find(1); // return True
findElements.find(3); // return True
findElements.find(5); // return False
Example 3:
Input
["FindElements","find","find","find","find"]
[[[-1,null,-1,-1,null,-1]],[2],[3],[4],[5]]
Output
[null,true,false,false,true]
Explanation
FindElements findElements = new FindElements([-1,null,-1,-1,null,-1]);
findElements.find(2); // return True
findElements.find(3); // return False
findElements.find(4); // return False
findElements.find(5); // return True
Constraints:
TreeNode.val == -1
20
[1, 10^4]
find()
is between [1, 10^4]
0 <= target <= 10^6
Given an array nums
of integers, we need to find the maximum possible sum of elements of the array such that it is divisible by three.
Example 1:
Input: nums = [3,6,5,1,8]
Output: 18
Explanation: Pick numbers 3, 6, 1 and 8 their sum is 18 (maximum sum divisible by 3).
Example 2:
Input: nums = [4]
Output: 0
Explanation: Since 4 is not divisible by 3, do not pick any number.
Example 3:
Input: nums = [1,2,3,4,4]
Output: 12
Explanation: Pick numbers 1, 3, 4 and 4 their sum is 12 (maximum sum divisible by 3).。
Constraints:
1 <= nums.length <= 4 * 10^4
1 <= nums[i] <= 10^4
Hard
Storekeeper is a game, in which the player pushes boxes around in a warehouse, trying to get them to target locations.
The game is represented by a grid
of size n*``m
, where each element is a wall, floor or a box.
Your task is move the box 'B'
to the target position 'T'
under the following rules:
'S'
and can move up, down, left, right in the grid
if its a floor (empy cell).'.'
that means free cell to walk.'#'
that means obstacle (impossible to walk there).'B'
and one target cell 'T'
in the grid
.Return the minimum number of pushes to move the box to the target. If there is no way to reach the target, return -1
.
Example 1:
Input: grid = [["#","#","#","#","#","#"],
["#","T","#","#","#","#"],
["#",".",".","B",".","#"],
["#",".","#","#",".","#"],
["#",".",".",".","S","#"],
["#","#","#","#","#","#"]]
Output: 3
Explanation: We return only the number of times the box is pushed.
Example 2:
Input: grid = [["#","#","#","#","#","#"],
["#","T","#","#","#","#"],
["#",".",".","B",".","#"],
["#","#","#","#",".","#"],
["#",".",".",".","S","#"],
["#","#","#","#","#","#"]]
Output: -1
Example 3:
Input: grid = [["#","#","#","#","#","#"],
["#","T",".",".","#","#"],
["#",".","#","B",".","#"],
["#",".",".",".",".","#"],
["#",".",".",".","S","#"],
["#","#","#","#","#","#"]]
Output: 5
Explanation: push the box down, left, left, up and up.
Example 4:
Input: grid = [["#","#","#","#","#","#","#"],
["#","S","#",".","B","T","#"],
["#","#","#","#","#","#","#"]]
Output: -1
Constraints:
1 <= grid.length <= 20
1 <= grid[i].length <= 20
grid
contains only characters '.'
, '#'
, 'S'
, 'T'
, or 'B'
.'S'
, 'B'
and 'T'
in the grid
.Given two words (beginWord
and endWord
), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord
to endWord
, such that:
beginWord
is not a transformed word.Note:
beginWord
and endWord
are non-empty and are not the same.Example 1:
Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
Output:
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
Example 2:
Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
Output: []
Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.
struct Qitem{
std::string node;
int parent_pos;
int step;
Qitem(std::string _node, int _parent_pos, int _step): node(_node), parent_pos(_parent_pos), step(_step){}
};
class Solution{
public:
std::vector<std::vector<std::string>> findLadders(std::string beginWord,
std::string endWord, std::vector<std::string> &wordList){
std::map<std::string, std::vector<std::string>> graph;
construct_graph(beginWord, wordList, graph);
std::vector<Qitem> Q;
std::vector<int> end_word_pos;
BFS_graph(beginWord, endWord, graph, Q, end_word_pos);
std::vector<std::vector<std::string>> result;
for(int i = 0; i < end_word_pos.size(); i++){
int pos = end_word_pos[i];
std::vector<std::string> path;
while(pos != -1){
path.push_back(Q[pos].node);
pos = Q[pos].parent_pos;
}
result.push_back(std::vector<std::string>());
for(int j = path.size() - 1; j >= 0; j--){
result[i].push_back(path[j]);
}
}
return result;
}
private:
void BFS_graph(std::string &beginWord, std::string &endWord,
std::map<std::string, std::vector<std::string>> &graph,
std::vector<Qitem> &Q, std::vector<int> &end_word_pos){
std::map<std::string, int> visit;
int min_step = 0;
Q.push_back(Qitem(beginWord, -1, 1));
visit[beginWord] = 1;
int front = 0;
while(front != Q.size()){
const std::string &node = Q[front].node;
int step = Q[front].step;
if(min_step != 0 && step > min_step){
break;
}
if(node == endWord){
min_step = step;
end_word_pos.push_back(front);
}
const std::vector<std::string> &neighbors = graph[node];
for(int i = 0; i < neighbors.size(); i++){
if(visit.find(neighbors[i]) == visit.end() || visit[neighbors[i]] == step + 1){
Q.push_back(Qitem(neighbors[i], front, step + 1));
visit[neighbors[i]] = step + 1;
}
}
front++;
}
}
bool connect(const std::string &word1, const std::string &word2){ // 判断 word1 word2 是否可以转化
int cnt = 0;
for(int i = 0; i < word1.length(); i++){
if(word1[i] != word2[i]){
cnt++;
}
}
return cnt == 1;
}
void construct_graph(std::string &beginWord, std::vector<std::string> &wordList,
std::map<std::string, std::vector<std::string>> &graph){
int has_begin_word = 0;
for(int i = 0; i < wordList.size(); i++){
if(wordList[i] == beginWord){
has_begin_word = 1;
}
graph[wordList[i]] = std::vector<std::string>();
}
for(int i = 0; i < wordList.size(); i++){
for(int j = i + 1; j < wordList.size(); j++){
if(connect(wordList[i], wordList[j])){
graph[wordList[i]].push_back(wordList[j]);
graph[wordList[j]].push_back(wordList[i]);
}
}
if(has_begin_word == 0 && connect(beginWord, wordList[i])){
graph[beginWord].push_back(wordList[i]);
}
}
}
};
Given an integer array nums
, find the contiguous subarray
(containing at least one number) which has the largest sum and return its sum.
Example:
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Follow up:
If you have figured out the O(n)
solution, try coding another solution using the divide and conquer approach, which is more subtle.
分析:将求n
个数的数组的最大子段和转化为分别求出以第1
个、第2
个...第n
个数字结尾的最大子段和,再找出这n
结果中最大的,即为结果。
算法思路:
dp[i]
为以第i
个数字结尾的最大子段和;dp[i-1] > 0
则dp[i] = dp[i-1] + nums[i]
,否则dp[i] = nums[i]
;dp[0] = nums[0]
。class Solution{
public:
int maxSubArray(std::vector<int> &nums){
std::vector<int> dp(nums.size(), 0);
dp[0] = nums[0];
int max_res = dp[0];
for(int i = 1; i < nums.size(); i++){
dp[i] = std::max(dp[i - 1] + nums[i], nums[i]);
if(max_res < dp[i]){
max_res = dp[i];
}
}
return max_res;
}
};
Given a binary tree, flatten it to a linked list in-place.
For example, given the following tree:
1
/ \
2 5
/ \ \
3 4 6
The flattened tree should look like:
1
\
2
\
3
\
4
\
5
\
6
算法思路:
方法一:
push
进入vector
;vector
中的节点,将前面的节点的左指针置空,右指针与后面的节点相连。该方法可以通过题目,但是不满足in-place
的条件。
class Solution{
public:
void flatten(TreeNode* root){
std::vector<TreeNode*> node_vec;
preorder(root, node_vec);
for(int i = 1; i < node_vec.size(); i++){
node_vec[i - 1] -> left = NULL;
node_vec[i - 1] -> right = node_vec[i];
}
}
private:
void preorder(TreeNode* node, std::vector<TreeNode*> &node_vec){
if(!node){
return;
}
node_vec.push_back(node);
preorder(node -> left, node_vec);
preorder(node -> right, node_vec);
}
};
方法二:
class Solution{
public:
void flatten(TreeNode* root){
TreeNode* last = NULL;
preorder(root, last);
}
private:
void preorder(TreeNode* node, TreeNode* &last){
if(!node){
return;
}
if(!node -> left && !node -> right){
last = node;
return;
}
TreeNode* left = node -> left;
TreeNode* right = node -> right;
TreeNode* left_last = NULL;
TreeNode* right_last = NULL;
if(left){
preorder(left, left_last);
node -> left = NULL;
node -> right = left;
last = left_last;
}
if(right){
preorder(right, right_last);
if(left_last){
left_last -> right = right;
}
last = right_last;
}
}
};
There are a total of n
courses you have to take, labeled from 0
to n-1
.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
Example 1:
Input: 2, [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0.
So it is possible.
Example 2:
Input: 2, [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take
course 0 you should also have finished course 1. So it is impossible.
Note:
题意:已知有n
个课程,标记从0
到n-1
,课程之间是有依赖关系的,已知n
个课程的依赖关系,求是否可以将n
个课程全部完成。
分析:将课程看做顶点,课程见的依赖关系看成有向边,构造有向图;如果图中无环,则可以完成全部课程,否则不能。
方法一:
算法思路:
struct GraphNode{
int label;
std::vector<GraphNode*> neighbors;
GraphNode(int x): label(x){}
};
bool DFS_graph(GraphNode* node, std::vector<int> &visit){
visit[node -> label] = 0;
for(int i = 0; i < node -> neighbors.size(); i++){
if(visit[node -> neighbors[i] -> label] == -1){
if(DFS_graph(node -> neighbors[i], visit) == 0){
return false;
}
}
else if(visit[node -> neighbors[i] -> label] == 0){
return false;
}
}
visit[node -> label] = 1;
return true;
}
class Solution{
public:
bool canFinish(int numCourse, std::vector<std::vector<int>> &prequisites){
std::vector<GraphNode*> graph;
std::vector<int> visit;
for(int i = 0; i < numCourse; i++){
graph.push_back(new GraphNode(i));
visit.push_back(-1);
}
for(int i = 0; i < prequisites.size(); i++){
GraphNode* begin = graph[prequisites[i][1]];
GraphNode* end = graph[prequisites[i][0]];
begin -> neighbors.push_back(end);
}
for(int i = 0; i < graph.size(); i++){
if(visit[i] == -1 && !DFS_graph(graph[i], visit)){
return false;
}
}
for(int i = 0; i < numCourse; i++){
delete graph[i];
}
return true;
}
};
方法二:
算法思路:
0
的点添加至队列;0
则添加至队列;0
,则无环,否自有环。struct GraphNode{
int label;
std::vector<GraphNode*> neighbors;
GraphNode(int x): label(x){}
};
class Solution{
public:
bool canFinish(int numCourse, std::vector<std::vector<int>> &prerequisites){
std::vector<GraphNode*> graph;
std::vector<int> degree;
for(int i = 0; i < numCourse; i++){
degree.push_back(0);
graph.push_back(new GraphNode(i));
}
for(int i = 0; i < prerequisites.size(); i++){
GraphNode* begin = graph[prerequisites[i][1]];
GraphNode* end = graph[prerequisites[i][0]];
begin -> neighbors.push_back(end);
degree[prerequisites[i][0]]++;
}
std::queue<GraphNode*> Q;
for(int i = 0; i < numCourse; i++){
if(degree[i] == 0){
Q.push(graph[i]);
}
}
while(!Q.empty()){
GraphNode* node = Q.front();
Q.pop();
for(int i = 0; i < node -> neighbors.size(); i++){
degree[node -> neighbors[i] -> label]--;
if(degree[node -> neighbors[i] -> label] == 0){
Q.push(node -> neighbors[i]);
}
}
}
for(int i = 0; i < graph.size(); i++){
delete graph[i];
}
for(int i = 0; i < degree.size(); i++){
if(degree[i]){
return false;
}
}
return true;
}
};
Tic-tac-toe is played by two players A and B on a 3 x 3 grid.
Here are the rules of Tic-Tac-Toe:
Given an array moves where each element is another array of size 2 corresponding to the row and column of the grid where they mark their respective character in the order in which A and B play.
Return the winner of the game if it exists (A or B), in case the game ends in a draw return "Draw", if there are still movements to play return "Pending".
You can assume that moves is valid (It follows the rules of Tic-Tac-Toe), the grid is initially empty and A will play first.
Example 1:
Input: moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
Output: "A"
Explanation: "A" wins, he always plays first.
"X " "X " "X " "X " "X "
" " -> " " -> " X " -> " X " -> " X "
" " "O " "O " "OO " "OOX"
Example 2:
Input: moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]]
Output: "B"
Explanation: "B" wins.
"X " "X " "XX " "XXO" "XXO" "XXO"
" " -> " O " -> " O " -> " O " -> "XO " -> "XO "
" " " " " " " " " " "O "
Example 3:
Input: moves = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]]
Output: "Draw"
Explanation: The game ends in a draw since there are no moves to make.
"XXO"
"OOX"
"XOX"
Example 4:
Input: moves = [[0,0],[1,1]]
Output: "Pending"
Explanation: The game has not finished yet.
"X "
" O "
" "
Constraints:
算法思路:
[i,j]
代表二进制数的第3*i + j
位,没走一步棋等价于与对应的位进行异或运算。k
进行与运算,如果结果为k
,则此方获胜,若双方都未获胜则:
7, 56, 448, 73, 146, 292, 273, 84
public String tictactoe(int[][] moves) {
int a = 0, b = 0, len = moves.length;
int[] ac = {7, 56, 448, 73, 146, 292, 273, 84};
for(int i = 0; i < len; i++){
if((i & 1) == 1){
b ^= 1 << (3 * moves[i][0] + moves[i][1]);
}else{
a ^= 1 << (3 * moves[i][0] + moves[i][1]);
}
}
for(int i : ac){
if((a & i) == i){
return "A";
}
if((b & i) == i){
return "B";
}
}
return len == 9 ? "Draw" : "Pending";
}
Given a non-negative integer num
, Return its encoding string.
The encoding is done by converting the integer to a string using a secret function that you should deduce from the following table:
Example 1:
Input: num = 23
Output: "1000"
Example 2:
Input: num = 107
Output: "101100"
Constraints:
0 <= num <= 10^9
算法思路:将num+1
转化为二进制后删去第一位,以字符串的格式输出。
class Solution {
public:
string encode(int num) {
num += 1;
string str = "";
while(num){
str += to_string(num % 2);
num /= 2;
}
string result = "";
for(int i = str.size() - 2; i > 0; i--){
result += str[i];
}
return result;
}
};
Given two integers tomatoSlices
and cheeseSlices
. The ingredients of different burgers are as follows:
Return [total_jumbo, total_small]
so that the number of remaining tomatoSlices
equal to 0 and the number of remaining cheeseSlices
equal to 0. If it is not possible to make the remaining tomatoSlices
and cheeseSlices
equal to 0 return []
.
Example 1:
Input: tomatoSlices = 16, cheeseSlices = 7
Output: [1,6]
Explantion: To make one jumbo burger and 6 small burgers we need 4*1 + 2*6 = 16 tomato and 1 + 6 = 7 cheese. There will be no remaining ingredients.
Example 2:
Input: tomatoSlices = 17, cheeseSlices = 4
Output: []
Explantion: There will be no way to use all ingredients to make small and jumbo burgers.
Example 3:
Input: tomatoSlices = 4, cheeseSlices = 17
Output: []
Explantion: Making 1 jumbo burger there will be 16 cheese remaining and making 2 small burgers there will be 15 cheese remaining.
Example 4:
Input: tomatoSlices = 0, cheeseSlices = 0
Output: [0,0]
Example 5:
Input: tomatoSlices = 2, cheeseSlices = 1
Output: [0,1]
Constraints:
0 <= tomatoSlices <= 10^7
0 <= cheeseSlices <= 10^7
class Solution {
public List<Integer> numOfBurgers(int tomatoSlices, int cheeseSlices) {
List<Integer> result = new ArrayList<>();
if(tomatoSlices > 4 * cheeseSlices || tomatoSlices < 2 * cheeseSlices || tomatoSlices % 2 != 0){
return result;
}
int bigBurgers = tomatoSlices / 2 - cheeseSlices;
int smallBurgers = 2 * cheeseSlices - tomatoSlices / 2;
result.add(bigBurgers);
result.add(smallBurgers);
return result;
}
}
Given an array of strings, group anagrams together.
Example:
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
Note:
题意:已知一组字符串,将所有由颠倒的字母顺序构成的字放到一起输出。
算法思路:
方法一:
哈希表以内部进行排序的各个单词为key
,以字符串向量为value
,存储各个字符数量相同的字符串。
anagram
,便利字符串向量strs
中的单词strs[i]
:
str = strs[i]
,对str
进行排序。str
未出现在anagram
中,设置str
到一个空字符串向量的映射。str[i]
添加至字符串向量anagram[str]
中。anagram
,将全部key
对应的value
push
进最终结果中。class Solution{
public:
std::vector<std::vector<std::string>> groupAnagrams(
std::vector<std::string>& strs){
std::map<std::string, std::vector<std::string>> anagram;
std::vector<std::vector<std::string>> result;
for(int i = 0; i < strs.size(); i++){
std::string str = strs[i];
std::sort(str.begin(), str.end());
if(anagram.find(str) == anagram.end()){
std::vector<std::string> item;
anagram[str] = item;
}
anagram[str].push_back((strs[i]));
}
std::map<std::string, std::vector<std::string>> :: iterator it;
for(it = anagram.begin(); it != anagram.end(); it++){
result.push_back((*it).second);
}
return result;
}
};
方法二:
哈希表以26个字母的字符数量为key
,以字符串向量为value
,存储各个字符数量相同的字符串。
vector
到字符串向量的哈希表anagram
,遍历字符串向量strs
中的单词trs[i]
:
strs[i
]中的各个字符数量,存储至vec
。vec
未出现在anagram
中,设置一个vec
到一个空字符串向量的映射。strs[i]
添加到字符串向量anagram[vec]
中。anagram
,将全部key
对应的value
push
进最终的结果中。void change_to_vector(std::string &str, std::vector<int> &vec){
for(int i = 0; i < 26; i++) {
vec.push_back(0);
}
for(int i = 0; i < str.length(); i++) {
vec[str[i] - 'a']++;
}
}
class Solution{
public:
std::vector<std::vector<std::string>> groupAnagrams(
std::vector<std::string>& strs){
std::map<std::vector<int>, std::vector<std::string>> anagram;
std::vector<std::vector<std::string>> result;
for(int i = 0; i < strs.size(); i++){
std::vector<int> vec;
change_to_vector(strs[i], vec);
if(anagram.find(vec) == anagram.end()){
std::vector<std::string> item;
anagram[vec] = item;
}
anagram[vec].push_back(strs[i]);
}
std::map<std::vector<int>, std::vector<std::string>> :: iterator it;
for(it = anagram.begin(); it != anagram.end(); it++){
result.push_back((*it).second);
}
return result;
}
};
Remember the story of Little Match Girl? By now, you know exactly what matchsticks the little match girl has, please find out a way you can make one square by using up all those matchsticks. You should not break any stick, but you can link them up, and each matchstick must be used exactly one time.
Your input will be several matchsticks the girl has, represented with their stick length. Your output will either be true or false, to represent whether you could make one square using all the matchsticks the little match girl has.
Example 1:
Input: [1,1,2,2,2]
Output: true
Explanation: You can form a square with length 2, one side of the square came two sticks with length 1.
Example 2:
Input: [3,3,3,3,4]
Output: false
Explanation: You cannot find a way to form a square with all the matchsticks.
Note:
0
to 10^9
.15
.class Solution {
public boolean makesquare(int[] nums) {
if(nums.length < 4){
return false;
}
int sum = 0;
for(int i = 0; i < nums.length; i++){
sum += nums[i];
}
if(sum % 4 != 0){
return false;
}
Integer[] list = new Integer[nums.length];
for(int i = 0; i < nums.length; i++) list[i] = nums[i];
Arrays.sort(list);
for(int i = 0; i < nums.length; i++) nums[i] = list[i];
int[] bucket = new int[]{0 , 0 , 0 , 0};;
return generate(0, nums, sum / 4, bucket);
}
public boolean generate(int i, int[] nums, int target, int[] bucket){
if(i >= nums.length){
return bucket[0] == target && bucket[1] == target && bucket[2] == target && bucket[3] == target;
}
for(int j = 0; j < 4; j++){
if(bucket[j] + nums[i] > target){
continue;
}
bucket[j] += nums[i];
if(generate(i + 1, nums, target, bucket)){
return true;
}
bucket[j] -= nums[i];
}
return false;
}
}
Medium
Given a non-negative integer num
, Return its encoding string.
The encoding is done by converting the integer to a string using a secret function that you should deduce from the following table:
Example 1:
Input: num = 23
Output: "1000"
Example 2:
Input: num = 107
Output: "101100"
Constraints:
0 <= num <= 10^9
class Solution {
public:
string encode(int num) {
num += 1;
string str = "";
while(num){
str += to_string(num % 2);
num /= 2;
}
string result = "";
for(int i = str.size() - 2; i > 0; i--){
result += str[i];
}
return result;
}
};
Medium
You are given some lists of regions
where the first region of each list includes all other regions in that list.
Naturally, if a region X
contains another region Y
then X
is bigger than Y
.
Given two regions region1
, region2
, find out the smallest region that contains both of them.
If you are given regions r1
, r2
and r3
such that r1
includes r3
, it is guaranteed there is no r2
such that r2
includes r3
.
It's guaranteed the smallest region exists.
Example 1:
Input:
regions = [["Earth","North America","South America"],
["North America","United States","Canada"],
["United States","New York","Boston"],
["Canada","Ontario","Quebec"],
["South America","Brazil"]],
region1 = "Quebec",
region2 = "New York"
Output: "North America"
Constraints:
2 <= regions.length <= 10^4
region1 != region2
Medium
Given a list of pairs of equivalent words synonyms
and a sentencetext
.
Example 1:
Input:
synonyms = [["happy","joy"],["sad","sorrow"],["joy","cheerful"]],
text = "I am happy today but was sad yesterday"
Output:
["I am cheerful today but was sad yesterday",
"I am cheerful today but was sorrow yesterday",
"I am happy today but was sad yesterday",
"I am happy today but was sorrow yesterday",
"I am joy today but was sad yesterday",
"I am joy today but was sorrow yesterday"]
Constraints:
0 <= synonyms.length <= 10
synonyms[i].length == 2
synonyms[0] != synonyms[1]
10
English letters only.text
is a single space separated sentence of at most 10
words.Hard
You are given an even number of people num_people
that stand around a circle and each person shakes hands with someone else, so that there are num_people / 2
handshakes total.
Return the number of ways these handshakes could occur such that none of the handshakes cross.
Since this number could be very big, return the answer mod 10^9 + 7
Example 1:
Input: num_people = 2
Output: 1
Example 2:
Input: num_people = 4
Output: 2
Explanation: There are two ways to do it, the first way is [(1,2),(3,4)] and the second one is [(2,3),(4,1)].
Example 3:
Input: num_people = 6
Output: 5
Example 4:
Input: num_people = 8
Output: 14
Constraints:
2 <= num_people <= 1000
num_people % 2 == 0
Given a 2D grid
of size n
* m
and an integer k
. You need to shift the grid
k
times.
In one shift operation:
grid[i][j]
becomes at grid[i][j + 1]
.grid[i][m - 1]
becomes at grid[i + 1][0]
.grid[n - 1][m - 1]
becomes at grid[0][0]
.Return the 2D
grid after applying shift operation k
times.
Example 1:
Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1
Output: [[9,1,2],[3,4,5],[6,7,8]]
Example 2:
Input: grid = [[3,8,1,9],[19,7,2,5],[4,6,11,10],[12,0,21,13]], k = 4
Output: [[12,0,21,13],[3,8,1,9],[19,7,2,5],[4,6,11,10]]
Example 3:
Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 9
Output: [[1,2,3],[4,5,6],[7,8,9]]
Constraints:
1 <= grid.length <= 50
1 <= grid[i].length <= 50
-1000 <= grid[i][j] <= 1000
0 <= k <= 100
class Solution {
public:
vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
if(k == 0){
return grid;
}
int n = grid.size();
int m = grid[0].size();
vector<vector<int>> result(n, vector<int>(m, 0));
for(int cnt = 0; cnt < k; cnt++){
for(int i = 0; i < n; i++){
for(int j = 1; j < m; j++){
result[i][j] = grid[i][j - 1];
}
}
for(int i = 1; i < n; i++){
result[i][0] = grid[i - 1][m - 1];
}
result[0][0] = grid[n - 1][m - 1];
grid = result;
}
return result;
}
};
There are n
people whose IDs go from 0
to n - 1
and each person belongs exactly to one group. Given the array groupSizes
of length n
telling the group size each person belongs to, return the groups there are and the people's IDs each group includes.
You can return any solution in any order and the same applies for IDs. Also, it is guaranteed that there exists at least one solution.
Example 1:
Input: groupSizes = [3,3,3,3,3,1,3]
Output: [[5],[0,1,2],[3,4,6]]
Explanation:
Other possible solutions are [[2,1,6],[5],[0,4,3]] and [[5],[0,6,2],[4,3,1]].
Example 2:
Input: groupSizes = [2,1,3,3,3,2]
Output: [[1],[0,5],[2,3,4]]
Constraints:
groupSizes.length == n
1 <= n <= 500
1 <= groupSizes[i] <= n
算法思路:
Map<Integer, List<Integer>>
暂存每一个组,循环判断数组中的每一个元素,根据元素的值加入相应的map
中,如果组的大小等于key
的值,则将map
加入result
中,清空map
。class Solution{
public List<List<Integer>> groupThePeople(int[] groupSizes){
Map<Integer, List<Integer>> map = new HashMap<>();
List<List<Integer>> result = new ArrayList<>();
for(int i = 0; i < groupSizes.length; i++){
int flag = groupSizes[i];
if(! map.containsKey(flag))
map.put(flag, new ArrayList<>());
map.get(flag).add(i);
if(map.get(flag).size() == flag){
result.add(map.get(flag));
map.remove(flag);
}
}
return result;
}
}
You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1
.
Example 1:
Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
Example 2:
Input: coins = [2], amount = 3
Output: -1
Note:
You may assume that you have an infinite number of each kind of coin.
分析:贪心算法在个别面值的组合的时候是可以的,比如我们使用的人民币,但此题的面值不确定,故不能使用贪心算法;可以使用动态规划法。
算法思路:
dp[i]
代表金额i
的最优解,dp[0]、dp[1]...dp[n-1]
都是已知的;i
可由金额i-1
和面值1
组合、也可由金额i-2
和面值2
组合;dp[i] = min(dp[i-1], dp[i-2]...) + 1
class Solution{
public:
int coinChange(std::vector<int> &coins, int amount){
std::vector<int> dp;
for(int i = 0; i <= amount; i++){
dp.push_back(-1);
}
dp[0] = 0;
for(int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.size(); j++) {
if(i - coins[j] >= 0 && dp[i - coins[j]] != -1){
if(dp[i] == -1 || dp[i] > dp[i - coins[j]] + 1){
dp[i] = dp[i - coins[j]] + 1;
}
}
}
}
return dp[amount];
}
};
Given an unsorted array of integers, find the length of longest increasing subsequence.
Example:
Input: [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence
is [2,3,7,101], therefore the length is 4.
Note:
LIS
combination, it is only necessary for you to return the length.O(n^2)
complexity.Follow up: Could you improve it to O(nlogn)
time complexity?
方法一:
算法思路:
dp[]
,第i
个状态dp[i]
代表了以第i
个数结尾的最长上升子序列的长度;dp[0]=1
,初始化result=1
;1
到n-1
,循环i
,计算dp[i]
0
到i-1
循环j
,若nums[i] > nums[j]
说明nums[i]
可以放置在nums[j]
的后面,组成最长子序列;若dp[i] < dp[j] + 1
则dp[i] = dp[j] + 1
。class Solution{
public:
int lengthOfLIS(std::vector<int> &nums){
if(nums.size() == 0){
return 0;
}
std::vector<int> dp(nums.size(), 0);
dp[0] = 1;
int result = 1;
for(int i = 1; i < dp.size(); i++){
dp[i] = 1;
for(int j = 0; j < i; j++){
if(nums[i] > nums[j] && dp[i] < dp[j] + 1){
dp[i] = dp[j] + 1;
}
}
if(dp[i] > result){
result = dp[i];
}
}
return result;
}
};
方法二:
算法思路:
stack
,将nums[0]
push
进栈中1
到n-1
遍历数组
nums[i]
> 栈顶元素,将nums[i]
push
进栈中;nums[i]
< 栈顶元素,利用二分搜索找到第一个大于nums[i]
的元素,用nums[i]
替换。分析:此方法得出的栈中的元素并不是最长上升子序列,但是栈的大小的是最长上升子序列的大小。
int binary_search(std::vector<int> &nums, int target){
int index = -1;
int begin = 0;
int end = nums.size() - 1;
while(index == -1){
int mid = (begin + end) / 2;
if(target == nums[mid]){
index = mid;
}
else if(target < nums[mid]){
if(mid == 0 || target > nums[mid - 1]){
index = mid;
}
end = mid - 1;
}
else if(target > nums[mid]){
if(mid == nums.size() - 1 || target < nums[mid + 1]){
index = mid + 1;
}
begin = mid + 1;
}
}
return index;
}
class Solution{
public:
int lengthOfLIS(std::vector<int> &nums){
if(nums.size() == 0){
return 0;
}
std::vector<int> stack;
stack.push_back(nums[0]);
for(int i = 1; i < nums.size(); i++){
if(nums[i] > stack.back()){
stack.push_back(nums[i]);
}
else{
int pos = binary_search(stack, nums[i]);
stack[pos] = nums[i];
}
}
return stack.size();
}
};
Given a 2d
grid map of '1's
(land) and '0's
(water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
Input:
11110
11010
11000
00000
Output: 1
Example 2:
Input:
11000
11000
00100
00011
Output: 3
方法一:DFS
算法思路:
DFS
该位置。class Solution{
public:
void DFS(std::vector<std::vector<int>> &mark, std::vector<std::vector<char>> &grid, int x, int y){
mark[x][y] = 1;
static const int dx[] = {-1, 1, 0, 0};
static const int dy[] = {0, 0, -1, 1};
for(int i = 0; i < 4; i++){
int newx = dx[i] + x;
int newy = dy[i] + y;
if(newx < 0 || newx >= mark.size() || newy < 0 || newy >= mark[newx].size()){
continue;
}
if(mark[newx][newy] == 0 && grid[newx][newy] == '1'){
DFS(mark, grid, newx, newy);
}
}
}
int numIslands(std::vector<std::vector<char>> &grid){
int island_num = 0;
std::vector<std::vector<int>> mark;
for(int i = 0; i < grid.size(); i++){
mark.push_back(std::vector<int>());
for(int j = 0; j < grid[i].size(); j++){
mark[i].push_back(0);
}
}
for(int i = 0; i < grid.size(); i++){
for(int j = 0; j < grid[i].size(); j++){
if(mark[i][j] == 0 && grid[i][j] == '1'){
DFS(mark, grid, i, j);
island_num++;
}
}
}
return island_num;
}
};
方法二:BFS
算法思路:
Q
,标记mark[i][j] = 1
,并将待搜索位置(x, y)
push进队列;newx, newy
;mark[newx][newy] = 1
class Solution{
public:
void BFS(std::vector<std::vector<int>> &mark, std::vector<std::vector<char>> &grid, int x, int y){
static const int dx[] = {-1, 1, 0, 0};
static const int dy[] = {0, 0, -1, 1};
std::queue<std::pair<int, int>> Q;
Q.push(std::make_pair(x, y));
mark[x][y] = 1;
while(!Q.empty()){
x = Q.front().first;
y = Q.front().second;
Q.pop();
for(int i = 0; i < 4; i++){
int newx = dx[i] + x;
int newy = dy[i] + y;
if(newx < 0 || newx >= mark.size() || newy < 0 || newy >= mark[newx].size()){
continue;
}
if(mark[newx][newy] == 0 && grid[newx][newy] == '1'){
Q.push(std::make_pair(newx, newy));
mark[newx][newy] = 1;
}
}
}
}
int numIslands(std::vector<std::vector<char>> &grid){
int island_num = 0;
std::vector<std::vector<int>> mark;
for(int i = 0; i < grid.size(); i++){
mark.push_back(std::vector<int>());
for(int j = 0; j < grid[i].size(); j++){
mark[i].push_back(0);
}
}
for(int i = 0; i < grid.size(); i++){
for(int j = 0; j < grid[i].size(); j++){
if(mark[i][j] == 0 && grid[i][j] == '1'){
BFS(mark, grid, i, j);
island_num++;
}
}
}
return island_num;
}
};
Given head which is a reference node to a singly-linked list. The value of each node in the linked list is either 0 or 1. The linked list holds the binary representation of a number.
Return the decimal value of the number in the linked list.
Example 1:
Input: head = [1,0,1]
Output: 5
Explanation: (101) in base 2 = (5) in base 10
Example 2:
Input: head = [0]
Output: 0
Example 3:
Input: head = [1]
Output: 1
Example 4:
Input: head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0]
Output: 18880
Example 5:
Input: head = [0,0]
Output: 0
Constraints:
class Solution {
public:
int getDecimalValue(ListNode* head) {
if(head == NULL)
return 0;
if(head->next == NULL)
return head->val;
int num = 0;
while (head){
num *= 2;
num += head->val;
head = head -> next;
}
return num;
}
};
An integer has sequential digits if and only if each digit in the number is one more than the previous digit.
Return a sorted list of all the integers in the range [low, high]
inclusive that have sequential digits.
Example 1:
Input: low = 100, high = 300
Output: [123,234]
Example 2:
Input: low = 1000, high = 13000
Output: [1234,2345,3456,4567,5678,6789,12345]
Constraints:
算法思路:一共36个数,通过打表即可解决。
class Solution {
public List<Integer> sequentialDigits(int low, int high) {
int[] list = {12, 23, 34, 45, 56, 67, 78, 89,
123, 234, 345, 456, 567, 678, 789,
1234, 2345, 3456, 4567, 5678, 6789,
12345, 23456, 34567, 45678, 56789,
123456, 234567, 345678, 456789,
1234567, 2345678, 3456789,
12345678, 23456789,
123456789};
List result = new LinkedList();
for(int i = 0; i < list.length; i++){
if(list[i] <= high && list[i] >= low){
result.add(list[i]);
}
}
return result;
}
}
Given a m x n matrix mat and an integer threshold. Return the maximum side-length of a square with a sum less than or equal to threshold or return 0 if there is no such square.
Example 1:
Input: mat = [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]], threshold = 4
Output: 2
Explanation: The maximum side length of square with sum less than 4 is 2 as shown.
Example 2:
Input: mat = [[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2]], threshold = 1
Output: 0
Example 3:
Input: mat = [[1,1,1,1],[1,0,0,0],[1,0,0,0],[1,0,0,0]], threshold = 6
Output: 3
Example 4:
Input: mat = [[18,70],[61,1],[25,85],[14,40],[11,96],[97,96],[63,45]], threshold = 40184
Output: 2
Constraints:
1 <= m, n <= 300
m == mat.length
n == mat[i].length
0 <= mat[i][j] <= 10000
0 <= threshold <= 10^5
class Solution {
public int maxSideLength(int[][] mat, int threshold) {
int result = 0;
for(int i = 0; i < mat.length; i++){
for(int j = 0; j < mat[0].length; j++){
if(j != 0){
mat[i][j] += mat[i][j - 1];
}
int len = 0;
int maxlen = Math.min(i, j) + 1;
while (len < maxlen){
int area = 0;
for(int k = 0; k < len + 1; k++){
int prefix = j - len - 1 < 0 ? 0 : mat[i - k][j - len - 1];
area += mat[i - k][j] - prefix;
}
if(area > threshold) {
break;
}
len++;
}
result = len > result ? len : result;
}
}
return result;
}
}
Given a list of words
, list of single letters
(might be repeating) and score
of every character.
Return the maximum score of any valid set of words formed by using the given letters (words[i]
cannot be used two or more times).
It is not necessary to use all characters in letters
and each letter can only be used once. Score of letters 'a'
, 'b'
, 'c'
, ... ,'z'
is given by score[0]
, score[1]
, ... , score[25]
respectively.
Example 1:
Input: words = ["dog","cat","dad","good"], letters = ["a","a","c","d","d","d","g","o","o"], score = [1,0,9,5,0,0,3,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0]
Output: 23
Explanation:
Score a=1, c=9, d=5, g=3, o=2
Given letters, we can form the words "dad" (5+1+5) and "good" (3+2+2+5) with a score of 23.
Words "dad" and "dog" only get a score of 21.
Example 2:
Input: words = ["xxxz","ax","bx","cx"], letters = ["z","a","b","c","x","x","x"], score = [4,4,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,5,0,10]
Output: 27
Explanation:
Score a=4, b=4, c=4, x=5, z=10
Given letters, we can form the words "ax" (4+5), "bx" (4+5) and "cx" (4+5) with a score of 27.
Word "xxxz" only get a score of 25.
Example 3:
Input: words = ["leetcode"], letters = ["l","e","t","c","o","d"], score = [0,0,1,1,1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0]
Output: 0
Explanation:
Letter "e" can only be used once.
Constraints:
1 <= words.length <= 14
1 <= words[i].length <= 15
1 <= letters.length <= 100
letters[i].length == 1
score.length == 26
0 <= score[i] <= 10
words[i]
, letters[i]
contains only lower case English letters.算法思路:
1<<word.size()
种情况,bit&(1<< i)
为真表明取到了第i
个单词;class Solution{
public:
vector<int> group(vector<string> &words, int bit){
vector<int> g(26, 0);
for(int i = 0; i < words.size(); i++){
if(bit & (1 << i)){
for(auto c : words[i]){
g[c - 'a']++;
}
}
}
return g;
}
int maxScoreWords(vector<string> &words, vector<char> &letters, vector<int> &score){
vector<int> l(26, 0);
for(auto c : letters){
l[c - 'a']++;
}
int result = 0;
for(int i = 0; i < (1 << words.size()); i++){
auto g = group(words, i);
int temp = 0;
for(int j = 0; j < 26; j++){
if(l[j] < g[j]){
temp = 0;
break;
}
else{
temp += g[j] * score[j];
}
}
result = max(result, temp);
}
return result;
}
};
Given a binary tree, find the lowest common ancestor (LCA)
of two given nodes in the tree.
According to the definition of
LCA
onWikipedia
: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.
Example 2:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a
descendant of itself according to the LCA definition.
Note:
题意:给定二叉树和两个数,找出两个数的最近公共祖先。
解题思路:
q
和p
的路径上最后一个相同节点。void preorder(TreeNode* node, TreeNode* search,
std::vector<TreeNode*> &path, std::vector<TreeNode*> &result, int &finish){
if(!node || finish){
return;
}
path.push_back(node);
if(node == search){
finish = 1;
result = path;
}
preorder(node -> left, search, path, result, finish);
preorder(node -> right, search, path, result, finish);
path.pop_back();
}
class Solution{
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q){
std::vector<TreeNode*> path;
std::vector<TreeNode*> node_p_path;
std::vector<TreeNode*> node_q_path;
int finish = 0;
preorder(root, p, path, node_p_path, finish);
path.clear();
finish = 0;
preorder(root, q, path,node_q_path, finish);
int path_len = 0;
if(node_p_path.size() < node_q_path.size()){
path_len = node_p_path.size();
}
else{
path_len = node_q_path.size();
}
TreeNode* result = 0;
for(int i = 0; i < path_len; i++){
if(node_p_path[i] == node_q_path[i]){
result = node_p_path[i];
}
}
return result;
}
};
Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
Example:
Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation:
1 <---
/ \
2 3 <---
\ \
5 4 <---
题意:这题就是求二叉树每层的最右边的节点。
算法思路:
pair
,压入队列中;view
中。class Solution{
public:
std::vector<int> rightSideView(TreeNode* root){
std::vector<int> view;
std::queue<std::pair<TreeNode*, int>> Q;
if(root){
Q.push(std::make_pair(root, 0));
}
while(!Q.empty()){
TreeNode* node = Q.front().first;
int depth = Q.front().second;
Q.pop();
if(view.size() == depth){
view.push_back(node -> val);
}
else{
view[depth] = node -> val;
}
if(node -> left){
Q.push(std::make_pair(node -> left, depth + 1));
}
if(node -> right){
Q.push(std::make_pair(node -> right, depth + 1));
}
}
return view;
}
};
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.