刷题记录

Problem: Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. For example: Given the below binary tree and  sum = 22 , 5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1 return true, as there exist a root-to-leaf path  5->4->11->2  which sum is 22. Analysis: From top to bottom, subtract sum by root.val. Once reach bottom, check whether val minus remaining sum == 0. Solution: /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean hasPathSum(TreeNode root, int sum) { if (root == null) return false; if (root.left == null && root.right == null && root.val - sum == 0) retu...

Analysis: Can not take min of left and right, it is possible one of them is null. Solution: /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int minDepth(TreeNode root) { if (root == null) return 0; if (root.right == null && root.left != null) return minDepth(root.left) + 1; if (root.left == null && root.right != null) return minDepth(root.right) + 1; return Math.min(minDepth(root.left), minDepth(root.right)) + 1; } }

Problem: Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes. You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity. Example: Given  1->2->3->4->5->NULL , return  1->3->5->2->4->NULL . Note: The relative order inside both the even and odd groups should remain as it was in the input. The first node is considered odd, the second node even and so on ... 05/02/2018 update: Convert the linkedlist to two linked lists above. There are two reasons to have this while condition. 1. when even.next == null, we reached the end. 2. odd.next points to even.next then odd goes one step further to odd.next. We have to make sure even.next is not null. Analysis: It's similar to copy randomlist. Just the last step split of copy random list. But have to be cautious about...

