算法

Posted on Edited on In

.

动态规划

1
2
3
4
5
6
7
8
9
10
11
有一排深渊法师，他们的护盾值用数组 a 表示；
你可以对深渊法师这样破盾：
1) 用重击破盾，每消耗1MP破1点护盾
2) 如果有两个相邻的深渊法师他们的元素不同，且护盾都不为0，你可以对他们俩使用高天之歌，消耗xMP破所有护盾
问最少消耗的MP？
下面输入的 els 表示深渊法师的元素，I 表示冰，W 表示水，F 表示火

输入：
a = [4, 8, 10, 2, 15, 2]
x = 9
els = WIFFII
1
dp[i]=min(dp[i-1]+a[i],dp[i-2]+x) if 能使用高天之歌 else dp[i-1]+a[i]

找规律题目

找规律后拼接

构建长度为n的字符串

1
2
3
4
5
6
A希望你构造一个长度为n的数组，满足以下条件：
1. 所有元素绝对值不大于3
2. 相邻两个元素乘积小于0，且和不为0
3. 所有元素之和=0
input: 2 output:no answer
input: 3 output: -1 2 -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
根据题目信息：
1. 数组的元素在{1,2,3}里挑选
2. 数组相邻元素一个为正一个为负，且互不相等，正号组和负号组可以互换。
3. 正负号数值和相同，且可拼接！！！因为0+0=0

考虑拼接条件：只要首尾元素不相同就可以拼接！！

开始找规律以及能用于拼接的元素：
input: 2 output:no answer
input: 3 output: -1 3 -2（这个可以用于拼接，首位元素不同） -1 2 -1（这个不可以）
input: 4 output: -1 2 -3 2（这个可以用于拼接，首位元素不同）
input: 5 output: no answer
我们发现所以大于5的数都可以由若干个3和若干个4相加得到，且3、4中有答案可以随意拼接，所以我们能利用3、4的答案拼接出n>5的满足条件的数组

拼接mhy字符串

1
2
3
4
5
6
7
如果不能定义：字符串的“权重”是字符串中出现的字符种类数量，比如 mmm 权重为1，mmh 为 2，mhy 为 3
输入：x, y, z 三个变量
输出：一个长度为 x + y + z + 2 的字符串，这个字符串只能由 m h y 三种字符组成，这个字符串一共有 x + y + z 个长度为 3 的子串，其中有 x 个权重为 1 的子串，y 个权重为 2 的子串，z 个权重为 3 的子串。
只用输出一种情况，若无法组成，输出-1

范例输入：x = 2, y = 1, z = 1
范例输出：mmmmhy
1
2
3
4
5
1. 找规律，发现权重3字符串后只能接权重2或权重3的字符串，不能跟权重1；所以如果x,z>0,y=0这种情况无解
2. 我们可以先拼接权重3字符串（若有）mhymhy...
3. 然后拼接权重2，mhymhyhyhy...；如果无权重三直接拼接权重2,hyhyh....
4. 只剩下一个权重2没拼时，拼一个可以接权重1的权重2，mhymhyhyhyy
5. 拼接权重1：mhymhyhyhyyyyyyy

找规律后计算

1
2
3
A拿到了3元无限长字符串{1,2,3；4,5,6；7,8,9；....}
其中3的倍数后用；分割，其他用逗号
求l个字符到r个字符之间有几个逗号和分号。
1
2
3
4
5
6
7
8
1. 求l到r字符之间有几个逗号分号——》r前逗号分号-l前逗号分号
2. 难点：数字为1-9时，每个数字只占1个字符，为10-99，每个数字就占两个字符了。
	开始找规律！
	1-9			每6个字符为一组{1,2,3;}			这样的组有3个
	10-99		每9个字符为一组{10,11,12;}			这样的组有30个
	100-999		每12个字符为一组{100,111,112;}		这样的组有300个
	以此类推

审题题

交换字母使字典序尽可能大

1
2
3
4
5
A拿到一个仅有小写字母组成的字符串，她准备进行恰好一次操作：交换连个相邻字母，在操作结束后使字符串的字典序尽可能大。

input: ba
output: ab
2<=len(input)<=200000

知识点：

  1. 字典序，就是按照字典排列顺序，英文字母按下面方式排列：

    1
    2
    ABCDEFG HIJKLMN OPQRST UVWXYZ
    abcdefg hijklmn opqrst uvwxyz

  2. 题目说的是恰好一次操作！！！！就算交换之后会让原来字符串字典序减小也需要进行操作！

寻找用例

1
2
3
4
5
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

  1. 找正例

    1
    2
    输入：coins = [1, 2, 5], amount = 11
    输出：3

  2. 找负例

    1
    2
    输入：coins = [2], amount = 3
    输出：-1

  3. 找边界条件

    1
    2
    输入：coins = [1], amount = 0
    输出：0