Algorithm

每日一题-二叉树最长连续路径

[每日一题] (二叉树最长连续路径)
在一个二叉树中找出最长连续递增的path，输出path中node的个数。path只能从上到下
Follow-up：path可以从下到上然后从上到下

解题思路


本次的代码没有经过具体测试，仅作讨论用途-.-
原题: 使用递归，每次都计算当前最长路径长度
Follow-up: 使用递归，每次递归的时候计算以当前结点为子树时的最长路径以及与父结点的连续路径。
     具体方法是在每个结点递归调用两次函数，计算左右子树的最长路径长度和连续路径长度，然后比较后返回以该结点为子树最长路径长度和连续路径长度

Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#!/usr/bin/env
# -*- coding:utf-8 -*-
# 原题
class Solution(object):
	def longestPath(self, root):
		if root == None:
			return 0
		left = self.recursive(root.left, root.val, 1) # 求左边子树的最大长度
		right = self.recursive(root.right, root.val, 1) # 求右边子树的最大长度
		return max(left, 1, right)
	def recursive(self, node, preVal, tempLength):
		if node == None:
			return 0
		thisLength = tempLength + 1 if node.val == preVal + 1 else 1 # 如果该节点和父节点连续，则当前最大长度为父节点的最大长度+1，否则为1
		left = self.recursive(node.left, node.val, thisLength) # 找左子树最大长度
		right = self.recursive(node.right, node.val, thisLength) # 找右子树最大长度
		return max(left, thisLength, right) # 返回当前节点以后的节点的最大路径长度
# Follow-up
class Solution(object):
	def longestPath(self, root):
		if root == None:
			return 0
		left, Lbig, Lsmall= self.recursive(root.left, root.val) # left代表左子树的最长路径长度, Lbig代表root节点左子树中比root大的连续路径长度, Lsmall代表root节点左子树中比root小的连续路径长度
		right, Rbig, Rsmall = self.recursive(root.right, root.val) # right代表右子树的最长路径长度, Rbig代表root节点右子树中比root大的连续路径长度, Rsmall代表root节点右子树中比root小的连续路径长度
		thisLength = max(left, right, Lbig+1+Rsmall, Rbig+1+Lsmall) # 以当前节点为根的子树的最长路径长度
		return thisLength
	def recursive(self, node, preVal): # 每次递归计算出以当前node为根的子树的最长路径长度
		if root == None:
			return 0, 0, 0
		left, Lbig, Lsmall = self.recursive(root.left, root.val)
		right, Rbig, Rsmall = self.recursive(root.right, root.val)
		thisLength = max(left, right, Lbig+1+Rsmall, Rbig+1+Lsmall)
		if root.val == preVal + 1:
			return thisLength, max(Lbig, Rbig)+1, 0
		elif root.val == preVal - 1:
			return thisLength, 0, max(Lsmall, Rsmall)+1
		else:
			return thisLength, 0, 0

Algorithm

每日一题-石之游戏

[每日一题] (石之游戏)
n堆石头排成一行，你每次可以把相邻的2堆石头聚成1堆，聚合后的石头数会成为你的分数的一部分。
问当进行n-1次，所有石头聚成一堆后，怎么使得总分最小。
例子: [3, 4, 3]
  第一次 3+4=7 -> [7, 3]
  第二次 (7) + 7 + 3 = 17 -> [17]
  总分17最少。

Follow-up(Google onsite): 变成一个环

解题思路


使用动态规划,思路可参考算法导论的矩阵链乘法。
状态转移矩阵:
  p[i][j] = min[p[i][k] + p[k+1][j] + s[i][j]] (i<=k<=j)
  s[i][j] = s[i][k] + s[k+1][j]
其中p[i][j]表示从i合并到j所得的最小分数，s[i][j]表示从i合并到j所得出的数

Python:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#!/usr/bin/env 
# -*- coding:utf-8 -*-
"""
时间复杂度 O(n^3)
"""
stone = [16,11,7,17,11,7,9,2,17,20,22,7,5,17,6,14,21,2,9,2,15,20,14,6,12,16,9,8,14,5,1,12,4,19,5,14,22,20,13,12,19,14,3,6,17,21,13,17,8,9,18,1,8,12,5,20,2,7,14,22,14,7,12,20,22,2,13,15,9,14,20,13,3,18,8,10,20,10,18,21]
N = len(stone) 
class Solution(object):
    def stoneGame(self, stone, N):
        p = [[0 for i in xrange(N)] for j in xrange(N)] # p[i][j]代表合并i到j的最优解
        s = [[0 if i != j else stone[i] for i in xrange(N)] for j in xrange(N)] # s[i][j]代表合并i到j后生成的值
        for l in xrange(1, N): # 循环N-1次， 每次得到长度为l+1的石头堆的最优解
            for i in xrange(N-l):
                j = i + l # 计算当前尾部j
                p[i][j] = None
                for k in xrange(i, j):
                    if p[i][j] == None:
                        s[i][j] = s[i][k] + s[k+1][j]
                        p[i][j] = p[i][k] + p[k+1][j] + s[i][j]
                    else:
                        p[i][j] = min(p[i][j], p[i][k] + p[k+1][j] + s[i][j])
        return p[0][N-1] # p[0][N-1]代表合并0到N-1的最优解，即为答案


乱七八糟

Hello world

  忙活了几天再加上大四瞎弄的一段时间，总算暂时使用github和hexo搭成了一个博客了。然而hexo中的有些东西还不是很了解-.-，以后再慢慢改吧！话说hexo还真是一个很好用的东西啊，如果自己也能写出这么好用的程序就好了……

  博客以后可能会贴一点刷题小组每天一题的解答，可能贴一点自己写的一些小程序，或者可能会贴一点收藏的教程。万事开头难，一步一步来吧！

  Markdown用得还不习惯，第一篇博客就到这里了吧。


  总之希望大家可以多捧场啦:)