剑指Offer简单题

03. 数组中重复的数字

找出数组中重复的数字。

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

示例 1:

输入:[2, 3, 1, 0, 2, 5, 3]

输出:2 或 3

解题思路:注意题目描述:一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的 范围 内,这个 范围 恰好与数组的下标可以一一对应。

所以我们可以执行某种操作,使索引与值一一对应,即索引 0 的值为 0,索引 1 的值为 1。而一旦某个索引的值不只一个,则找到了重复的数字,也即发生了哈希冲突

05. 替换空格

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

示例 1:

输入:s = "We are happy."

输出:"We%20are%20happy."

06. 从尾到头打印链表

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

示例 1:

输入:head = [1,3,2]

输出:[2,3,1]

这道题目的输入是一个链表,输出是一个数组。

链表具有的特点:

事先链表的长度是不知道的,也就是说事先你是不知道链表中存在多少节点的

链表只能从头节点开始往后遍历,而不能从非头节点往前遍历

数组具有的特点:

数组初始化的时候就必须指定长度

我们不仅可以从数组的第一个元素往后遍历访问数组,而且也可以从最后一个元素往前遍历数组

所以,我们要返回一个数组,首先需要计算出这个数组的长度,实际上数组的长度就等于链表的节点的个数,那么问题就变成了求链表的节点个数了,我们可以这样求解:

先初始化一个整形变量 length

从链表的头节点往后遍历,每遇到一个节点,那么 length 就自加 1,一直到链表的空节点为止

得到了数组的长度后,我们就可以初始化一个结果数组,然后再次从链表的头节点开始往后遍历,每遇到一个节点,那么就将节点的值放到数组的后端 (这里利用了数组可以从最后一个元素往前访问的特点)

这道题需要解决的问题本质上就是将链表倒序了,而由于链表只能从头节点往后遍历,所以我们可以借助栈来完成链表的倒序排列过程。

栈的特点是:后进先出,即最后压入的元素最先弹出。

09. 用两个栈实现队列

用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 )

示例 1:

输入:

["CQueue","appendTail","deleteHead","deleteHead"]

[[],[3],[],[]]

输出:[null,null,3,-1]

示例 2:

输入:

["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]

[[],[],[5],[2],[],[]]

输出:[null,-1,null,null,5,2]

栈是一种先进后出的数据结构,队列却是一种先进先出的数据结构。

题目要求我们使用两个栈来实现一个队列,首先一点我们可以确定的是一开始往队列中 append 的数据肯定是存储在一个栈中的。

也就是说先 append 的数据都是存储在栈的栈底,换句话说,队头的元素一开始肯定是存储在一个栈中的栈底

如果我们现在想删除队头的元素的话,也就是说我们要删除的是一个栈底的元素,肯定是直接删除不到的

因为我们有两个栈,所以我们可以将 append 进来的数据从栈中 pop 出来,然后 push 到另一个栈中,这样之前栈底的元素就变为另一个栈顶的元素了,然后 pop 掉栈顶元素就可以了。

  1. ### 斐波那契数列-Ⅰ

写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项(即 F(N))。斐波那契数列的定义如下:

F(0) = 0, F(1) = 1

F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

示例 1:

输入:n = 2

输出:1

img

首先,我们用回溯的思想来考虑这个问题

接下来我们使用记忆化搜索,消除重复解

img

可以用数组的方式存重复解,也可以用map,但是map消耗的存储空间比较大。

最后的话,采用自底而上的思路,也就是动态规划的思路

难点:状态数组和状态转移方程的定义

本题解答:计算中取模和结果取模答案一样,但是计算中取模不会超过内存限制

  1. ### 斐波那契数列-Ⅱ

一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

示例 1:

输入:n = 7

输出:21

当n等于1的时候,只需要跳一次即可,只有一种跳法,记f(1)=1

当n等于2的时候,可以先跳一级再跳一级,或者直接跳二级,共有2种跳法,记f(2)=2

当n等于3的时候,他可以从一级台阶上跳两步上来,也可以从二级台阶上跳一步上来,所以总共有f(3)=f(2)+f(1);

同理当等于n的时候,总共有f(n)=f(n-1)+f(n-2)(这里n>2)种跳法。

  1. ### 旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转,该数组的最小值为1。

示例 1:

输入:[3,4,5,1,2]

输出:1

暴力法:初始化两个指针,向后移动,直到右指针比左指针小

二分查找:

  1. ### 二进制中1的个数

请实现一个函数,输入一个整数(以二进制串形式),输出该数二进制表示中 1 的个数。例如,把 9 表示成二进制是 1001,有 2 位是 1。因此,如果输入 9,则该函数输出 2。

示例 1:

输入:00000000000000000000000000001011

输出:3

解释:输入的二进制串 00000000000000000000000000001011 中,共有三位为 '1'。

  1. ### 删除链表的节点

给定单向链表的头指针和一个要删除的节点的值,定义一个函数删除该节点。

返回删除后的链表的头节点。

注意:此题对比原题有改动

示例 1:

输入: head = [4,5,1,9], val = 5

输出: [4,1,9]

解释: 给定你链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 4 -> 1 -> 9.

删除值为 val 的节点可分为两步:定位节点、修改引用。

定位节点: 遍历链表,直到 head.val val 时跳出,即可定位目标节点。

修改引用: 设节点 cur 的前驱节点为 pre ,后继节点为 cur.next ;则执行 pre.next = cur.next ,即可实现删除 cur 节点。

img

  1. ### 调整数组顺序使奇数位于偶数前面

输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。

示例:

输入:nums = [1,2,3,4]

输出:[1,3,2,4]

注:[3,1,2,4] 也是正确的答案之一。

考虑定义双指针 ii , jj 分列数组左右两端,循环执行:

指针 ii 从左向右寻找偶数;

指针 jj 从右向左寻找奇数;

将 偶数 nums[i]nums[i] 和 奇数 nums[j]nums[j] 交换。

可始终保证: 指针 ii 左边都是奇数,指针 jj 右边都是偶数

img

  1. ### 链表中倒数第k个节点

输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点。

例如,一个链表有 6 个节点,从头节点开始,它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例:

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

img

第一时间想到的解法:

先遍历统计链表长度,记为 nn ;

设置一个指针走 (n-k)步,即可找到链表倒数第 kk 个节点。

使用双指针则可以不用统计链表长度。

  1. ### 反转链表

定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。

示例:

输入: 1->2->3->4->5->NULL

输出: 5->4->3->2->1->NULL

如果再定义一个新的链表,实现链表元素的反转,其实这是对内存空间的浪费。

其实只需要改变链表的next指针的指向,直接将链表反转 ,而不用重新定义一个新的链表,如图所示:

img

  1. ### 合并两个排序的链表

输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1:

输入:1->2->4, 1->3->4

输出:1->1->2->3->4->4

img

  1. ### 二叉树的镜像

请完成一个函数,输入一个二叉树,该函数输出它的镜像。

例如输入:

​ 4

/ \

2 7

/ \ / \

1 3 6 9

镜像输出:

​ 4

/ \

7 2

/ \ / \

9 6 3 1

示例 1:

输入:root = [4,2,7,1,3,6,9]

输出:[4,7,2,9,6,3,1]

img

img

  1. ### 对称的二叉树

请实现一个函数,用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样,那么它是对称的。

例如,二叉树 [1,2,2,3,4,4,3] 是对称的。

​ 1

/ \

2 2

/ \ / \

3 4 4 3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

​ 1

/ \

2 2

\ \

3 3

示例 1:

输入:root = [1,2,2,3,4,4,3]

输出:true

示例 2:

输入:root = [1,2,2,null,3,null,3]

输出:false

img

img

  1. ### 顺时针打印矩阵

输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。

示例 1:

输入:matrix = [[1,2,3],[4,5,6],[7,8,9]]

输出:[1,2,3,6,9,8,7,4,5]

示例 2:

输入:matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]

