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

精选留言

• 
  Jerry银银

  2019-02-05 11:11:12

  早上起来拿出电脑，准备做题。
  老妈说：今天就别工作了，玩一天吧，啥也别干，啥也别想。
  我说：不行呀，老师布置了题目，必须得做呀。
  老妈说：大过年的老师还在工作，真不容易，替我向你老师说声：🔥🔥新年好！！！
• 
  李皮皮皮皮皮

  2019-02-04 21:09:26

  感谢分享，虽然工作很忙，每天下班就不想动了。但是还是要不断克服自己。数据结构和算法的重要性可能在面试的时候才能深刻感悟。如果平时多下点功夫，结果可能会大不一样。前面很多期因为各种原因没有跟上，庆幸的是后面慢慢追上了。现在养成每天做一道算法题的习惯。每天装着一道算法题在脑子里。这感觉其实也不错，不是任务，感觉像是习惯😄
• 
  Smallfly

  2019-02-05 09:58:25

  哈哈，被提名了，谢谢老师。
  
  有兴趣的同学可以把你的答案分享到 Github: https://github.com/iostalks/Algorithms
  
  有问题也可以在 issue 中一起讨论。
  
  新的一年跟大家一起进步，一起流弊。
• 
  fancy

  2019-02-05 10:29:24

  新年好！
  leetcode的题都做过了😁。
• 
  菜菜

  2019-02-06 10:35:47

  大小固定的有序数组，支持增删改：既然有序，则查询操作都可以用二分查询。增加操作，找到第一个大于新数据的值的位置，从最后一个有效数据往后移一个位置，目的是为了给新数据腾位置，然后插入。删除操作：找到第一个等于要删除的数据的值，然后将其后面的数据依次向前挪一个位置。改操作，查询再修改。要注意临界条件和找不到数据，以及数组满等情况。
• 
  Abner

  2019-02-13 01:06:13

  java实现一个动态扩容的数组（扩容2倍）
  代码如下:
  package array;
  
  public class DynamicArray {
  
  private String[] data;
  private int count;
  private int size;
  
  public DynamicArray(int capacity) {
  data = new String[capacity];
  count = 0;
  size = capacity;
  }
  
  public String[] expand(String[] data) {
  if (count >= size) {
  String[] newArray = new String[this.size * 2];
  this.size = this.size * 2;
  for (int i = 0;i < count;i++) {
  newArray[i] = this.data[i];
  }
  return newArray;
  } else {
  return this.data;
  }
  }
  
  public boolean append(String item) {
  if (count >= size) {
  this.data = expand(this.data);
  }
  this.data[count] = item;
  count++;
  return true;
  }
  
  public void printAll() {
  for (int i = 0;i < count;i++) {
  System.out.print(data[i] + " ");
  }
  System.out.println();
  }
  
  public static void main(String[] args) {
  DynamicArray dynamicArray = new DynamicArray(5);
  for (int i = 0;i < dynamicArray.size;i++) {
  dynamicArray.data[i] = "This value is " + i;
  dynamicArray.count++;
  }
  dynamicArray.append("This value is 5");
  System.out.println("Now the size of data is " + dynamicArray.size);
  dynamicArray.printAll();
  }
  
  }
  
• 
  寒溪

  2019-10-31 11:30:28

  请问答案在哪里公布？好对比老师的实现，看一下自己的实现不足点在哪里。
• 
  William

  2019-02-06 16:23:10

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

  作者回复

  感谢您参与春节七天练的活动，为了表彰你在活动中的优秀表现，赠送您99元专栏通用阅码，我们会在3个工作日之内完成礼品发放，如有问题请咨询小明同学，微信geektime002。

  2019-02-22 11:09:50

