Leetcode hot topic 100 topic 6-10 solution

           

Catalog

T6 10. Regular Expression Matching （ difficult ）

T7 11. Into a container with the most water

Ideas 1（ Double pointer ）

 T8 15. Sum of three numbers

Ideas 1（ Sort + Double pointer ）

T9 17. Letter combination of telephone number

  Ideas 1（ Level traversal ）

Ideas 2（ Depth traversal ）

T10 19. Delete the last of the linked list N Nodes .（ Simple , Skipping ）

Ideas 1

---

T6 10. Regular Expression Matching

  Not yet done , I'll add it when I make it .

T7 11. Into a container with the most water

  Topic presentation ：

Power button https://leetcode-cn.com/problems/container-with-most-water/

Ideas 1

Set the pointer at both ends respectively l,r, Gradually search in the middle . Because traversal through the middle , The length of the container is reduced , If you want to maximize the container capacity , therefore , Move l,r The middle and small end , If the capacity becomes larger , Then the maximum capacity value is recorded . until i=j, stop searching .

class Solution {
    public int maxArea(int[] height) {
        int head = 0,tail = height.length-1;
        int max = 0;
        int min = 0;
        int square = 0;
        while(head<tail){
            min = height[head];
            if(min>height[tail]){
                min = height[tail];
                tail--;
            }else
                head++;
            square = min * (tail-head+1);
            if(square>max){// to update max
                max = square;
            }
        }
        return max;
    }
}

 T8 15. Sum of three numbers

  Topic presentation ：

Power button https://leetcode-cn.com/problems/3sum/

Ideas 1

Sort + Double pointer ： Because the title requires no repeating elements , So first sort the array . Then the first element i use for Loop through , The last two elements , Set as j = i+1,k = len-1（ One of the biggest , A minimum ）.

• If the sum of the three numbers is greater than 0, Then move k Elements .（ Reduce the sum of three numbers ）
• If less than 0, Then move j Elements .（ Increase the sum of three numbers ）
• If it is equal to the 0, Add this triplet to the list , Move at the same time j,k Two elements .

May adopt list.contains(s） Remove duplicate tuples , But it takes a lot of time . So you can add a double condition .

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res  = new ArrayList<List<Integer>>();
        int i,j,k;
        // // Bubbling 
        // for(i= 0;i<nums.length;i++){
        //     int min = i;
        //     for(j = i+1;j<nums.length;j++){
        //         if(nums[min]>nums[j]){
        //             min = j;
        //         }
        //     }
        //     if(min!=i){
        //         int t = nums[min];
        //         nums[min] = nums[i];
        //         nums[i] = t;
        //     }
        // }
        Arrays.sort(nums);// Sorting function 
        for(i = 0;i<nums.length-2;i++){
            if(nums[i]>0||nums[nums.length-1]<0)// If the first element is greater than 0 Or the last element is less than 0, And then jump out of the loop .
                break;
            while(i!=0&&i<nums.length-2&&nums[i]==nums[i-1]){// Avoid repeating elements 
                i++;
            }
            j = i+1;
            k = nums.length-1;
            while(j<k){
                if(nums[i]+nums[j]+nums[k]==0){
                    List<Integer> s = new ArrayList<Integer>();
                    s.add(nums[i]);
                    s.add(nums[j]);
                    s.add(nums[k]);
                    // if(!res.contains(s)){// With this function, some conditions can be removed , But it takes a lot of time 
                    //     res.add(s);
                    // }
                    res.add(s);
                    j++;// hinder while The condition is to remove duplicate elements .
                    while(j<k && nums[j]==nums[j-1]) j++;
                    k--;
                    while(k>j && nums[k]==nums[k+1]) k--;
                }else if(nums[i]+nums[j]+nums[k]>0){
                        // if(nums[j]>0)//********************** */
                        //     break;
                        k--;
                        while(k>j && nums[k]==nums[k+1]) k--;
                }else{
                    if(nums[k]<0)//************************** */
                        break;
                    j++;
                    while(j<k && nums[j]==nums[j-1]) j++;
                } 
                
            }

        }
        return res;
    }
}

T9 17. Letter combination of telephone number

Topic presentation ： 

Power button https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/

  Ideas 1

          Use hierarchical traversal . First for loop , take digits Number in , Whenever you take out a new number , Then update list.

class Solution {
    public List<String> letterCombinations(String digits) {
        int len = digits.length();
        ArrayList<String> s = new ArrayList<String>();
        s.addAll(Arrays.asList("abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"));
        int i,j,k;
        List<String> res = new ArrayList<String>();// Store returned results 
        
        if(len==0)// If digits It's empty , Direct return null 
            return res;
        res.add("");
        for(i = 0;i<len;i++){
            int num = digits.charAt(i)-'2';
            String letter = s.get(num);
            int count = res.size();
            for(j = 0;j<count;j++){
                String str = res.get(j);
                res.set(j,str+letter.charAt(0));
                String a;
                for(k = 1;k<s.get(num).length();k++){
                    a = str + s.get(num).charAt(k);
                    res.add(a);
                }
            }
        }
        return res;
    }
}

Ideas 2

      Using depth traversal .

class Solution {
    String[] smap = {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    List<String> res = new ArrayList<String>();// Record the returned results 
    public List<String> letterCombinations(String digits) {
        dfs(0,"",digits); 
        return res;
    }

    public void dfs(int depth, String letter,String digits){
        if(depth == digits.length()){
            return;
        }else{
            for(int i = 0;i<smap[digits.charAt(depth)-'2'].length();i++){
                dfs(depth+1,letter+smap[digits.charAt(depth)-'2'].charAt(i),digits);
                if(depth==digits.length()-1)
                    res.add(letter+smap[digits.charAt(depth)-'2'].charAt(i));
            }
        }
    }
}

T10 19. Delete the last of the linked list N Nodes .

Title Description

Power button https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

Ideas 1

First, traverse the total number of nodes in the linked list . Then find the penultimate n individual , Delete them .

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head.next==null){
            return null;
        }
        int count = 1;
        ListNode p = head;
        while(p.next!=null){
            p = p.next;
            count++;
        }// Traversing the linked list , Record the total number of nodes .
        if(count==n){
            p = head.next;
            return p;
        }else{
            count = count - n;
            int num = 1;
            p = head;
            while(num<count){
                p = p.next;
                num++;
            }
            p.next = p.next.next;
            return head;
        }
    }
}