网站建设使用的什么软件有哪些,优质网站策划,怎样给网站做超链接,泉州做网站优化的公司问题描述 给定一个高精度的正整数 n#xff08;n≤1000 位#xff09;#xff0c;需要删除其中任意 s 个数字#xff0c;使得剩下的数字按原左右顺序组成一个新的正整数#xff0c;并且这个新的正整数最小。例如#xff0c;对于数字 153748#xff0c;删除 2 个数字后n≤1000 位需要删除其中任意 s 个数字使得剩下的数字按原左右顺序组成一个新的正整数并且这个新的正整数最小。例如对于数字 153748删除 2 个数字后最小的数是 1348。 解题思路 1. 贪心算法 要解决这个问题我们可以使用贪心算法。贪心算法在每一步选择中都采取在当前状态下最好或最优即最有利的选择从而希望导致结果是全局最好或最优的。 2. 维护单调递增栈 我们可以通过维护一个单调递增的栈来实现这个目标。具体步骤如下 2.1 初始化栈 创建一个空栈 stack用于存储最终结果中的数字。 2.2 遍历每个数字 遍历输入的高精度正整数 n 的每一位数字 num。 2.3 维护单调递增栈 弹出条件当栈不为空stack且还需要删除数字s 0且栈顶元素大于当前数字stack[-1] num时弹出栈顶元素并减少 s 的值。这样做的目的是尽可能地让结果数的高位更小从而使得整个数更小。 入栈操作将当前数字 num 入栈。这一步是为了保留当前数字以便后续继续判断。 2.4 处理剩余的删除操作 遍历结束后如果 s 还大于0说明原数是单调递增的。在这种情况下直接去掉末尾的 s 个数字即可。因为从末尾去掉数字对结果数的影响最小。 2.5 拼接结果并处理前导0 拼接结果将栈中的数字拼接成一个字符串。 处理前导0使用 lstrip(0) 去掉前导0。如果去掉前导0后字符串为空即原数删除后只剩下0则返回 0。 3. 示例解释 以 n 153748 和 s 2 为例详细说明每一步的操作 初始化栈stack []。 遍历每一位数字 num 1栈为空直接入栈。stack [1]。 num 5栈顶元素 1 小于 5直接入栈。stack [1, 5]。 num 3栈顶元素 5 大于 3弹出 5s 减1。stack [1]。然后 3 入栈。stack [1, 3]。 num 7栈顶元素 3 小于 7直接入栈。stack [1, 3, 7]。 num 4栈顶元素 7 大于 4弹出 7s 减1。stack [1, 3]。然后 4 入栈。stack [1, 3, 4]。 num 8栈顶元素 4 小于 8直接入栈。stack [1, 3, 4, 8]。 遍历结束后s 为0不需要再处理。 拼接结果并处理前导0.join(stack).lstrip(0)结果为 1348。 最终结果为 1348这是删除2个数字后得到的最小数。 4. 代码实现 def min_number_after_delete(n, s):删除s个数字后得到的最小数:param n: 原始高精度正整数字符串形式:param s: 需要删除的数字个数:return: 删除s个数字后得到的最小数字符串形式stack []# 遍历每个数字for num in n:# 当栈不为空且s大于0且栈顶元素大于当前数字时弹出栈顶元素while stack and s 0 and stack[-1] num:stack.pop()s - 1# 当前数字入栈stack.append(num)# 如果s还大于0说明原数是单调递增的直接去掉末尾的s个数字即可if s 0:stack stack[:-s]# 将栈中的数字拼接成字符串并去掉前导0return .join(stack).lstrip(0) or 0# 示例
n 153748
s 2
print(min_number_after_delete(n, s)) # 输出1348n 1087
s 1
print(min_number_after_delete(n, s)) # 输出87 5. 总结 通过维护一个单调递增的栈我们可以有效地找到删除 s 个数字后得到的最小数。这种方法的时间复杂度为 O(n)其中 n 是输入数字的长度因为每个数字最多只会被入栈和出栈一次。希望这个解释能帮助你更好地理解这个问题的解法。如果有任何疑问欢迎继续提问。
