面试题-算法-LeetCode-书籍-剑指offer

LeetCode-剑指offer系列

面试题03、数组中重复的数字

点击看答案

HashSet 是否添加进去了

自己写的时候的问题：没啥，用hashset 搞定，但是忘了 new 关键字。。。

面试题04、二维数组中的查找

点击看答案

左下角标志法

自己写的时候的问题：自己写得完美，没问题。为了加深印象，我们说行数 rowNum = matrix.length; columnNum = matrix[0].length, 之后从左下角开始即可。

面试题05、替换String空格

点击看答案

使用 StringBuilder

自己写的时候的问题：没啥问题，StringBuilder 疯狂拼接即可

面试题10-I、斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出，求第n个数，但是结果要对 1000000007，如计算初始结果为：1000000008，请返回 1。

点击看答案

使用 StringBuilder

自己写的时候的问题：大体上使用数组是对的，但是在做计算的时候写成了： arrs[i] = arrs[i - 1]%mod + arrs[i-2] % mod;，而实际上应该写成： arrs[i] = (arrs[i - 1] + arrs[i-2]) % mod; 以后要注意

还可以延伸青蛙跳台阶问题

面试题11、旋转数组的最小数字

点击看答案

二分法

自己写的时候的问题：没啥难，就是要注意细节，1、没有旋转的情况 2、所有数字都相同的情况 3、只有一个数字的情况 4、剩下的就是从后面往前面找，当到某一个数字它的前面一个数字比当前数字大的时候，那最小数字就是当前数字了。

面试题15、二进制中1的个数

点击看答案

n & (n -1)

自己写的时候的问题：没啥，还是 n & (n-1)

面试题18、删除链表的节点

点击看答案

两个指针

自己写的时候的问题：没啥，处理好head，之后就是常用的pre 指针、current 指针了

面试题21、调整数组顺序使奇数位于偶数前面

点击看答案

首尾双指针

自己写的时候的问题：没啥，很顺利。双指针，快排思想

面试题22、链表中倒数第k个节点

点击看答案

前后指针

自己写的时候的问题：没啥，快慢指针，快指针先走k步

面试题24、反转链表。反转一个单链表，如输入： 1->2->3->4->5->Null ，则输出：5->4->3->2->1->Null

点击看答案

存储当前节点和上一个节点

自己写的时候的问题：没啥，搞个pre

面试题25、合并两个排序的链表

点击看答案

一个链表到表尾之后，需要接上另一个表的剩余部分

自己写的时候的问题：没啥，造一个空节点

包含min函数的栈

点击看答案

两个栈，一个维持压入数据，一个维持最小数栈，注意相同最小值要都压入最小数栈

面试题39、数组中出现次数超过一半的数字

点击看答案

既然出现次数超过一半那么排序后在中间的就是所需数字

自己写的时候的问题：先排序后取值不难，但是时间复杂度太高，提交的时候耗时1.3s；使用hashMap 计数，也不难，只是略微繁琐，还有 HashMap 额外占用空间。要熟练摩尔计数法，这才是最优解。

面试题40、最小的k个数

点击看答案

大顶堆

自己写的时候的问题：暂时还没做

还可以引申数据流中中位数

连续子数组的最大和

点击看答案

要么取大值，要么另起炉灶

自己写的时候的问题：与之前写的力扣53题的答案，这次更加简洁粗暴，直接判断result < 0 是否成立，成立就放弃result，否则就还让它继续 result += element;重点记住这个答案就好

面试题50、第一个只出现一次的字符

点击看答案

hashmap 存储次数

自己写的时候的问题：HashMap 辅助，没啥难度。在字符出现次数 > 1 的时候，不要尝试去增加它的次数，节省put 操作。因为 2次和 100次对我们意义是一样的

面试题52、两个链表的第一个公共节点

点击看答案

两个指针 node1，node2 分别指向两个链表 headA，headB 的头结点，然后同时分别逐结点遍历，当 node1 到达链表 headA 的末尾时，重新定位到链表 headB 的头结点；当 node2 到达链表 headB 的末尾时，重新定位到链表 headA 的头结点。这样，当它们相遇时，所指向的结点就是第一个公共结点

自己写的时候的问题：刚开始脑抽只允许一个转换，其实应该 A 和B两个链表应该各有一次转换机会。

面试题53 - I、在排序数组中查找数字 I，统计一个数字在排序数组中出现的次数

点击看答案

二分法

自己写的时候的问题：自己写没问题，二分查找没毛病。

面试题53 - II. 0～n-1中缺失的数字。一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字

点击看答案

解法1：与下标是否相等解法2：求和？(要考虑溢出) 解法3：二分法

自己写的时候的问题：在数组下标都对应得上的时候，缺失的就是最后一个数字，写的时候没想到这点。

面试题56 - I、数组中数字出现的次数。一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)

点击看答案

异或-> 数字分组

自己写的时候的问题：不太熟练，自己只能想到全员异或，然后分组，之后想不到了。其实在分组过后，每组元素都是由若干个出现两次的数字和一个只出现一次的数字组成，组内异或就能得到那个只出现一次的数字。

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素

