求职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;}
}