首页目录 点击查看

第一题

• 难度：中等
• 题目: 6. Z 字形变换
  将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。
  比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：

L   C   I   R
E T O E S I I G
E   D   H   N

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。
请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

示例

输入: s = "LEETCODEISHIRING", numRows = 3
输出: "LCIRETOESIIGEDHN"

输入: s = "LEETCODEISHIRING", numRows = 4
输出: "LDREOEIIECIHNTSG"

解题思路

解题思路创建一个数组rows 和rowIndex,rowIndex代表的是第几行。遍历字符串的时候，rowIndex也跟着增加，只是当rowIndex大于numRows的时候就要改变方向，这个时候就要减小rowIndex，当小于0的时候就又要改变方向，rows[rowIndex] 对象是个字符串，动态的把字符拼接上去。最后把数组转为字符串输出。

答案

        var convert = function (s, numRows) {
            let rows = [];
            let rowIndex = 0
            let down = true
            for (let i = 0; i <= s.length - 1; i++) {
                !rows[rowIndex] && (rows[rowIndex] = "")
                rows[rowIndex] += s[i]
                rowIndex = down ? rowIndex + 1 : rowIndex - 1
                if (rowIndex === numRows - 1) {
                    down = false
                } else if (rowIndex === 0) {
                    down = true
                }
            }
            return rows.join("")
        };

image.png

第二题

• 难度：中等
• 题目：12. 整数转罗马数字
  罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。
示例：

输入: 3
输出: "III"

输入: 4
输出: "IV"

输入: "IX"
输出: 9

输入: 9
输出: "IX"

输入: 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.

解题思路

• 暴力解法，根据数字大小不断的和对应的罗马数字对比，然后减去已经比对过得数值，最后输出字符串。
• 贪心算法

我的答案

        var intToRoman = function (num) {
            let str = ""
            while (num >= 1) {
                if ((num / 1000) >= 1) {
                    console.log(num)
                    str += "M"
                    num = num - 1000
                } else if ((num / 900) >= 1) {
                    str += "CM"
                    num = num - 900
                } else if ((num / 500) >= 1) {
                    console.log(num)
                    str += "D"
                    num = num - 500
                } else if ((num / 400) >= 1) {
                    console.log(num)
                    str += "CD"
                    num = num - 400
                } else if ((num / 100) >= 1) {
                    str += "C"
                    num = num - 100
                } else if ((num / 90) >= 1) {
                    str += "XC"
                    num = num - 90
                } else if ((num / 50) >= 1) {
                    str += "L"
                    num = num - 50
                } else if ((num / 40) >= 1) {
                    str += "XL"
                    num = num - 40
                } else if ((num / 10) >= 1) {
                    str += "X"
                    num = num - 10
                } else if ((num / 9) >= 1) {
                    str += "IX"
                    num = num - 9
                } else if ((num / 5) >= 1) {
                    str += "V"
                    num = num - 5
                } else if ((num / 4) >= 1) {
                    str += "IV"
                    num = num - 4
                } else if ((num / 1) >= 1) {
                    str += "I"
                    num = num - 1
                }
            }
            return str
        };

image.png

• 贪心算法：
  根据上面的算法，其实可以改造一下提取公共方法，也就是贪心算法

        var intToRoman = function (num) {
            let strArray = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"],
                values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1],
                str = "",
                index = 0
            while (index < strArray.length) {
                while (num >= values[index]) {
                    str += strArray[index]
                    num = num - values[index]
                }
                index++
            }
            return str
        };

image.png

第三题

• 难度：简单
• 题目：13. 罗马数字转整数
  罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。
示例：

输入: "III"
输出: 3

输入: "IV"
输出: 4

输入: "IX"
输出: 9

输入: "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.

输入: "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

解题思路

• 遍历字符串，按着对应的表解析对应的数字并相加在一起，但是要考虑6中特殊情况，I、X、C在下一个数字的左边的时候。

我的答案

var romanToInt = function (s) {
            let num = 0
            for (let i = 0; i <= s.length - 1; i++) {

                switch (s[i]) {
                    case "I":
                        if (s[i + 1] === "V" || s[i + 1] === "X") {
                            num -= 1
                        } else {
                            num += 1;
                        }
                        break;
                    case "V":
                        num += 5;
                        break;
                    case "X":
                        if (s[i + 1] === "L" || s[i + 1] === "C") {
                            num -= 10
                        } else {
                            num += 10;
                        }
                        break;
                    case "L":
                        num += 50;
                        break;
                    case "C":
                        if (s[i + 1] === "D" || s[i + 1] === "M") {
                            num -= 100
                        } else {
                            num += 100;
                        }
                        break;
                    case "D":
                        num += 500;
                        break;
                    case "M":
                        num += 1000;
                        break
                }
            }
            return num
        };
        console.log(romanToInt("MCMXCIV"))

• 时间复杂度：O(N)

• 空间复杂度： O(N)

  
  image.png

高分答案

