IT技術小屋
          
				
          秋風秋雨，皆入我心
          
			          		
		
          
	
          

          

          
	
          
		
          
			
 
BlogJava ::
首頁 ::
新隨筆 ::
聯系 ::
聚合
 ::
管理 ::


			
			
				

          
	
          
		
          
			
			
			
				 
				38 
				隨筆 ::
				1 文章
				::
				19 評論
				::
				0 Trackbacks
			
		
          
	
          

          

			          		
		
          
	
          

          


          


          
	
					


          
			  
	#

          


		
          
			
			
			
          
				
          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 閱讀(144) | 評論 (0) | 編輯 收藏
			
          
		
          
		
          
	
		
          
			
			
			
          
				
          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 閱讀(172) | 評論 (0) | 編輯 收藏
			
          
		
          
		
          
	
		
          
			
			
			
          
				
          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 閱讀(109) | 評論 (0) | 編輯 收藏
			
          
		
          
		
          
	
		
          
			
			
			
          
				
          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 閱讀(646) | 評論 (0) | 編輯 收藏
			
          
		
          
		
          
	
		
          
			
			
			
          
				
          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 閱讀(692) | 評論 (0) | 編輯 收藏
			
          
		
          
		
          
	
		
          
			
			
			
          
				
          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 閱讀(774) | 評論 (0) | 編輯 收藏
			
          
		
          
		
          
	
		
          
			
			
			
          
				
          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 閱讀(2270) | 評論 (0) | 編輯 收藏
			
          
		
          
		
          
	
		
          
			
			
			
          
				
          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 閱讀(1557) | 評論 (1) | 編輯 收藏
			
          
		
          
		
          
	
		
          
			
			
			
          
				
          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 閱讀(4318) | 評論 (0) | 編輯 收藏
			
          
		
          
		
          
	
		
          
			
			
			
          
				
          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 閱讀(1238) | 評論 (0) | 編輯 收藏
			
          
		
          
		
          
	
          僅列出標題
          
	共4頁: 上一頁 1 2 3 4 下一頁 

          

				

          




    
          
        
	




主站蜘蛛池模板：
扶风县|
龙南县|
建德市|
巴马|
那曲县|
胶州市|
麻阳|
清苑县|
开阳县|
尚志市|
新龙县|
余姚市|
长兴县|
南安市|
闸北区|
江陵县|
盐津县|
饶平县|
盐边县|
墨玉县|
临城县|
贵阳市|
乳山市|
金寨县|
平山县|
定结县|
赤壁市|
黎城县|
天门市|
新河县|
信丰县|
鄯善县|
临朐县|
冕宁县|
宜章县|
通海县|
景泰县|
沂南县|
禹州市|
自贡市|
喀什市|