IT技术小屋

秋风秋雨，皆入我心
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  38 随笔 :: 1 文章 :: 19 评论 :: 0 Trackbacks

#

[Leetcode] Multiply Strings
Given two numbers represented as strings, return multiplication of the numbers as a string.
Note: The numbers can be arbitrarily large and are non-negative.

对每个数字相乘，记录到一个数组中，然后对这个数字的每个元素进行进位检查。主要相乘的时候要分别从两个数字的最后一位开始，还要记录偏移量。实现如下：
 1 public class MultiplyStrings {
 2     public String multiply(String num1, String num2) {
 3         int length1 = num1.length();
 4         int length2 = num2.length();
 5         int[] m = new int[length1 + length2];
 6         for (int k = length2 - 1, offset2 = 0; k >= 0; k--, offset2++) {
 7             for (int i = length1 - 1, offset1 = 0; i >= 0; i--, offset1++) {
 8                 m[length1 + length2 - 1 - offset1 - offset2] += (num1.charAt(i) - '0') * (num2.charAt(k) - '0');
 9             }
10         }
11         int add = 0;
12         for (int t = length1 + length2 - 1; t >= 0; t--) {
13             int value = m[t] + add;
14             add = value / 10;
15             m[t] = value % 10;
16         }
17         StringBuffer sb = new StringBuffer();
18         int w = 0;
19         for (; w < length1 + length2; w++) {
20             if (m[w] != 0) break;
21         }
22         for (int e = w; e < length1 + length2; e++) {
23             sb.append(m[e]);
24         }
25         return sb.length() == 0 ? "0" : sb.toString();
26     }
27 }

posted @ 2013-12-23 11:59 Meng Lee 阅读(137) | 评论 (0) | 编辑 收藏

[Leetcode] Search for a Range
Given a sorted array of integers, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

这个题目有递归和非递归两个解法。
递归解法：这个解法比较简洁，代码如下：
 1 public class SearchforaRange {
 2         public int[] searchRange(int[] A, int target) {
 3                 int low = findLow(A, target, 0, A.length - 1);
 4                 int high = findHigh(A, target, 0, A.length - 1);
 5                 int[] ret = new int[2];
 6                 ret[0] = low;
 7                 ret[1] = high;
 8                 return ret;
 9         }
10 
11         private int findLow(int[] A, int target, int l, int r) {
12                 int mid = 0;
13                 int ret = -1;
14                 while (l <= r) {
15                         mid = (l + r) / 2;
16                         if (A[mid] == target) {
17                                 ret = mid;
18                                 int next = findLow(A, target, l, mid - 1);
19                                 if (next != -1) {
20                                         ret = next;
21                                 }
22                                 break;
23                         } else if (A[mid] < target) {
24                                 l = mid + 1;
25                         } else {
26                                 r = mid - 1;
27                         }
28 
29                 }
30                 return ret;
31         }
32 
33         private int findHigh(int[] A, int target, int l, int r) {
34                 int mid = 0;
35                 int ret = -1;
36                 while (l <= r) {
37                         mid = (l + r) / 2;
38                         if (A[mid] == target) {
39                                 ret = mid;
40                                 int next = findHigh(A, target, mid + 1, r);
41                                 if (next != -1) {
42                                         ret = next;
43                                 }
44                                 break;
45                         } else if (A[mid] < target) {
46                                 l = mid + 1;
47                         } else {
48                                 r = mid - 1;
49                         }
50                 }
51                 return ret;
52         }
53 }

