每日两题--20220103

每日两题--2022/01/03 1171. 从链表中删去总和值为零的连续节点

描述

给你一个链表的头节点 head，请你编写代码，反复删去链表中由 总和 值为 0 的连续节点组成的序列，直到不存在这样的序列为止。
删除完毕后，请你返回最终结果链表的头节点。

思路
要删去链表中由 总和 值为 0 的连续节点组成的序列，刚开始想的是先转换成数组，然后通过遍历，找出和为0的序列，以此解决问题，但是复杂度比较高。
可以通过前缀和来解决，当出现相同的前缀和是，则中间的序列和为0，直接全部摘链

1. new一个虚拟头node指向head，注意后续遍历中 *** 作链表node不能动，均需用临时tmp *** 作
2. 第一遍遍历链表，用map记录前缀和sum以及节点node的关系，此时会记录下最后一次出现的(sum，node)
3. 第二遍遍历链表，将链表中前缀和所对应的节点的next指到map中该前缀和所对应的节点的next（相当于把中间和为0的节点全部摘链）
4. 返回node.next

题解

class Solution {
    public ListNode removeZeroSumSublists(ListNode head) {
        ListNode node = new ListNode(0, head);     
        Map map = new HashMap<>();

        //第一遍遍历，把前缀和以及对应节点存入map，后续相同前缀和会直接覆盖
        int sum = 0; 
        ListNode tmp = node;
        while(tmp != null){
            sum += tmp.val;
            map.put(sum, tmp);
            tmp = tmp.next; 
        }

        //第二遍遍历，将链表中前缀和对应节点的next指到map中该前缀和对应节点的next，相同前缀和中间（说明中间序列和为0）的节点摘链
        sum = 0; 
        tmp = node;
        while(tmp != null){
            sum += tmp.val;
            tmp.next = map.get(sum).next;
            tmp = tmp.next;
        }

        return node.next;
    }
}

136. 只出现一次的数字

描述

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

思路

1. 用异或来解
2. 交换律：a ^ b ^ c <=> a ^ c ^ b
3. 任何数于0异或为任何数 0 ^ n => n
4. 相同的数异或为0: n ^ n => 0

题解

class Solution {
    public int singleNumber(int[] nums) {
        int tmp = 0;

        for(int i = 0; i < nums.length; i++){
            tmp ^= nums[i];
        }

        return tmp;
    }
}