Problem: Given a linked list, swap every two adjacent nodes and return its head. For example, Given  1->2->3->4 , you should return the list as  2->1->4->3 . 5/1/2018 update: First.next is like next in regular reverse.  -------------------------------------------------------------------------------------------------------------------------------------------- Analysis: Simple reverse linked list, but need to think about how to handle head. dummy不是随便一初始化就行了，需要考虑dummy的安置问题，不留死角。 Solution: cur.next 把head给转移到了second, 然后cur就完成了任务，继续下一次reverse。 class Solution { public ListNode swapPairs ( ListNode head) { if (head == null) return null; ListNode dummy = new ListNode ( 0 ); dummy . next = head; ListNode prev = dummy; while (prev . next != null && prev . next . next != null) { ListNode first = prev . next, second = prev . next . next; firs...

Problem: You are given two  non-empty  linked lists representing two non-negative integers. The digits are stored in  reverse order  and each of their nodes contain a single digit. Add the two numbers and return it as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself. Example Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 Explanation: 342 + 465 = 807. 7/22/2018 update: It it different from merge two sorted list. This one uses || the other one uses &&. class Solution { public ListNode addTwoNumbers ( ListNode l1 , ListNode l2 ) { ListNode dummy = new ListNode ( 0 ) ; ListNode head = dummy ; int carry = 0 ; while ( l1 ! = null | | l2 ! = null | | carry = = 1 ) { int num1 = l1 = = null ? 0 : l1 . val ; int num2 = l2 = = null ? 0 : l2 . val ; int num = num1 + num2 + carry ; carry = num / 10...

Revert right half, when remaining <= right half we know we have reached the mid. There is a special case when x ends with 0.

Problem: Given a non-negative integer represented as a  non-empty  array of digits, plus one to the integer. You may assume the integer do not contain any leading zero, except the number 0 itself. The digits are stored such that the most significant digit is at the head of the list. Analysis: There is no need to has a carry boolean variable. If there is carry, go through plus one to next digit. Solution: class Solution { public int[] plusOne(int[] digits) { boolean hasCarry = false; int len = digits.length; for (int i = len - 1; i >= 0; i--) { if (digits[i] < 9) { digits[i]++; return digits; } digits[i] = 0; } int[] res = new int[len + 1]; res[0] = 1; return res; } }

Analysis: Need to consider overflow. It's easy to use long instead of int when handling overflow issue. Solution: class Solution { public int reverse(int x) { long res = 0; while (x!=0) { res *= 10; res += x%10; x /= 10; if (res > Integer.MAX_VALUE || res < Integer.MIN_VALUE) return 0; } return (int)res; } }

Problem: Given two strings  s  and  t , determine if they are both one edit distance apart. Note:   There are 3 possiblities to satisify one edit distance apart: Insert a character into  s  to get  t Delete a character from  s  to get  t Replace a character of  s  to get  t Example 1: Input: s = "ab", t = "acb" Output: true Explanation: We can insert 'c' into s  to get  t. Example 2: Input: s = "cab", t = "ad" Output: false Explanation: We cannot get t from s by only one step. Example 3: Input: s = "1203", t = "1213" Output: true Explanation: We can replace '0' with '1' to get  t. Analysis : 8/3/2018 update: 这一次用的方法非常屌。在循环内不用考虑长度大小问题，循环肯定按照长度小的来。和Median of Two sorted array一样，用递归解决。刷题功力又上一层了。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution { public boolean isOneEditDistance ( String s , String t ) { ...

Problem: Given a string  s , find the longest palindromic substring in  s . You may assume that the maximum length of  s  is 1000. Example: Input: "babad" Output: "bab" Note: "aba" is also a valid answer. Example: Input: "cbbd" Output: "bb" 5/22/2018 update: No need to think about after while loop, whether start and end are valid or not. Just update palindrome length within the loop. class Solution { int max = 1 ; int start = 0 ; public String longestPalindrome ( String s) { if (s == null || s . length() == 0 ) return "" ; for ( int i = 0 ; i < s . length() - 1 ; i ++ ) { computePalindrome(s, i, i); computePalindrome(s, i, i + 1 ); } return s . substring(start, start + max); } private void computePalindrome ( String s, int l, int r) { int temp = 0 , len = 0 ; while (l ...

Problem: Given a sorted integer array without duplicates, return the summary of its ranges. Example 1: Input: [0,1,2,4,5,7] Output: ["0->2","4->5","7"] Example 2: Input: [0,2,3,4,6,8,9] Output: ["0","2->4","6","8->9"] Analysis : Still, overflow problem. Use index instead of actual value solves overflow issue. Solution: public class Solution { public List<String> summaryRanges(int[] nums) { List<String> summary = new ArrayList<>(); for (int i = 0, j = 0; j < nums.length; ++j) { // check if j + 1 extends the range [nums[i], nums[j]] if (j + 1 < nums.length && nums[j + 1] == nums[j] + 1) continue; // put the range [nums[i], nums[j]] into the list if (i == j) summary.add(nums[i] + ""); else summary.add(nums[i] + "->" + nums[j]); ...

Problem: Given a sorted integer array where  the range of elements are in the inclusive range [ lower ,  upper ] , return its missing ranges. For example, given  [0, 1, 3, 50, 75] ,  lower  = 0 and  upper  = 99, return  ["2", "4->49", "51->74", "76->99"]. Analysis: It is hard to check the boundaries, so add lower - 1 and upper + 1 to the nums array. However, adding or subtracting would cause overflow issue. It is too much to consider over flow for this problem. So use long instead of int to avoid overflow. Solution: class Solution { public List<String> findMissingRanges(int[] nums, int lower, int upper) { List<String> result = new LinkedList<>(); long prev = (long)lower - 1; for (int i = 0; i <= nums.length; i++) { long cur = (i == nums.length) ? ((long)upper + 1) : (long)nums[i]; if (cur - prev >= 2) { result.add(get...

Problem: Given a string, find the length of the longest substring T that contains at most  k  distinct characters. For example, Given s =  “eceba”  and k = 2, T is "ece" which its length is 3. 3/1/2018 update: Solution follow template: class Solution { public int lengthOfLongestSubstringKDistinct ( String s, int k) { if (s == null || s . length() == 0 ) return 0 ; int l = 0 , r = 0 , counter = 0 , res = 0 ; int [] map = new int [ 256 ]; while (r < s . length()) { if (map[s . charAt(r ++ )] ++ == 0 ) counter ++ ; // not satisfy while (counter > k) { // move left pointer if (map[s . charAt(l ++ )] -- == 1 ) counter -- ; } // update result res = Math . max(res, r - l); } return res; } } Analysis: The key point of this sort of problem is t...

Problem: Given a string, find the length of the  longest substring  without repeating characters. Examples: Given  "abcabcbb" , the answer is  "abc" , which the length is 3. Given  "bbbbb" , the answer is  "b" , with the length of 1. Given  "pwwkew" , the answer is  "wke" , with the length of 3. Note that the answer must be a  substring ,  "pwke"  is a  subsequence  and not a substring.

Analysis : Leetcode上面90个赞，785个踩，和String to integer是难兄难弟。考到的几率很小。 Solution: class Solution { public boolean isNumber(String s) { int i = 0, n = s.length(); boolean isNumber = false; // start space while (i

无聊的题目，leetcode上177赞，1808踩。代码如吓： 反正记住result一开始用double就好了。 public class Solution { public int myAtoi(String str) { if( str.length() < 1|| str==null) return 0; str=str.trim(); char flag='+'; int i=0; double result=0; if(str.charAt(0)=='-') { flag='-'; i++; }else if(str.charAt(0)=='+') { i++; } while(str.length()>i&&str.charAt(i)>='0'&&str.charAt(i)<='9') { result=result*10+(str.charAt(i)-'0'); i++; } if(flag=='-') result=-result; // handle max and min if (result > Integer.MAX_VALUE) return Integer.MAX_VALUE; if (result < Integer.MIN_VALUE) return Integer.MIN_VALUE; return (int) result; } }

Problem: Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters. The input string does not contain leading or trailing spaces and the words are always separated by a single space. For example, Given s = " the sky is blue ", return " blue is sky the ". Could you do it  in-place  without allocating extra space? Analysis: Similar to rotate array, if a word is detected, reverse the word. Then reverse the whole string.  Solution: class Solution { public void reverseWords(char[] str) { if (str == null || str.length == 0) { return; } int start = 0; for (int end = 0; end < str.length; end++) { if (end == str.length - 1 || str[end+1] == ' ') { reverse(start, end, str); start = end + 2; } } reverse(0, str.length - 1, str); } private void reverse(int start, int end, char[] str) { ...