这是我参与更文挑战的第 15 天，活动详情查看 更文挑战

122. 最长公共前缀 (longest-common-prefix)

标签

• 字符串
• 简单

题目

leetcode 传送门

这里不贴题了，leetcode打开就行，题目大意：

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

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

示例 1：

输入：strs = ["flower","flow","flight"]
输出："fl"

示例 2：

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

基本思路

先做个广告，我上一篇思维题很有意思，可以一看放松下脑子。 点击这里快速进入

本题有个技巧，可以先对这些字符数组进行排序，排完之后，我们只需要对头尾两个元素进行公共前缀查询就行了。

第二个点，公共前缀 Js 中可以用一个判断字符串是否以某个字符开头的 api 函数会较简单。

String.prototype.startsWith()

例子

const str1 = 'Saturday night plans';

console.log(str1.startsWith('Sat'));
// expected output: true

console.log(str1.startsWith('Sat', 3));
// expected output: false

console.log(str1.startsWith('urday', 3));
// 从坐标 3开始，就是 true

语法

参数

• searchString

要搜索的子字符串。

• position 可选

在 str 中搜索 searchString 的开始位置，默认值为 0。

返回值

描述

写法实现

var longestCommonPrefix = function(strs) {
    let [res, len] = ["", strs.length]
    // 特判 len = 0
    if (len === 0) {
        return ""
    }
    // 特判 len = 1
    if (len === 1) {
        return strs[0]
    }
    // 我们可以先简化这个问题，因为 Js 数组可以按字典序排序 sort()
    // 排序后数组只需比较头尾两个元素，找出最长公共前缀
    let startStr = strs.sort()[0]
    let endStr = strs.sort()[len - 1]
    
    for (let i = 0; i < startStr.length; i++) {
        let temp = startStr.substring(0, i+1)
        // 同时以截取的字符串开头，res 就是公共子串
        if (startStr.startsWith(temp) && endStr.startsWith(temp)) {
            res = temp
        }
    }
    return res
};

let strs = ["flower", "flight", "flow"]
console.log(longestCommonPrefix(strs))

123. 最长连续递增序列 (longest-continuous-increasing-subsequence)

标签

• Array
• 简单

题目

leetcode 传送门

这里不贴题了，leetcode打开就行，题目大意：

给定一个未经排序的整数数组，找到最长且连续递增的子序列，并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

示例 1：

输入：nums = [1,3,5,4,7]
输出：3
解释：最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。 

示例 2：

输入：nums = [2,2,2,2,2]
输出：1
解释：最长连续递增序列是 [2], 长度为1。

基本思路

思路还是比较简单的，就是遍历数组，记录下历史最大，和当前的长度比较更新最大值，遍历到最后，得到最长连续递增序列。代码注释应该已经比较清晰。

写法实现

var findLengthOfLCIS = function(nums) {
    if (nums.length === 0) {
        return 0;
    }
    // curCount 记录本次循环时当前递增序列长度
    let [res, curCount, len] = [0, 1, nums.length]
    for (let i = 0; i < len; i++) {
        if (nums[i] < nums[i+1]) {
            // console.log(nums[i], '==')
            curCount++;
        } else {
            // 说明递增断了，从当前，记录下一个递增序列吧
            curCount = 1;
        }
        // 当前递增序列长度跟历史比较取最大
        res = Math.max(res, curCount)
    }
    return res
}

let nums = [1,3,5,4,7]
console.log(findLengthOfLCIS(nums))

今天就到这儿，想跟我一起刷题的小伙伴可以加我微信哦 点击此处交个朋友 Or 搜索我的微信号infinity_9368，可以聊天说地 加我暗号 "天王盖地虎" 下一句的英文，验证消息请发给我 presious tower shock the rever monster，我看到就通过，加了之后我会尽我所能帮你，但是注意提问方式，建议先看这篇文章：提问的智慧

参考

• developer.mozilla.org/zh-CN/docs/…