面试算法题

题目来源于牛客网:https://www.nowcoder.com/ta/coding-interviews

1、二维数组中的查找

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

public class Solution {
    public static boolean find(int target, int [][] array) {
        int m = array.length;//行数
        int n = array[0].length;//列数
        //从左下角开始查找
        int x=m-1;  //行号
        int y=0;    //列号
        while(x>=0 && y<=n-1){
            if(target<array[x][y]){
                x--;//上移1行
            }else if(target>array[x][y]){
                y++;//右移1列
            }else {//查到
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args){
        int[][] array={{1,2,3,5,7,8,9,10,11},
                       {2,3,4,5,8,10,11,13,15},
                       {3,4,5,6,10,11,14,18,20},
                       {5,6,8,10,15,18,20,25,29},
                       {7,10,20,27,36,41,47,50,56},
                       {10,12,23,29,48,57,63,77,99}};
        System.out.println(find(36,array));
        System.out.println(find(19,array));
    }
}
true
false

2、替换空格

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

public class Solution {

    /**
     * 偷懒方式
     */
    public static String replaceSpace(StringBuffer str) {
        return str.toString().replaceAll(" ", "%20");
    }
    /**
     * 需要考察的方式
     */
    public static String replaceSpace2(StringBuffer str) {
        for(int i=0;i<str.length();i++){
            if(' '==str.charAt(i)){
                str.replace(i, i+1, "%20");
                i=i+2;
            }
        }
        return str.toString();
    }

    public static void main(String[] args ){
        StringBuffer sb=new StringBuffer("a b cd e f g h");
        System.out.println(replaceSpace(sb));
        System.out.println(replaceSpace2(sb));
    }
}

3、单链表逆序的递归算法

package test;

public class LinkList {

    static class ListNode {
        int val;
        ListNode next = null;
        ListNode(int val) {
            this.val = val;
        }
    }
    /**
     * 单链表递归逆序,将单链表分解为首节点和其他节点
     * @param head
     */
    public static ListNode reverse(ListNode head){ 
        if(head==null||head.next==null){
            return head;
        }
        ListNode newTail=head.next;
        //对其他节点进行逆序。注意:head.next指向子链表的第一个节点,逆序后指向最后一个节点
        ListNode newHead=reverse(head.next);
        //将头节点放到已经逆序子链表最后
        newTail.next=head;
        head.next=null;
        return newHead;
    }

    public static ListNode reverseList(ListNode head){ 
        ListNode q;
        ListNode p=head.next;//p节点是当前节点
        head.next=null;//断开
        while(p!=null){//当前节点非空
            q=p.next;   //q指向下一节点
            p.next=head;
            head=p;
            p=q;
        }
        return head;
    }

    public static void main(String[] args){
        ListNode head=new ListNode(1);
        ListNode p=head;
        p.next=new ListNode(2);
        p=p.next;
        p.next=new ListNode(3);
        p=p.next;
        p.next=new ListNode(4);
        p=p.next;
        p.next=new ListNode(5);
        p=p.next;
        p.next=new ListNode(6);
        p=p.next;
        p.next=new ListNode(7);
        p.next.next=null;
        p=head;
        while(p!=null){
            System.out.print(p.val+" ");
            p=p.next;
        }
        System.out.println();
        head=reverse(head);
        p=head;
        while(p!=null){
            System.out.print(p.val+" ");
            p=p.next;
        }
        System.out.println();
        head=reverseList(head);
        p=head;
        while(p!=null){
            System.out.print(p.val+" ");
            p=p.next;
        }
    }
}
1 2 3 4 5 6 7 
7 6 5 4 3 2 1 
1 2 3 4 5 6 7 

4、重建二叉树

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

package test;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}

public class BinaryTree {
    public static TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        return createBinaryTree(pre,0,pre.length-1,in,0,in.length-1);
    }

    private static TreeNode createBinaryTree(int[] pre,int startPre,int endPre,int[] in,int startIn,int endIn){
        if(startPre>endPre||startIn>endIn){
            return null;
        }
        //构造root节点,前序第一个值是根节点值
        TreeNode root=new TreeNode(pre[startPre]);
        int step=0;
        for(int i=startIn;i<=endIn;i++){//查询root节点在中序中的位置
            if(in[i]==pre[startPre]){//i是真实下标
                //移动距离
                step=i-startIn;
                //构造左子树
                root.left=createBinaryTree(pre,startPre+1,startPre+step,in,startIn,i-1);
                //构造右子树
                root.right=createBinaryTree(pre,startPre+step+1,endPre,in,i+1,endIn);       
                break;
            }   
        }
        return root;
    }

