## leetcode Find Median from Data Stream

### leetcode Find Median from Data Stream

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples:
`[2,3,4]` , the median is `3`

`[2,3]`, the median is `(2 + 3) / 2 = 2.5`

Design a data structure that supports the following two operations:

• void addNum(int num) – Add a integer number from the data stream to the data structure.
• double findMedian() – Return the median of all elements so far.

For example:

• findMedian() -> 1.5
• findMedian() -> 2

## leetcode Nim Game

### leetcode Nim Game

You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.

Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.

For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.

## leetcode Word Pattern

### leetcode Word Pattern

Given a `pattern` and a string `str`, find if `str` follows the same pattern.

Examples:

1. pattern = `"abba"`, str = `"dog cat cat dog"` should return true.
2. pattern = `"abba"`, str = `"dog cat cat fish"` should return false.
3. pattern = `"aaaa"`, str = `"dog cat cat dog"` should return false.
4. pattern = `"abba"`, str = `"dog dog dog dog"` should return false.

Notes:

1. Both `pattern` and `str` contains only lowercase alphabetical letters.
2. Both `pattern` and `str` do not have leading or trailing spaces.
3. Each word in `str` is separated by a single space.
4. Each letter in `pattern` must map to a word with length that is at least 1.

## leetcode Find the Duplicate Number

### leetcode Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Note:

1. You must not modify the array (assume the array is read only).
2. You must use only constant, O(1) extra space.
3. Your runtime complexity should be less than `O(n2)`.
4. There is only one duplicate number in the array, but it could be repeated more than once.

• push
• pop
• 堆的创建及其他应用

## 算法复习 – 图论 最短路和最小生成树

• 最短路径
• dijkstra
• SPFA
• floyd
• 用SPFA解决差分约束
• 最小生成树MST
• prim
• kruskal
• 次小生成树
• 二分图
• 最大匹配和最小覆盖

## leetcode Graph 图论

• 133 Clone Graph
• 207 Course Schedule
• 210 Course Schedule II

## leetcode 链表

• 依照leetcode定义 自己写的链表创建/打印方法，便于测试
• 19 . Remove Nth Node From End of List
• 21. Merge Two Sorted Lists
• 23. Merge k Sorted Lists
• 24. Swap Nodes in Pairs
• 25. Reverse Nodes in k-Group
• 61. Rotate List
• 86. Partition List
• 138 . Copy List with Random Pointer
• 141 . Linked List Cycle
• 142. Linked List Cycle II
• 143 . Reorder List
• 147. Insertion Sort List
• 148. Sort List
• 160. Intersection of Two Linked Lists
• 203 . Remove Linked List Elements
• 206 . Reverse Linked List
• 234 . Palindrome Linked List
• 237 . Delete Node in a Linked List

update:2015-7-14

• add a 203 solution code:
• using recursion and reference to delete linklist node which value equals x
• 单项链表递归删除，使用引用

## leetcode 数学

• 7. Reverse Integer
• 9. Palindrome Number
• 43. Multiply Strings
• 50. Pow(x, n)
• 65 . Valid Number
• 66. Plus One
• 149 . Max Points on a Line
• 166 . Fraction to Recurring Decimal
• 168 . Excel Sheet Column Title
• 171. Excel Sheet Column Number
• 172. Factorial Trailing Zeroes
• 179 . Largest Number
• 224. Basic Calculator
• 227 . Basic Calculator II
• 233 . Number of Digit One
• 273. Integer to English Words

## leetcode 动态规划（DP）

• 53. Maximum Subarray
• 62. Unique Paths
• 63. Unique Paths II
• 64. Minimum Path Sum
• 70. Climbing Stairs
• 72. Edit Distance
• 87. Scramble String
• 91 . Decode Ways
• 97. Interleaving String
• 115 Distinct Subsequences
• 120. Triangle
• 139. Word Break
• 140. Word Break II
• 152. Maximum Product Subarray
• 174 . Dungeon Game
• 198. House Robber
• 213 . House Robber II
• 221 . Maximal Square
• 712. Minimum ASCII Delete Sum for Two Strings
• 718. Maximum Length of Repeated Subarray
• 799. Champagne Tower
• 818. Race Car