春节7天练 | Day 1：数组和链表

特地新开了一个git仓库，https://github.com/Si3ver/LeetCode。刷完5道题，思路大致写一下。1.数组三数之和，时间复杂度是O(n^2)，先排序，外层i遍历数组，内层左右双指针，寻找两数之和 = -nums[i]。 2. 求数组中出现次数大于一半的数字。复杂度O(n)，是利用摩尔投票法。3.求缺失的最小正整数，复杂度O(n)，思路是哈希表统计。4.环形链表用快慢指针。5.合并k个有序链表，用的是两两归并，据说用堆会更快，这个有待补充。

第三题，看这题，我就会想到用快排的思想在一堆数中求第n大。于是乎我就套，先把负数全部移掉，o(n)不影响。然后每轮迭代随机取个数n，比它小的放左边，比他大的放右边。比如说第一轮迭代，左边的数据个数小于n-1那么必然在左边。但这里有个问题是数据是可以重复的，怎么办，想呀想，我就选定n后，开始扫描，如果是1我就放第一个位置，如果是2我就放第二个位置，如果再有1，发现重复了，不用移动了，这样我就能计算小于n大于n的正整数有多少种了，然后就能迭代下去了。当然里面还有些细节，比如如果n很大已超过了数组长度，那说明那个数一定在左边。

class Solution(object): def threeSum(self, nums): """ :type nums: List[int] :rtype: List[List[int]] 通过hash结构缓存去重值及出现的次数 将值按正负区分, 将正负列表中的数字求和, 判断和的相反数是否仍存在于字典中 """ #将输入列表的值作为索引, 对应出现的次数作为新的字典结构的值 dic = {} for ele in nums: if ele not in dic: dic[ele] = 0 dic[ele] += 1 # 存在3个0的特殊情况 if 0 in dic and dic[0] > 2: rst = [[0, 0, 0]] else: rst = [] pos = [p for p in dic if p > 0] neg = [n for n in dic if n < 0] # 若全为正或负值, 不存在和为0的情况 for p in pos: for n in neg: inverse = -(p + n) if inverse in dic: if inverse == p and dic[p] > 1: rst.append([n, p, p]) elif inverse == n and dic[n] > 1: rst.append([n, n, p]) # 去重: 小于负值且大于正值可以排除掉重复使用二者之间的值 elif inverse < n or inverse > p or inverse == 0: rst.append([n, inverse, p]) return rst def majorityElement(self, nums): """ :type nums: List[int] :rtype: int hash反存值和出现的次数 """ #利用字典表反存值:出现的次数 dic = {} for i in nums: if i not in dic: dic[i] = 1 else: dic[i] +=1 #根据列表获取值最大的索引 vs = list(dic.values()) return list(dic.keys())[vs.index(max(vs))] def firstMissingPositiveFast(self, nums): """ :type nums: List[int] :rtype: int """ n = 1 while n in nums: n +=1 return n

王老师，请教您一个问题，想参加NOIP c++考这些算法吗？

加油礼包的福利在哪里领呢？

