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

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 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…

LeetCode EasyTopic Notes6
type: item
date: 2021-09-20T04:01:00+08:00
description: 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;…

LeetCode EasyTopic Notes5
type: item
date: 2021-09-15T09:06:00+08:00
description: 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 hea…

LeetCode EasyTopic Notes4
type: item
date: 2021-09-06T10:22:00+08:00
description: 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…

LeetCode EasyTopic Notes2
type: item
date: 2021-08-14T06:14:00+08:00
description: 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 publi…

LeetCode EasyTopic Notes1
type: item
date: 2021-08-08T06:26:00+08:00
description: 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 tha…