发表于

思路：

本题是要求解在1:n的石子堆内，先出手者的最大收益。

dp(i,j)表示，i:n的石子堆内，先出手者的最大收益。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        piles.insert(0, 0)
        n = len(piles)
        for i in range(1, n):
            piles[i] += piles[i - 1]
        a = [[0] * n for i in range(n)]

        def dp(i, j):
            if n - i <= 2 * j:
                return piles[n - 1] - piles[i - 1]
            if a[i][j] > 0:
                return a[i][j]
            for k in range(2 * j):
                if i + k >= n:
                    break
                if a[i][j] == 0:
                    a[i][j] = piles[n - 1] - piles[i - 1] - dp(i + k + 1, max(k + 1, j))
                else:
                    a[i][j] = max(a[i][j], piles[n - 1] - piles[i - 1] - dp(i + k + 1, max(k + 1, j)))
            return a[i][j]

        return dp(1, 1)

反思：

dp问题分两种，1）每增加一项，寻找第i项与第i-1项之间的递推关系。2）将大的范围，逐渐减小至小范围，临界条件已知，最后求解大范围处的值。

发表于

Scons介绍

1 简介

Scons是一个python写的编译工具，与makefile功能类似，但能兼容makefile，同时更加智能，可以自动解析系统的include路径、typedef等。

2 Scons文件

1）配置文件：与scons命令位于同一目录下的SConstruct、Sconstruct、sconstruct文件

2）SConstruct使用函数SConscript()来定附属配置文件，这些附属配置文件被命名为SConscript。附属配置文件将脚本内的目标文件编译后传给SConstruct

学习参考：https://blog.csdn.net/sealyao/article/details/6402257

发表于

这周的心情，应该算是跌入谷底了吧。一篇杂谈，吐槽我低落的心情~

师父让我做一个自动出bin的工具，思路很简单，但当所有的需求都完成后，我居然花了一周。

今年华为的校招形势比往年都严峻，我不清楚我得多努力才能被认可，才能被留用。

在华为每天准点下班，居然被师父怼了。他对我的训斥，记忆犹新——命运要掌握在自己的手里，不要交给运气。如果你不好好干，就回去继续搞土木吧！

之前一直以为答辩时间早8月底，所以就一直很放松。但没想到提前到8月中旬了。时间不等人，我得马上进入备考状态了！

之前答应老师的一篇论文，估计8月底写不出来了。成果都有了，但如果让我现在分心去写论文，我做不到。上次面试阿里的悲剧，我绝不要重复！

LTE的那本书总算到了，接下来得要好好准备复习之前所学的内容了。

如果我们组今年只招1个，我一定要努力到，能留用的那1个就是我！I am the best, others are trashes!

hexo HW1

发表于

题目：给你两个长度相等的整数数组，返回下面表达式的最大值：

1
|arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j|

其中下标 i，j 满足 0 <= i, j < arr1.length。

思路：其实这道题的引申问题也就是求最远曼哈顿距离。而最远曼哈顿距离也可以引申为新增一个点，求该点到一群点的最大曼哈顿距离。

最大曼哈顿距离的求解方法：

1
2
3
4
|x1 - x2| + |y1 - y2| 
等价于 x1-x2 + y1-y2 (1,1), -x1+x2 + -y1+y2 (-1,-1), x1-x2 + -y1+y2 (1,-1), -x1+x2 + y1-y2 (-1,1) 
也就等价于 (x1,y1)-(x2,y2),(-(x1,y1))-(-(x2,y2)),(x1,-y1)-(x2,-y2),(-x1,y1)-(-x2,y2)
最后的最大距离的点，必然是位于这四种情况中的某一种，因此对于每种情况，保留其中的min坐标，对于新加入的点，若为最大，必然是减去min坐标
1
2
3
4
5
6
7
8
9
10
class Solution:
    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
        res = 0
        for i, j in [[1, 1], [1, -1], [-1, -1], [-1, 1]]:
            close = arr1[0] * i + arr2[0] * j
            for k in range(1, len(arr1)):
                p = arr1[k] * i + arr2[k] * j + k
                res = max(res, p - close)
                close = min(close, p)
        return res

反思：这道题其实很有借鉴意义，因为之前面试的时候就遇到过这道题，结果没有做出来。原来就是四种情况，每次保存每种情况最小的那个坐标即可。

发表于

leetcode 1130

思路:

dp[i,j]=min(dp[i,k]+dp[k+1,j]+max(arr[i:k+1])*max(arr[k+1:j+1])

因此，直接使用dp函数求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        a = [[0] * len(arr) for i in range(len(arr))]

        def dp(i, j):
            if i == j:
                return 0
            if a[i][j] != 0:
                return a[i][j]
            res = float('inf')
            for k in range(i, j):
                res = min(res, dp(i, k) + dp(k + 1, j) + max(arr[i:k + 1]) * max(arr[k + 1:j + 1]))
            a[i][j] = res
            return res

        return dp(0, len(arr) - 1)

反思：因为很久没有做leetcode的题目了，结果这道这么简单的题都没有做出来，是时候反省一下自己了。为什么最近自己总是想着玩，没有认真对待自己的代码。对于coder而言，代码就是自己的尊严呀！