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

Removing duplicate Nodes (02.01)

Topic describes

Write code to remove duplicate nodes from an unsorted linked list. Keep the original node.

Example 1:

Input: [1, 2, 3, 3, 2, 1] Output: [1, 2, 3]Copy the code

Example 2:

Input: [1, 1, 1, 2] Output: [1, 2]Copy the code

prompt

  • The list length is in the range of [0, 20000].
  • The list elements are in the range [0, 20000].

** What if temporary buffers are not allowed?

Thought analysis

It is easy to think of using a hash table to solve this problem. Put the numbers in the hash table in sequence, and remove the node if it exists (with equal values). Time complexity is O(n){O(n)}O(n), space complexity is O(n){O(n)}O(n).

O(n2){O(n^2)}O(n2) {O(n^2)}O(n2) {O(n^2)}O(n2) The inner loop looks for the same value, and if it does, it removes the value, and the outer loop iterates to get the value after removing the duplicate node.

The code shown

Solution one: Time complexity is O(n){O(n)}O(n), space complexity is O(n){O(n)}O(n).

public ListNode removeDuplicateNodes(ListNode head) {
        if (head == null) {return null;
        }
        ListNode p = head;
        Set<Integer> set = new HashSet<>(); / / 1,2,3,3,2,1
        ListNode prev = null;
        while(p ! =null) {if (set.contains(p.val)){
                p = p.next;
                prev.next = prev.next.next;
            } else{ prev = p; set.add(p.val); p = p.next; }}return head;
    }
Copy the code

Method 2: time complexity is O (n2) {O (n ^ 2)} O (n2), space complexity is O (1) (1)} {O O (1).

public ListNode removeDuplicateNodes(ListNode head) {
        ListNode ob = head;
        while(ob ! =null) {
            ListNode oc = ob;
            while(oc.next ! =null) {
                if (oc.next.val == ob.val) {
                    oc.next = oc.next.next;
                } else {
                    oc = oc.next;
                }
            }
            ob = ob.next;
        }
        return head;
    }

Copy the code

Determining whether mutual character rearrangement is possible (01.02)

Topic describes

Given two strings s1 and s2, write a program that determines whether the characters of one string can be rearranged into the other string.

Example 1:

Input: s1 = "ABC ", s2 = "bca" Output: trueCopy the code

Example 2:

Input: s1 = "ABC ", s2 = "bad" output: falseCopy the code

Description:

  • 0 <= len(s1) <= 100
  • 0 <= len(s2) <= 100

Thought analysis

Topic given two strings, a string after rearrangement can become another string, we can also use hash table, put the string of characters stored in the hash table one by one, if already exists, the hash table corresponding to the value of the key value plus one, and then remove one by one, if the final value of the hash table is empty, Then you can determine that the two strings are rearranged as characters of each other. This solution is so simple that I won’t show it in this article.

Another solution is to create an array with the length of alphabet (26) and add and subtract the array index of the corresponding alphabet through a loop. Finally, if the unequal zeros in the array are not mutually rearranged.

The code shown

Solution 1: Time complexity is O(logn){O(logn)}O(logn), space complexity is O(1){O(1)}O(1).

public boolean CheckPermutation(String s1, String s2) {
        if (s1 == null || s2 == null) {return false;
        }
        int lengthOne = s1.length();
        int lengthTwo = s2.length();
        if (lengthOne == 0 || lengthTwo == 0) {return false;
        }
        if(lengthOne ! = lengthTwo){return false;
        }
        int[] memory = new int[26];
        for (int i = 0; i < lengthOne; i++){ memory[s1.charAt(i) -'a'] + +; memory[s2.charAt(i) -'a']--;
        }
        for (int num: memory){
            if(num ! =0) {return false; }}return true;
    }
Copy the code

conclusion

Hash table solution, a lot of times to simplify the problem solving process, but also can not avoid increased time complexity. It needs to be treated as appropriate according to the title.