• 看了题解，发现还有一个方法非常好用，就是左减右加,思路就是拿下一个数和上一个数作比较，如果是小于则做减法，如果是大于右边的则做加法。

          let map = {
                    "I": 1,
                    "V": 5,
                    "X": 10,
                    "L": 50,
                    "C": 100,
                    "D": 500,
                    "M": 1000
                },
                sum = 0,
                now = 0,
                num = 0
            for (let i = 0; i <= s.length - 1; i++) {
                now = map[s[i]]
                if (num < now) {
                    sum -= num
                } else {
                    sum += num
                }
                num = now
            }
            sum += num
            return sum

image.png

但是我跑出来的性能和我之前的版本，在内存上差距还是挺大的，只是说时间几乎相当。

第四题

• 难度：简单
• 题目: 14. 最长公共前缀
  编写一个函数来查找字符串数组中的最长公共前缀。
  如果不存在公共前缀，返回空字符串 ""。

示例

输入: ["flower","flow","flight"]
输出: "fl"

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

说明：所有输入只包含小写字母 a-z 。

解题思路

创建len变量，表示当前匹配的字符串长度，has变量用于表示是否数组内的字符串都符合。
用while循环，只要has为true,而且len的长度小于第一个字符串的长度，这里按第一个字符串为标准，只要它都不符合，后面其他的也不符合了。
遍历字符串数组，每个元素和strs[0].slice(0,len)去比较，如果都符合则增加len长度，如果不符合则把has置为false，输出当前的len的字符。

答案

        var longestCommonPrefix = function (strs) {
            if (!strs.length) return ""
            let len = 0;
            let has = true
            function findStr(len) {
                let str = strs[0].slice(0, len);
                for (let i = 1; i <= strs.length - 1; i++) {
                    if (strs[i].indexOf(str) !== 0) {
                        has = false
                        return has
                    }
                }
                return has
            }
            while (has && len <= strs[0].length) {
                len += 1
                findStr(len)
            }
            return strs[0].slice(0, len - 1)
        };

image.png

第五题

• 难度：中等
• 题目：165. 比较版本号
  比较两个版本号 version1 和 version2。
  如果 version1 > version2 返回 1，如果 version1 < version2 返回 -1， 除此之外返回 0。
  你可以假设版本字符串非空，并且只包含数字和 . 字符。
  . 字符不代表小数点，而是用于分隔数字序列。
  例如，2.5 不是“两个半”，也不是“差一半到三”，而是第二版中的第五个小版本。
  你可以假设版本号的每一级的默认修订版号为 0。例如，版本号 3.4 的第一级（大版本）和第二级（小版本）修订号分别为 3 和 4。其第三级和第四级修订号均为 0。

示例

输入: version1 = "0.1", version2 = "1.1"
输出: -1

输入: version1 = "1.0.1", version2 = "1"
输出: 1

输入: version1 = "7.5.2.4", version2 = "7.5.3"
输出: -1

输入：version1 = "1.01", version2 = "1.001"
输出：0
解释：忽略前导零，“01” 和 “001” 表示相同的数字 “1”。

解题思路

• 这道题简单来说就是把两个字符串都转换为数组后，按顺序进行比较，只要有一个大于或小于就可以判断出来。

我的答案

var compareVersion = function (version1, version2) {
    let v1Array = version1.split(".");
    let v2Array = version2.split(".");
    let len = v1Array.length > v2Array.length ? v1Array.length : v2Array.length;
    for (let i = 0; i <= len - 1; i++) {
        let n1 = Number(v1Array[i]) || 0
        let n2 = Number(v2Array[i]) || 0
        if (n1 > n2) {
            return 1
        } else if (n1 < n2) {
            return -1
        } else {
            continue
        }
    }
    return 0
};

• 时间复杂度：O(N)

  
  image.png

第六题

• 难度：中等
• 题目： 443. 压缩字符串
  给定一组字符，使用原地算法将其压缩。
  压缩后的长度必须始终小于或等于原数组长度。
  数组的每个元素应该是长度为1 的字符（不是 int 整数类型）。
  在完成原地修改输入数组后，返回数组的新长度。
  进阶：
  你能否仅使用O(1) 空间解决问题？

示例

输入：
["a","a","b","b","c","c","c"]

输出：
返回 6 ，输入数组的前 6 个字符应该是：["a","2","b","2","c","3"]

说明：
"aa" 被 "a2" 替代。"bb" 被 "b2" 替代。"ccc" 被 "c3" 替代。

解题思路

• 这道题的方法就是按顺序找当前字符是否和下一位字符相等，相等就累加，不相等，把累加的数字替换重复的数字，主要要动态的处理index变化。因为替换后数字的长度就发生了变化。

我的答案

var compress = function (chars) {
    let index = 0;
    let num = 1;
    while (index <= chars.length - 1) {
        let len = 0;
        if (chars[index + 1] !== chars[index]) {
            if (num > 1) {
                len = num - num.toString().length - 1;
                chars.splice(index + 1 - num, num, chars[index], ...num.toString().split(""))
            }
            index = index - len
            num = 1
        } else {
            num += 1
        }
        index++
    }
};

