326. Power of Three

Given an integer, write a function to determine if it is a power of three.（判断一个数是否是3的次方数，不使用循环和迭代）

由于输入是int，正数范围是0-2^{31，在此范围中允许的最大的3的次方数为3}19=1162261467，那么我们只要看这个数能否被n整除即可。

class Solution(object):
    def isPowerOfThree(self, n):
        """
        :type n: int
        :rtype: bool
        """
        return n > 0 and 1162261467 % n ==0

---

152. Maximum Product Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest product.For example, given the array [2,3,-2,4],the contiguous subarray [2,3] has the largest product = 6
从数组（至少包含一个数字）中找出一个连续的子数组，该子数组的乘积最大。

对于Product Subarray，要考虑到一种特殊情况，即负数和负数相乘：如果前面得到一个较小的负数，和后面一个较大的负数相乘，得到的反而是一个较大的数，如{2，-3，-7}，所以，我们在处理乘法的时候，除了需要维护一个局部最大值，同时还要维护一个局部最小值，由此，可以写出如下的转移方程式：big, small=max(n, n*big, n*small), min(n, n*big, n*small)

class Solution(object):
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        maximum=big=small=nums[0]
        for n in nums[1:]:
            big, small=max(n, n*big, n*small), min(n, n*big, n*small)
            maximum=max(maximum, big)
        return maximum

155. Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.

利用元组tuple，同时储存数和最小值。

class MinStack(object):

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.q = []


    def push(self, x):
        """
        :type x: int
        :rtype: void
        """
        curMin = self.getMin()
        if curMin == None or x < curMin:
            curMin = x
        self.q.append((x, curMin));

    def pop(self):
        """
        :rtype: void
        """
        self.q.pop()

    def top(self):
        """
        :rtype: int
        """
        if len(self.q) == 0:
            return None
        else:
            return self.q[-1][0]

    def getMin(self):
        """
        :rtype: int
        """
        if len(self.q) == 0:
            return None
        else:
            return self.q[-1][1]

---

198. House Robber

题目描述：你是一名专业强盗，计划沿着一条街打家劫舍。每间房屋都储存有一定数量的金钱，唯一能阻止你打劫的约束条件就是：由于房屋之间有安全系统相连，如果同一个晚上有两间相邻的房屋被闯入，它们就会自动联络警察，因此不可以打劫相邻的房屋。给定一列非负整数，代表每间房屋的金钱数，计算出在不惊动警察的前提下一晚上最多可以打劫到的金钱数。

解题思路：
这道题的本质相当于在一列数组中取出一个或多个不相邻数，使其和最大。 这是一道动态规划问题。 我们维护一个一位数组dp，其中dp[i]表示到i位置时不相邻数能形成的最大和。 对于第i个房间我们的选择是偷和不偷， 如果决定是偷 则第i-1个房间必须不偷 那么 这一步的就是dp[i] = nums(i-1) + dpNotTake[i -1] , 假设dp[i]表示打劫到第i间房屋时累计取得的金钱最大值.如果是不偷， 那么上一步就无所谓是不是已经偷过， dp[i] = dp[i -1 ]， 因此 dp[i] =max(dpNotTake[i-1 ] + nums(i-1), dp[i-1] ) 其中dpNotTake[i-1]=dp[i-2]利用动态规划，状态转移方程：dp[i] = max(dp[i - 1], dp[i - 2] + num[i - 1])其中，dp[i]表示打劫到第i间房屋时累计取得的金钱最大值。

状态转移方程：
dp[0] = num[0] （当i=0时）
dp[1] = max(num[0], num[1]) （当i=1时）
dp[i] = max(num[i] + dp[i - 2], dp[i - 1])   （当i !=0 and i != 1时）

class Solution(object):
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
last, now = 0, 0
for i in nums: last, now = now, max(last + i, now)
return now

***
### 310. Minimum Height Trees
For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.