点击看答案

全员异或

面试题57、和为s的两个数字。输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可

点击看答案

双指针即可

自己写的时候的问题：没啥说的，提交完美。双指针即可

面试题58 - I、翻转单词顺序。输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串”I am a student. “，则输出”student. a am I”

点击看答案

两次翻转

自己写的时候的问题：这题目本身就有点坑爹，注意审题，因为它首尾的空格要求在结果中去掉，并且单词间有多个空格也只保留一个。还有，清空StringBuilder 可以使用 sb.setLength(0) 的方式。其他的倒是没啥。

面试题58 - II、左旋转字符串。字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串”abcdefg”和数字2，该函数将返回左旋转两位得到的结果”cdefgab”

点击看答案

subString即可

自己写的时候的问题：没啥，StringBuilder 拼接，简单粗暴

面试题59 - I、滑动窗口的最大值。给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值

点击看答案

上一次的最大值是不是被滑过的位置

自己写的时候的问题：自己写，不难。充分利用好上一次的最大值即可

面试题61、扑克牌中的顺子。从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14

点击看答案

根据差值计算大小王是否够用就行

自己写的时候的问题：看懂原理，就不难(抄别人的)：如果我们能够知道 5 张扑克牌中的最大值 maxValue 和最小值 minValue ，那我们就知道，要使它为顺子需要 maxValue - minValue + 1 张牌，所以我们只需要计算最大最小值(0除外)，然后通过上述规律来判断。当然，如果其中有重复的数字(0除外),那么肯定凑不齐了。所以我们关键是找最大最小值，以及判断是否重复。这里面的细节很多，比如boolean[] 用来表示元素是否重复的数组，它的index 不是遍历牌的 i ，而是牌面值，即 nums[i]

面试题62、圆圈中最后剩下的数字。0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字

点击看答案

约瑟夫环，记得公式就行（返回的是数组下标）

int cir(int n,int m){
	int p=0;
	for(int i=2;i<=n;i++)
	{
		p=(p+m)%i;
	}
	return p;
}

面试题65、不用加减乘除做加法。写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号

点击看答案

异或操作

自己写的时候的问题：凭记忆做出来了，后续还是要加强。注意一点再java中不要做 <<< 操作，非法的。

面试题66、给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B 中的元素 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。

点击看答案

对称数组

自己写的时候的问题：似懂非懂

66、加一，给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一，最高位存放在数组收尾，数组中每个元素只存储单个数字，可以假设除了0之外，这个整数不会以0开头。假如输入：[1,2,3] ，代表123，则输出 [1,2,4]；输入 [4,3,2,1] ，代表 4321，则输出 [4,3,2,2]

点击看答案

它只是加一的话，可能的情况只有两种：

除9之外的数字加一
数字9加一
加一得十，进一位，个位数为0；如加法运算不出现进位，则运算就结束了。还有一种情况就是当出现 9，99，999 之类的数字时，循环到最后也需要进位，需要手动将它进一位

自己写的时候的问题：没啥问题，遍历每个元素让每个元素 +1 ，当某个元素 +1 之后 < 10,就将当前数组返回；否则，加到最后也还没返回，就要新建一个数组，最开始位为1

LeetCode-剑指offer系列

面试题03、数组中重复的数字

面试题04、二维数组中的查找

面试题05、替换String空格

面试题10-I、斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出，求第n个数，但是结果要对 1000000007，如计算初始结果为：1000000008，请返回 1。

面试题11、旋转数组的最小数字

面试题15、二进制中1的个数

面试题18、删除链表的节点

面试题21、 调整数组顺序使奇数位于偶数前面

面试题22、 链表中倒数第k个节点

面试题24、 反转链表。反转一个单链表，如输入： 1->2->3->4->5->Null ，则输出：5->4->3->2->1->Null

面试题25、 合并两个排序的链表

包含min函数的栈

面试题39、 数组中出现次数超过一半的数字

面试题40、最小的k个数

连续子数组的最大和

面试题50、第一个只出现一次的字符

面试题52、两个链表的第一个公共节点

面试题53 - I、在排序数组中查找数字 I，统计一个数字在排序数组中出现的次数

面试题53 - II. 0～n-1中缺失的数字。一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字

面试题56 - I、数组中数字出现的次数。一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素

面试题57、和为s的两个数字。输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可

面试题58 - I、翻转单词顺序。输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串”I am a student. “，则输出”student. a am I”

面试题59 - I、 滑动窗口的最大值。给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值

面试题61、 扑克牌中的顺子。从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14

面试题62、圆圈中最后剩下的数字。0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字

面试题65、不用加减乘除做加法。写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号

面试题66、给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B 中的元素 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。

面试题21、调整数组顺序使奇数位于偶数前面

面试题22、链表中倒数第k个节点

面试题24、反转链表。反转一个单链表，如输入： 1->2->3->4->5->Null ，则输出：5->4->3->2->1->Null

面试题25、合并两个排序的链表

面试题39、数组中出现次数超过一半的数字

面试题59 - I、滑动窗口的最大值。给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值

面试题61、扑克牌中的顺子。从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14