image.png

第七题

• 难度：中等
• 题目： 468. 验证IP地址
  编写一个函数来验证输入的字符串是否是有效的 IPv4 或 IPv6 地址。
  如果是有效的 IPv4 地址，返回 "IPv4" ；
  如果是有效的 IPv6 地址，返回 "IPv6" ；
  如果不是上述类型的 IP 地址，返回 "Neither" 。
  IPv4 地址由十进制数和点来表示，每个地址包含 4 个十进制数，其范围为 0 - 255， 用(".")分割。比如，172.16.254.1；
  同时，IPv4 地址内的数不会以 0 开头。比如，地址 172.16.254.01 是不合法的。
  IPv6 地址由 8 组 16 进制的数字来表示，每组表示 16 比特。这些组数字通过 (":")分割。比如, 2001:0db8:85a3:0000:0000:8a2e:0370:7334 是一个有效的地址。而且，我们可以加入一些以 0 开头的数字，字母可以使用大写，也可以是小写。所以， 2001:db8:85a3:0:0:8A2E:0370:7334 也是一个有效的 IPv6 address地址 (即，忽略 0 开头，忽略大小写)。
  然而，我们不能因为某个组的值为 0，而使用一个空的组，以至于出现 (::) 的情况。 比如， 2001:0db8:85a3::8A2E:0370:7334 是无效的 IPv6 地址。
  同时，在 IPv6 地址中，多余的 0 也是不被允许的。比如， 02001:0db8:85a3:0000:0000:8a2e:0370:7334 是无效的。

示例

输入：IP = "172.16.254.1"
输出："IPv4"
解释：有效的 IPv4 地址，返回 "IPv4"

输入：IP = "2001:0db8:85a3:0:0:8A2E:0370:7334"
输出："IPv6"
解释：有效的 IPv6 地址，返回 "IPv6"

输入：IP = "256.256.256.256"
输出："Neither"
解释：既不是 IPv4 地址，又不是 IPv6 地址

输入：IP = "2001:0db8:85a3:0:0:8A2E:0370:7334:"
输出："Neither"

解题思路

• 这道题就是先判断是否包含.和:，分别分开处理，将字符转化为数组，判断数组长度，ipv4好判断，只需要遍历每个元素是否在0-255的区间内，而ipv6则稍微麻烦一点，需要单个判断每个字符是否是16进制的。

我的答案

        var validIPAddress = function (IP) {
            if (IP.indexOf(".") !== -1) {
                let array = IP.split(".");
                if (array.length !== 4) {
                    return "Neither"
                } else {
                    for (let i = 0; i <= array.length - 1; i++) {
                        if (array[i] !== Number(array[i]).toString()) {
                            return "Neither"
                        } else if (array[i] <= 255 && array[i] >= 0) {
                            continue
                        } else {
                            return "Neither"
                        }
                    }
                    return 'IPv4'
                }
            } else if (IP.indexOf(":") !== -1) {
                let array = IP.split(":");
                if (array.length !== 8) {
                    return "Neither"
                } else {
                    let boolean = true
                    array.forEach((item) => {
                        (!item || item.length > 4 || item.length === 0) && (boolean = false);
                        for (let i = 0; i <= item.length - 1; i++) {
                            let value = item[i].toUpperCase().charCodeAt()
                            if ((value < 48 || value > 57) && (value < 65 || value > 70)) {
                                boolean = false
                            }
                        }
                    })
                    if (boolean) {
                        return "IPv6"
                    }
                    return "Neither"
                }
            } else {
                return "Neither"
            }
        };

image.png

第八题

• 难度：中等
• 题目：686. 重复叠加字符串匹配
  给定两个字符串 a 和 b，寻找重复叠加字符串 a 的最小次数，使得字符串 b 成为叠加后的字符串 a 的子串，如果不存在则返回 -1。
  注意：字符串 "abc" 重复叠加 0 次是 ""，重复叠加 1 次是 "abc"，重复叠加 2 次是 "abcabc"。

示例

输入：a = "abcd", b = "cdabcdab"
输出：3
解释：a 重复叠加三遍后为 "abcdabcdabcd", 此时 b 是其子串。

输入：a = "a", b = "aa"
输出：2

输入：a = "abc", b = "wxyz"
输出：-1

解题思路

• 这道题很简单，主要是边界的确定，因为一个完整的B可能首部用到A的一部分，尾部用到A的一部分，像这样A'[AA....AA]A' , [ ] 内必然<=B的长度，故总长<=2*A+B

我的答案

var repeatedStringMatch = function (a, b) {
    if (a.indexOf(b) !== -1) { //如果a直接包含b
        return 1
    }
    let num = 1
    let str = a
    while (str.length <= (b.length + a.length * 2)) { //判断的最大边界是b.length + a.length * 2
        str += a;
        num += 1
        if (str.indexOf(b) !== -1) { //如果b存在于新的strz中返回重复的次数
            return num
        }
    }
    return -1
};

image.png