【华为OD机试 】 找最小数（C++ Java JavaScript Python）

原文链接

【华为OD机试 】 找最小数（C++ Java JavaScript Python）

题目描述

给一个正整数NUM1，计算出新正整数NUM2，NUM2为NUM1中移除N位数字后的结果，需要使得NUM2的值最小。

输入描述

1.输入的第一行为一个字符串，字符串由0-9字符组成，记录正整数NUM1，NUM1长度小于32。
2.输入的第二行为需要移除的数字的个数，小于NUM1长度。

输出描述

输出一个数字字符串，记录最小值NUM2。

用例

C++

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
  string num1;
  int removeCount;
  cin >> num1;
  cin >> removeCount;
  vector<int> arr(num1.size());
  for (int i = 0; i < num1.size(); i++) {
    arr[i] = num1[i] - '0';
  }

  if (arr.size() == removeCount) {
    cout << "0" << endl;
    return 0;
  }

  int remainCount = arr.size() - removeCount;
  vector<int> stack;
  for (int i = 0; i < arr.size(); i++) {
    while (!stack.empty() && removeCount > 0 && stack.back() > arr[i]) {
      stack.pop_back();
      removeCount--;
    }
    stack.push_back(arr[i]);
  }

  while (stack.size() > remainCount) {
    stack.pop_back();
  }

  while (stack[0] == 0 && stack.size() != 1) {
    stack.erase(stack.begin());
  }
  for (auto it : stack) {
    cout << it;
  }
  cout << endl;
  return 0;
}

java

import java.util.Scanner;
import java.util.ArrayList;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String num1 = sc.next();
    int removeCount = sc.nextInt();
    ArrayList<Integer> arr = new ArrayList<>();
    for (int i = 0; i < num1.length(); i++) {
      arr.add(num1.charAt(i) - '0');
    }

    if (arr.size() == removeCount) {
      System.out.println("0");
      return;
    }

    int remainCount = arr.size() - removeCount;
    ArrayList<Integer> stack = new ArrayList<>();
    for (int i = 0; i < arr.size(); i++) {
      while (!stack.isEmpty() && removeCount > 0 && stack.get(stack.size()-1) > arr.get(i)) {
        stack.remove(stack.size()-1);
        removeCount--;
      }
      stack.add(arr.get(i));
    }

    while (stack.size() > remainCount) {
      stack.remove(stack.size()-1);
    }

    while (stack.get(0) == 0 && stack.size() != 1) {
      stack.remove(0);
    }

    for (int it : stack) {
      System.out.print(it);
    }
    System.out.println();
  }
}

javaScript

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

rl.on('line', (num1) => {
  rl.once('line', (removeCountInput) => {
    let removeCount = Number(removeCountInput);
    const arr = [...num1].map(Number);

    if (arr.length === removeCount) {
      console.log('0');
      return;
    }

    const remainCount = arr.length - removeCount;
    const stack = [];
    for (let i = 0; i < arr.length; i++) {
      while (stack.length > 0 && removeCount > 0 && stack[stack.length - 1] > arr[i]) {
        stack.pop();
        removeCount--;
      }
      stack.push(arr[i]);
    }

    while (stack.length > remainCount) {
      stack.pop();
    }

    while (stack[0] === 0 && stack.length !== 1) {
      stack.shift();
    }

    console.log(stack.join(''));
  });
});

python

num1=input()
removeCount=int(input())
arr = list(map(int, num1))

if len(arr) == removeCount:
    print('0')
    exit()

remainCount = len(arr) - removeCount
stack = []
for i in range(len(arr)):
    while stack and removeCount > 0 and stack[-1] > arr[i]:
        stack.pop()
        removeCount -= 1
    stack.append(arr[i])

while len(stack) > remainCount:
    stack.pop()

while stack[0] == 0 and len(stack) != 1:
    stack.pop(0)
print(''.join(str(i) for i in stack))

2522011411@qq.com普通

打赏 收藏 海报 链接