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

精选留言(87)

• 
  李皮皮皮皮...

  2019-02-04

   24

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

  展开
• 
  Smallfly

  2019-02-05

   19

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

  展开
• 
  Jerry银银

  2019-02-05

   18

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

  展开
• 
  fancyyou

  2019-02-05

   10

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

  2019-02-05

   4

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

  展开
• 
  峰

  2019-02-05

   4

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

  展开

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

• 
  _CountingS...

  2019-02-05

   3

  合并有序数组 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-16

   2

  求众数
  解题思路：将数组排序，统计每个数字出现的次数，当满足众数条件时返回。时间复杂度 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;
  }

  展开
• abner

  2019-02-13

   2

  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();
      }
    
  }
  

  展开
• 
  kai

  2019-02-11

   2

  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

   2

  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

   2

  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个链表的总长。

  展开
• 
  William

  2019-02-06

   2

  特地新开了一个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-06

   2

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

  展开
• 
  神盾局闹别...

  2019-02-18

   1

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

  展开

  编辑回复: 运营同学稍后会联系获奖同学哈

• 
  Ben

  2019-02-14

   1

  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。

• 
  Zoctopus

  2019-02-12

   1

  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
  }
  

  展开

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

• 
  Sharry

  2019-02-12

   1

  链表篇
  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;
  }

  展开

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

• 
  神盾局闹别...

  2019-02-07

   1

  
  实现两个有序的链表合并为一个有序链表：
  Node *MergeNode(Node *head1, Node *head2)
  {
      if (head1 == NULL)
          return head2;
      if (head2 == NULL)
          return head1;
      stu *pMergedHead;
      if (head1->age < head2->age)
      {
          pMergedHead = head1;
          pMergedHead->next = MergeNode(head1->next, head2);
      }
      else
      {
          pMergedHead = head2;
          pMergedHead->next = MergeNode(head1, head2->next);
      }
      return pMergedHead;
  }

  展开
• 
  ALAN

  2019-02-07

   1

  linkedlist answer:
  import java.util.ArrayList;
  import java.util.List;
  
  /**
   *
   * @author root alan
   *
   */
  public class List1 {
  
      Node tail;
      Node head;
  
      public void addOneWay(int value) {
          if (head == null) {
              head = new Node(value);
              tail = head;
          } else {
              Node node = new Node(value);
              tail.next = node;
              tail = node;
          }
      }
  
      public void deleteOneWay(int value) {
          Node node = head;
          Node prev = head;
          while (node.value != value) {
              prev = node;
              node = node.next;
  
          }
          if (node == head)
              head = head.next;
          else if (node != tail)
              prev.next = node.next;
          else {
              tail = prev;
              prev.next = null;
          }
  
      }
  
  
  
      public Node reverse(Node node) {
          Node prev = null;
          Node now = node;
          while (now != null) {
              Node next = now.next;
              now.next = prev;
              prev = now;
              now = next;
          }
  
          return prev;
      }
  
      public Node middle() {
          Node nd = head;
          Node nd2 = head;
          while (nd2 != null) {
              nd = nd.next;
              nd2 = nd2.next.next;
          }
          return nd;
      }
  
  }
  
  class Node {
      Node prev;
      Node next;
      int value;
  
      public Node(int ele) {
          value = ele;
      }
  }
  

  展开