Menu Sidebar
Menu

Leetcode

Coin Change 2

给一个amount给一个coin数组, 问从coin中组成amount的多少种可能. 这个是典型的dp题, 设dp[i]是i块钱的找零个数. 那么我们就可以推断出, dp[i] += dp[i-coin[j]], 但是dp的初始值怎么设计? 我们设dp[0] = 1, 这意味着当, 当前的coin的和等于amount的时候, 算作一种找零方法.

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.

Delete Node in a BST

BST中删除节点, 经典算法: 先BST搜到节点, 然后: 1. 如果左子树是空, 返回右子树. 2. 如果右子树是空, 返回左子树. 3. 两个都不是空的, 找到右子树最左的节点, 赋值给root, 然后继续删除右子树root的当前值.

Older Posts

书脊

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

October 2019
M T W T F S S
« Sep    
 123456
78910111213
14151617181920
21222324252627
28293031