最近偶然间翻到了CranBerries 的MV,虽然年代久远,画质略渣,但也丝毫不影响体会的感觉,MV主唱头戴花环披肩长发+素色长裙的搭配甚是喜欢,里面站在窗边凝视远方呜呜和在院子里赤脚跳舞的片段也着实动人……




The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P A H N

A P L S I I G

Y I R

And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
public String convert(String s, int nRows) {
if (nRows == 1) {
return s;
}

int num = nRows*2 - 2;
int len = s.length();

StringBuilder sb = new StringBuilder();


for (int i = 0; i < nRows; i++) {
for (int j = i; j < len; j += num) {
sb.append(s.charAt(j));
if (i != 0 && 2*i != num && j + num - 2*i < len) {
sb.append(s.charAt(j + num - 2*i));
}
}
}

return sb.toString();
}
}

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

  1. Only one letter can be changed at a time
  2. Each intermediate word must exist in the dictionary
    For example,

Given:
start = “hit”
end = “cog”
dict = [“hot”,”dot”,”dog”,”lot”,”log”]
Return

[
  ["hit","hot","dot","dog","cog"],
  ["hit","hot","lot","log","cog"]
]

Note:

  • All words have the same length.
  • All words contain only lowercase alphabetic characters.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
public class Solution {


ArrayList<ArrayList<String>> buildPath(Map<String,Set<String>> father, String start, String end) {
ArrayList<ArrayList<String>> ret = new ArrayList<ArrayList<String>>();

if (end.equals(start)) {
ArrayList<String> list = new ArrayList<String>();
list.add(start);
ret.add(list);
return ret;
}

for (String parent : father.get(end)) {
ArrayList<ArrayList<String>>paths = buildPath(father,start,parent);
for (ArrayList<String> path : paths) {
path.add(end);
ret.add(path);
}
}

return ret;
}


public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict) {
if (start == null || end == null || dict.isEmpty()) {
return new ArrayList<ArrayList<String>>();
}

boolean isFound = false;

ArrayList<ArrayList<String>> ret = new ArrayList<ArrayList<String>>();

Map<String,Set<String>> father = new HashMap<String,Set<String>>();

Map<String,Integer> level = new HashMap<String, Integer>();

List<String> queue = new ArrayList<String>();
queue.add(start);
level.put(start,0);

int cnt = 1;

while (!queue.isEmpty() && !isFound) {

ArrayList<String> founded = new ArrayList<String>();

for (String s : queue) {
char[] ch = s.toCharArray();

for (int i = 0; i < ch.length; i++) {
char c = ch[i];

for (char d = 'a'; d <= 'z'; d ++) {
ch[i] = d;
String str = new String(ch);

if (dict.contains(str)) {
if (father.containsKey(str)) {
if (cnt == level.get(str)) {
father.get(str).add(s);
}
} else {
founded.add(str);
level.put(str,cnt);

father.put(str,new HashSet<String>());
father.get(str).add(s);
}
}

if (str.equals(end)) {
isFound = true;
}
}
ch[i] = c;
}
}

queue = founded;
cnt ++;

}

if (isFound) {
return buildPath(father,start,end);
} else {
return new ArrayList<ArrayList<String>>();
}


}
}

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

  1. Only one letter can be changed at a time
  2. Each intermediate word must exist in the dictionary
    For example,

Given:
start = “hit”
end = “cog”
dict = [“hot”,”dot”,”dog”,”lot”,”log”]
As one shortest transformation is “hit” -> “hot” -> “dot” -> “dog” -> “cog”,
return its length 5.

Note:

  • Return 0 if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
