angryhen/code_with_py

编程任务

All Tasks

Task 1：数组和链表（2天）

时间：2019-08-03 21:00 - 2019-08-05 21:00 讨论&CR时间: 2019-08-05 21:00 - 2019-08-05 22:30

• ** **【数组】
  • 实现一个支持动态扩容的数组，支持增删改操作
  • 实现两个有序数组合并为一个有序数组
  • 学习哈希表**，并完成leetcode上的两数之和(1)及Happy Number(202)！(要求全部用哈希**实现！)（选做）（注意：在第四天会进行继续学习）
• 【链表】
  • 实现单链表、循环链表、双向链表，支持增删操作
  • 实现单链表反转
  • 实现两个有序的链表合并为一个有序链表
  • 实现求链表的中间结点
• 【对应的 LeetCode 练习题】
  • Three Sum（求三数之和）
    • 英文版：https://leetcode.com/problems/3sum/
    • 中文版：https://leetcode-cn.com/problems/3sum/
  • Majority Element（求众数）
    • 英文版：https://leetcode.com/problems/majority-element/
    • 中文版：https://leetcode-cn.com/problems/majority-element/
  • Missing Positive（求缺失的第一个正数）[作为可选]
    • 英文版：https://leetcode.com/problems/first-missing-positive/
    • 中文版：https://leetcode-cn.com/problems/first-missing-positive/
  • Linked List Cycle I（环形链表）
    • 英文版：https://leetcode.com/problems/linked-list-cycle/
    • 中文版：https://leetcode-cn.com/problems/linked-list-cycle/
  • Merge k Sorted Lists（合并 k 个排序链表）
    • 英文版：https://leetcode.com/problems/merge-k-sorted-lists/
    • 中文版：https://leetcode-cn.com/problems/merge-k-sorted-lists/

**~~Task 2： 栈 + 队列 + 递归 (4天) ~~**

时间：2019-08-05 21:00 - 2019-08-09 21:00

• 【栈】
  • 用数组实现一个顺序栈
  • 用链表实现一个链式栈
  • 编程模拟实现一个浏览器的前进、后退功能（选做）
• 【队列】
  • 用数组实现一个顺序队列
  • 用链表实现一个链式队列
  • 实现一个循环队列
• 【递归】
  • • 编程实现斐波那契数列求值 f(n)=f(n-1)+f(n-2)
  • • 编程实现求阶乘 n!
  • • 编程实现一组数据集合的全排列
• 【对应的 LeetCode 练习题】
  • 栈
    • Valid Parentheses（有效的括号）
      • 英文版：https://leetcode.com/problems/valid-parentheses/
      • 中文版：https://leetcode-cn.com/problems/valid-parentheses/
    • Longest Valid Parentheses（最长有效的括号）
      • 英文版：https://leetcode.com/problems/longest-valid-parentheses/
      • 中文版：https://leetcode-cn.com/problems/longest-valid-parentheses/
    • Evaluate Reverse Polish Notatio（逆波兰表达式求值）
      • 英文版：https://leetcode.com/problems/evaluate-reverse-polish-notation/
      • 中文版：https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/
  • 队列
    • Design Circular Deque（设计一个双端队列）
      • 英文版：https://leetcode.com/problems/design-circular-deque/
      • 中文版：https://leetcode-cn.com/problems/design-circular-deque/
    • Sliding Window Maximum（滑动窗口最大值）
      • 英文版：https://leetcode.com/problems/sliding-window-maximum/
      • 中文版：https://leetcode-cn.com/problems/sliding-window-maximum/
  • 递归
    • Climbing Stairs（爬楼梯）
      • 英文版：https://leetcode.com/problems/climbing-stairs/
      • 中文版：https://leetcode-cn.com/problems/climbing-stairs/

Task 3：排序 + 二分查找 (3天)

时间：2019-08-09 21:00 - 2019-08-12 21:00

• 【排序】
  • 实现归并排序、快速排序、插入排序、冒泡排序、选择排序、堆排序（完成leetcode上的返回滑动窗口中的最大值(239)，这是上一期第三天的任务进行保留（涉及队列可以对第二天进行整理复习））
  • 编程实现 O(n) 时间复杂度内找到一组数据的第 K 大元素
• 【二分查找】
  • 实现一个有序数组的二分查找算法
  • 实现模糊二分查找算法（比如大于等于给定值的第一个元素）
• 【对应的 LeetCode 练习题】
  • Sliding Window Maximum（滑动窗口最大值）
    • 英文版：https://leetcode.com/problems/sliding-window-maximum/
    • 中文版：https://leetcode-cn.com/problems/sliding-window-maximum/
  • Sqrt(x) （x 的平方根）
    • 英文版：https://leetcode.com/problems/sqrtx/
    • 中文版：https://leetcode-cn.com/problems/sqrtx/

~~Task 4：散列表(哈希表) + 字符串 (~~~~4~~~~天) ~~

时间：2019-08-12 21:00 - 2019-08-16 21:00

• 【散列表（哈希表）】
  • 实现一个基于链表法解决冲突问题的散列表
  • 实现一个 LRU 缓存淘汰算法
• 【字符串】
  • 实现一个字符集，只包含 a～z 这 26 个英文字母的 Trie 树
  • 实现朴素的字符串匹配算法
