双指针,求解《942. 增减字符串匹配》

例题

942. 增减字符串匹配

由范围 [0,n] 内所有整数组成的 n + 1 个整数的排列序列可以表示为长度为 n 的字符串 s ,其中:

  • 如果 perm[i] < perm[i + 1] ,那么 s[i] == 'I'
  • 如果 perm[i] > perm[i + 1] ,那么 s[i] == 'D'
    给定一个字符串 s ,重构排列 perm 并返回它。如果有多个有效排列perm,则返回其中 任何一个 。

答案

双指针

var diStringMatch = function(s) {
  const n = max = s.length, r = new Uint32Array(n + 1)
  let min = 0, i = -1
  while (i++ < n) r[i] = s[i] === 'I' ? min++ : max--
  return r
};
function diStringMatch(s: string): number[] {
  const n = s.length, r = new Array(n + 1)
  let i = -1, min = 0, max = n
  while (i++ < n) r[i] = s[i] === 'I' ? min++ : max--
  return r
};
func diStringMatch(s string) []int {
  n := len(s)
  r := make([]int, n + 1)
  min, max := 0, n
  for i := 0; i <= n; i++ {
    if i < n && s[i] == 'I' {
      r[i] = min
      min++
    } else {
      r[i] = max
      max--
    }
  }
  return r
}
class Solution {
  function diStringMatch($s) {
    $n = strlen($s);
    $r = array_fill(0, $n, 0);
    $min = 0;
    $max = $n;
    for ($i = 0;  $i <= $n; $i++) {
      $r[$i] = $s[$i] === 'I' ? $min++ : $max--;
    }
    return $r;
  }
}
class Solution:
    def diStringMatch(self, s: str) -> List[int]:
        n = len(s)
        r = [0] * (n + 1)
        min, max = 0, n
        for i in range(n):
            if s[i] == 'I':
                r[i] = min
                min += 1
            else:
                r[i] = max
                max -= 1
        r[n] = max
        return r
class Solution {
    public int[] diStringMatch(String s) {
        int n = s.length(), min = 0, max = n;
        int[] r = new int[n + 1];
        for (int i = 0; i < n; i++) {
            r[i] = s.charAt(i) == 'I' ? min++ : max--;
        }
        r[n] = max;
        return r;
    }
}

代码
双指针,字符串截取、拼接:求解《面试题 01.05. 一次编辑》
双指针,字符串截取、拼接,2 解法求解《面试题 01.05. 一次编辑》
代码
自定义排序:求解《937. 重新排列日志文件》
自定义排序和 Golang 的字符串分割函数,求解《937. 重新排列日志文件》
代码
消元法,正则和栈:求解《591. 标签验证器》
消元法,正则和栈,求解《591. 标签验证器》