Three Sum（求三数之和）Go语言： func threeSum(nums []int) [][]int { results := [][]int{} n := len(nums) if n == 0 || n < 3 { return results } sort.Ints(nums) //首先，对数组进行排序 for i := 0; i < n-2; i++ { if i > 0 && nums[i] == nums[i-1] { //如果相邻两个数相等 continue } target := -nums[i] left := i + 1 right := n - 1 for left < right { sum := nums[left] + nums[right] if sum == target { results = append(results, []int{nums[left], nums[right], nums[i]}) left++ right-- for left < right && nums[left] == nums[left-1] { left++ } for left < right && nums[right] == nums[right+1] { right-- } } else if sum > target { right-- } else if sum < target { left++ } } } return results }

链表篇 1. 翻转单链表 /*翻转单链表*/ void reversalList(Node<int>* head) { Node<int>* p = head; Node<int>* prev = NULL; Node<int>* temp = NULL; while (p) { // 1. 保存要遍历的下一个结点 temp = p->next; // 2. 将 node->next 指向前驱结点 p->next = prev; // 3. 更新前驱结点 prev = p; // 4. 更新下一个要遍历的结点 p = temp; } } 2. 将两个有序的单链表合并 /* 合并两个有序链表, 将 list2 合并到 list1 中 */ Node<int>* mergeOrderList(Node<int>* list1, Node<int>* list2) { // 记录 list2 的头结点 Node<int>* head = list2; // 创建哨兵, 用于处理将 list2 中的元素插入到 list1 头结点前面的情况 Node<int>* sentry = new Node<int>(-1); sentry->next = list1; // 记录 list1 要遍历的元素 Node<int>* node = sentry; Node<int>* temp = NULL; while (node->next && head) { if (node->next->data > head->data) { temp = head->next; head->next = node->next; node->next = head; head = temp; } else { node = node->next; } } // 若 list2 的头结点不为 NULL, 则说明 list1 中的元素提前遍历结束了 // 剩下的 list2 中的元素均比 list1 中的大 // 直接将 list1 的尾结点连接到 list2 的首结点即可 if (head) { node->next = head; } // 释放哨兵结点内存 list1 = sentry->next; sentry->next = NULL; delete(sentry); return list1; } 3. 求单链表的中间结点 /* 查询单链表的中间结点 */ template<typename E> Node<E>* findMidNode(Node<E>* head, Node<E>** mid_node) { if (!head) { return NULL; } Node<E>* fast = head; Node<E>* slow = head; while (fast && fast->next && fast->next->next) { // 快指针走两步 fast = fast->next->next; // 慢指针走一步 slow = slow->next; } *mid_node = slow; }

array answer: import java.util.Arrays; public class Array1 { public int n; public int cur; public static int ary[]; //dynamic expand public static int fix[]; //fixed array public Array1(int size) { n=size; ary=new int [n]; } //dynamic expand public void insert(int ele) { if(cur==ary.length) { ary=Arrays.copyOf(ary, ary.length*2); System.out.println("length:"+ary.length); } ary[cur]=ele; cur++; } //fixed array --add public void add(int ele) { if(cur==fix.length) { return; } fix[cur]=ele; cur++; } //fixed array --delete public void delete() { if(cur==-1) return ; fix[cur]=0; cur--; } //fixed array --update public void update(int index,int ele) { if(index>=0 && index<fix.length) fix[index]=ele; } //merge public int[] merge(int[] a,int[] b ) { int[]c =new int[a.length+b.length]; int j=0,k=0; for(int i=0;i<a.length+b.length;i++) { if(j==a.length) { c[i]=b[k]; k++; continue; }else if(k==b.length){ c[i]=a[j]; j++; continue; } if(a[j]<b[k]) { c[i]=a[j]; j++; }else { c[i]=b[k]; k++; } } return c; } }

自己总结了链表的部分算法，链表算是很简单的数据结构了，只要你心里有一个个节点的概念，必要时画图看一下还是很简单的。 1.单链表反转 反转比较简单,就是要有一个先前节点prev和当前节点cur，要有一个临时节点保存cur的下一个节点（cur.next），否则反转之后你就找不到下一个节点了。然后让head指向前一个节点prev。之后继续移动cur和prev节点进行下一次反转 public ListNode reverse(ListNode head) { ListNode prev = null; ListNode cur = head; while(cur != null) { ListNode temp = cur.next; cur.next = prev; prev = cur; cur = temp; } return prev; } 2.两个有序的链表合并 思路就是自己创建一个链表，每次从两个链表头中找到较小的那个节点，接到自己的那个链表中。说着很简单，但还是有很多细节要注意。 public ListNode mergeTwoLists(ListNode l1,ListNode l2) { if (l1 == null) return l2; if (l2 == null) return l1; ListNode head = new ListNode(0); ListNode cur = head; while(l1 != null && l2 != null) { if (l1.val < l2.val) { cur.next = l1; l1 = l1.next; }else { cur.next = l2; l2 = l2.next; } cur = cur.next; } if (l1 == null) cur.next = l2; if (l2 == null) cur.next = l1; return head.next; } 3.求链表的中间结点(如果是偶数，返回中间两个中靠右的那个） 这个问题就很简单了，环的检测也可以用到这种方法。就是用快慢指针，快的前进两步，慢的前进一步，等到快的指针到结尾时，慢的指针就到了中点。 public ListNode findCenter(ListNode head) { ListNode slow = head; ListNode fast = head; while(fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } return slow; }

这些题，我都做了一遍，除了那个“求缺失的第一个正数“没有相处方法，其它的都是自己做出来了。尤其最后那个”合并 k 个排序链表“，其实以前我也看过一次，当时的想法觉得是一个个取出来，然后排序然后再遍历。学完这堂课之后，看完题目，咦，这不是合并两个链表么？哦，合并多个，怎么处理多个问题？好像可以分治归并，嗯，好像是可以。我了个去，就有那种顿塞的感觉，那种开心。谢谢这门课。也谢谢老师，虽然课程里面还有很多没有明白，不过有些数据结构，算法，细细品味，好爽。