发表于   |   分类于 ，   |   ❤

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

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

访问原文「CODE 42. Subsets II」

Given a collection of integers that might contain duplicates, 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,
If S = [1,2,2],
a solution is:
[
[2],
[1],
[1,2,2],
[2,2],
[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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public ArrayList<ArrayList<Integer>> subsetsWithDup(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]);
		if (!result.contains(element)) {
			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);
			int j = sList.indexOf(oldElement.get(oldElement.size() - 1)) + 1;
			if (oldElement.size() > 1) {
				for (int m = oldElement.size() - 2; m >= 0; m--) {
					if (oldElement.get(m) == oldElement.get(oldElement
							.size() - 1)) {
						j++;
					} else {
						break;
					}
				}
			}
			for (; j < S.length; j++) {
				ArrayList<Integer> element = new ArrayList<Integer>();
				element.addAll(oldElement);
				element.add(S[j]);
				if (!result.contains(element)) {
					result.add(element);
				}
			}
		}
		start = end;
		end = result.size();
	}
	result.add(new ArrayList<Integer>());
	return result;
}

发表于   |   分类于 ，   |   ❤

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

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/11/17/2013-11-17-CODE 51 Search in Rotated Sorted Array II/

访问原文「CODE 51. Search in Rotated Sorted Array II」

Follow up for “Search in Rotated Sorted Array”:
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.

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
  		public boolean search(int[] A, int target) {
	// IMPORTANT: Please reset any member data you declared, as
	// the same Solution instance will be reused for each test case.
	int pivot = 1;
	for (; pivot < A.length; pivot++) {
		if (A[pivot] < A[pivot - 1]) {
			break;
		}
	}
	int start = 0;
	int end = 0;
	if (pivot == A.length) {
		end = A.length - 1;
	} else {
		if (A[0] <= target && A[pivot - 1] >= target) {
			start = 0;
			end = pivot - 1;
		} else {
			start = pivot;
			end = A.length - 1;
		}
	}
	while (start < end) {
		int mid = (start + end) / 2;
		if (A[mid] < target) {
			start = mid + 1;
		} else if (A[mid] > target) {
			end = mid;
		} else {
			return true;
		}
	}
	if (A[start] == target) {
		return true;
	}
	return false;
}

发表于   |   分类于 ，   |   ❤

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

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/11/17/2013-11-17-CODE 53 Remove Duplicates from Sorted Array II/

访问原文「CODE 53. Remove Duplicates from Sorted Array II」

Follow up for “Remove Duplicates”:
What if duplicates are allowed at most twice?
For example,
Given sorted array A = [1,1,1,2,2,3],
Your function should return length = 5,
and A is now [1,1,2,2,3].

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
public int removeDuplicates(int[] A) {
		// IMPORTANT: Please reset any member data you declared, as
		// the same Solution instance will be reused for each test case.
		if (A.length <= 0) {
			return 0;
		}
		int length = A.length;
		int cur = 0;
		int nxt = 1;
		boolean morethan2 = false;
		for (; nxt < A.length; nxt++) {
			if (A[nxt] != A[nxt - 1]) {
				A[cur] = A[nxt - 1];
				cur++;
				morethan2 = false;
			} else if (!morethan2) {
				A[cur] = A[nxt - 1];
				cur++;
				morethan2 = true;
			} else {
				length--;
			}
		}
		A[cur] = A[nxt - 1];
		return length;
	}

发表于   |   分类于 ，   |   ❤

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

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/11/16/2013-11-16-CODE 74 Spiral Matrix II/

