image frame

四月八日

Google 搜索提示您的连接不是私密连接 NET::ERR_CERT_AUTHORITY_INVALID

其他

  • Google 浏览器搜索报错，但是可以使用翻译等功能，但不能搜索。

原因

  • chrome将你输入的字符转换成google搜索指令时出错所致。新版chrome为增强安全性，对非https的地址会报如上错误。

  • 也可能是运营商网络原因

解决办法

删除原来的goole搜索引擎，手动输入一个新的即可。

  • 进入设置

  • 进入管理搜索引擎

  • 点击添加

  • 填入下面几项

搜索引擎： Goolge 或任意名字

关键字： www.google.com.hk

网址格式： https://www.google.com.hk/search?q=%s&{google:RLZ}{google:originalQueryForSuggestion}{google:assistedQueryStats}{google:searchFieldtrialParameter}{google:iOSSearchLanguage}{google:searchClient}{google:sourceId}{google:instantExtendedEnabledParameter}{google:contextualSearchVersion}ie={inputEncoding}

  • 保存并选设为默认选项

58. 最后一个单词的长度

算法 / 关联题目
LeetCode

解法一

  • 因为是从查找最后一个单词，考虑从后向前匹配

  • 因为有以一个或多个空字符串结尾的情况，所以如果先遇到空字符串则跳过，从遇到的第一个字符串开始基数，再次遇到空格则返回结果

  • 注意边界的处理，如果字符串为空，返回0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var lengthOfLastWord = function (s) {
    // 边界处理
    if (s === '') return 0
    var i = s.length - 1;
    var res = 0;
    for (; i >= 0; i--) {
        if (s[i] === ' ' && res !== 0) {
            return res;
        }
        else if(s[i] !== ' '){
            res++;
        }
        //跳过空字符串的情况
    }
    return res;
};

复杂度分析

  • 时间复杂度：

  • 空间复杂度：

方法二

1
2
3
4
var lengthOfLastWord = function(s) {
    if(s==='') return 0
    return s.trim().split(' ').pop().length;
};

文件和目录命令

Linux / 基础命令
目录 说明
/bin 存放⼆二进制可执⾏行行⽂文件(ls,cat,mkdir等)，常⽤用命令⼀一般都在这⾥里里。
/etc 存放系统管理理和配置⽂文件
/home 存放所有⽤用户⽂文件的根⽬目录，是⽤用户主⽬目录的基点，⽐比如⽤用户user的主⽬目录就是/home/user，可以⽤用~user表示
/usr ⽤用于存放系统应⽤用程序，⽐比较重要的⽬目录/usr/local 本地系统管理理员软件安装⽬目录（安装系统级的应⽤用）。这是最庞⼤大的⽬目录，要⽤用到的应⽤用程序和⽂文件⼏几乎都在这个⽬目录。/usr/x11r6 存放x window的⽬目录/usr/bin 众多的应⽤用程序/usr/sbin超级⽤用户的⼀一些管理理程序/usr/doc linux⽂文档/usr/include linux下开发和编译应⽤用程序所需要的头⽂文件/usr/lib 常⽤用的动态链接库和软件包的配置⽂文件/usr/man 帮助⽂文档/usr/src 源代码，linux内核的源代码就放在/usr/src/linux⾥里里/usr/local/bin本地增加的命令/usr/local/lib 本地增加的库
/opt 额外安装的可选应⽤用程序包所放置的位置。⼀一般情况下，我们可以把tomcat等都安装到这⾥里里。
/proc 虚拟⽂文件系统⽬目录，是系统内存的映射。可直接访问这个⽬目录来获取系统信息。
/root 超级⽤用户（系统管理理员）的主⽬目录（特权阶级^o^）
/sbin 存放⼆二进制可执⾏行行⽂文件，只有root才能访问。这⾥里里存放的是系统管理理员使⽤用的系统级别的管理理命令和程序。如ifconfig等。
/dev ⽤用于存放设备⽂文件。
/mnt 系统管理理员安装临时⽂文件系统的安装点，系统提供这个⽬目录是让⽤用户临时挂载其他的⽂文件系统。
/boot 存放⽤用于系统引导时使⽤用的各种⽂文件
/lib 存放跟⽂文件系统中的程序运⾏行行所需要的共享库及内核模块。共享库⼜又叫动态链接共享库，作⽤用类似windows⾥里里的.dll⽂文件，存放了了根⽂文件系统程序运⾏行行所需的共享⽂文件。
/tmp ⽤用于存放各种临时⽂文件，是公⽤用的临时⽂文件存储点。
/var ⽤用于存放运⾏行行时需要改变数据的⽂文件，也是某些⼤大⽂文件的溢出区，⽐比⽅方说各种服务的⽇日志⽂文件（系统启动⽇日志等。）等。
/lost+found 这个⽬目录平时是空的，系统⾮非正常关机⽽而留留下“⽆无家可归”的⽂文件（windows下叫什什么.chk）就在这⾥里里
序号 命令 对应英文 作用
01 ls list 查看当前文件夹下内容
02 pwd print work directory 查看当前所在文件夹

