Menu Sidebar
Menu

Archive: October 14, 2019

Longest Palindromic Subsequence

最长回文子序列, 首先这个子序列就是substring, 这题用dp做, dp[i][j]表示在substring(s, i, j)的最长回文子序列. 这时,有一下集中情况: i==j, 这时候就是一个字符,当前最长回文子序列是1 i>j, 这时候越界了, 返回0 i<j时, 我们需要判断i和j的字符是不是相同, 如果相同, 继续探索i+1和j-1的答案并且加上i和j作为答案,即+2 如果不同, 则当前的i和j无法构成回文, 因为我们需要的是longest,所以选择i+1和j-1之间较大的那个.

Minesweeper

扫雷游戏, 给一个board给一个操作, 问操作过后的board什么样子. 这个就是dfs, 注意一点如果周围有雷, 需要用count记录一下雷数, 然后把count写入board.

Diameter of Binary Tree

二叉树周长, 找到最长的一条路径在二叉树上. 这个路径不一定过root, 也不一定在某节点两侧. 所以我先要写一个找到depth的方法. 然后找每个节点的左边和右边. 最后把所有的结果取max.

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.