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

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…