剑指offer（一）

╰半橙微兮° 2022-05-19 05:58 196阅读 0赞

## 1.二维数组中的查找 ##

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

###### 思路：这题有比较多的解法，第一种最容易的当然是暴力破解法，复杂度为n^2，这显然不是题目理想的解法。第二种，因为每一行都是递增的，所以我们可以在每一行上使用二分查找，时间复杂度为mlogn。第三种，如果从左上角开始，向右或者向下都是递增，无法判断，所以换个思路，从左下角开始，这样向右就是递增，向上就是递减。 ######

**解法1：使用二分法**

public class Solution {
        public boolean Find(int target, int [][] array) {
            for(int i = 0; i < array.length; i++) {
                int start = 0;
                int end = array[i].length - 1;
                while(start <= end) {
                    int m = (start + end) / 2;
                    if(target == array[i][m]) {
                        return true;
                    } else if(target < array[i][m]) {
                        end = m - 1;
                    } else {
                        start = m + 1;
                    }
                }
            }
            return false;
        }
    }

**解法2：从左下角开始**

public class Solution {
        // 如果从左上角开始，向右或者向下都是递增，无法判断，所以换个思路，从左下角开始，这样向右就是递增，向上就是递减
        public boolean Find(int target, int [][] array) {
            int j = 0;
            int i = array.length - 1;
            while(j < array[0].length && i >= 0) {
                if(target == array[i][j]) {
                    return true;
                } else if(target < array[i][j]) {
                    i--;
                } else {
                    j++;
                }
            }
            return false;
        }
    }

--------------------

## 2.替换空格 ##

请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy

**解法1：使用现有的replace方法**

public class Solution {
        public String replaceSpace(StringBuffer str) {
            return str.toString().replace(" ", "%20");
        }
    }

**解法2：不使用replace方法，从前往后遍历字符串，遇到空格则进行替换**

public class Solution {
        public String replaceSpace(StringBuffer str) {
            StringBuilder sb = new StringBuilder();
            for(int i = 0; i < str.length(); i++) {
                if(str.charAt(i) == ' ') {
                    sb.append("%20");
                } else {
                    sb.append(str.charAt(i));
                }
            }
            return sb.toString();
        }
    }

--------------------

## 3.从尾到头打印链表 ##

输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

###### 思路：我的想法就是使用两个ArrayList，第一个先存放遍历一遍链表的结果，然后把第一个ArrayList逆着赋值给第二个ArrayList。因为这里题目给了import，所以我觉得应该是不能自己添加import，只能使用ArrayList。 ######

/** * public class ListNode { * int val; * ListNode next = null; * * ListNode(int val) { * this.val = val; * } * } * */
    import java.util.ArrayList;
    public class Solution { 
        public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
            ArrayList<Integer> result = new ArrayList<>();
            ArrayList<Integer> temp = new ArrayList<>();
            while(listNode != null) {
                temp.add(listNode.val);
                listNode = listNode.next;
            }
            for(int i = temp.size() - 1; i >= 0; i--) {
                result.add(temp.get(i));
            }
            return result;
        }
    }

--------------------

## 4.重建二叉树 ##

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{1,2,4,7,3,5,6,8\}和中序遍历序列\{4,7,2,1,5,3,8,6\}，则重建二叉树并返回。

**思路：知道前中遍历，可以确定一棵树，知道中后遍历，也可以确定一棵树，但知道前后遍历，则不能确定一棵树。**  
**这里我们通过前序遍历，可以知道前序遍历的第一个元素就是树的根节点，通过中序遍历，找到根节点，则可以知道树的左右子树，然后依次递归查找左右子树即可。**

