前言
对于剑指offer中前20道算法题的解题思路和代码总结。
题目1： 在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
思路
首先判断二维数组是否为空，为空则直接返回false，由于这个二维数组从左到右，从上到下都是递增的，因此数组的左上角数字是最小的，右下角数字是最大的。当选择左上角或者右下角数字为遍历的起始节点时，遍历的方向不唯一，所以只能从左下角和右上角中选着一个作为遍历的起始点，因为遍历方向是唯一的。下图为一个二维数组，右上角为查询的起始节点，查询点为16。
代码
public class Solution {
public boolean Find(int target, int [][] array) {
if((array==null||array.length==0)||(array.length==1&&array[0].length==0))
return false;
int row = 0;
int low = array[0].length-1;
while(row <= array.length-1 && low >= 0){
if(array[row][low] > target){
low--;
}else if(array[row][low] < target){
row++;
}else{
return true;
}
}
return false;
}
}
题目2： 请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
思路
遍历字符串的每个字符，因为String类型是常量，不能更改，所用采用StringBuffer类型，new一个StringBuffer类型的变量nstr，当遍历到的字符不是空格时，就将该字符添加nstr变量中。当遍历到的字符是空格时，将“%20”添加到nstr变量中。最后再调用toString()方法，将StringBuffer类型转成String类型返回。
代码
public class Solution {
public String replaceSpace(StringBuffer str) {
int length= str.length();
StringBuffer nstr = new StringBuffer();
for (int i = 0 ; i<length;i++)
{
if (str.charAt(i)!=' ')
nstr.append(str.charAt(i));
else
nstr.append("%20");
}
return nstr.toString();
}
}
题目3： 输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
思路
方法一：利用栈先进后出的原理，遍历链表的同时，将元素放入栈中，等链表遍历完了，在从栈顶依次弹出元素并放入new出来的ArrayList中。
方法二：利用递归的方式。
代码
/**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
import java.util.ArrayList;
public class Solution {
ArrayList<Integer> ret = new ArrayList<Integer>();
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
if(listNode == null){
return ret;
}
printListFromTailToHead(listNode.next);
ret.add(listNode.val);
return ret;
}
}
--> 题目4： 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
思路
解本题的关键在于，前序遍历序列的第一个元素是当前树的根节点元素，同时这个元素在中序遍历序列中的位置划分左右子树，这样就可以得到左子树先序遍历序列{2，4，7}，左子树中序遍历序列{4，7，2}，右子树先序遍历序列{3，5，6，8}，右子树中序遍历序列{5，3，8，6}。然后递归的调用当前方法，分别将相应子树的先序遍历序列和中序遍历序列作为参数传入，递归的终止条件为：先序遍历序列或中序遍历序列的长度为空。
<img src="https://s2.ax1x.com/2019/12/17/QoOcsf.png" alt="QoOcsf.png" title="QoOcsf.png" />
代码
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
if(pre.length == 0){
return null;
}
TreeNode tn = new TreeNode(pre[0]);
System.out.println(pre[0]);
int id = 0;
for(int i = 0; i < in.length; i++){
if(pre[0] == in[i]){
id = i;
break;
}
}
int leftlength = id;
int rightlength = pre.length-id-1;
int[] preleft = new int[leftlength];
int[] inleft = new int[leftlength];
int[] preright = new int[rightlength];
int[] inright = new int[rightlength];
if(leftlength != 0){
System.arraycopy(pre, 1, preleft, 0, leftlength);
System.arraycopy(in, 0, inleft, 0, leftlength);
}
if(rightlength != 0){
System.arraycopy(pre, id+1, preright, 0, rightlength);
System.arraycopy(in, id+1, inright, 0, rightlength);
}
tn.left = reConstructBinaryTree(preleft, inleft);
tn.right = reConstructBinaryTree(preright, inright);
return tn;
}
public static void main(String[] args){
int[] pre = new int[]{1,2,4,7,3,5,6,8};
int[] in = new int[]{4,7,2,1,5,3,8,6};
Solution st = new Solution();
TreeNode root = st.reConstructBinaryTree(pre, in);
}
}
题目5： 用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
思路
栈是先进后出，队列是先进先出，想要用两个栈来实现队列，必须把放入stack1的原始进行反转，即依次弹出并装入stack2，就完成了反转。也就是说，添加元素时放入stack1，弹出元素时从stack2中取，当stack2为空时，就将stack1的元素依次弹出，并放入stack2。
代码
import java.util.Stack;
public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
stack1.push(node);
if(stack2.size() == 0){
while(stack1.size() != 0){
stack2.push(stack1.pop());
}
}
}
public int pop() {
if(stack2.size() != 0){
return stack2.pop();
}else{
if(stack1.size() != 0){
while(stack1.size() != 0){
stack2.push(stack1.pop());
}
return stack2.pop();
}
}
return -1;
}
}
题目6： 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
思路
首先判断数组是否空。然后遍历数组，并比较当前位置上的数字和后一位数字的大小，如果大于，直接返回后一位数字。
代码
import java.util.ArrayList;
public class Solution {
// 遍历（时间复杂度O(n)）
public int minNumberInRotateArray(int [] array) {
if(array.length == 0)
return 0;
for(int i = 0; i < array.length-1; i++){
if(array[i]>array[i+1])
return array[i+1];
}
return array[0];
}
// 利用二分查找(时间复杂度O(logn))
public int minNumberInRotateArray(int [] array) {
if(array.length == 0)
return 0;
int left = 0, right = array.length - 1;
while(left < right){
int mid = (left + right)/2;
if (array[mid] > array[right]){
left = mid + 1;
}else{
right = mid;
}
}
return array[left];
}
}
题目7：大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39
思路
斐波那契数列的特点是，第n项的值等于第n-1项的值加上第n-2项的值。可以用递归和循环的方法解题。
递归：终止条件：当n==0时返回0，当n <= 2时返回1。
迭代：斐波那契数列第0项为f(0) = 0，第1项为f(1) = 1，第2项f(2) = f(1) + f(0) = 1，第3项f(3) = f(2) + f(1)...，第n项f(n-1) + f(n-2）。
代码
// 递归
public class Solution {
public int Fibonacci(int n) {
if(n == 0){
return 0;
}else if(n <= 2){
return 1;
}
return Fibonacci(n-1) + Fibonacci(n-2);
}
}
// 迭代
public class Solution{
public int Fibonacci(int n){
int a = 0, b = 1, c = 1;
if(n == 0){
return 0;
}if(n <= 2){
return 1;
}else{
for(int i = 3, i < n, i++){
a = b + c;
b = c;
c = a;
}
}
return c;
}
}
题目8： 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
思路
这题本质上和斐波那契数列相似，台阶为1时f(1) = 1，台阶为2时f(2) = 2，台阶为3时f(3) = f(2) + f(1) = 3，台阶为4时f(4) = f(3) + f(2) = 5...台阶为n时f(n) = f(n - 1) + f(n - 2)。可以用递归和循环的方法解题。
递归：终止条件：当target==0时返回0，当target <= 2时返回target。
代码
// 递归
public class Solution {
public int JumpFloor(int target) {
if(target == 0){
return 0;
}else if(target <= 2){
return target;
}
return JumpFloor(target-1) + JumpFloor(target-2);
}
}
// 迭代
public class Solution {
public int JumpFloor(int target) {
int a = 0, b = 1, c = 2;
if(target == 0){
return 0;
}else if(target <= 2){
return target;
}
for(int i = 3; i <= target; i++){
a = b + c;
b = c;
c = a;
}
return c;
}
}
题目9： 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
思路
首先需要分析这题的规律，f(1) = 1, f(2) = f(2-1) + f(2-2) = 2, f(3) = f(3-1) + f(3-2) + f(3-3) = 4, f(4) = f(3) + f(2) + f(1) + f(0) = 8,...f(n-1) = f(n-2) + f(n-3) + ... + f(1) + f(0), f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(1) + f(0) = 2*f(n-1)。可以用递归和循环的方法解题。
代码
// 递归
public class Solution {
public int JumpFloorII(int target) {
if(target <= 2){
return target;
}
return 2*JumpFloorII(target-1);
}
}
// 迭代
public class Solution {
public int JumpFloorII(int target) {
int a = 0, b = 1, c = 2;
if (target == 0){
return 0;
}else if(target <= 2){
return target;
}
for(int i = 3; i <=target; i++){
a = 2*c;
b = c;
c = a;
}
return c;
}
}
题目10： 我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
思路
这个题也可以转化为初级跳台阶问题，解法和题8一样。
<img src="https://s2.ax1x.com/2019/12/18/QHlo5T.png" alt="QHlo5T.png" title="QHlo5T.png" />
题目11： 输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
思路
如下图所示，由于计算机是通过补码运算，减去1相当于加上（-1）补码，所以任何两个数之间的加减运算都会变成补码的加法预算，当一个数减去1（即加上-1的补码），相当于将二进制表示中的最后一位1以及其后面的0进行反转，所谓反转就是0变成1，1变成0，最后再与原数据的补码表示进行位与运算，就可以去掉原数据补码形式最右边的1。这个过程每进行一次，二进制补码表示中的1的数量就加一，直到变成零。
<img src="https://s2.ax1x.com/2019/12/19/QqyZGD.png" alt="QqyZGD.png" title="QqyZGD.png" />
代码
public class Solution {
public int NumberOf1(int n) {
if(n == 0){
return 0;
}
int count = 0;
while(n != 0){
count ++;
n = n&(n-1);
}
return count;
}
}
题目12：给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。保证base和exponent不同时为0
思路
本题需要注意的一点就是exponent如果小于0，就需要哦输出base的-exponent次方的倒数，以及exponent等于零时，输出1。
代码
public class Solution {
public double Power(double base, int exponent) {
double result = base;
int n = exponent;
if (exponent < 0) {
exponent = - exponent;
}
else if(exponent == 0) {
return 1;
}
for (int i = 1; i < exponent; i++) {
result *= base;
}
return n < 0 ? 1 / result : result;
}
}
题目12： 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
思路
指针ind始终指向偶数第一个元素，当遍历到奇数是，偶数指针ind和遍历指针i之间的数都是偶数，使用jj寄存遍历指针i指向的奇数，并将偶数指针ind和遍历指针i之间的偶数后移一位，原来偶数指针指向的位置换成变量jj中的奇数，最后ind+1。
<img src="https://s2.ax1x.com/2019/12/19/Qqj6fO.png" alt="Qqj6fO.png" title="Qqj6fO.png" />
代码
public class Solution {
public void reOrderArray(int [] array) {
int even = -1;
for (int i = 0; i < array.length; i++){
if(array[i]%2 == 0 && even == -1)
even = i;
if(array[i]%2 != 0 && even != -1){
int temp = array[i];
System.arraycopy(array, even, array, even+1, i-even);
array[even] = temp;
even++;
}
}
}
}
题目13： 输入一个链表，输出该链表中倒数第k个结点。
思路
使用指针listh和指针lista，他们先同时指向链表的第一个元素，让lista先遍历链表，当遍历到第k个元素时，listh开始和lista以相同的速度开始遍历，当lista指向null时，listh就指向倒数第k个元素。
代码
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(head == null){
return null;
}
ListNode listh = head;
ListNode lista = head;
while(lista != null){
if(k == 0){
listh = listh.next;
}
if(k > 0)
k--;
lista = lista.next;
}
if(k > 0)
return null;
return listh;
}
}
题目14： 输入一个链表，反转链表后，输出新链表的表头。
思路
使用头插法
代码
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode ReverseList(ListNode head) {
ListNode pre = null;
ListNode next = null;
while(head != null){
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}
}
题目15： 输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
思路
可以使用递归和迭代的方法。
代码
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
// 迭代
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
ListNode ln = null;
if(list1 == null){
return list2;
}else if (list2 == null){
return list1;
}
if(list1.val <= list2.val){
ln = list1;
list1 = list1.next;
}else{
ln = list2;
list2 = list2.next;
}
ListNode rln = ln;
while(list1 != null && list2 != null){
if(list1.val <= list2.val){
ln.next = list1;
ln = ln.next;
list1 = list1.next;
}else{
ln.next = list2;
ln = ln.next;
list2 = list2.next;
}
}
if(list1 != null){
ln.next = list1;
}else{
ln.next = list2;
}
return rln;
}
}
//递归
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
if(list1 == null){
return list2;
}else if(list2 == null){
return list1;
}
ListNode ln = null;
if(list1.val <= list2.val){
ln = list1;
ln.next = Merge(list1.next, list2);
}else{
ln = list2;
ln.next = Merge(list1, list2.next);
}
return ln;
}
}
--> 题目16： 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
思路
1.判断A树和B树是否为空，其中任意一棵为空则返回false。
2.判断A树和B树的根节点是否相同，如果相同则递归的判断A树左右子树和B树的左右子树是否相同，相同返回true，不同则递归判断A树的左右子树和B树是否相同。
代码
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
if(root2 == null){
return false;
}
if(root1 == null){
return false;
}
return isSubtree(root1,root2) || HasSubtree(root1.left,root2) || HasSubtree(root1.right,root2);
}
public boolean isSubtree(TreeNode root1,TreeNode root2){
if(root2 == null){
return true;
}
if(root1 == null){
return false;
}
if(root1.val == root2.val){
return isSubtree(root1.left, root2.left) && isSubtree(root1.right, root2.right);
}
return false;
}
}
题目17: 操作给定的二叉树，将其变换为原二叉树的镜像。
输入描述:
二叉树的镜像定义：源二叉树
8
/ \
6 10
/ \ / \
5 7 9 11
镜像二叉树
8
/ \
10 6
/ \ / \
11 9 7 5
思路
从根节点开始交换左右子树，然后从左右子树递归此过程，当树为空时终止递归。
代码
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public void Mirror(TreeNode root) {
if(root == null){
return;
}
TreeNode tn = root.left;
root.left = root.right;
root.right = tn;
Mirror(root.left);
Mirror(root.right);
}
}
题目18： 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
思路
分别记录最外圈四个角的位置，一次从左到右，从上到下，从右到左，从下到上遍历，然后将四个角的位置向内圈缩一圈。最后需要单独处理三种情况：剩下一行，一列和一格。
代码
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printMatrix(int [][] matrix) {
ArrayList al = new ArrayList();
int left = 0, right = matrix[0].length - 1, top = 0, bottom = matrix.length - 1;
while(right > left&&bottom > top){
// 从左到右
for(int i = left; i <= right; i++){
al.add(matrix[top][i]);
}
// 从上到下
for(int i = top+1; i <= bottom; i++){
al.add(matrix[i][right]);
}
// 从右到左
for(int i = right - 1; i >= left; i--){
al.add(matrix[bottom][i]);
}
// 从下到上
for(int i = bottom - 1; i >= top + 1; i--){
al.add(matrix[i][left]);
}
left++;
right--;
top++;
bottom--;
}
if(right > left && bottom == top){
for(int i = left; i <=right; i++){
al.add(matrix[top][i]);
}
}
if(right == left && bottom > top){
for(int i = top; i <=bottom; i++){
al.add(matrix[i][left]);
}
}
if(left == right && bottom == top){
al.add(matrix[left][top]);
}
return al;
}
}
题目19： 定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
思路
用stc1正常存数据 ，用stc2存当前stc1这种最小的数，当一个数进来时与stc2（栈顶）中当前最小的数比，如果比当前最小的数小，则同时存入stc1和stc2，如果比stc2中当前最小的数最大，则只存入stc1中。当需要 弹出栈顶元素时，如果stc1栈顶的元素和stc2栈顶的元素相同，则同时弹出，不同，则只弹出stc1中栈顶元素。
代码
import java.util.Stack;
public class Solution {
private Stack<Integer> stc1 = new Stack();
private Stack<Integer> stc2 = new Stack();
public void push(int node) {
stc1.push(node);
if(stc2.empty()){
stc2.push(stc1.peek());
}else{
if(stc1.peek() <= stc2.peek()){
stc2.push(node);
}
}
}
public void pop() {
if(!stc1.empty()){
if(stc1.peek() == stc2.peek()){
stc1.pop();
stc2.pop();
}else{
stc1.pop();
}
}
}
public int top() {
if(!stc1.empty()){
return stc1.peek();
}
return -1;
}
public int min() {
if(!stc2.empty()){
return stc2.peek();
}
return -1;
}
}
-->题目20： 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
思路
根据给定的入栈出栈序列模拟入栈出栈过程，先按照入栈序列入栈，每入一个元素，就对比当前出栈序列的第一个元素，如果不同，继续按照入栈序列入栈，如果相同，则弹出当前栈顶元素，当前出栈序列的第一个元素指向下一个元素。如果能遍历完出栈序列的所有元素，则返回true，如果出栈序列没有遍历完，入栈序列超出范围，则返回false。
代码
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
Stack<Integer> sta = new Stack();
int curpush = 0, curpop = 0;
sta.push(pushA[0]);
while(curpop < popA.length){
if(sta.peek() == popA[curpop]){
sta.pop();
curpop++;
}else{
if (curpush == pushA.length-1)
break;
sta.push(pushA[++curpush]);
}
}
return sta.isEmpty();
}
}
