发表于   |   分类于 ，   |   ❤

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/10/06/2013-10-06-CODE 63 Sqrt(x)/

访问原文「CODE 63. Sqrt(x)」

Implement int sqrt(int x).
Compute and return the square root of x.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int sqrt(int x) {
	// Note: The Solution object is instantiated only once and is reused by
	// each test case.
	if (x <= 0) {
		return 0;
	}
	double pre = -1.0;
	double cur = 1.0;
	while (Math.abs(pre - cur) > 0.00001) {
		pre = cur;
		cur = (cur + x / cur) / 2;
	}
	return (int) cur;
}

发表于   |   分类于 ，   |   ❤

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/10/06/2013-10-06-CODE 62 Climbing Stairs/

访问原文「CODE 62. Climbing Stairs」

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?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int climbStairs(int n) {
	// Note: The Solution object is instantiated only once and is reused by
	// each test case.
	if (n <= 0) {
		return 0;
	} else if (1 == n) {
		return 1;
	} else if (2 == n) {
		return 2;
	}
	int[] ways = new int[n + 1];
	ways[1] = 1;
	ways[2] = 2;
	for (int i = 3; i <= n; i++) {
		ways[i] = ways[i - 1] + ways[i - 2];
	}
	return ways[n];
}

发表于   |   分类于 ，   |   ❤

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/10/06/2013-10-06-CODE 61 Simplify Path/

访问原文「CODE 61. Simplify Path」

Given an absolute path for a file (Unix-style), simplify it.
For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

click to show corner cases.
Corner Cases:

  • Did you consider the case where path = "/../"?
    In this case, you should return "/".
  • Another corner case is the path might contain multiple slashes '/' together,
    such as "/home//foo/".
    In this case, you should ignore redundant slashes and return "/home/foo".
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
public String simplifyPath(String path) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (null == path || "".equals(path) || !path.startsWith("/")) {
		return "";
	}
	List<String> pathList = new ArrayList<String>();
	char[] paths = path.toCharArray();
	StringBuilder sb = new StringBuilder();
	for (int i = 0; i < paths.length; i++) {
		if (paths[i] == '/') {
			if (!sb.toString().equals("")) {
				if (!sb.toString().equals(".")
						&& !sb.toString().equals("..")) {
					pathList.add(sb.toString());
				} else if (sb.toString().equals("..")) {
					if (!pathList.isEmpty()) {
						pathList.remove(pathList.size() - 1);
					}
				}
				sb = null;
				sb = new StringBuilder();
			}
		} else {
			sb.append(paths[i]);
		}
	}
	if (!sb.toString().equals("")) {
		if (!sb.toString().equals(".") && !sb.toString().equals("..")) {
			pathList.add(sb.toString());
		} else if (sb.toString().equals("..")) {
			if (!pathList.isEmpty()) {
				pathList.remove(pathList.size() - 1);
			}
		}
	}
	if (pathList.isEmpty()) {
		return "/";
	} else {
		sb = null;
		sb = new StringBuilder();
		for (String s : pathList) {
			sb.append("/" + s);
		}
		return sb.toString();
	}
}

发表于   |   分类于 ，   |   ❤

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/10/05/2013-10-05-CODE 60 Set Matrix Zeroes/

访问原文「CODE 60. Set Matrix Zeroes」

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.click to show follow up.
Follow up:Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m+n) space, but still not the best solution.
Could you devise a constant space solution?

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
public void setZeroes(int[][] matrix) {
	// Note: The Solution object is instantiated only once and is reused by
	// each test case.
	int zeroH = -1;
	int rows = matrix.length;
	int cols = matrix[0].length;
	if (0 == matrix[0][0]) {
		zeroH = 0;
	}
	for (int i = 1; i < rows; i++) {
		if (0 == matrix[i][0]) {
			matrix[0][0] = 0;
			break;
		}
	}
	for (int i = 1; i < cols; i++) {
		if (0 == matrix[0][i]) {
			zeroH = 0;
			break;
		}
	}
	for (int i = 1; i < rows; i++) {
		for (int j = 1; j < cols; j++) {
			if (0 == matrix[i][j]) {
				matrix[i][0] = 0;
				matrix[0][j] = 0;
			}
		}
	}
	for (int i = 1; i < rows; i++) {
		if (0 == matrix[i][0]) {
			for (int j = 0; j < cols; j++) {
				matrix[i][j] = 0;
			}
		}
	}
	for (int i = 0; i < cols; i++) {
		if (0 == matrix[0][i]) {
			for (int j = 0; j < rows; j++) {
				matrix[j][i] = 0;
			}
		}
	}
	if (0 == zeroH) {
		for (int j = 0; j < cols; j++) {
			matrix[0][j] = 0;
		}
	}
}

发表于   |   分类于 ，   |   ❤

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/10/04/2013-10-04-CODE 59 Search a 2D Matrix/

访问原文「CODE 59. Search a 2D Matrix」

