402. Remove K Digits

sf190404 发布于2019-08-14 17:26 / 2135人阅读

摘要：题目链接根据题目的描述，移掉个数字然后得到最小值，肯定是。后面的和需要移掉也是同理。用个来保存之前递增的数字。注意这个例子，去掉之后，最高位是，也得去掉。

402. Remove K Digits

题目链接：https://leetcode.com/problems...

根据题目的描述，移掉k个数字然后得到最小值，肯定是greedy。那么greedy的feature是什么呢？
看例子，首先是1432219，k = 3，不去掉1的原因是后面接的是4，当前这一步，看到下一个数比自己大的时候移掉是不划算的，因为移掉这个数之后最高位变成4，是不如保留1小的。所以可以看出规律实际上是从msb开始只要发现比之前有比当前位大的数字，那肯定要移掉之前的数字，这样当前最高位的数字就变小了。后面的3和2需要移掉也是同理。用个Stack来保存之前递增的数字。
再看1223，k = 1，从左往右扫一遍发现没有出现nums[i-1] > nums[i]的情况，所以第一次扫的时候删了0个，这时候就从最大值开始移。
注意10200这个例子，去掉1之后，最高位是0，也得去掉。

public class Solution {
    public String removeKdigits(String num, int k) {
        StringBuilder sb = new StringBuilder();
        int n = num.length();
        char[] stack = new char[n];
        int count = 0;
        // remove the digit that larger than digit after it
        for(int i = 0; i < n; i++) {
            while(count != 0 && k > 0 && num.charAt(i) < stack[count-1]) {
                count--;
                k--;
            }
            stack[count++] = num.charAt(i);
        }
        // remove 0 at the beginning
        int start = 0;
        while(start < count && stack[start] == "0") start++;
        
        // remove from lsb
        return start >= count - k ? "0" : new String(stack, start, count - start - k);
    }
}

云服务器 GPU云服务器 v402 Digits remove remove()方法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66638.html

leetcode402. Remove K Digits

摘要：当我们用尽了所有删除时，就保留后面所有的数字，不再进行任何比较。因为我们已经尽可能获得了最小的最高位，因此无论后面的数字如何取值，其最高位上的数字一定是可以获得的最小的这个数字。题目要求 Given a non-negative integer num represented as a string, remove k digits from the number so that t...

paraller 2019-08-16 15:38 评论0 收藏0
316. Remove Duplicate Letters and 402. Remove K Di

摘要：每个字母只留一个，而且保证字典序最小。从前往后扫描，还要往前看一个检出是否删除的，要用解。需要一个数据结构记录是否使用这个字母，可以用。结构也可以用数组加顶点指针模拟。 316 Remove Duplicate Given a string which contains only lowercase letters, remove duplicate letters so that e...

novo 2019-08-14 18:01 评论0 收藏0
[LintCode] Delete Digits [Greedy]

摘要：题意为取删去个字符后最小的值，仍以返回。所以无论删除个元素之后的元素放入顺序如何，此时栈内元素从底到顶的排列一定是满足条件的最小值。这种情况下，就要从堆栈顶部删除剩下的两个元素和然后，将栈内的元素放入，并将顶部的全部去掉，然后以返回。 Problem Given string A representative a positive integer which has N digits,...

张汉庆 2019-08-14 15:21 评论0 收藏0
前端每日实战：164# 视频演示如何用原生 JS 创作一个数独训练小游戏（内含 4 个视频）

摘要：第部分第部分第部分第部分源代码下载每日前端实战系列的全部源代码请从下载代码解读解数独的一项基本功是能迅速判断一行一列或一个九宫格中缺少哪几个数字，本项目就是一个训练判断九宫格中缺少哪个数字的小游戏。 showImg(https://segmentfault.com/img/bVbkNGa?w=400&h=300); 效果预览按下右侧的点击预览按钮可以在当前页面预览，点击链接可以全屏预...

Heier 2019-08-23 13:57 评论0 收藏0
前端每日实战：164# 视频演示如何用原生 JS 创作一个数独训练小游戏（内含 4 个视频）

摘要：第部分第部分第部分第部分源代码下载每日前端实战系列的全部源代码请从下载代码解读解数独的一项基本功是能迅速判断一行一列或一个九宫格中缺少哪几个数字，本项目就是一个训练判断九宫格中缺少哪个数字的小游戏。 showImg(https://segmentfault.com/img/bVbkNGa?w=400&h=300); 效果预览按下右侧的点击预览按钮可以在当前页面预览，点击链接可以全屏预...

OBKoro1 2019-08-30 15:54 评论0 收藏0