算法 | 一周刷完《剑指Offer》 Day1：第1~16题
开个新坑，准备校招研发岗面试，基本的算法还是要过关的。
写在前面
- 本系列包含《剑指Offer》66道算法题，预计一周刷完。
系列汇总：剑指Offer 66题 Java 刷题笔记汇总 - 所有题目均可在牛客网在线编程平台进行调试。
网址：https://www.nowcoder.com/ta/coding-interviews - 本系列包含题目，解题思路及代码（Java）。
代码同步发布在GitHub：https://github.com/JohnnyJYWu/offer-Java
下一篇：算法 | 一周刷完《剑指Offer》 Day2：第17~26题
Day1：第1~16题
后面总会遇到难的绕的题，前两天多做几道，总不会亏的。
- T1. 二维数组中的查找
- T2. 替换空格
- T3. 从尾到头打印链表
- T4. 重建二叉树
- T5. 用两个栈实现队列
- T6. 旋转数组的最小数字
- T7. 斐波那契数列
- T8. 跳台阶
- T9. 变态跳台阶
- T10. 矩阵覆盖
- T11. 二进制中 1 的个数
- T12. 数值的整数次方
- T13. 调整数组顺序使奇数位于偶数前面
- T14. 链表中倒数第 K 个结点
- T15. 反转链表
- T16. 合并两个排序的链表
T1. 二维数组中的查找
题目描述
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
解题思路
因为矩阵中的每一个数，左边都比它小，下边都比它大。因此，从右上角开始查找，就可以根据 target 和当前元素的大小关系来缩小查找区间。
public boolean Find(int target, int[][] array) {
if(array == null || array.length == 0 || array[0].length == 0) {
return false;
}
int m = 0, n = array[0].length - 1;//从右上角开始找，array[0][n-1]
while(m <= array.length - 1 && n >= 0) {
if(target == array[m][n])
return true;
else if(target > array[m][n])
m ++;
else
n --;
}
return false;
}
T2. 替换空格
题目描述
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy，则经过替换之后的字符串为We%20Are%20Happy。
解题思路
由于每个空格替换成了三个字符，首先要扩容字符串长度至替换后的长度，因此当遍历到一个空格时，需要在尾部填充两个任意字符。
然后声明两个下标，一个为原字符串末尾下标 i，一个为现字符串末尾 j，两个下标同步从后往前扫。当 i 指向空格时，j 就倒着依次添加 '0', '2', '%'。
这样做的目的是： j 下标不会超过 i 下标，不会影响原字符串的内容。
public String replaceSpace(StringBuffer str) {
int oldLen = str.length();
for(int i = 0; i < oldLen; i ++) {
if(str.charAt(i) == ' ') {//每出现一个空格，在结尾添加两个任意字符，扩充字符串长度
str.append("12");
}
}
int i = oldLen - 1;
int j = str.length() - 1;
while(i >= 0 && j > i) {
char c = str.charAt(i);
i --;
if(c == ' ') {//每出现一个空格，替换为%20
str.setCharAt(j, '0');
j --;
str.setCharAt(j, '2');
j --;
str.setCharAt(j, '%');
j --;
} else {//否则照旧
str.setCharAt(j, c);
j --;
}
}
return str.toString();
}
T3. 从尾到头打印链表
题目描述
输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
解题思路
使用栈实现：先入后出。全部入栈，依次出栈，顺序即为从尾到头。
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
//使用栈实现，先入后出
Stack<Integer> stack = new Stack<>();
ArrayList<Integer> arrayList = new ArrayList<>();
while(listNode != null) {
stack.push(listNode.val);
listNode = listNode.next;
}
while(!stack.isEmpty()) {
arrayList.add(stack.pop());
}
return arrayList;
}
使用递归实现：先加入链表后面的结点，再加入当前结点，顺序即为从尾到头。
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
//使用递归实现，先加入链表后面的结点，再加入当前结点
ArrayList<Integer> arrayList = new ArrayList<>();
if(listNode != null) {
arrayList.addAll(printListFromTailToHead(listNode.next));//先递归
arrayList.add(listNode.val);//再加入当前
}
return arrayList;
}
T4. 重建二叉树
题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
解题思路
首先清楚以下性质：
前序遍历：根 -> 左 -> 右，中序遍历：左 -> 根 -> 右。
因此一颗二叉树中，前序遍历的第一个结点为根结点，通过它在中序遍历中的位置，可以将中序遍历分为两部分，左半部分是该结点的左子树，右半部分是该结点的右子树。
根据这个原理，递归执行即可重构出二叉树。
private Map<Integer, Integer> map = new HashMap<>();//用于查找中序遍历数组中，每个值对应的索引
public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
for(int i = 0; i < in.length; i ++) {
map.put(in[i], i);//key: in的值，value: 值在in中位置
}
return getBiTree(pre, 0, pre.length - 1,
in, 0, in.length - 1);
}
private TreeNode getBiTree(int[] pre, int preLeft, int preRight, //前序遍历及当前在前序遍历中的区间
int[] in, int inLeft, int inRight) { //中序遍历及当前在前序遍历中的区间
if(preLeft == preRight) { //即根据前序遍历，当前结点无子结点
return new TreeNode(pre[preLeft]);
}
if(preLeft > preRight || inLeft > inRight) {
return null;
}
TreeNode root = new TreeNode(pre[preLeft]);
int inIndex = map.get(root.val);
int leftTreeSize = inIndex - inLeft;//该结点左半部分的结点数
//递归，获取左子树及右子树
root.left = getBiTree(pre, preLeft + 1, preLeft + leftTreeSize, //左半部分在前序遍历中的区间
in, inLeft, inIndex - 1);//左半部分在中序遍历中的区间
root.right = getBiTree(pre, preLeft + 1 + leftTreeSize, preRight, //右半部分在前序遍历中的区间
in, inIndex + 1, inRight);//右半部分在中序遍历中的区间
return root;
}
T5. 用两个栈实现队列
题目描述
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
解题思路
队列：先进先出，栈：先进后出
例如，假设 1 ~ n 的数字顺序，入Stack1，出的顺序为 n ~ 1 。
这时，Stack1出栈进入Stack2，进入Stack2的顺序为n ~ 1，那么Stack2出的顺序为 1 ~ n 。
相当于队列 1 ~ n 进， 1 ~ n 出。
Stack<Integer> stack1 = new Stack<Integer>();//stack1入栈时使用
Stack<Integer> stack2 = new Stack<Integer>();//stack2出栈时使用，直接出栈即可
public void push(int node) {
while(!stack2.isEmpty()) {//先将stack2中所有元素压入stack1
stack1.push(stack2.pop());
}
stack1.push(node);//然后将当前要进入队列元素压入stack1
while(!stack1.isEmpty()) {//最后将stack1所有元素压入stack2
stack2.push(stack1.pop());//此时stack2中出栈顺序即为队列出栈顺序，相当于先入先出
}
}
public int pop() {
return stack2.pop();
}
T6. 旋转数组的最小数字
题目描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
解题思路
我们可以认为数组分成了两部分，前半部分是较大的数，后半部分是较小的数。
利用二分查找的思路，观察取中的数在前半部分还是后半部分，以此来找出最小的数（后半部分的第一个数）。
public int minNumberInRotateArray(int[] array) {
if(array.length == 0) {
return 0;
}
//二分查找
int low = 0, high = array.length - 1;
while (array[low] >= array[high]) {
if(high - low == 1) {
return array[high];
}
int mid = low + (high - low) / 2;//取中
if(array[mid] >= array[low]) {//此时mid在前半区大的数里
low = mid;
} else {//此时mid在后半区小的数里
high = mid;
}
}
return array[low];
}
T7. 斐波那契数列
题目描述
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39
解题思路
斐波那契数列：F[n]=F[n-1]+F[n-2] (n>=3,F[1]=1,F[2]=1)
注意：此题要求F[1]=0。
public int Fibonacci(int n) {//n<=39
int[] array = new int[40];
array[0] = 0;
array[1] = 1;
for(int i = 2; i < array.length; i ++) {
array[i] = array[i - 1] + array[i - 2];
}
return array[n];
}
T8. 跳台阶
题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
解题思路
动态规划的思想。这里采用倒着往前推的方法递减target，最后一次跳1或最后一次跳2，倒着往前递归。
public int JumpFloor(int target) {
if(target == 0) {
return 0;
}
if(target == 1) {
return 1;
}
if(target == 2) {
return 2;
}
if(target > 2) {//递归求可能出现的情况总数（最后一次跳1或最后一次跳2，倒着往前推）
return JumpFloor(target - 1) + JumpFloor(target - 2);
}
return 0;
}
或者，其本质上是斐波那契数列的原理。
public int JumpFloor(int target) {
if(target == 0) {
return 0;
}
if(target == 1) {
return 1;
}
int[] array = new int[target];
array[0] = 1;
array[1] = 2;
for (int i = 2; i < target; i++) {
array[i] = array[i - 1] + array[i - 2];
}
return array[target - 1];
}
T9. 变态跳台阶
题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
解题思路
同理，动态规划的思想，递归求解。（这次情况有点多，用到循环了）
public int JumpFloorII(int target) {
if(target == 0 || target == 1) {
return 1;
}
if(target == 2) {
return 2;
}
int sum = 0;
for(int i = 0; i < target; i ++) {//本次跳0次到跳target-1次
sum += JumpFloorII(i);//对于本次的跳跃又有多少种跳法？递归获取结果
}
return sum;
}
T10. 矩阵覆盖
题目描述
我们可以用 2 * 1 的小矩形横着或者竖着去覆盖更大的矩形。请问用n个 2 * 1 的小矩形无重叠地覆盖一个 2 * n 的大矩形，总共有多少种方法？
解题思路
原理同T8，详见图片。
public int RectCover(int target) {
if(target == 0) {
return 0;
}
if(target == 1) {
return 1;
}
int[] array = new int[target];
array[0] = 1;
array[1] = 2;
for (int i = 2; i < target; i++) {
array[i] = array[i - 1] + array[i - 2];
}
return array[target - 1];
}
T11. 二进制中 1 的个数
题目描述
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
解题思路
Integer.bitCount(n)：技术整型的二进制表示中1的个数。。。
public int NumberOf1(int n) {//（？？？）
return Integer.bitCount(n);
}
正常算法：&按位与。每次将 n 和 n-1 进行 & 运算，从右往左去掉二进制最右边的一个1。例如：
n: 100100
n - 1: 100011
n & (n-1): 100000
一次运算后，n由100100变为100000，去除了一个1。所有1去完时，n为0。
public int NumberOf1(int n) {//正常算法
int sum = 0;
while(n != 0) {
sum ++;
n = n & (n-1);//&按位与
}
return sum;
}
T12. 数值的整数次方
题目描述
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
解题思路
由于xn = (x*x)n/2，通过递归求解可减小时间复杂度，每递归一次，n 减一半。时间复杂度O(logn)。
注意：需要小心 n 的正负、奇偶。
public double Power(double base, int exponent) {
if(exponent == 0) return 1;
if(exponent == 1) return base;
boolean isPositive = true;//正负次方以此判断
if(exponent < 0) {
exponent = -exponent;
isPositive = false;
}
double pow = Power(base * base, exponent / 2);//递归，每次递归n减小一半，即 (x*x)^(n/2)
if(exponent % 2 != 0) pow *= base;//奇次幂的话，/2会少算一次，在这补回来
return isPositive ? pow : (1 / pow);//三元表达式，正次幂为pow，负次幂为1/pow
}
T13. 调整数组顺序使奇数位于偶数前面
题目描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
解题思路
先统计奇偶数的个数。在所要求的数组中，奇数的个数即为数组中偶数应该开始储存的位置。
clone一个数组，按顺序往原数组里存，奇数存前面，偶数存后面。
public void reOrderArray(int[] array) {
int oddNum = 0;
for(int value: array) {
if(value % 2 == 1) {
oddNum++;
}
}
int[] copyArray = array.clone();//克隆数组，对原数组赋值
int i = 0, j = oddNum;//j为偶数开始存储的位置
for(int num : copyArray) {
if(num % 2 == 1) {
array[i] = num;
i ++;
} else {
array[j++] = num;
j ++;
}
}
}
或者，声明两个ArrayList存奇数和偶数，然后合并。
public void reOrderArray(int[] array) {
ArrayList<Integer> odd = new ArrayList<>();
ArrayList<Integer> even = new ArrayList<>();
for(int i = 0; i < array.length; i ++) {
if(array[i] % 2 == 0) {
even.add(array[i]);
} else {
odd.add(array[i]);
}
}
odd.addAll(even);
for(int i = 0; i < array.length; i ++) {
array[i] = odd.get(i);
}
}
T14. 链表中倒数第 K 个结点
题目描述
输入一个链表，输出该链表中倒数第k个结点。
解题思路
假设，共 n 个结点，倒数第k个结点即为第 n-k+1 个结点。
定义两个指针node1和node2，使他们都指向第一个结点。到第 n-k+1 个结点则需要移动 n-k次。
此时，node1移动n次会指向空。
先让node1移动 k 次，还剩 n-k 次指向空。
这时，node2与node1同步移动，当node1指空时，node2移动了 n-k 次，刚好到第 n-k+1 个结点。
public ListNode FindKthToTail(ListNode head, int k) {
if(head == null) return null;
ListNode node1 = head;
ListNode node2 = head;
while(node1 != null && k > 0) {//node1移动k次，还有n-k次会指空
node1 = node1.next;
k --;
}
if(k > 0) return null;
while(node1 != null) {//移动n-k次，此时node2到n-k+1个结点，即倒数第k个结点
node1 = node1.next;
node2 = node2.next;
}
return node2;
}
T15. 反转链表
题目描述
输入一个链表，反转链表后，输出新链表的表头。
解题思路
关键在于声明一个结点preNode用来记录前一个结点，使下一次循环时的结点的next指向它，反转顺序。
public ListNode ReverseList(ListNode head) {
if(head == null || head.next == null) return head;
ListNode preNode = null;
while(head != null) {
ListNode tmp = head.next;//tmp记录【下一个结点】
head.next = preNode;//【当前结点】的next指向【前一个结点】，反转链表顺序
preNode = head;//preNode记录【当前结点】，即【下一个结点】的【前一个结点】
head = tmp;//将【当前结点】更改为【下一个结点】，进入下一次循环
}
//当head为null时跳出了循环，此时它的前一个结点preNode即为原链表的最后一个结点，链表顺序已反转
return preNode;
}
T16. 合并两个排序的链表
题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
解题思路
声明一个新链表，不断比较原来两个链表的 val 值，小的插入新链表即可。
注意：要求返回的表头是声明的链表的next结点。
public ListNode Merge(ListNode list1, ListNode list2) {
ListNode head = new ListNode(-9999);
ListNode tmp = head;
while(list1 != null && list2 != null) {
if(list1.val < list2.val) {//比较两个链表当前结点的值，小的先插入新链表
tmp.next = list1;
list1 = list1.next;
} else {
tmp.next = list2;
list2 = list2.next;
}
tmp = tmp.next;
}
//容错，将剩余链表补到新链表结尾，此时能保持单调不减
if(list1 != null) tmp.next = list1;
if(list2 != null) tmp.next = list2;
return head.next;//记得head为声明的无意义表头，head.next才是新链表的头
}
项目地址：https://github.com/JohnnyJYWu/offer-Java
下一篇：算法 | 一周刷完《剑指Offer》 Day2：第17~26题
希望这篇文章对你有帮助~
