初级算法 字符串

翻转字符串

https://leetcode.cn/problems/reverse-string/

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

const reverseString = function(s) {
    return s.reverse().join();
};

字符串中的第一个唯一字符

https://leetcode.cn/problems/first-unique-character-in-a-string/

给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。

思路

使用 Map 存储 count 和 index 然后找到其中 count 为 1 中 index 最小的那个，返回这个 index 即可。

const firstUniqChar = function (s) {
  const base = "a".charCodeAt(0);
  const charCodeList = [];
  for (let i = 0; i < s.length; i++) {
    let code = s.charCodeAt(i) - base;
    charCodeList.push(code);
  }
  const map = {};
  charCodeList.forEach((item, index) => {
    // [count, index]
    if (map[item]) {
      map[item][0] += 1;
    } else {
      map[item] = [];
      map[item][0] = 1;
      map[item][1] = index;
    }
  });
  // find single count === 1
  // find first  sort 
  const result = map.filter((item) => item[0] === 1).sort((a, b) => a[1] - b[1]);
  // return result index
  if (result.length) return result[0][1];
  // if not exist return -1
  return -1;
};

最长公共前缀

https://leetcode.cn/problems/longest-common-prefix/

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

var longestCommonPrefix = function (strs) {
  if (strs.length == 1) return strs[0];
  let minLength = Math.min(...strs.map((item) => item.length));
  let left = -1;
  let right = minLength - 1;
  let mid = Math.round((left + right) / 2);
  for (let i = 0; i < minLength; i++) {
    // 扫描
    let char = "";
    let match = true;
    for (let j = 0; j < strs.length; j++) {
      // 遍历字符串
      if (char == "") char = strs[j][mid];
      if (char != "") {
        if (strs[j][mid] != char) {
          match = false;
        }
      }
    }
    if (match) {  
      left = mid;
    } else {
      if (right == mid) mid -= 1;
      right = mid;
    }
    mid = Math.round((left + right) / 2);
  }
  return strs[0].slice(0, mid + 1) 
};