精选留言(110)

• 
  Jerry银银

  2019-02-05

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

  

  126
• 
  李皮皮皮皮皮

  2019-02-04

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

  

  61
• 
  Smallfly

  2019-02-05

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

  展开

  共 5 条评论

  50
• 
  fancyyou

  2019-02-05

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

  共 1 条评论

  21
• 
  菜菜

  2019-02-06

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

  

  7
• 
  Abner

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

  展开

  共 1 条评论

  6
• 
  寒溪

  2019-10-31

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

  

  4
• 
  William

  2019-02-06

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

  

  4
• 
  Abner

  2019-02-05

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

  展开

  共 4 条评论

  4
• 
  mgxian

  2019-02-05

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

  展开

  

  4
• 
  峰

  2019-02-05

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

  展开

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

  

  4
• 
  kai

  2019-02-11

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

  展开

  

  3
• 
  kai

  2019-02-11

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

  展开

  

  3
• 
  纯洁的憎恶

  2019-02-08

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

  展开

  

  3
• 
  未来的胡先森

  2019-02-16

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

  展开

  

  2
• 
  Ben

  2019-02-14

  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。

  

  2
• 
  赵菁垚

  2019-08-08

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

  作者回复: 也考的

  

  1
• 
  神盾局闹别扭

  2019-02-18

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

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

  

  1
• 
  hopeful

  2019-02-13

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

  展开

  

  1
• 
  Neo_Zhang

  2019-02-12

  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。

  

  1