• 
  Abner

  2019-02-05 21:56:58

  Java语言实现一个大小固定的有序数组，支持动态增删改操作
  代码如下:
  public class Array {
  private String[] data;
  private int count;
  privvate int size;
  public Array(int capacity) {
  data = new String[capacity];
  count = 0;
  size = capacity;
  }
  public boolean insert(int index, String value) {
  if (count >= size) {
  return false;
  }
  if (index < 0 || index > count) {
  return false;
  }
  for (int i = count - 1;i >= index;i--) {
  data[i+1] = data[i];
  }
  data[index] = value;
  count++;
  }
  public String delete(int index, String value) {
  if (count == 0) {
  return false;
  }
  if (index < 0 || index >count) {
  return false;
  }
  value = data[index];
  for (int i = index;i <= count - 1;i++) {
  data[i - 1] = data[i];
  }
  count--;
  return value;
  }
• 
  mgxian

  2019-02-05 19:51:37

  合并有序数组 go 语言实现
  package main
  
  import "fmt"
  
  func mergeOrderedArray(a, b []int) (c []int) {
  i, j, k := 0, 0, 0
  mergedOrderedArrayLength := len(a) + len(b)
  c = make([]int, mergedOrderedArrayLength)
  for {
  if i >= len(a) || j >= len(b) {
  break
  }
  
  if a[i] <= b[j] {
  c[k] = a[i]
  i++
  } else {
  c[k] = b[j]
  j++
  }
  k++
  }
  
  for ; i < len(a); i++ {
  c[k] = a[i]
  k++
  }
  
  for ; j < len(b); j++ {
  c[k] = a[j]
  k++
  }
  
  return
  }
  
  func main() {
  a := []int{1, 3, 5, 7, 9, 10, 11, 13, 15}
  b := []int{2, 4, 6, 8}
  fmt.Println("ordered array a: ", a)
  fmt.Println("ordered array b: ", b)
  fmt.Println("merged ordered array: ", mergeOrderedArray(a, b))
  }
  
• 
  峰

  2019-02-05 10:23:51

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

  作者回复

  感谢您参与春节七天练的活动，为了表彰你在活动中的优秀表现，赠送您99元专栏通用阅码，我们会在3个工作日之内完成礼品发放，如有问题请咨询小明同学，微信geektime002。

  2019-02-22 10:54:34

• kai

  2019-02-11 10:12:52

  3. 实现求链表的中间结点
  public class FindMidNode {
  
  // 1. T(n) = O(2*n) 遍历2次
  public static Node findMidNode(Node head) {
  if (head == null) {
  return null;
  }
  
  int len = 0;
  Node p = head;
  
  while(p != null) {
  len++;
  p = p.next;
  }
  
  p = head;
  for (int i = 0; i < len/2; i++) {
  p = p.next;
  }
  
  return p;
  }
  
  // 2. T(n) = O(n) 遍历1次
  // 快慢指针法
  public static Node findMidNodeFast(Node head) {
  if (head == null) {
  return null;
  }
  
  Node fast = head;
  Node slow = head;
  
  while (fast != null && fast.next != null) {
  fast = fast.next.next;
  slow = slow.next;
  }
  
  return slow;
  }
  
  
  public static Node createNode(int value) {
  return new Node(value, null);
  }
  
  public static class Node {
  public int data;
  public Node next;
  
  public Node(int data, Node next) {
  this.data = data;
  this.next = next;
  }
  }
  }
  
  4. Linked List Cycle I（环形链表）
  /**
  * 141. Linked List Cycle
  * https://leetcode.com/problems/linked-list-cycle/
  */
  public class LinkedListCycle {
  public boolean hasCycle(ListNode head) {
  if (head == null || head.next == null) {
  return false;
  }
  
  ListNode fast = head;
  ListNode slow = head;
  
  while (fast != null && fast.next != null) {
  fast = fast.next.next;
  slow = slow.next;
  if (fast == slow) return true;
  }
  
  return false;
  }
  
  public static class ListNode {
  int val;
  ListNode next;
  ListNode(int x) { val = x;}
  }
  }
• kai

  2019-02-11 10:10:13

  1. 实现单链表反转：
  /**
  * 206. Reverse Linked List
  * https://leetcode.com/problems/reverse-linked-list/
  */
  public class ReverseList {
  public ListNode reverseList(ListNode head) {
  if (head == null || head.next == null) return head;
  
  ListNode pre = null;
  ListNode next = null;
  
  while (head != null) {
  next = head.next;
  head.next = pre;
  pre = head;
  head = next;
  }
  
  return pre;
  }
  
  public static class ListNode {
  int val;
  ListNode next;
  ListNode(int x) {
  this.val = val;
  }
  }
  }
  
  2. 实现两个有序的链表合并为一个有序链表
  /**
  * 21. Merge Two Sorted Lists
  * https://leetcode.com/problems/merge-two-sorted-lists/
  */
  public class Merge2SortedLists {
  public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
  if (l1 == null) return l2;
  if (l2 == null) return l1;
  
  // 利用哨兵（前哨节点）简化实现难度
  ListNode outpost = new ListNode(-1);
  ListNode temp = outpost;
  
  while (l1 != null && l2 != null) {
  if (l1.val <= l2.val) {
  temp.next = l1;
  l1 = l1.next;
  } else {
  temp.next = l2;
  l2 = l2.next;
  }
  
  temp = temp.next;
  }
  
  if (l1 == null) {
  temp.next = l2;
  }
  
  if (l2 == null) {
  temp.next = l1;
  }
  
  return outpost.next;
  }
  
  public ListNode mergeTwoListsRecur(ListNode l1, ListNode l2) {
  if (l1 == null) return l2;
  if (l2 == null) return l1;
  if (l1.val < l2.val) {
  l1.next = mergeTwoListsRecur(l1.next, l2);
  return l1;
  } else {
  l2.next = mergeTwoListsRecur(l1, l2.next);
  return l2;
  }
  }
  
  public static class ListNode {
  int val;
  ListNode next;
  ListNode(int x) { val = x;}
  }
  }
  
  
  
