《剑指offer》 java版本 牛客网全AC

1.二维数组中的查找

public class Solution {
    public boolean Find(int target, int [][] array) {
        if(array.length == 0 || array[0].length == 0  )
            return false;
        int rows = array.length-1;
        int cols = array[0].length-1;
        int i = 0;
        int j = cols;
        while(i <= rows && j >= 0)
        {
            if(array[i][j] < target)
            {
                i++;
            }
            if(array[i][j] > target)
            {
                j--;
            }
            if(array[i][j] == target)
                return true;
        }
        return false;
    }
}

2.替换空格
简略思路：新开一个数组，从后往前，依次复制

import java.util.*;
public class Solution {
    public String replaceSpace(StringBuffer str) {
        String str1 = str.toString();
    	if(str1.equals(""))
            return str1;
        char [] strArray = str1.toCharArray();
        int i =0;
        int lengthSpace = 0;
        while(i < strArray.length)
        {
            if(strArray[i] == ' ')
                lengthSpace++;
            i++;
        }
        int newStrLength = strArray.length + lengthSpace*2;
        char [] newStr = new char[newStrLength];
        int j = newStrLength-1;
        i = strArray.length - 1;
        while(i >= 0)
        {
            if(strArray[i] !=  ' ')
            {
                newStr[j--] = strArray[i--];
            }else{
                newStr[j--] = '0';
                newStr[j--] = '2';
                newStr[j--] = '%';
                i--;
            }
        }
        return new String(newStr);
    }
}

3.从尾到头打印链表（反转链表）
思路：就是三个指针，pre,p,next，然后互相指就行，首先把pre的next指为null,然后p指向head的next,然后处理完开始的两个头结点，然后再处理后序的链表节点

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> resultList = new ArrayList<Integer>();
        if(listNode == null)
            return resultList;
        if(listNode.next == null)
        {
            resultList.add(new Integer(listNode.val));
        }
        ListNode head = listNode;
        ListNode p = listNode.next;
        ListNode pre = listNode;
        ListNode next;
        pre.next = null;
        while(p.next != null)
        {
            next = p.next;
            p.next = pre;
            pre = p;
            p = next;
        }
        p.next = pre;
        head = p;
        ListNode temp = head;
        while(temp != null)
        {
            resultList.add(temp.val);
            temp = temp.next;
        }
        return resultList;
    }
}

4.用两个栈实现队列

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);
    }
    
    public int pop() {
        if(stack2.empty())
        {
            while(stack1.empty() != true)
            {
                stack2.push(stack1.pop());
            }
        }
        if(stack2.empty() == true)
        {
            return -1;
        }
        return stack2.pop();
    }
}

5.旋转数组的最小数字

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        if(array.length == 0)
            return 0;
        if(array[0] < array[array.length-1])
            return array[0];
        int start = 0;
        int end = array.length - 1;
        int flag = 0;
        while(start+1 != end)
        {
            int mid = (start+end)/2;
            if(array[mid] > array[start])
                start = mid;
            else if(array[mid] < array[end])
                end = mid;
            else{
                flag = 1;
                break;
            }
        }
        if(flag == 1)
        {
            int min = Integer.MAX_VALUE;
            for(int i=0;i<array.length;i++)
            {
                if(min >= array[i])
                    min = array[i];
            }
            return min;
        }
        return array[end];
    }
}

6.斐波那契数列

public class Solution {
    public int Fibonacci(int n) {
        int a = 0;
        int b = 1;
        if(n == 0)
            return 0;
        if(n == 1)
            return 1;
        int i = 2;
        int sum=0;
        while(i <= n)
        {
            sum = a + b;
            a = b;
            b = sum;
            i++;
        }
        return sum;
    }
}

7.跳台阶

public class Solution {
    public int JumpFloor(int target) {
        if(target == 1)
            return 1;
        if(target == 2)
            return 2;
        int a = 1;
        int b = 2;
        int sum = a + b;
        for(int i=3;i<=target;i++)
        {
            sum = a + b;
            a = b;
            b = sum;
        }
        return sum;
    }
}

8.变态跳台阶

public class Solution {
    public int JumpFloorII(int target) {
        return (int)Math.pow(2,target-1);
    }
}

9.矩形覆盖

public class Solution {
    public int RectCover(int target) {
        if(target == 1)
            return 1;
        if(target == 2)
            return 2;
        int a = 1;
        int b = 2;
        int sum = 0;
        for(int i=3;i<=target;i++)
        {
            sum = a+b;
            a = b;
            b = sum;
        }
        return sum;
    }
}

10.二进制中1的个数
n与n-1相与，为0说明就是2的n次幂

public class Solution {
    public int NumberOf1(int n) {
        if(n == 0)
            return 0;
        int count = 0;
        while((n&(n-1)) != 0)
        {
            count++;
            n = n & (n-1);
        }
        count++;
        return count;
    }
}

