剑指offer-在线编程（牛客网）- 基础知识

分手后的思念是犯贱 2022-05-17 00:47 180阅读 0赞

声明：本博客中的代码都是自己实现，若有问题，请大家不吝赐教！

## 面试需要的基础知识--------数组 ##

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

### 【面试题3】 数组中重复的数字 ###

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组\{2,3,1,0,2,5,3\}，那么对应的输出是第一个重复的数字2。

分析：因为数组中数字的范围是0到n-1，而长度是n，不妨将数组中的元素放到对应的坐标下，如若有重复的数字，那么该值代表的坐标下的数字必定已经是该值。那么就返回该值就可以了。

public class Solution {
        // Parameters:
        //    numbers:     an array of integers
        //    length:      the length of array numbers
        //    duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
        //                  Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
        //    这里要特别注意~返回任意重复的一个，赋值duplication[0]
        // Return value:       true if the input is valid, and there are some duplications in the array number
        //                     otherwise false
        public boolean duplicate(int numbers[],int length,int [] duplication) {
            if(length < 2 || numbers.length != length){
                return false;
            }
            for(int i = 0;i < length; i++){
                if(numbers[i]<0 || numbers[i]>length-1){
                    return false;
                }
                while(numbers[i] != i){
                    if(numbers[numbers[i]] == numbers[i]){
                        duplication[0] = numbers[i];
                        return true;
                    }
                    int temp = numbers[i];
                    numbers[i] = numbers[temp];
                    numbers[temp] = temp;
                }
            }
            return false;
        }
    }

### 【面试题4】 二维数组中查找 ###

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

分析：只能从右上角或左下角开始查找，否则会有两个区域无法选择。

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

## 面试需要的基础知识--------字符串 ##

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

### 【面试题5】 替换空格 ###

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

public class Solution {
        public String replaceSpace(StringBuffer str) {
            int spaceNum = 0;
            for(int i = 0; i < str.length(); i++){
                if(str.charAt(i) == ' '){
                    spaceNum++;
                }
            }
            int j = str.length() + 2*spaceNum - 1;
            char[] result = new char[j+1];
        	for(int i = str.length()-1; i>=0; i--){
                if(str.charAt(i) == ' '){
                    result[j--] = '0';
                    result[j--] = '2';
                    result[j--] = '%';
                }else{
                    result[j--] = str.charAt(i);
                }
            }
            return new String(result);
        }
    }

### 【面试题6】 从尾到头打印链表 ###

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

分析：递归思想，要添加链表当前节点的值到数组列表中，先添加链表下一节点的值。

import java.util.ArrayList;
    public class Solution {
        public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
            ArrayList<Integer> result = new ArrayList<Integer>();
            if(listNode != null){
                printCore(listNode,result);
            }
            return result;
        }
        public void printCore(ListNode listNode, ArrayList<Integer> result){
            if(listNode == null){
                return;
            }
            printCore(listNode.next,result);
            result.add(listNode.val);
        }
    }

## 面试需要的基础知识--------树 ##

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

### 【面试题7】 重建二叉树 ###

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

public class Solution {
        public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
                   if(pre==null||in==null){
                return null;
            }
     
            java.util.HashMap<Integer,Integer> map= new java.util.HashMap<Integer, Integer>();
            for(int i=0;i<in.length;i++){
                map.put(in[i],i);
            }
            return preIn(pre,0,pre.length-1,in,0,in.length-1,map);
        }
         
          public TreeNode preIn(int[] p,int pi,int pj,int[] n,int ni,int nj,java.util.HashMap<Integer,Integer> map){
     
            if(pi>pj){
                return null;
            }
            TreeNode head=new TreeNode(p[pi]);
            int index=map.get(p[pi]);
            head.left=preIn(p,pi+1,pi+index-ni,n,ni,index-1,map);
            head.right=preIn(p,pi+index-ni+1,pj,n,index+1,nj,map);
            return head;
        }
    }

### 【面试题8】 二叉树的下一个节点 ###

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

