刷题记录

思路： 三角形的任意两边之和大于第三边。如果小的两条边之和大于最大的一条边长，那肯定是三角形。不用检查其它情况了。所以这道题是找i的左边，有多少种情况是S[left] + S[right] > S[i]成立。 代码如下： public class Solution { /** * @param S: A list of integers * @return: An integer */ public int triangleCount(int S[]) { // write your code here int res = 0; Arrays.sort(S); for(int i = 0; i < S.length; i++) { int left = 0; int right = i - 1; while(left < right) { if(S[left] + S[right] > S[i]) { res += right - left; right--; } else { left++; } } } return res; } }

实现： 去重在这里已经不重要了，可以忽略，重复的数不影响最终结果。 记得到初始化int res = numbers[0] + numbers[1] + numbers[numbers.length - 1]，而不是0。和two sum closest不一样，前者是求different。这道题的result是会参与比较影响结果的：Math.abs(sum - target) < Math.abs(res - target) 代码如下: public class Solution { /* * @param numbers: Give an array numbers of n integer * @param target: An integer * @return: return the sum of the three integers, the sum closest target. */ public int threeSumClosest(int[] numbers, int target) { // write your code here // write your code here Arrays.sort(numbers); int res = numbers[0] + numbers[1] + numbers[numbers.length - 1]; for(int i = 0; i < numbers.length - 2; i++) { int left = i + 1; int right = numbers.length - 1; while(left < right) { int sum = numbers[left] + numbers[right] + numbers[i]; if (sum < target) { left++; } else { ri

思路： 好无聊的题，打擂台。。。。

2/20/2018 update Better not include while within while. Use the original solution. --------------------------------------------------------- 11/30/2017 update A more concise version is as follows. class Solution { public boolean isPalindrome(String s) { int i = 0, j = s.length() - 1; while (i < j) { while (i<j&&!Character.isLetterOrDigit(s.charAt(i))) i++; while (i<j&&!Character.isLetterOrDigit(s.charAt(j))) j--; if (Character.toLowerCase(s.charAt(i))!= Character.toLowerCase(s.charAt(j))) { return false; } i++; j--; } return true; } } Have to add i<j as condition when skip none letter or digit char, otherwise index would out of bound. ------------------------ 思路： 这道题主要要熟悉java build-in 对操作string的一些函数。 String.toLowerCase(). Character.isLetterOrDigit(). 实现： 先把s转换成lower case，这样不用在循环里面再每个转了。lintcode答案是刷题学生自己传

思路： 解法很巧妙，没想出来。只有发现规律然后实现。 代码如下： public class Solution { /* * @param nums: an integer array * @return: */ public void moveZeroes(int[] nums) { // write your code here int z = 0, n = 0; while(n < nums.length) { if(nums[n] != 0) { int temp = nums[z]; nums[z] = nums[n]; nums[n] = temp; z++; } n++; } } }

思路： 一看到求连续sum的就要考虑prefixsum。 代码如下： public class Solution { /* * @param nums: a list of integers. * @param k: length of window. * @return: the sum of the element inside the window at each moving. */ public int[] winSum(int[] nums, int k) { // write your code here int[] preSum = new int[nums.length + 1]; List<Integer> list = new ArrayList<>(); for(int i = 1; i <= nums.length; i++) { preSum[i] = preSum[i-1] + nums[i-1]; if(i >= k) { list.add(preSum[i] - preSum[i - k]); } } int[] res = new int[list.size()]; int i = 0; for(int n: list) { res[i++] = n; } return res; } }

思路： 去重，是去答案的重，所以要在sum == target的时候去。

2/22/2018 update 这道题还是挺有意思的，用于拓宽思路。 Binary search solution: class Solution { public int [] intersection ( int [] nums1, int [] nums2) { if (nums1 == null || nums2 == null || nums1 . length == 0 || nums2 . length == 0 ) return new int []{}; Set< Integer > set = new HashSet<> (); Arrays . sort(nums2); for ( int n : nums1) { if (search(nums2, n)) { set . add(n); } } int [] res = new int [set . size()]; int index = 0 ; for ( int n : set) { res[index ++ ] = n; } return res; } private boolean search ( int [] nums, int target) { int l = 0 , r = nums . length - 1 ; while (l + 1 < r) { int mid = l + (r - l) / 2 ; if (nums[mid] <= target) { l = mid; } else { r = mid; }

2/23/2018 update 从大到小merge， 可以不用考虑nums1里面数的位置问题。如果nums1[i]很大就被一道后面去了，如果nums[i]很小，就保持不变就行了。nums1[i]不可能移到前面。最后只需要检查nums2是否为空。 Solution: class Solution { public void merge ( int [] nums1, int m, int [] nums2, int n) { int i = m - 1 ; int j = n - 1 ; int t = m + n - 1 ; while (i >= 0 && j >= 0 ) { if (nums1[i] < nums2[j]) { nums1[t -- ] = nums2[j -- ]; } else { nums1[t -- ] = nums1[i -- ]; } } while (j >= 0 ) { nums1[t -- ] = nums2[j -- ]; } } } ------------------------------------------- ------------------------------------------- ------------------------------------ 思路： 从大到小开始merge, 如果从小到大，需要把A后面的数往后挪，挪数组的时间复杂度是O(n)。 代码如下 public class Solution { /* * @param A: sorted integer array A which has m elements, but size of A is m+n * @param m: An integer * @param B: sor

思路： A和B从index 0开始挨个对比，谁小先取谁到新数组中。最后检查A或者B如果有剩余就把剩下的全部放到C中。 实现： if(i != A.length) { while(i != A.length) { C[q++] = A[i++]; } } 最后一步检查，我用了多余的if， 直接用while就好了，while本身也包含条件判断。

6/11/2018 update: Why use R value instead of L when len is odd? Because cutR starts  with nums1.length, the mid point drops on right, so that the right part has more numbers. 这道题到道理懂，会实现。但是为什么这样实现还是一头雾水。为什么cutL要从length开始，二分条件是cutL <= cutR? -------------------------------------------------------------------------------------------------------------------------- 01/19/2018 Problem: There are two sorted arrays  nums1  and  nums2  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)). Example 1: nums1 = [1, 3] nums2 = [2] The median is 2.0 Example 2: nums1 = [1, 2] nums2 = [3, 4] The median is (2 + 3)/2 = 2.5 Analysis: L1 L2 nums1: 3 5 | 8 9 cut1: 2 nums2: 1 2 7 | 10 11 12 cut2: 3 R1 R2 nums3: 1 2 3 4 5 7 | 8 9 10 11 12 See the above table. If the cuts reach median, L1, L2, R1 and R2 satisfy the below conditions: L1 <= R2 R1 <= L2 Then use binary search to tune cut1. 

思路： 这道题十分无聊，求non-overlapping 2个sub array加起来最大的和。先把从左往右的max subarray求出来，再求从右往左的。然后遍历数组，打擂台 max = Math.max(max, left[i] + right[i + 1]) 。为什么parameter要用List不用数组，有什么意义？难道是要我们掌握nums.get(i)。 还有一道更无聊的题 Maximum Subarray Difference，真是体力活，一共要求4个数组分别是leftMax[], leftMin[], rightMax[], rightMin[]。如果有公司面试面这种题，那肯定是公司面试官脑子进水了。

Problem: Given an array consisting of  n  integers, find the contiguous subarray whose  length is greater than or equal to   k  that has the maximum average value. And you need to output the maximum average value. Example 1: Input: [1,12,-5,-6,50,3], k = 4 Output: 12.75 Explanation: when length is 5, maximum average value is 10.8, when length is 6, maximum average value is 9.16667. Thus return 12.75. Note: 1 <=  k  <=  n  <= 10,000. Elements of the given array will be in range [-10,000, 10,000]. The answer with the calculation error less than 10 -5  will be accepted. Analysis: 6/20/2018 update: Use binary search to guess the average value. And make sure the error is within 0.00001. To compare the average, for instance, a1, a2, a3, a4 and b1, b2, b3, b4. If (a1-b1) + (a2-b2)  + (a3-b3) + (a4-b4) > 0, we can tell that a's average is greater than b. preSum is the sum that k away from current index( subaray length greater than or equal to k

Problem: Given an integer arrays, find a contiguous subarray which has the largest sum and length should be greater or equal to given length  k . Return the largest sum, return 0 if there are fewer than k elements in the array. Analysis: 2/26/2018 update 这道题的坑真多。 1. corner case include when k > nums.length 2. sliding window problem, maxSum's inital value needs to be sum(0, k). 3. Maintain a minSum that k distance away from the current location. Solution: public class Solution { /** * @param nums: an array of integer * @param k: an integer * @return : the largest sum */ public int maxSubarray4 ( int [] nums, int k) { // write your code here if (nums == null || nums . length == 0 || nums . length < k) { return 0 ; } int minSum = 0 , sum = 0 , min = 0 , max = 0 ; for ( int i = 0 ; i < k; i ++ ) { max += nums[i]; } sum = max;

Problem: Given an integer array, find a subarray with sum closest to zero. Return the indexes of the first number and last number. 2/23/2018 update Again well explained below. Solution with better format: public class Solution { /* * @param nums: A list of integers * @return: A list of integers includes the index of the first number and the index of the last number */ class Pair { int index; int sum; public Pair ( int index, int sum) { this . index = index; this . sum = sum; } } public int [] subarraySumClosest ( int [] nums) { // write your code here if (nums == null || nums . length == 0 ) return new int []{}; Pair [] pairs = new Pair [nums . length + 1 ]; pairs[ 0 ] = new Pair ( - 1 , 0 ); int sum = 0 ; for ( int i = 0 ; i < nums . length; i ++ ) { sum += nums[i]; pairs[

思路： 用当前节点next的值取代当前值。然后删掉node.next。一开始没想出来，这种题做一次就会了。

思路： 用merge sort的思想来做很简单，时间复杂度是O(nlogn)。因为没一次递归都要遍历链表找中点。 另一种是inorder traversal, 实在是太巧妙了，估计面试的时候想不出来。 实现： 关于找中点slow和fast初始化问题, fast =  head or fast  =  head.next对于最后结果并没有什么影响。

思路： Merge sort. 实现： 先排序mid.next, 在排序head。在排序head之前mid.next = null。 具体merge的时候，循环走完后检查left和right是否为空，如果不为空, 根据链表的特性，直接链接到temp上，不用再一个node一个node的加。

思路： 快慢指针，和找mid不同的是fast初始指向head.next。找到circle， head也开始往后走，当head == slow.next的时候head就是入口。

思路： 做法非常直观就不再赘述。难点是如何处理k。k>=0，情况就很多了。k会超过linked list的长度。k超过size倍数的部分就没有意义。直接对size取模就好了。k = k%size。

Problem: Given a singly linked list  L :  L 0 → L 1 →…→ L n -1 → L n , reorder it to:  L 0 → L n → L 1 → L n -1 → L 2 → L n -2 →… You may  not  modify the values in the list's nodes, only nodes itself may be changed. Example 1: Given 1->2->3->4, reorder it to 1->4->2->3. Example 2: Given 1->2->3->4->5, reorder it to 1->5->2->4->3. 05/02/2018 update: 这道题做完了，感觉linked list功力又上一层。把这一遍刷linked lsit总结的东西都用上了。所以在merge的时候想出来了最易读，效率最高点的方法。beat 100%。 Find mid和parlindrome list一样 fast 从head.next开始。mid.next = null是我自己想出来的。因为reverse过后，mid.next实际上还是指向之前的mid.next,要重构linked list必须把它指向null。 在merge的时候做法比较直接。head.next 指向secHead, secHead.next 指向 head.next, head.next和secHead.next会丢失，更新，所以需要先cache他们。 while条件只判断secHead != null就行了，因为secHead.length <= head.length。 class Solution { public void reorderList ( ListNode head) { if (head == null) return ; ListNode mid = findMid(head); ListNode secHead = reverse(

如何判断while循环里面的条件。一般来说是结束的时候，如果不清楚则看while里面，需要用到next的ListNode不为空。 如果node在后面的操作中会丢失，那么先要cache。比如reverse里面的，cur.next会丢失。 1. Reverse 其实reserse就只有有个操作，cur.next = prev，其它的就是调整pre 和cur。 ListNode prev = null; ListNode cur = mid; while(cur != null) { ListNode temp = cur.next; cur.next = prev; prev = cur; cur = temp; } return prev; 2. Merge while (l1 != null) { ListNode n1 = l1.next, n2 = l2.next; l1.next = l2; if (n1 == null) break; l2.next = n1; l1 = n1; l2 = n2; } 3. Find mid and cut ListNode slow = head; ListNode fast = head; ListNode prev = null; while(fast != null && fast.next != null) { prev = slow; slow = slow.next; fast = fast.next.next; } prev.next =null; return slow; 4. Determine cycle public boolean hasCycle(ListNode head) { if (head == null || head.next

12/27/2017 update 1. have to check random == null when match random. 2. original list can not be modified. -------------------------------------------------------------------- 思路： 2种方法 1. hash map key是old node, value是新node。然后再匹配next和random。空间复杂度是O(n) 2. O(1) 1->2->3->null 变成1->1'->2->2'->3->3'->null，然后拷贝random，最后split。 实现： 第二种方法split说一下。需要一个temp node来迭代新的 linkedlist。每一次取node.next.next的时候，要坚持node.next是否为空。代码如下： /** * Definition for singly-linked list with a random pointer. * class RandomListNode { * int label; * RandomListNode next, random; * RandomListNode(int x) { this.label = x; } * }; */ public class Solution { public RandomListNode copyRandomList(RandomListNode head) { if(head == null){ return null; } head = insert(head); head = matchRandom(head); return split(head); } private RandomListNode insert(RandomListNode head) { R

Problem: Reverse a linked list from position  m  to  n . Do it in one-pass. Note:  1 ≤  m  ≤  n  ≤ length of list. Example: Input: 1->2->3->4->5->NULL, m = 2, n = 4 Output: 1->4->3->2->5->NULL 5/1/2017 update: 第三遍是自己想出来的one pass。 主要是搞清楚怎么把m 到n reverse过后的头和尾和原链表链接起来。 class Solution { public ListNode reverseBetween ( ListNode head, int m, int n) { ListNode dummy = new ListNode ( 0 ); dummy . next = head; ListNode prev = dummy; ListNode beforeM = null; for ( int i = 0 ; i < m - 1 ; i ++ ) { prev = prev . next; } beforeM = prev; prev = prev . next; ListNode cur = prev . next, tail = prev; for ( int i = 0 ; i < n - m; i ++ ) { ListNode next = cur . next; cur . next = prev; prev = cur; cur = next; } beforeM . next = prev;

Problem: Given a linked list and a value  x , partition it such that all nodes less than  x  come before nodes greater than or equal to  x . You should preserve the original relative order of the nodes in each of the two partitions. Example: Input: head = 1->4->3->2->5->2, x = 3 Output: 1->2->2->4->3->5 5/30/2018 update: Analysis: Copy val of node and create new one is cheating. Can not pass interview. How to partition is intuitive. But remember to cut greater parts last node, assign its next to null to avoid cycle. Solution: class Solution { public ListNode partition ( ListNode head, int x) { if (head == null) return null; ListNode dummy1 = new ListNode ( 0 ); ListNode dummy2 = new ListNode ( 0 ); ListNode p1 = dummy1, p2 = dummy2; while (head != null) { if (head . val < x) { p1 . next = head; p1 = head; } else {

5/5/2018 update: 12/21/2017 update A better and more concise approach. Two points need to keep in mind. 1.  the newHead needs to be stored before adjust the list. 2. counter location is no longer accurate after reversing. /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseKGroup ( ListNode head, int k) { ListNode dummy = new ListNode ( 0 ); ListNode counter = head; dummy . next = head; head = dummy; int count = 0 ; while (counter != null) { count ++ ; if (count % k == 0 ) { // reverse ListNode prev = head . next; ListNode cur = head . next . next; for ( int i = 0 ; i < k - 1 ; i ++ ) { ListNode temp = cur . next; cur . next = prev; pre