Skip to content

Latest commit

 

History

History
140 lines (113 loc) · 6.5 KB

zz_coding_index.md

File metadata and controls

140 lines (113 loc) · 6.5 KB
Raw

#zz Coding Summary

##Two Pointers

  1. 两个pointers从头往后走：感觉绝大多数的linked list的题目都涉及到这个操作，当然还有array。这类题目很多时候又可以称为sliding window。
  • Implement strStr()
  • Longest Substring Without Repeating Characters
  • Minimum Window Substring
  • Remove Duplicates from Sorted Array I & II
  • Remove Duplicates from Sorted List I & II
  • Remove Element
  • Remove Nth Node From End of List
  • Reverse Linked Llist II
  • Rotate List
  • Substring with Concatenation of All Words
  • Swap Nodes in Pairs
  1. 两个pointers从两头往中间走：一般面试出现的的都是singly linked list,因此这类题主要是array题。
  • 3Sum
  • 3Sum Closest
  • 4Sum
  • Container With Most Water
  • Sort Colors
  • Trapping Rain Water
  • Two Sum
  • Binary search (will discuss it in a separate section)
  1. 两个pointers控制两个不同的数组或链表：一般出现在跟merge相关的题目上。
  • Add Binary
  • Add Two Numbers
  • Merge Sorted Array
  • Merge Two Sorted Lists
  • Multiply Strings
  • Partition List

##Permutation and Combination ######Permutation

  • 输入没有重复：Permutations, CC150 9.5, PIE Chapter7 Permutations of a String
  • 输入有重复，输出不能有重复：Permutations II
  • Next Permutation: 经典算法，背吧
  • Permutation Sequence: 非常有意思的题目
  • Combination

######纯粹的subset

  • 输入没有重复：Subsets, CC150 9.4, PIE Chapter7 Combinations of a String
  • 输入有重复，输出不能有重复：Subsets II

######需要满足一定要求的组合

  • 一个元素只能取一次(输入没有重复): Combinations
  • 一个元素可以取多次(输入没有重复): Combination Sum, CC150, 9.8
  • 一个元素只能取一次(输入有重复，输出不能有重复）: Combination Sum II
  • Gray Code: 具有subset的序列特点 （考虑CC150 9.4 Solution#2: Combinatorics)

##Binary Search and Divide and Conquer

Binary search非常tricky，虽说道理简单，但是面试的时候却很容易出bug，因此总结一下是必须的。假设i=0,j=A.length-1, 我做了一下LeetCode上的所有binary search的题目，发现了以下几点值得注意。

  • 终止条件不同 i<=j, i<j
  • mid的上下取向不同 i+(j-i)/2, j-(j-i)/2
  • 如何合理分半
  • 分半的时候取=mid, mid-1, or mid+1

Questions

  • Search a 2D Matrix： 这是一道普通的binary search。终止条件i<=j, mid取向i+(j-i)/2, 分半的时候=mid-1 or mid+1。
  • Search for a Range：这道题需要终止条件i<j, mid取向两种都需要用到，分半的时候需要用到=mid。我发现一般＝mid的时候，终止条件往往是i<j,不然会有死循环。

如何合理分半：下边这几道题都很tricky，分半的时候都有各自的特点，很不容易一次写对。需要多多练习和体会。

  • Search in Rotated Sorted Array
  • Search in Rotated Sorted Array II
  • Median of Two Sorted Arrays

还有一个有趣的现象就是很多数学相关的题目也是通过binary search来解决的：

  • Divide Two Integers：这题没做过面试也容易跪
  • Pow(x, n)
  • Sqrt(x)：其实算是一道典型的binary search题目，不过里边包括了几个tricky的地方，很难一次写对

##Linked List 首先LeetCode上几乎所有的Linked list的题目都可以用two pointers来解决，或者会用到two pointers这个基本编程技巧。因此two pointers跟linked list是紧密相关的。因为two pointers以前已经总结过了，就不多讲了。

其次，因为LinkedList和Array/ArrayList一样都具备有List的特性，因此很多题目都出现在了两种数据结构上，或者说很多题目都是可以把这两种数据结构互换的。比如：

  • Add Two Numbers
  • Convert Sorted List to Binary Search Tree
  • Insert Interval
  • Merge Intervals
  • Merge k Sorted Lists
  • Merge Two Sorted Lists
  • Remove Duplicates from Sorted List
  • Remove Duplicates from Sorted List II

第三，LinkedList的题目大多自然而然使用iteration来解决的，但是我发现有些时候iteration比较容易出bug，换成recursion实现更容易。面试的时候万一iteration卡住可以换换recursion的思路。 第四，dummy head非常有用，可以使代码简洁很多，并且容易写bug free的code。这个技巧可以大量使用。

第五，今天做了一遍LinkedList的题目，发现两个地方容易出bug。一是two pointers loop完之后常常会有一个收尾的工作，比如Add Two Numbers需要处理carrier>0的情况。二是在swap了nodes之后，新的tail需要把next置空，不然就出现死循环了。

##Tree

  1. Recursive DFS
  2. Iterative DFS
  3. BFS

有些tree的题目比较tricky一些，但是最终解法还是逃不出这三个套路，所以我觉得面试的时候代码的质量就变得更加的重要了。因为没有什么太多总结的，下边就随便聊一下了。

Leetcode上graph的题目涉及的很少，不过从算法和coding来说DFS，BFS完全适用于tree和graph。因此，把tree的题目练好了，graph的多数题目应该也不会有什么问题才对。当然graph涉及的算法比tree还是要多的，比如shortest path,toposort等等，但是DFS,BFS还是基本中的基本。因此做Leetcode上的tree的题目也相当于练习了graph的题目了。

由于Tree的题目比较多，我感觉一些可以skip掉，如果时间不充裕的话。或者做一遍即可，不需要反复练习。这些题目或者太简单，或者面试不太可能碰到。

  • Balanced Binary Tree
  • Binary Tree Level Order Traversal II
  • Maximum Depth of Binary Tree
  • Minimum Depth of Binary Tree
  • Same Tree
  • Symmetric Tree
  • Unique Binary Search Trees
  • Unique Binary Search Trees II
  • Pre-order, In-order, Post-order traversal 需要会recursive和iterative的两种实现方式。可惜Leetcode上只包含了In-order，有
  • 些遗憾。
  • Tree的serialization/deserialization也是常常被考到的题目，这个Leetcode目前还没有包含，当然套路还是DFS/BFS。
  • LinkedList和Binary Tree相互转换的题目。
  • Convert Sorted List to Binary Search Tree
  • Flatten Binary Tree to Linked List (这题原题在CC150是一道双向链表题，不知道Leetcode上怎么改单向了。双向链表应该更复杂一些，大家要注意一下）

##数据结构

  • Array, ArrayList
  • String, StringBuffer
  • LinkedList
  • HashMap, HashSet
  • Stack and Queue
  • Tree:
  • BT: binary tree
  • BST: binary search tree,
  • Balanced BST (red-black tree): TreeMap, TreeSet
  • Trie: prefix tree
  • Heap: PriorityQueue
  • Grpah

zz Thanks to Peking2 @ http://blog.sina.com.cn/leetcode