LeetCode(每日练习)-402. 移掉 K 位数字、316. 去除重复字母、1081. 不同字符的最小子序列、321. 拼接最大数

亦凉 2023-09-29 08:47 18阅读 0赞

## 402. 移掉 K 位数字 ##

【题目描述】  
给你一个以字符串表示的非负整数 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 。

提示：

*  1 <= k <= num.length <= 10
 *  num 仅由若干位数字（0 - 9）组成
 *  除了 0 本身之外，num 不含任何前导零

【解题思路】  
**对于两个数 123a456 和 123b456，如果 a > b， 那么数字 123a456 大于 数字 123b456，否则数字 123a456 小于等于数字 123b456**。也就说，**两个相同位数的数字大小关系取决于第一个不同的数的大小**

*  从左到右遍历
 *  对于遍历到的元素，我们选择保留。
 *  但是我们可以选择性丢弃前面相邻的元素。
 *  丢弃与否的依据如上面阐述中的方法  
    ![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3blsZXnpLo_size_20_color_FFFFFF_t_70_g_se_x_16]  
    【注意】如果给定的数字是一个单调递增的数字，那么我们的算法会永远选择不丢弃。这个题目中要求的，我们要永远确保丢弃 k 个矛盾。

思路：

*  每次丢弃一次，k 减去 1。当 k 减到 0 ，我们可以提前终止遍历。
 *  而当遍历完成，如果 k 仍然大于 0。不妨假设最终还剩下 x 个需要丢弃，那么我们需要选择删除末尾 x 个元素

【全部代码】

import java.util.Deque;
    import java.util.LinkedList;
    
    public class Solution {
        
        public static void main(String[] args) {
        
            String s = removeKdigits("1432219", 3);
            System.out.println(s);
        }
        public static String removeKdigits(String num, int k) {
        
            Deque<Character> queue = new LinkedList<>();
            int len = num.length();
            for(int i = 0;i < len;i++){
        
                // 获取指定索引字符
                char ch = num.charAt(i);
                // k > 0要保证是需要移除的
                // queue.peekLast() > ch后面的小于前面，移除前面相邻大的数字
                while (!queue.isEmpty() && k > 0 && queue.peekLast() > ch){
        
                    k--;
                    queue.pollLast();
                }
                queue.offerLast(ch);
            }
            String result = "";
            int size = queue.size();
            // -k 是为了 防止给定的数字是一个单调递增的数字，那么我们的算法会永远选择不丢弃
            for(int i = 0;i < size - k;i++){
        
                // 去除前置0
                if(result.length() == 0 && queue.peekFirst() == '0'){
        
                    queue.pollFirst();
                    continue;
                }
                result += queue.pollFirst();
            }
            // 如果是空直接返回0
            if("".equals(result)){
        
                result += '0';
            }
            return result;
        }
    }

## 316. 去除重复字母、1081. 不同字符的最小子序列 ##

【题目描述】  
给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

示例 1：

输入：s = "bcabc"
    输出："abc"

示例 2：

输入：s = "cbacdcbc"
    输出："acdb"

提示：

*  1 <= s.length <= 10^4
 *  s 由小写英文字母组成

【解题思路】  
思路其实和移掉k位数字一样，只不过这里的k是每个字符都有一个要删除的数量k = 每个字符的个数 - 1

*  通过map记录每个字符的个数
 *  遍历字符串，每经过一个字符，map中的数量-1
 *  遍历过程中可以查看与前面的字符的比较，如果前面字符大于后面的字符，且前面的字符能够删除（次数大于1），那就把前面的删除掉

【AC代码】

import java.util.Deque;
    import java.util.LinkedList;
    
    public class Solution {
        
        public static String removeDuplicateLetters(String s) {
        
            Map<Character,Integer> map = new HashMap<>();
            int len = s.length();
            // 计算每个字符出现的次数，每个字符要删除k-1次
            for (int i = 0; i < len; i++) {
        
                char ch = s.charAt(i);
                if(map.containsKey(ch)){
        
                    map.put(ch,map.get(ch) + 1);
                }else{
        
                    map.put(ch, 1);
                }
            }
            // 用来存储的双端队列
            Deque<Character> queue = new LinkedList<>();
            for(int i = 0;i < len; i++){
        
                char ch = s.charAt(i);
                // 判断队列中是否存在
                if(!queue.contains(ch)){
        
                    // 移除掉重复的k > 1的且比ch大的
                    while (!queue.isEmpty() && ch < queue.peekLast() && map.get(ch) > 0){
        
                        if(map.get(queue.peekLast()) > 0){
        
                            queue.pollLast();
                        }else {
        
                            break;
                        }
                    }
                    // 加入到队列中
                    queue.offerLast(ch);
                }
                // 每次遍历到的字符，次数减一
                map.put(ch,map.get(ch) - 1);
            }
            int size = queue.size();
            // 组装答案
            String result = "";
            for (int i = 0; i < size; i++) {
        
                result += queue.pollFirst();
            }
            return result;
        }
    }