ls命令

linux 下文件和目录的特点

  • Linux 文件或目录名称最长可以有256个字符
  • 以.开头的文件为隐藏文件
  • .代表当前目录
  • ..代表上一级目录

ls 命令常用选项

参数 意义
-a 显示指定目录下所有子目录和文件，包括隐藏文件
-l 以列表方式显示文件详细信息
-h 配合-l命令更直观的方式显示文件大小 
1
ls -lh

ls 通配符

通配符 含义
* 代表人一个数字符
？ 代表任意一个字符，至少一个
[] 匹配其中的任意一个 
1
ls [abc].txt

cd

命令 含义
cd 切换到当前用户的主目录（/home/用户目录）
cd ~ 切换到当前用户的主目录（/home/用户目录）
cd . 保持当前目录不变
cd .. 上级目录
cd - 可以在最近两次工作目录间切换

相对路径和绝对路径

  • 相对路经：在输入路径时，最前面的不是/或者～，表示相对当前目录所在位置的目录位置

  • 绝对路径：在输入路径时，最前面是/或者～，表示从根目录/家目录开始的目录位置

pwd

其功能是显示当前所在工作目录的全路径。主要用在当不确定当前所在位置时，通过pwd来查看当前目录的绝对路径。

-L --logical 显示当前的路径，有连接文件时，直接显示连接文件的路径，(不加参数时默认此方式).
-p --physical，显示当前的路径，有连接文件时，不使用连接路径，直接显示连接文件所指向的文件，参考示例2。 当包含多层连接文件时，显示连接文件最终指向的文件.

创建和删除

创建文件touch

创建文件或修改文件时间

  • 如果文件不存在，可以创建一个空白文件

  • 如果文件存在，可以修改文件的修改日期

创建目录mkdir

选项 含义
-p 可以递归创建目录 
1
mkdir -p a/b/c

新建目录名称不能与当前目录中已有的目录或文件重复

删除命令rm

删除文件或目录，不能恢复

选项 含义
-f 强制删除，忽略不存在的文件，无需提示
-r 递归删除目录下面的内容，删除文件必须添加此参数 
1
rm -rf workspace

修改文件权限

序号 命令 作用
01 chown 修改拥有者
02 chgrp 修改组
03 chmod 修改权限

修改文件|目录的拥有者

1
chown 用户名 文件名|目录名

递归修改文件|目录的组

1
chown 用户名 文件名|目录名

常见数字组合有（u表示用户／g表示组／o表示其他）：

  • 777 ===> u=rwx,g=rwx,o=rwx
  • 755 ===> u=rwx,g=rx,o=rx
  • 644 ===> u=rw,g=r,o=r

用户权限和组管理

Linux / 基础命令

