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

精选留言(98)

• 

  李皮皮皮皮皮

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

  2019-02-04

  

   38
• 

  Jerry银银

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

  2019-02-05

  

   34
• 

  Smallfly

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

  2019-02-05

   2

   26
• 

  fancyyou

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

  2019-02-05

  

   15
• 

  abner

  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

   3

   4
• 

  _CountingStars

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

  

   4
• 

  峰

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

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

  2019-02-05

  

   4
• 

  abner

  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-02-13

  

   3
• 

  未来的胡先森

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

  2019-02-16

  

   2
• 

  kai

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

  2019-02-11

  

   2
• 

  kai

  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-11

  

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

  2019-02-08

  

   2
• 

  William

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

  

   2
• 

  赵菁垚

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

  作者回复: 也考的

  2019-08-08

  

   1
• 

  神盾局闹别扭

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

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

  2019-02-18

  

   1
• 

  Ben

  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-14

  

   1
• 

  hopeful

  //单链表反转（带头结点）
  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("单链表反转成功");
  }
  }

  2019-02-13

  

   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。

  2019-02-12

  

   1
• 

  Sharry

  链表篇
  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-12

  

   1