資訊專欄INFORMATION COLUMN
摘要：題意為取刪去個(gè)字符后最小的值，仍以返回。所以無論刪除個(gè)元素之后的元素放入順序如何，此時(shí)棧內(nèi)元素從底到頂?shù)呐帕幸欢ㄊ菨M足條件的最小值。這種情況下，就要從堆棧頂部刪除剩下的兩個(gè)元素和然后，將棧內(nèi)的元素放入，并將頂部的全部去掉，然后以返回。
Problem
Given string A representative a positive integer which has N digits, remove any k digits of the number, the remaining digits are arranged according to the original order to become a new positive integer.
Find the smallest integer after remove k digits.
N <= 240 and k <= N,
ExampleGiven an integer A = "178542", k = 4
return a string "12"
Note題意為取String A刪去k個(gè)字符后最小的值，仍以String返回。
使用Greedy的解法如下：
首先通過用字符與"0"相減的結(jié)果int cur進(jìn)行數(shù)值大小的比較。然后遍歷整個(gè)字符串，將較小的元素替換棧內(nèi)較大元素并放在棧底，形成一個(gè)從底部到頂端逐漸增大的堆棧。例如0812743456（不考慮刪除元素個(gè)數(shù)k），堆棧的排列從下到上就變成123456了。又例如087123654，k = 2,那么放入堆棧后就變成0123654。
那么，現(xiàn)在就有兩種情況：刪掉的元素?cái)?shù)目小于或等于k。
如果在for循環(huán)中正好刪除了k個(gè)元素，這k個(gè)元素一定是從原字符串A的高位（棧底）開始刪除的。所以無論刪除k個(gè)元素之后的元素放入順序如何，此時(shí)棧內(nèi)元素從底到頂?shù)呐帕幸欢ㄊ菨M足條件的最小值。
如果在for循環(huán)刪除的元素少于k個(gè)，一定是這樣的情況：081234567, k = 3, 在for循環(huán)結(jié)束的時(shí)候只刪除了元素8，因?yàn)槭Ｏ碌脑厥且粋€(gè)完全上升序列01234567。這種情況下，就要從堆棧頂部刪除剩下的兩個(gè)元素6和7.
然后，將棧內(nèi)的元素放入StringBuilder，并將StringBuilder頂部的"0"全部去掉，然后以.toString()返回String。
public class Solution {
public String DeleteDigits(String A, int k) {
if (A == null || A.length() < k) return null;
Stack stack = new Stack();
int deleted = 0;
for (int i = 0; i < A.length(); i++) {
int cur = A.charAt(i) - "0";
while (!stack.isEmpty() && stack.peek() > cur && deleted < k) {
stack.pop();
deleted++;
}
stack.push(cur);
}
while (deleted++ < k) stack.pop();
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty()) sb.insert(0, stack.pop());
while (sb.charAt(0) == "0") sb.deleteCharAt(0);
return sb.toString();
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/65677.html
摘要：建立動(dòng)規(guī)數(shù)組，表示從起點(diǎn)處到達(dá)該點(diǎn)的可能性。循環(huán)結(jié)束后，數(shù)組對所有點(diǎn)作為終點(diǎn)的可能性都進(jìn)行了賦值。和的不同在于找到最少的步數(shù)。此時(shí)的一定是滿足條件的最小的，所以一定是最優(yōu)解。 Jump Game Problem Given an array of non-negative integers, you are initially positioned at the first index...
Problem Given a non-negative number represented as an array of digits, plus one to the number. The digits are stored such that the most significant digit is at the head of the list. Example Given [1,2...
摘要：題目鏈接根據(jù)題目的描述，移掉個(gè)數(shù)字然后得到最小值，肯定是。后面的和需要移掉也是同理。用個(gè)來保存之前遞增的數(shù)字。注意這個(gè)例子，去掉之后，最高位是，也得去掉。 402. Remove K Digits 題目鏈接：https://leetcode.com/problems... 根據(jù)題目的描述，移掉k個(gè)數(shù)字然后得到最小值，肯定是greedy。那么greedy的feature是什么呢？看例子，...
Problem Given a non-negative integer num, repeatedly add all its digits until the result has only one digit. Example Given num = 38.The process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one dig...
Problem Given a string s and a string t, check if s is subsequence of t. You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) ...
閱讀 852·2021-11-16 11:56
閱讀 1676·2021-11-16 11:45
閱讀 3124·2021-10-08 10:13
閱讀 4113·2021-09-22 15:27
閱讀 734·2019-08-30 11:03
閱讀 653·2019-08-30 10:56
閱讀 957·2019-08-29 15:18
閱讀 1750·2019-08-29 14:05
