Leetcode: Remove K Digits
LeetCode remove digits
2023-09-11 14:14:07 时间
Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible. Note: The length of num is less than 10002 and will be ≥ k. The given num does not contain any leading zero. Example 1: Input: num = "1432219", k = 3 Output: "1219" Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest. Example 2: Input: num = "10200", k = 1 Output: "200" Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes. Example 3: Input: num = "10", k = 2 Output: "0" Explanation: Remove all the digits from the number and it is left with nothing which is 0.
Greedy + Stack: 用一个栈维护最后要留存下来的digits
需要注意的是:如果遍历到string的某个char, string后面的char数刚刚好能填满这个栈,那么即使这个char比栈顶还要小,也不出栈,直接入栈
最后要删除leading 0
1 public class Solution { 2 public String removeKdigits(String num, int k) { 3 if (num.length()==0 || k>=num.length()) return "0"; 4 char[] arr = num.toCharArray(); 5 Stack<Character> stack = new Stack<Character>(); 6 StringBuilder res = new StringBuilder(); 7 int size = arr.length - k; 8 for (int i=0; i<arr.length; i++) { 9 while (!stack.isEmpty() && arr[i]<stack.peek() && (size-stack.size()+1 <= arr.length-i)) { 10 stack.pop(); 11 } 12 if (size > stack.size()) 13 stack.push(arr[i]); 14 } 15 while (!stack.isEmpty()) { 16 res.insert(0, stack.pop()); 17 } 18 while (res.length()>1 && res.charAt(0)=='0') res.deleteCharAt(0); 19 return res.toString(); 20 } 21 }
用char[]实现栈,思路一样,要快很多,beat96%
1 public class Solution { 2 public String removeKdigits(String num, int k) { 3 int remain = num.length() - k; 4 char[] numArray = num.toCharArray(), res = new char[remain]; 5 int index = 0; 6 for(int i = 0; i < numArray.length; i++) { 7 while((numArray.length - i > remain - index) && (index > 0 && numArray[i] < res[index - 1])) index--; 8 if(index < remain) res[index++] = numArray[i]; 9 } 10 11 // check leading zeroes 12 index = -1; 13 while(++index < remain) { 14 if(res[index] != '0') break; 15 } 16 String s = new String(res).substring(index); 17 18 return s.length() == 0 ? "0" : s; 19 } 20 }
相关文章
- Leetcode: LFU Cache && Summary of various Sets: HashSet, TreeSet, LinkedHashSet
- Leetcode: Serialize and Deserialize BST
- Leetcode: Remove Linked List Elements
- Leetcode: Wildcard Matching
- Leetcode: Remove Nth Node From End of List
- Leetcode: Remove Duplicates from Sorted List
- Leetcode: Remove Duplicates from Sorted Array
- LeetCode 83:Remove Duplicates from Sorted List
- [LeetCode] Remove Duplicates from Sorted List II
- [LeetCode] Combinations
- [LeetCode] Remove Duplicates from Sorted Array
- (看懂LeetCode)1. 两数之和
- 每日leetcode算法题:1两数之和
- 【LeetCode】241. Different Ways to Add Parentheses
- 【LeetCode】82. Remove Duplicates from Sorted List II
- 【LeetCode】80. Remove Duplicates from Sorted Array II (2 solutions)
- [Leetcode]-Remove Duplicates from Sorted Array
- LeetCode——Remove Nth Node From End of List
- [LeetCode] 1249. Minimum Remove to Make Valid Parentheses 移除无效的括号
- [LeetCode] 1175. Prime Arrangements 质数排列
- [LeetCode] 1171. Remove Zero Sum Consecutive Nodes from Linked List 从链表中删去总和值为零的连续节点
- [LeetCode] 1007. Minimum Domino Rotations For Equal Row 行相等的最少多米诺旋转
- [LeetCode] 546. Remove Boxes 移除盒子
- [LeetCode] 301. Remove Invalid Parentheses 移除非法括号
- [LeetCode] 19. Remove Nth Node From End of List 移除链表倒数第N个节点
- [LeetCode] 27. Remove Element 移除元素
- [LeetCode] Remove Linked List Elements 移除链表元素
- [LeetCode] 80. Remove Duplicates from Sorted Array II 有序数组中去除重复项之二
- [LeetCode] 189. Rotate Array 旋转数组
- [LeetCode] Fraction to Recurring Decimal 分数转循环小数
- Leetcode——26. Remove Duplicates from Sorted Array
- leetcode 83. Remove Duplicates from Sorted List 删除排序链表中的重复元素(简单)
- leetcode算法125.验证回文串