public class Solution {
public int ladderLength(String start, String end, HashSet<String> dict) {

if (start == null || end == null || dict == null || dict.isEmpty()) {
return 0;
}

List<String> queue = new ArrayList<String>();
queue.add(start);


Set<String> visited = new HashSet<String>();

boolean isFound = false;

int level = 1;

while (!queue.isEmpty() && !isFound) {

List<String> newFound = new ArrayList<String>();

for (String s : queue) {
if (isFound) {
break;
}
char[] ch = s.toCharArray();

// find

for (int i = 0; i < ch.length; i++) {
char c = ch[i];

for (char d = 'a'; d <= 'z'; d++) {
ch[i] = d;
String newStr = new String(ch);

if (newStr.equals(end)) {
isFound = true;
break;
}

if (dict.contains(newStr) && !visited.contains(newStr)) {
visited.add(newStr);
newFound.add(newStr);
}
}

ch[i] = c;
}
}

level ++;
queue = newFound;
}

return isFound ? level : 0;

}
}

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = “catsanddog”,
dict = [“cat”, “cats”, “and”, “sand”, “dog”].

A solution is [“cats and dog”, “cat sand dog”].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
public class Solution {


ArrayList<String> build(int[][] dp, Map<Integer,String> strMap, String s) {
ArrayList<String> ret = new ArrayList<String>();
if (s.equals("")) {
ret.add("");
return ret;
}

if (dp[s.length()][0] == 0) {
return ret;
}

for (int i = 1; i <= strMap.size(); i++) {
if (dp[s.length()][i] == 1) {
ArrayList<String> parent = build(dp,strMap, s.substring(0,s.length()-strMap.get(i-1).length()));
for (String ss : parent) {
ret.add(ss.equals("")?strMap.get(i-1):ss + " " + strMap.get(i-1));
}
}
}

return ret;

}




public ArrayList<String> wordBreak(String s, Set<String> dict) {
ArrayList<String> ret = new ArrayList<String>();

if (s == null || s.length() == 0) {
return ret;
}
int maxLen = 0;
Map<String,Integer> idxMap = new HashMap<String,Integer>();
Map<Integer, String> strMap = new HashMap<Integer,String>();
int idx = 0;

for (String w : dict) {
maxLen = Math.max(maxLen,w.length());
strMap.put(idx,w);
idxMap.put(w,idx++);
}

int len = s.length();
int cnt = dict.size();

int[][] dp = new int[len+1][cnt+1];
dp[0][0] = 1;

for (int i = 1; i <= len; i++) {
if (dp[i-1][0] == 0) {
continue;
}

for (int j = i; j < i + maxLen && j <= s.length(); j++) {
String sub = s.substring(i-1,j);
if (dict.contains(sub)) {
dp[j][0] = 1;
dp[j][idxMap.get(sub)+1] = 1;
}
}
}

return build(dp,strMap,s);

}
}

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = “leetcode”,
dict = [“leet”, “code”].

Return true because “leetcode” can be segmented as “leet code”.

思路0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class Solution {
public boolean wordBreak(String s, Set<String> dict) {

int len = s.length();

int[] dp = new int [len];

for (int i = 0; i < len; i++) {
String sub = s.substring(0,i + 1);
if (dict.contains(sub)) {
dp[i] = 1;
}

for (int j = 0; j < i; j++) {
if (dp[j] == 1) {
String sub2 = s.substring(j+1,i+1);
if (dict.contains(sub2)) {
dp[i] = 1;
break;
}
}
}
}

return dp[len-1] == 1;



}
}

Implement wildcard pattern matching with support for ‘?’ and ‘*’.

‘?’ Matches any single character. ‘*’ Matches any sequence of

characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be: bool isMatch(const char *s, const

char *p)

Some examples:

isMatch(“aa”,”a”) → false isMatch(“aa”,”aa”) → true

isMatch(“aaa”,”aa”) → false isMatch(“aa”, “*”) → true

isMatch(“aa”,”a*”) → true

