Menu Sidebar
Menu

Coin Change 2

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

Perfect Number

一个数是Perfect number就是他的factor的和等于这个数. 那么先求factor, 然后求和就可以了.

Find Largest Value in Each Tree Row

给一个二叉树, 找每层最大的值. 直接层序扫描.

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之间较大的那个.

Find Bottom Left Tree Value

给一个二叉树, 返回左下的节点的值, 直接层序扫描, 然后最后一层的第一个值肯定就是啦.

Fibonacci Number

Fib数, 当前数等于前两个数的和, 需要记录一下前两个数即可.

Minesweeper

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

Diameter of Binary Tree

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

Student Attendance Record I

给一个string, 问有没有连续三个L或者超过一个A. 超过一个A用boolean判断, 连续三个L用一个counter和prev, prev记录前一个字符, counter记录几次重复.

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