• 
  纯洁的憎恶

  2019-02-08 16:08:32

  1.Three Sum：暴力匹配三元组，三层循环结束后打印保存三元组的数组即可，时间复杂度O（n^3），空间复杂度O（n）。简化一下，为减少比较次数先排序。外层循环i遍历数组，内层循环从数组两头元素（s、t）开始考察，找出使num【s】+num【t】=-num【i】的s和t，若大了t- -，若小了s++（内层要避开i）s大于等于t则匹配失败。这样两层循环就可以了，时间复杂度O（n^2）。
  
  2.Majority Element：重点在于统计每个元素出现次数，可以先排序，然后顺序计算出每个数的出现次数，与阈值比较，大于则输出，时间复杂度O（nlogn）。也可以采用散列表，把每个元素存入散列表，并记录出现次数，最后把出现次数超过阈值的元素输出即可，时间复杂度O（n），空间复杂度O（n）。
  
  3.Missing Positive：本来想用散列表，发现要求时间复杂度O（n），空间复杂度为常量，有点捉急。只能从原数组上做文章。假设数组A长度为n，若i为1到n的正整数，若i存在于A中，我们就把它的位置调整到A【i-1】处，这样通过A【i】是否为i+1即可知道i+1是否在数组中。那么A中不满足上述条件的最小下标+1即为缺失的最小正整数值。
  
  4. Linked List Cycle I（环形链表）：用图的拓扑排序算法可以，但是要统计顶点出入度，空间复杂度无法达到O（1）。那可以用快慢指针，*fast以*slow的两倍速前进，如果fast和slow重合则说明有环。
  
  5. Merge k Sorted Lists（合并 k 个排序链表）：两两硬生生合并，时间复杂度应该是O（kN），再高级的方法想不出来。ps：如果可以抛弃原来的链表，那么新建一个合并后链表的时间复杂度可以是O（N）吧？N是k个链表的总长。
• 
  未来的胡先森

  2019-02-16 11:12:05

  求众数
  解题思路：将数组排序，统计每个数字出现的次数，当满足众数条件时返回。时间复杂度 nlogn
  
  int compare(const void *a, const void *b)
  {
  return (*(int*)a - *(int*)b);
  }
  int majorityElement(int* nums, int numsSize) {
  qsort(nums,numsSize,sizeof(int), compare);
  int num = nums[0],flag=numsSize>>1,count=1;
  for (int i = 1; i < numsSize; i++)
  {
  if (nums[i] != num)
  {
  num = nums[i]; count = 1;
  }
  else
  {
  count++;
  }
  if (count > flag)
  break;
  }
  return num;
  }
  更优解
  
  数组元素为奇数个，众数数量大于半数，所以相互抵消后最后剩余的一定为众数，时间复杂度 O(n)
  
  int majorityElement(int* nums, int numsSize)
  {
  int count = 1,num=nums[0];
  for (int i = 1; i < numsSize; i++)
  if (count == 0 || num == nums[i])
  {
  count++; num = nums[i];
  }
  else
  count--;
  return num;
  }
• 
  Ben

  2019-02-14 17:57:44

  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

  作者回复

  感谢您参与春节七天练的活动，为了表彰你在活动中的优秀表现，赠送您10元无门槛优惠券，我们会在3个工作日之内完成礼品发放，如有问题请咨询小明同学，微信geektime002。

  2019-02-22 11:12:16

• 
  acqierement

  2019-02-05 11:28:51

  自己总结了链表的部分算法，链表算是很简单的数据结构了，只要你心里有一个个节点的概念，必要时画图看一下还是很简单的。
  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;
  }

  作者回复

  感谢您参与春节七天练的活动，为了表彰你在活动中的优秀表现，赠送您99元专栏通用阅码，我们会在3个工作日之内完成礼品发放，如有问题请咨询小明同学，微信geektime002。

  2019-02-22 10:58:02

• 
  赵菁垚

  2019-08-08 15:43:35

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

  作者回复

  也考的

  2019-08-09 06:43:46

• 
  神盾局闹别扭

  2019-02-18 20:11:44

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

  作者回复

  运营同学稍后会联系获奖同学哈

  2019-02-18 22:12:48

• 
  hopeful

  2019-02-13 17:59:00

  //单链表反转（带头结点）
  void reverse(struct node* head){
  struct node* L;
  struct node* p;
  struct node* p2;
  struct node* p3;
  L = head->next;
  if(head == NULL){
  printf("链表未创建");
  }else if(L->next==NULL){
  printf("单链表只有一个节点，无需反转");
  return;
  }else if(L->next->next == NULL){
  head->next = L->next;
  head->next->next = L;
  L->next = NULL;
  printf("单链表反转成功");
  }else{
  p = L;
  p2 = L->next;
  p3 = L->next->next;
  while(p3!=NULL){
  p2->next = p;
  p = p2;
  p2 = p3;
  p3 = p3->next;
  }
  p2->next = p;
  L->next = NULL;
  head->next = p2;
  printf("单链表反转成功");
  }
  }