11.数值的整数次方

public class Solution {
    public double Power(double base, int exponent) {
        if(exponent == 0)
        {
            if(equalZero(base) == true)
                return 0;
            return 1;
        }
        if(exponent > 0)
        {
            return complex(base,exponent);
        }
        if(equalZero(base))
        {
            if(base > 0)
                return Double.POSITIVE_INFINITY;
            if(exponent % 2 == 0)
                return Double.POSITIVE_INFINITY;
            return Double.NEGATIVE_INFINITY;
        }
        return 1 / complex(base,exponent);
    }
    double complex(double base,int exponent)
    {
        double result = 1.0;
        if(exponent < 0)
            exponent = 0 - exponent;
        for(int i=0;i<exponent;i++)
            result = result * base;
        return result;
    }
    boolean equalZero(double base)
    {
        if(base >0 && base < 0.00000001)
            return true;
        if(base < 0 && base > -0.00000001)
            return true;
        return false;
    }
}

12.调整数组顺序使得奇数在偶数前面

import java.util.*;
public class Solution {
    public void reOrderArray(int [] array) {
        ArrayList<Integer> A = new ArrayList<>();
        ArrayList<Integer> B = new ArrayList<>();
        for(int i=0;i<array.length;i++)
        {
            if(array[i] % 2 == 1)
                A.add(array[i]);
            else{
                B.add(array[i]);
            }
        }
        int i =0;
        for(;i<A.size();i++)
        {
            array[i] = A.get(i);
        }
        A.clear();
        for(int j=0;j < B.size();j++)
        {
            array[i] = B.get(j);
            i++;
        }
        B.clear();
    }
}

13.链表中倒数的第K个节点
先判断链表长度够不够K个，够的话，在让一个节点先走K-1步，然后另一个节点再走K-1步

public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        int length = 0;
        ListNode tempHead = head;
        while(tempHead != null)
        {
            length++;
            tempHead = tempHead.next;
        }
        if(k > length || k <=0)
            return null;
        ListNode before = head;
        ListNode after = head;
        for(int i=0;i<k-1;i++)
            before = before.next;
        while(before.next != null)
        {
            before = before.next;
            after = after.next;
        }
        return after;
    }
}

14.合并两个排序链表

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode head = new ListNode(-1);
        ListNode result;
        result = head;
        while(list1 != null && list2 != null)
        {
            if(list1.val < list2.val)
            {
                head.next = list1;
                list1 = list1.next;
            }else{
                head.next = list2;
                list2 = list2.next;
            }
            head = head.next;
        }
        if(list1 != null)
        {
            head.next = list1;
        }else{
            head.next = list2;
        }
        return result.next;
    }
}

15.树的子结构
思路;写一个额外的函数doHasSubtree，这个doHasSubtree 用来判读是不是子树，然后主函数进行前序的一个递归遍历，去遍历每一个节点是不是包含这个子树。

public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        boolean flag = false;
        if(root1 == null || root2 == null)
            return false;
        if(root1.val == root2.val)
            flag = doHasSubtree(root1,root2);
        if(flag == true)
            return true;
        flag = HasSubtree(root1.left,root2);
        if(flag)
            return true;
        flag = HasSubtree(root1.right,root2);
        if(flag)
            return true;
        return false;
    }
    public boolean doHasSubtree(TreeNode root1,TreeNode root2)
    {
        if(root2 == null)
            return true;
        if(root1 == null && root2 != null)
            return false;
        if(root1.val != root2.val)
            return false;
        return doHasSubtree(root1.left,root2.left) && doHasSubtree(root1.right,root2.right);
    }
}

16.二叉树的镜像
直接左右两个树进行交换进行。

public class Solution {
    public void Mirror(TreeNode root) {
        if(root == null )
            return;
        if(root.left == null && root.right == null)
            return;
        TreeNode tempNode = root.right;
        root.right = root.left;
        root.left = tempNode;
        Mirror(root.left);
        Mirror(root.right);
    }
}

17.顺时针打印矩阵
思路：count进行计数，count用来记录遍历的时候遍历了矩阵中多少个数，当遍历的总数达到count则结束，同时设置左边界，右边界，上边界，下边界，每走从左到右（从右到左，从上到下，从下到上），那么适当地改变边界值。

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printMatrix(int [][] matrix) {
        ArrayList<Integer> resultList = new ArrayList<>();
        int cols = matrix[0].length;
        int rows = matrix.length;
        int left=0,top=0,bottom=rows-1,right=cols-1;
        int count = 0;
        while(count < cols*rows)
        {
            for(int i=left;i<=right;i++)
            {
                resultList.add(matrix[top][i]);
                count++;
                if(count >= cols*rows)
                    return resultList;
            }
            top++;
            for(int i=top;i<=bottom;i++)
            {
                resultList.add(matrix[i][right]);
                count++;
                if(count >= cols*rows)
                    return resultList;
            }
            right--;
            for(int i=right;i>=left;i--)
            {
                resultList.add(matrix[bottom][i]);
                count++;
                if(count >= cols*rows)
                    return resultList;
            }
            bottom--;
            for(int i=bottom;i>=top;i--)
            {
                resultList.add(matrix[i][left]);
                count++;
                if(count >= cols*rows)
                    return resultList;
            }
            left++;
        }
        return resultList;
    }
}

