kitt blog (欢迎留言，最近刷的题目放到github上了)

用一个队列实现按层遍历二叉树。遇到第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.

我们正向扫一遍, 求出每天的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相同。

使用递归来求解, 从网上看到一种很好的棋盘表示方法, 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的留言。

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

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

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

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

Merge sort

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

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

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

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

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

先把链表转成数组，再递归。每次数组的中点元素为root, 再递归地建立左右子树。

递归。每次数组的中点元素为root, 再递归地建立左右子树。