LeetCode1370. 上升下降字符串-Java&Go-数组哈希表 | TreeMap

• 算法
  • 1.用数组当作简易哈希表，同时又能保证按照key有序遍历该哈希表
  • 2.首先统计字符串中字符个数
  • 3.然后每次都 “先从头到尾后从尾到头” 操作数组中非0的字符添加到结果字符串中

public String sortString(String s) {
    int n = s.length();
    int[] dict = new int[26];
    for (char c : s.toCharArray()) {
        dict[c-'a']++;
    }

    StringBuilder sb = new StringBuilder();
    while (sb.length() < n) {
        pick(dict, sb, true);
        pick(dict, sb, false);
    }
    return sb.toString();
}

private void pick(int[] dict, StringBuilder sb, boolean ascend) {
    for (int i = 0; i < 26; i++) {
        int j = ascend ? i : 25 - i;
        if (dict[j]-- > 0) {
            sb.append((char)(j+'a'));
        }
    }
}

func sortString(s string) string {
    count := make([]int, 26)
    for _, c := range s {
        count[c-'a']++
    }

    var result string
    for len(result) < len(s) {
        result = pick(count, result, true)
        result = pick(count, result, false)
    }
    return result
}

func pick(count []int, result string, ascend bool) string {
    for i := 0; i < 26; i++ {
        var j int
        if ascend {
            j = i
        } else {
            j = 25 - i
        }
        if count[j] > 0 {
            result += string(rune(j + 'a'))
            count[j]--
        }
    }
    return result
}

• 算法
  • 1.使用TreeMap达到同样的效果
  • 2.注意细节
    • 2.1 需要使用TreeMap获得的keySet去初始化一个TreeSet，做深拷贝；而不是直接赋值给一个TreeSet/NavigableSet，做浅拷贝，这样在遍历的时候删除其中的key回出现并发修改错误
    • 2.2 注意以下两种初始化TreeSet的区别
      • new TreeSet<>(treeMap.keySet())：返回的TreeSet一定是按照key升序的
      • new TreeSet(treeMap.keySet())：返回的TreeSet的key顺序依赖于里面的treeMap的key顺序，里面是key升序他就是key升序，里面是key降序他就是key降序

public String sortString(String s) {
    int n = s.length();
    TreeMap<Character, Integer> treeMap = new TreeMap<>();
    for (char c : s.toCharArray()) {
        treeMap.put(c, treeMap.getOrDefault(c, 0) + 1);
    }

    boolean ascend = true;
    StringBuilder sb = new StringBuilder();
    while (sb.length() < n) {
        TreeSet<Character> characters = ascend ? new TreeSet<>(treeMap.keySet()) : new TreeSet(treeMap.descendingKeySet());
        for (char c : characters) {
            sb.append(c);
            treeMap.put(c, treeMap.get(c) - 1);
            treeMap.remove(c, 0);
        }
        ascend = !ascend; // ascend ^= ascend;
    }
    return sb.toString();
}