isMatch(“ab”, “?“) → true isMatch(“aab”, “ca*b”) → false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
bool isMatch(const char *s, const char *p) {
bool star = false;
const char *str, *ptr;
for (str = s, ptr = p; *str != '\0'; str++, ptr++) {
switch (*ptr) {
case '?':
break;
case '*':
star = true;
s = str, p = ptr;
while (*p == '*') p++; //skip continuous '*'
if (*p == '\0') return true;
str = s - 1;
ptr = p - 1;
break;
default:
if (*str != *ptr) {
// 如果前面没有'*',则匹配不成功
if (!star) return false;
s++;
str = s - 1;
ptr = p - 1;
}
}
}
while (*ptr == '*') ptr++;
return (*ptr == '\0');
}
};.

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.
confused what “{1,#,2,3}” means? > read more on how binary tree is serialized on OJ.

OJ’s Binary Tree Serialization:
The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.

Here’s an example:

  1
 / \
2   3
   /
  4
   \
    5

The above binary tree is serialized as “{1,2,3,#,#,4,#,#,5}”.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/

public class Solution {

int last = Integer.MIN_VALUE;


boolean check(TreeNode top, int min, int max) {
if (top == null) {
return true;
}


if (top.val <= min || top.val >= max) {
return false;
}


boolean ret = true;
ret &= check(top.left,min,top.val);
ret &= check(top.right,top.val,max);

return ret;
}


public boolean isValidBST(TreeNode root) {



return check(root, Integer.MIN_VALUE, Integer.MAX_VALUE);

}
}

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character ‘.’.
enter image description here

A partially filled sudoku which is valid.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public class Solution {
public boolean isValidSudoku(char[][] board) {
// row
for (int i = 0; i < 9; i++) {
int mask = 0;
for (int j = 0; j < 9; j++) {
if (board[i][j] == '.') {
continue;
}
int d = board[i][j] - '0';
if ((mask & (1 << d)) != 0) {
return false;
}
mask |= (1<<d);
}
}
// column
for (int i = 0; i < 9; i++) {
int mask = 0;
for (int j = 0; j < 9; j++) {
if (board[j][i] == '.') {
continue;
}
int d = board[j][i] - '0';
if ((mask & (1 << d)) != 0) {
return false;
}
mask |= (1<<d);
}
}
// block
for (int i = 0; i < 3 ; i++) {
for (int j = 0; j < 3; j++) {
int mask = 0;
for (int k = 0; k < 9; k++) {
if (board[3*i+k/3][3*j+k%3] == '.') {
continue;
}
int d = board[3*i+k/3][3*j+k%3] - '0';
if ((mask & (1<<d))!=0) {
return false;
}
mask |= (1<<d);
}
}
}

return true;

}
}

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.

For example,
Given board =

[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]

word = “ABCCED”, -> returns true,
word = “SEE”, -> returns true,
word = “ABCB”, -> returns false.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
public class Solution {
public boolean exist(char[][] board, String word) {

if (word == null || word.equals("")) {
return true;
}

if (board == null || board.length == 0 || board[0] == null || board[0].length == 0) {
return false;
}


int h = board.length;
int w = board[0].length;

int[][] mark = new int[h][w];

//int arr[] = new char[word.length()];

for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (search(board,mark,i,j,0,word)) {
return true;
}
}
}

return false;

}

boolean search(char[][] board, int[][] mark, int i, int j, int cnt, String word) {
int h = board.length;
int w = board[0].length;

if (cnt == word.length()) {
return true;
}

if (i < 0 || i >= h || j < 0 || j >= w) {
return false;
}

if (mark[i][j] == 1 ) {
return false;
}

if ( board[i][j] != word.charAt(cnt) ){
return false;
}


mark[i][j] = 1;

boolean ret =
search(board,mark,i+1,j,cnt+1,word)
|| search(board,mark,i-1,j,cnt+1,word)
|| search(board,mark,i,j+1,cnt+1,word)
|| search(board,mark,i,j-1,cnt+1,word) ;


mark[i][j] = 0;

return ret;






}
}