发表于   |   分类于 ，   |   ❤

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

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

访问原文「CODE 73. Permutation Sequence」

The set [1,2,3,…,n] contains a
total of n! unique permutations.
By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

  1. "123"
  2. "132"
  3. "213"
  4. "231"
  5. "312"
  6. "321"

Given n and k, return the kth permutation sequence.
Note: Given n will be between 1 and 9 inclusive.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 	public String getPermutation(int n, int k) {
	// Start typing your Java solution below
	// DO NOT write main() function
	--k;
	ArrayList<Integer> numbers = new ArrayList<Integer>();
	String s = new String();
	int njiecheng = 1;
	for (int i = 1; i <= n; i++) {
		numbers.add(i);
		njiecheng *= i;
	}
	for (int j = n; j >= 1; j--) {
		int num = k / (njiecheng / j);
		s = s + numbers.get(num);
		numbers.remove(num);
		k = k % (njiecheng / j);
		njiecheng = njiecheng / j;
	}
	return s;
}

发表于   |   分类于 ，   |   ❤

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

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

访问原文「CODE 72. Rotate List」

Given a list, rotate the list to the right by k places, where k is non-negative.
For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

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
public ListNode rotateRight(ListNode head, int n) {
	// Note: The Solution object is instantiated only once and is reused by
	// each test case.
	if (null == head) {
		return null;
	}
	ListNode round1 = null;
	ListNode p = head;
	int length = 0;
	while (null != p) {
		ListNode node = new ListNode(p.val);
		node.next = round1;
		p = p.next;
		round1 = node;
		length++;
	}
	if (n % length == 0) {
		return head;
	} else {
		n = n % length;
	}
	int num = 0;
	ListNode round2 = null;
	ListNode p1 = round1;
	while (num < n) {
		ListNode node = new ListNode(p1.val);
		node.next = round2;
		p1 = p1.next;
		round2 = node;
		num++;
	}
	ListNode round3 = new ListNode(0);
	ListNode round3Cpy = round3;
	ListNode p2 = round2;
	while (null != p2) {
		ListNode node = new ListNode(p2.val);
		p2 = p2.next;
		round3Cpy.next = node;
		round3Cpy = round3Cpy.next;
	}
	while (null != p1) {
		ListNode node = new ListNode(p1.val);
		node.next = round3Cpy.next;
		round3Cpy.next = node;
		p1 = p1.next;
	}
	return round3.next;
}

发表于   |   分类于 ，   |   ❤

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

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/10/07/2013-10-07-CODE 70 Unique Paths II/

访问原文「CODE 70. Unique Paths II」

Follow up for “Unique Paths”:
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as 1 and 0 respectively
in the grid.
For example,

There is one obstacle in the middle of a 3x3 grid as illustrated below.
[
[0,0,0],
[0,1,0],
[0,0,0]
]

The total number of unique paths is 2.
Note: m and n will be at most 100.

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
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
	// Note: The Solution object is instantiated only once and is reused by
	// each test case.
	int m = obstacleGrid.length;
	int n = obstacleGrid[0].length;
	int[][] sum = new int[m][n];
	sum[0][0] = obstacleGrid[0][0] == 1 ? 0 : 1;
	for (int i = 1; i < m; i++) {
		if (obstacleGrid[i][0] == 1) {
			sum[i][0] = 0;
		} else {
			sum[i][0] = sum[i - 1][0];
		}
	}
	for (int i = 1; i < n; i++) {
		if (obstacleGrid[0][i] == 1) {
			sum[0][i] = 0;
		} else {
			sum[0][i] = sum[0][i - 1];
		}
	}
	for (int i = 1; i < m; i++) {
		for (int j = 1; j < n; j++) {
			if (obstacleGrid[i][j] != 1) {
				sum[i][j] = sum[i - 1][j] + sum[i][j - 1];
			} else {
				sum[i][j] = 0;
			}
		}
	}
	return sum[m - 1][n - 1];
}

发表于   |   分类于 ，   |   ❤

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

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

访问原文「CODE 71. Unique Paths」

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).
How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?
Note: m and n will be at most 100.

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

发表于   |   分类于 ，   |   ❤

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

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

