LeetCode-316. 去除重复字母&&1081.不同字符的最小子序列(java)

bug菌

发布于 2023-05-27 15:32:00

2260

发布于 2023-05-27 15:32:00

文章被收录于专栏：《项目实战教学》

一、前言：

👨‍🎓作者：bug菌 ✏️博客：CSDN、掘金等 💌公众号：猿圈奇妙屋 🚫特别声明：原创不易，转载请附上原文出处链接和本文声明，谢谢配合。 🙏版权声明：文章里可能部分文字或者图片来源于互联网或者百度百科，如有侵权请联系bug菌处理。

二、题目描述：

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

示例 1：

s = "bcabc"
"abc"

注意：该题与 1081. 不同字符的最小子序列相同

三、思路分析：

统计字符出现次数，遍历字符串，当前字符出现次数-1；当前字符不在栈中（目的：去重，如abcabc的第二个a）；栈顶字符 > 当前字符（目的：字典序最小。贪心策略：字符越小越前）；栈顶字符后面还有出现（目的：字符至少出现一次。没有出现不能删）；弹出，即删。重复上面的判断，直到条件不成立；即：数组越界或栈顶字符 < 当前字符或 >，但后面没有该字符；

四、算法实现：

方法一：

public List<Integer> findDisappearedNumbers(int[] nums) {
         ArrayList<Integer> list = new ArrayList<Integer>();
         Map<Integer, Integer> map = new HashMap<Integer,Integer>(16);
         //只需记录不同的num 存key即可
         for(Integer num :nums){
             map.put(num,1);
         }
         for (int i = 1; i <= nums.length; i++) {
             //判断key不存在即写入
             if(!map.containsKey(i)){
                 list.add(i);
             }
         }
         return list;
     }

方法二：

public static List<Integer> findDisappearedNumbers(int[] nums) {
         ArrayList<Integer> list = new ArrayList<Integer>();
         for (int i = 0; i < nums.length; i++) {
             int newIndex = Math.abs(nums[i]) - 1;//防止下标为负
             //防止下标越界
             if(newIndex >=nums.length){
                 continue;
             }
             if (nums[newIndex] > 0) {
                 nums[newIndex] *= -1;
             }
         }
         for (int i = 1; i <= nums.length; i++) {
             if (nums[i - 1] > 0) {
                 list.add(i);
             }
         }
         return list;
     }