1

There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:
Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.

1. 分治法

将小孩分成两边，分别计算每一边需要最优糖果分配。
在合并时，有两种边界情况需要考虑，这里设mid为二分中点，左边界为mid,右边界为mid+1，最优糖果分配数组为candy：
a) rating[mid] > rating[mid+1] and candy[mid] < candy[mid+1]
此时左边界违背了题中条件，需要调整左边界rating值为右边界值+1，并接着调整左边小孩的值。
b) rating[mid] < rating[mid+1] and candy[mid] > candy[mid+1]
此时右边界违背了题中条件，需要调整右边界rating值为左边界+1，并接着调整右边小孩的值。

具体代码如下：

1

def candyUtil(ratings, left, right, candies):
    if left == right:
        candies[left] = 1
        return 1
    mid = (left+right) / 2
    leftCandy = candyUtil(ratings, left, mid, candies)
    rightCandy = candyUtil(ratings, mid+1, right, candies)
    if ratings[mid] < ratings[mid+1]:
        if candies[mid] >= candies[mid+1]:
            j = mid+1
            while j <= right and ratings[j] > ratings[j-1] and candies[j] <= candies[j-1]:
                rightCandy += candies[j-1]+1-candies[j]
                candies[j] = candies[j-1]+1
                j += 1
    elif ratings[mid] > ratings[mid+1]:
        if candies[mid] <= candies[mid+1]:
             j = mid
             while j >= 0 and ratings[j] > ratings[j+1] and candies[j] <= candies[j+1]:
                leftCandy += candies[j+1]+1-candies[j]
                candies[j] = candies[j+1]+1
                j -= 1
    print left, right, candies
    return leftCandy+rightCandy

def candyDivide(ratings):
    return candyUtil(a, 0, len(a)-1, [1]*len(ratings))

递推公式为T(n) = 2T(n/2) + O(n)
时间复杂度为O(n)，空间复杂度为O(n)

1. 贪心算法

采用类似贪心思想，扫描数组两次。
第一次从左往右扫描，当rating[i] > rating[i-1]时，candy[i] = candy[i-1]+1

保证如果第i个孩子的rating值如果大于其左边i-1孩子的值，那么它分得的糖果一定比左边的多。

第二次从右往左扫描，，当rating[i] > rating[i+1]时，candy[i] = max(candy[i], candy[i+1]+1)

保证第i个孩子的rating值如果大于其右边i+1孩子的值，那么他分得的糖果一定比右边孩子多。

两次扫描，分别保证了孩子左边和右边情况，并且一定是最优的。

1

def candy(self, ratings):
    ret = 0
    c = [1] * len(ratings)
    for i in range(1, len(ratings)):
        if ratings[i] > ratings[i-1]:
            c[i] = c[i-1]+1
        else:
            c[i] = 1
    ret = c[-1]
    for i in reversed(range(len(c)-1)):
        if ratings[i] > ratings[i+1]:
            c[i] = max(c[i+1]+1, c[i])
        ret += c[i]
    return ret

时间复杂度为O(n)，空间复杂度为O(n)

1

有座N层的建筑，请你用两个相同鸡蛋确定鸡蛋可以安全落下的最高位置，求最少的尝试次数。

1. 逐层尝试
   首先想到的是最简单的办法是一层开始往上试。那么显然最坏情况是在最后一层不能安全降落，此时尝试次数为N-1。时间复杂度为O(N)

2. 二分尝试
   我们还容易想到2分的办法。第一次在N/2层，如果碎了回到一的办法一层层向上检查{1,N/2-1}层，如果没碎则继续2分考察3/4*N层。
   此方法最坏情况发生在第一次鸡蛋就碎了，此时我们需要从第一层，或者N/2层开始，依次向上试。需要尝试N/2次，时间复杂度为O(N)

