当前位置 博文首页 > xiaochengzi0419的博客：剑指offer系列刷题笔记
剑指offer应该属于比较基础且高频的算法知识点，应该融合贯通，学习里面优秀的算法思维
当然在解题时，我们尽量使用时间复杂度和空间复杂度比较好的算法
一共75道题:主要分为解题思路和题解
在一个 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。
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return false;
}
int rows = matrix.length, columns = matrix[0].length;
int row = 0, column = columns - 1;
while (row < rows && column >= 0) {
int num = matrix[row][column];
if (num == target) {
return true;
} else if (num > target) {
column--;
} else {
row++;
}
}
return false;
}
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
示例 1：
输入：s = "We are happy."
输出："We%20are%20happy."
解题思路:
标签：字符串
最简单的方案自然是直接使用库函数啦！当然题目肯定是不希望我们这样做的！
增加一个新字符串，遍历原来的字符串，遍历过程中，如果非空格则将原来的字符直接拼接到新字符串中，如果遇到空格则将%20拼接到新字符串中
时间复杂度：O(n)O(n)，空间复杂度：O(n)O(n)
class Solution {
public String replaceSpace(String s) {
StringBuilder sb = new StringBuilder();
for(int i = 0 ; i < s.length(); i++){
char ch = s.charAt(i);
if(ch == ' ') {
sb.append("%20");
}
else {
sb.append(ch);
}
}
return sb.toString(); // 这个转化非常重要
}
}
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。
示例 1：
输入：[3,4,5,1,2]
输出：1
示例 2：
输入：[2,2,2,0,1]
输出：0
解题方案:
思路:
标签：二分查找
整体思路：首先数组是一个有序数组的旋转，从这个条件可以看出，数组是有大小规律的，可以使用二分查找利用存在的规律快速找出结果
时间复杂度：O(logn)O(logn)，空间复杂度：O(1)O(1)
算法流程
初始化下标 left 和 right
每次计算中间下标 mid = (right + left) / 2?，这里的除法是取整运算，不能出现小数
当 numbers[mid] < numbers[right]? 时，说明最小值在 ?[left, mid]? 区间中，则令 right = mid，用于下一轮计算
当 numbers[mid] > numbers[right]? 时，说明最小值在 [mid, right]? 区间中，则令 left = mid + 1，用于下一轮计算
当 numbers[mid] == numbers[right]? 时，无法判断最小值在哪个区间之中，此时让 right–，缩小区间范围，在下一轮进行判断
为什么是 right-- 缩小范围，而不是 left++？
因为数组是升序的，所以最小值一定靠近左侧，而不是右侧
比如，当存在 [1,2,2,2,2] 这种情况时，left = 0，right = 4，mid = 2，数值满足 numbers[mid] == numbers[right] 这个条件，如果 left++，则找不到最小值
代码
class Solution {
public int minArray(int[] numbers) {
int left = 0;
int right = numbers.length - 1;
while (left < right) {
int mid = (right + left) / 2;
if (numbers[mid] < numbers[right]) {
right = mid;
} else if (numbers[mid] > numbers[right]) {
left = mid + 1;
} else {
right --;
}
}
return numbers[left];
}
}
输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。
示例 1:
输入: n = 1
输出: [1,2,3,4,5,6,7,8,9]
解题方案:
整体思路：首先求出要打印的数字范围，然后再从 1 开始打印到最大的数字
算法流程 1
class Solution {
public int[] printNumbers(int n) {
int sum = 1;
for (int i = 0; i < n; i++) {
sum *= 10;
}
int[] res = new int[sum - 1];
for(int i = 0; i < sum - 1; i++){
res[i] = i + 1;
}
return res;
}
}
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
示例：
输入：nums = [1,2,3,4]
输出：[1,3,2,4]
注：[3,1,2,4] 也是正确的答案之一。
解题方案
思路
标签：双指针
算法流程
class Solution {
public int[] exchange(int[] nums) {
int start = 0;
int end = nums.length - 1;
while(start < end) {
while(start < end && (nums[start] % 2) == 1) {
start++;
}
while(start < end && (nums[end] % 2) == 0) {
end--;
}
int tmp = nums[start];
nums[start] = nums[end];
nums[end] = tmp;
}
return nums;
}
}
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
示例 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]
解决方案：
思路：
标签:二维数组
整体思路:循环遍历整个数组，循环中再嵌套四个循环，分别是从左至右，从上至下，从右至左，从下至上
这几个方向，按照题意将整个数组遍历完成，控制好边界
算法流程
class Solution {
public int[] spiralOrder(int[][] matrix) {
if(matrix.length == 0) return new int[0];
int left = 0, right = matrix[0].length - 1, top = 0, bottom = matrix.length - 1, x = 0;
int[] res = new int[(right + 1) * (bottom + 1)];
while(true) {
for(int i = left; i <= right; i++) res[x++] = matrix[top][i];
if(++top > bottom) break;
for(int i = top; i <= bottom; i++) res[x++] = matrix[i][right];
if(left > --right) break;
for(int i = right; i >= left; i--) res[x++] = matrix[bottom][i];
if(top > --bottom) break;
for(int i = bottom; i >= top; i--) res[x++] = matrix[i][left];
if(++left > right) break;
}
return res;
}
}
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2
摩尔投票法
class Solution {
public int majorityElement(int[] nums) {
int cur = 0;
int count = 0;
for(int num : nums){
if(count == 0) {
cur = num;
}
if(num == cur) {
count++;
} else {
count--;
}
}
return cur;
}
}
输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
示例 1:
输入: [10,2]
输出: "102"
示例 2:
输入: [3,30,34,5,9]
输出: "3033459"
本质上是个排序算法
解题方案:
思路:
拼接数组内所有元素使所有元素使结果最小，本质上是排序
若字符串拼接a + b > b + a,那么排序上b < a；
根据这个规则对数组内的元素排序
算法流程:
class Solution {
public String minNumber(int[] nums) {
List<String> strList = new ArrayList<>();
for (int num : nums) {
strList.add(String.valueOf(num));
}
strList.sort((a, b) -> (a + b).compareTo(b + a)); // 这个排序
StringBuilder sb = new StringBuilder();
for (String str : strList) {
sb.append(str);
}
return sb.toString();
}
}
统计一个数字在排序数组中出现的次数。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: 0
该题本身的解法应该非常多
但是二分法的变种模板很给力
解决方案
整体思路:
算法流程
边界的模板
class Solution {
public int search(int[] nums, int target) {
return getRightMargin(nums, target) - getRightMargin(nums, target - 1);
}
int getRightMargin(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left <= right) {
int mid = (left + right) / 2;
if(nums[mid] <= target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
}
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
示例 1:
输入: [0,1,3]
输出: 2
示例 2:
输入: [0,1,2,3,4,5,6,7,9]
输出: 8
这道题的方法很多，位运算应该是比较简单的
位运算
class Solution {
public int missingNumber(int[] nums) {
int len = nums.length;
int xor = 0;
for(int i = 0;i < len ; i++){
xor ^= nums[i] ^ (i+1);
}
return xor;
}
}
输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,2]
示例 2：
输入：nums = [10,26,30,31,47,60], target = 40
输出：[10,30] 或者 [30,10]
解题方案
思路
标签： 双指针
整体思路：因为数组本身是有序的，那么完全可以在数组的开头 start 和结尾 end 位置各设置一个指针，
通过二者的加和 sum 来找到目标值 target，如果 sum < target，则 start++，
这样可以让下一次的 sum 变大，如果 sum > target，则 end--，这样可以让下一次的 sum 变小，找到结果
时间复杂度：O(n)O(n)O(n)，空间复杂度：O(1)O(1)O(1)
算法流程
首先初始化 start = 0，end = nums.length - 1，作为双指针
当 start < end 时，始终进行循环遍历
计算 sum = nums[start] + nums[end]，并将 sum 与 target 进行比较
如果 sum < target，则需要将下一次的 sum 值变大，因为数组有序，故而 start++
如果 sum > target，则需要将下一次的 sum 值变小，因为数组有序，故而 end--
如果 sum == target，则找到了最终的结果，将结果返回即可
class Solution {
public int[] twoSum(int[] nums, int target) {
int start = 0;
int end = nums.length - 1;
while(start < end) {
int sum = nums[start] + nums[end];
if(sum < target) {
start++;
} else if(sum > target) {
end--;
} else {
return new int[] { nums[start], nums[end] };
}
}
return new int[0];
}
}
输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
示例 1：
输入：target = 9
输出：[[2,3,4],[4,5]]
示例 2：
输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]
class Solution {
public int[][] findContinuousSequence(int target) {
int left = 1;
int right = 2;
List<int[]> res = new ArrayList<>();
while (left < right) {
int sum = (left + right) * (right - left + 1) / 2;
if (sum == target){
int[] arr = new int[right - left + 1];
for (int k = left; k <= right; k++) {
arr[k - left] = k;
}
res.add(arr);
left++;
}
else if (sum < target) {
right++;
}
else {
left++;
}
}
return res.toArray(new int[res.size()][]);
}
}
输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. “，则输出"student. a am I”。
示例 1：
输入: "the sky is blue"
输出: "blue is sky the"
示例 2：
输入: " hello world! "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3：
输入: "a good example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
双指针
算法流程:
class Solution {
public String reverseWords(String s) {
String tmp = s.trim();
int start = tmp.length() - 1;
int end = tmp.length() - 1;
String res = "";
while(start >= 0) {
while(start >= 0 && tmp.charAt(start) != ' ') {
start--;
}
res += tmp.substring(start + 1, end + 1) + " ";
while(start >= 0 && tmp.charAt(start) == ' ') {
start--;
}
end = start;
}
return res.trim();
}
}
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。
示例 1：
输入: s = "abcdefg", k = 2
输出: "cdefgab"
示例 2：
输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"
算法流程:
class Solution {
public String reverseLeftWords(String s, int n) {
String res = "";
int len = s.length();
for(int i = n; i < len; i++) {
res += s.charAt(i);
}
for(int i = 0; i < n; i++) {
res += s.charAt(i);
}
return res;
}
}
从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。
示例 1:
输入: [1,2,3,4,5]
输出: True
示例 2:
输入: [0,0,1,2,5]
输出: True
方法一:
// 思路非常简洁
class Solution {
public boolean isStraight(int[] nums) {
Set<Integer> repeat = new HashSet<>();
int max = 0, min = 14;
for(int num : nums) {
if(num == 0) continue; // 跳过大小王
max = Math.max(max, num); // 最大牌
min = Math.min(min, num); // 最小牌
if(repeat.contains(num)) return false; // 若有重复，提前返回 false
repeat.add(num); // 添加此牌至 Set
}
return max - min < 5; // 最大牌 - 最小牌 < 5 则可构成顺子
}
}
方法二:
主要的思想是：排序 + 遍历
class Solution {
public boolean isStraight(int[] nums) {
int joker = 0;
Arrays.sort(nums); // 数组排序
for(int i = 0; i < 4; i++) {
if(nums[i] == 0) joker++; // 统计大小王数量
else if(nums[i] == nums[i + 1]) return false; // 若有重复，提前返回 false
}
return nums[4] - nums[joker] < 5; // 最大牌 - 最小牌 < 5 则可构成顺子
}
}
给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
解题方案
思路
标签：数组遍历
整体思路：
这道题如果可以使用除法，那么就很简单了，先求出来所有数的乘积，然后再依次除掉每个对应的值即可
不让使用除法，那么最简单的思路就是将B[i]每个位置都把所有需要的数乘一遍，但是这样的时间复杂度非常高
降低时间复杂度的方式就是以A[i]为界线，分割出左右三角形，其中每个三角形从尖部到底部都是可以累积的，这样就可以减少时间复杂度（具体见画）
复杂度：
时间复杂度：O(n)O(n)O(n)。因为左右三角遍历求乘积的时间复杂度都是O(n)O(n)O(n)
空间复杂度：O(1)O(1)O(1)。不将结果数组算入的话，只需要常量的空间复杂度
算法流程
首先申请结果数组 res
求出左侧三角从上到下的值，依次存入 res[i] 中
求出右侧三角从下到上的值，并且和之前的 res[i] 做乘积存入，即可得到结果
示例:
输入: [1,2,3,4,5]
输出: [120,60,40,30,24]
class Solution {
public int[] constructArr(int[] a) {
int[] res = new int[a.length];
int left = 1;
for (int i = 0; i < a.length; i++) {
res[i] = left;
left *= a[i];
}
int right = 1;
for (int i = a.length - 1; i >= 0; i--) {
res[i] *= right;
right *= a[i];
}
return res;
}
}
写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。
当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0。
说明：
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [?231, 231 ? 1]。如果数值超过这个范围，请返回 INT_MAX (231 ? 1) 或 INT_MIN (?231) 。
示例 1:
输入: "42"
输出: 42
示例 2:
输入: " -42"
输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。
我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
示例 3:
输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。
示例 4:
输入: "words and 987"
输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
因此无法执行有效的转换。
示例 5:
输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。
因此返回 INT_MIN (?231) 。
class Solution {
public int strToInt(String str) {
char[] c = str.trim().toCharArray();
if(c.length == 0) return 0;
int res = 0, boundry = Integer.MAX_VALUE / 10;
int start = 1, sign = 1;
if(c[0] == '-') sign = -1;
else if(c[0] != '+') start = 0;
for(int i = start; i < c.length; i++) {
if(c[i] < '0' || c[i] > '9') break;
if(res > boundry || res == boundry && c[i] > '7') return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
res = res * 10 + (c[i] - '0');
}
return sign * res;
}
}
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
示例 1：
输入：head = [1,3,2]
输出：[2,3,1]
解题思路:
使用栈特有属性
关键点在于会使用栈的几个常用的方法进行操作
class Solution {
public int[] reversePrint(ListNode head) {
Stack<ListNode> stack = new Stack<>();
while(head != null){
stack.push(head);
head = head.next;
}
int len = stack.size();
int[] res = new int[len];
for(int i = 0 ;i < len ; i++){
res[i] = stack.pop().val;
}
return res;
}
}
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 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]
解题思路:
Deque -> 这是一个接口
线性结合，支持两端的元素插入和移除。Deque是double ended queue的简称，习惯上称之为双端队列
interface Deque<E>
子接口:
BlockingDeque<E>
实现类
class CQueue {
Deque<Integer> stack1 ;
Deque<Integer> stack2 ;
public CQueue() {
stack1 = new LinkedList<Integer>();
stack2 = new LinkedList<Integer>();
}
public void appendTail(int value) {
stack1.push(value);
}
public int deleteHead() {
if(stack2.isEmpty()){
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
if (stack2.isEmpty()) {
return -1;
} else {
int dele = stack2.pop();
return dele;
}
}
}
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
示例:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.min(); --> 返回 -2.
该题比较简单，使用辅助栈即可
算法流程
