试题一

给出n个数字组成的字符串，移走k个字符，求剩下的字符组成的最小数字；

示例

• 字符串：132，移走1个字符， 输出：12
• 字符串：001032，移走2个字符，输出： 2
• 字符串： 132450， 移走2个字符，输出：1240

解答

移走k个字符，可以转换为移走1个字符，移k次，每一次都让剩下的字符组成的数字最小；

这样转换意味着，每次操作的最优解，就是多次操作同时进行后的最优解（局部最优累积成为全局最优），需要对此进行证明，之后我们会使用严格的数学推导方式得出操作的规律，从而证明局部最优累积为全局最优；

这可以理解为贪心算法的思想，但本题目是有严格解的，并不是绝对的贪心算法；

先看移走1个字符的情形：

设n个字符，排列顺序为$a_{1}a_{2}...a_{n}$，$a_{1}\neq 0$, 那么该字符串表示的数字为

如果移走的字符是$a_{i}$， $1\leqq i\leqq n$，则剩下的字符组成的数字为

从f(i)的表达式不容易看出问题，但Sn和f(i)之间是存在关系的，且Sn是固定值，因此计算差值

如果要求f(i)最小，$\Delta S_{i}$则要求最大；

所以，我们需要观察$\Delta S_{i}$的表达式，找到跟i的规律；

• 从表达式来看，如果我们从高位到低位来移动字符（即从第一位到最后一位的顺序），每移动后一位字符时，就会多出一个$(a_{i}-a_{i-1})\times 10^{n-i}$项，而对于未知的数字，并不能判断$(a_{i}-a_{i-1})$是否＞0，所以应该分情况讨论；

  • 如果$(a_{i}-a_{i-1})>0$，那么就继续向第i+1个字符的方向观察，因为此时多出来的那一项是正数，只会让$\Delta S_{i}$越来越大；
  • 如果$(a_{i}-a_{i-1})<0$，那么就要移走第i-1个字符了，防止出现负数；

• 另外，从表达式来看，高位的权重大（a1的权重是$10^{n-1}$），应该从高位来开始判断；

  • 如果a2 < a1，那么不能让(a2-a1)出现，则要移走a1即可；
  • 如果a2 > a1, 那么继续看a3和a2的关系，重复本过程；

所以，综上所述，应该从最高位开始判断，一旦出现$a_{i}<a_{i-1}$, 那么就移动$a_{i-1}$，否则继续判断下一位；

再看移走k个字符

移走k个字符的情况，表达式中无非就是缺少了某些项，但跟移走1个字符的思路是一致的，规律是一致的，因此移走k个字符与移动k次，每次移走1个字符是等效的；

程序设计

/**
 * 
 * @param {*} inputStr: string，满足/[0-9]{n}/正则规则， 例如132450
 * @param {*} k: integer, k 应该小于inputStr去除开头为0的字符后的长度，例如inputStr为00132450, k < 6而不是8
 */
function minimize(inputStr, k) {
  // 先去除字符串开头的0
  let handledArr = inputStr.split('');
  while(handledArr[0] === '0') {
    handledArr = handledArr.slice(1);
  }
  // 开始取走字符
  for(let i = 0; i < k; i ++) {
    let j = 0;
    while (handledArr[j] < handledArr[j + 1]) {
      j ++;
    }
    handledArr.splice(j, 1);
  }
  while(handledArr[0] === '0') {
    handledArr = handledArr.slice(1);
  }
  return handledArr.join('');
}