    public static void preOrderTraverse(TreeNode root){
        if(root==null){
            return ;
        }
        System.out.print(root.val+" ");
        preOrderTraverse(root.left);
        preOrderTraverse(root.right);       
    }

    public static void inOrderTraverse(TreeNode root){
        if(root==null){
            return ;
        }
        preOrderTraverse(root.left);
        System.out.print(root.val+" ");
        preOrderTraverse(root.right);       
    }


    public static void main(String[] args){
        int[] pre={1,2,4,7,3,5,6,8};
        int[] in={4,7,2,1,5,3,8,6};
        TreeNode root=reConstructBinaryTree(pre,in);
        preOrderTraverse(root);
        System.out.println();
        inOrderTraverse(root);
    }
}
1 2 4 7 3 5 6 8 
2 4 7 1 3 5 6 8 

5、用两个栈实现队列

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

package test;
import java.util.Stack;
public class QueueStack {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

    /**
     * 当入栈的时候,将它全放进栈1中
     * @param node
     */
    public void push(int node) {
        stack1.push(node);
    }
    /**
     * 当需要出栈的时候,将栈1出栈到栈2中,然后再将栈2依次出栈。
     * @return
     */
    public int pop() {
        if(stack2.empty()){
            while(!stack1.empty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }

    public static void main(String[] args){
        QueueStack queue=new QueueStack();
        queue.push(1);
        queue.push(2);
        System.out.print(queue.pop()+" ");
        System.out.print(queue.pop()+" ");
        queue.push(3);
        queue.push(4);
        queue.push(5);
        System.out.print(queue.pop()+" ");
        System.out.print(queue.pop()+" ");
        System.out.print(queue.pop()+" ");
    }
}
1 2 3 4 5 

6、旋转数组的最小数字

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

package test;
import java.util.ArrayList;

/**
 * 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。
 * 非递减数组的一个旋转{3,4,5,1,2}
 *
 */
public class ArrayDemo {
    /**
     * 时间复杂度O(n)
     */
    public static int minNumberInRotateArray(int [] array) {
        if(array.length==0){//0数组
            return 0;
        }
        for(int i=0;i<array.length-1;i++){
            if(array[i]>array[i+1]){//一般旋转情况
                return array[i+1];
            }
            if(i==array.length-2){//特殊情况,未旋转
                return array[0];
            }
        }
        return -1;
    }
    /**
     * 时间复杂度O(logn)
     */
    public static int minNumber(int[] array) {
        int low = 0 ; 
        int high = array.length - 1;  
        while(low < high){
            int mid = low + (high - low) / 2;  
            if(array[mid]>array[high]){
                low=mid+1;
            }else if(array[mid]<array[high]){
                high=mid;//不是mid-1
            }else{//相等情况, [2,1,2,2,2,2,2] 或者[2,2,2,2,2,1,2]
                high--; //无法判定在左还是在右
            }
        }
        return array[low];
    }

    public static void main(String[] args){
        int[] a={1,2,3,4,5};//未旋转情况
        int[] b={3,4,5,1,2};
        int[] c={2,1,2,2,2,2,2};
        System.out.print(minNumberInRotateArray(a)+" ");
        System.out.print(minNumberInRotateArray(b)+" ");
        System.out.print(minNumberInRotateArray(c)+" ");
        System.out.println();
        System.out.print(minNumber(a)+" ");
        System.out.print(minNumber(b)+" ");
        System.out.print(minNumber(c)+" ");

    }
}
1 1 1 
1 1 1 

7、斐波那契数列

大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项。 n<=39

public class Fib {
    public static int fibonacci(int n) {
        if(n<=0){
            return 0;
        }if(n<3){
            return 1;
        }
        int f1,f2,f=0;
        f1=f2=1;
        for(int i=3;i<=n;i++){
            f=f1+f2;
            f1=f2;
            f2=f;
        }
        return f;

    }

    public static void main(String[] args){
        System.out.println(fibonacci(39));
    }
}
63245986

8、跳台阶

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

分析:只有一阶的时候 f(1) = 1 ,只有两阶的时候可以有 f(2) = 2,只有3阶时,f(3)=3

最后一跳,跳1阶时,有f(n-1)种 最后一跳,跳2阶时,有f(n-2)种 所以f(n)=f(n-1)+f(n-2)

这是一个斐波那契数列

9、任意跳台阶

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

最后一跳,跳1阶时,有f(n-1)种 最后一跳,跳2阶时,有f(n-2)种 … 最后一跳,跳n阶时,有f(0)=1种

所以f(n)=f(n-1)+f(n-2)+..+f(0) f(n-1)=f(n-2)+f(n-3)..+f(0) 所以,f(n)=2f(n-1)

初始值 f(0)=0 f(1)=1 f(2)=2

所以,f(n)=2f(n-1)=22f(n-2)=..=2n-1f(n-(n-1))=2n-1f(1)=2n-1

10、矩形覆盖

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

public class Solution {
    public int RectCover(int target) {
        int f1=1,f2=2,f=0;
        if(target==1){
            return 1;
        }
        if(target==2){
            return 2;
        }
        for(int i=3;i<=target;i++){
            f=f1+f2;
            f1=f2;
            f2=f;
        }
        return f;
    }
}

11、二进制中1的个数

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

public class Solution {
    /**
    * 正数的二进制中1的个数
    */
    public int numberOf1(int n) {
            int count=0;
        while(n>0){
            if( (n&1) == 1){
                count++;
            }
            //右移1位,相当于n=n/2;
            n=n >> 1;
        }
        return count;
    }

   /**
    * 整数的二进制中1的个数
    */
    public int countOf1(int n){
        int count=0;
        while(n!=0){
            count++;
            //每次消耗1
            n=(n-1) & n;
        }
        return count;
    }
}

12、数值的整数次方

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

import java.math.BigDecimal;
public class Solution {
public double Power(double base, int exponent) {
        BigDecimal b=new BigDecimal(base);
        BigDecimal result=null;
        if(exponent==0){
            return 1.0;
        }else if(exponent<0){
            result=b.pow(-exponent);
            result=new BigDecimal(1).divide(result);
        }else{
            result=b.pow(exponent);
        }
        return result.doubleValue();
  }
}

13、调整数组顺序使奇数位于偶数前面

输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。

package test;

public class ArrayDemo {
    //利用插排的思想就好了,是奇数就前移。
    public void reOrderArray(int [] array) {
        int tmp=0;
        //i指向当前元素,j指向已经查找到的最后一个奇数
        for(int i=0,j=-1;i<array.length;i++){
            if(array[i]%2==1){//奇数插入
                tmp=array[i];
                for(int k=i;k>j+1;k--){
                    array[k]=array[k-1];
                }
                array[++j]=tmp;
            }
        }
    }
}

14、链表中倒数第k个结点

输入一个链表,输出该链表中倒数第k个结点。

两个指针,先让第一个指针和第二个指针都指向头结点,然后再让第一个指正走(k-1)步,到达第k个节点。然后两个指针同时往后移动,当第一个结点到达末尾的时候,第二个结点所在位置就是倒数第k个节点了。

public class Solution {
    public static ListNode FindKthToTail(ListNode head,int k) {
        ListNode p,q;
        p=q=head;
        if(head==null||k<=0){
            return null;
        }
        for(int i=0;i<k-1;i++){
            if(p.next!=null){
                p=p.next;   
            }else{
                return null;
            }
        }
        while(p.next!=null){
            p=p.next;
            q=q.next;
        }
        return q;
    }
}

15、合并两个排序的链表

输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        //合并后的链表表头
        ListNode head,p;
        //p1和p2分别指向两个链表
        ListNode p1=list1,p2=list2;
        if(list1!=null){
            head=list1;
            p=head;
            p1=p1.next;
        }else if(list2!=null){
            head=list2;
            p=head;
            p2=p2.next;
        }else{
            return null;
        }

        while(p1!=null&&p2!=null){
            if(p1.val<=p2.val){
                p.next=p1;
                p=p.next;
                p1=p1.next;
            }else{
                p.next=p2;
                p=p.next;
                p2=p2.next;
            }
        }
        if(p1!=null){
            p.next=p1;
        }
        if(p2!=null){
            p.next=p2;
        }
        return head;

    }
}