输出:[1,2,3,4,8,12,11,10,9,5,6,7]

根据题目示例 matrix = [[1,2,3],[4,5,6],[7,8,9]] 的对应输出 [1,2,3,6,9,8,7,4,5] 可以发现,顺时针打印矩阵的顺序是 “从左向右、从上向下、从右向左、从下向上” 循环。

因此,考虑设定矩阵的“左、上、右、下”四个边界,模拟以上矩阵遍历顺序。

img

img

  1. ### 包含min函数的栈

定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例:

img

  1. ### 数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。

你可以假设数组是非空的,并且给定的数组总是存在多数元素。

示例 1:

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]

输出: 2

利用HashMap

  1. ### 最小的k个数

输入整数数组 arr ,找出其中最小的 k 个数。例如,输入4、5、1、6、2、7、3、8这8个数字,则最小的4个数字是1、2、3、4。

示例 1:

输入:arr = [3,2,1], k = 2

输出:[1,2] 或者 [2,1]

本题使用排序算法解决最直观,对数组 arr 执行排序,再返回前 k 个元素即可。使用任意排序算法皆可,本文采用并介绍 快速排序。

  1. ### 第一个只出现一次的字符

在字符串 s 中找出第一个只出现一次的字符。如果没有,返回一个单空格。 s 只包含小写字母

示例:

s = "abaccdeff"

返回 "b"

s = ""

返回 " "

用hashmap存储每个字符出现的次数,注意HashMap遍历的时候不是按照插入的顺序遍历的,需要采用LinkedHashMap才可以。

输入两个链表,找出它们的第一个公共节点。

如下面的两个链表

img

在节点 c1 开始相交。

输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3

输出:Reference of the node with value = 8

输入解释:相交节点的值为 8 (注意,如果两个列表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,0,1,8,4,5]。在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。

输入:intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2

输出:null

输入解释:从各自的表头开始算起,链表 A 为 [2,6,4],链表 B 为 [1,5]。由于这两个链表不相交,所以 intersectVal 必须为 0,而 skipA 和 skipB 可以是任意值。

解释:这两个链表不相交,因此返回 null。

先把第一个链表的节点全部存放到集合set中,然后遍历第二个链表的每一个节点,判断在集合set中是否存在,如果存在就直接返回这个存在的结点。如果遍历完了,在集合set中还没找到,说明他们没有相交,直接返回null即可。

  1. ### 第一个只出现一次的字符

统计一个数字在排序数组中出现的次数。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8

输出: 2

排序数组中的问题,优化大概率是二分法,二分法就三个框架,一个是搜索确定元素的下标,一个是搜索左边界,一个是右边界。

那么这个题用二分法,我们找到它的左右边界left和right,然后元素个数就是right-left+1