Write an efficient algorithm that searches for a value in anmxnmatrix. This matrix has the following properties:

  • Integers in each row are sorted from left to right.
  • The first integer of each row is greater than the last integer of the previous row.

For example,
Consider the following matrix:
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]

Giventarget=3, returntrue.

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
public boolean searchMatrix(int[][] matrix, int target) {
	// Note: The Solution object is instantiated only once and is reused by
	// each test case.
	if (null == matrix || matrix.length <= 0) {
		return false;
	}
	int rows = matrix.length;
	int cols = matrix[0].length;
	int all = rows * cols;
	boolean finded = false;
	int i;
	for (i = 0; i < all - 1; i++) {
		if (matrix[i / cols][i % cols] > matrix[(i + 1) / cols][(i + 1)
				% cols]) {
			break;
		}
		if (matrix[i / cols][i % cols] == target) {
			finded = true;
		}
	}
	if (i < all - 1) {
		return false;
	} else if (matrix[rows - 1][cols - 1] == target) {
		finded = true;
	}
	return finded;
}

发表于   |   分类于 ，   |   ❤

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/10/04/2013-10-04-CODE 58 Sort Colors/

访问原文「CODE 58. Sort Colors」

Given an array with n objects colored red, white or blue, sort them 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.
click to show follow up.
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 an one-pass algorithm using only constant space?

WORST CODE:

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
public void sortColors(int[] A) {
	// Note: The Solution object is instantiated only once and is reused by
	// each test case.
	// 012012012012
	int start = 0;
	int end = A.length - 1;
	while (start < A.length && A[start] == 0) {
		start++;
	}
	while (end > 0 && A[end] == 2) {
		end--;
	}
	for (int mid = start; mid <= end; mid++) {
		if (A[mid] == 0) {
			int tmp = A[mid];
			A[mid] = A[start];
			A[start] = tmp;
			start++;
			while (start < A.length && A[start] == 0) {
				start++;
			}
			mid = start - 1;
		} else if (mid != end && A[mid] == 2) {
			int tmp = A[mid];
			A[mid] = A[end];
			A[end] = tmp;
			end--;
			mid--;
			while (end > 0 && A[end] == 2) {
				end--;
			}
		}
	}
}

发表于   |   分类于 ，   |   ❤

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/10/04/2013-10-04-CODE 57 Minimum Window Substring/

访问原文「CODE 57. Minimum Window Substring」

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).For example,
S="ADOBECODEBANC"
T="ABC"

Minimum window is"BANC".
Note:
If there is no such window in S that covers all characters in T, return the emtpy string"".
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
WORST CODE:

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
95
96
97
98
public String minWindow(String S, String T) {
	// Note: The Solution object is instantiated only once and is reused by
	// each test case.
	if (T.length() > S.length()) {
		return "";
	}
	Map<Character, Integer> table = new HashMap<Character, Integer>();
	char[] ss = S.toCharArray();
	char[] tt = T.toCharArray();
	Map<Character, Integer> ttable = new HashMap<Character, Integer>();
	ArrayList<Character> cs = new ArrayList<Character>();
	for (char c : tt) {
		if (ttable.containsKey(c)) {
			int num = ttable.get(c);
			ttable.put(c, num + 1);
		} else {
			ttable.put(c, 1);
		}
		cs.add(c);
	}
	int start = -1;
	int end = -1;
	String substring = "";
	for (int i = 0; i < ss.length; i++) {
		if (ttable.keySet().contains(ss[i])) {
			if (-1 == start) {
				start = i;
			}
			int num = ttable.get(ss[i]);
			if (num > 1) {
				ttable.put(ss[i], num - 1);
			} else {
				ttable.remove(ss[i]);
			}
			if (ttable.isEmpty()) {
				end = i;
				substring = S.substring(start, end + 1);
				break;
			}
		} else if (cs.contains(ss[i])) {
			if (table.containsKey(ss[i])) {
				int num = table.get(ss[i]);
				table.put(ss[i], num + 1);
			} else {
				table.put(ss[i], 1);
			}
		}
	}
	if (-1 == start || -1 == end) {
		return "";
	}
	for (start = start + 1; start <= ss.length - tt.length
			&& end < ss.length; start++) {
		if (!cs.contains(ss[start - 1])) {
			String tmp = S.substring(start, end + 1);
			if (tmp.length() < substring.length()) {
				substring = tmp;
			}
			continue;
		} else {
			if (table.containsKey(ss[start - 1])) {
				int num = table.get(ss[start - 1]);
				if (num > 1) {
					table.put(ss[start - 1], num - 1);
				} else {
					table.remove(ss[start - 1]);
				}
				String tmp = S.substring(start, end + 1);
				if (tmp.length() < substring.length()) {
					substring = tmp;
				}
			} else {
				for (end = end + 1; end < ss.length; end++) {
					if (ss[start - 1] == ss[end]) {
						break;
					}
					if (cs.contains(ss[end])) {
						if (table.containsKey(ss[end])) {
							int num = table.get(ss[end]);
							table.put(ss[end], num + 1);
						} else {
							table.put(ss[end], 1);
						}
					}
				}
				if (end < ss.length) {
					String tmp = S.substring(start, end + 1);
					if (tmp.length() < substring.length()) {
						substring = tmp;
					}
				} else {
					break;
				}
			}
		}
	}
	return substring;
}

