去除重复字母

C++ 解法, 执行用时: 5ms, 内存消耗: 804KB, 提交时间: 2022-04-28

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return string字符串
     */
    string removeDuplicateLetters(string str) {
        // write code here
        vector<int> hash(27);
        vector<int> vis(27);
        string s;
        //string res=NULL;
        for(int i=0;i<str.size();i++){
            hash[str[i]-'a']=i;
        }
        for(int i=0;i<str.size();i++){
            if(vis[str[i]-'a']){
                continue;
            }
            while(!s.empty()&&s.back()>str[i]&&hash[s.back()-'a']>i){
                char topchar=s.back();
                s.pop_back();
                vis[topchar-'a']=false;
            }
            s.push_back(str[i]);
            vis[str[i]-'a']=true;
        }
        
        
        return s;
    }
};

Go 解法, 执行用时: 5ms, 内存消耗: 1144KB, 提交时间: 2022-06-22

package main

import "strings"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param str string字符串
 * @return string字符串
 */
func removeDuplicateLetters(str string) string {
	count := [26]int{}
	for _, ch := range str {
		count[ch-'a']++
	}

	in := [26]bool{}
	s := New()

	for _, c := range str {
		ch := c - 'a'
		count[ch]--
		if in[ch] {
			continue
		}

		for !s.IsEmpty() && s.Peek() > ch {
			if count[s.Peek()] == 0 {
				break
			}
			in[s.Pop()] = false
		}
		s.Push(ch)
		in[ch] = true
	}

	runes := make([]rune, 0, s.Len())

	for !s.IsEmpty() {
		runes = append(runes, s.Pop()+'a')
	}

	var builder strings.Builder

	for i := len(runes) - 1; i >= 0; i-- {
		builder.WriteRune(runes[i])
	}

	return builder.String()
}

type Stack struct {
	top  *node
	size int
}

type node struct {
	val  rune
	prev *node
}

func New() *Stack {
	return &Stack{top: nil}
}

func (s *Stack) IsEmpty() bool {
	return s.size == 0
}

func (s *Stack) Push(r rune) {
	n := &node{r, s.top}
	s.top = n
	s.size++
}

func (s *Stack) Peek() rune {
	return s.top.val
}

func (s *Stack) Len() int {
	return s.size
}

func (s *Stack) Pop() rune {
	n := s.top.val
	s.top = s.top.prev
	s.size--
	return n
}

Go 解法, 执行用时: 5ms, 内存消耗: 1260KB, 提交时间: 2022-06-04

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param str string字符串 
 * @return string字符串
*/


func removeDuplicateLetters(s string) string {
    letters := make([]int, 256)
    for _, v := range s {
        letters[v-'a']++
    }
    flag := [256]bool{}
    stack := []rune{}
    for _, v := range s {
        if !flag[v-'a'] {
            for len(stack) > 0 && v < stack[len(stack)-1] && letters[stack[len(stack)-1]-'a'] > 0 {
                flag[stack[len(stack)-1]-'a'] = false   
                stack = stack[:len(stack)-1]
            }
            flag[v-'a'] = true
            stack = append(stack, v)
        }
        letters[v-'a']--
    }
    return string(stack)
}

Go 解法, 执行用时: 5ms, 内存消耗: 1360KB, 提交时间: 2022-07-14

package main

func removeDuplicateLetters(s string) string {
	e := make([]int, 256)
    
	for _, v := range s {
		e[v-'a']++
	}
    
	f := [256]bool{}
	t := []rune{}
    
	for _, v := range s {
		if !f[v-'a'] {
			for len(t) > 0 && v < t[len(t)-1] && e[t[len(t)-1]-'a'] > 0 {
				f[t[len(t)-1]-'a'] = false
				t = t[:len(t)-1]
			}
			f[v-'a'] = true
			t = append(t, v)
		}
		e[v-'a']--
	}
	return string(t)
}

C 解法, 执行用时: 6ms, 内存消耗: 692KB, 提交时间: 2022-06-27

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param str string字符串 
 * @return string字符串
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
char* removeDuplicateLetters(char* str ) {
    int hash[26] = { 0 }, sLen = strlen(str), key;
    for (int i = 0; i < sLen; i++) {
        key = str[i] - 'a';
        hash[key] += 1;
    }
    char stack[sLen];
    int sTop = 0, inStack[26] = { 0 };
    for (int i = 0; i < sLen; i++) {
        while(sTop > 0 && inStack[str[i] - 'a'] == 0 && hash[stack[sTop-1] - 'a'] > 0 && str[i] < stack[sTop - 1]) {
            inStack[stack[sTop-1] - 'a'] = 0;
            sTop--;
        }
        
        if (inStack[str[i] - 'a'] == 0) {
            stack[sTop++] = str[i];
            inStack[str[i] - 'a'] = 1;
        }
        
        hash[str[i] - 'a'] -= 1;
    }
    char *result = (char *)malloc(sizeof(char) * (sTop+1));
    for (int i = 0; i < sTop; i++) {
        result[i] = stack[i];
    }
    result[sTop] = '\0';
    
    return result;
}

详情