18.包含min函数的栈
思路：设置成两个栈，一个栈用来存取最小数，每压入一个栈，就比较栈顶的数，然后就如果比栈顶的数大，那么最小栈就继续压入最小栈的栈顶的数。

import java.util.Stack;
public class Solution {

    Stack<Integer> stack1 = new Stack<>();
    Stack<Integer> stack2 = new Stack<>();
    public void push(int node) {
        stack1.push(node);
        if(stack2.empty())
        {
            stack2.push(node);
        }else{
            if(node <= (int)stack2.peek())
                stack2.push(node);
            else{
                stack2.push(stack2.peek());
            }
        }
    }
  
    public void pop() {
        stack2.pop();
        stack1.pop();
    }
  
    public int top() {
        return (int)stack1.peek();
    }
    
    public int min() {
        return (int)stack2.peek();
    }
}

19.栈的压入、弹出序列
思路：新建一个栈，从压栈序列中一直压栈，然后每次都去比较栈顶的值与弹栈序列的数是不是一样，不一样就继续压栈，直到一样了，说明弹栈序列的下标可以往后移动一个了，同时再次比较栈中的栈顶与弹栈序列的值是不是一样

import java.util.*;
public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        if(pushA.length != popA.length)
            return false;
        Stack<Integer> stack1 = new Stack<>();
        int j = 1;
        stack1.push(pushA[0]);
        for(int i=0;i<popA.length;i++)
        {
            while(j < pushA.length && stack1.peek() != popA[i])
            {
                stack1.push(pushA[j]);
                j++;
            }
            if(j >= pushA.length && stack1.peek() != popA[i])
                return false;
            stack1.pop();
        }
        return true;
    }
}

20.从上到下打印二叉树
思路：就是建个队列，依次入队，就是二叉树的层次遍历

public class Solution {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> resultList = new ArrayList<>();
        if(root == null)
            return resultList;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(queue.size() != 0)
        {
            TreeNode tempRoot = queue.poll();
            if(tempRoot.left != null)
                queue.offer(tempRoot.left);
            if(tempRoot.right != null)
                queue.offer(tempRoot.right);
            resultList.add(tempRoot.val);
        }
        return resultList;
    }
}

21.二叉树的后序遍历序列

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length == 0)
            return false;
        return verify(sequence,0,sequence.length-1);
    }
    public boolean verify(int [] sequence,int begin,int end)
    {
        if(begin == end)
            return true;
        int rootValue = sequence[end];
        int leftBegin = -1;
        int leftEnd = -1;
        int rightBegin = -1;
        int rightEnd = -1;
        for(int i=begin;i<end;i++)
        {
            if(sequence[begin] < rootValue)
                leftBegin = begin;
            if(sequence[i] < rootValue)
                leftEnd = i;
            else{
                if(rightBegin == -1)
                    rightBegin = i;
                rightEnd = i;
            }
        }
        if(rightBegin < leftEnd && rightBegin != -1)
            return false;
        return verify(sequence,leftBegin,leftEnd) && verify(sequence,rightBegin,rightEnd);
    }
}

22.二叉搜索树的后序遍历序列
思路：二叉树后序遍历最后的一个数是数的根结点的值，然后就每次都一趟遍历这个序列，记录下来左子树的最优的下标位置，和右子树的最左的下标位置，然后如果右子树的最左下标位置比左子树的最右下标位置小，那么就不是后序遍历序列

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length == 0)
            return false;
        return verify(sequence,0,sequence.length-1);
    }
    public boolean verify(int [] sequence,int begin,int end)
    {
        if(begin == end)
            return true;
        int rootValue = sequence[end];
        int leftBegin = -1;
        int leftEnd = -1;
        int rightBegin = -1;
        int rightEnd = -1;
        for(int i=begin;i<end;i++)
        {
            if(sequence[begin] < rootValue)
                leftBegin = begin;
            if(sequence[i] < rootValue)
                leftEnd = i;
            else{
                if(rightBegin == -1)
                    rightBegin = i;
                rightEnd = i;
            }
        }
        if(rightBegin < leftEnd && rightBegin != -1)
            return false;
        return verify(sequence,leftBegin,leftEnd) && verify(sequence,rightBegin,rightEnd);
    }
}```