基本概念

  • 用户 是 Linux 系统工作中重要的一环，用户管理包括 用户 与 组 管理

  • 在 Linux 系统中，不论是由本机或是远程登录系统，每个系统都必须拥有一个账号，并且对于不同的系统资源拥有不同的使用权限

  • 在 Linux 中，可以指定 每一个用户 针对 不同的文件或者目录 的 不同权限对 文件／目录 的权限包括：

序号 权限 英文 缩写 数字代号
01 读 read r 4
02 写 write w 2
03 执行 excute x 1

组

  • 为了方便用户管理，提出了 组 的概念，如下图所示

  • 在实际应用中，可以预先针对 组 设置好权限，然后 将不同的用户添加到对应的组中，从而不用依次为每一个用户设置权限

ls -l 扩展

  • ls -l 可以查看文件夹下文件的详细信息，从左到右依次是：

    • 权限，第 1 个字符如果是 d 表示目录

    • 硬链接数，通俗地讲，就是有多少种方式，可以访问到当前目录／文件

      文件硬链接数为1，只能通过一种绝对路径访问

      文件夹的硬连接数取决于子文件夹的数量，可以在当前文件夹通过 .方法，也可以在子文件夹通过 .. 访问

    • 拥有者，家目录下 文件／目录 的拥有者通常都是当前用户

    • 组，在 Linux 中，很多时候，会出现组名和用户名相同的情况

    • 大小

    • 创建/修改时间

    • 名称

chmod

chmod 可以修改 用户／组 对 文件／目录 的权限

1
chmod +/-rwx 文件名|目录名

以上方式会一次性修改 拥有者 / 组 权限

读权限控制目录是否可以被访问

取消文件的可读可写权限

1
chmod -rw xxx.md

增加文件的可读权限

1
chmod +r xxx.md

在添加文件的可执行权限后,文件名变为绿色

1
chmod +x test.js

对目录的权限操作

  • 可读权限控制目录是否可以被访问

  • 可读权限控制目录中是否可以创建文件

  • 可读可写都需要可执行权限,且如果没有可执行权限目录不能被访问

超级用户

  • Linux 系统中的 root 账号通常 用于系统的维护和管理，对操作系统的所有资源 具有所有访问权限

  • 在大多数版本的 Linux 中，都不推荐 直接使用 root 账号登录系统

  • 在 Linux 安装的过程中，系统会自动创建一个用户账号，而这个默认的用户就称为“标准用户”

sudo

  • su 是 substitute user 的缩写，表示 使用另一个用户的身份

  • sudo 命令用来以其他身份来执行命令，预设的身份为 root

  • 用户使用 sudo 时，必须先输入密码，之后有 5 分钟的有效期限，超过期限则必须重新输入密码

若其未经授权的用户企图使用 sudo，则会发出警告邮件给管理员

组管理

创建组 / 删除组 的终端命令都需要通过 sudo 执行

序号 命令 作用
01 groupadd 组名 添加组
02 groupdel 组名 删除组
03 cat /etc/group 确认组信息
04 chgrp -R 组名 文件/目录名 递归修改文件/目录的所属组

组信息保存在 /etc/group 文件中

/etc 目录是专门用来保存 系统配置信息 的目录

在实际应用中，可以预先针对 组 设置好权限，然后 将不同的用户添加到对应的组中，从而不用依次为每一个用户设置权限

  • 新建文件夹dev
1
mkdir zhen
  • 新建组zhengrp
1
sudo groupadd zhengrp
  • 把zhen目录的组修改为zhengrp
1
sudo chgrp -R zhengrp zhen

53.最大子序和

算法 / 关联题目
LeetCode

