皆、お疲れ様です - LeetCode
type: channel
link: https://iamyqhp.com/category/LeetCode/
items: LeetCode EasyTopic Notes3
items: LeetCode MediumTopic Notes5
items: LeetCode MediumTopic Notes4
items: LeetCode MediumTopic Notes3
items: LeetCode MediumTopic Notes2
items: LeetCode MediumTopic Notes1
items: LeetCode EasyTopic Notes10
items: LeetCode EasyTopic Notes9
items: LeetCode EasyTopic Notes8
items: LeetCode EasyTopic Notes7

LeetCode EasyTopic Notes3
type: item
date: 2023-08-26T05:46:00+08:00
description: 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 trave…

LeetCode MediumTopic Notes5
type: item
date: 2021-11-30T11:40:00+08:00
description: 54. Spiral MatrixThis problem is a two-dimensional array processing problem.The test point is how to loop and iterate when facing different situations.We can draw a picture to better understand.We can get the the array location [row,col].So we only need to proceed according to the requirements of the question.The difficulty of this question is that every time the position of the element is determined,it is easy to confirm the error.When we search for a complete row or column,we must subtract the current row or column,otherwise an error will occur.Solution public List<Integer> spiralOrder(int[][] matrix) { ArrayList<Integer> list = new ArrayList<>(); //define row and col int rowStart = 0, rowEnd = matrix.length - 1; int colStart = 0, colEnd = matrix[0].length - 1; //the number of all elements int allElement = (rowEnd + 1) * (colEnd + 1); //count the number of the elements what we add int counter = 0; while (rowStart <= rowEnd || colStart <= colEnd) { //top from left to right for (int i = colStart; i <= colEnd; i++) { list.add(matrix[rowStart][i]); counter++; } //we must subtract the current row or column,otherwise an error will occur rowStart++; if (counter == allElement) { break; } //right from top to bottom for (int i = rowStart; i <= rowEnd; i++) { list.add(matrix[i][colEnd]); counter++; } colEnd--; if (counter == allElement) { break; } //bottom from right to left for (int i = colEnd; i >= colStart; i--) { list.add(matrix[rowEnd][i]); counter++; } rowEnd--; if (counter == allElement) { break; } //left from bottom to top for (int i = rowEnd; i >= rowStart; i--) { list.add(matrix[i][colStart]); counter++; } colStart++; if (counter == allElement) { break; } } return list; }55. Jump GameIf you have already written the question 45. Jump Game II.So you can know this problem is also a greedy problem.The main idea to solve this question is the farthest distance every time you jump.The distance that each position can jump out is i+nums[i].So we can set a value maxMove,but …

LeetCode MediumTopic Notes4
type: item
date: 2021-11-17T04:47:00+08:00
description: 43. Multiply StringsThis question is very similar with question 2. Add Two Numbers.It's all math problems,if you want to understand this question clearly.You should draw a picture first.We can find that one number is multiplied by each digit of another number in turn.So we can think of using double for.Because we traverse the multiplier from right to left,so the whole process involves adding more strings.So we can use an array to instead of a string to store the result.And how long do we set the array?This is a very important question.We can set num1's length is m and num2's length is n,and both are them are not 0.If the num1 and num2 lengths are all take the minimum.So $num1=10^(m-1)$,$num2=10^(n-1)$,so $num1\times num2=10^(m+n-2)$,the length of the result is $m+n-1$If the num1 and num2 lengths are all take the maximum.So $num1=10^m-1$,$num2=10^n-1$,$num1 \times num2 = 10^(m+n)-10^m-10^n+1$,the length of the result is $m+n$So we can set a array which its length is $m+n$,and judge it at last.If it's first digit is 0,so we jump this digit.Solution public String multiply(String num1, String num2) { //the special situation if (num1.equals("0") || num2.equals("0")) { return "0"; } //we can use StringBuffer to create the result StringBuffer sb = new StringBuffer(); //n+m int[] array = new int[num1.length() + num2.length()]; for (int i = num1.length() - 1; i >= 0; i--) { //we can get the number int n1 = num1.charAt(i) - '0'; for (int i1 = num2.length() - 1; i1 >= 0; i1--) { int n2 = num2.charAt(i1) - '0'; int sum = array[i + i1 + 1] + n1 * n2; //make a example,8*4=32 32/10=3 32%10=2 array[i + i1 + 1] = sum % 10; array[i + i1] += sum / 10; } } //judge the first digit whether is 0 int index = array[0] == 0 ? 1 : 0; while (index < array.length) { sb.append(array[index]); index++; } return sb.toString(); }45. Jump Game IIThis question is a Greedy question.And what is greedy?Greedy is a very interesting solution.When we meet a problem of finding the optimal solution,we can reg…

LeetCode MediumTopic Notes3
type: item
date: 2021-11-08T05:22:00+08:00
description: 29. Divide Two IntegersThis question is a very interesting question.It does a lot of conditional restrictions.So we can only go back to the simplest mathematical method to think.What is division.7/3=2int count=0,7-3=4>3 count=1 4-3=1<3 count=2So this is division.Division is an optimization of subtraction.We can simplify this question.3*n=7 or 3*n-1<7 3*n>7The n is what we need to get.But when the dividend becomes extremely large,and the divisor becomes extremely small,it will cost so much time.So how do we optimize the addition operation?We know that double that multiplying growth is very fast.So we can use recursion to solve this question.There is one thing we must be notice.That's the problem of out-of bounds overflow.For example,if the dividend is Integer.MIN_VALUE and the divisor is 1,the result will overflow.Therefore,in order to facilitate the calculation,we make the situation where the dividend and the divisor are different,and turn both numbers into negative numbers.The box I drew is like multiplication,doubling.Solution public int divide(int dividend, int divisor) { //the special situation if (dividend == 0) { return 0; } if (dividend == Integer.MIN_VALUE && divisor == -1) { return Integer.MAX_VALUE; } //mark the different situation boolean sign = true; if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)) { sign = false; } //change them both into negative number dividend = dividend > 0 ? -dividend : dividend; divisor = divisor > 0 ? -divisor : divisor; //if there are different,so it must be a negative number,just 0 minus the result return sign == false ? 0 - count(dividend, divisor) : count(dividend, divisor); } /** * This recursion main code is while,it just likes optimization of subtraction */ private int count(int a, int b) { //if 3*n==7 just plus 1,or 3*n>7 just plus 0 if (a >= b) { return a > b ? 0 : 1; } //the default number is 1,and 2,4,8...doubling int n = 1; // int result = 0; int temp = b; while (a <= temp && temp < 0) { a -= temp; …

LeetCode MediumTopic Notes2
type: item
date: 2021-10-26T08:58:00+08:00
description: 15. 3SumThis question is similar with 1. Two Sum.But they have some different,the main different is this question is the solution set must not contain duplicate triplets.So we can't just use enumeration method,we need to think about how to avoid duplication.In the past,there were two main ways to avoid duplication.One is use HashMap,the other one is this array is ordered.If we just use enumeration method to traverse the entire array and then use HashMap.It will cost a lot of time and lost of space.So we should sort this array at first.And we can set center pointn.There three pointer are n,n+1,nums.length-1.Because this array is ordered,so if the n is the head of the array,so it means the all elements after n are all >0.So we don't need to traverse all the elements.But this is just a special situation.And how can we avoid duplication?This is a easy question,there three pointercenter n,left n+1,right nums.length-1.If the value of their next position is equal to the current,we move the current position to the next.Solution public List<List<Integer>> threeSum(int[] nums) { ArrayList<List<Integer>> lists = new ArrayList<>(); //the special situation if (nums.length < 3) { return lists; } //sort the array Arrays.sort(nums); //traversal the array for (int i = 0; i < nums.length; i++) { //if the smallest element is larger than 0,so all the elements are larger than 0,just break if (nums[i] > 0) { break; } //repetitive situation,just update the location if (i > 0 && nums[i] == nums[i - 1]) { continue; } //use two pointers,search from both sides int left = i + 1, right = nums.length - 1; while (left < right) { //find the 3sum if (nums[i] + nums[left] + nums[right] == 0) { //use Arrays.aslist make array to list lists.add(Arrays.asList(nums[i], nums[left], nums[right])); //repetitive situation,just update the location while (left < right && nums[left] == nums[left + 1]) { left++; } while (left < right && nums[right] == nums[right - 1]) { right--; } //update location left++; right…

LeetCode MediumTopic Notes1
type: item
date: 2021-10-21T09:23:00+08:00
description: 2. Add Two NumbersThis question is mathematics question. Each of us must have learned addition.So this is a carry sums of addition question.The question becomes clear.Addition of the same rank from left to right,when there is one carry left,ten digits will be added in the next calculationWhen the last number is reached,it is also necessary to judge whether to carrySolution public ListNode addTwoNumbers(ListNode l1, ListNode l2) { //create a ListNode of head ListNode head = new ListNode(0); //move pointer ListNode pre = head; //n is tens digit,cur is to judge the last number whether plus 1 int n = 0, cur = 0; while (l1 != null || l2 != null) { //if l1 ot l2 is to the end,just let it 0 int n1 = 0, n2 = 0; if (l1 != null) { n1 = l1.val; } if (l2 != null) { n2 = l2.val; } //count the sum of all this location number int sum = n1 + n2 + n; //refresh n,otherwise the last result will retained n = 0; //judge whether it is greater than 10 if (sum >= 10) { //tens digit n = 1; //digit sum = sum - 10; } //if n is 0,don't need add 1 at last cur = n; //create the new node pre.next = new ListNode(sum); //update the move pointer and two ListNode pre = pre.next; if (l1 != null) { l1 = l1.next; } if (l2 != null) { l2 = l2.next; } } //whether to add 1 at last if (cur == 1) { pre.next = new ListNode(cur); } return head.next; }3. Longest Substring Without Repeating CharactersThis question is a dynamic window problem.We need begin from the head,use two pointer.If the right pointer find the repeating character.Just move the left pointer one step.Record the distance between the left pointer and the right pointer each time.The max value is the answer.Solution public int lengthOfLongestSubstring(String s) { //use HashSet to mark the character HashSet<Character> hashSet = new HashSet<>(); //if j is 0,j++ is 1,equivalent to ignoring the first,so j must -1 int j = -1, length = 0; for (int i1 = 0; i1 < s.length(); i1++) { //this situation must find a repeating characters,so remove the first,if st…

LeetCode EasyTopic Notes10
type: item
date: 2021-10-17T09:09:00+08:00
description: 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 < ma…

LeetCode EasyTopic Notes9
type: item
date: 2021-10-11T10:09:00+08:00
description: 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 …

LeetCode EasyTopic Notes8
type: item
date: 2021-10-06T09:29:00+08:00
description: 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…

LeetCode EasyTopic Notes7
type: item
date: 2021-09-25T03:49:00+08:00
description: 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 s…