3. 动态规划
   上述两种方案都不够好，对于方法1尝试的太过保守，导致大量丢第一颗蛋。方法2尝试的太过激进，需要大量丢第二颗蛋。可以发现，如果第一颗鸡蛋碎了后，第二颗鸡蛋的尝试次是恒定的，它将只能从上一次没碎的未知到这次碎了的未知逐一检测。发现这个性质后，我们考虑使用动态动态规划。
   设F(i)表示i层楼梯两个鸡蛋最少需要尝试的次数。
   对于i层高的建筑，假设第一颗鸡蛋在第K层丢下。它如果碎了，则第二颗鸡蛋需要向下需要尝试K-2次。而如果没碎，则仍然使用第一颗鸡蛋，测试剩下的i-k层。

   F(i) = 1+min{K-2, F(i-k)} k = 1 to i
   时间复杂度为O(n^2)

   Read More

logsystem是一道最近在facebook面试中经常遇到的问题，本文抛砖引玉，介绍我关于该问题的思考。

需求

是用来收集什么日志？ => 收集手机app的crush记录
收集日志的目的? => 分析crush的原因 => 最好需要上层的查询分析接口
日志的存储时间?永久还是有期限? => 两年 or 永久?为了估算空间

数据特点

1. Crush收集的记录可能经常会发生变化
   时间 模块 错误信息 栈信息等
2. 写明显大于读

潜在的需求

1. 数据安全性
2. 日志的汇总
3. 查询接口
4. 严重bug通知

   Read More

1

Given an array of integers and an integer k, find out whether there there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.

思想：使用哈希表存储最近出现的k个元素，对于每个元素检查其是否在哈希表中即可。
做法步骤：

1. 初始时哈希表为空
2. 对于每一个元素i，检查其是否在哈希表中，如果是则返回。
3. 如果不是，则将其插入到哈希表中
4. 当哈希表元素超过k个时，删除第i-k个元素

1

def containsNearbyDuplicate(nums, k):
    if k == 0:
        return False
    dic = {}
    for i, num in enumerate(nums):
        if num in dic:
            return True
        dic[num] = i
        if i >= k:
            del dic[nums[i-k]]
    return False

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.

这一题是对上一题的扩展，允许元素的差值最大为k。
思想：每个元素除以t后得到v，仅需检查[v/t-1, v/t, v/t+1]这三个值是否在哈希表中即可判断是否存在差值小于k的元素

做法步骤：将每个元素值num除以t存入哈希表中。哈希表存储最近k个元素。

1. 初始时哈希表为空
2. 对于每一个元素i，将其除以t，得到key。
3. 检查[key-1, key, key+1]是否在哈希表中存在。如果存在，检查其实际值的差是否小于t
4. 如果不存在，将val存入哈希表中，并记录其实际值: dict[num[i]/t] = num[i]
5. 当哈希表元素超过k个时，删除第i-k个元素

当t等于0时，需要进行特殊处理。此时key=num

1

def containsNearbyAlmostDuplicate(self, nums, k, t):
    if k < 1 or t < 0:
        return False
    dic = {}
    for i, num in enumerate(nums):
        key = num / t if t else num
        for v in [key-1, key, key+1]:
            if v in dic and abs(dic[v] - num) <= t:
                return True
        if len(dic) == k:
            prevKey = nums[i-k] / t if t else nums[i-k]
            del dic[prevKey]
        dic[key] = num
    return False

#二叉树的遍历

##非递归 Morris

思想是利用prev节点(左孩子的最右子节点)的右节点保存当前node节点，从而保证能安全访问左节点并且能退回当前节点。

对于前序遍历和中序遍历，均是按照左、中、右的访问方式，遍历整个树结构，分别用cur和prev表示当前节点和上一个节点。prev节点是为了防止左节点已经被访问过。中序遍历算法流程为：

1. 如果cur左节点存在，则根据prev指针的右孩子节点情况考虑遍历左子树还是右子树。
   1.1. 如果prev的右孩子为空，则说明左子树还未访问。
   此时访问左子树，并设置prev的右指针为当前节点。
   1.2. 如果prev的右孩子不为空，则说明左子树已经访问完成，访问右子树。
   此时复原指针，重新设置prev的右指针为空，并将当前指针设置为右孩子即可