发表于   |   分类于 ，   |   ❤

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/10/03/2013-10-03-CODE 56 Combinations/

访问原文「CODE 56. Combinations」

Given two integers n and k, return all possible combinations ofk numbers out of 1 … n.For example,
Ifn= 4 andk= 2, a solution is:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

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
public ArrayList<ArrayList<Integer>> combine(int n, int k) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (n < k) {
		return null;
	}
	
	ArrayList<Integer> sList = new ArrayList<Integer>();
	for (int i = 1; i <= n; i++) {
		sList.add(i);
	}
	ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
	for (int i = 1; i <= n; i++) {
		ArrayList<Integer> element = new ArrayList<Integer>();
		element.add(i);
		result.add(element);
	}
	int start = 0;
	int end = result.size();
	for (int num = 2; num <= k; num++) {
		ArrayList<ArrayList<Integer>> tmp = new ArrayList<ArrayList<Integer>>();
		for (int i = start; i < end; i++) {
			ArrayList<Integer> oldElement = result.get(i);
			for (int j = sList
					.indexOf(oldElement.get(oldElement.size() - 1)) + 2; j <= n; j++) {
				ArrayList<Integer> element = new ArrayList<Integer>();
				element.addAll(oldElement);
				element.add(j);
				tmp.add(element);
			}
		}
		result.clear();
		result.addAll(tmp);
		start = 0;
		end = result.size();
	}
	return result;
}

发表于   |   分类于 ，   |   ❤

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/10/01/2013-10-01-CODE 55 Subsets/

访问原文「CODE 55. Subsets」

Given a set of distinct integers, S, return all possible subsets.Note:

  • Elements in a subset must be in non-descending order.
  • The solution set must not contain duplicate subsets.

For example,
IfS=[1,2,3], a solution is:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

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
public ArrayList<ArrayList<Integer>> subsets(int[] S) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (null == S || S.length <= 0) {
		ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
		result.add(new ArrayList<Integer>());
		return result;
	}
	Arrays.sort(S);
	ArrayList<Integer> sList = new ArrayList<Integer>();
	for (int i = 0; i < S.length; i++) {
		sList.add(S[i]);
	}
	
	ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
	for (int i = 0; i < S.length; i++) {
		ArrayList<Integer> element = new ArrayList<Integer>();
		element.add(S[i]);
		result.add(element);
	}
	int start = 0;
	int end = result.size();
	for (int num = 2; num <= S.length; num++) {
		for (int i = start; i < end; i++) {
			ArrayList<Integer> oldElement = result.get(i);
			for (int j = sList
					.indexOf(oldElement.get(oldElement.size() - 1)) + 1; j < S.length; j++) {
				ArrayList<Integer> element = new ArrayList<Integer>();
				element.addAll(oldElement);
				element.add(S[j]);
				result.add(element);
			}
		}
		start = end;
		end = result.size();
	}
	result.add(new ArrayList<Integer>());
	return result;
}

发表于   |   分类于 ，   |   ❤

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/10/01/2013-10-01-CODE 54 Word Search/

访问原文「CODE 54. Word Search」

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,
Givenboard=
[
[“ABCE”],
[“SFCS”],
[“ADEE”]
]

word = "ABCCED", -> returnstrue,
word = "SEE", -> returnstrue,
word = "ABCB", -> returnsfalse.

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
public boolean exist(char[][] board, String word) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (null == board || board.length <= 0) {
		return false;
	}
	if (null == word || "".equals(word)) {
		return true;
	}
	int rows = board.length;
	int cols = board[0].length;
	boolean[][] walked = new boolean[rows][cols];
	for (int i = 0; i < rows; i++) {
		for (int j = 0; j < cols; j++) {
			if (checkExist(board, word, i, j, 0, walked)) {
				return true;
			}
		}
	}
	return false;
}
boolean checkExist(char[][] board, String word, int i, int j, int index,
		boolean[][] walked) {
	boolean existed = false;
	if (board[i][j] == word.charAt(index) && !walked[i][j]) {
		if (index == word.length() - 1) {
			return true;
		}
		for (int m = -1; m <= 1; m++) {
			for (int n = -1; n <= 1; n++) {
				if (Math.abs(n - m) != 1 || i + m < 0
						|| i + m >= board.length || j + n < 0
						|| j + n >= board[0].length || walked[m + i][n + j]) {
					continue;
				}
				walked[i][j] = true;
				existed = checkExist(board, word, m + i, n + j, index + 1,
						walked);
				walked[i][j] = false;
				if (existed) {
					return existed;
				}
			}
		}
	}
	return existed;
}