LeetCode 移除重复节点/单词频率[哈希]-一一网

这是我参与更文挑战的第 16 天，活动详情查看：更文挑战

移除重复节点（02.01）

题目描述

编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。

示例 1：

输入：[1, 2, 3, 3, 2, 1]
输出：[1, 2, 3]
复制代码

示例 2：

输入：[1, 1, 1, 1, 2]
输出：[1, 2]
复制代码

提示

链表长度在[0, 20000]范围内。
链表元素在[0, 20000]范围内。

**进阶：**如果不得使用临时缓冲区，该怎么解决？

思路分析

看到这道题很容易想到使用哈希表进行解答，依次将数字存放到哈希表中，如果存在该节点（值相等），就移除该节点，时间复杂度是 ${O(n)}$ ，空间复杂度为 ${O(n)}$ 。

题目的进阶要求不使用临时缓冲区，就说要求空间复杂度为 ${O(1)}$ ，那么时间复杂度肯定就没有上面那样简单了，我们需要 ${O(n^2)}$ 的时间复杂度，先遍历外层循环，拿出某个链表的值，再在内层循环上查找是否有相等的值，如果存在，就移除该值，一样外层循环遍历完，就得到了移除重复节点后的值。

代码展示

解法一：时间复杂度是 ${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;
    }
复制代码

解法二：时间复杂度是 ${O(n^2)}$ ，空间复杂度是 ${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;
    }

复制代码

判断是否互为字符重排（01.02）

题目描述

给定两个字符串 s1 和 s2，请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。

示例 1：

输入: s1 = "abc", s2 = "bca"
输出: true 
复制代码

示例 2：

输入: s1 = "abc", s2 = "bad"
输出: false
复制代码

说明：

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

思路分析

题目给定两个字符串，某个字符串重排后就能变成另一个字符串，我们也可以利用哈希表进行处理，将字符串中的字符一个个存放到哈希表中，如果已经存在，就把哈希表对应 key 的 value 值加一，最后再一个个移除掉，如果最终哈希表的值为空，那么就可以确定两个字符串是互为字符重排的。这种解法很简单，本文就不做展示了。

还有一种解法是我们新建长度为字母表长度（26）的数组，通过一次循环，对对应字母表上的数组索引进行自加和自减，最后如果该数组上的不等 0，就不是互为字符重排。

代码展示

解法一：时间复杂度是 ${O(logn)}$ ，空间复杂度是 ${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;
    }
复制代码