非递归解法：以寻找左边界为例，这个解法的思路就是一直向左进行二分查找，直到找到最左的目标元素或者最左的目标元素的下一个元素。因此，二分查找结束之后，需要判断找到的元素到底是目标元素还是他的第一个不满足的元素，然后根据情况返回下标。代码实现如下：
 1 public class Solution {
 2     public int[] searchRange(int[] A, int target) {
 3         int left = findLeft(A, target);
 4         int right = findRight(A, target);
 5         return new int[] { left, right };
 6     }
 7 
 8     private int findLeft(int[] A, int target) {
 9         int i = 0, j = A.length - 1;
10         while (i < j) {
11             int mid = (i + j) / 2;
12             if (A[mid] < target) {
13                 i = mid + 1;
14             } else {
15                 j = mid - 1;
16             }
17         }
18         if (A[i] == target) return i;
19         if (i < A.length - 1 && A[i + 1] == target) return i + 1;
20         return -1;
21     }
22 
23     private int findRight(int[] A, int target) {
24         int i = 0, j = A.length - 1;
25         while (i < j) {
26             int mid = (i + j) / 2;
27             if (A[mid] > target) {
28                 j = mid - 1;
29             } else {
30                 i = mid + 1;
31             }
32         }
33         if (j >= 0 && A[j] == target)
34             return j;
35         if (j > 0 && A[j - 1] == target)
36             return j - 1;
37         return -1;
38     }
39 }
posted @ 2013-12-23 09:58 Meng Lee 阅读(168) | 评论 (0) | 编辑 收藏

[Leetcode] Search Insert Position
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

本题先对数组进行二分搜索，如果找到了目标元素就返回相应的index，如果最终没有找到对应的元素，则比较最后一个元素与目标元素的大小。实现代码如下：
 1 public class Solution {
 2     public int searchInsert(int[] A, int target) {
 3         int length = A.length;
 4         if (A.length == 0) return 0;
 5         int i = 0, j = length - 1;
 6         while (i < j) {
 7             int mid = (i + j) / 2;
 8             if (A[mid] == target) return mid;
 9             if (A[mid] < target) {
10                 i = mid + 1;
11             } else {
12                 j = mid - 1;
13             }
14         }
15         return A[i] < target ? i + 1 : i;
16     }
17 }
posted @ 2013-12-23 09:11 Meng Lee 阅读(100) | 评论 (0) | 编辑 收藏

[Leetcode] 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.

本题比较简单，需要注意的是左指针右移时，需要将它掠过的元素从map中移除。实现代码如下：
 1 public class Solution {
 2     public int lengthOfLongestSubstring(String s) {
 3         int length = s.length();
 4         if (length == 0) return 0;
 5         Map<Character, Integer> map = new HashMap<Character, Integer>();
 6         int ret = 0;
 7         int count = 0;
 8         int start = 0;
 9         for (int i = 0; i < length; i++) {
10             char c = s.charAt(i);
11             if (map.containsKey(c)) {
12                 int newStart = map.remove(c).intValue() + 1;
13                 for (int j = start; j < newStart; j++) {
14                     map.remove(s.charAt(j));
15                 }
16                 start = newStart;
17                 ret = ret < count ? count : ret;
18                 count = i - start + 1;
19             } else {
20                 count++;
21             }
22             map.put(c, i);
23         }
24         return ret < count ? count : ret;
25     }
26 }
posted @ 2013-12-22 20:07 Meng Lee 阅读(641) | 评论 (0) | 编辑 收藏

[Leetcode] Spiral Matrix
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
For example,
Given the following matrix:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
You should return [1,2,3,6,9,8,7,4,5].

可以为矩阵设置上下左右四个边界，每次绕着这四个边界打印元素。实现代码如下：
 1 public class Solution {
 2     public ArrayList<Integer> spiralOrder(int[][] matrix) {
 3         ArrayList<Integer> ret = new ArrayList<Integer>();
 4         if (matrix.length == 0) return ret;
 5         int upper = 0, bottom = matrix.length - 1;
 6         int left = 0, right = matrix[0].length - 1;
 7         int i = 0, j = 0;
 8         while (true) {
 9             for (i = left; i <= right; i++) {
10                 ret.add(matrix[upper][i]);
11             }
12             if (++upper > bottom) break;
13             for (j = upper; j <= bottom; j++) {
14                 ret.add(matrix[j][right]);
15             }
16             if (--right < left) break;
17             for (i = right; i >= left; i--) {
18                 ret.add(matrix[bottom][i]);
19             }
20             if (--bottom < upper) break;
21             for (j = bottom; j >= upper; j--) {
22                 ret.add(matrix[j][left]);
23             }
24             if (++left > right) break;
25         }
26         return ret;
27     }
28 }
posted @ 2013-12-22 16:59 Meng Lee 阅读(684) | 评论 (0) | 编辑 收藏