>(1)树是一个无向图，其中任何2个顶点通过唯一一条路径连接。
(2) 任何含有n个节点和n-1条边的连通图是一棵树。
(3) 图中一点的度等于该点的边的数量。
(4) 叶子节点的度为1，内部节点的度大于等于2。
(5) 一个路径图是一棵含有2个及以上的不分支的节点的树。
(6) 如果一棵树的一个节点被指定为根，则这棵树为根树。
(7) 有根树的高度是根与叶之间最长的向下路径上的边数。

It is very easy to get the idea of two pointers. One from each end and move at the same speed. When they meet or they are one step away, (depends on the parity of n), we have the roots we want.For a tree we can do some thing similar. We start from every end, by end we mean vertex of degree 1 (aka leaves). We let the pointers move the same speed. When two pointers meet, we keep only one of them, until the last two pointers meet or one step away we then find the roots.

It is easy to see that the last two pointers are from the two ends of the longest path in the graph.

The actual implementation is similar to the BFS topological sort. Remove the leaves, update the degrees of inner vertexes. Then remove the new leaves. Doing so level by level until there are 2 or 1 nodes left. What's left is our answer!
>实际类似于BFS（广度优先算法）。除去叶子（度为1），更新内部顶点的度。然后删除新的叶子节点。一直继续下去，直到剩下个1个或2个节点，这就是我们的答案！

The time complexity and space complexity are both O(n).

Note that for a tree we always have V = n, E = n-1.

class Solution(object):
def findMinHeightTrees(self, n, edges):
"""
:type n: int
:type edges: List[List[int]]
:rtype: List[int]
"""
if n == 1: return [0]
adj = [set() for _ in xrange(n)]
for i, j in edges:
adj[i].add(j)
adj[j].add(i)

    leaves = [i for i in xrange(n) if len(adj[i]) == 1]

    while n > 2:
        n -= len(leaves)
        newLeaves = []
        for i in leaves:
            j = adj[i].pop()
            adj[j].remove(i)
            if len(adj[j]) == 1: newLeaves.append(j)
        leaves = newLeaves
    return leaves

***
### 318. Maximum Product of Word Lengths
Given a string array`words`, find the maximum value of length`(word[i]) * length(word[j])`where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.




>思路：利用bitmap的方法，将字符串转换为数字。对于字符串中的每个字符ch，转换为1<<(ch-‘a‘).只要两个字符串转换之后的数字进行&操作结果为0，说明这两个字符串没有相同的字符。就可以求这两个字符串的长度的乘积，和最终要返回的值ret比较，保证ret一直是最大的。为了简化步骤，可以首先将字符串按照长度进行排序，长度较长的字符串排在前面。这样，在内部循环之中，只要满足条件可以计算乘积，内部循环就马上终止，因为后续就算计算出了乘积也一定比当前计算的乘积值要小。同样的，在外部循环之中，如果ret>=(words[i].length()*words[i].length())，那么直接终止循环，因为后面计算出的乘积一定比ret要小。


代码一：

class Solution(object):
def maxProduct(self, words):
"""
:type words: List[str]
:rtype: int
"""
if not words:
return 0
curr_max = 0
while words:
curr_word = set(words[0])
curr_len = len(words[0])
words = words[1:]
for word in words:
for char in curr_word:
if char in word:
break
else:
curr_max = max(curr_max, curr_len*len(word))
return curr_max

代码二：

class Solution(object):
def maxProduct(self, words):
"""
:type words: List[str]
:rtype: int
"""
maskLen = {reduce(lambda x, y: x | y, [1 << (ord(c) - 97) for c in word], 0): len(word)
for word in sorted(words, key = lambda x: len(x))}.items()
return max([x[1] * y[1] for i, x in enumerate(maskLen) for y in maskLen[:i] if not (x[0] & y[0])] or [0])

>注：
- ord（）：函数返回值为字符在ASCII码中的序号
- reduce( )：reduce内建函数是一个二元操作函数，他用来将一个数据集合（链表，元组等）中的所有数据进行下列操作：用传给reduce中的函数 func()（必须是一个二元操作函数）先对集合中的第1，2个数据进行操作，得到的结果再与第三个数据用func()函数运算，最后得到一个结果。第三个参数为0，则先对0和集合中的第一个数据进行操作。
- enumerate( )：遍历数组。

