求职Leetcode题目（12）

1.只出现一次的数字

异或运算满足交换律 a⊕b=b⊕a ，即以上运算结果与 nums 的元素顺序无关。代码如下：

class Solution {public int singleNumber(int[] nums) {int ans =0;for(int num:nums){ans^=num;}return ans;}
}

 2.只出现一次的数字II

这是今天滴滴的原题，要求时间复杂度为O(1)和空间复杂度为O(n) 

方法一：哈希表

思路与算法

我们可以使用哈希映射统计数组中每个元素的出现次数。对于哈希映射中的每个键值对，键表示一个元素，值表示其出现的次数。

在统计完成后，我们遍历哈希映射即可找出只出现一次的元素。

class Solution {public int singleNumber(int[] nums) {Map<Integer,Integer> freg =new HashMap<Integer,Integer>();for(int num:nums){freg.put(num,freg.getOrDefault(num,0)+1);}int ans =0;for(Map.Entry<Integer,Integer> entry:freg.entrySet()){int num =entry.getKey(),occ=entry.getValue();if(occ==1){ans =num;break;}}return ans;}
}

这个方法的效率显然不高，我们换一个思路试试看,而且时间复杂度不为O(1)

解法二：

如下图所示，考虑数字的二进制形式，对于出现三次的数字，各 二进制位 出现的次数都是 3 的倍数。
因此，统计所有数字的各二进制位中 1 的出现次数，并对 3 求余，结果则为只出现一次的数字。

3.随机链表复制

解题思路：

// Definition for a Node.
class Node {int val;Node next;public Node(int val) {this.val = val;this.next = null;}
}

 本题链表的节点定义如下：

// Definition for a Node.
class Node {int val;Node next, random;public Node(int val) {this.val = val;this.next = null;this.random = null;}
}

给定链表的头节点 head ，复制普通链表很简单，只需遍历链表，每轮建立新节点 + 构建前驱节点 pre 和当前节点 node 的引用指向即可。

本题链表的节点新增了 random 指针，指向链表中的 任意节点 或者 null 。这个 random 指针意味着在复制过程中，除了构建前驱节点和当前节点的引用指向 pre.next ，还要构建前驱节点和其随机节点的引用指向 pre.random 。

本题难点： 在复制链表的过程中构建新链表各节点的 random 引用指向。

class Solution {public Node copyRandomList(Node head) {Node cur = head;Node dum = new Node(0), pre = dum;while(cur != null) {Node node = new Node(cur.val); // 复制节点 curpre.next = node;               // 新链表的 前驱节点 -> 当前节点// pre.random = "???";         // 新链表的 「 前驱节点 -> 当前节点 」 无法确定cur = cur.next;                // 遍历下一节点pre = node;                    // 保存当前新节点}return dum.next;}
}

 可以对上面经典的复制链表的办法来解决这个问题

class Solution {public Node copyRandomList(Node head) {if(head == null) return null;Node cur = head;Map<Node, Node> map = new HashMap<>();// 3. 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射while(cur != null) {map.put(cur, new Node(cur.val));cur = cur.next;}cur = head;// 4. 构建新链表的 next 和 random 指向while(cur != null) {map.get(cur).next = map.get(cur.next);map.get(cur).random = map.get(cur.random);cur = cur.next;}// 5. 返回新链表的头节点return map.get(head);}
}

4.重排链表

 先了解怎么反转链表

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

思路分析:

对于题目给出的链表，简化如下：

class Solution {public void reorderList(ListNode head) {ListNode prev=null;ListNode cur =head;while(cur!=null){ListNode nextNode =cur.next;cur.next=prev;prev=cur;cur=nextNode;}return prev;}
}

还有一个关键步骤，求出链表的中间节点 ：

题目要求的是如果有两个中间节点，则返回第二个中间节点。因此，对于该题目而言，快指针fast向前移动的条件是：fast!=null && fast.next != null。

 

 下面是完整解法：

完整代码 ：

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
public void reorderList(ListNode head) {if (head == null) {return;}// 获得中间节点ListNode mid = findMid(head);// 中间节点之后的部分进行反转ListNode head2 = mid.next;mid.next = null;head2 = reverseList(head2);// 合并ListNode head1 = head;mergeList(head1, head2);
}// LeetCode 876
private ListNode findMid(ListNode head){ListNode slow = head;ListNode fast = head;while (fast.next != null && fast.next.next != null) {slow = slow.next;fast= fast.next.next;}return slow;
}// LeetCode 206
private ListNode reverseList(ListNode head){ListNode prev = null;ListNode cur = head;while (cur != null) {ListNode nextNode = cur.next;cur.next = prev;prev =cur;cur = nextNode;}return prev;
}private void mergeList(ListNode head1, ListNode head2) {ListNode next1 = null;ListNode next2 = null;while (head1 != null && head2 != null) {next1 = head1.next;next2 = head2.next;head1.next = head2;head1 = next1;head2.next = head1;head2 = next2;}
}