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:

  • add(1)
  • add(2)
  • findMedian() -> 1.5
  • add(3)
  • findMedian() -> 2

Continue reading


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.

Continue reading


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.

Continue reading


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.

Continue reading


leetcode 链表

本次题解包括:

  • 依照leetcode定义 自己写的链表创建/打印方法,便于测试
  • 2. Add Two Numbers
  • 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
  • 817. Linked List Components

update:2015-7-14

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

Continue reading


leetcode 数学

本次题解包括

  • 7. Reverse Integer
  • 9. Palindrome Number
  • 43. Multiply Strings
  • 50. Pow(x, n)
  • 65 . Valid Number
  • 66. Plus One
  • 67. Add Binary
  • 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
  • 258. Add Digits
  • 273. Integer to English Words

Continue reading


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

Continue reading