public class Solution {
        public TreeLinkNode GetNext(TreeLinkNode pNode)
        {
            if(pNode == null){
                return null;
            }
            else if(pNode.right != null){
                TreeLinkNode node = pNode.right;
                while(node.left != null){
                    node = node.left;
                }
                return node;
            }else if(pNode.next != null){
                int val = pNode.val;
                TreeLinkNode parent = pNode.next;
                while(parent.left != null && parent.left.val != val){
                     if(parent.next == null){
                          break;
                    }
                    val = parent.val;
                    parent = parent.next;
                }
                if(parent.left != null && parent.left.val == val){
                    return parent;
                }
            }
            return null;
        }
    }

## 面试需要的基础知识--------栈和队列 ##

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

### 【面试题9】 用两个栈实现队列 ###

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

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);
    //        System.out.println(node);
        }
        
        public int pop() {
            if(stack2.isEmpty()){
                while(!stack1.isEmpty()){
                    stack2.push(stack1.pop());
                }
            }
            return stack2.pop();
        }
    }

## 面试需要的基础知识--------递归和循环 ##

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

### 【面试题10】 斐波那契数列 ###

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

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

### 引申：青蛙跳台问题 ###

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

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

### 引申：矩形覆盖 ###

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

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

## 面试需要的基础知识--------查找和排序 ##

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

### 【面试题11】 旋转数组中的最小数字 ###

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组\{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 len = array.length;
            if(array[0] < array[len-1]){
                return array[0];
            }
            for(int i = 0; i<len-1; i++){
                if(array[i]>array[i+1]){
                    return array[i+1];
                }
            }
            return array[len-1];
        }
    }

## 面试需要的基础知识--------回溯法 ##

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

### 【面试题12】矩阵中的路径 ###

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。 例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

需要注意的是：矩阵并不是由二维数组表示，而是由从左到右，从上到下，依次将数组保存到一维数组中。

public class Solution {
        public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
        {
            int []flag=new int[matrix.length];
            for(int i=0;i<rows;i++)
            {
                for(int j=0;j<cols;j++)
                {
                   if(helper(matrix,rows,cols,i,j,0,str,flag))
                      return  true;
                }
            }
          return false;
        }
        public boolean helper(char[]matrix,int rows,int cols,int i,int j,int k,char[]str,int[]flag)
        {
            int index=i*cols+j;
            if(i<0||i>=rows||j<0||j>=cols||flag[index]==1||matrix[index]!=str[k])return false;
            if(k==str.length-1)return true;
            flag[index]=1;
            if(helper(matrix,rows,cols,i+1,j,k+1,str,flag)||helper(matrix,rows,cols,i-1,j,k+1,str,flag)||helper(matrix,rows,cols,i,j+1,k+1,str,flag)||helper(matrix,rows,cols,i,j-1,k+1,str,flag))
              return  true;
            flag[index]=0;
            return false;
        }
    }

### 【面试题13】 机器人的运动范围 ###

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

public class Solution {
        public int movingCount(int threshold, int rows, int cols)
        {
            if(threshold<0 || rows<=0 || cols<=0){
                return 0;
            }
            boolean[] visited = new boolean[rows*cols];
            for(int i = 0; i<rows*cols; i++){
                visited[i] = false;
            }
            return movingCountCore(threshold,rows,cols,0,0,visited);
        }
        public int movingCountCore(int threshold,int rows,int cols,int row,int col,boolean[] visited){
            int count = 0;
            if(check(threshold,rows,cols,row,col,visited)){
                visited[row*cols+col] = true;
                count = 1 + movingCountCore(threshold,rows,cols,row-1,col,visited)
                    + movingCountCore(threshold,rows,cols,row+1,col,visited)
                    + movingCountCore(threshold,rows,cols,row,col-1,visited)
                    + movingCountCore(threshold,rows,cols,row,col+1,visited);
    
            }
            return count;
        }
        public boolean check(int threshold,int rows,int cols,int row,int col,boolean[] visited){
            if(row>=0 && col>=0 && row<rows && col<cols && !visited[row*cols+col] && checkSum(row,col,threshold))
                return true;
            return false;
        }
        public boolean checkSum(int row,int col,int threshold){
            int sum = 0;
            while(row > 0){
                sum += row%10;
                row = row/10;
            }
             while(col > 0){
                sum += col%10;
                col = col/10;
            }
            if(sum > threshold)
                return false;
            return true;
        }
    }

## 面试需要的基础知识--------位运算 ##

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

### 【面试题15】 二进制中1的个数 ###

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

分析：n & (n-1) 可以消除掉n的二进制表示中最右端的1.

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