[数据结构与算法]LeetCode 942. 增减字符串匹配

题目链接：

力扣https://leetcode.cn/problems/di-string-match/

【方法一】从头开始构造，哈希表判重

class Solution {
    public int[] diStringMatch(String s) {
        int n = s.length();
        int j = 0, i = 0, t, min = 0;
        char c;
        Set<Integer> set = new HashSet();
        int[] ans = new int[n + 1];
        set.add(0);
        while(i < n){
            c = s.charAt(i);
            if(c == 'I'){
                t = ans[i] + 1;
                while(set.contains(t)) t++;
                ans[i + 1] = t;
                set.add(t);
            }else{
                t = ans[i] - 1;
                while(set.contains(t)) t--;
                ans[i + 1] = t;
                min = Math.min(min, t);
                set.add(t);
            }
            i++;
        }
        for(i = 0; i <= n; i++) ans[i] -= min;
        return ans;
    }
}

【方法二 贪心】如果perm[0]=I，那么就让ans[0] = 0，那么后面无论是啥都满足比0大，同理如果是D，就让ans[0]=n，后面无论是什么都比n小，确定第一个后，对后面的n-1个来说，最小是1，最大是n-1，这样再遇到I和D的时候分别填入最小值和最大值即可。

class Solution {
    public int[] diStringMatch(String s) {
        int n = s.length(), i;
        int left = 0, right = n;
        int[] ans = new int[n + 1];
        for(i = 0; i < n; i++){
            if(s.charAt(i) == 'I'){
                ans[i] = left++;
            }else{
                ans[i] = right--;
            }
        }
        ans[i] = left;
        return ans;
    }
}

?

?

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