顺序遍历,计数和奇偶性交换 2 种算法,求解《1417. 重新格式化字符串》

2022-08-11 13:20:12
顺序遍历,计数和奇偶性交换 2 种算法,用双指针技巧,求解《1417. 重新格式化字符串》

例题

1417. 重新格式化字符串

给你一个混合了数字和字母的字符串 s,其中的字母均为小写英文字母。
请你将该字符串重新格式化,使得任意两个相邻字符的类型都不同。也就是说,字母后面应该跟着数字,而数字后面应该跟着字母。
请你返回 重新格式化后 的字符串;如果无法按要求重新格式化,则返回一个 空字符串 。
示例 1:
输入:s = "a0b1c2"
输出:"0a1b2c"
解释:"0a1b2c" 中任意两个相邻字符的类型都不同。 "a0b1c2", "0a1b2c", "0c2a1b" 也是满足题目要求的答案。

答案

顺序遍历 · 双指针 · 拼接字符串

var reformat = function(s) {
  const n = s.length
  let p1 = 0, p2 = 0, r = ''
  while (true) {
    while (p1 < n && s[p1] >  '9') p1++
    while (p2 < n && s[p2] <= '9') p2++
    if (p1 === n || p2 === n) break
    r += s[p1++]
    r += s[p2++]
  }
  if (r.length < n - 1) return ''
  if (r.length === n) return r
  const j = p1 === n ? p2 : p1
  return s[j] > '9' ? s[j] + r : r + s[j]
};
class Solution {
  function reformat($s) {
    $n = strlen($s);
    $p1 = $p2 = 0;
    $r = '';
    while (true) {
      while ($p1 < $n && $s[$p1]  > '9') $p1++;
      while ($p2 < $n && $s[$p2] <= '9') $p2++;
      if ($p1 === $n || $p2 === $n) break;
      $r .= $s[$p1++];
      $r .= $s[$p2++];
    }
    $l = strlen($r);
    if ($l < $n - 1) return '';
    if ($l === $n) return $r;
    $j = $p1 === $n ? $p2 : $p1;
    return $s[$j] > '9' ? $s[$j] . $r : $r . $s[$j];
  }
}
char * reformat(char * s){
  int n = strlen(s), p1 = 0, p2 = 0, i = 0;
  char* r = malloc(sizeof(char) * n + 1);
  while (true) {
    while (p1 < n && s[p1] >  '9') p1++;
    while (p2 < n && s[p2] <= '9') p2++;
    if (p1 == n || p2 == n) break;
    r[i++] = s[p1++];
    r[i++] = s[p2++];
  }
  if (i < n - 1) return "";
  r[i] = '\0';
  if (i == n) return r;
  int j = p1 == n ? p2 : p1;
  char* t = malloc(sizeof(char) * (2 + i));
  t[0] = s[j];
  t[1] = '\0';
  return s[j] > '9' ? strcat(t, r) : strcat(r, t);
}
class Solution {
public:
  string reformat(string s) {
    int n = s.size(), p1 = 0, p2 = 0;
    string r = "";
    while (true) {
      while (p1 < n && s[p1]  > '9') p1++;
      while (p2 < n && s[p2] <= '9') p2++;
      if (p1 == n || p2 == n) break;
      r += s[p1++];
      r += s[p2++];
    }
    if (r.size() < n - 1) return "";
    if (r.size() == n) return r;
    int j = p1 == n ? p2 : p1;
    return s[j] > '9' ? s[j] + r : r + s[j];
  }
};
class Solution:
  def reformat(self, s: str) -> str:
    n, p1, p2, r = len(s), 0, 0, ''
    while True:
      while p1 < n and s[p1] >  '9': p1 += 1
      while p2 < n and s[p2] <= '9': p2 += 1
      if p1 == n or p2 == n: break
      r += s[p1]
      p1 += 1
      r += s[p2]
      p2 += 1
    m = len(r)
    if m < n - 1: return ""
    if m == n: return r
    j = p2 if p1 == n else p1
    return s[j] + r if s[j] > '9' else r + s[j]

顺序遍历 · 双指针 · 用坐标奇偶性交换

