Duplicate Zeros
往后加一个0，然后移动其他数 看到讨论里有个o(1) time, o(n) space的, 利用queue作为结果的预存储:
two pointers
Find the Duplicate Number
双指针. 找环
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
public class FloydsCycleDetection { public static int floyd(int[] a){ int s = a[0]; int f = a[0]; do { s = a[s]; f = a[a[f]]; } while (s!=f); s = a[0]; while (s != f){ s = a[s]; f = a[f]; } return f; } public static void main(String[] args) { int[] t = new int[]{1,3,4,2,2}; System.out.println(floyd(t)); } } |
[LintCode] Triangle Count
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
public int triangleCount(int S[]) { // write your code here int res = 0; if(S.length == 0 || S == null) return res; Arrays.sort(S); for(int i = S.length - 1; i > 0; i--) { int l = 0; int r = i - 1; while(l < r) { if(S[l] + S[r] > S[i]){ res += (r-l); r--; } else l++; } } return res; } |
[LintCode] Valid Palindrome
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
public boolean isPalindrome(String s) { // Write your code here if(s.length() == 0 || s == null) return true; s = s.toLowerCase(); s = s.trim(); int i = 0; int j = s.length() - 1; while(i <= j) { while(i <= j && !((s.charAt(i) <= 'z' && s.charAt(i) >= 'a') || (s.charAt(i) >= '0' && s.charAt(i) <= '9'))) i++; while(i <= j && !((s.charAt(j) <= 'z' && s.charAt(j) >= 'a') || (s.charAt(j) >= '0' && s.charAt(j) <= '9'))) j--; if(i <= j && s.charAt(i) != s.charAt(j)) return false; i++; j--; } return true; } |
[LintCode] Linked List Cycle
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
public boolean hasCycle(ListNode head) { // write your code here if(head == null) return false; ListNode fast = head; ListNode slow = head; while(fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; if(slow == fast) return true; } return false; } |
[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] 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] 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; } |