《剑指Offer》-02字符串

发表于 | 分类于

tip: 在VS Code中有一个插件——code runner，可以安装后直接运行在node 环境中，然后在vscode中输出文件的结果。

替换空格

题目描述 简单
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

方法一：正则

1
2
3
4
function replaceSpace(str)
{
    return str.replace(/\s/g,"%20");
}

方法二：切片再聚合

1
2
3
4
function replaceSpace(str)
{
    return str.split(" ").join("%20");
}

正则表达式匹配

题目描述 困难
请实现一个函数用来匹配包括’.’和’*‘的正则表达式。模式中的字符’.’表示任意一个字符，而’*‘表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”ab\ac\a”匹配，但与”aa.a”和”ab*a”均不匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//s, pattern都是字符串
function match(s, pattern) {
    // write code here
    if (s === null || pattern === null) {
        return false;
    }
    return matchCore(s, 0, pattern, 0)
}

function matchCore(s, s_index, pattern, p_index) {
    //有效性检验：s到尾，pattern到尾，匹配成功
    if (s_index === s.length && p_index === pattern.length) {
        return true;
    }
    //pattern先到尾，匹配失败
    if (s_index !== s.length && p_index === pattern.length) {
        return false;
    }
    //模式第2个是*，且字符串第1个跟模式第1个匹配,分3种匹配模式；如不匹配，模式后移2位
    if (p_index + 1 < pattern.length && pattern[p_index + 1] === '*') {
        if ((s_index !== s.length && pattern[p_index] === s[s_index]) || (s_index !== s.length && pattern[p_index] === '.')) {
            return (matchCore(s, s_index, pattern, p_index + 2)//模式后移2，视为x*匹配0个字符
                || matchCore(s, s_index + 1, pattern, p_index + 2)//视为模式匹配1个字符
                || matchCore(s, s_index + 1, pattern, p_index))//*匹配1个，再匹配s中的下一个
        }
        else {
            return matchCore(s, s_index, pattern, p_index + 2);
        }
    }

    //模式第2个不是*，且字符串第1个跟模式第1个匹配，则都后移1位，否则直接返回false
    if (s_index !== s.length && pattern[p_index] === s[s_index] || pattern[p_index] === '.' && s_index !== s.length) {
        return matchCore(s, s_index + 1, pattern, p_index + 1);
    } else {
        return false;
    }
}

总结：思路来自于牛客网讨论区题解
链接：https://www.nowcoder.com/questionTerminal/45327ae22b7b413ea21df13ee7d6429c?f=discussion
当模式中的第二个字符不是“*”时：
1、如果字符串第一个字符和模式中的第一个字符相匹配，那么字符串和模式都后移一个字符，然后匹配剩余的。
2、如果 字符串第一个字符和模式中的第一个字符相不匹配，直接返回false。

而当模式中的第二个字符是“*”时：
如果字符串第一个字符跟模式第一个字符不匹配，则模式后移2个字符，继续匹配。如果字符串第一个字符跟模式第一个字符匹配，可以有3种匹配方式：
1、模式后移2字符，相当于x*被忽略；
2、字符串后移1字符，模式后移2字符；
3、字符串后移1字符，模式不变，即继续匹配字符下一位，因为*可以匹配多位；

表示数值的字符串

题目描述 中等
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100”,”5e2”,”-123”,”3.1416”和”-1E-16”都表示数值。 但是”12e”,”1a3.14”,”1.2.3”,”+-5”和”12e+4.3”都不是。

1
2
3
4
5
6
7
//s字符串
function isNumeric(s)
{
    // write code here
    var reg=/^[+-]?\d*\.?\d+(e[+-]?\d+)?$/i;
    return reg.test(s);
}

总结：正则相关知识点复习

  1. 开头符 ^ 和 结尾符 $ 界定待匹配字符串的界限；
  2. [+-]? 匹配字符串开头的正负号，可正可负，也可以没有正负号；
  3. \d*\.?\d+ 表示数字部分，\d为匹配[0-9]的数字 * 表示0次或多次 + 表示至少1次
  4. (\[e][+-]?\d+)? 表示科学计数法，可有可无；
  5. JavaScript中可以给正则表达式设置 i标识，以忽略匹配规则中的大小写。

字符流中第一个不重复的字符

题目描述
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符”go”时，第一个只出现一次的字符是”g”。当从该字符流中读出前六个字符“google”时，第一个只出现一次的字符是”l”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function Init()
{
    map={};
}

function Insert(ch){
    if(map[ch]){
        map[ch]+=1;
    }else{
        map[ch]=1;
    }
}

function FirstAppearingOnce(){
    for(const index in map){
        if(map[index]===1){
            return index;
        }
    }
    return '#';
}

总结：遍历
for循环–array
for…in –Object
for…of –一切可遍历的元素（数组、对象、集合）等

for…of 语句创建一个循环来迭代可迭代的对象。在 ES6 中引入的 for…of 循环，以替代 for…in 和 forEach() ，并支持新的迭代协议。for…of 允许你遍历 Arrays（数组）, Strings（字符串）, Maps（映射）, Sets（集合）等可迭代的数据结构等。

0%