/** * 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) {
            TreeNode root = getReConstructBinaryTree(pre, 0, pre.length - 1, in, 0, in.length - 1);
            return root;
        }
    
        private static TreeNode getReConstructBinaryTree(int[] pre, int preStart, int preEnd, int[] in, int inStart, int inEnd) {
            if(preStart > preEnd || inStart > inEnd) {
                return null;
            }
            // 先序遍历的第一个节点就是根节点
            TreeNode root = new TreeNode(pre[preStart]);
            for(int i = inStart; i <= inEnd; i++) {
                // 相等的时候，就知道左右子树分别是哪些节点了
                if(in[i] == pre[preStart]) {
                    // 左子树
                    root.left = getReConstructBinaryTree(pre, preStart + 1, preStart + i - inStart, in, inStart, i - 1);
                    root.right = getReConstructBinaryTree(pre, i - inStart + preStart + 1, preEnd, in, i + 1, inEnd);
                    break;
                }
            }
            return root;
        }
    }

--------------------

## 5.用两个栈实现队列 ##

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

###### 思路：用一个栈（stack1）作为入队列，直接放入数据。另一个栈（stack2）作为出队列，出队列分为两种情况：如果stack2为空，则先把stack1的所有数据放入stack2，然后弹出stack2的栈顶元素。如果stack2不为空，则直接弹出栈顶元素。 ######

import java.util.Stack;
    
    public class Solution {
        Stack<Integer> stack1 = new Stack<Integer>();
        Stack<Integer> stack2 = new Stack<Integer>();
        // 用stack1作为入队列，直接放入
        // 出队列时分为以下两种情况
        public void push(int node) {
            stack1.push(node);
        }
    
        public int pop() {
            // 1.如果stack2为空，则把stack1的数据全部放入stack2，在弹出
            if(stack2.empty()) {
                while(!stack1.empty()) {
                    stack2.push(stack1.pop());
                }
            }
            // 2.不为空则直接弹出
            return stack2.pop();
        }
    }

扩展

## 用两个队列实现一个栈 ##

###### 思路：假设有两个队列queue1，queue2，queue1提供压栈功能，queue2提供出栈功能。压栈时直接把数据压入queue1，出栈时分为两种情况：如果queue1只有一个元素，则直接输出该元素。如果queue1不止一个元素，则把queue1的除了最后那个元素，全部放入queue2，然后输出queue1剩下的那个元素，再把queue2的所有元素入queue1。 ######

import java.util.Queue;
    import java.util.ArrayDeque;
    public class Solution { 
        Queue<Integer> queue1= new ArrayDeque<Integer>();
        Queue<Integer> queue2= new ArrayDeque<Integer>();
    
        public void push(int node) {
            queue1.offer(node);
        }
    
        public int pop() {
            if(queue1.size() <= 1) {
                return queue1.poll();
            } else {
                while(queue1.size() > 1) {
                    queue2.add(queue1.poll());
                }
            }
            while(queue2.size() > 0) {
                queue1.add(queue2.poll());
            }
            return queue1.poll();
        }
    }

--------------------

## 6.旋转数组最小的数字 ##

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组\{3,4,5,1,2\}为\{1,2,3,4,5\}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

import java.util.ArrayList;
    public class Solution {
        public int minNumberInRotateArray(int [] array) {
            if(array.length == 0) {
                return 0;
            }
            int result = 0;
            for(int i = 0; i < array.length - 1; i++) {
                if(array[i] > array[i + 1]) {
                    result = array[i + 1];
                    break;
                }
            }
            return result;
        }
    }

###### 貌似我这样写不对，但的确ac了。题目说非减排序的数组，但也没说递增，所以我这样的解法是不对的。 ######

--------------------

## 7.斐波那契数列 ##

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。

n<=39

0,1,1,2,3,5…….

###### 思路：记得看清题目，从0开始，第0项为0。 ######

public class Solution {
        public int Fibonacci(int n) {
            if(n == 0) {
                return 0;
            }
            int f0 = 1;
            int f1 = 1;
            int result = 1;
            for(int i = 2; i < n; i++) {
                result = f0 + f1;
                f0 = f1;
                f1 = result;
            }
            return result;
        }
    }

--------------------

## 8.跳台阶 ##

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

###### 思路：这题你多写几级台阶就找到规律了，和上题大同小异。 ######

public class Solution {
        public int JumpFloor(int target) {
            if(target == 1) {
                return 1;
            }
            int f0 = 1;
            int f1 = 2;
            int r = 2;
            for(int i = 2; i < target; i++) {
                r = f0 + f1;
                f0 = f1;
                f1 = r;
            }
            return r;
        }
    }

--------------------

## 9.变态跳台阶 ##

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

###### 思路：也是找规律找出来的 ######

public class Solution {
        public int JumpFloorII(int target) {
            int r = 1;
            for(int i = 1; i < target; i++) {
                r = r * 2;
            }
            return r;
        }
    }

--------------------

## 10.矩形覆盖 ##

我们可以用2\*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2\*1的小矩形无重叠地覆盖一个2\*n的大矩形，总共有多少种方法？

###### 思路：画一画分析一下，你会发现它其实还是一个斐波那契的盗版。 ######

public class Solution {
        public int RectCover(int target) {
            if(target == 0) {
                return 0;
            }
            int f0 = 1;
            int f1 = 1;
            int r = 1;
            for(int i = 1; i < target; i++) {
                r = f0 + f1;
                f0 = f1;
                f1 = r;
            }
            return r;
        }
    }