[Leetcode] Longest Valid Parentheses
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
For "(()", the longest valid parentheses substring is "()", which has length = 2.
Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

本题的主要思路就是标记那些括号是被匹配的。
我们可以利用一个布尔数组，如果位置为i的值为true，则表示第i个括号是被匹配的，然后我们只需要求连续为true的元素的个数即可。实现代码如下：
 1 public class LongestValidParentheses {
 2     public int longestValidParentheses(String s) {
 3         int length = s.length();
 4         if (length == 0)
 5             return 0;
 6         int left = 0;
 7         Stack<Integer> indexs = new Stack<Integer>();
 8         boolean[] record = new boolean[length];
 9         for (int i = 0; i < length; i++) {
10             if (s.charAt(i) == '(') {
11                 left++;
12                 indexs.push(i);
13             } else if (left > 0) {
14                 int idx = indexs.pop();
15                 record[idx] = true;
16                 record[i] = true;
17                 left--;
18             }
19         }
20         int ret = 0;
21         int current = 0;
22         for (int k = 0; k < length; k++) {
23             if (record[k]) {
24                 current++;
25             } else {
26                 ret = current > ret ? current : ret;
27                 current = 0;
28             }
29         }
30         return ret > current ? ret : current;
31     }
32 }
posted @ 2013-12-21 21:28 Meng Lee 阅读(767) | 评论 (0) | 编辑 收藏

[Leetcode] Minimum Depth of Binary Tree
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

本题有两种解法。
第一种解法：对二叉树进行BFS，由于是按层遍历的，因此如果在某一层发现了一个叶子节点，那么就找到了最小深度，此时返回当前深度即可。实现代码如下：
 1 public class Solution {
 2     public int minDepth(TreeNode root) {
 3         if (root == null) return 0;
 4         int depth = 1;
 5         int currentLevel = 1;
 6         int nextLevel = 0;
 7         Queue<TreeNode> queue = new LinkedList<TreeNode>();
 8         queue.add(root);
 9         while (!queue.isEmpty()) {
10             TreeNode node = queue.remove();
11             currentLevel--;
12             if (node.left == null && node.right == null) {
13                 return depth;
14             }
15             if (node.left != null) {
16                 queue.add(node.left);
17                 nextLevel++;
18             }
19             if (node.right != null) {
20                 queue.add(node.right);
21                 nextLevel++;
22             }
23             if (currentLevel == 0) {
24                 if (nextLevel != 0) {
25                     depth++;
26                 }
27                 currentLevel = nextLevel;
28                 nextLevel = 0;
29             }
30         }
31         return depth;
32     }
33 }

第二种解法：采用递归的思想，分别求左右子树的最小深度，比较之后返回较小值。实现如下：
 1 public class MinimumDepthofBinaryTree {
 2     public int minDepth(TreeNode root) {
 3         if (root == null)
 4             return 0;
 5         if (root.left == null && root.right == null)
 6             return 1;
 7         else {
 8             int leftDepth = root.left != null ? minDepth(root.left)
 9                     : Integer.MAX_VALUE;
10             int rightDepth = root.right != null ? minDepth(root.right)
11                     : Integer.MAX_VALUE;
12             return Math.min(leftDepth, rightDepth) + 1;
13         }
14     }
15 }
posted @ 2013-12-21 21:19 Meng Lee 阅读(2264) | 评论 (0) | 编辑 收藏

[Leetcode] Permutations II
Given a collection of numbers, return all possible permutations.
For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