暴力解法 窗口移动

  • 指定窗口大小，初始窗口大小为1。
  • 向右移动窗口并计算窗口内的元素和，直到窗口移动到数组尾部结束。
  • 在移动的过程中，比较窗口内的和是否比上一次大，如果比上一次大记录最大值。
  • 扩大窗口大小，并重复上面过程，直到窗口大小与数组大小相同，并返回最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var maxSubArray = function (nums) {
    var sum;
    for (var i = 0; i < nums.length; i++) {
        for (var j = 0; j + i < nums.length; j++) {
            var temp = 0;
            for (var k = 0; k < i + 1; k++) {
                temp += nums[j + k];
            }
            if (sum === undefined) sum = temp
            if (temp > sum) sum = temp;
        }
    }
    return sum;
};

复杂度分析

  • 时间复杂度：,时间复杂度较高，数据量大的时候可能通不过测试。

  • 空间复杂度：

暴力解法优化

  • 不需要确认窗口大小，只需要每次遍历到数组结尾即可
  • 也可以理解为线改变窗口大小遍历，下一次移动启示位置之后重新遍历窗口大小

1
2
3
4
5
6
7
8
9
10
11
12
var maxSubArray = function (nums) {
  var sum;
  for (var i = 0; i < nums.length; i++) {
      var temp = 0;
      for (var j = i; j < nums.length; j++) {
          temp += nums[j];
          if (temp > sum || sum === undefined) sum = temp;
      }
  }
  return sum;
};

复杂度分析

  • 时间复杂度：

  • 空间复杂度：

动态规划

我们用 代表 nums[i]，用 代表以第 个数结尾的「连续子数组的最大和」，那么很显然我们要求的答案就是：

因此我们只需要求出每个位置的 ，然后返回 数组中的最大值即可。那么我们如何求 呢？我们可以考虑 单独成为一段还是加入 对应的那一段，这取决于 和的大小，我们希望获得一个比较大的，于是可以写出这样的动态规划转移方程：

关键在于 子数组最大值的求法，为什么两两比较的最大值是最终最大字串的值？

  • 首先需要舍弃索引的概念，并不需要通过索引区间记录哪个区间字串的和最大
  • 每一次的结果是基于上一次的最大值比较的,从长度等于1开始，所以取和中最大的就是子数组中的最大的原因就在于此，因为上一次的结果就是最优解（最大值），所以本次只需要比较一次就可以了
  • 最后每次更新保存最终最大值的变量就可以了
