# 贪心算法
贪婪法(greedy algorithm),又称贪心算法,是寻找最优解问题的常用方法。这种方法模式一般将求解过程分成若干个步骤,在每个步骤都应用贪心原则,选取当前状态下最好的或最优的选择(局部最有利的选择),并以此希望最后堆叠出的结果也是最好或最优的解。
贪婪法和动态规划法以及分治法一样,都需要对问题进行分解,定义最优解的子结构。但是,贪婪法与其他方法最大的不同在于,贪婪法每一步选择完之后,局部最优解就确定了,不再进行回溯处理,也就是说,每一个步骤的局部最优解确定以后,就不再修改,直到算法结束。因为不进行回溯处理,贪婪法只在很少的情况下可以得到真正的最优解,比如最短路径问题、图的最小生成树问题。大多数情况下,由于选择策略的“短视”,贪婪法会错过真正的最优解,得不到问题的真正答案。但是贪婪法简单高效,省去了为找最优解可能需要的穷举操作,可以得到与最优解比较接近的近似最优解,通常作为其他算法的辅助算法使用。
贪婪法的基本设计思想有以下三个步骤。
- 建立对问题精确描述的数学模型,包括定义最优解的模型;
- 将问题分解为一系列子问题,同时定义子问题的最优解结构;
- 应用贪心原则确定每个子问题的局部最优解,并根据最优解的模型,用子问题的局部最优解堆叠出全局最优解。
# 1663.具有给定数值的最小字符串
中等
小写字符的数值 是它在字母表中的位置(从 1 开始),因此 a 的数值为 1 ,b 的数值为 2 ,c 的数值为 3 ,以此类推。
字符串由若干小写字符组成,字符串的数值 为各字符的数值之和。例如,字符串 "abe" 的数值等于1 + 2 + 5 = 8
。
给你两个整数 n 和 k 。返回长度等于 n 且数值等于 k 的字典序最小的字符串。详细 (opens new window)
/**
* @param {number} n
* @param {number} k
* @return {string}
*/
var getSmallestString = function(n, k) {
const s = new Array(n).fill('a');
k = k - n;
for (let i = n-1; i >= 0 && k > 0; --i) {
if (k > 25) s[i] = 'z', k -= 25;
else s[i] = String.fromCharCode(97+k), k -= k;
}
return s.join('');
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14