小于n的最大数

liang302 / 2024-09-22 / 原文

贪心+回溯：
找某位的最小值的时候用set实现的二分

求hack

#include <algorithm>
#include <unordered_set>
#include <vector>
#include <iostream>
using namespace std;
// getMaxDigitLtD 获取小于指定数字的最大数字。
int getMaxDigitLtD(const vector<int> &digits, int digit) {
  for (auto it = digits.rbegin(); it != digits.rend(); it++) {
    if (*it < digit) {
      return *it;
    }
  }
  return -1;
}

// getMaxNumLtN 获取小于 n 的最大数。
int getMaxNumLtN(vector<int> &digits, int n) {
  // 获取 n 的每一位数字。12345
  vector<int> ndigits;
  while (n > 0) {
    ndigits.push_back(n % 10);
    n /= 10;
  }
  // 排序给定的数字数组。 5 4 3 2 1 
  sort(digits.begin(), digits.end());
  // 数字写入 map 用于快速查看是否存在。
  unordered_set<int> set;
  for (auto v : digits) {
    set.insert(v);
  }

  // 目标数的每一位数字。
  vector<int> tdigits(ndigits.size());

  // 从原数字高位到低位遍历，尽可能地取相同值，除了最后一位，最后一位需要比他小。
  for (int i = ndigits.size() - 1; i >= 0; i--) {
    // 存在相同的数字，可以直接看下一位（最后一位除外）。
    if (i > 0 && set.find(ndigits[i]) != set.end()) {
      tdigits[i] = ndigits[i];
      continue;
    }
    
    // 找不到相同的数字，那就找到存在小于当前位的最大数字。
	// 如果最高位真的找到比他小的而且不是0的，说明之后数字都可以取nums最大 ,break 
    // 123 直接放99 
	// 213 直接放09 
    auto d = getMaxDigitLtD(digits, ndigits[i]);
    if (d != -1) {
      tdigits[i] = d;
      break;
    }
    
	// 需要回溯。数组{2} target:219 2xy
	// 现在x=2就已经无敌了  
    for (i++; i < ndigits.size(); i++) {
      tdigits[i] = 0;
      // 小于当前位的最大数字。
      d = getMaxDigitLtD(digits, ndigits[i]);
      if (d > 0) {
        tdigits[i] = d;
        break;
      }
      // 最高位也没有小于其的最大数字。
      if (i == ndigits.size() - 1) {
        tdigits.resize(tdigits.size() - 1);
      }
    }
    break;
  }

  // 拼装目标数。
  int target = 0;
  for (int i = tdigits.size() - 1; i >= 0; i--) {
    target *= 10;
    if (tdigits[i] > 0) {  
      target += tdigits[i];
      continue;
    }
    // 取数字数组中最大的数字。
    target += digits.back();
  }
  return target;
}

int main() {
	
	
  auto digits = vector<int>{5, 9};
  cout << getMaxNumLtN(digits, 5555) << endl;
  
  
  digits = vector<int>{0, 2, 9, 4};
  cout << getMaxNumLtN(digits, 2533) << endl;

  digits = vector<int>{1, 2, 5, 4};
  cout << getMaxNumLtN(digits, 2543) << endl;

  digits = vector<int>{1, 2, 5, 4};
  cout << getMaxNumLtN(digits, 2541) << endl;

  digits = vector<int>{1, 2, 9, 4};
  cout << getMaxNumLtN(digits, 2111) << endl;

	  
}