访问原文「CODE 74. Spiral Matrix II」

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
For example,
Given n = 3,
You should return the following matrix: [
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 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
public int[][] generateMatrix(int n) {
	// IMPORTANT: Please reset any member data you declared, as
	// the same Solution instance will be reused for each test case.
	int[][] matrix = new int[n][n];
	int number = 1;
	int halfCol = (n - 1) / 2;
	int halfRow = (n - 1) / 2;
	int col = 0;
	int row = 0;
	while (row <= halfRow && col <= halfCol) {
		for (int i = col; i < n - col; i++) {
			matrix[row][i] = number++;
		}
		for (int i = row + 1; i < n - row; i++) {
			matrix[i][n - col - 1] = number++;
		}
		if (row != n - row - 1) {
			for (int i = n - col - 2; i >= col; i--) {
				matrix[n - row - 1][i] = number++;
			}
		}
		if (col != n - col - 1) {
			for (int i = n - row - 2; i >= row + 1; i--) {
				matrix[i][col] = number++;
			}
		}
		row++;
		col++;
	}
	return matrix;
}

发表于   |   分类于 ，   |   ❤

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

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/11/16/2013-11-16-CODE 129 Two Sum/

访问原文「CODE 129. Two Sum」

Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=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
40
public int[] twoSum(int[] numbers, int target) {
	// IMPORTANT: Please reset any member data you declared, as
	// the same Solution instance will be reused for each test case.
	if (null == numbers || numbers.length <= 1) {
		return new int[] {};
	}
	int[] tmp = new int[numbers.length];
	int[] results = new int[2];
	for (int i = 0; i < numbers.length; i++) {
		tmp[i] = numbers[i];
	}
	Arrays.sort(tmp);
	int start = 0;
	int end = tmp.length - 1;
	while (start < end) {
		if (tmp[start] + tmp[end] < target) {
			start++;
		} else if (tmp[start] + tmp[end] > target) {
			end--;
		} else {
			break;
		}
	}
	for (int i = 0; i < numbers.length; i++) {
		if (numbers[i] == tmp[start] || numbers[i] == tmp[end]) {
			results[0] = i + 1;
			break;
		}
	}
	for (int i = numbers.length - 1; i >= results[0] - 1; i--) {
		if (numbers[i] == tmp[start] || numbers[i] == tmp[end]) {
			results[1] = i + 1;
			break;
		}
	}
	return results;
}

发表于   |   分类于 ，   |   ❤

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

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/11/15/2013-11-15-CODE 128 Median of Two Sorted Arrays/

访问原文「CODE 128. Median of Two Sorted Arrays」

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall
run time complexity should be O(log (m+n)).

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 double findMedianSortedArrays(int A[], int B[]) {
	// Start typing your Java solution below
	// DO NOT write main() function
	int k = A.length + B.length;
	if ((k & 0x1) == 1) {
		return find(A, 0, A.length, B, 0, B.length, k / 2 + 1);
	} else {
		return (find(A, 0, A.length, B, 0, B.length, k / 2) + find(A, 0,
				A.length, B, 0, B.length, k / 2 + 1)) / 2.0;
	}
}
double find(int A[], int startA, int lengthA, int B[], int startB,
		int lengthB, int k) {
	if (lengthA > lengthB) {
		return find(B, startB, lengthB, A, startA, lengthA, k);
	}
	if (lengthA <= 0) {
		return B[startB + k - 1];
	}
	if (lengthB <= 0) {
		return A[startA + k - 1];
	}
	if (k <= 1) {
		return Math.min(A[startA], B[startB]);
	}
	int i = Math.min(k >> 1, lengthA);
	int j = k - i;
	if (A[startA + i - 1] < B[startB + j - 1]) {
		return find(A, startA + i, lengthA - i, B, startB, lengthB, k - i);
	} else {
		return find(A, startA, lengthA, B, startB + j, lengthB - j, k - j);
	}
}

发表于   |   分类于 ，   |   ❤

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

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/11/14/2013-11-14-CODE 127 Longest Substring Without Repeating Characters/

访问原文「CODE 127. Longest Substring Without Repeating Characters」

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring
without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.

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
public int lengthOfLongestSubstring(String s) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (null == s || "".equals(s)) {
		return 0;
	}
	ArrayList<Character> list = new ArrayList<Character>();
	int max = Integer.MIN_VALUE;
	char[] cs = s.toCharArray();
	for (int i = 0; i < cs.length; i++) {
		if (list.isEmpty()) {
			list.add(cs[i]);
		} else {
			int index = list.indexOf(cs[i]);
			if (index == -1) {
				list.add(cs[i]);
			} else {
				for (int j = 0; j <= index; j++) {
					list.remove(0);
				}
				list.add(cs[i]);
			}
		}
		if (list.size() > max) {
			max = list.size();
		}
	}
	return max;
}