## 321. 拼接最大数 ##

【题目描述】  
给定长度分别为 m 和 n 的两个数组，其元素由 0-9 构成，表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。

求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。

说明: 请尽可能地优化你算法的时间和空间复杂度。

示例 1:

输入:

nums1 = [3, 4, 6, 5]
    nums2 = [9, 1, 2, 5, 8, 3]
    k = 5
    输出:
    [9, 8, 6, 5, 3]

示例 2:

输入:

nums1 = [6, 7]
    nums2 = [6, 0, 4]
    k = 5
    输出:
    [6, 7, 6, 0, 4]

示例 3:

输入:

nums1 = [3, 9]
    nums2 = [8, 9]
    k = 3
    输出:
    [9, 8, 9]

【解题思路】

*  和第一道题类似，只不不过这一次是两个数组，而不是一个，并且是求最大数
 *  最大最小是无关紧要的，关键在于是两个数组，并且要求从两个数组选取的元素个数加起来一共是 k
 *  假设我们从 nums1 中取了 k1 个，从 num2 中取了 k2 个，其中 k1 + k2 = k。而 k1 和 k2 这 两个子问题我们是会解决的。由于这两个子问题是相互独立的，因此我们只需要分别求解，然后将结果合并即可
 *  所以我们可以分别从一个数组中找到0，1，2…k个数和k,k-1…0个数，只要满足k1 + k2 = k，且k1 < len1 && k2 < len2就行  
    【AC代码】

import java.util.*;
    
    public class Solution {
        
        public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        
            int len1 = nums1.length;
            int len2 = nums2.length;
            int[] result = new int[k];
            List<Integer> list = new ArrayList<>();
            for(int i = 0;i <= k;i++){
        
            	// 对每个数组分别取 i，k-i个数的最大数
                if(i <= len1 && k - i <= len2){
        
                    int[] one = removeKdigits(nums1, len1 - i);
                    int[] two = removeKdigits(nums2, len2 - (k - i));
                    // 合并数组
                    int[] merge = merge(one, two);
                    // 比较结果和新得到的数组的大小
                    if(compare(merge,0,result,0) > 0){
        
                        System.arraycopy(merge,0,result,0,k);
                    }
                }
            }
            return result;
        }
        // 合并两个数组
        public int[] merge(int[] subsequence1, int[] subsequence2) {
        
            int x = subsequence1.length, y = subsequence2.length;
            if (x == 0) {
        
                return subsequence2;
            }
            if (y == 0) {
        
                return subsequence1;
            }
            int mergeLength = x + y;
            int[] merged = new int[mergeLength];
            int index1 = 0, index2 = 0;
            for (int i = 0; i < mergeLength; i++) {
        
                if (compare(subsequence1, index1, subsequence2, index2) > 0) {
        
                    merged[i] = subsequence1[index1++];
                } else {
        
                    merged[i] = subsequence2[index2++];
                }
            }
            return merged;
        }
    	// 判断合并时取哪个数组的元素
        public int compare(int[] subsequence1, int index1, int[] subsequence2, int index2) {
        
            int x = subsequence1.length, y = subsequence2.length;
            while (index1 < x && index2 < y) {
        
                int difference = subsequence1[index1] - subsequence2[index2];
                // 如果不相等直接返回
                if (difference != 0) {
        
                    return difference;
                }
                // 如果相等，继续比较后面
                index1++;
                index2++;
            }
            // 如果跳出循环，说明有一个数组的索引到达了边界
            return (x - index1) - (y - index2);
        }
    
        public int[] removeKdigits(int[] num, int k) {
        
            Deque<Integer> queue = new LinkedList<>();
            int len = num.length;
            for(int i = 0;i < len;i++){
        
                // 获取指定索引字符
                int ch = num[i];
                // k > 0要保证是需要移除的
                // queue.peekLast() > ch后面的小于前面，移除前面相邻大的数字
                while (!queue.isEmpty() && k > 0 && queue.peekLast() < ch){
        
                    k--;
                    queue.pollLast();
                }
                queue.offerLast(ch);
            }
            // 将队列转换成数组
            int size = queue.size();
            int[] result = new int[size - k];
            int index = 0;
            for(int i = 0;i < size - k;i++){
        
                if(result[0] == 0 && queue.peekFirst() == 0){
        
                    queue.pollFirst();
                    continue;
                }
                result[index++] = queue.pollFirst();
            }
            return result;
        }
    
    }

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3blsZXnpLo_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/a802bbe0c709426699de79e16fcc162f.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAY3blsZXnpLo=,size_20,color_FFFFFF,t_70,g_se,x_16