1 | 给定一个无重复元素的有序整数数组 nums 。 |
1 | class Solution { |
1 | 给定一个无重复元素的有序整数数组 nums 。 |
1 | class Solution { |
1 | 给你一个整数 n ,请你找到满足下面条件的一个序列: |
回溯填充index和index+n的位置,每次填充都从最大的数字开始,使用visit保存已经填充过的元素
1 | public class Solution { |
1 | 给你一个字符串 s 和两个整数 x 和 y 。你可以执行下面两种操作任意次。 |
假设消除ab的收益最大,如果不是,则转换成消除ab的收益最大
如果遇到一个a,字符a的计数增加
如果遇到一个b,并且字符a的数量大于零,那么字符a的数量减去1,结果加上消除a的收益x
如果遇到一个b,并且字符a的数量等于零,那么字符b的数量加上1
ab消除完成后,消除ba,查看字符a与字符b的数量的最小值,即能消除的最大的数目再乘以y
1 | class Solution { |
1 | 设计一种算法,打印 N 皇后在 N × N 棋盘上的各种摆法,其中每个皇后都不同行、不同列,也不在对角线上。这里的“对角线”指的是所有的对角线,不只是平分整个棋盘的那两条对角线。 |
对角线的计算方式是
主对角线的计算方式是:row-cloumn
在主对角线上的点的坐标的row-column
的差值相同
副对角线的计算方式是:row+column
在副对角线上的点的坐标的row+column
的差值相同
1 | class Solution { |
1 | 给定数量不限的硬币,币值为25分、10分、5分和1分,编写代码计算n分有几种表示法。(结果可能会很大,你需要将结果模上1000000007) |
背包问题:
用 $f(i,v)$ 来表示前 $i$ 种面值的硬币构成面值为 $v$ 的方案数量,用 $c_i$来表示第 i种面值的硬币的面值。
我们可以从 $f(i - 1, v - 0 \times c_i)$,$f(i - 1, v - 1 \times c_i)$, $f(i - 1, v - 2 \times c_i)\cdots$ $f(i - 1, v - k \times c_i)$转移得到,它们表示第 $i$ 个面值的硬币选 $0, 1, 2 \cdots k$ 个的时候,构成面值为 $v$ 的方案数量,其中 $k$ 为满足 $v - k \times c_i \geq 0$的最大整数。于是我们可以推导出这样的动态规划转移方程:
$f(i, v)=\sum_{j=0}^{k} f(i-1, v-j \times c i), k=\left\lfloor\frac{v}{c i}\right\rfloor$
举个例子: 假设这里 $c = {1, 5, 10, 25}$,在$i = 4$ 的时候,$c_i = 25$(假设下标从 $1$ 开始),如果我们要求前 $4$ 种面值构成 $90$ 的方案数量,可以这么写:
$f(4, 90) = f(3, 90) + f(3, 90 - 25) + f(3, 90 - 2 \times 25) + f(3, 90 - 3 \times 25)$
优化时间复杂度:
$f(i, v)=f(i-1, v)+f\left(i-1, v-c_{i}\right)+f\left(i-1, v-2 c_{i}\right) \cdots f\left(i-1, v-k c_{i}\right)$
共 $k + 1$ 项,其中 $k = \lfloor \frac{v}{c_i} \rfloor$ 那么我们可以得到使用 $v - c_i$替换 $v$,得到:
$f\left(i, v-c_{i}\right)=f\left(i-1, v-c_{i}\right)+f\left(i-1, v-2 c_{i}\right)+f\left(i-1, v-3 c_{i}\right) \cdots f\left(i-1, v-k c_{i}\right)$
共 $k$ 项。注意到上面两个方程中标成红色的 $k$ 项是完全相同的,于是我们可以用下面式子的左半部分 $f(i, v - c_i)$等价替换上面式子红色的 $k$ 项,得到化简后的转移方程:
$f(i, v) = f(i - 1, v) + f(i, v - c_i)$
1 | class Solution{ |
1 | class Solution{ |
1 | class Solution { |
1 | 作者:LeetCode-Solution |
1 | 给定一个方阵,其中每个单元(像素)非黑即白。设计一个算法,找出 4 条边皆为黑色像素的最大子方阵。 |
1 | class Solution { |
1 | class Solution { |
1 | 给定字典中的两个词,长度相等。写一个方法,把一个词转换成另一个词, 但是一次只能改变一个字符。每一步得到的新词都必须能在字典中找到。 |
这是单词接龙的题目,依旧超时,不过注释掉vis回溯,就可以通过
因为如果某个节点不可达最终节点,那么该节点在以后也不可达,所以应将其去掉
1 | class Solution { |
利用map维护一个链表,每个链表中对应当前元素的转移状态
1 | class Solution { |
如果使用两个同时进行的广搜可以有效地减少搜索空间。一边从 beginWord 开始,另一边从 endWord 开始。我们每次从两边各扩展一层节点,当发现某一时刻两边都访问过同一顶点时就停止搜索。这就是双向广度优先搜索,它可以可观地减少搜索空间大小,从而提高代码运行效率。
1 | class Solution { |
参考文献
作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/word-ladder/solution/dan-ci-jie-long-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
1 | 给定一个较长字符串big和一个包含较短字符串的数组smalls,设计一个方法,根据smalls中的每一个较短字符串,对big进行搜索。输出smalls中的字符串在big里出现的所有位置positions,其中positions[i]为smalls[i]出现的所有位置。 |
1 | class Solution { |
1 | class TrieNode{ |
1 | class Solution { |
1 | 有个马戏团正在设计叠罗汉的表演节目,一个人要站在另一人的肩膀上。出于实际和美观的考虑,在上面的人要比下面的人矮一点且轻一点。已知马戏团每个人的身高和体重,请编写代码计算叠罗汉最多能叠几个人。 |
1 | public int bestSeqAtIndex(int[] height, int[] weight) { |
1 | class Solution { |
1 | import java.util.Arrays; |
tag:
缺失模块。
1、请确保node版本大于6.2
2、在博客根目录(注意不是yilia根目录)执行以下命令:
npm i hexo-generator-json-content --save
3、在根目录_config.yml里添加配置:
jsonContent: meta: false pages: false posts: title: true date: true path: true text: false raw: false content: false slug: false updated: false comments: false link: false permalink: false excerpt: false categories: false tags: true