顾北清歌

题解

图片（转成链接使用）(4) 笔记(3) 面试算法题(3)

/ 注册

全部文章 / 题解（共7篇）

最长公共子序列 LCS

题目给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。例如，"ace" 是 "abcde" 的子序列，但 "aec" ...

动态规划

2020-10-17

0 544

LCP 19. 秋叶收藏集

题目描述小扣出去秋游，途中收集了一些红叶和黄叶，他利用这些叶子初步整理了一份秋叶收藏集 leaves，字符串 leaves 仅包含小写字符 r 和 y，其中字符 r 表示一片红叶，字符 y 表示一片黄叶。出于美观整齐的考虑，小扣想要将收藏集中树叶的排列调整成「红、黄、红」三部分。每部分树叶数...

每日一题动态规划

2020-10-16

0 597

监控二叉树

题目给定一个二叉树，我们在树的节点上安装摄像头。节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。计算监控树的所有节点所需的最小摄像头数量。思路后序遍历，根据子节点的状态设置父节点的状态。若任一子节点未被监视，父节点则需安装摄像头；若任一子节点已安装摄像头，则父节点已被监视且无需安...

树深度优先搜索动态规划

2020-09-22

0 592

最长回文子串

题目给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。代码暴力匹配时间复杂度 O(N^3) 空间复杂度 O(1) public String longestPalindrome(String str) { int n = st...

字符串动态规划

2020-09-19

1 656

组合总和Ⅳ

题目给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。代码深度有限搜索超时 int count; public int combinationSum4(int[] nums, int target) { count = 0; ...

深度优先搜索动态规划回溯

2020-09-09

0 560

货币找零问题

题目你要出去旅游，有N元的预算住酒店，有M家酒店供你挑选，这些酒店都有价格X。需要你正好花完这N元住酒店（不能多，也不能少）最少能住几晚？返回最少住的天数，没有匹配的返回-1 比如你有1000元，所有酒店都是大于1000的，则返回-1 比如你有1000元，有1家1000元的，有1家300，有1...

动态规划背包问题

2020-09-08

0 692

马贼和金矿

题目 A、B两伙马贼意外地在一片沙漠中发现了一处金矿，双方都想独占金矿，但各自的实力都不足以吞下对方，经过谈判后，双方同意用一个公平的方式来处理这片金矿。处理的规则如下：他们把整个金矿分成n段，由A、B开始轮流从最左端或最右端占据一段，直到分完为止。马贼A想提前知道他们能分到多少金子，因此请你帮...

动态规划博弈

2020-09-08

0 571