70. Climbing StairsThis problem it seem just like Tower of Hanoi,so we can use the same idea to solve this problem$1 stair:1=1+0$​​​$2stairs: 2=1+1=2$$3stairs:1stair+2stairs=3=1+1+1=1+2=2+1$$4stairs:3stairs+2stairs=5=2+2=1+1+1+1=2+1+1=1+2+1=1+1+2$solution public int climbStairs(int n) { //p is stair0,q is stair1,result is sum of two stairs int p = 0, q = 1, result = 0; //result is 1,2,3,4... for (int i = 0; i < n; i++) { result = p + q; p = q; q = result; } return result; }83. Remove Duplicates from Sorted ListThis problem is a easy Singly linked list problem.If you want to learn more about Singly linked list,you can read more in my blog Data Structure Chapter5.solution public ListNode deleteDuplicates(ListNode head) { //if ListNode is [],just return if (head == null) { return head; } //marked the old head ListNode oldHead = head; //form head to tail while (head.next != null) { //compare each node if (head.val == head.next.val) { head.next = head.next.next; } else { head = head.next; } } //return the head return oldHead; }88. Merge Sorted ArrayThis problem is a very easy problem.We can use double pointer solve this problem easily.solution public void merge(int[] nums1, int m, int[] nums2, int n) { //make a new array to get the answer int[] result = new int[m + n]; //beginning from both head int i = 0, j = 0, temp; while (i < m || j < n) { if (i == m) { //if nums1 is ending just copy the nums2 temp = nums2[j++]; } else if (j == n) { //if nums2 is ending just copy the nums1 temp = nums1[i++]; } else if (nums1[i] < nums2[j]) { //copy the smaller number temp = nums1[i++]; } else { temp = nums2[j++]; } result[i + j - 1] = temp; } //copy the answer to the nums1 for (int length = 0; length < n + m; length++) { nums1[length] = result[length]; } }94. Binary Tree Inorder TraversalUse recursion to solve this problem.This problem is a very symble in Binary Tree.I wrote a very detailed note about Binary Tree Data Structure Chapter11.You can read it and clear how to Inorder traversal.And Inorder, Preorder and Postordersolution public List<Integer> inorderTraversal(TreeNode root) { //make an array to store the notes ArrayList<Integer> array = new ArrayList<>(); //use the method midErgodic(root, array); //return the array return array; } public void midErgodic(TreeNode root, List<Integer> array) { //this root is not exist if (root == null) { return; } //recursion the left note if (root.left != null) { midErgodic(root.left, array); } //add this root into the arrays array.add(root.val); //recursion the right root if (root.right != null) { midErgodic(root.right, array); } }100. Same TreeThis problem is a sequence traversal of binary tree.I wrote the detailed ideads in my notes Data Structure Chapter11.The main idea is search from the root,and search left and right.But you must be attention is if the location is null,you must compare with the another tree the same location too.If you use the ArrayList to store data,you must store the null not only the numbers,Because the [1,2]is not the same[1,null,2].So i can use the recursive to solve this problem too.There's one thing we must be atention.right solutionelse if (p.val != q.val) { return false; } else { return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); }failed solutionelse if (p.val == q.val) { return true; } else { return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); }If the same location is equal.We must judge the left and right tree,If we use the failed solution.Such as [1,2]and[1,null,2],we can't judge the subtree.solution public boolean isSameTree(TreeNode p, TreeNode q) { if (p == null && q == null) { //if the same location is null,then this location is true return true; } else if (p == null || q == null) { //if one is null,the another one is not null,return false return false; } else if (p.val != q.val) { //we can't use p.val==q.val return true.If will judgement after interruption return false; } else { //recursive the same location return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); } }101. Symmetric TreeThis problem has two solutions,but the main idea is the same.I make some examplesA B B A trueA null falseA null null A falseThe tree only have a root is trueSo I can use recursively and iteratively to solve this problem.recursionTermination conditionleft is not equal to right,or left and right are both nullrecursive comparison each tree,both two tree roots are the same.and left.left equals to right.right,left.right equals to right.leftsolution1 public boolean isSymmetric(TreeNode root) { //the root is not to judge,we judge the subtree return symmetric(root.left, root.right); } public boolean symmetric(TreeNode p, TreeNode q) { //null null is the symmetric if (p == null && q == null) { return true; } else if (p == null || q == null) { //null number or number null is not symmetric return false; } else { //val is equal and the left subtree and right subtree is symmetric,it is true return p.val == q.val && symmetric(p.left, q.right) && symmetric(p.right, q.left); } }iterationWe can make a Queue to store the note.Just like Push and Pop.The conparison method is similar to recursion.roots are the same,left.left==right.right,left.right==right.left.Until the Queue is empty,it means the tree is symmetricsolution2 public boolean isSymmetric(TreeNode root) { //if root is null or only have the root if (root == null || (root.left == null && root.right == null)) { return true; } //make a LinkedList to store the notes LinkedList<TreeNode> Queue = new LinkedList<>(); //add the left node and right node Queue.add(root.left); Queue.add(root.right); //iterate through the loop while (Queue.size() > 0) { //pop the first node TreeNode leftNode = Queue.removeFirst(); //pop the second node TreeNode rightNode = Queue.removeFirst(); //if left is null and right is null if (leftNode == null && rightNode == null) { continue; } else if (leftNode == null || rightNode == null) { //left is number and right is null or right is number and left is null return false; } else if (leftNode.val != rightNode.val) { //values are not equal return false; } //make a example A(1) B(1) B(2) A(2) //add A(1) Queue.add(leftNode.left); //add A(2) Queue.add(rightNode.right); //add B(1) Queue.add(leftNode.right); //add B(2) Queue.add(rightNode.left); } //if the Queue is empty,so it is true return true; }104. Maximum Depth of Binary TreeThis problem is a vary easy problem.If we have a clear thinking it is easy to solve it.Implementation stepsIf the root is null,so the max depth is 0count the left subtree depthcount the right subtree depthmax depth of the current tree = the greater of the max depth of the left subtree and the max depth of the right subtreesolution public int maxDepth(TreeNode root) { return maxDepthSolution(root); } private int maxDepthSolution(TreeNode x) { //if node is null,so the depth is 0 if (x == null) { return 0; } //define two variables,x.left tree's depth,x.right tree's depth int maxL = 0, maxR = 0; //count the depth if (x.left != null) { maxL = maxDepthSolution(x.left); } if (x.right != null) { maxR = maxDepthSolution(x.right); } //compare the two depth,return the max and plus 1 return maxL > maxR ? maxL + 1 : maxR + 1; }108. Convert Sorted Array to Binary Search TreeThis problem is a In-order traversal problem.Becasue the characteristic of in-order traversal is orderly.The alphabetical order is in order.Just like the nums.You can find that the mid number is the subtree's root.The reminds me of binary search.We always find the mid number.if we choose the mid left number as the root,it means the small number as the right subtree.if we choose the mid right number as the root,it means the big number as the right subtree.solution1 public TreeNode sortedArrayToBST(int[] nums) { return put(nums, 0, nums.length - 1); } private TreeNode put(int[] nums, int left, int right) { //find the mid if (left > right) { return null; } //always choose the number to the left of the middle position as the root node int mid = (left + right) / 2; //make the node tree TreeNode treeNode = new TreeNode(nums[mid]); //recursive call the put function treeNode.left = put(nums, left, mid - 1); treeNode.right = put(nums, mid + 1, right); return treeNode; }solution2 public TreeNode sortedArrayToBST(int[] nums) { return put(nums, 0, nums.length - 1); } private TreeNode put(int[] nums, int left, int right) { if (left > right) { return null; } int mid = (left + right + 1) / 2; TreeNode treeNode = new TreeNode(nums[mid]); treeNode.left = put(nums, left, mid - 1); treeNode.right = put(nums, mid + 1, right); return treeNode; }110. Balanced Binary TreeThis problem is the Problem104 Tree Depth Upgraded version.If you want to understand this problem,you must undertand Problem104.You can read my blog LeetCode EasyTopic Notes3 and Data Structure Chapter11.Let's analyze this problem.We must to find whether each layer is balancedIf the number of layers differs by more than 1,the tree is not balancedWe can find from the beginning and compare each layer from the beginningWe can also start form the backSolution1 beginning from the head public boolean isBalanced(TreeNode root) { //if the root is null,just return null if (root == null) { return true; } else { //if the number of layers differs by more than 1 or the left subtree is not balanced or the // right subtree is not balanced just return false return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right); } } public int height(TreeNode node) { //get each layer subtree max height if (node == null) { return 0; } else { return Math.max(height(node.left), height(node.right)) + 1; } }This solution cost lot of time,because we should start from the root and we did two recursion.So this solution time is $O(n^2)$,space is $O(n)$Solution2 beginning form the tail public boolean isBalanced(TreeNode root) { //if the number of layers differs by more than 1 just return false return maxDepth(root) >= 0; } private int maxDepth(TreeNode x) { if (x == null) { return 0; } //verify the left subtree whether balance int maxL = maxDepth(x.left); //verify the right subtree whether balance int maxR = maxDepth(x.right); //if one layers is -1,just all return -1 if (maxL == -1 || maxR == -1 || Math.abs(maxL - maxR) > 1) { return -1; } //get the max depth return maxL > maxR ? maxL + 1 : maxR + 1; }This solution we just use one recursion,so the time cost just only $O(n)$ and the space is $O(n)$ too.
374. Guess Number Higher or LowerThis question is also a Binary Search question.We can notice one thing.1 <= pick <= n.So this question is search 1 between n.We can search their mid number.If is less than the target just need to update the head.If is bigger than the target just need to update the tail.Solution public int guessNumber(int n) { int head = 1, tail = n; while (head < tail) { int mid = head + (tail - head) / 2; //mid > n if (guess(mid) == -1) { tail = mid - 1; } else if (guess(mid) == 1) { //mid < n head = mid + 1; } else { //find the target return mid; } } //while head==tail return head; }383. Ransom NoteThis question is a little similar to 349. Intersection of Two Arrays We can also use HashMap. The number of occurrences of each letter corresponds to a value.And find all the letters that appear in the first string.Solution1 public boolean canConstruct(String ransomNote, String magazine) { HashMap<Integer, Integer> hashMap = new HashMap<>(); for (int i = 0; i < magazine.length(); i++) { int value = magazine.charAt(i) - 'a'; //if is the first time appear,just set initial value if (!hashMap.containsKey(value)) { hashMap.put(value, 1); } else { //calculate the number of occurrences hashMap.put(value, hashMap.get(value) + 1); } } for (int i = 0; i < ransomNote.length(); i++) { int value = ransomNote.charAt(i) - 'a'; //if don't include this letter,just return false if (!hashMap.containsKey(value)) { return false; } else { //the number of occurrences is less than the number of times needed if (hashMap.get(value) - 1 < 0) { return false; } else { hashMap.put(value, hashMap.get(value) - 1); } } } return true; }But the efficiency of HashMap is not high,we can notice consist of lowercase English letters So we can use array to store the number of occurrences.This solution is simplified.But the core solution idea has not changed.Solution2 public boolean canConstruct(String ransomNote, String magazine) { //26 letters int[] result = new int[26]; for (int i = 0; i < magazine.length(); i++) { result[magazine.charAt(i) - 'a']++; } for (int i = 0; i < ransomNote.length(); i++) { if (result[ransomNote.charAt(i) - 'a'] == 0) { return false; } else { result[ransomNote.charAt(i) - 'a']--; } } return true; }387. First Unique Character in a StringThis question is very similar to 383. Ransom Note.If you understand that question,you can also solve this question easily.We can also use HashMap or ASCII to solve it.Solution1 public int firstUniqChar(String s) { HashMap<Character, Integer> hashMap = new HashMap<>(); for (int i = 0; i < s.length(); i++) { //count the number of occurrences hashMap.put(s.charAt(i), hashMap.getOrDefault(s.charAt(i), 0) + 1); } for (int i = 0; i < s.length(); i++) { //if the number is 1,just return the location of the letter if (hashMap.get(s.charAt(i)) == 1) { return i; } } return -1; }Solution2 public int firstUniqChar(String s) { int[] result = new int[26]; for (int i = 0; i < s.length(); i++) { //use ASCII table to judge the letter result[s.charAt(i) - 'a']++; } for (int i = 0; i < s.length(); i++) { //if the letter's occurrences is 1,just return the location of the letter if (result[s.charAt(i) - 'a'] == 1) { return i; } } return -1; }389. Find the DifferenceThis question is similar to 136. Single Number.We can just traverse the string once.The main idea is XOR or use ASCII.We can set a value to store the difference between each of their elements.It is seems like commutative law of addition.Add the last element of T in the end.Solution1 public char findTheDifference(String s, String t) { int result = 0; for (int i = 0; i < s.length(); i++) { //char - char the result is int result += t.charAt(i) - s.charAt(i); } //use ASCII table to get the letter return (char) (result + t.charAt(t.length() - 1)); }Solution2 public char findTheDifference(String s, String t) { int result = 0; for (int i = 0; i < s.length(); i++) { //use XOR,just like question 136 result ^= s.charAt(i); result ^= t.charAt(i); } return (char) (result ^ t.charAt(t.length() - 1)); }392. Is SubsequenceThis question is also a double pointer question.We can search from the head of s and t.If there are equal,just continue.Solution public boolean isSubsequence(String s, String t) { int i = 0, j = 0; while (i < s.length() && j < t.length()) { //if there are equal,just update the i if (s.charAt(i) == t.charAt(j)) { i++; } //j must update each time j++; } //verify that the value of i is equal to the length of s return i == s.length(); }401. Binary WatchThis question is not a easy question.When i thought about it for the first time,i have no idea.But i gradually discovered that this is an enumeration problem.We can use two HashMap to store hour and minute values separately.Then pair with the other party and verify that it meets the specifications.Solution1 public List<String> readBinaryWatch(int turnedOn) { //make two HashMap to store hour and minutes values separately HashMap<Integer, List<String>> hashHour = new HashMap<>(); HashMap<Integer, List<String>> hashMins = new HashMap<>(); //such as hour : 1,2,4,8 only have one 1 for (int i = 0; i < 12; i++) { int hours = numberOf1(i); hashHour.putIfAbsent(hours, new ArrayList<String>()); hashHour.get(hours).add(i + ""); } //count the minute,get the number of 1 for (int i = 0; i < 60; i++) { int mins = numberOf1(i); hashMins.putIfAbsent(mins, new ArrayList<String>()); //if the minute is 01,02,04,08 if (i < 10) { hashMins.get(mins).add("0" + i); } else { hashMins.get(mins).add(i + ""); } } ArrayList<String> result = new ArrayList<>(); //if the hour's number of 1 is n,so minute's number of 1 is m-n for (int i = 0; i <= turnedOn; i++) { //non-existent situation,just continue if (!hashHour.containsKey(i) || !hashMins.containsKey(turnedOn - i)) { continue; } //enumeration method,paired with each other for (String s : hashHour.get(i)) { for (String s1 : hashMins.get(turnedOn - i)) { result.add(s + ":" + s1); } } } return result; } /** * count the number of 1 in binary */ private int numberOf1(int num) { int count = 0; while (num != 0) { ++count; num &= (num - 1); } return count; }But this question can also be enumerated directly without storing the result of enumeration.The idea of solving the problem as a whole is still the same.Solution2 public List<String> readBinaryWatch(int turnedOn) { ArrayList<String> strings = new ArrayList<>(); //hour for (int i = 0; i < 12; i++) { //minute for (int j = 0; j < 60; j++) { //if n + m = turnedOn if (numberOf1(i) + numberOf1(j) == turnedOn) { //judge the minute strings.add(i + ":" + ((j < 10) ? "0" + j : j)); } } } return strings; } /** * count the number of 1 in binary */ private int numberOf1(int num) { int count = 0; while (num != 0) { ++count; num &= (num - 1); } return count; }
303. Range Sum Query - ImmutableThis question is a very clever question.It requires us to reduce the time required for calculation.We need to pay attention to two points.At most 10^4 calls will be made to sumRange.1 <= nums.length <= 10^4We know use sum to count the result.But if left=0 and right=nums.length-1,the time is n,and the number of calculations is n.So the time is $n^2$.It is easy to time to.But it does not prevent us from writing this kind of code.Solution1class NumArray1 { int[] array; public NumArray1(int[] nums) { array = nums; } public int sumRange(int left, int right) { int result = 0; for (int i = left; i <= right; i++) { result += array[i]; } return result; } }But let's think about it carefully.Why we spend a lot of time,because we spend a lot of time on count the result.Can we spend time on make the array?Because it is only used once.So i came up with designing an array.It's elements store the sum of the previous elements of nums.We can get the difference between the left and right range by subtracting its elements.Solution2class NumArray2 { int[] array; public NumArray2(int[] nums) { int n = nums.length + 1; array = new int[n]; //array[i+1] is the previous elements of nums[0] to nums[i] for (int i = 0; i < nums.length; i++) { array[i + 1] = array[i] + nums[i]; } } public int sumRange(int left, int right) { //array[right+1]=nums[0]+...+nums[right] array[left+1]=nums[0]+...+nums[left] //array[right+1]-array[left+1]=nums[right]-...-nums[left] return array[right + 1] - array[left]; } }326. Power of ThreeThis question is the same as question 231. Power of Two.It also has two solutions.The first solution is universal solution to judge whether is a remainder.Solution1 public boolean isPowerOfThree(int n) { if (n <= 0) { return false; } while (n > 1) { if (n % 3 == 0) { n /= 3; } else { return false; } } return true; }The second solution is a very clever solution.We know that n is in the range of int.So the largest power of 3 in int is 1162261467.We can directly judge whether this number is a divisor of 1162261467Solution2 public boolean isPowerOfThree(int n) { return n > 0 && 1162261467 % n == 0; }338. Counting BitsThis is a very interesting problem.We have two solutions.But their core idea are all bit operation.First,let us consider how to calculate the number of 1 in a binary number.We can use & operation.public static int bitCount(int n){ int count = 0; while(n != 0){ n = n & (n - 1); count++; } return count; }So we can traverse the n,get each number of 1.But this solution time is $O(nlogn)$,space is $O(1)$Solution1 public int[] countBits(int n) { //make the result array int[] result = new int[n + 1]; //result[0] default is 0 for (int i = 1; i <= n; i++) { //record the current number int j = i; //calculate the number of 1 int a = i; int count = 0; while (a != 0) { a = a & (a - 1); count++; } //record into array result[j] = count; } return result; }Let's think about why the time is $O(nlogn)$.Because we have to recalculate the 1 in each number.How can we avoid this situation?We know power of two only have 1 1.1=12=13=24=15=26=27=38=1How can we judge whether the number is power of two?You must know the question 231. Power of Two.if(i&(i-1))==0.So this number is power of two.The number of 1 is 1.And let this number bit=1result[i]=result[i-bit]+1So this solution time has became $O(n)$Solution2 public int[] countBits(int n) { int[] result = new int[n + 1]; int bit = 0; for (int i = 1; i <= n; i++) { //judge the number whether is power of two if ((i & (i - 1)) == 0) { bit = i; } //the main code result[i] = result[i - bit] + 1; } return result; }342. Power of FourThis question is a very easy question.It has a same solution with 326. Power of Three.You can read it in my Blog.Solution1 public boolean isPowerOfFour(int n) { if (n <= 0) { return false; } while (n > 1) { if (n % 4 == 0) { n /= 4; } else { return false; } } return true; }But this question is very similar with question 231. Power of Two.You can read my Blog LeetCode EasyTopic Notes7.As we all know 4 is the power of 2.So if it is a power of 2,it must be a power of 4.But how about number 8.It isn't the power of 4 but it is the power of 2.$4\div3=1...1$If there is a number is power of 2 and not the power of 4,just like 8.It can be written by $n=4^x\times2$$8=4\times2$$8\div3=(4\div3)\times2=2...2$So the remainder of this number divided by 3 must be 2 instead of 1Solution2 public boolean isPowerOfFour(int n) { return n > 0 && (n & (n - 1)) == 0 && n % 3 == 1; }344. Reverse StringThis is a very easy question.We just need use two pointers can solve it.Solution public void reverseString(char[] s) { int head = 0, tail = s.length - 1; //swap the head and the tail,until they are meeting while (head <= tail) { char temp = s[head]; s[head] = s[tail]; s[tail] = temp; head++; tail--; } }345. Reverse Vowels of a StringThis is an upgraded version of 344. Reverse String.If you want to solve this question,you must understand that question.This question the main idea is determine whether a letter is a vowel.And we must notice a situation.,.If we still move two pointers.There will be a cross-border situation.Solution public String reverseVowels(String s) { int head = 0, tail = s.length() - 1; //we can change the string,so we change it into a char array char[] array = s.toCharArray(); //use two pointer while (head < tail) { //make this judgement head < tail is to avoid ",." cross-border situation while (head < tail && vowele(array[head])) { head++; } while (head < tail && vowele(array[tail])) { tail--; } if (head >= tail) { break; } //swap the two pointers char swap = array[head]; array[head] = array[tail]; array[tail] = swap; head++; tail--; } return new String(array); } /** * determine whether a letter is a vowel */ private boolean vowele(char ch) { return !(ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' || ch == 'A' || ch == 'E' || ch == 'I' || ch == 'O' || ch == 'U'); }349. Intersection of Two ArraysThis question is a easy question,We can use two solutions to solve it.The first thing that comes to mind must be HashSet.We can use two HashSet to store each elements.Solution1 public int[] intersection(int[] nums1, int[] nums2) { HashSet<Integer> hashSet1 = new HashSet<>(); HashSet<Integer> hashSet2 = new HashSet<>(); //add elements into hashSet1 for (int i : nums1) { hashSet1.add(i); } for (int i : nums2) { //exclude elements not included if (hashSet1.contains(i)) { hashSet2.add(i); } } int[] result = new int[hashSet2.size()]; int index = 0; //take all elements in hashSet2 into array for (Integer integer : hashSet2) { result[index++] = integer; } return result; }The second solution we can use sort.So the two nums will change.1 1 2 22 2If the current element is the same as another element,and not the same as the previous element in the answer array.So is the new element.If one party is smaller than the other,update the data.Solution2 public int[] intersection(int[] nums1, int[] nums2) { //sort the two nums Arrays.sort(nums1); Arrays.sort(nums2); //because the result length must be less than or equal to the nums2 or nums1 int index1 = 0, index2 = 0, n = 0; while (index1 < nums1.length && index2 < nums2.length) { //if are equal if (nums1[index1] == nums2[index2]) { //and not the same as the previous element,just updata if (n == 0 || nums1[index1] != nums2[n - 1]) { nums2[n++] = nums1[index1]; } index1++; index2++; } else if (nums1[index1] > nums2[index2]) { index2++; } else { index1++; } } //copy the same length of result return Arrays.copyOfRange(nums2, 0, n); }350. Intersection of Two Arrays IIThis question is the update version of question 349. Intersection of Two Arrays.But it is also a easy problem.This question the best solution i think is use HashMap.As we all know HashMap has <Key,Value>.A element can be regarded as a key.The number of times it appears is the value.When it appears in another array,we just need --.Make its value greater than 0,we can get the minimum number of occurrences.Solution public int[] intersect(int[] nums1, int[] nums2) { HashMap<Integer, Integer> hashMap1 = new HashMap<>(); for (int i : nums1) { //if is the first time appear,just give a default value of 1 if (!hashMap1.containsKey(i)) { hashMap1.put(i, 1); } else { //plus the value 1 hashMap1.put(i, hashMap1.get(i) + 1); } } //length of calculation result int n = 0; for (int i : nums2) { //if have the same key,and value > 0,just add into the result array if (hashMap1.containsKey(i) && hashMap1.get(i) > 0) { nums2[n++] = i; hashMap1.put(i, hashMap1.get(i) - 1); } } return Arrays.copyOfRange(nums2, 0, n); }367. Valid Perfect SquareThis question is also a Binary Search question.But one thing it needs to pay attention to is that it may cross the boundary.If an out-of-bounds occurs,the wrong answer will be returned.Solution public boolean isPerfectSquare(int num) { //1 is true if (num == 1) { return true; } //use long to store the calculation result long head = 2, tail = num; while (head <= tail) { long mid = head + (tail - head) / 2; if (mid * mid > num) { tail = mid - 1; } else if (mid * mid < num) { head = mid + 1; } else { return true; } } return false; }
242. Valid AnagramThis question is similar to question 205. Isomorphic Strings. They have similarities.We can also use ASCII table to solve it.Solution1 public boolean isAnagram(String s, String t) { //different length,just return false if (s.length() != t.length()) { return false; } //26 letters int[] ch = new int[26]; //traversal s and t for (int i = 0; i < s.length(); i++) { ch[s.charAt(i) - 'a']++; ch[t.charAt(i) - 'a']--; } //traversal the arrays for (int i = 0; i < 26; i++) { if (ch[i] != 0) { return false; } } return true; }But this question also ask us what to do if the input string contains unicode characters.So this time we have to use HashMap.Because HashMap can mark each characters in the string.Solution2 public boolean isAnagram(String s, String t) { //different length,just return false if (s.length() != t.length()) { return false; } //character is the charAt,integer is the number of the character HashMap<Character, Integer> hashMap = new HashMap<>(); for (int i = 0; i < s.length(); i++) { char ch = s.charAt(i); //if is the first time find the character,so use the defaultValue 0 and plus 1 hashMap.put(ch, hashMap.getOrDefault(ch, 0) + 1); } for (int i = 0; i < t.length(); i++) { char ch = t.charAt(i); //and minus 1 hashMap.put(ch, hashMap.getOrDefault(ch, 0) - 1); //it means they are different string,just return false if (hashMap.get(ch) < 0) { return false; } } return true; }257. Binary Tree PathsThis question is very similar to question 144. Binary Tree Preorder Traversal. It is also traversal this tree.You only need to store the found Tree Nodes.And also determine whether it is the last leaf node.So we can use two java class.ArrayList to store all paths,LinkedList to store the current node.Solution /** * store all paths */ ArrayList<String> result = new ArrayList<String>(); /** * store the current node */ LinkedList<String> path = new LinkedList<>(); public List<String> binaryTreePaths(TreeNode root) { traverse(root); return result; } /** * just like Binary Tree Preorder Traversal */ private void traverse(TreeNode node) { //if node is null,just return if (node == null) { return; } //String.valueOf make this value become String,and add into the path path.add(String.valueOf(node.val)); //Return leaf node if (node.left == null && node.right == null) { //add into the result,"->path" result.add(String.join("->", path)); } if (node.left != null) { traverse(node.left); } if (node.right != null) { traverse(node.right); } //Delete and return the last element path.removeLast(); }258. Add DigitsThis problem has two solutions.The first one solution is a easy math thinking.We can update the num when we finish the calculation.Solution1 public int addDigits(int num) { int result = 0; while (num > 0) { //get every digit result += num % 10; num /= 10; //if num is 38,so result is 11,we need to update the num and the result if (num == 0 && result > 9) { num = result; result = 0; } } return result; }The second solution is a very clever solution,because this question requires us to think about the time cost $O(N)$.We all know that in mathematical addition,9 plus 1 carry to 10.So i make a example.$18=10+8$.If num=18,the result=9$18=9+1+8=9+9$$38=10+10+10+8$ ifnum=38,theresult=2$38=9+1+9+1+9+1+8=9+9+9+9+2$So we found the patternIf this number is divided by 9 there is no remainder,the result is 9If this number is divided by 9 there is a remainder,the result is remainderSolution2 public int addDigits(int num) { if (num == 0) { return 0; } if (num % 9 == 0) { return 9; } else { return num %= 9; } }263. Ugly NumberThis problem is a very easy math problem.As we all know if n>0 and n is the ugly number,$n=2^a\times3^b\times5^c$,if a b d are all 0,so the n is 1.And because multiplication satisfies the commutative law.So no matter which number we divide first.If its remainder is not 0,so it's not ugly number.Solution public boolean isUgly(int n) { //n<=0 are all false if (n <= 0) { return false; } //n will become 1 at last while (n > 1) { if (n % 2 == 0) { n /= 2; continue; } if (n % 3 == 0) { n /= 3; continue; } if (n % 5 == 0) { n /= 5; continue; } //it's not ugly number if (n % 2 != 0 && n % 3 != 0 && n % 5 != 0) { return false; } } return true; }268. Missing NumberThis problem is a easy math problem.We can find a constrains in the problem,all the number of the nums are unique.So we can use Gauss Summation to solve this problem.We have the length of the nums,and we can calculate the synthesis of all the elements.And minus each elements,the result is the answer.Solution public int missingNumber(int[] nums) { //calculate the synthesis of all the elements int n = (1 + nums.length) * nums.length / 2; //minus all the elements for (int num : nums) { n -= num; } return n; }278. First Bad VersionThis test point for this question if Binary Search.If you want to understand the Binary Search method carefully,you can read my Blog LeetCode EasyTopic Notes2.We just need to determine whether the elements is bad version.And use Binary Search.Solution public int firstBadVersion(int n) { int head = 1; while (head < n) { int mid = (n - head) / 2 + head; if (!isBadVersion(mid)) { head = mid + 1; } else { n = mid; } } return head; }283. Move ZeroesThis problem has two easy solution.This problem require us must do this in-place without making a copy of the array.Solution1We can traversal the array twice.Begin from the head,while the element isn't 0,put it to the head.So the non-zero elements are all sorted at the head.And let all tail elements be 0 public void moveZeroes(int[] nums) { int n = 0; //let [0,n] are all non-zero elements for (int i = 0; i < nums.length; i++) { if (nums[i] != 0) { nums[n] = nums[i]; n++; } } //[n+1,nums.length] are all 0 for (int i = n; i < nums.length; i++) { nums[i] = 0; } }Solution2We can solve it like quick sort.0 as a demarcation point.When the element is not 0,exchange with the previous element. public void moveZeroes(int[] nums) { int n = 0; for (int i = 0; i < nums.length; i++) { //while the element is not 0,exchange with the previous element if (nums[i] != 0) { int temp = nums[i]; nums[i] = nums[n]; nums[n++] = temp; } } }290. Word PatternThis question is an upgraded version of the difficulty of question 205.If you want to know how to solve this question,you must know how to solve 205,you can read my notes about 205 LeetCode EasyTopic Notes6.This question we also use HashMap and HashSet.And the main idea is similar with 205.We still iterate over the string.And verify in turn whether it has appeared.If it has appeared but the data recorded on both sides are different just return false.Else update the record.Solution public boolean wordPattern(String pattern, String s) { //such as <a,dog> <c,cat> HashMap<Character, String> pMap = new HashMap<>(); //such as <dog> <cat> HashSet<String> sSet = new HashSet<>(); //Remove the spaces in the string,and change it to array,such as array[0] is dog,array[1] is cat String res[] = s.split(" "); //if the length is not equal,just return false if (res.length != pattern.length()) { return false; } //traversal the string for (int i = 0; i < pattern.length(); i++) { //if a letter has appeared if (pMap.containsKey(pattern.charAt(i))) { //compare whether the current array element are the same as the previous ones if (!res[i].equals(pMap.get(pattern.charAt(i)))) { return false; } } else { //if the letter is the first time appear,just add the array element if (!sSet.add(res[i])) { //if the element has been added,so just return false return false; } //HashMap put the new <s,ship> pMap.put(pattern.charAt(i), res[i]); } } return true; }292. Nim GameThis is a very interesting question.When i first time read this question,i thought it is a recursion solution.I did a reasoning.Person A :can take as much as he wantnumber1number2number3PersonB :can take as much as he wantnumber1number2number3When A has taken it.So this question can change to B take n-1 or n-2 or n-3And the n become n<=3,the next person to take it will win.So i write this code first. if (n <= 3) { return true; }And if the number is 5.PersonA can choose how many what he take.He can only take 1,and the n become 4.So no matter how many what personB take,personA will always win.So if personB must win situation is no matter how many what personA take.It is always n>3,must return false.So the opposite situation is A always win,the number always n<3.So you can come up with all the recursion code.Solution1 public boolean canWinNim(int n) { //n<=3,it will win,so return true if (n <= 3) { return true; } else { //if n==4,no matter hwo many A take.B will always win.So get the opposite situation !(B win) return !(canWinNim(n - 1) && canWinNim(n - 2) && canWinNim(n - 3)); } }But the recursion will over time,because the number of n is 1<=n<=2^31-1.So i change this code.We can find a patternn=1 A take 1,A winn=2 A take 2,A winn=3 A take 3,A winn=4A take 1,B take 3,B winA take 2,B take 2,B winA take 3,B take 1,B winn=5A take 1,n=4,A always winSo this question is a game problem.Code it is very easy and interstingSolution2 public boolean canWinNim(int n) { return n % 4 != 0; }
225. Implement Stack using QueuesThis problem requires us to create a last in first out(LIFO) stack.Pay attention to the requirements of this question:You must use only standard operations of a queue.What are the characteristics of the queue?The characteristics of the queue is first in first out.If you want to know more about stack and queue,you can read my Blog stack queue.We can use two queue.Queue2 to stores each incoming element.Then store the elements before queue1 into queue2.Then swap queue1 and queu2.The last element that came in becomes the second element.Every time an element of queue1 is pushed,it is the lasted element. Solution class MyStack { Queue<Integer> que1; Queue<Integer> que2; /** * Initialize your data structure here. */ public MyStack() { this.que1 = new LinkedList<Integer>(); this.que2 = new LinkedList<Integer>(); } /** * Push element x onto stack. */ public void push(int x) { //element push into queue2 que2.offer(x); //push the old element in queue1 while (!que1.isEmpty()) { que2.offer(que1.poll()); } //swap the queue1 and queue2 Queue<Integer> temp = que1; que1 = que2; que2 = temp; } /** * Removes the element on top of the stack and returns that element. */ public int pop() { return que1.poll(); } /** * Get the top element. */ public int top() { return que1.peek(); } /** * Returns whether the stack is empty. */ public boolean empty() { return que1.isEmpty(); } }226. Invert Binary TreeThis problem is a very easy problem.Because you don't need to mind the left subtree and the right subtree whether is null.Because you just need to invert the two subtree.Solution public TreeNode invertTree(TreeNode root) { invert(root); return root; } private void invert(TreeNode node) { //if the node is null,just return if (node == null) { return; } //don't mind the two subtree invert(node.left); invert(node.right); //invert the two subtree,make a temp TreeNode temp; temp = node.left; node.left = node.right; node.right = temp; }228. Summary RangesThis idea of solving this problem is to traverse the array.And use two pointers to delimit the range.beginning from the array's headif the next position number is one bigger than him,just let the fast pointer get the locationotherwise update the slow pointerSolution public List<String> summaryRanges(int[] nums) { ArrayList<String> strings = new ArrayList<>(); int i = 0; while (i < nums.length) { //compare i with each j int j = i + 1; while (j < nums.length && nums[j] - nums[j - 1] == 1) { j++; } //start from i StringBuffer buffer = new StringBuffer(Integer.toString(nums[i])); //if just a single number,just need like this "7",else end to j-1 if (i < j - 1) { buffer.append("->"); buffer.append(Integer.toString(nums[j - 1])); } //update i location i = j; strings.add(buffer.toString()); } return strings; }231. Power of TwoThis is a very easy math problem.Just need us to judge whether the result has a remainder.Solution public boolean isPowerOfTwo(int n) { //all impossible,just return false if (n < 1) { return false; } //special cases if (n == 1) { return true; } //ordinary number while (n > 1) { if (n % 2 != 0) { return false; } n /= 2; } return true; }232. Implement Queue using StacksThere is a very similar question 225. Implement Stack using Queues.I had wrote a note in my Blog LeetCode EasyTopic Notes7.If you want to understand this problem,i think you should understand that problem first.This problem wo also must know the characteristics of Stack and Queue.The characteristics of the Stack is FILO.So when i push a new element into Stack.I must clear all elements in the Stack.And push them all back to the Stack. So i can use another Stack to storage the elements,so the idea of this question is solved.Solution class MyQueue { Stack<Integer> sta1; Stack<Integer> sta2; /** * Initialize your data structure here. */ public MyQueue() { this.sta1 = new Stack<Integer>(); this.sta2 = new Stack<Integer>(); } /** * Push element x to the back of queue. */ public void push(int x) { //clear the stack1,push all the elements into stack2 while (!sta1.empty()) { sta2.push(sta1.pop()); } //Push to the bottom of the stack sta1.push(x); //push all the elements back to the stack1 while (!sta2.empty()) { sta1.push(sta2.pop()); } } /** * Removes the element from in front of queue and returns that element. */ public int pop() { return sta1.pop(); } /** * Get the front element. */ public int peek() { return sta1.peek(); } /** * Returns whether the queue is empty. */ public boolean empty() { return sta1.empty(); } }234. Palindrome Linked ListThis problem is a very interesting problem.Its own solution is not difficult,but some of its requirements are difficult.Let's go from simple to complex.Solution1 Use ArrayThis is a very easy solution,you just need to iterate the array.And then begin from the head of the array and the tail of the array.Compare each elements. public boolean isPalindrome(ListNode head) { ArrayList<Integer> list = new ArrayList<>(); //iterate the array to find the tail of the array ListNode tail = head; while (tail != null) { list.add(tail.val); tail = tail.next; } int i = 0, j = list.size() - 1; //compare each elements while (i < j) { if (!list.get(i).equals(list.get(j))) { return false; } i++; j--; } return true; }Solution2 RecursionThis is the first idea what i thought of before.We can use recursion to find the tail,and just compare node with its relative to it. private ListNode tail; public boolean isPalindrome(ListNode head) { tail = head; return recursion(head); } private boolean recursion(ListNode node) { if (node != null) { if (!recursion(node.next)) { return false; } //compare the elements node and relative to it if (node.val != tail.val) { return false; } //just find the taile tail = tail.next; } return true; }Solution3 Double Pointer and ReverseThe 2 solutions just now time spending $N$,space spending $N$.But this question requires us space spending only $1$.So we can change this List.Use double pointer to find the middle elementsReverse the elements which are after the middle elementCompare the first half of the elements with the second half of the elementsIf you want know how to reverse the List,you can read my Blog LeetCode EasyTopic Notes6 public boolean isPalindrome(ListNode head) { if (head == null) { return true; } //get the middle element ListNode half = findHalf(head); //reverse the elements which are after the middle ListNode reverse = reverseList(half.next); //compare with each element ListNode left = head; ListNode right = reverse; while (right != null) { if (left.val != right.val) { return false; } left = left.next; right = right.next; } return true; } /** * find the middle element */ private ListNode findHalf(ListNode head) { ListNode fast = head; ListNode slow = head; /** *this is very important thing you must be notice *if you write(fast.next.next!=null&&fast.next!=null) it will java.lang.NullPointerException *because if fast is the last element.fast.next is null,so null.next will java.lang.NullPointerException * but you write fast.next != null at first.It will select the error first and exit directly * */ while (fast.next != null && fast.next.next != null) { fast = fast.next.next; slow = slow.next; } return slow; } /** * reverse the ListNode */ private ListNode reverseList(ListNode node) { //slow pointer begin from the null ListNode cur = null; //fast pointer begin from the head ListNode pre = node; //until to the end while (pre != null) { //marked the fast next position ListNode temp = pre.next; //make the fast point to the slow pre.next = cur; //update the slo position cur = pre; //update the fast position pre = temp; } //return the new head return cur; }235. Lowest Common Ancestor of a Binary Search TreeThis is a very interesting problem.As we all know the structure of a binary tree.The smaller number is used as the left subtree,the larger number is the left subtree.So we can think about how mant situations.root.val>p.val&&root.val>q.val,so we can just search the root.left subtreeroot.val<p.val&&root.val<q.val,so we can just search the root.right subtreeroot.val>p.val&&root.val<q.val,so we can just search the rootor root.val==p.val || root.val==q.val,just return the rootSolution public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { // search the right subtree if (root.val < p.val && root.val < q.val) { return lowestCommonAncestor(root.right, p, q); } else if (root.val > p.val && root.val > q.val) { //search the left subtree return lowestCommonAncestor(root.left, p, q); } { return root; } }237. Delete Node in a Linked ListThis is a very easy problem.We can draw a picture to understand it.Solution public void deleteNode(ListNode node) { //copy the next node value node.val = node.next.val; //delete the next node node.next = node.next.next; }
191. Number of 1 BitsThis problem is very similar to problem190.The main idea is still bit operation and XORuse XOR to get the tail numberuse bit operation to remove the mantissasolution public int hammingWeight(int n) { //count the number of 1 int count = 0; int i = 0; //it must less than 32 while (i < 32) { //use XOR to get the tail number if ((n & 1) == 1) { count++; } //remove the mantissa n = n >> 1; i++; } return count; }202. Happy NumberThis problem is a very interesting problem.I have two problems at first.Will it become infinity?Will it fall into an infinite loop?So i make a table to prove my idea.As we all know,want it to be the biggest number.9*9is the biggest.So i make every digit a 9.DigitsLargestresult19812991623999243499993241399999999999991053So we can find a very interesting things.When the number has 13 digits,it will eventually become smaller than 243,so it wouldn't become infinity.Let's think of limit.if the number is smaller than 243.It becomes every number,there are only 243 cases.So when it gets into a loop,it will repeat.Then how can we prove whether it has been repeated.We have two ideas.use Hashuse double pointersSo it is easy to solve this problem.Hash public boolean isHappy(int n) { //make a HashSet HashSet<Integer> hashSet = new HashSet<>(); //if n not 1 and n not repeat,just continue count while (n != 1 && !hashSet.contains(n)) { hashSet.add(n); n = count(n); } //judge whether n is 1 return n == 1; } /** * to count the next number */ private int count(int n) { int result = 0; while (n > 0) { int i = n % 10; result += i * i; n /= 10; } return result; }Double Pointers public boolean isHappy(int n) { //fast speed is two times slow int slow = n; int fast = count(n); //when they meet again while (fast != 1 && slow != fast) { slow = count(slow); fast = count(count(fast)); } //judge whether fast is 1 return fast == 1; } /** * to count the next number */ private int count(int n) { int result = 0; while (n > 0) { int i = n % 10; result += i * i; n /= 10; } return result; }203. Remove Linked List ElementsThis problem is a very basic LinkedList Problem.If you want to understand the basic principles,you can read my Blog Data Structure Chapter5.But this problem has something different.Just like head = [7,7,7,7], val = 7.How to delete 7.So i have two solutions.Basic method traversal Linked ListRecursive resolutionWhen the beginning number is the number what we want to delete.We can change the head position.Untill the head is we don't want to delete.Then traversal the Linked List just we know.Traversal public ListNode removeElements(ListNode head, int val) { //situation head = [7,7,7,7], val = 7 while (head != null && head.val == val) { head = head.next; } //situation head = [], val = 1 if (head == null) { return head; } //situation head = [1,2,6,3,4,5,6], val = 6 ListNode oldNode = head; while (oldNode.next != null) { //oldNode is 2,oldNode next is 6 if (oldNode.next.val == val) { //so 2 point to 3,delete 6 oldNode.next = oldNode.next.next; } else { //oldNode is 1,oldNode next is 2,update oldNode oldNode = oldNode.next; } } return head; }We can think of this Linked List as a connection of many Linked List.So we can use recursion. This problem change to removeElements(ListNode head.next, int val).So we classify and discuss.if head==null,just return nullif head.val==val,just return head.nextif head.val!=null,just return headif head.next!=null,just recursion head.next,valRecursion public ListNode removeElements(ListNode head, int val) { //just return null if (head == null) { return null; } //Recursion head.next if (head.next != null) { head.next = removeElements(head.next, val); } //if head.val is val,just delete this head if (head.val == val) { return head.next; } else { return head; } }205. Isomorphic StringsThe first reaction to this kind of problem is the Hash Table.But i don't want to always use it,so i analyze this question.If want to solve this problem,we need to find each letter location. So i want to use a calculator to caltulate.iletter is different form i+1 letter just plus1,otherwise minus 1.So i write a code,but it was a wrong solution.Initial wrong idea public boolean isIsomorphic(String s, String t) { int S = 0, T = 0; int j = 0; for (int i = 1; i < s.length(); i++) { if (s.charAt(i) != (s.charAt(j))) { S++; } else { S--; } if (t.charAt(i) != t.charAt(j)) { T++; } else { T--; } j++; if (S != T) { return false; } } return true; }Because it is only count the each different letter location.It can't judge like this "badc" "baba".It is different from the last letter,but it isn't the isomorphic.So i must determine where each letter appears.So i use ASCII table,because each letter have it's location.solution public boolean isIsomorphic(String s, String t) { int[] sLocation = new int[128]; int[] tLocation = new int[128]; for (int i = 0; i < s.length(); i++) { //get it's ASCII location char sCh = s.charAt(i); char tCh = t.charAt(i); //if it has the letter,just judge it is isomorphic if (sLocation[sCh] != tLocation[tCh]) { return false; } //if it is the first time appear,so remember it if (sLocation[sCh] == 0) { //why +1,because if i is 0,so it will stuck in an endless loop sLocation[sCh] = i + 1; tLocation[tCh] = i + 1; } } return true; }206. Reverse Linked ListI have recorded this problem in detail in my notes Data Structure Chapter6.But that solution is recursion,this problem requires us to use iteratively.So let's think about how to write the code.If we want to use iteratively solution,we need two pointers.One begin from the null,one begin from the head.Move foreward one position at the same time.The faster always point to the slower,so this linked list has been reversed. public ListNode reverseList(ListNode head) { //slow pointer begin from the null ListNode cur = null; //fast pointer begin from the head ListNode pre = head; //until to the end while (pre != null) { //marked the fast next position ListNode temp = pre.next; //make the fast point to the slow pre.next = cur; //update the slo position cur = pre; //update the fast position pre = temp; } //return the new head return cur; }RecursionThis solution i had wrote in my notes,if you want to read it,you can follow my Blog Data Structure Chapter6.The most difficult to understand code maybe is head.next.next = head.Suppose the linked list is:n1->...->nk-1->nk->nk+1->...->nmWe hope nk+1 next pointer is nkSo nk.next.next=nk public ListNode reverseList(ListNode head) { if (head == null || head.next == null) { return head; } ListNode cur = reverseList(head.next); head.next.next = head; //we must make the next is null,if we don't do this,it may produce loops head.next = null; return cur; }217. Contains DuplicateThis problem is a very easy problem.We have two solutions to solve it.SortWe can sort this nums.And begin from the head,compare two adjacent numbers,if they are the same just return true. public boolean containsDuplicate(int[] nums) { Arrays.sort(nums); for (int i = 0; i < nums.length - 1; i++) { if (nums[i] == nums[i + 1]) { return true; } } return false; }HashWe can also use Hash,it is a very common method. public boolean containsDuplicate(int[] nums) { HashSet<Integer> hashSet = new HashSet<>(); for (int num : nums) { //if the num has been existed,it will return false if (!hashSet.add(num)) { return true; } } return false; }219. Contains Duplicate IIThis problem is a very typical HashMap problem.It's test point is the mastery of key-value pairs.Solution public boolean containsNearbyDuplicate(int[] nums, int k) { //nums[i] is key,i is value HashMap<Integer, Integer> hashMap = new HashMap<>(); for (int i = 0; i < nums.length; i++) { //if find the same nums[i] if (hashMap.containsKey(nums[i])) { //check the value i is standards compliant if (i - hashMap.get(nums[i]) <= k) { return true; } } //it must put at last,it put at first,it is a fault code,because when i is 0,it will always // return true hashMap.put(nums[i], i); } return false; }
155. Min StackThis problem is not a how to create Stack problem.Is a how to find the min number in Stack problem.As we all know the characteristics of the Stack is FILO.When we pop up the number,how can we find the min number.So we can think use another Stack to storage the min number.as one number is pushing into the Stack,we compare this number with the min number.If is smaller than the old min number,so we just push it into the auxiliary Stackas one number is pop up the Stack,we also pop the auxiliary Stack,because the top of the auxiliary Stack is the min numberin anytime,the top of the auxiliary Stack is the min numbersolutionclass MinStack { /** * initialize your data structure here. */ int min = Integer.MAX_VALUE; LinkedList<Integer> list; public MinStack() { //make the min number is the largest min = Integer.MAX_VALUE; list = new LinkedList<>(); } public void push(int val) { list.add(val); //compare with every number list.addFirst(val <= min ? val : min); min = list.peek(); } public void pop() { list.poll(); list.pollLast(); //switch to the next min number min = list.isEmpty() ? Integer.MAX_VALUE : list.peek(); } public int top() { return list.peekLast(); } public int getMin() { return min; } }160. Intersection of Two Linked ListsThis is a very easy math problem.We can use Hash Map to solve this problem,but it cost to much space.So i use math to solve.A length is mB length is nwhen they meet,A move m+n-b,B mover n+m-b,so they move the same distanceif two lines do not intersectm=n,they will reach in the end at the same time,and all become null,so it just return nullm!=n,they will traversing the two lines,each one distance ism+n and n+m,and also reach in the end at the same timeif two lines are intersecta=b,they will reach the node where the two linked lists intersect at the same timea!=b,they will also reach at the same time,just like the picture what i drawsolution public ListNode getIntersectionNode(ListNode headA, ListNode headB) { //if one of headA or headB is null,just return null if (headA == null || headB == null) { return null; } ListNode A = headA; ListNode B = headB; //until they reach together,if A==B,it means they reach the end,just return while (A != B) { //if A is null,just change to the headB,if not null,just go on if (A == null) { A = headB; } else { // A = A.next; } if (B == null) { B = headA; } else { B = B.next; } } //return B is also fine return A; }167. Two Sum II - Input array is sortedThis question is the same as Problem1.Can be easily solved with a Hash Map.But there is one thing you should be notice.[1,2]!=[2,1],so you should change the order in resultsolution public int[] twoSum(int[] numbers, int target) { //make a result array int[] result = new int[2]; HashMap<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < numbers.length; i++) { if (map.containsKey(target - numbers[i]) && i != map.get(target - numbers[i])) { //change the order in result result[0] = map.get(target - numbers[i]) + 1; result[1] = i + 1; break; } //put the number in HashMap map.put(numbers[i], i); } //just return return result; }168. Excel Sheet Column TitleThe test point for this question is knowledge of mathematics and ASCII table.As we know,in the division operation of Java,$6\div3=2$,$7 \div3=2$.And in ASCII table.We can use it like this'A'=0+'A' 'B'=1+'A' 'C'=2+'A'So let's see this question1-1=0 0%26=0 0+'A'='A'2-1=1 1%26=1 1+'A'='B'26-1=25 25%26=25 25+'A'='Z'And what if the number is greater than 2628-1=27 27%26=1 1+'A'='B' 27/26=1 1-1=0 0%26=0 0+'A'='A'This question is need to return String,so we can use StringBuffer.It is very easy thinking.Solution public String convertToTitle(int columnNumber) { StringBuffer sb = new StringBuffer(); //make a remainder int remainder = 0; while (columnNumber > 0) { columnNumber--; remainder = columnNumber % 26; //get a single letter sb.append((char) (remainder + 'A')); //get the next letter columnNumber /= 26; } //the result is opposite.so we need to use reverse return sb.reverse().toString(); }169. Majority ElementThis problem is a very interesting problem.We usually think HashMap to solve it,but i don't want to use it like everyone.SortAs we all know this problem is need to find the majority element.So i can give a example.A B A B A A is a nums,but when we sort this nums,it becomes A A A A B BWe can find a pattern,no matter how many elements what it has,the majority element number is always larger than the half length of the nums.So we just get by sorting. public int majorityElement(int[] nums) { Arrays.sort(nums); return nums[nums.length / 2]; }Boyer-Moore voting algorithmWe can see this nums have two kinds of numbers.the majority element number Athe minority element numberBNumber of A is always larger than Number of B,all other numbers are all B,i can make a result to count the numberfor exampleA 1 2 A A A result=01 2 A A A result+1=12 A A A result-1=0A A A result-1=-1A A result+1=0A result+1=1result+1=2Because the A number is always larger than B number,so when the result is equals to 0,just update the result public int majorityElement(int[] nums) { //count the most number int result = 0; //get the new number int ticket = 0; for (int num : nums) { //if A number is equals to B number,the result is 0 if (result == 0) { ticket = num; } //judge which is the most number result += (num == ticket) ? +1 : -1; } return ticket; }171. Excel Sheet Column NumberThis problem requires us to observe carefully.ZY$701=26\times26^(2-1)+25\times26^(1-1)$AB$28=1\times26^(2-1)+2\times26^(1-1)$A$1=1\times26^(1-1)$If we express it in math,it is very easysolution1 public int titleToNumber(String columnTitle) { //j is the power int result = 0, j = columnTitle.length(); for (int i = 0; i < columnTitle.length(); i++) { //'A' - 'A' =0,so plus 1,n=1 int n = (int) (columnTitle.charAt(i) - 'A') + 1; //go down one place j--; //use Math to count the result of each int m = (int) Math.pow(26, j); result += m * n; } return result; }But this solution will open up new Math space every time,so we can change a littlesolution2 public int titleToNumber(String columnTitle) { int result = 0, num = 0; for (int i = 0; i < columnTitle.length(); i++) { num = columnTitle.charAt(i) - 'A' + 1; //the first letter times 26 length()-1 and plus the next letter result = result * 26 + num; } return result; }172. Factorial Trailing ZeroesWhen i first time saw this question,i know the most easy and the most stupid method is calculate the result of factorial.But in the real interview this is impossible.My second feeling is to discover a mathematical law.So i wrote all the factorials from 0 to 10 for observation.$0! = 0$$1! = 1$$2! = 2$$3! = 6$$4! = 24$$5! = 120$$6! = 720$$7! = 5040$$8! = 40320$$9! = 362,880$$10! = 3,628,800$$11! = 39,916,800$We can find a very interesting pattern.When there are multiples of 5 and 5,the mantissa will only add 0.It is equivalent to how many 5 powers there are in this number n.So this problem it become very easy to solve it.solution public int trailingZeroes(int n) { int count = 0; while (n > 0) { //just divide by 5 n /= 5; //count is the quotient count += n; } return count; }190. Reverse BitsWhen i first encountered this question,i made a mistake.I thought that when performing bit operations.n=0110 reverse=1n and reverse are decimal number.This is a big mistake.In this question all the number are all the Binary number.So in Binary calculationn+reverse=0111,so this problem it is very easy to slove.This question just like Greedy snake.Go out from the left come in from the right.When it end,this bits has been reverse.So we will use &,as we know only 1&1can be 1,so we can get the head,and then get each digit number.And plus them together is the result.solution public int reverseBits(int n) { //1=00000000000000000000000000000001,so n&1 can get the tail of n int reverse = n & 1; int i = 1; //only need 31 times while (i < 32) { //shift one bit to the right,equivalent to removing the tail n = n >> 1; //get a new tail reverse = reverse << 1; //plus the old tail reverse += n & 1; i++; } return reverse; }
111. Minimum Depth of Binary TreeAs we all know how to find the Max depth of the tree.Here we can review the thoughts at the time,If the root is null,so the max depth is 0count the left subtree depthcount the right subtree depthmax depth of the current tree = the greater of the max depth of the left subtree and the max depth of the right subtreeIf we find the min depth,what to keep and what to modify?If the root is null,so the max depth is 0If the left and right subtree are all null,so the depth is 1count the left subtree depthcount the right subtree depthbut we can't get the max depth,we get the smaller of themwe can preset the number of layers to the maximumthe min subtree's depth plus this layer depth 1solution public int minDepth(TreeNode root) { return findMin(root); } private int findMin(TreeNode node) { //let the number of this layer be the largest int depth = Integer.MAX_VALUE; //if this layer is null,so it doesn't have subtree if (node == null) { return 0; } //if just have the node tree,so the number of the layer is 1 if (node.left == null && node.right == null) { return 1; } //get the min number of the subtree if (node.left != null) { depth = Math.min(findMin(node.left), depth); } if (node.right != null) { depth = Math.min(findMin(node.right), depth); } //plus this node tree layer number 1 return depth + 1; }112. Path SumThis problem is a very typical recursion problem.I think it is very similar to the Tower of Hanoi problem.Let's take a closer look at this photoif 11 don't have a left subtree and right subtree,it is a leafthe target number is 22,but we minus the right subtree is 22this question change can we start 7 to the root-to-leaf,plus the all number can be 22?after constant recursionthis question change 4 left subtree can plus 5 22?or 8 right subtree plus 5 get 22So this question we can get the recursion thoughtif the node is null,return falseif the left subtree and the right subtree are all null,so judge this node value whether equals to the target sumjudge the left subtree number and right subtree number whether equals to the target sum minus the node valuesolution public boolean hasPathSum(TreeNode root, int targetSum) { //if don't have this node,just return false if (root == null) { return false; } //judge this node value whether equals to the target number if (root.left == null && root.right == null) { return targetSum == root.val; } //recursion this function,find target number minus this node value return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val); }118. Pascal's TriangleThis question is a very easy question.Like a two-dimensional array,but this is a List question.head and tail number must be 1$j<=i$[i][j]=[i-1][j-1]+[i-1][j]So we can solve this problem easilysolution public List<List<Integer>> generate(int numRows) { ArrayList<List<Integer>> lists = new ArrayList<>(); for (int i = 0; i < numRows; i++) { ArrayList<Integer> arrayList = new ArrayList<Integer>(); for (int j = 0; j <= i; j++) { //the head and tail must be 1 if (j == 0 || j == i) { arrayList.add(1); } else { //[i-1][j-1]+[i-1][J] arrayList.add(lists.get(i - 1).get(j - 1) + lists.get(i - 1).get(j)); } } //add this new lists lists.add(arrayList); } return lists; }119. Pascal's Triangle IIThis problem is very similar to number118.If you understand number118,then you can solve this problem easily.solution public List<Integer> getRow(int rowIndex) { ArrayList<List<Integer>> lists = new ArrayList<>(); //this question example rowIndex = 3,[1,3,3,1].So the answer is the line 4,we should plus for (int i = 0; i < rowIndex + 1; i++) { ArrayList<Integer> arrayList = new ArrayList<>(); for (int j = 0; j <= i; j++) { if (j == 0 || j == i) { arrayList.add(1); } else { arrayList.add(lists.get(i - 1).get(j - 1) + lists.get(i - 1).get(j)); } } lists.add(arrayList); } //get the answer return lists.get(rowIndex); }121. Best Time to Buy and Sell StockThis problem is also a Dynamic programming problem.The time complexity of this kind of problem is generally $O(n)$. This problem has two solutions,one solution is Brute force calculation.But this solution can be out of time.solution1 public int maxProfit(int[] prices) { int result = 0; //beginning for the head for (int i = 0; i < prices.length - 1; i++) { for (int j = i + 1; j < prices.length; j++) { //compare i ,i+1,until the end if (prices[i] < prices[j]) { if (result < prices[j] - prices[i]) { //update the result result = prices[j] - prices[i]; } } } } return result; }The second solution is a very easy thinking.This problem is to find the max price.So we must find the min price to buy.And find the max price which after the min price.solution2 public int maxProfit(int[] prices) { int maxPrice = Integer.MAX_VALUE; int result = 0; for (int i = 0; i < prices.length; i++) { //find the min price if (prices[i] < maxPrice) { maxPrice = prices[i]; } else if (result < prices[i] - maxPrice) { //find the max price which after the min price result = prices[i] - maxPrice; } } return result; }125. Valid PalindromeThis problem is a not difficult but very complicated to solve.We can use double pointers to solve it.if head is not lowercase and uppercase letter and is not a number,just plusif tail is not lowercase and uppercase letter and is not a number,just minususe the ASCII to judge the head,if the lowercase or the number,we don't need tochange,if the uppercase,just change to the lowercaseuse the ASCII to judge the tail,if the lowercase or the number,we don't need tochange,if the uppercase,just change to the lowercasejudge the head and the tailthe end is head>=tailSo this problem has many judgement,it will make a lot of time to write,it is very complicatedsolution public boolean isPalindrome(String s) { //make double pointers int head = 0, tail = s.length() - 1; while (head <= tail) { //if head is not lowercase and uppercase letter and is not a number,just plus while (head <= tail && !(s.charAt(head) >= 'a' && s.charAt(head) <= 'z') && !( s.charAt(head) >= 'A' && s.charAt(head) <= 'Z') && !(s.charAt(head) >= '0' && s.charAt(head) <= '9')) { head++; } //if tail is not lowercase and uppercase letter and is not a number,just minus while (head <= tail && !(s.charAt(tail) >= 'a' && s.charAt(tail) <= 'z') && !( s.charAt(tail) >= 'A' && s.charAt(tail) <= 'Z') && !(s.charAt(tail) >= '0' && s.charAt(tail) <= '9')) { tail--; } //make two temps char headTemp, tailTemp; //if the s is null character.such as " ".it will out of time,so this is to judge the s if (head > tail) { return true; } //we can use the ASCII to judge the head,if the lowercase or the number,we don't need to // change if ((s.charAt(head) >= 'a' && s.charAt(head) <= 'z') || (s.charAt(head) >= '0' && s.charAt(head) <= '9')) { headTemp = s.charAt(head); } else { //if the uppercase,just change to the lowercase headTemp = (char) ((int) s.charAt(head) + 32); } //we can use the ASCII to judge the tail,if the lowercase or the number,we don't need to // change if ((s.charAt(tail) >= 'a' && s.charAt(tail) <= 'z') || (s.charAt(tail) >= '0' && s.charAt(tail) <= '9')) { tailTemp = s.charAt(tail); } else { //if the uppercase,just change to the lowercase tailTemp = (char) ((int) s.charAt(tail) + 32); } //just judge the head and the tail if (headTemp == tailTemp) { head++; tail--; continue; } else { return false; } } return true; }136. Single NumberJava Xor Operator is a very elegant method,it's not like a HashMap.It doesn't cost a lot of space.Any number and 0 are XOR,the result is still the original number,a^0=aXOR any number with itself,the result is 0,a^a=0The exclusive XOR operation satisfies the commutative law and associative law.a^b^a=b^a^a=b^(a^a)=b^0=bsolution public int singleNumber(int[] nums) { int number = 0; for (int num : nums) { number ^= num; } return number; }141. Linked List CycleThis is a typical problem of fast and slow pointers.I wrote a note about double pointers in my Blog Data Structure Chapter6 If you want to know about it,you can read it.solution public boolean hasCycle(ListNode head) { //make fast and slow double pointer ListNode fast = head, slow = head; //test example [] -1,just return false if (fast == null) { return false; } while (fast.next != null && fast.next.next != null) { fast = fast.next.next; slow = slow.next; //has cycle if (fast == slow) { return true; } } return false; }144. Binary Tree Preorder TraversalThis is a very simple Binary Tree problem.I wrote typical note in my blog Data Structure Chapter11 If you want to know more about Binary Tree,you can read it.solution public List<Integer> preorderTraversal(TreeNode root) { ArrayList<Integer> list = new ArrayList<>(); preErgodic(root, list); return list; } private void preErgodic(TreeNode node, ArrayList<Integer> keys) { //if the node is null,just return if (node == null) { return; } //add the ArrayList keys.add(node.val); //the left subtree if (node.left != null) { preErgodic(node.left, keys); } //the right subtree if (node.right != null) { preErgodic(node.right, keys); } }145. Binary Tree Postorder TraversalThis is a very simple Binary Tree problem.I wrote typical note in my blog Data Structure Chapter11 If you want to know more about Binary Tree,you can read it.solution public List<Integer> postorderTraversal(TreeNode root) { ArrayList<Integer> list = new ArrayList<>(); afterErgodic(root, list); return list; } private void afterErgodic(TreeNode node, ArrayList<Integer> keys) { if (node == null) { return; } if (node.left != null) { afterErgodic(node.left, keys); } if (node.right != null) { afterErgodic(node.right, keys); } keys.add(node.val); }
26. Remove Duplicates from Sorted ArrayThis problem is a two points problem.Because this problem require remover the duplicates in-place.So we can only have the existing array.We can make two points.Compare with these two points,if one is smaller than another one.So update the nums.solution public int removeDuplicates(int[] nums) { //Because it must have a result,the answer is the head of the nums,such as [1,1,1,1] int result = 1; //make a faster point,it always larger than head point int j = 1; for (int i = 0; i < nums.length - 1; i++) { //if meet a new number if (nums[i] < nums[j]) { //update the result,and let it +1 nums[result] = nums[j]; result++; } //whether you find it or not,must update i and j j++; } return result; }27. Remove ElementThis problem is the same as problem 26.We also can use two points to solve this problem.We can get information which is no requirement on the order.So wo can set two point.One point is from the nums head another one is from the nums tail.I listed the example process$3(head)->2->2->3(tail)$$3(head)->2->2(tail)->3$​$2(head)->2(tail)->2->3$$2->2(head,tail)-2->3$solution public int removeElement(int[] nums, int val) { //make two points int head = 0, tail = nums.length; while (head < tail) { //if find the val,exchange the head if (nums[head] == val) { nums[head] = nums[tail - 1]; tail--; } else { head++; } } return head; }We can also scratch from the start.$3(find)->2->2->3$$2->2(find)->2->3$solution public int removeElement(int[] nums, int val) { int find = 0; for (int num : nums) { if (num != val) { nums[find] = num; find++; } } return find; }28. Implement strStr()This question is a classic string single-mode matching model.This question we use Knuth-Morris-Pratt algorithm is the best.But KMP algorithm is a little complex,so i will explain the KMP algorithm in a separate chapter.We can match each letter from the beginning of the haystack. If one of the letter is equal to the needle.Just return the beginning location.solution public int strStr(String haystack, String needle) { //special case if (needle.length() == 0) { return 0; } int L1 = haystack.length(); int L2 = needle.length(); //if L1="aaa",L2="aaa",L1-L2 will be 0,so it is a special case if (L1 == L2) { if (haystack.equals(needle)) { return 0; } else { return -1; } } for (int i = 0; i <= L1 - L2; i++) { String str = haystack.substring(i, i + L2); if (str.equals(needle)) { return i; } } return -1; }35. Search Insert PositionThis problem is a simple binary-search problem.It looks simple,but it has some places we should be notice.writewhile(head<tail),when exiting the loop,we don't have to judge return head or return taildistinguish [head tail] has two situations[head mid] and [mid+1 tail],each corresponding to [tail=mid] and [head=mid+1][head mid-1] and [mid tail],each corresponding to [tail=mid-1] and [head=mid],this situation we need change int mid=head+(tail-head)/2 to int mid=head+(tail-head+1)/2.Otherwise there will be an infinite loop.You can print the value of head and tail to provesolution1 public int searchInsert(int[] nums, int target) { int head = 0, tail = nums.length; int mid; while (head < tail) { mid = (tail - head) / 2 + head; if (nums[mid] < target) { head = mid + 1; } else { tail = mid; } } return head; }solution2 public int searchInsert(int[] nums, int target) { int head = 0, tail = nums.length; int mid = 0; while (head < tail) { mid = head + (tail - head + 1) / 2; if (nums[mid - 1] < target) { head = mid; } else { tail = mid - 1; } } return head; }This problem has a very important place we should be attentionIn solution1,we write like this mid = (tail - head) / 2 + head; if (nums[mid] < target) { head = mid + 1; } else { tail = mid; }if we write like this,it looks equal to solution1,but it is fault mid = (tail - head) / 2 + head; if (nums[mid] > target) { tail = mid; } else { head = mid + 1; }We give a example.There are five numbers 1 2 3 4 5,mid=(5-0)/2=2,if the result is 3,so head=mid+1=3 is fault.This is a same attention in solution2,i think we don't need remember this.If you forget about,just make a example just this.53. Maximum SubarrayThis is a typical dynamic programming problem.We use a sum to save the last result.And if the answer is less than 0.So plus the next number is meaningless.Because negative number plus any number is less than that number.We only need traverse the array once to get the result.solution public int maxSubArray(int[] nums) { int sum = nums[0], result = 0; //traverse the array for (int num : nums) { if (result > 0) { //update the result result += num; } else { //if result<=0,get a new result result = num; } //save the maximum sum = Math.max(sum, result); //you can use this to Watch the whole process //System.out.println("sum :" + sum + " " + "result :" + result); } //get the max return sum; }58. Length of Last WordThis problem have two situations."world "like this.The following characters are all spaces."luffy is still joyboy",The following characters are all letters.We should search from behind.Get the letters' tail location and the head location.Subtract the two is the answer.solution1 public int lengthOfLastWord(String s) { //length is the tail,i is the head int i = s.length() - 1, length = 0; while (i >= 0) { //find the tail if (s.charAt(i) != ' ') { length = i; break; } else { i--; } } //find the head while (i >= 0) { if (s.charAt(i) == ' ') { break; } else { i--; } } //subtract the two return length - i; }solution2 public int lengthOfLastWord(String s) { int end = s.length() - 1; int start; //find the word tail while (end >= 0 && s.charAt(end) == ' ') { end--; } //if have no word if (end < 0) { return 0; } //begin from the tail start = end; //find the head while (start >= 0 && s.charAt(start) != ' ') { start--; } return end - start; }66. Plus OneThis problem is a easy math problem.I give some example.$4->4+1->5$$9->9+1->10$$14->14+1->15$$99->99+1->100$You can find if a letter is $9$,it will become $0$,and next digit plus one.And if all add one, the first letter will become $1$So we can solve this problem easily.solution public int[] plusOne(int[] digits) { for (int i = digits.length - 1; i >= 0; i--) { //this letter plus 1 digits[i]++; //judge this letter whether 9 or other number"0-8" digits[i] = digits[i] % 10; //if this letter is 9,so the next digit plus one,or not just return the new digits if (digits[i] != 0) { return digits; } } //if all letters are 9,the first letter must 1,"999" "1000" digits = new int[digits.length + 1]; digits[0] = 1; return digits; }67. Add BinaryThis problem is very same as Problem 66.We have two solutions.Use math to count.I give you some examplea = "11"="3" b="1" a+b="100"=4a="1010"="10" b="1011"="11" a+b="10101"="21"We can use binary conversion to decimal to count the result.And convert the decimal result to binaryBut this is not a good solutions.Because it will face the problem of crossing the boundary.So we can think this problem we can use the same method as Problem 66."0+0=0""0+1=1""1+1=10"We can use StringBuilder to build a new string.And compare every digit.If this digit dose not exist,it is treated as 0solution public String addBinary(String a, String b) { StringBuilder sb = new StringBuilder(); //get a and b length int i = a.length() - 1; int j = b.length() - 1; //judge whether add 1 to the next digit int result = 0; //from tail to head while (i >= 0 || j >= 0) { //get the two digit sum int sum = result; //if a is end if (i >= 0) { //'1'-'0'=1,'0'-'0'=0 sum += a.charAt(i) - '0'; } //if i is end if (j >= 0) { sum += b.charAt(j) - '0'; } //judge sum whether is 1 or 2 or 3 sb.append(sum % 2); //if sum is 0 or 1,just continue,if i is 3,should +1 result = sum / 2; i--; j--; } //if new add 1 if (result != 0) { sb.append(result); } //return the new string return sb.reverse().toString(); }69. Sqrt(x)This problem we can use Math method,but i think if we used essentially unchanged.So we can use Binary search one more timesolution public int mySqrt(int x) { int head = 0, tail = x, result = 0; while (head <= tail) { int mid = head + (tail - head) / 2; //such as 3*3=9,2*2<9 if ((long) mid * mid <= x) { //to record last mid result = mid; head = mid + 1; } else { tail = mid - 1; } } return result; }
1. Two SumThis problem we usually think to iterate over the array,this solution can solve this problem.We can use for twice,the solution time is $O(n^2)$solution1 public int[] twoSum(int[] nums, int target) { int[] result = new int[2]; for (int i = 0; i < nums.length; i++) { for (int i1 = i + 1; i1 < nums.length; i1++) { if (nums[i] + nums[i1] == target) { result[0] = i; result[1] = i1; break; } } } return result; }but this problem has a follow-up which is come up with an algorithm that is less than $O(n^2)$​​​​​time complexity.Let's think about,if we search the second result one more time,the time is power of the first time.So we must marked in the first time.We can use HashMap,it can help us to marked number when we searching,so this time is$O(n)$solution2 public int[] twoSum(int[] nums, int target) { int[] result = new int[2]; HashMap<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { //the second number must not not equal to the first number,and add up to target if (map.containsKey(target - nums[i]) && i != map.get(target - nums[i])) { result[0] = i; result[1] = map.get(target - nums[i]); break; } map.put(nums[i], i); } return result; }7. Reverse IntegerThis problem is a bit operation.I think these problem looks very simple,but they have a same question Overflow and out-of-bounds.As we all know the range of int is $-2147483648(-2^31)-->2147483647(2^31-1) $.But this problem is reverse number,For example there is a number $1147483649$,when it was reverse,it became $9463847411$,so it is overflow.Positive numberThe last digit must be less than $7$negative numberThe last digit must be greater than $-8$Modulo operationWe use modulo operation can count the resultsolution public int reverse(int x) { int result = 0; //modulo operation while (x != 0) { int temp = x % 10; //The last digit must be less than 7 if (result > Integer.MAX_VALUE / 10 || (result == Integer.MAX_VALUE / 10 && temp > 7)) { return 0; } //The last digit must be greater than -8 if (result < Integer.MIN_VALUE / 10 || (result == Integer.MIN_VALUE / 10 && temp < -8)) { return 0; } result = result * 10 + temp; x /= 10; } return result; }9. Palindrome NumberThis's problem is same as Problem 7,it just only changed one place.If the number is a negative number,it will return false.So we just judge it at first.solution if (x < 0) { return false; } int result = 0, x1 = x; while (x != 0) { int temp = x % 10; if (result > Integer.MAX_VALUE / 10 || (result == Integer.MAX_VALUE / 10 && temp > 7)) { return false; } result = result * 10 + temp; x /= 10; } if (result == x1) { return true; } else { return false; }13. Roman to IntegerWe must find a rule in the Roman number.We can see them one by one.There are made up of individual Roman number.For example:$3=III=I+I+I=1+1+1$$4=IV=V-I=5-1=4$$9=IX=X-I=10-1=9$$58=LVIII=L+V+I+I+I=50+5+1+1+1=58$We can find a rule:The previous number is less than the next number is equal to the less number minus the previous number$IV=5-1=4$The previous number is greater than or equal to the next number is equal to the less number plus the previous number$LVIII=50+5+1+1+1=58$Because there is no number after the last number.So the last number must be plused at last.solution public int romanToInt(String s) { int result = 0; //count the first number to compare with the next number int temp = getValue(s.charAt(0)); for (int i = 1; i < s.length(); i++) { int now = getValue(s.charAt(i)); if (temp < now) { result -= temp; } else { result += temp; } temp = now; } //plus the last number at last result += temp; return result; } /** * make a switch method to judge the Roman number */ private int getValue(char c) { switch (c) { case 'I': return 1; case 'V': return 5; case 'X': return 10; case 'L': return 50; case 'C': return 100; case 'D': return 500; case 'M': return 1000; default: return 0; } }14. Longest Common PrefixVertical scanWe can set the first str as the template str.Scan each char of the first str and compare with the after str one by one.While finish scan,it shows the whole first str is the common prefix public String longestCommonPrefix(String[] strs) { //Special case if (strs.length == 0) { return ""; } //the Common Prefix can't longer than the shortest string int StrsLength = strs.length; //to count the compare number int firstLength = strs[0].length(); for (int i = 0; i < firstLength; i++) { char compare = strs[0].charAt(i); for (int j = 1; j < StrsLength; j++) { //compare with each one of them if (i == strs[j].length() || compare != strs[j].charAt(i)) { return strs[0].substring(0, i); } } } return strs[0]; }Sort the strsWe can use the API Arrays to sort this strs.Before sort:"flower","fsdsda","fl"After sort:"fl","flower","fsdsda"We can just compare the first one with the last one.Most of this time is spent on sorting public String longestCommonPrefix(String[] strs) { //First strs:"flower","fsdsda","fl" Arrays.sort(strs); //Now strs:"fl","flower","fsdsda" char[] array1 = strs[0].toCharArray(); char[] array2 = strs[strs.length - 1].toCharArray(); int i = 0; while (i < array1.length && i < array2.length) { if (array1[i] != array2[i]) { break; } i++; } return strs[0].substring(0, i); }20. Valid ParenthesesLet's analyze this problem.If the parenthese is a left bracket,we push into the Stack else we pop the Stack.Because the feature of the stack is first-in-last-out.But this problem has some place to be attention.We can't use == operator to test the equality of strings,it will create bad Bugs in the programEmptystackexception it will be appear.If the stack is empty but we still pop the stack,it will meet this Bug.If you want to learn more the principle of the stack,you can read my data structure notes iamyqhp.comsolution public boolean isValid(String s) { if (s.length() % 2 == 1) { return false; } //create a stack to storage parentheses Stack<String> chars = new Stack<>(); for (int i = 0; i < s.length(); i++) { //convert char to string String currChar = String.valueOf(s.charAt(i)); /* judge the current character is a left parentheses.if is a left parentheses,push it onto the stack*/ //to be attention,never be used "==",In order to avoid bad bugs in the program. On the surface, this kind of bug looks like a random intermittent error if ("(".equals(currChar) || "{".equals(currChar) || "[".equals(currChar)) { chars.push(currChar); } else if (")".equals(currChar)) { //if Stcak is empty,return false if (chars.isEmpty()) { return false; } String StringPop = chars.pop(); if (StringPop == null || !("(".equals(StringPop))) { return false; } } else if ("}".equals(currChar)) { if (chars.isEmpty()) { return false; } String StringPop = chars.pop(); if (StringPop == null || !("{".equals(StringPop))) { return false; } } else if ("]".equals(currChar)) { if (chars.isEmpty()) { return false; } String StringPop = chars.pop(); if (StringPop == null || !("[".equals(StringPop))) { return false; } } } //if the chars still have,it means still have left bracket if (chars.isEmpty()) { return true; } else { return false; } }21. Merge Two Sorted ListsThis problem has two solutionsrecursionWe can compare two number,if A is larger than B.So we can compare A.next with B get a answer C,and let A.next point to the answer CTime complexity:$O(n+m)$Space complexity:$O(n+m)$solution1 public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) { return l2; } else if (l2 == null) { return l1; } if (l1.val < l2.val) { l1.next = mergeTwoLists(l1.next, l2); return l1; } else { l2.next = mergeTwoLists(l2.next, l1); return l2; } }IterationWe can make a new ListNode.Head node's next is the question answer.Iterate from start to finish these two List.When they end let the point to the remaining numberssolution2 public ListNode mergeTwoLists(ListNode l1, ListNode l2) { //make a New ListNode ListNode preHead = new ListNode(); //let the head still the head,make a pre to be a mark to find the next ListNode pre = preHead; while (l1 != null && l2 != null) { if (l1.val <= l2.val) { pre.next = l1; l1 = l1.next; } else { pre.next = l2; l2 = l2.next; } //update the pre pre = pre.next; } //the remaining ListNode must larger than another one,so just point to it pre.next = l1 == null ? l2 : l1; //after the head is the answer return preHead.next; }Time complexity:$O(n+m)$Space complexity:$O(1)$