1
2
3
4
5
6
7
8
9
10
11
var maxSubArray = function (nums) {
    var sum_endof_here = nums[0];
    var sum_far_from = nums[0];
    for (var i = 1; i < nums.length; i++) {
        // 只有在当前值大于之前的和时，之前的值才会被丢弃，
        // 否则前面的值无论怎样波动增大或减小，但此时此刻加上当前值，就是当前子数组的最大值
        sum_endof_here = Math.max(nums[i], nums[i] + sum_endof_here);
        sum_far_from = Math.max(sum_far_from, sum_endof_here);
    }
    return sum_far_from;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
var maxSubArray = function (nums) {
    var sum_endof_here = 0;
    var sum_far_from = nums[0];
    for (var i = 0; i < nums.length; i++) {
        // 等同于 if(sum_endof_here>0){}
       if(sum_endof_here+ nums[i]>nums[i]){
        sum_endof_here = sum_endof_here+ nums[i]
       }else{
        sum_endof_here = nums[i];
       }
       sum_far_from = Math.max(sum_far_from,sum_endof_here)
    }
    return sum_far_from;
};

  • 时间复杂度： 只需要遍历一次数组就可以得到结果。

  • 空间复杂度：

分治

38. 外观数列

算法 / 关联题目
LeetCode

注意

  • 处理边界情况，当n==1返回'1'

暴力解法 循环+使用栈结构

使用数组来处理统计字符个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var countAndSay = function (n) {
    if (n === 1) return '1';
    var res = '1',
        i = 1;
    for (; i < n; i++) {
        var str = '';
        var count = 0;
        var stack = [];
        for (var j = 0; j < res.length; j++) {
            if (stack[0] !== undefined && stack[0] !== res[j]) {
                str += stack.length + stack[0];
                stack = [];
            }
            stack.push(res[j])
        }
        if (stack.length) {
            str += stack.length + stack[0];
        }
        res = str;
    }
    return res;
};

优化 双指针

在处理字符个数时有个很通用且巧妙的解法，使用双指针来统计连续字符串出现的个数

计数二进制子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var countAndSay = function (n) {
    if (n === 1) return '1';
    var res = '1';
    for (var i = 1; i < n; i++) {
        var j = 0;
        var temp = '';
        for (var k = 0; k < res.length; k++) {
            if (res[j] !== res[k]) {
                temp += String(k - j) + res[j];
                j = k;
            }
        }
        temp += String(k - j) + res[j];
        res = temp;
    }
    return res;
};

递归

可以把循环n时改为递归的形式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var countAndSay = function (n) {
    if (n === 1) return '1';
    var res = countAndSay(n - 1);
    var j = 0;
    var temp = '';
    for (var k = 0; k < res.length; k++) {
        if (res[j] !== res[k]) {
            temp += String(k - j) + res[j];
            j = k;
        }
    }
    temp += String(k - j) + res[j];
    return temp
};

35. 搜索插入位置

算法 / 关联题目

搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

1
2
输入: [1,3,5,6], 2
输出: 1

注意

  • 如果数组中已经存在相同的数字，插入位置是当前数字的前一位
    1
    2
    输入: [1,3,5,6], 5
    输出: 2

暴力解法

1
2
3
4
5
6
7
8
9
10
11
12
13
var searchInsert = function (nums, target) {
    var i = 0,
        len = nums.length;
    // 处理边界
    if (nums[len - 1] < target) return len;
    if (nums[len - 1] === target) return len - 1;
    for (; i < len - 1; i++) {
        if (nums[i] === target) return i;
        if (nums[i] < target && nums[i + 1] > target) {
            return i + 1;
        }
    }
};

二分法

此题很容易想到用二分法解决，如果在一个给定范围的数组中查询某一项，大概率可以使用二分法。

思路

  • 定义左下标left,和右下标right
  • 计算mid=Math.floor(left+right),向下取整保证下表位整数
  • 根据nums[mid]值来判断，如果nums[mid]===target 返回mid，如果nums[mid]<target说明mid左侧值全都比mid小，下次比较时只需要关心mid右侧值，所以left变为mid的下一位，left=mid+1. 同理，nums[mid]>target 只需要关心mid左侧值，right=mid-1
  • 最后如果没有和mid相等的情况是返回left即位插入的位置.


为什么可以使用left作为返回结果？
因为向下取整所以在相邻位置时left===mid

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var searchInsert = function (nums, target) {
    var len = nums.length,
        left = 0,
        right = (0, len - 1);
    while (left <= right) {
        mid = Math.floor((right + left) / 2)
        if (nums[mid] === target) {
            return mid;
        }
        if (nums[mid] < target) {
            left = mid + 1;
        }
        if (nums[mid] > target) {
            right = mid - 1
        }
    }
    return left;
};

复杂度分析

  • 时间复杂度：

  • 空间复杂度：

2. 两数相加

算法 / 关联题目
LeetCode

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

1
2
3
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

分析

  • 观察题目可能会思考，如何实现进位，和从低位开始依次相加？
  • 进位可以通过一个变量来控制
  • 按位相加其实就是从链表的根节点依次相加，因为l1,l2两个链表表示的数字是从地位到高位。

基于以上分析何以做一个简单的实现

简单实现

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
 var addTwoNumbers = function (l1, l2) {
    //新链表
    var head = {
        next: null
    }
    //头指针
    var cur = head;
    //当前为的和
    var sum = 0;
    //进位
    var curry = 0;
    while (l1 !== null || l2 !== null) {
        if (l1 && l2) {
            sum = (l1.sum + l2.sum + curry) % 10;
            curry = (l1.sum + l2.sum + curry) / 10 | 0;
            l1 = l1.next;
            l2 = l2.next;
        }
        if (l1 && !l2) {
            sum = l1.sum
            l1 = l1.next;
        }
        if (!l1 && l2) {
            sum = l2.sum
            l2 = l2.next;
        }
        cur.next = {
            sum: sum,
            next: null
        }
        cur = cur.next;
    }
    return head.next
};

处理边界

虽然上面的代码可以正确输出 7 -> 0 -> 8 的新链表，但是存在很多问题

  • 有一个链表为空时没有判断
    如果l1===null 应该直接返回 l2 无需关新 l2 是否为空

  • 边界判断
    如果是 [5],[5] 这样的两个链表求和时，没有在while中判断carry是否为有值，不应该直接跳出循环。

  • 边界判断
    如果是 [1],[999] 这样的两个链表求和时,即使[1].next===null, 也需要每次循环判断是否需要进位

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
38
39
40
41
42
43
44

var addTwoNumbers = function (l1, l2) {
    // 判断边界条件
    if (l1 === null) return l2;
    if (l2 === null) return l1;
    var head = {
        next: null
    }
    var cur = head;
    var sum = 0;
    var carry = 0;
    //有进位是需要继续处理
    while (l1 !== null || l2 !== null || carry) {
        if (l1 && l2) {
            sum = (l1.sum + l2.sum + carry) % 10;
            carry = (l1.sum + l2.sum + carry) / 10 | 0;
            l1 = l1.next;
            l2 = l2.next;
        } else {
            if (!l1 && !l2) {
                sum = carry;
                carry = 0;
            }
            // 处理[999]+[1] 的情况，即使另一个链表为空，也需要注意是否回合当链表的值，产生进位的情况
            if (l1 && !l2) {
                sum = (l1.sum + carry) % 10;
                //位运算取强制转换位整数 等同于Math.floor()
                carry = (l1.sum + carry) / 10 | 0;
                l1 = l1.next;
            }
            if (!l1 && l2) {
                sum = (l2.sum + carry) % 10;
                carry = (l2.sum + carry) / 10 | 0;
                l2 = l2.next;
            }
        }
        cur.next = {
            sum: sum,
            next: null
        }
        cur = cur.next;
    }
    return head.next
};

优化算法

  • 清除重复计算,有大量重复的求和与求进位的运算

    1
    2
    sum = (l2.sum + carry) % 10;
    carry = (l2.sum + carry) / 10 | 0;

  • 相似的条件语句，我们分别判断 l1 && !l2 和 !l1 && l2 等情况，其实只需要关心，是否l1 !== null || l2 !== null, 如果其中一个链表先位null，它的值可以用0来代替，从而避免大量重复计算

  • 经过上面一条的优化，边界条件carry,只需要在循环结束时判断一次即可

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
var addTwoNumbers = function (l1, l2) {
    var head = {
            next: null
        },
        cur = head,
        carry = 0;
    while (l1 !== null || l2 !== null) {
        var x = l1 !== null ? l1.val : 0,
            y = l2 !== null ? l2.val : 0,
            sum = x + y + carry;
        carry = sum / 10 | 0;
        cur.next = {
            val: sum % 10,
            next: null
        }
        cur = cur.next;
        l1 = l1 !== null ? l1.next : l1
        l2 = l2 !== null ? l2.next : l2
    }
    if (carry > 0) {
        cur.next = {
            val: carry,
            next: null
        }
    }
    return head.next
};

复杂度分析

  • 时间复杂度： ，假设 和 分别表示 和 的长度，上面的算法最多重复 次。

  • 空间复杂度：。使用的额外空间复杂度为常数。

28. 实现 strStr()

算法 / 关联题目
LeetCode

描述：

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。

说明：

+

1
2
输入: haystack = "hello", needle = "ll"
输出: 2

+

1
2
输入: haystack = "aaaaa", needle = "bba"
输出: -1

  • 当 needle 是空字符串时我们应当返回 0，这与C语言的 strstr() 以及 Java，javascript的 indexOf() 定义相符。

1.双指针

  • 首先，只有子串的第一个字符跟 needle 字符串第一个字符相同的时候才需要比较。

  • 其次，可以一个字符一个字符比较，一旦不匹配了就立刻终止。

  • 注意在遇到不匹配位时，重置指针的位置

  • 返回字串的开始位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
    var strStr = function (haystack, needle) {
    if (needle == '') return 0;
    var i = 0,
        j = 0,
        haystackLength = haystack.length,
        needleLength = needle.length;
    while (i !== haystack.length) {
        // 剩余长度不足字串长度跳出
        if (haystackLength - i < needleLength) return -1;
        while (haystack[j + i] === needle[j]) {
            j++
            if (j === needleLength) {
                return i;
            }
        }
        //不满足时重置索引
        j = 0;
        i++;
    }
    return -1
};

复杂度分析

  • 时间复杂度：最坏时间复杂度 ，最好

  • 空间复杂度：

27. 移除元素

算法 / 关联题目
LeetCode

描述：

  • 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
  • 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
  • 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

注意:

  • 在 原地 删除重复出现的元素，表示必须在原数组上操作

  • 方法返回的是一个长度，表示过滤后的个数，但并不代表是过滤后的数组长度。

    1
    2
    3
    4
    5
    6
    7
    8
    //给定 nums = [0,1,2,2,3,0,4,2], val = 2,

    //函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

    //注意这五个元素可为任意顺序。

    //你不需要考虑数组中超出新长度后面的元素。

  • 为什么返回数值是整数，但输出的答案是数组呢?
    输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

    1
    2
    3
    4
    5
    6
    7
    8
    // nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
    int len = removeDuplicates(nums);

    // 在函数里修改输入数组对于调用者是可见的。
    // 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
    for (int i = 0; i < len; i++) {
        print(nums[i]);
    }

1.暴力解法 逐个删除

1
2
3
4
5
6
7
8
9
10
11
12
var removeElement = function (nums, val) {
    var i = 0,
        len = nums.length;
    for (; i < len; i++) {
        if (nums[i] === val) {
            nums.splice(i, 1)
            len--;
            i--;
        }
    }
    return len;
};

2. 双指针

  • 当 nums[j]与给定的值相等时，递增 j以跳过该元素。只要 nums[j]!==val,就复制 nums[j]到 nums[i]并同时递增两个索引。重复这一过程，直到 j到达数组的末尾，该数组的新长度为 i。

  • 此解法和(26)删除排序数组中的重复项相似

1
2
3
4
5
6
7
8
9
10
11
12
var removeElement = function (nums, val) {
    var i = 0,
        j = 0,
        len = nums.length;
    for (; j < len; j++) {
        if (nums[j] !== val) {
            nums[i] = nums[j];
            i++
        }
    }
    return i;
};

复杂度分析

  • 时间复杂度：，假设数组总共有 个元素， 和 最多遍历 次。

  • 空间复杂度：

3. 双指针 交换位置

  • 考虑数组包含很少的要删除的元素的情况。例如，，，，，,。之前的算法会对前四个元素做不必要的复制操作。似乎没有必要将 ，，，这几个元素左移一步，因为问题描述中提到元素的顺序可以更改。
1
2
3
4
5
6
7
8
9
10
11
12
13
var removeElement = function (nums, val) {
    var i = 0,
        j = nums.length;
    while (i < j) {
        if (nums[i] === val) {
            nums[i] = nums[j - 1];
            j--;
        } else {
            i++
        }
    }
    return i;
};

复杂度分析

  • 时间复杂度：

  • 空间复杂度：

  • Copyrights © 2015-2026 SunZhiqi

此时无声胜有声！

支付宝
微信