candy

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)

dropegg

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

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

需求

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

数据特点

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

潜在的需求

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

    Read More

Contain Duplicate

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

TreeVisit

#二叉树的遍历

##非递归 Morris

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

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

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

    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

Graph

#无向图的判环

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

算法步骤:

  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
邻接矩阵表示法