Leetcode 20 valid parentheses, 33 search rotation sort array, 88 merge two ordered arrays (nums1 length is m+n), 160 intersecting linked list, 54 spiral matrix, 415 character addition (cannot be direc

Top1：Leetcode 20 Valid parenthesis

Official explanation ：https://leetcode.cn/problems/valid-parentheses/solution/you-xiao-de-gua-hao-by-leetcode-solution/
Title Description ：
Given one only includes ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ String s , Determines whether the string is valid .

Valid string needs to meet ：

Opening parentheses must be closed with closing parentheses of the same type .
The left parenthesis must be closed in the correct order .

Example 1：
Input ：s = “()”
Output ：true

Example 2：
Input ：s = “()[]{}”
Output ：true

Example 3：
Input ：s = “(]”
Output ：false

Example 4：
Input ：s = “([)]”
Output ：false

Example 5：
Input ：s = “{[]}”
Output ：true

One 、 Double ended queue implementation heap , Actually used to store the left parenthesis , Create a new one map Of key It's right bracket ,value It's left bracket .

Every time you encounter a right parenthesis map.containsKey(ch) When , Determine whether the heap top element is the corresponding left bracket , namely value value ,return eject stack.pop().else Just stack.push(ch). Finally back to stack Is it empty .

• Time complexity ：O（n）.n Is the length of a string
• Spatial complexity ：O(n+∣Σ∣), among \SigmaΣ Represents the character set , The string in this question only contains 66 Kind bracket ,|\Sigma| = 6∣Σ∣=6. The number of characters in the stack is O(n)O(n), The space used by the hash table is O(|\Sigma|)O(∣Σ∣), Add to get the total space complexity .

You can use the complete code ：

public boolean isValid(String s) {
    
    int n = s.length();
    if (n % 2 == 1) return false;   //  prune , Reduce useless cycles 
    Map<Character, Character> map = new HashMap<Character, Character>() {
       // <> If the type is not written in it, an error will be reported 
        {
    
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }
    };
    Deque<Character> stack = new LinkedList<>();   //  Double ended queue implementation heap 【 Double ended queue peek and pop It's all the one on the top 、 The team First that 】（ First in, then out , Pile things up 【 At first, everything was piled underneath 】）
    for (int i = 0; i < n; i++) {
       //  meet {[]} situations , First step [ Already added , Judge directly later stack Whether the pile top exists （ Or whether the heap is empty ）
        char ch = s.charAt(i);
        if (map.containsKey(ch)) {
    
            if (stack.isEmpty() || stack.peek() != map.get(ch)) return false;   //  If not of the same type , Or there is no left parenthesis in stack , So the string  s  Invalid 
// if (stack.peek() != map.get(ch)) return false; // 【 No judgment stack The pile is empty , Just judge the top of the pile 】
            stack.pop();
        } else {
    
            stack.push(ch);
        }
    }
    return stack.isEmpty();
}

Top2：Leetcode 33 Search rotation sort array

Official explanation ： Add link description
Title Description ：
An array of integers nums In ascending order , The values in the array Different from each other .

Before passing it to a function ,nums In some unknown subscript k（0 <= k < nums.length） On the rotate , Make array [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（ Subscript from 0 Start Count ）. for example , [0,1,2,4,5,6,7] In subscript 3 It may turn into [4,5,6,7,0,1,2] .

Here you are. After rotation Array of nums And an integer target , If nums There is a target value in target , Returns its subscript , Otherwise return to -1 .

You have to design a time complexity of O(log n) The algorithm to solve this problem .

Example 1：
Input ：nums = [4,5,6,7,0,1,2], target = 0
Output ：4

Example 2：
Input ：nums = [4,5,6,7,0,1,2], target = 3
Output ：-1

Example 3：
Input ：nums = [1], target = 0
Output ：-1

Two points search .nums[0] <= nums[mid] For left order , example ：【456 7 8 123】.else Right order

• Time complexity ：O（logn）. among n by nums Size of array . The time complexity of the whole algorithm is the time complexity of binary search O(logn).
• Spatial complexity ：O（1）. We only need constant level to store variables . Directly to arrays nums1 Modify in place , No need for extra space .

You can use the complete code ：

public int search(int[] nums, int target) {
       // [3, 1]
    int n = nums.length;
    if (n == 0) return -1;
    if (n == 1) return nums[0] == target ? 0 : -1;   //  Dichotomy requires n At least for 2
    int l = 0, r = n - 1;
    while (l <= r) {
    
        int mid = (l + r) / 2;
        if (nums[mid] == target) return mid;
        if (nums[0] <= nums[mid]) {
       //  Left order 【456 7 8 123】
            if (nums[0] <= target && target < nums[mid]) r = mid - 1;
            else l = mid + 1;   //  In the case of equality, the first 3 That's ok , At this time, it has been excluded 
        } else {
       //  Right order 【78 12 3 45】
            if (nums[mid] < target && target <= nums[n - 1]) l = mid + 1;
            else r = mid - 1;
        }
    }
    return -1;
}

Top3：Leetcode 88 Merge two ordered arrays （nums1 The length is m+n）

Official explanation ：https://leetcode.cn/problems/merge-sorted-array/solution/he-bing-liang-ge-you-xu-shu-zu-by-leetco-rrb0/
Title Description ：
Here are two buttons Non decreasing order Array of arranged integers nums1 and nums2, There are two other integers m and n , respectively nums1 and nums2 The number of elements in .

Would you please Merge nums2 To nums1 in , Make the merged array press Non decreasing order array .

Be careful ： Final , The merged array should not be returned by the function , It's stored in an array nums1 in . In response to this situation ,nums1 The initial length of is m + n, The top m Elements represent the elements that should be merged , after n Elements are 0 , It should be ignored .nums2 The length of is n .

Example 1：
Input ：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output ：[1,2,2,3,5,6]
explain ： Need merger [1,2,3] and [2,5,6] .
The combined result is [1,2,2,3,5,6] , In which, bold italics indicates nums1 The elements in .

Example 2：
Input ：nums1 = [1], m = 1, nums2 = [], n = 0
Output ：[1]
explain ： Need merger [1] and [] .
The combined result is [1] .

Example 3：
Input ：nums1 = [0], m = 0, nums2 = [1], n = 1
Output ：[1]
explain ： The array to be merged is [] and [1] .
The combined result is [1] .
Be careful , because m = 0 , therefore nums1 No elements in .nums1 The only remaining 0 Just to ensure that the merged results can be successfully stored in nums1 in .

One 、 Reverse double pointer . Compare nums1[p1] and nums2[p2] Size , Select place to nums1[tail--] The elements of . a party p1 or p2 by -1 When , direct tail-- = p1-- perhaps tail-- = p2-- The element is finished .

example ： There are only two elements 1 and 2, First, compare the placement nums1[tail–] = 2; Then judge p2==-1【 More than 2 When the elements are three, they gradually ！=-1 Join in p1】, prevent nums1[tail–] = 1 end

• Time complexity ：O（m+n）. One traverse
• Spatial complexity ：O（1）. Constant space complexity

You can use the complete code ：

public void merge(int[] nums1, int m, int[] nums2, int n) {
    
    int p1 = m - 1, p2 = n - 1;
    int tail = m + n - 1;
    int cur;
    while (p1 >= 0 || p2 >= 0) {
       //  Suppose there is one element each ： Compare 1 2 After placement 2 The subscript of becomes -1,nums1[tail--] = cur = nums[0--]
        if (p1 == -1) {
    
            cur = nums2[p2--];
        } else if (p2 == -1) {
    
            cur = nums1[p1--];
        } else if (nums1[p1] > nums2[p2]) {
    
            cur = nums1[p1--];
        } else {
    
            cur = nums2[p2--];
        }
        nums1[tail--] = cur;
    }
}

Top4：Leetcode 160 Intersecting list

Official explanation ：https://leetcode.cn/problems/intersection-of-two-linked-lists/solution/xiang-jiao-lian-biao-by-leetcode-solutio-a8jn/
Title Description ：
Here are two head nodes of the single linked list headA and headB , Please find out and return the starting node where two single linked lists intersect . If two linked lists do not have intersecting nodes , return null .

Figure two linked lists at the node c1 Start meeting ：

One 、 Double pointer . Take a step from pA Turn into pA.next. If it intersects , When all gone a+b+c Then they will meet at the intersection

Two 、 After walking each other , because It's starting from the beginning , So go to pA=null after ; Continue to point to headB The head node of , Start walking B The length of

Disjoint words will become null , No matter what m whether =n, Walk the m+n after , Will appear pA=pA.next【 At this time, if they are not equal ,pA Already pointed pB On a node 】=null,pB=pB.next【 Empathy 】=null The situation of ,return pA=null

• Time complexity ：O（m+n）. among m and n Yes, they are linked lists headA and headB The length of . Two pointers traverse two linked lists at the same time , Each pointer traverses two linked lists once each .
• Spatial complexity ：O（1）.

You can use the complete code ：

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    
    if (headA == null || headB == null) return null;
    ListNode pA = headA, pB = headB;
    while (pA != pB) {
       //  Take a step from pA Turn into pA.next
        pA = pA == null ? headB : pA.next;   //  Because I finished walking at the same time a+b+c, Just to c The first node of , That is, the intersection 
        pB = pB == null ? headA : pB.next;   //  Example ： It's all over a+b+c=8 After step , All to the one before the intersection node
    }
    return pA;
}

Top5：Leetcode 54 Spiral matrix

Official explanation ：https://leetcode.cn/problems/spiral-matrix/solution/luo-xuan-ju-zhen-by-leetcode-solution/
Title Description ：
To give you one m That's ok n Columns of the matrix matrix , Please follow Clockwise spiral sequence , Returns all elements in the matrix .

One 、 Layer by layer simulation . Define the endpoints of two line segments ：left,right;top,bottom. It's best to draw four dots , Pay attention to the scanning for Circular boundary conditions

Two 、 cross , After the vertical scan , Reuse < Scan left and scan up to prevent repeated scanning

• Time complexity ：O（mn）.
• Spatial complexity ：O（1）. In addition to the output array , Space complexity is a constant .【 The output array is not included in the computational space complexity 】

You can use the complete code ：

public List<Integer> spiralOrder(int[][] matrix) {
    
    List<Integer> order = new ArrayList<>();
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return order;
    int rows = matrix.length, columns = matrix[0].length;   //  Row and column 
    int left = 0, right = columns - 1, top = 0, bottom = rows - 1;   //  Define the four point subscripts of two edges 
    while (left <= right && top <= bottom) {
       //  There's an equal sign , Because there will be odd numbers , Only the middle one is left 
        for (int column = left; column <= right; column++) {
    
            order.add(matrix[top][column]);
        }
        for (int row = top + 1; row <= bottom; row++) {
    
            order.add(matrix[row][right]);
        }
        if (left < right && top < bottom) {
       //  Use < Prevent repeated scanning 
            for (int column = right - 1; column > left; column--) {
       //  The shortest one , barring left
                order.add(matrix[bottom][column]);
            }
            for (int row = bottom; row > top; row--) {
       //  From bottom to top 
                order.add(matrix[row][left]);
            }
        }
        left++;
        right--;
        top++;
        bottom--;
    }
    return order;
}

Top6：Leetcode 415 Character addition （ Don't go straight to Int）

Official explanation ：https://leetcode.cn/problems/add-strings/solution/zi-fu-chuan-xiang-jia-by-leetcode-solution/
Title Description ：
Given two non negative integers in string form num1 and num2 , Calculate their sum and return as a string .

You can't use any built-in library for handling large integers （ such as BigInteger）, You can't directly convert the input string to integer form .

Example 1：
Input ：num1 = “11”, num2 = “123”
Output ：“134”

Example 2：
Input ：num1 = “456”, num2 = “77”
Output ：“533”

Example 3：
Input ：num1 = “0”, num2 = “0”
Output ：“0”

One 、 Use thread safe StringBuffer To save the answer , Try to write less code . Use intermediate variables int x = i < 0 ? 0 : num1.charAt(i--) - '0'; // Because there is j-- therefore i Minimum to -1x,y Come on , The last cycle can be one more add！=0.

Use -‘0’ To calculate the number represented by characters instead of directly converting

Two 、 Join in %,add=/.StringBuffer Of reverse() The time complexity of the function is O（n）

• Time complexity ：O（max(len1,len2)）.
• Spatial complexity ：O（1）. In addition to the answer We just need constant space to hold a number of variables .

You can use the complete code ：

public String addStrings(String num1, String num2) {
    
    StringBuffer ans = new StringBuffer();
    int i = num1.length() - 1, j = num2.length() - 1;
    int add = 0;
    while (i >= 0 || j >= 0 || add != 0) {
       //  Finally, if there is a carry, it will also be executed add！=0
        int x = i < 0 ? 0 : num1.charAt(i--) - '0';   //  Because there is j-- therefore i Minimum to -1
        int y = j < 0 ? 0 : num2.charAt(j--) - '0';
        int result = x + y + add;
        ans.append(result % 10);
        add = result / 10;
    }
    ans.reverse();
    return ans.toString();   //  To String Class return 
}

Stringbuffer Of reverse() Function source code ：

j = (n-1) >> 1   //  Subscript divided by 2

You can see in the source code

• j = (n-1) >> 1：//j Is the subscript corresponding to the left traversal from the center of the array . Intermediate and firstEnd
• k = n - j：//k Is the subscript corresponding to the right traversal from the center of the array . Intermediate and secondStart

Time complexity : O(n), Spatial complexity : O(1)
The code is as follows ：

public AbstractStringBuilder reverse() {
    boolean hasSurrogates = false;
    //count Is the length of a string 
    int n = count - 1;
    //j The initial value of is the array length /2
    for (int j = (n-1) >> 1; j >= 0; j--) {
    //j Is the subscript corresponding to the left traversal from the center of the array 
    //k Is the subscript corresponding to the right traversal from the center of the array 
        int k = n - j;
        // take value[j] And value[k] Exchange of elements 
        char cj = value[j];
        char ck = value[k];
        value[j] = ck;
        value[k] = cj;
        if (Character.isSurrogate(cj) ||
            Character.isSurrogate(ck)) {
            hasSurrogates = true;
        }
    }
    if (hasSurrogates) {
        reverseAllValidSurrogatePairs();
    }
    return this;
}

Reference link ：StringBuilder Of Reverse() Method source code