访问原文「CODE 69. Minimum Path Sum」

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int minPathSum(int[][] grid) {
	// Start typing your Java solution below
	// DO NOT write main() function
	int[][] sum = new int[grid.length][grid[0].length];
	sum[0][0] = grid[0][0];
	for (int i = 1; i < grid.length; i++) {
		sum[i][0] = grid[i][0] + sum[i - 1][0];
	}
	for (int i = 1; i < grid[0].length; i++) {
		sum[0][i] = grid[0][i] + sum[0][i - 1];
	}
	for (int i = 1; i < grid.length; i++) {
		for (int j = 1; j < grid[0].length; j++) {
			sum[i][j] = grid[i][j] + Math.min(sum[i - 1][j], sum[i][j - 1]);
		}
	}
	return sum[sum.length - 1][sum[0].length - 1];
}

发表于   |   分类于 ，   |   ❤

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

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/10/07/2013-10-07-CODE 68 Merge Two Sorted Lists/

访问原文「CODE 68. Merge Two Sorted Lists」

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes
of the first two lists.

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 ListNode mergeTwoLists(ListNode l1, ListNode l2) {
	// Note: The Solution object is instantiated only once and is reused by
	// each test case.
	if (null == l1 && null == l2) {
		return null;
	} else if (null == l2) {
		return l1;
	} else if (null == l1) {
		return l2;
	}
	ListNode newList = new ListNode(0);
	ListNode p = newList;
	ListNode p1 = l1;
	ListNode p2 = l2;
	while (null != p1 && null != p2) {
		if (p1.val < p2.val) {
			ListNode node = new ListNode(p1.val);
			p.next = node;
			p = p.next;
			p1 = p1.next;
		} else {
			ListNode node = new ListNode(p2.val);
			p.next = node;
			p = p.next;
			p2 = p2.next;
		}
	}
	if (null != p1) {
		p.next = p1;
	} else if (null != p2) {
		p.next = p2;
	}
	return newList.next;
}

发表于   |   分类于 ，   |   ❤

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

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

访问原文「CODE 67. Add Binary」

Given two binary strings, return their sum (also a binary string).
For example,
a = "11"
b = "1"
Return "100".

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
public String addBinary(String a, String b) {
	// Note: The Solution object is instantiated only once and is reused by
	// each test case.
	char[] as = a.toCharArray();
	char[] bs = b.toCharArray();
	int i = as.length - 1;
	int j = bs.length - 1;
	int c = 0;
	StringBuilder sb = new StringBuilder();
	while (i >= 0 && j >= 0) {
		if (0 == c) {
			if ((as[i] == '0' && bs[j] == '1')
					|| (as[i] == '1' && bs[j] == '0')) {
				sb = sb.insert(0, '1');
				c = 0;
			} else if ((as[i] == '0' && bs[j] == '0')) {
				sb = sb.insert(0, '0');
				c = 0;
			} else {
				sb = sb.insert(0, '0');
				c = 1;
			}
		} else if (1 == c) {
			if ((as[i] == '0' && bs[j] == '1')
					|| (as[i] == '1' && bs[j] == '0')) {
				sb = sb.insert(0, '0');
				c = 1;
			} else if ((as[i] == '0' && bs[j] == '0')) {
				sb = sb.insert(0, '1');
				c = 0;
			} else {
				sb = sb.insert(0, '1');
				c = 1;
			}
		}
		i--;
		j--;
	}
	while (i >= 0) {
		if (0 == c) {
			sb = sb.insert(0, as[i]);
			c = 0;
		} else if (1 == c) {
			if (as[i] == '0') {
				sb = sb.insert(0, '1');
				c = 0;
			} else {
				sb = sb.insert(0, '0');
				c = 1;
			}
		}
		i--;
	}
	while (j >= 0) {
		if (0 == c) {
			sb = sb.insert(0, bs[j]);
			c = 0;
		} else if (1 == c) {
			if (bs[j] == '0') {
				sb = sb.insert(0, '1');
				c = 0;
			} else {
				sb = sb.insert(0, '0');
				c = 1;
			}
		}
		j--;
	}
	if (1 == c) {
		sb = sb.insert(0, '1');
	}
	return sb.toString();
}