数组全排列题目，基本思想是对每一个字符与后面的字符作交换，以生成新的序列。为了防止重复，交换之前需要检查之前是否已经和同样的字符串做过交换。代码如下：
 1 public class PermutationsII {
 2     public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
 3         ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
 4         permuteUnique(num, 0, result);
 5         return result;
 6     }
 7 
 8     void permuteUnique(int[] num, int begin,
 9             ArrayList<ArrayList<Integer>> result) {
10         if (begin > num.length - 1) {
11             ArrayList<Integer> item = new ArrayList<Integer>();
12             for (int h = 0; h < num.length; h++) {
13                 item.add(num[h]);
14             }
15             result.add(item);
16         }
17         for (int end = begin; end < num.length; end++) {
18             if (isSwap(num, begin, end)) {
19                 swap(num, begin, end);
20                 permuteUnique(num, begin + 1, result);
21                 swap(num, begin, end);
22             }
23         }
24     }
25 
26     boolean isSwap(int[] arr, int i, int j) {
27         for (int k = i; k < j; k++) {
28             if (arr[k] == arr[j]) {
29                 return false;
30             }
31         }
32         return true;
33     }
34     
35     private void swap(int[] a, int i, int j) {
36         int tmp = a[i];
37         a[i] = a[j];
38         a[j] = tmp;
39     }
40 }
posted @ 2013-12-20 15:30 Meng Lee 阅读(1548) | 评论 (1) | 编辑 收藏

[Leetcode] Unique Binary Search Trees
Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
For example,
Given n = 3, there are a total of 5 unique BST's.
   1          3     3      2      1
    \        /      /       / \       \
     3     2     1       1   3       2
    /     /        \                      \
   2    1          2                     3
本题使用一维线性规划解决。
如果n等于0时，结果为0；
如果n等于1时，只有一个节点，结果为1；
如果n等于2时，根节点有两种选择，结果为2；
如果n大于3时，根节点有n种选择，确定根节点后分别计算左右子树的可能情况，然后相乘就是当前根节点下所有的变形种类，之后在求和即可。算法实现如下：
 1 public class UniqueBinarySearchTrees {
 2     public int numTrees(int n) {
 3         if (n == 1)
 4             return 1;
 5         if (n == 2)
 6             return 2;
 7         int[] record = new int[n + 1];
 8         record[0] = 1;
 9         record[1] = 1;
10         record[2] = 2;
11         for (int i = 3; i <= n; i++) {
12             int tmp = 0;
13             for (int k = 0; k < i; k++) {
14                 tmp += (record[k] * record[i - k - 1]);
15             }
16             record[i] = tmp;
17         }
18         return record[n];
19     }
20 }
posted @ 2013-12-20 11:58 Meng Lee 阅读(4310) | 评论 (0) | 编辑 收藏

[Leetcode] Palindrome Partitioning
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = "aab",
Return
[
    ["aa","b"],
    ["a","a","b"]
]

这个题目考虑用动态规划解题，关键在于构造一个解空间，确定S的任意子串S(i, j)是不是对称的。判断标准如下：
1、如果i == j，则S(i, j)是对称的；
2、如果j - i == 1 && S[i] == S[j]，则S(i, j)是对称的；
3、如果j - i > 1 && S[i] == S[j] && S(i + 1, j - 1)是对称的，则S(i, j)也是对称的。
在构造完这样的解空间后，就可以在O(1)时间内判定任意子串是不是对称的了。算法实现如下：
 1 public class PalindromePartitioning {
 2     public ArrayList<ArrayList<String>> partition(String s) {
 3         ArrayList<ArrayList<String>> ret = new ArrayList<ArrayList<String>>();
 4         ArrayList<String> r = new ArrayList<String>();
 5         int length = s.length();
 6         boolean[][] map = new boolean[length][length];
 7         findPartition(s, 0, ret, r, map);
 8         return ret;
 9     }
10 
11     private void findPartition(String s, int start,
12             ArrayList<ArrayList<String>> ret, ArrayList<String> r,
13             boolean[][] map) {
14         int length = s.length();
15         if (start == length && r.size() != 0) {
16             ArrayList<String> clone = new ArrayList<String>(r);
17             ret.add(clone);
18         } else {
19             for (int j = start; j < length; j++) {
20                 if (start == j
21                         || (j - start > 1 && s.charAt(start) == s.charAt(j) && map[start + 1][j - 1])
22                         || (j - start == 1 && s.charAt(start) == s.charAt(j))) {
23                     map[start][j] = true;
24                     r.add(s.substring(start, j + 1));
25                     findPartition(s, j + 1, ret, r, map);
26                     r.remove(r.size() - 1);
27                 }
28             }
29         }
30     }
31 }
posted @ 2013-12-19 17:03 Meng Lee 阅读(1231) | 评论 (0) | 编辑 收藏

仅列出标题
共4页: 上一页 1 2 3 4 下一页