Description

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring.
The same letter cell may not be used more than once.

Example:

1
2
3
4
5
6
7
8
9
10

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

Constraints:

• board and word consists only of lowercase and uppercase English letters.
• 1 <= board.length <= 200
• 1 <= board[i].length <= 200
• 1 <= word.length <= 10^3

Difficulty: Medium

Code:

1
2
3
4
5

class Solution {
    public boolean exist(char[][] board, String word) {
        
    }
}

题意

给定一个2D的棋盘和一个单词，找出单词是否在网格出现。单词可以从有序相邻的单元格中构造，同一个字符只能用一次。

原二维数组就像一个迷宫，可以上下左右四个方向走，可以以每个数都作为起点来走。

Description

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

1
2
3
4
5
6
7
8
9
10
11
12

Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Difficulty: Medium

Code:

1
2
3
4
5

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        
    }
}

题意

给定一组不重复的数字，返回所有不重复的子集。

Description

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

Example:

1
2
3
4
5
6
7
8
9
10

Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Difficulty: Medium

Code:

1
2
3
4
5

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        
    }
}

题意

给定数字n和k，从数字1到n中返回k个数字到所有组合。

Description

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:

1
2

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Note:

• If there is no such window in S that covers all characters in T, return the empty string “”.
• If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

Difficulty: Hard

Code:

1
2
3
4
5

class Solution {
    public String minWindow(String s, String t) {
        
    }
}

题意

给定一个字符串S和字符串T，从S中找出最短的子字符串能包含T中所有的字符，复杂度要求O(n)。

Description

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note: You are not suppose to use the library’s sort function for this problem.

Example:

1
2

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Follow up:

• A rather straight forward solution is a two-pass algorithm using counting sort.
  First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2’s.
• Could you come up with a one-pass algorithm using only constant space?

Difficulty: Medium

Code:

1
2
3
4
5

class Solution {
    public void sortColors(int[] nums) {
        
    }
}

题意

一个数组用数字表示颜色，0表示红色，1表示白色，2表示蓝色，将数字按照从0到1到顺序排序。要求不能使用排序API，看能否只遍历一遍数组。