function reformat(s: string): string {
  const n = s.length
  let digits = 0
  for (let i = 0; i < n; i++) {
    if (s[i] <= '9') digits++
  }
  const alphas =  n - digits
  if (Math.abs(digits - alphas) > 1) return ''
  const isDigitMore = digits > alphas, a = Array.from(s)
  for (let i = 0, j = 1; i < n; i += 2) {
    if (a[i] > '9' && isDigitMore === true || a[i] <= '9' && isDigitMore === false) {
      while (a[j] > '9' && isDigitMore === true || a[j] <= '9' && isDigitMore === false) j += 2
      ;[a[i], a[j]] = [a[j], a[i]]
    }
  }
  return a.join("")
};
func reformat(s string) string {
  n, digts := len(s), 0
  a := make([]rune, n)
  for i, c := range s {
    a[i] = c
    if c <= '9' {
      digts++
    }
  } 
  alpha := n - digts
  if math.Abs(float64(digts - alpha)) > 1 {
    return ""
  }
  isDigtsMore := digts > alpha
  for i, j := 0, 1; i < n; i += 2 {
    if isDigtsMore == true && a[i] > '9' || isDigtsMore == false && a[i] <= '9' {
      for isDigtsMore == true && a[j] > '9' || isDigtsMore == false && a[j] <= '9' {
        j += 2
      }
      a[i], a[j] = a[j], a[i]
    }
  }
  return string(a)
}
class Solution {
  public String reformat(String s) {
    int digit = 0, n = s.length();
    char[] a = s.toCharArray();
    for (char c : a) {
      if (c <= '9') {
        digit++;
      }
    }
    int alpha = n - digit;
    if (Math.abs(alpha - digit) > 1) return "";
    final boolean isDigitMore = digit > alpha;
    for (int i = 0, j = 1; i < n; i += 2) {
      if (isDigitMore == true && a[i] > '9' || isDigitMore == false && a[i] <= '9') {
        while (isDigitMore == true && a[j] > '9' || isDigitMore == false && a[j] <= '9') j += 2;
        final char t = a[i];
        a[i] = a[j];
        a[j] = t;
      }
    }
    return new String(a);
  }
}
public class Solution {
  public string Reformat(string s) {
    int n = s.Length, digit = 0;
    for (int i = 0; i < n; i++) {
      if (s[i] <= '9') digit++;
    }
    int alpha = n - digit;
    if (Math.Abs(digit - alpha) > 1) return "";
    bool isDigitMore = digit > alpha;
    char[] a = s.ToCharArray();
    for (int i = 0, j = 1; i < n; i += 2) {
      if (isDigitMore == true && a[i] > '9' || isDigitMore == false && a[i] <= '9') {
        while (isDigitMore == true && a[j] > '9' || isDigitMore == false && a[j] <= '9') j += 2;
        char t = a[i];
        a[i] = a[j];
        a[j] = t;
      }
    }
    return new String(a);
  }
}
char * reformat(char * s){
  int n = strlen(s), digit = 0;
  for (int i = 0; i < n; i++) {
    if (s[i] <= '9') digit++;
  }
  int alpha = n - digit;
  if (abs(digit - alpha) > 1) return "";
  bool isDigitMore = digit > alpha;
  for (int i = 0, j = 1; i < n; i += 2) {
    if (isDigitMore == true && s[i] > '9' || isDigitMore == false && s[i] <= '9') {
      while (isDigitMore == true && s[j] > '9' || isDigitMore == false && s[j] <= '9') j += 2;
      char t = s[i];
      s[i] = s[j];
      s[j] = t;
    }
  }
  return s;
}
class Solution {
public:
  string reformat(string s) {
    int n = s.size(), digit = 0;
    for (int c : s) {
      if (c <= '9') digit++;
    }
    int alpha = n - digit;
    if (abs(digit - alpha) > 1) return "";
    bool isDigitMore = digit > alpha;
    for (int i = 0, j = 1; i < n; i += 2) {
      if (isDigitMore == true && s[i] > '9' || isDigitMore == false && s[i] <= '9') {
        while (isDigitMore == true && s[j] > '9' || isDigitMore == false && s[j] <= '9') j += 2;
        swap(s[i], s[j]);
      }
    }
    return s;
  }
};
class Solution:
  def reformat(self, s: str) -> str:
    n, digit, j = len(s), sum(c <= '9' for c in s), 1
    if abs(n - (digit << 1)) > 1: return ""
    isDigitMore, a = digit << 1 > n, list(s)
    for i in range(0, n, 2):
      if isDigitMore == True and a[i] > '9' or isDigitMore == False and a[i] <= '9':
        while isDigitMore == True and a[j] > '9' or isDigitMore == False and a[j] <= '9': j += 2
        a[i], a[j] = a[j], a[i]
    return ''.join(a)

哈希表(用 uthash / Dictionary / dict / HashMap / unordered_map 等 + 定长列表实现),排序 + 拼接字符串 2 算法,求解《1460. 通过翻转子数组使两个数组相等》
哈希表(用 uthash / Dictionary / dict / HashMap / unordered_map 等 + 定长列表实现),排序 + 拼接字符串 2 算法,用 join / implode / fmt.Sprint 将列表转字符串比较,用 Array.equal/ (int[]).SequenceEqual 比较列表,C++ 直接比较 vector<……
位图(位集),0b 和 C# Convert.ToInt32("字符串", 2) 表示二进制数字,求解《782. 变为棋盘》
位图(位集),0b 和 C# Convert.ToInt32("字符串", 2) 表示二进制数字,求解《782. 变为棋盘》
广度优先搜索,深度优先搜索(前序 / 中序(含莫里斯) / 后序 遍历,递归和迭代(单栈 / 双栈)),数字转为字符串,求解《655. 输出二叉树》
广度优先搜索,深度优先搜索(前序 / 中序(含莫里斯) / 后序 遍历,递归和迭代(单栈 / 双栈)),''+ int / strconv.Itoa / Integer.toString / int.ToString / sprintf(char*, "%d", int) / to_string / str 将数字转为字符串,求解《655. 输出二叉树》