2. 如果cur左节点不存在，访问该节点，并设置节点指针为右孩子即可。

   Read More

1

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
For example:
Given the following binary tree,
   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

You should return [1, 3, 4].

Read More

Robber

有个聪明的小偷，打算偷一连串的房间。为了不被人发现，相邻的房间最多只偷一个。假设每个房间的价值为a[i]，问最大能偷取的价值。

如果价值都大于0，那么对于每间房间有两种情况，要么不偷，要么偷（此时不能偷前面一家），则存在递推公式如下：

dp[i] represents best value for robber to rob a[0..i]
dp[i] = max(dp[i-1], dp[i-2]+a[i])

如果存在价值小于0的，那么对于该房间选择显然是不偷的，此时：

dp[i] = max(dp[i-1], dp[i-2] + c) c = a[i] if a[i] > 0 else 0

1

def rob(self, nums):
    dp = deque([0] * 2)
    for i, num in enumerate(nums):
        c = num if num > 0 else 0
        val = max(dp[-1], dp[-2]+c)
        dp.popleft()
        dp.append(val)
    return dp[-1]

Robber2

聪明的小偷发现相邻房间不偷还是不安全，更改条件为相邻k家都不能偷，问此时能得到的最大价值。

Read More

字符串的编码

字符串的编码是一个生活中随处都要使用到的问题，本篇文章将从最基本的编码方式说起。
最简单的办法可在每个单词前纪录单词长度，并用特殊字符分割即可。

1

def encode1(words):
    res = ""
    for word in words:
        res += str(len(word)) + ':' + word
    return res

有时可能找不到一个合理的分隔符，同时此编码方式长度部分并没有表示字符串本身值，实际上是浪费的。

为了解决上面两个问题，使用两个特殊字符来标示单词之间的分割，如Linux采用\t\n分割。
当字符中出现\t时，需在其后面再补上\t。

1

def encode2(words):
    res = ""
    for word in words:
        for c in word:
            if c != '\t':
                res += c
            else:
                res += '\t\t'
        res += '\t\n'
    return res


def decode2(s):
    word, words = "", []
    i = 0
    while i < len(s):
        if s[i] != '\t':
            word += s[i]
            i += 1
        else:
            if s[i+1] == '\t':
                word += '\t'
            elif s[i+1] == '\n':
                words.append(word)
                word = ""
            else:
                return []  # invalid
            i += 2
    return words

上述编码还可进行一个简单的优化，将重复的字符用数字表示。
如aacccd -> a2c3d

Read More

给定二维平面n个矩阵，矩阵采用三元组表示(left, right, height)分别表示矩阵的左端点，右端点，以及高。矩阵都以地面作为底边。
矩阵可能相交。求n个矩阵围成的面积。

Read More

#无向图的判环

思想：如果一个点被访问两次，则说明存在两条不同的路径到达该点。将这两条路径连接起来，则必然存在环。

算法步骤：

1. 采用DFS，从任意一点开始遍历图
2. 使用visited标记已经走过的路径
3. 由于对于无向图，当前节点与相邻节点必然存在双向路径，使用parent标记父亲节点
4. 遍历当前节点的所有相邻节点adj
   如果当相邻节点adj不是父亲节点，且已经访问过，则说明存在环，直接返回存在环。
   否则递归遍历相邻节点

1

def isUndirectedCycleDFS(graph, node, visited, parent):
    if visited[node]:
        return false
    visited[node] = true
    for adj in graph[node].adjs:
        if adj != parent and visited[adj]: #此点已经被访问，且不是父亲节点
            return false
        if !isUndirectedCycleDFS(graph, adj, visited, node): #子节点存在环，直接返回
            return false
    return true

#无向图的连通性

思想：从任意一点开始，可以完整遍历图中所有节点。为了避免图中出现环而导致无限循环，使用visited标记所有走过的节点。

#树的判定

树是特殊的无向图，其判定条件如下：