• 【对应的 LeetCode 练习题】
  • 两数之和
    • 英文版：https://leetcode.com/problems/two-sum/
    • 中文版：https://leetcode-cn.com/problems/two-sum/
  • Reverse String （反转字符串）
    • 英文版：https://leetcode.com/problems/reverse-string/
    • 中文版：https://leetcode-cn.com/problems/reverse-string/
  • Reverse Words in a String（翻转字符串里的单词）
    • 英文版：https://leetcode.com/problems/reverse-words-in-a-string/
    • 中文版：https://leetcode-cn.com/problems/reverse-words-in-a-string/
  • String to Integer (atoi)（字符串转换整数 (atoi)）[作为可选]
    • 英文版：https://leetcode.com/problems/string-to-integer-atoi/
    • 中文版：https://leetcode-cn.com/problems/string-to-integer-atoi/

Task 5：二叉树 + 堆 (2天)

时间：2019-08-16 21:00 - 2019-08-18 21:00

• 【二叉树】
  • 实现一个二叉查找树，并且支持插入、删除、查找操作
  • 实现查找二叉查找树中某个节点的后继、前驱节点
  • 实现二叉树前、中、后序以及按层遍历
  • 并完成leetcode上的验证二叉搜索树(98)及二叉树 层次遍历(102,107)！（选做）（保留往期第四天任务）注：这个跟下面的习题有重复
• 【堆】
  • 实现一个小顶堆、大顶堆、优先级队列
  • 实现堆排序
  • 利用优先级队列合并 K 个有序数组
  • 求一组动态数据集合的最大 Top K
  • （选做）第三天堆排序学习（复习）
• 【对应的 LeetCode 练习题】
  • Invert Binary Tree（翻转二叉树）
    • 英文版：https://leetcode.com/problems/invert-binary-tree/
    • 中文版：https://leetcode-cn.com/problems/invert-binary-tree/
  • Maximum Depth of Binary Tree（二叉树的最大深度）
    • 英文版：https://leetcode.com/problems/maximum-depth-of-binary-tree/
    • 中文版：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
  • Validate Binary Search Tree（验证二叉查找树）[作为可选]
    • 英文版：https://leetcode.com/problems/validate-binary-search-tree/
    • 中文版：https://leetcode-cn.com/problems/validate-binary-search-tree/
  • Path Sum（路径总和）
    • 英文版：https://leetcode.com/problems/path-sum/
    • 中文版：https://leetcode-cn.com/problems/path-sum/

Task 6：图 (3天)【当前任务】

时间：2019-08-18 21:00 - 2019-08-21 21:00

• 【图】
  • 实现有向图、无向图、有权图、无权图的邻接矩阵和邻接表表示方法
  • 实现图的深度优先搜索、广度优先搜索
  • 实现 Dijkstra 算法
  • 实现拓扑排序
• 【对应的 LeetCode 练习题】
  • Number of Islands（岛屿的个数）
    • 英文版：https://leetcode.com/problems/number-of-islands/description/
    • 中文版：https://leetcode-cn.com/problems/number-of-islands/description/
  • Valid Sudoku（有效的数独）
    • 英文版：https://leetcode.com/problems/valid-sudoku/
    • 中文版：https://leetcode-cn.com/problems/valid-sudoku/

Task 7：递归 + 回溯 + 分治 + 动态规划 (2天)

时间：2019-08-21 21:00 - 2019-08-23 21:00

• 【递归】
  • 通过LeetCode上【70. 爬楼梯】学习（建议）
• 【回溯】
  • 利用回溯算法求解八皇后问题
  • 利用回溯算法求解 0-1 背包问题
• 【分治】
  • 利用分治算法求一组数据的逆序对个数
• 【动态规划】
  • 0-1 背包问题
  • 最小路径和（详细可看 Minimum Path Sum）
  • 编程实现莱文斯坦最短编辑距离
  • 编程实现查找两个字符串的最长公共子序列
  • 编程实现一个数据序列的最长递增子序列
• 【对应的 LeetCode 练习题】
  • 实战递归：完成Leetcode上的Letter Combinations of a Phone Number(17)及permutations(46)
  • 实战DP：完成0-1背包问题实现(自我实现)及Leetcode上Palindrome Partitioning II(132)
  • Regular Expression Matching（正则表达式匹配）
    • 英文版：https://leetcode.com/problems/regular-expression-matching/
    • 中文版：https://leetcode-cn.com/problems/regular-expression-matching/
  • Minimum Path Sum（最小路径和）
    • 英文版：https://leetcode.com/problems/minimum-path-sum/
    • 中文版：https://leetcode-cn.com/problems/minimum-path-sum/
  • Coin Change （零钱兑换）[作为可选]
    • 英文版：https://leetcode.com/problems/coin-change/
    • 中文版：https://leetcode-cn.com/problems/coin-change/
  • Best Time to Buy and Sell Stock（买卖股票的最佳时机）[作为可选]
    • 英文版：https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
    • 中文版：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
  • Maximum Product Subarray（乘积最大子序列）[作为可选]
    • 英文版：https://leetcode.com/problems/maximum-product-subarray/
    • 中文版：https://leetcode-cn.com/problems/maximum-product-subarray/
  • Triangle（三角形最小路径和）[作为可选]
    • 英文版：https://leetcode.com/problems/triangle/
    • 中文版：https://leetcode-cn.com/problems/triangle/