剑指 Offer 03. 数组中重复的数字

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof

思路

1.哈希表
2.原地交换数字（将数组元素与其索引号对应，遍历后有不对应说明有重复）

剑指offer 04 二维数组中的查找

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

示例:

现有矩阵 matrix 如下：

[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
] 给定 target = 5，返回 true。

给定 target = 20，返回 false。

https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof

思路

两种思路，一种暴力，两层循环找，但是要注意判断数组是否存在：

1
2
3

if (matrix.length == 0 || matrix[0].length == 0) {
      return false;
}

还有种思路是利用题目中给的特性，每行从左到右都是递增，可以把矩阵往左旋转45度，可以看成一棵二叉树，往左是小的，往右是大的。

剑指 Offer 05. 替换空格

请实现一个函数，把字符串 s 中的每个空格替换成”%20”。

示例 1：

输入：s = “We are happy.”
输出：”We%20are%20happy.”

https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof

思路

1.直接用js的api

return s.replaceall(“ “, “%20”);

1. 遍历，遇到空格就替换

1
2
3
4
5
6
7
8
9
10
11
12

var replaceSpace = function(s) {
    let backup = s;
    let re = '';
    for(let i = 0; i< backup.length; i++) {
        if(s[i] == ' ') {
            re = re + "%20";
            continue;
        }
        re = re + backup[i];
    }
    return re;
};

剑指 Offer 06. 从尾到头打印链表

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：

输入：head = [1,3,2]
输出：[2,3,1]

https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/

思路

这道题需要用到unshift这个api，用于将元素插入到数组头部（push是插入到尾部）。

思路就是开辟一个数组，按照栈的方式往数组中插入元素，然后返回这个数组即可。