This is the 7th day of my participation in Gwen Challenge

Subject address: leetcode-cn.com/problems/3s…

15 questions

Title description:

Given an array nums containing n integers, determine if there are three elements a, B, and c in nums such that a + b + c = 0. Please find all the triples that sum to 0 and are not repeated.

Note: Repeated triples cannot be included in the answer.

Example 1:

Input: nums = [1, 2, 1, 4] output: [[1, 1, 2], [1, 1]] example 2:

Input: nums = [] Output: [] Example 3:

Input: nums = [0]

Tip:

0 <= nums.length <= 3000 -105 <= nums[i] <= 105

Violence to solve

Step1: How to remove repetition? To make sure that we don’t have three numbers that are repeated, we can take three numbers that are ordered in order a<=b<=c and that’s because a+b+c = 0. The idea of taking a number is:

Take a first. If a is the same as the last one, skip the next one.

I’m going to take b, and I’m going to take b after a and if B is the same as b last time, I’m going to skip the next one

So let’s do the same thing with c, c if it’s the same as last time we skip it.

Step2: judge whether the sum of the three numbers taken out is 0

Because when the smallest number is greater than 0, the sum of the three numbers cannot be 0, so you just quit the loop

Reference code:

/** ** */
    List<List<Integer>> solution1(int[] nums) {
        Arrays.sort(nums);
        int length = nums.length;
        int lastI = Integer.MAX_VALUE, lastJ, lastK;
        List<List<Integer>> arrayList = new ArrayList<>();
        for (int i = 0; i < length; i++) {
            if (lastI == nums[i]) {
                continue;
            }
            if(lastI > 0) {break;
            }
            // Enter the next cycle
            lastJ = Integer.MAX_VALUE;
            lastI = nums[i];
            for (int j = i + 1; j < length; j++) {
                if (lastJ == nums[j]) {
                    continue;
                }
                lastJ = nums[j];
                lastK = Integer.MAX_VALUE;
                for (int k = j + 1; k < length; k++) {
                    if (lastK == nums[k]) {
                        continue;
                    }
                    lastK = nums[k];
                    if (lastI + lastJ + lastK == 0) {
                        ArrayList<Integer> integerArrayList = new ArrayList<>();
                        integerArrayList.add(lastI);
                        integerArrayList.add(lastJ);
                        integerArrayList.add(lastK);
                        arrayList.add(integerArrayList);
                    }
                }
            }
        }
        System.out.println("solution1 size " + arrayList.size());
        return arrayList;
    }
Copy the code

Double pointer

When the sum of the three numbers is less than 0, the middle number is increased; when the sum of the three numbers is greater than 0, the maximum number is decreased

Reference code:

List<List<Integer>> solution2(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> arrayList = new ArrayList<>();
        int lastI = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] == lastI){
                continue;
            }
            lastI = nums[i];
            int start=i+1, end = nums.length - 1;
            int lastStart = Integer.MAX_VALUE;
            int lastEnd = Integer.MAX_VALUE;
            boolean changeStart = true;
            while (start<end){
                if(lastStart == nums[start] && changeStart){
                    start++;
                    continue;
                }
                if(lastEnd == nums[end] && ! changeStart){ end--;continue;
                }
                lastStart = nums[start];
                lastEnd = nums[end];
                int result = nums[i]+nums[start]+nums[end];
                if(result > 0){
                    changeStart = false;
                    end--;
                }else if(result < 0){
                    changeStart = true;
                    start++;
                }else {
                    ArrayList<Integer> integerArrayList = new ArrayList<>();
                    integerArrayList.add(nums[i]);
                    integerArrayList.add(nums[start]);
                    integerArrayList.add(nums[end]);
                    arrayList.add(integerArrayList);
                    start++;
                    changeStart = true; }}}return arrayList;
    }
Copy the code

19 questions

Subject address: leetcode-cn.com/problems/re…

Title description:

Given a linked list, delete the NTH node from the bottom of the list and return the head of the list.

** Advanced: ** Can you try using a scan implementation?

Example 1:

Input: head = [1,2,3,4,5], n = 2 output: [1,2,3,5] example 2

Input: head = [1], n = 1 Output: [] Example 3:

Input: head = [1,2], n = 1

Tip:

The number of nodes in the linked list is sz 1 <= sz <= 30 0 <= node. val <= 100 1 <= n <= sz

Answer key:

Since the problem requires a scan, it’s easy to think of using double Pointers to solve the problem.

Let’s say we want the next-to-last pointer, so we don’t want to store too much data, and when the next pointer is empty, the previous pointer is at 3, and the next element is deleted. 13,24,35 we use count to record the number of steps taken by the previous pointer. The front pointer starts to move when count is greater than n.

Special circumstances:

If n is greater than the length of the list, there is no need to delete elements

N is equal to the length of the list, and it’s the header that needs to be deleted

Reference code:

 public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head == null) {return null;
        }
        ListNode h = head;
        ListNode pre = head;
        int count = 0;
        while(pre! =null) {if(count>n){
                h = h.next;
            }
            pre = pre.next;
            count++;
        }
        if(count>n){// You need to delete it
            ListNode temp = h.next;
            h.next = temp.next;
        }else if(count == n){// Delete the header pointer
            head = h.next;
        }
        return head;
    }
Copy the code