发表于   |   分类于 ，   |   ❤

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

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

访问原文「CODE 66. Valid Number」

Validate if a given string is numeric.
Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true

Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.

1
2
3
4
5
6
public boolean isNumber(String s) {
	// Start typing your Java solution below
	// DO NOT write main() function
	String regExp = "[ ]*[+|-]{0,1}([0-9]+\\.{0,1}|([0-9]*\\.[0-9]+))(e[+|-]{0,1}[0-9]+){0,1}[ ]*";
	return s.matches(regExp);
}

发表于   |   分类于 ，   |   ❤

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

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

访问原文「CODE 65. Plus One」

####
Given a number represented as an array of digits, plus one to the number.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int[] plusOne(int[] digits) {
	// Start typing your Java solution below
	// DO NOT write main() function
	int c = 1;
	int i;
	for (i = digits.length - 1; i >= 0; i--) {
		if (digits[i] < 9) {
			digits[i] += c;
			break;
		} else if (digits[i] == 9) {
			digits[i] = 0;
		}
	}
	if (i < 0 && digits[0] == 0) {
		int[] newDigits = new int[digits.length + 1];
		newDigits[0] = 1;
		return newDigits;
	} else {
		return digits;
	}
}

发表于   |   分类于 ，   |   ❤

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

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

访问原文「CODE 64. Text Justification」

Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.
You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly L characters.
Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
For the last line of text, it should be left justified and no extra space is inserted between words.
For example,
words: ["This", "is", "an", "example", "of", "text", "justification."]
L: 16.
Return the formatted lines as:

[
   "This    is    an",
   "example  of text",
   "justification.  "
]

Note: Each word is guaranteed not to exceed L in length.
click to show corner cases.
Corner Cases:

  • A line other than the last line might contain only one word. What should you do in this case?
    In this case, that line should be left-justified.
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
public ArrayList<String> fullJustify(String[] words, int L) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (null == words || words.length <= 0) {
		ArrayList<String> result = new ArrayList<String>();
		result.add("");
		return result;
	} else if (words.length == 1 && words[0].equals("") && L > 0) {
		ArrayList<String> result = new ArrayList<String>();
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < L; i++) {
			sb.append(" ");
		}
		result.add(sb.toString());
		return result;
	}
	ArrayList<String> result = new ArrayList<String>();
	int groupNumber = 0;
	int groupLength = 0;
	int startWord = 0;
	for (int i = 0; i < words.length; i++) {
		if (groupLength + words[i].length() <= L) {
			groupLength += words[i].length() + 1;
			groupNumber++;
		} else {
			StringBuilder sb = new StringBuilder();
			int[] spaceNumber = new int[groupNumber - 1];
			if (groupNumber == 1) {
				sb.append(words[startWord]);
				for (int m = 0; m < L - words[startWord].length(); m++)
					sb.append(" ");
			} else {
				if (groupLength - 1 == L) {
					for (int j = 0; j < groupNumber - 1; j++) {
						spaceNumber[j] = 1;
					}
				} else {
					for (int j = 0; j < groupNumber - 1; j++) {
						spaceNumber[j] = (L - (groupLength - groupNumber))
								/ (groupNumber - 1);
					}
					for (int j = 0; j < (L - (groupLength - groupNumber))
							% (groupNumber - 1); j++) {
						spaceNumber[j] += 1;
					}
				}
				for (int j = startWord; j < startWord + groupNumber; j++) {
					sb.append(words[j]);
					if (startWord + groupNumber - 1 != j) {
						for (int m = 0; m < spaceNumber[j - startWord]; m++)
							sb.append(" ");
					}
				}
			}
			result.add(sb.toString());
			groupNumber = 0;
			groupLength = 0;
			startWord = i;
			i--;
		}
	}
	if (groupNumber != 0) {
		StringBuilder sb = new StringBuilder();
		for (int j = startWord; j < startWord + groupNumber; j++) {
			sb.append(words[j]);
			if (startWord + groupNumber - 1 != j) {
				sb.append(" ");
			}
		}
		if (sb.length() < L) {
			for (int m = sb.length(); m < L; m++) {
				sb.append(" ");
			}
		}
		result.add(sb.toString());
	}
	return result;
}