***



### 90. Subsets II
Given a collection of integers that might contain duplicates, ***nums***, return all possible subsets.
**Note:** The solution set must not contain duplicate subsets.
For example,
If ***nums*** = `[1,2,2] `
a solution is:`[ [2], [1], [1,2,2], [2,2], [1,2], []]`

解（一）：

class Solution(object):
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums.sort()
res=[[]]
for num in nums:
res+=[i +[num] for i in res if i +[num] not in res]
return res

进一步分析选取该元素的条件：
>- 该元素为整个集合中的第一个元素。
- 即该元素下标为 0
- 该元素不等于前一个元素
- 该元素等于前一个元素，但是前一个元素也在我们现在枚举的子集中

由此可推出解（二）：

class Solution:
# @param num, a list of integer
# @return a list of lists of integer
def subsetsWithDup(self, S):
res = [[]]
S.sort()
for i in range(len(S)):
if i == 0 or S[i] != S[i - 1]:
l = len(res)
for j in range(len(res) - l, len(res)):
res.append(res[j] + [S[i]])
return res

>代码分析：
1. 数列中本身包含空集[ ]
2. 第一轮i=0，l=0,j从0到0，添加[1]
3. 第二轮i=1,s[1]!=s[0],l=1,j从0到1，添加[2],[1,2]
4. 第三轮i=2,s[2]=s[1],l=1,j从3到4，添加[2,2],[1,2,2]

***
### 306. Additive Number
Additive number is a string whose digits can form additive sequence.

A valid additive sequence should contain **at least** three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.

**For example:**`"112358"`is an additive number because the digits can form an additive sequence: `1, 1, 2, 3, 5, 8` 
`"199100199"`is also an additive number, the additive sequence is: `1, 99, 100, 199`

**Note:** Numbers in the additive sequence **cannot** have leading zeros, so sequence `1, 2, 03`or `1, 02, 3`is invalid.

Given a string containing only digits` '0'-'9'`, write a function to determine if it's an additive number.

class Solution(object):
def isAdditiveNumber(self, num):
n = len(num)
for i, j in itertools.combinations(range(1, n), 2):
a, b = num[:i], num[i:j]
if b != str(int(b)) or a != str(int(a)):
continue
while j < n:
c = str(int(a) + int(b))
if not num.startswith(c, j):
break
j += len(c)
a, b = b, c
if j == n:
return True
return False

