当前位置:网站首页>402. 移掉 K 位数字-贪心
402. 移掉 K 位数字-贪心
2022-04-23 17:32:00 【hequnwang10】
一、题目描述
给你一个以字符串表示的非负整数 num 和一个整数 k ,移除这个数中的 k 位数字,使得剩下的数字最小。请你以字符串形式返回这个最小的数字。
示例 1:
输入:num = "1432219", k = 3
输出:"1219"
解释:移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。
示例 2:
输入:num = "10200", k = 1
输出:"200"
解释:移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
示例 3:
输入:num = "10", k = 2
输出:"0"
解释:从原数字移除所有的数字,剩余为空就是 0 。
二、解题
贪心
class Solution {
public String removeKdigits(String num, int k) {
if (num == null || num.length() == 0) {
return num;
}
int length = num.length();
if (k <= 0 || k > length) {
return num;// 非法
}
if (k == length) {
return "0";
}
char[] chars = num.toCharArray();
char[] newChars = new char[length]; // 移除k个数字的结果
int newCharsTop = 0;
for (int i = 0; i < length; i++) {
while (k > 0 && newCharsTop > 0 && newChars[newCharsTop - 1] > chars[i]) {
newCharsTop--;
k--; // 移除一个数字
}
newChars[newCharsTop] = chars[i];
newCharsTop++;
}
if (k > 0) {
// 从后面移除k个数字
newCharsTop = newCharsTop - k;
k = 0;
}
// 起始位置不能是0
int startIndex = 0;
while (newChars[startIndex] == '0' && startIndex < newCharsTop) {
startIndex++;
}
// 从起始位置返回 newCharsTop - startIndex
if (newCharsTop - startIndex > 0) {
return new String(newChars, startIndex, newCharsTop- startIndex);
}
return "0";
}
}
版权声明
本文为[hequnwang10]所创,转载请带上原文链接,感谢
https://blog.csdn.net/hequnwang10/article/details/124361302
边栏推荐
- Devexpress GridView add select all columns
- JS failed to change all variables and changed to the return method. Finally, the problem was solved
- stm32入门开发板选野火还是正点原子呢?
- C dapper basically uses addition, deletion, modification and query transactions, etc
- Shell-awk命令的使用
- How to use the input table one-way service to send (occupy less) picture files (body transmission)? FileReader built-in object involved
- Indexes and views in MySQL
- Websocket (basic)
- Metaprogramming, proxy and reflection
- Solution of Navicat connecting Oracle library is not loaded
猜你喜欢
stm32入门开发板选野火还是正点原子呢?
Bottom processing of stack memory in browser
Use of todesk remote control software
Using quartz under. Net core -- job attributes and exceptions of [4] jobs and triggers
On lambda powertools typescript
Lock lock
Simulation of infrared wireless communication based on 51 single chip microcomputer
[logical fallacy in life] Scarecrow fallacy and inability to refute are not proof
.Net Core3. 1 use razorengine NETCORE production entity generator (MVC web version)
练习:求偶数和、阈值分割和求差( list 对象的两个基础小题)
随机推荐
[simple understanding of database]
2. Electron's HelloWorld
Use of five routing guards
JS to find the character that appears three times in the string
ASP. Net core JWT certification
Use of shell sed command
Qt error: /usr/bin/ld: cannot find -lGL: No such file or directory
. net type transfer
给 el-dialog 增加拖拽功能
C语言程序设计之函数的构造
How to manually implement the mechanism of triggering garbage collection in node
练习:求偶数和、阈值分割和求差( list 对象的两个基础小题)
How to sort the numbers with text in Excel from small to large instead of the first number
Allowed latency and side output
常用SQL语句总结
Conversion between hexadecimal numbers
Model problems of stock in and stock out and inventory system
C listens for WMI events
Baidu Map Case - Zoom component, map scale component
In ancient Egypt and Greece, what base system was used in mathematics