发表于   |   分类于 ，   |   ❤

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

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/11/14/2013-11-14-CODE 126 Add Two Numbers/

访问原文「CODE 126. Add Two Numbers」

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)

Output: 7 -> 0 -> 8

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
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
	// Start typing your Java solution below
	// DO NOT write main() function
	ListNode cpyl1 = l1;
	ListNode cpyl2 = l2;
	int c = 0;
	while (null != cpyl1 && null != cpyl2) {
		int tmp = cpyl1.val + cpyl2.val + c;
		if (tmp > 9) {
			c = tmp / 10;
		}
		cpyl1.val = tmp % 10;
		cpyl1 = cpyl1.next;
		cpyl2 = cpyl2.next;
	}
	while (cpyl1 != null) {
		int tmp = cpyl1.val + c;
		if (tmp > 9) {
			c = tmp / 10;
		}
		cpyl1.val = tmp % 10;
		cpyl1 = cpyl1.next;
	}
	cpyl1 = l1;
	while (null != cpyl1.next) {
		cpyl1 = cpyl1.next;
	}
	while (cpyl2 != null) {
		int tmp = cpyl2.val + c;
		if (tmp > 9) {
			c = tmp / 10;
		}
		cpyl1.next = new ListNode(tmp % 10);
		cpyl1 = cpyl1.next;
		cpyl2 = cpyl2.next;
	}
	if (c != 0) {
		cpyl1.next = new ListNode(c);
	}
	return l1;
}

发表于   |   分类于 ，   |   ❤

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

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/11/14/2013-11-14-CODE 125 Longest Palindromic Substring/

访问原文「CODE 125. Longest Palindromic Substring」

Given a string S,
find the longest palindromic substring in S.
You may assume that the maximum length of S is
1000, and there exists one unique longest palindromic substring.

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
public String longestPalindrome(String s) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (null == s || s.length() <= 0) {
		return "";
	} else if (s.length() == 1) {
		return s;
	}
	boolean[][] isPalindromic = new boolean[s.length()][s.length()];
	char[] cs = s.toCharArray();
	for (int i = 0; i < s.length(); i++) {
		isPalindromic[i][i] = true;
	}
	int start = -1;
	int end = -1;
	for (int i = s.length() - 2; i >= 0; i--) {
		isPalindromic[i][i + 1] = cs[i] == cs[i + 1];
		if (end - start < 1 && isPalindromic[i][i + 1]) {
			start = i;
			end = i + 1;
		}
		for (int j = i + 2; j < s.length(); j++) {
			isPalindromic[i][j] = cs[i] == cs[j]
					&& isPalindromic[i + 1][j - 1];
			if (end - start < j - i && isPalindromic[i][j]) {
				start = i;
				end = j;
			}
		}
	}
	if (start == -1 && end == -1) {
		return s.substring(0, 1);
	} else {
		return s.substring(start, end + 1);
	}
}

发表于   |   分类于 ，   |   ❤

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

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/11/13/2013-11-13-CODE 124 ZigZag Conversion/

访问原文「CODE 124. ZigZag Conversion」

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
25
26
27
28
29
30
31
public String convert(String s, int nRows) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if(nRows == 1){
		return s;
	}
	ArrayList<ArrayList<Character>> charLists = new ArrayList<ArrayList<Character>>();
	for (int i = 0; i < nRows; i++) {
		charLists.add(new ArrayList<Character>());
	}
	char[] cs = s.toCharArray();
	for (int i = 0; i < s.length(); i++) {
		if (i % (nRows - 1) == 0) {
			int j = 0;
			for (j = i; j < cs.length && j < i + nRows; j++) {
				charLists.get(j - i).add(cs[j]);
			}
			i = j - 1;
		} else {
			int row = charLists.size() - 1 - i % (nRows - 1);
			charLists.get(row).add(cs[i]);
		}
	}
	StringBuilder sb = new StringBuilder();
	for (ArrayList<Character> charList : charLists) {
		for (char c : charList) {
			sb.append(c);
		}
	}
	return sb.toString();
}