一、只出现一次的数字
1.1 题目描述
给你一个非空整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
1.2 思路分析
这道题可以通过使用Map集合将数组中的数字作为键存储，这个数字出现的次数作为值存储，将整个数组遍历按这个键值对的方式存储，最后再遍历这个集合判断哪个数字对应的值为1就表示这个数字只出现了一次：
- 创建Map集合，遍历数组，根据当前数字作为键的参数拿到集合中的值count，再判断这个count值是否为空，若为空，则默认这个值为1，将其和当前数字添加到Map集合中，若不为空，则这个值自增1，表示第二次出现这个数字，再将其和当前数字添加到Map集合中，覆盖之前的键值对，当遍历完这个数组后，再对Map集合进行遍历，根据数字作为键的参数得到它所出现的次数，判断这个此时是否等于1，若等于1，即表示当前数字只出现了一次，返回这个数字即可。
巧用技巧，这道题还有一个比较简单的方式，由于数组中肯定有一个数字只出现了一次，其它数字都是成对出现的，所以可以将整个数组的数字进行按位异或，两个相同的数字异或为0,0异或任何数仍未任何数：- 定义一个变量拿到数组的第一个元素，然后从他的下一个索引处开始遍历数组，遍历得到的数组的每一个元素都和这个值进行异或，结果再赋给这个值，遍历结束后返回这个值即可。
1.3 代码演示
- Map集合：
public int singleNumber(int[] nums) { Map<Integer,Integer> map = new HashMap<>(); //map集合中的键是查的数字，值是数字出现的次数 for(Integer num : nums) { Integer count = map.get(num); count = count == null ? 1 : ++count; map.put(num,count); } for (Integer num : map.keySet()) { int count = map.get(num); if (count == 1) { return num; } } return -1; }
- 异或：
public int singleNumber(int[] nums) { int result = nums[0]; if (nums.length > 1) { for (int i = 1; i < nums.length; i++) { result = result ^ nums[i]; } } return result; }
二、多数元素
2.1 题目描述
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
2.2 思路分析
与上一道题类似，也是通过使用Map集合将数组中的数字作为键存储，这个数字出现的次数作为值存储，将整个数组遍历按这个键值对的方式存储，最后再遍历这个集合判断哪个数字对应的值大于数组长度的½：
- 创建一个Map集合，遍历数组得到数组的每一个数字，根据这个数字作为map集合获取值的参数得到一个整型值赋给一个整型变量，判断这个变量的值是否存在，若不存在，则将该值默认赋值为1表示该数字出现一次，否则该数字自增1，表示该数字多次出现，遍历完数字后，就收集到了每个数字出现的次数，遍历Map集合，得到每个数字的值判断其是否大于数组长度的½，若存在这个数字，直接返回该数字即可。
2.3 代码演示
public int majorityElement(int[] nums) { //利用map排序 Map<Integer,Integer> map = new HashMap<>(); for (Integer num : nums) { Integer count = map.get(num); count = count == null ? 1 : ++count; map.put(num,count); } for (Integer num : map.keySet()) { int count = map.get(num); if (count > (nums.length/2)) { return num; } } return -1; }
三、环形链表 II
3.1 题目描述
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改链表。
3.2 思路分析
这个算是环形链表判断的进阶版，是要返回环的入口节点所对应的索引值，我的思路还是利用快慢指针，先将入环节点找到，再定义一个新的节点指向链表的头，新节点从链表头开始与入环处节点同时遍历，当两个节点相遇时，新节点就可以作为入环节点的索引返回：
- 当链表为空或者链表的第二个节点为空时，返回空，表示没有环
- 链表不为空时，定义两个指针均指向链表头，当快指针不为空时，进入循环，此时，慢指针指向它的下一个节点，当快指针的下一个节点不为空时，快指针指向它的下一个节点的下一个节点（比慢指针多走一步），当快指针的下一个节点为空时，直接返回空（表示没有环），当快指针和慢指针相遇时，此时的快（或慢）指针即为入环节点，定义一个节点指向链表头结点，当新节点与此时的慢指针不相等时，开始循环，每次各走一步，当两个节点相遇时，新指针就是入环节点的索引，返回即可。
3.3 代码演示
public ListNode detectCycle(ListNode head) { if (head == null || head.next == null) { return null; } //定义快慢指针 ListNode fast = head; ListNode slow = head; while(fast != null) { slow = slow.next; if(fast.next != null) { fast = fast.next.next; } else { return null; } if (fast == slow) { ListNode ptr = head; while(ptr != slow) { ptr = ptr.next; slow = slow.next; } return ptr; } } return null; }
四、两数相加
4.1 题目描述
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
4.2 思路分析
直接分析代码的逻辑，这道题的实现是将两个链表中节点的值相加，最后得到一个新的链表，新链表对应的值是两个旧链表值的和：
- 定义两个节点指针分别表示新链表的头和尾，初始时均为空，定义一个整型变量作为进位节点的值，当有链表不为空时，进入循环，定义整型变量记录非空节点的值，将两个链表的值与进位值相加得到一个总数，当新链表的头为空时，将新链表的头和尾军指向一个值为总数模10得到的余数的节点，然后更新进位值为总数除以10得到的商（向下取整），当两个链表不为空时继续遍历两个链表，进入第二次循环，记录非空链表的节点值，记录总数（两个节点值+进位值），第二次循环新链表的头不为空，则将新链表的尾的下一个节点指向一个值为总数模10得到的余数的节点，再将尾指向尾的下一个节点，更新进位值为总数除以10得到的商（向下取整），继续遍历链表，当两个链表都遍历完时，还需要判断进位值是否大于0，若大于0，则将新链表的尾的下一个节点指向值为进位值的新节点，再将为指向尾的下一个节点，最后返回新链表的头。
4.3 代码演示
public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode head = null; ListNode tail = null; //定义进位节点值 int carry = 0; //当有一个链表不为空时，进入循环 while(l1 != null || l2 != null) { //记录非空链表的节点值 int n1 = l1 != null ? l1.val : 0; int n2 = l2 != null ? l2.val : 0; //记录总数 int sum = n1 + n2 + carry; if(head == null) { head = tail = new ListNode(sum%10); } else { tail.next = new ListNode(sum%10); tail = tail.next; } //更新carry的值 carry = sum / 10; //当链表不为空时，继续遍历两个链表 if(l1 != null) { l1 = l1.next; } if(l2 != null) { l2 = l2.next; } } if(carry > 0) { tail.next = new ListNode(carry); tail = tail.next; } return head; }
