这里看到一种很巧妙的解法, 在遍历当前层时, 构建下一层。

I saw a wonderful solution here. When traversing the current level, build the next level.

继续阅读

用一个队列实现按层遍历二叉树。遇到第1, 3, 7, 15, 31...个节点时(都和2的幂有关)让它们的next指向空, 判断N是不是1, 3, 7, 15, 31...的公式是 N & (N + 1) == 0, 位运算。

 

Use a queue to traverse the binary tree by level. When we meet the 1st, 3rd, 7th, 15th, 31th... node (note that they are close to 2^n), assign None to their "next" field. Bit operation can be used to check whether N is 1, 3, 7, 15, 31... or not. N & (N + 1) == 0

 

继续阅读

动态规划, 用isPal记录子串是不是回文串, isPal[i][j] == true含义是从s[i]到s[j]的子串(包含起点终点)是回文串。用minPalNum记录以s[0]为起点的子串包含的最少的回文串的个数, minPalNum[i] == 3 含义是从s[0]到s[i]的子串(包含起点终点)中回文串的最小数目是3个。当遇到一个isPal[i][j] == true的情况, 就更新minPalNum。最后minPalNum[lenS] - 1即为所求。

 

Dynamic programming. Use "isPal" to record whether a substring is a palindrome or not, "isPal[i][j] == true" means a substring starts from s[i] (includsive) to s[j] (inclusive) is a palindrome. Use "minPalNum" to record the minimum number of palindromes within a substring start from s[0], "minPalNum[i] == 3" means a substring starts from s[0] (included) to s[i] (included) has 3 palindromes and 3 is the minimum number. When we meet a "isPal[i][j] == true" case, we update minPalNum. Finally the result is minPalNum[lenS] - 1.

 

继续阅读

Count and Say @ LeetCode (Python)

2014年3月21日 01:07

 

继续阅读

我们正向扫一遍, 求出每天的maxProfit放到maxProfitForward里, 再逆向扫一遍, 求出每天的maxProfit放到maxProfitBackward里, 都是O(N)时间。如果不进行transaction, maxProfit为0。如果只进行一次transaction, maxProfit为maxProfitForward[-1]。如果进行两次transaction, 顺序只能是买入->卖出->买入->卖出, 设第一次卖出发生在前i天, 第二次卖出发生在第i+1天到最后一天之间, 那么maxProfit就是 maxProfitForward[i-1] + maxProfitBackward[i] 的最大值, 还是O(N)时间。总的时间复杂度是O(N)。

 

First we scan forward and put everyday's maxProfit into maxProfitForward list, then we scan backward and put everyday's minProfit into maxProfitBackward list. Time complexity is O(N). If there's no transaction, the maxProfit will be 0. If there's only one transaction, the maxProfit will be maxProfitForward[-1]. If there are two transactions, the order must be buying -> selling -> buying -> selling. We assume that the first selling happens within first i days and the second selling happens between i+1 day and the last day, so maxProfit is the max value of ( maxProfitForward[i-1] + maxProfitBackward[i] ). Time complexity is O(N). The total time complexity is O(N).

 

继续阅读

任何时候只能最多持有一股, 即每天的选择就是买入一股, 卖出一股或者不行动, 要卖出股票的话手头必须有一股。只要遇到递增序列, 就赚到了profit。

继续阅读

扫描一遍,不断更新最大利润和最低价格即可。最大利润是当前价格减去最低价格。

继续阅读

N-Queens II @ LeetCode (Python)

2014年3月15日 22:07

这基本上和N-Queens相同。

继续阅读

N-Queens @ LeetCode (Python)

2014年3月15日 22:03

使用递归来求解, 从网上看到一种很好的棋盘表示方法, N = 4时, 棋盘为[1, 3, 0, 2], 即第1行的queen放在第2列, 第2行的queen放在第4列。Queen逐行放入棋盘, 每放入一个新的queen, 只需要检查她跟之前的queen是否列冲突和对角线冲突就可以了。如果两个queen的坐标为(i1, j1)和(i2, j2), 当abs(i1 - i2) = abs(j1 - j2)时就对角线冲突。

继续阅读

动态规划,写出二维数组的表达式后会发现dp[i][j]只和dp[i-1][j]、dp[i-1][j-1]有关,所以可以进一步简化为一维数组,感谢traceformula的留言。

继续阅读

Clone Graph @ LeetCode (Python)

2014年3月15日 16:36

BFS和DFS应该都可以, 我用了BFS。根据一楼评论, 用了一个dictionary来记录所有新生成的node, 并且测试数据中有...#3,4,4#...的情况, 所以只要node一入队,就认为是visited. 而不是node出队时才认为是visited (这种情况下node 4会被访问两次)。

继续阅读

Gas Station @ LeetCode (Python)

2014年3月15日 15:26

看了网上的解法, 太巧妙了。如果sum(gas) < sum(cost)则无解, 否则必定有解。Sum < 0那一块不考虑, 因为total >= 0, 所以剩下那一块必定Sum >= 0。

继续阅读

Partition List @ LeetCode (Python)

2014年3月15日 14:19

用两个链表分别记录<x的节点和>=x的节点。

Use two linked lists to separately record nodes < x and nodes >= x.

继续阅读

Sort List @ LeetCode (Python)

2014年3月15日 13:16

Merge sort

继续阅读

Minimum Path Sum @ LeetCode (Python)

2014年3月13日 01:30

动态规划, 这道题和Unique Paths II如出一辙。

继续阅读

Unique Paths II @ LeetCode (Python)

2014年3月13日 01:20

动态规划, 初始化第一行和第一列时遇到障碍物就停止, 因为障碍物之后的位置肯定到达不了。递推公式是如果grid[i][j]没有障碍物, dp[i][j] = dp[i-1][j] + dp[i][j-1], 如果grid[i][j]有障碍物, dp[i][j] = 0。

继续阅读

Unique Paths @ LeetCode (Python)

2014年3月12日 23:52

m行n列, 需要往下走m-1步, 往右走n-1步, 也就是求C(m-1+n-1, n-1)或C(m-1+n-1, m-1)。

继续阅读

Path Sum II @ LeetCode (Python)

2014年3月12日 21:59

需要记录走过路径上的值, 我另外用了一个currSum变量来记录当前valList中所有数的和, 省去了sum(valList), 可以节省一些时间。Solution.res 和 Solution.Sum是类变量, 每一个getPath函数都可以访问它们。

继续阅读

用Python分割图片 (PIL)

2014年3月10日 01:39

今天试了下Python Imaging Library, 分割图片真方便, 当然还有其他逆天功能。有幅图片 a.bmp , 宽度1600, 高度1200, 需要把它均匀分割成相等大小的4份。

 

继续阅读

Triangle @ LeetCode (Python)

2014年3月08日 12:26

动态规划, 使用两个数组, dp记录当前行信息, oldDp记录上一行信息。dp[i]的含义是从顶端走到当前行dp[i]这个位置的最小路径和。

继续阅读