案例

反转字符串(简)

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

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

示例 1：

输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例 2：

输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]\

解题思路

双指针思想

1. 定义头尾指针
2. 找出迭代停止条件：数组中间的数
3. 交换头尾指针，交换后头指针后移，尾部指针前移

/**
 * @param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */
var reverseString = function(s) {
    const mid = Math.floor(s.length / 2);
    let left = 0;
    let right = s.length - 1;
    while(left < mid) {
        [s[left],s[right]] = [s[right],s[left]]
        left ++;
        right --;
    }
};

有效的括号(简)

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

提示

• 1 <= s.length <= 104
• s 仅由括号 '()[]{}' 组成

解题思路

• 有效括号字符串的长度，一定是偶数！
• 右括号前面，必须是相对应的左括号，才能抵消！
• 右括号前面，不是对应的左括号，那么该字符串，一定不是有效的括号！

let isValid = function(s) {
    let stack = [], length = s.length;
    if(length % 2) return false;
    for(let item of s){
        switch(item){
            case "{":
            case "[":
            case "(":
                stack.push(item);
                break;
            case "}":
                if(stack.pop() !== "{") return false;
                break;
            case "]":
                if(stack.pop() !== "[") return false;
                break;
            case ")":
                if(stack.pop() !== "(") return false;
                break;
        }
    }
    return !stack.length;
};

找出字符串中第一个匹配项的下标(简)

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

示例 1：

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：

输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

提示：

• 1 <= haystack.length, needle.length <= 104
• haystack 和 needle 仅由小写英文字符组成

暴力破解

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function (haystack, needle) {
    for (let i = 0; i < haystack.length; i++) {
        let flag = true
        for (j = 0; j < needle.length; j++) {
            if (haystack[i + j] !== needle[j]) {
                flag = false
                break;
            }
        }
        if (flag) return i
    }
    return -1
};

KMP

var strStr = function(haystack, needle) {
    // 获取输入字符串的长度
    const n = haystack.length, m = needle.length;

    // 如果要查找的字符串为空，则返回 0
    if (m === 0) {
        return 0;
    }

    // 创建一个长度为 m 的数组 pi，用于存储部分匹配表（partial match table）
    const pi = new Array(m).fill(0);

    // 构建部分匹配表
    for (let i = 1, j = 0; i < m; i++) {
        // 当 j 大于 0 且当前字符不匹配时，回溯 j 的值
        while (j > 0 && needle[i] !== needle[j]) {
            j = pi[j - 1];
        }

        // 如果当前字符匹配，增加部分匹配值 j
        j++;

        // 将部分匹配值保存到部分匹配表中
        pi[i] = j;

        // 注意：以上过程构建了 needle 字符串的部分匹配表
    }

    // 在 haystack 字符串中查找 needle 字符串
    for (let i = 0, j = 0; i < n; i++) {
        // 当 j 大于 0 且当前字符不匹配时，回溯 j 的值
        while (j > 0 && haystack[i] !== needle[j]) {
            j = pi[j - 1];
        }

        // 如果当前字符匹配，增加 j
        j++;

        // 如果 j 的值等于 needle 字符串的长度 m，说明找到了匹配，返回匹配的起始位置
        if (j === m) {
            return i - m + 1;
        }
    }

    // 没有找到匹配，返回 -1
    return -1;
};

N 字形变换(中)

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

P   A   H   N
A P L S I I G
Y   I   R

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

示例 1：

输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"

示例 2：

输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P     I    N
A   L S  I G
Y A   H R
P     I

示例 3：

输入：s = "A", numRows = 1
输出："A"

提示：

• 1 <= s.length <= 1000
• s 由英文字母（小写和大写）、',' 和 '.' 组成
• 1 <= numRows <= 1000

解题思路

这题刚开始看没看懂。。。后面发现要转过来看，相当于写倒 N。

字符串 s 是以 z 字形为顺序存储的字符串，目标是按行打印。

设 numRows 行字符串分别为s1，s2，…，sn，则容易发现：按顺序遍历字符串 s 时，每个字符在 N 字形中对应的行索引先从 s1增大至 sn，再从 sn，减小至 s1 .如此反复。
因此解决方案为：模拟这个行索引的变化，在遍历 s 中把每个字符填到正确的行 res[i]。

/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */
var convert = function (s, numRows) {
    // 如果 numRows 小于 2，则无需进行变换，直接返回原字符串
    if (numRows < 2) return s;

    // 创建一个长度为 numRows 的数组 res，用于存储变换后的结果
    let res = new Array(numRows).fill("");
    
    // 初始化变量 i 为 0，flag 为 -1，flag 用于控制行号的递增或递减
    let i = 0, flag = -1;

    // 遍历输入字符串 s 中的每个字符
    for (let c of s) {
        // 将当前字符 c 添加到对应行号 i 的字符串中
        res[i] += c;

        // 如果当前行号 i 为首行或末行，改变 flag 的方向（正负号取反）
        if (i === 0 || i === numRows - 1) flag = -flag;

        // 更新行号 i，根据 flag 的值递增或递减
        i += flag;
    }

    // 将结果数组 res 中的字符串拼接起来并返回
    return res.join("");
};