Add to Array-Form of Integer
数组相加. 先把k变成数组格式, 然后想加. 最后再翻转数组.
array
[LintCode] Merge Intervals
|
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 List<Interval> merge(List<Interval> intervals) { // write your code here List<Interval> res= new ArrayList<Interval>(); if(intervals.size() == 0 || intervals == null) return res; Collections.sort(intervals, new IntervalComparator()); Interval first = intervals.get(0); for(int i = 1; i < intervals.size(); i++) { Interval cur = intervals.get(i); if(cur.start <= first.end) { first.end = Math.max(cur.end, first.end); }else{ res.add(first); first = cur; } } res.add(first); return res; } class IntervalComparator implements Comparator{ public int compare(Object o1, Object o2){ Interval i1 = (Interval)o1; Interval i2 = (Interval)o2; return i1.start - i2.start; } } |
[LintCode] Best Time to Buy and Sell Stock II
|
1 2 3 4 5 6 7 8 9 |
public int maxProfit(int[] prices) { // write your code here int max = 0; for(int i = 1; i < prices.length; i++) { if(prices[i] - prices[i-1] > 0) max += prices[i] - prices[i-1]; } return max; } |
[LintCode] 3 Sum
|
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 ArrayList<ArrayList<Integer>> threeSum(int[] numbers) { // write your code here ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>(); if(numbers.length == 0 || numbers == null) return res; Arrays.sort(numbers); for(int i = 0 ; i < numbers.length - 2; i++) { if(i != 0 && numbers[i] == numbers[i-1]) continue; int l = i+1; int r = numbers.length - 1; while(l < r){ int sum = numbers[i] + numbers[l] + numbers[r]; if(sum == 0){ ArrayList<Integer> tmp = new ArrayList<Integer>(); tmp.add(numbers[i]); tmp.add(numbers[l]); tmp.add(numbers[r]); res.add(tmp); l++; r--; while(l < r && numbers[l] == numbers[l-1]) l++; while(l < r && numbers[r] == numbers[r+1]) r--; }else if(sum > 0) r--; else l++; } } return res; } |
[LintCode] 3 Sum Closest
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
public int threeSumClosest(int[] numbers ,int target) { // write your code here Arrays.sort(numbers); if(numbers.length == 0 || numbers == null) return 0; int close = Integer.MAX_VALUE; for(int i = 0; i < numbers.length - 2; i++) { int j = i + 1; int k = numbers.length - 1; while(j < k) { int sum = numbers[i] + numbers[j] + numbers[k]; if(sum == target) return target; else if (sum > target) k--; else j++; if(Math.abs(target - sum) < Math.abs(target - close)) close = sum; } } return close; } |
[LintCode] First Missing Positive
|
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 int firstMissingPositive(int[] A) { // write your code here if(A == null || A.length == 0) return 1; int i = 0; int n = A.length; while(i < n) { if(A[i] >= 0 && A[i] < n && A[A[i]] != A[i]) swap(A, i, A[i]); else i++; } int k = 1; while(k < n && A[k] == k) k++; if(k < n) return k; else return k+1; } public void swap(int[] A, int i, int j) { int tmp = A[i]; A[i] = A[j]; A[j] = tmp; } |
[LintCode] Merge Sorted 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 |
public void mergeSortedArray(int[] A, int m, int[] B, int n) { // write your code here int i = m - 1; int j = n - 1; int index = m+n - 1; while(i >= 0 && j >= 0) { if(A[i] < B[j]) { A[index] = B[j]; j--; index --; } else{ A[index] = A[i]; i--; index--; } } while(i >= 0){ A[index] = A[i]; i--; index--;; } while(j >= 0) { A[index] = B[j]; j--; index--; } } |
[LintCode] Remove Duplicates from Sorted Array
|
1 2 3 4 5 6 7 8 9 10 11 12 |
public int removeDuplicates(int[] nums) { // write your code here int res = 0; if(nums.length == 0 || nums == null) return res; for(int i = 1 ; i < nums.length; i++) { if(nums[res] != nums[i]){ nums[++res] = nums[i]; } } return res+1; } |
[LintCode] Subarray Sum
|
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 |
public ArrayList<Integer> subarraySum(int[] nums) { // write your code here ArrayList<Integer> res = new ArrayList<Integer>(); if(nums.length == 0 || nums == null) return res; HashMap<Integer,Integer> map = new HashMap<Integer,Integer>(); int sum = 0; for(int i = 0 ; i < nums.length; i++) { sum += nums[i]; if(nums[i] == 0){ res.add(i); res.add(i); break; } if(sum == 0) { res.add(0); res.add(i); break; } if(map.containsKey(sum)) { res.add(map.get(sum)+1); res.add(i); break; } map.put(sum, i); } return res; } |
[LintCode] Remove Element
|
1 2 3 4 5 6 7 8 9 10 11 |
public int removeElement(int[] A, int elem) { // write your code here int res = 0; if(A.length == 0 || A == null) return res; for(int i = 0 ; i < A.length; i++) { if(A[i] != elem) A[res++] = A[i]; } return res; } |