>1. a != str(int(a))用于保证序列不以零开头
2.  print list(itertools.combinations([1,2,3,4],2))
[(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
3.  num.startswith(c, j) num数列中第一个与c匹配的数字位于j

***
### 322. Coin Change
You are given coins of different denominations and a total amount of money *amount*. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return `-1`

**Example 1:**`coins = [1, 2, 5], amount = 11`
return `3` (11 = 5 + 5 + 1)
**Example 2:**`coins = [2] , amount = 3`
return `-1`

**Note**:You may assume that you have an infinite number of each kind of coin.
>**背景：**
有时会遇到这样一类题目，它的问题可以分解，但是又不能得出明确的动态规划或是递归解法，此时可以考虑用回溯法解决此类问题。回溯法的优点 在于其程序结构明确，可读性强，易于理解，而且通过对问题的分析可以大大提高运行效
率。但是，对于可以得出明显的递推公式迭代求解的问题，还是不要用回溯 法，因为它花费的时间比较长。
 
>**回溯法中，首先需要明确下面三个概念**
：（一）约束函数：约束函数是根据题意定出的。通过描述合法解的一般特征用于去除不合法的解，从而避免继续搜索出这个不合法解的剩余部分。因此，约束函数是对于任何状态空间树上的节点都有效、等价的。（二）状态空间树：刚刚已经提到，状态空间树是一个对所有解的图形描述。树上的每个子节点的解都只有一个部分与父节点不同。（三）扩展节点、活结点、死结点：所谓扩展节点，就是当前正在求出它的子节点的节点，在DFS中，只允许有一个扩展节点。活结点就是通过与约束函数的对照，节点本身和其父节点均满足约束函数要求的节点；死结点反之。由此很容易知道死结点是不必求出其子节点的（没有意义）。
 
>**为什么用DFS**
深度优先搜索（DFS）和广度优先搜索（FIFO）在 分支界限法中，一般用的是FIFO或最小耗费搜索；其思想是一次性将一个节点的所有子节点求出并将其放入一个待求子节点的队列。通过遍历这个队列（队列在 遍历过程中不断增长）完成搜索。而DFS的作法则是将每一条合法路径求出后再转而向上求第二条合法路径。而在回溯法中，一般都用DFS。为什么呢？这是因 为可以通过约束函数杀死一些节点从而节省时间，由于DFS是将路径逐一求出的，通过在求路径的过程中杀死节点即可省去求所有子节点所花费的时间。
FIFO 理论上也是可以做到这样的，但是通过对比不难发现，DFS在以这种方法解决问题时思路要清晰非常多。
 
>**回溯法可以被认为是一个有过剪枝的DFS过程**
利用回溯法解题的具体步骤首先，要通过读题完成下面三个步骤：
(1)描述解的形式，定义一个解空间，它包含问题的所有解。
(2)构造状态空间树。
(3)构造约束函数（用于杀死节点）。
然后就要通过DFS思想完成回溯，完整过程如下：
(1)设置初始化的方案（给变量赋初值，读入已知数据等）。
(2)变换方式去试探，若全部试完则转(7)。
(3)判断此法是否成功（通过约束函数），不成功则转(2)。
(4)试探成功则前进一步再试探。
(5)正确方案还未找到则转(2)。
(6)已找到一种方案则记录并打印。
(7)退回一步（回溯），若未退到头则转(2)。
(8)已退到头则结束或打印无解。

class Solution(object):
def coinChange(self, coins, amount):
coins.sort(reverse = True)
lenc, self.res = len(coins), 2**31-1

    def dfs(pt, rem, count):
        if not rem:
            self.res = min(self.res, count)
        for i in range(pt, lenc):
            if coins[i] <= rem < coins[i] * (self.res-count):  # if hope still exists
                dfs(i, rem-coins[i], count+1)

    for i in range(lenc):
        dfs(i, amount, 0)
    return self.res if self.res < 2**31-1 else -1

***
### 88. Merge Sorted Array

Given two sorted integer arrays *nums1* and *nums2*, merge *nums2* into *nums1* as one sorted array.

**Note:**You may assume that *nums1* has enough space (size that is greater or equal to *m* + *n*) to hold additional elements from *nums2*. The number of elements initialized in *nums1*and *nums2* are *m* and *n* respectively.


比较如下两种方法：

(1)
class Solution(object):
def merge(self, nums1, m, nums2, n):
while n > 0:
if m <= 0 or nums2[n-1] >= nums1[m-1]:
nums1[m+n-1] = nums2[n-1]
n -= 1
else:
nums1[m+n-1] = nums1[m-1]
m -= 1

(2)
class Solution(object):
def merge(self, nums1, m, nums2, n):
while m > 0 and n > 0:
if nums1[m-1] >= nums2[n-1]:
nums1[m+n-1] = nums1[m-1]
m -= 1
else:
nums1[m+n-1] = nums2[n-1]
n -= 1
if n > 0:
nums1[:n] = nums2[:n]

>（1）更加简洁，思考为什么？ 因为（1）中的循环能够保证`num2`中的数全部添加到`num1`，而（2）不行。

***

### 98. Validate Binary Search Tree
Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:
- The left subtree of a node contains only nodes with keys **less than** the node's key.
- The right subtree of a node contains only nodes with keys **greater - than** the node's key.
- Both the left and right subtrees must also be binary search trees.

Definition for a binary tree node.

class TreeNode(object):

def init(self, x):

self.val = x

self.left = None

self.right = None

class Solution(object):
def isValidBST(self, root, floor=float('-inf'), ceiling=float('inf')):
if not root:
return True
if root.val <= floor or root.val >= ceiling:
return False
# in the left branch, root is the new ceiling;
return self.isValidBST(root.left, floor, root.val) and
self.isValidBST(root.right, root.val, ceiling)

>Python中可以用如下方式表示正负无穷：float("inf"), float("-inf")

***

### 96. Unique Binary Search Trees

Given *n*, how many structurally unique **BST's** (binary search trees) that store values 1...*n*?

>假如整个树有 *n* 个节点，根节点为 *1* 个节点，两个子树平分剩下的 *n-1* 个节点。
假设我们已经知道节点数量为 *x* 的二叉树有`dp[x]`种不同的形态。
则一颗二叉树左节点节点数量为 *k* 时，其形态数为`dp[k] * dp[n - 1 - k]`。
而对于一颗 *n* 个节点的二叉树，其两个子树分配节点的方案有 *n-1* 种：
```(0, n-1), (1, n-2), ..., (n-1, 0)```
因此我们可以得到对于 ***i* **个节点的二叉树，其形态有：

for j in xrange(i):
res[i] += res[j] * res[i-1-j]

并且可以发现，dp数组有递推关系，我们可以使用递推或是记忆化搜索来实现。
边界条件为dp[0] = 1。

dp（dynamic-programming）动态规划解：

class Solution(object):
def numTrees(self, n):
res = [0] * (n+1)
res[0] = 1
for i in xrange(1, n+1):
for j in xrange(i):
res[i] += res[j] * res[i-1-j]
return res[n]

利用**卡塔兰数**：

Catalan Number (2n)!/((n+1)!*n!)

def numTrees(self, n):
return math.factorial(2n)/(math.factorial(n)math.factorial(n+1))

>**卡塔兰数**是[组合数学](http://baike.baidu.com/view/44868.htm)中一个常在各种计数问题中出现的数列。
卡塔兰数列的前几项为 [注： n = 0, 1, 2, 3, … n]：
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, …


***


### 46. Permutations
Given a collection of **distinct** numbers, return all possible permutations.

For example,
`[1,2,3]`have the following permutations:

[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

class Solution(object):
def permute(self, nums):
return map(list, itertools.permutations(nums))

***

### 80. Remove Duplicates from Sorted Array II
Follow up for "Remove Duplicates":What if duplicates are allowed at most *twice*?
For example,Given sorted array *nums* = `[1,1,1,2,2,3]`,
Your function should return length = `5`,
with the first five elements of *nums* being `1, 1, 2, 2, 3`. 
It doesn't matter what you leave beyond the new length.

class Solution(object):
def removeDuplicates(self, nums):
i = 0
for n in nums:
if i < 2 or n > nums[i-2]:
nums[i] = n
i += 1
return i

>注：不能去掉`i<2`,因为考虑`nums`中只有一个元素的情况下`n  = nums[-2]`,`return i = 0 ` 不符合实际。

***
###  19. Remove Nth Node From End of List

Given a linked list, remove the *n* th
 node from the end of list and return its head.

Definition for singly-linked list.

class ListNode(object):

def init(self, x):

self.val = x

self.next = None

class Solution:
def removeNthFromEnd(self, head, n):
fast = slow = head
for _ in range(n):
fast = fast.next
if not fast:
return head.next
while fast.next:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return head

***

### 179. Largest Number

Given a list of non negative integers, arrange them such that they form the largest number.

For example, given `[3, 30, 34, 5, 9]`, the largest formed number is `9534330`.

Note: The result may be very large, so you need to return a string instead of an integer.




>1. we define a function that compares two string (`a , b`) . we consider a bigger than b if `a+b>b+a` for example : (`a = 2, b = 11`) a is bigger than b because `211` >`112`

>2. convert all elements of the list from int to string

>3. sort the list descendingly using the comparing function we defined for example sorting this list `["2","11","13"]` using the function defined in step 1 would produce` ["2","13","11"]`

>4. we concatatenate the list `21311`

class Solution:

@param num, a list of integers

@return a string

def largestNumber(self, num):
comp=lambda a,b:1 if a+b>b+a else -1 if a+b<b+a else 0
num=map(str,num)
num.sort(cmp=comp,reverse=True)
return str(int("".join(num)))

***

### 300. Longest Increasing Subsequence
Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,Given `[10, 9, 2, 5, 3, 7, 101, 18]`,
The longest increasing subsequence is `[2, 3, 7, 101]`, 
therefore the length is`4`. 
Note that there may be more than one LIS combination, it is only necessary for you to return the length.


>**tails**
 is an array storing the smallest tail of all increasing subsequences with length `i+1` in `tails[i]`. For example, say we have nums = `[4,5,6,3]`, then all the available increasing subsequences are:

len = 1 : [4], [5], [6], [3] => tails[0] = 3
len = 2 : [4, 5], [5, 6] => tails[1] = 5
len = 3 : [4, 5, 6] => tails[2] = 6

We can easily prove that tails is a increasing array. Therefore it is possible to do a binary search in tails array to find the one needs update.

>Each time we only do one of the two:

(1) if x is larger than all tails, append it, increase the size by 1
(2) if tails[i-1] < x <= tails[i], update tails[i]

Doing so will maintain the tails invariant. The the final answer is just the size.

class Solution(object):
def lengthOfLIS(self, nums):
tails = [0] * len(nums)
size = 0
for x in nums:
i, j = 0, size
while i != j:
m = (i + j) / 2
if tails[m] < x:
i = m + 1
else:
j = m
tails[i] = x
size = max(i + 1, size)
return size

***
### 142. Linked List Cycle II
Given a linked list, return the node where the cycle begins. If there is no cycle, return `null`.

Consider the following linked list,
where E is the cylce entry and X,
the crossing point of fast and slow.
H: distance from head to cycle entry E
D: distance from E to X
L: cycle length

If fast and slow both start at head, when fast catches slow,
slow has traveled H+D and fast 2(H+D).
Assume fast has traveled n loops in the cycle,
we have: 2H + 2D = H + D + L --> H + D = nL --> H = nL - D
Thus if two pointers start from head and X,
respectively, one first reaches E, the other also reaches E.
In my solution, since fast starts at head.next,
we need to move slow one step forward in the beginning of part 2

Definition for singly-linked list.

class ListNode(object):

def init(self, x):

self.val = x

self.next = None

class Solution:
# @param head, a ListNode
# @return a list node
def detectCycle(self, head):
try:
fast = head.next
slow = head
while fast is not slow:
fast = fast.next.next
slow = slow.next
except:
# if there is an exception, we reach the end and there is no cycle
return None

    # since fast starts at head.next, we need to move slow one step forward
    slow = slow.next
    while head is not slow:
        head = head.next
        slow = slow.next

    return head

>1.[参考答案](https://leetcode.com/discuss/43146/share-my-python-solution-with-detailed-explanation)


***

### 16. 3Sum Closest

Given an array *S* of *n* integers, find three integers in *S* such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

>比较简单，不解释了

class Solution:
# @return an integer
def threeSumClosest(self, num, target):
num.sort()
result = num[0] + num[1] + num[2]
for i in range(len(num) - 2):
j, k = i+1, len(num) - 1
while j < k:
sum = num[i] + num[j] + num[k]
if sum == target:
return sum

            if abs(sum - target) < abs(result - target):
                result = sum

            if sum < target:
                j += 1
            elif sum > target:
                k -= 1

    return result

***

### 141. Linked List Cycle

Given a linked list, determine if it has a cycle in it.
>解释见142

Definition for singly-linked list.

class ListNode(object):

def init(self, x):

self.val = x

self.next = None

class Solution(object):
def hasCycle(self, head):
try:
slow = head
fast = head.next
while slow is not fast:
slow = slow.next
fast = fast.next.next
return True
except:
return False

***

### 143. Reorder List
Given a singly linked list *L*: *L*0→*L*1→…→*L**n*-1→*L*n,
reorder it to: *L*0→*L**n*→*L*1→*L**n*-1→*L*2→*L**n*-2→…
You must do this in-place without altering the nodes' values.
For example,Given `{1,2,3,4}`, reorder it to` {1,4,2,3}`.

>

Definition for singly-linked list.

class ListNode(object):

def init(self, x):

self.val = x

self.next = None

class Solution(object):
def reorderList(self, head):
if not head:
return

    # find the mid point
    slow = fast = head 
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # reverse the second half in-place
    pre, node = None, slow
    while node:
        pre, node.next, node = node, pre, node.next

    # Merge in-place; Note : the last node of "first" and "second" are the same
    first, second = head, pre
    while second.next:
        first.next, first = second, first.next
        second.next, second = first, second.next
    return 

> 对于`pre, node.next, node = node, pre, node.next`，此处并非通常意义上的赋值，可以看作更接近与指针顺序的调换。（如果仅仅是多变量赋值，则不需要第三个变量来暂时储存，可看成元组） [参考](https://leetcode.com/discuss/11122/a-python-solution-o-n-time-o-1-space)

***

### 221. Maximal Square

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and return its area.

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 4.

class Solution(object):
def maximalSquare(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
rows, max_size = len(matrix), 0
'''
size[i]: the current number of continuous '1's in a column of matrix.
Reset when discontinued.
The idea is to do a by-row scan, updating size[i]
Then check if there are continuous elements in size whose value is
bigger than current maximal size.
'''
if rows > 0:
cols = len(matrix[0])
size = [0] * cols
for x in xrange(rows):
# update size
count, size = 0, map(lambda x, y: x+1 if y == '1' else 0, size, matrix[x])
for y in xrange(cols):
# check if it exceeds current maximal size
if size[y] > max_size:
count += 1
if count > max_size:
# increase maximal size by 1
max_size += 1
break
else:
count = 0

    return max_size*max_size

>理解map（）函数的用法

***


### 134. Gas Station

There are *N* gas stations along a circular route, where the amount of gas at station *i* is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station *i* to its next station (*i*+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.

**Note:**The solution is guaranteed to be unique.

class Solution(object):
def canCompleteCircuit(self, gas, cost):
"""
:type gas: List[int]
:type cost: List[int]
:rtype: int
"""
if len(gas) == 0 or len(cost) == 0 or sum(gas) < sum(cost):
return -1
position = 0
balance = 0 # current tank balance
for i in range(len(gas)):
balance += gas[i] - cost[i] # update balance
if balance < 0: # balance drops to negative, reset the start position
balance = 0
position = i+1
return position

>If the total number of gas is bigger than the total number of cost. There must be a solution.


***


### 347. Top K Frequent Elements

Given a non-empty array of integers, return the ***k*** most frequent elements.

For example,
Given `[1,1,1,2,2,3]` and k = 2, return `[1,2]`.

**Note: **
You may assume *k* is always valid, 1 ≤ *k* ≤ number of unique elements.
Your algorithm's time complexity **must be** better than O(*n* log *n*), where *n* is the array's size.

import collections

class Solution(object):
def topKFrequent(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
# Use Counter to extract the top k frequent elements
# most_common(k) return a list of tuples, where the first item of the tuple is the element,
# and the second item of the tuple is the count
return [i[0] for i in collections.Counter(nums).most_common(k)]

***
### 48. Rotate Image

You are given an *n* x *n* 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up:Could you do this in-place?


**Most Pythonic - [::-1] and zip**
The most pythonic solution is a simple one-liner using [::-1] to flip the matrix upside down and thenzip to transpose it. It assigns the result back into A, so it's "in-place" in a sense and the OJ accepts it as such, though some people might not.

class Solution:
def rotate(self, A):
A[:] = zip(*A[::-1])

>[zip()函数](http://www.cnblogs.com/frydsh/archive/2012/07/10/2585370.html)

**Flip Flip** 
Basically the same as the first solution, but using reverse instead of [::-1] and transposing the matrix with loops instead of zip. It's 100% in-place, just instead of only moving elements around, it also moves the rows around.

class Solution:
def rotate(self, A):
A.reverse()
for i in range(len(A)):
for j in range(i):
A[i][j], A[j][i] = A[j][i], A[i][j]

###