1. LeetCode316

Remove duplicate letters

This question has three requirements:
1. Remove duplicate elements from string
2. The alphabetical order in the string cannot be disordered
3. The minimum dictionary order of the returned string is required
Here, the first two requirements are easy to meet. It's easy to think of monotonous stack, but the third requirement is what is dictionary order? This means that if "abc" and "bac" meet the first two requirements, the first combination with smaller dictionary order needs to be returned. That is to say, before we re-enter the stack, we must judge whether the element to be put into the stack is larger than the element at the top of the stack. If it is larger than the element at the top of the stack, we need to know whether the element at the top of the stack will appear in the future. If there is any, it means that we can boldly pop it out first and then put the new element into the stack. If there is no element at the top of the stack in the future, we can't pop it up.

class Solution {
    public String removeDuplicateLetters(String s) {
        //Save the result of de duplication
        Stack<Character> stack = new Stack<>();
        //Count the number of occurrences of each character in s
        int[] cnt = new int[256];
        for(char c : s.toCharArray()){
            cnt[c]++;
        }
        //Flag whether the element exists in the stack
        boolean[] isExist = new boolean[256]; 
        for(char c : s.toCharArray()){
            cnt[c]--;//Reduce the number by one for each traversal
            if(isExist[c]) continue;
            //If not included, compare the letter at the top of the stack with the letter at the top of the stack, and judge whether it will appear later. If it will appear again, the element at the top of the stack will pop up. If it does not appear, it cannot pop up
            while(!stack.isEmpty() && c < stack.peek()){
                if(cnt[stack.peek()] == 0){
                    break;
                }
                isExist[stack.peek()] = false;
                stack.pop();    
            }
            stack.push(c);
            isExist[c] = true;
        }

        StringBuilder sb = new StringBuilder();
        while(!stack.isEmpty()){
            sb.append(stack.pop());
        }
        return sb.reverse().toString();
    }
}

2. LeetCode26

Remove duplicates from ordered arrays


The title requires no additional space, that is, we are required to modify the array in situ. The array is already in order, so the repeated elements must be connected together. This is a typical double pointer problem. First define a left pointer and a right pointer. The right pointer first finds the first number that is not equal to the left pointer, and then assigns the number pointed by the left pointer + 1 and the right pointer to the left pointer. In this way, when the right pointer reaches the end of the array, the left pointer + 1 is the length of the non repeating array.

class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums == null) return 0; 

        int left = 0;
        int right = 1;
        while(right < nums.length){
           if(nums[left] != nums[right]){
               left++;
               nums[left] = nums[right];
           }
           right++;
        }
        return left+1;
    }
}

3. LeetCode83

Delete duplicate elements in the sorting linked list


This question is basically the same as the previous one, except that the operation of array assignment is programmed to operate the next node of the linked list. Consistent thinking. However, it should be noted that the array only needs to return the length that is not repeated, and the linked list needs to disconnect the part connected with the back!

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null) return null;
        ListNode low = head;
        ListNode fast = head;
        while(fast != null){
            if(fast.val != low.val){
                low.next = fast;
                low = low.next;
  **Bold style**          }
            fast = fast.next;
        }
        low.next = null;  //Disconnect from subsequent elements
        return head;
    }
}

4. LeetCode27

Removing Elements


The idea of removing elements is similar. The right pointer first finds the first number that is not the target value, and then assigns it to the left pointer. The left pointer moves back until the right pointer traverses the array.

class Solution {
    public int removeElement(int[] nums, int val) {
        int left = 0;
        int right = 0;
        while(right < nums.length){
            if(nums[right] != val){
                nums[left] = nums[right];
                left++;
            }
            right++;
        }
        return left;
    }
}

5. LeetCode283

Move zero

This question is based on the previous question. Just add a zero filling operation later.

class Solution {
    public void moveZeroes(int[] nums) {
        int left = 0;
        int right = 0;
        while(right < nums.length){
            if(nums[right] != 0){
                nums[left] = nums[right];
                left++;
            }
            right++;
        }
        for(int i = left; i < nums.length; i++){
            nums[i] = 0;
        }
    }
}