1. 树上所有节点是联通的
2. 到任意一点只存在唯一路径 => 树上不存在环
3. 两点之间只存在唯一路径

#有向图的判环

思想：记录从起点开始的访问路径，有向图存在环当且仅当：当前节点访问的下一个相邻节点出现在访问路径中。

算法步骤：

1. 采用DFS，从任意一点开始遍历图
2. 使用visited标记已经走过的路径
3. 使用数组path标记当前走的路径
4. 遍历当前节点的相邻节点adj
   当adj出现在路径中，则说明存在环
   否则递归遍历

1

def isDirectedCycleDFS(graph, node, visited, path):
    if visited[node]:
        return true
    visited[node] = true
    path[node] = true
    for adj in graph[node].adjs:
        if path[adj] or !isDirectedCycleDFS(graph, adj, visited, path):
            return false
    path[node] = false
    return true

#有向图的连通性

思想：对于任意一个点，当它能通往图上其它所有点，且图上其它所有点能到达该点则说明图是联通的

算法步骤：

1. 从任意一点p开始，检查其是否能通往其它所有点
2. 将图上的所有连线颠倒
3. 采用有向图判环方法，从p开始，检查其是否能通往其它所有点

   1

   def isDirectedConnected(graph): init visited array to false traverse(graph, 0, visited) for flag in visited: #检查是否可达其它所有点 if !flag: return fasle reversed_graph = reverseGraph(graph) #将图中连线颠倒 init visited array to false traverse(reversed_graph, 0, visited) for flag in visited: #检查是否可达其它所有点 if !flag: return fasle return true

#拓扑排序

##广度优先遍历

思想： 入度为0的节点表明当前工作可以开始

1. 使用队列保存所有入度为0的节点
2. 每次从队列中取出节点，进行访问后，扩展相邻的节点，修改相邻节点的入度值，如果为0则加入队列
3. 如果未遍历为所有节点，则说明出现环(由于环内节点入度都大于0)。

   1	for node in graph: if node not in inCnt: inCnt[node] = 1 for adj in node.adjs: inCnt[adj] += 1 for node, val in inCnt: if val == 0:

分析: 可以一边遍历一边输出结果，需要O(n)保存visited,O(n)保存入度,O(n)保存队列

##深度优先遍历

思想：当一个节点所有相邻节点访问完成后，此节点可以放在工程最后执行

1. 同有向图判环方法类似，遍历整个图
2. 当所有相邻节点访问完后，将节点加入待访问的最后。
3. 逆序输出访问节点

   1

   def dfs(self, topo, path, visited, node): if node in visited: return True visited.add(node) path.add(node) for neigh in node.neighbors: if neigh in path: return False if neigh not in visited: if not self.dfs(topo, path, visited, neigh): return False topo.append(node) path.remove(node) return True def topSort(self, graph): path, visited, topo = set(), set(), [] for node in graph: if not self.dfs(topo, path, visited, node): throw DETECT_CYCLE topo.reverse() return topo

分析：在最后才能输出结果，需要O(n)保存Path,O(n)保存visited, O(n)保存最后结果

#欧拉回路

##无向图
条件是：

1. 所有顶点的度为偶数。
2. 图是联通的
   对于欧拉路径，起点和终点可以为奇数，其它顶点都为偶数
   打印欧拉回路：优先访问度为偶数的顶点，当不存在时才访问度为奇数的顶点

##有向图
条件是：

1. 所有定点的入度等于出度
2. 图是联通的
   对于欧拉路径,起点的入度比出度多1，终点的入度比出度少1。

#有向图的最短路径
设有V个顶点，E条边

1. 无环图
   使用拓扑排序后，依次更新，复杂度O(V+E)
2. 有环，无负边
   Dijkstra, 使用优先队列，每次从队首取出距离最近的顶点，O(E+VlgV)
3. 有环，有负边
   BellFord, DP，从底向上计算一个顶点到经过至多i条边后到其他顶点的距离。O(V*E)

http://www.cnblogs.com/Ixia/p/3917675.html
邻接矩阵表示法