16、树的子结构

输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)

public class Solution {
    /**
    * 从当前的根节点开始的子结构判定,
    */
    public static boolean isRootSubtree(TreeNode root1,TreeNode root2){
        if(root2==null){
            return true;
        }
        if(root1==null ){
            return false;
        }
        if(root1.val!=root2.val){
            return false;
        }else{
            return isRootSubtree(root1.left,root2.left) && isRootSubtree(root1.right,root2.right);
        }

    }
    public static boolean HasSubtree(TreeNode root1,TreeNode root2) {
        //空树不是任意一个树的子结构
        if(root1==null||root2==null){
            return false;
        }
        //以下情况是root1,root2均非空
        if(HasSubtree(root1.left,root2)||HasSubtree(root1.right,root2)){//root2是root1的子树的子结构
            return true;
        }else{//判定是否从根节点开始的子结构
            return isRootSubtree(root1,root2);
        }
    }
}

17、二叉树镜像

操作给定的二叉树,将其变换为源二叉树的镜像。

二叉树的镜像定义:源二叉树

源二叉树     
            8
           /  \
          6   10
         / \  / \
        5  7 9  11

镜像二叉树
            8
           /  \
          10   6
         / \  / \
        11 9 7   5
public class Solution {
    public void Mirror(TreeNode root) {
        if(root==null){
            return;
        }
        TreeNode tmp=root.left;
        root.left=root.right;
        root.right=tmp;
        Mirror(root.left);
        Mirror(root.right);
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏aCloudDeveloper

公司数据结构+算法面试100题

1.把二元查找树转变成排序的双向链表(树) 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 ...

4069
来自专栏腾讯Bugly的专栏

深入源码探索 ReactNative 通信机制

本文从源码角度剖析 ReactNative 中 Java <> Js 的通信机制(基于最新的 ReactNative for Android Release 2...

2979
来自专栏mathor

堆及其相关应用

 提到堆就不得不说到二叉树这个结构,堆就是一颗完全二叉树,什么叫完全二叉树,用一句话来概括就是:设二叉树的深度为h,除第h层外,其它各层的结点数都达到最大个数,...

772
来自专栏SeanCheney的专栏

《图解算法》总结第1章 算法简介第2章 选择排序第3章 递归第4章 快速排序第5章 散列表第6章 广度优先搜索第7章 狄克斯特拉算法第8章 贪婪算法第9章 动态规划

Grokking Algorithms: An illustrated guide for programmers and other curious peop...

3679
来自专栏苦逼的码农

从零打卡leetcode之day 2--两数相加

我靠,居然还用到了链表的知识,突然就想起了当初用c语言自学链表的那段日子,真的差点被搞死。各种指针指来指去的。

772
来自专栏JadePeng的技术博客

从编辑距离、BK树到文本纠错

搜索引擎里有一个很重要的话题,就是文本纠错,主要有两种做法,一是从词典纠错,一是分析用户搜索日志,今天我们探讨使用基于词典的方式纠错,核心思想就是基于编辑距离,...

3966
来自专栏null的专栏

挑战数据结构和算法面试题——左旋转字符串

题目来源“数据结构与算法面试题80道”。在此给出我的解法,如你有更好的解法,欢迎留言。 ? 问题分析:本题是常见的旋转字符串的问题,解决的方法是两步旋转的方法...

29310
来自专栏wym

树状数组理论基础

  树状数组(binary indexed trees,二进制索引树),最早由Peter M. Fenwick于1994年以“A New Data Struct...

562
来自专栏郭耀华‘s Blog

剑指offer 第十二天

58.对称的二叉树 请实现一个函数,用来判断一颗二叉树是不是对称的。注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的。 /* public clas...

2865
来自专栏java一日一条

前端面试中常见的算法问题总结

虽说我们很多时候前端很少有机会接触到算法。大多都交互性的操作,然而从各大公司面试来看,算法依旧是考察的一方面。实际上学习数据结构与算法对于工程师去理解和分析问题...

691

扫码关注云+社区