算法每日学打卡——java语言基础题目打卡(01-10)

本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer,已开源在github ,欢迎star!

转载声明:转载请注明出处,本技术博客是本人原创文章

本文GitHub https://github.com/OUYANGSIHAI/JavaInterview 已收录,这是我花了6个月总结的一线大厂Java面试总结,本人已拿大厂offer,欢迎star

原文链接:blog.ouyangsihai.cn >> 算法每日学打卡——java语言基础题目打卡(01-10)

文章有不当之处,欢迎指正,如果喜欢微信阅读,你也可以关注我的微信公众号: 好好学java,获取优质学习资源。

-

“算法每日学”计划01打卡: 问题描述 对于长度为5位的一个01串,每一位都可能是0或1,一共有32种可能。它们的前几个是: 00000 00001 00010 00011 00100 请按从小到大的顺序输出这32种01串。 输入格式 本试题没有输入。 输出格式 输出32行,按从小到大的顺序每行一个长度为5的01串。 样例输出 00000 00001 00010 00011 <以下部分省略>

解题思路与实现

如果有小伙伴很少接触到这种题目的话,可能会觉得有点陌生,不知道从何下手,可能一开始我们能想到“最笨”的方法,但是也觉得挺有“娱乐性”的方法。


System.out.println("00000")
..........
System.out.println("11111")

这种方式是不是也能够得到最后的结果,没错,当然没问题,但是,我们在思考的时候可以一步一步来,尝试多种方法,找到最优解。

这种方法看来不太好,一是不够灵活,二是敲代码很累,所以,改进一下。

image

这种方式是不是能够更加灵活的解决这个问题,这个解决的方式就是我们常说的“暴力破解”,全部用for循环来遍历所有的情况,如果找到符合的情况就输出,但是我们会发现,这个算法的时间复杂度是: O(n^5),这个方法比前一种方法更好了,但是还不是最好的答案。


public static void main(String[] args) {
        for (int i = 0; i &lt; 32; i++) {
            String result = Integer.toBinaryString(i);
            int num = result.length();
                for (int j = 0; j &lt; 5 - num; j++) {
                    result = "0" + result;
                }
                System.out.println(result);

    }

}

再来看看这种方法,这种方法的思路:通过jdk的方法 Integer.toBinaryString()获取到每个数字的二进制,因为要求输出的是形如 “11111”的五位数字,所以,我们还需要根据得到的二进制的数字的长度,在这个字符串的前面加上 5 - num “0”,比如,得到的二进制是 1(长度为1),所以在 1的前面要加上 5-(num=1)等于4个 0

是不是特别的简洁,而且这种方法的效率应该也是不错的: O(n),因为这个是jdk提供的方法,在底层是用位移的方法来实现的(注:我们不推荐用jdk的方法来解决,我们尽量用自己思考的方法来解决,就算这个方法“笨”,但是也是自己思考了)。

当然,如果我们换个角度,也可以的到另一种解法。


 public static void main(String args[]){ 
        for(int i=0;i&lt;32;i++){ 
            String str = Integer.toBinaryString(i); 
            switch (str.length()) { 
            case 1: 
                str = "0000"+str; 
                break; 
            case 2: 
                str = "000"+str;
                break;
            case 3:
                str = "00"+str;
                break;
            case 4:
                str = "0"+str;
                break;
            }
                System.out.println(str);

        }
    }
}

这种解法只是用switch-case的方式来解决而已,思路和上面一样。

“算法每日学”计划02打卡: 问题描述   十六进制数是在程序设计时经常要使用到的一种整数的表示方式。它有0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F共16个符号,分别表示十进制数的0至15。十六进制的计数方法是满16进1,所以十进制数16在十六进制中是10,而十进制的17在十六进制中是11,以此类推,十进制的30在十六进制中是1E。   给出一个非负整数,将它表示成十六进制的形式。 输入格式   输入包含一个非负整数a,表示要转换的数。0<=a<=2147483647 输出格式   输出这个整数的16进制表示 样例输入 30 样例输出 1E


import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Integer n = in.nextInt();
        in.close();
        System.out.println(Integer.toHexString(n).toUpperCase());
    }
}

上面是api,下面看看其他:

这道题本身是没什么难度的,只要用递归处理,当输入的数字大于等于16时,则递归处理该数整除16的值,然后再输出最后一位即可。

但是,我在做的时候,一开始没有考虑到整除16后的值大于9的情况和整除16的次数大于9的情况,结,如下图 这里写图片描述

以后要注意考虑全方面和一定要注意数据范围!


import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int a=sc.nextInt();
        int[] b=new int[8];            
//数组b的元素个数由a决定,由于a&lt;=2^32,即a&lt;=16^8
        char[] s={<!-- -->'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
        if(a&gt;=0&amp;&amp;a&lt;16){
            for(int i=0;i&lt;16;i++){

                int m=a%16;
                if(m==i)
                        System.out.println(s[i]);
                    }
            }
        else{
            int i=0;
            while(a!=0){
                b[i]=a%16;
            a=a/16;
                i++;
            }

        for(int j=i-1;j&gt;=0;j--){
            if(b[j]==10)
                System.out.print("A");
            else if(b[j]==11)
                System.out.print("B");
            else if(b[j]==12)
                System.out.print("C");
            else if(b[j]==13)
                System.out.print("D");
            else if(b[j]==14)
                System.out.print("E");
            else if(b[j]==15)
                System.out.print("F");
            else
                System.out.print(b[j]);
        }
        }
        }
}

“算法每日学”计划03打卡: 问题描述   数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。   例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。 输入格式   每个测试案例包括2行:   第一行输入一个整数n(1<=n<=100000),表示数组中元素的个数。   第二行输入n个整数,表示数组中的每个元素,这n个整数的范围是[1,1000000000]。 输出格式   对应每个测试案例,输出出现的次数超过数组长度的一半的数,如果没有输出-1。 样例输入 9 1 2 3 2 2 2 5 4 2 9 1 1 1 2 2 2 3 3 3 样例输出 2 -1


    /**
     * 数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。
     * 例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。
     * 由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。
     */
    public int findMoreThanHalfNum(int[] numbers) {
        int length = numbers.length;
        if (length == 0) return 0;

        int num = numbers[0], count = 1;
        for (int i = 1; i &lt; length; i++) {
            if (numbers[i] == num) count++;
            else count--;
            if (count == 0) {
                num = numbers[i];
                count = 1;
            }
        }
        // Verifying
        count = 0;
        for (int i = 0; i &lt; length; i++) {
            if (numbers[i] == num) count++;
        }
        if (count * 2 &gt; length) return num;
        return 0;
    }

“算法每日学”计划04打卡: 问题描述     在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。   请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。 输入  输入可能包含多个测试样例,对于每个测试案例,   输入的第一行为两个整数m和n(1<=m,n<=1000):代表将要输入的矩阵的行数和列数。   输入的第二行包括一个整数t(1<=t<=1000000):代表要查找的数字。   接下来的m行,每行有n个数,代表题目所给出的m行n列的矩阵(矩阵如题目描述所示,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。 输出 对应每个测试案例,   输出”Yes”代表在二维数组中找到了数字t。   输出”No”代表在二维数组中没有找到数字t。 样例输入 3 3 5 1 2 3 4 5 6 7 8 9 3 3 1 2 3 4 5 6 7 8 9 10 样例输出 YES NO


public class Main {
       public boolean Find(int target, int [][] array) {
       int rowCount = array.length;//获取数据的行数
       int colCount = array[0].length; //获取数据的列数
       int i,j;
       i=rowCount-1;
       j=0;

      while((i &gt;=0 )&amp;&amp;(j&lt;colCount)) {
           if (target == array[i][j]) {
                    return true;    
                    }
           else if (target&lt;array[i][j]) {
                i--;
           }else {
               j++;
           } 
       }       
        return false;   
       }
}

“算法每日学”计划05打卡: 问题描述     理论知识学习,算法基础,理解时间复杂度,理解空间复杂度。 输入  无 输出 无      查看相关资料
“算法每日学计划”06打卡: 问题描述   给定一个长度为n的数列,将这个数列按从小到大的顺序排列。1<=n<=200 输入格式   第一行为一个整数n。   第二行包含n个整数,为待排序的数,每个整数的绝对值小于10000。 输出格式   输出一行,按从小到大的顺序输出排序后的数列。 样例输入 5 8 3 6 4 9 样例输出 3 4 6 8 9 注:题目简单,解法不少于10种,踊跃发言。

查看相关排序算法,公众号将逐步更新排序算法。

“算法每日学计划”07打卡: 问题描述   求出区间[a,b]中所有整数的质因数分解。 输入格式   输入两个整数a,b。 输出格式   每行输出一个数的分解,形如k=a1a2a3…(a1<=a2<=a3…,k也是从小到大的)(具体可看样例) 样例输入 3 10 样例输出 3=3 4=22 5=5 6=23 7=7 8=222 9=33 10=25 提示   先筛出所有素数,然后再分解。 数据规模和约定 2<=a<=b<=10000


import java.util.Scanner;

public class Main {<!-- -->

    /**
     * (1)如果这个质数恰等于n,则说明分解质因数的过程已经结束,打印出即可。
     * (2)如果n&gt;k,但n能被k整除,则应打印出k的值,并用n除以k的商作为新的正整数n,重复执行第一步。
     * (3)如果n不能被k整除,则用k+1作为k的值,重复执行第一步。
     * 
     * @param joy
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Integer a = sc.nextInt();
        Integer b = sc.nextInt();
        for (int i = a; i &lt;= b; i++) {
            // 输入值大于等于3
            if (i &gt;= 3) {
                String m = "";
                int k = 2;
                int j = i;
                while (j != k) {
                    // 如果n&gt;k,但n能被k整除,则应打印出k的值,并用n除以k的商作为新的正整数n
                    if (j % k == 0) {
                        m = m + k + "*";
                        j = j / k;
                    }
                    // 如果n不能被k整除,则用k+1作为k的值
                    else if (j % k != 0) {
                        k++;
                    }
                }
                m = m + k;
                System.out.println(i + "=" + m);
            } else {
                System.out.println(i + "=" + i);
            }
        }
    }
}

“算法每日学计划”08打卡: 问题描述   给定两个仅由大写字母或小写字母组成的字符串(长度介于1到10之间),它们之间的关 系是以下4中情况之一:   1:两个字符串长度不等。比如 Beijing 和 Hebei   2:两个字符串不仅长度相等,而且相应位置上的字符完全一致(区分大小写),比如 Beijing 和 Beijing   3:两个字符串长度相等,相应位置上的字符仅在不区分大小写的前提下才能达到完 全一致(也就是说,它并不满足情况2)。比如 beijing 和 BEIjing   4:两个字符串长度相等,但是即使是不区分大小写也不能使这两个字符串一致。比 如 Beijing 和 Nanjing   编程判断输入的两个字符串之间的关系属于这四类中的哪一类,给出所属的类的编号 。 输入格式   包括两行,每行都是一个字符串 输出格式   仅有一个数字,表明这两个字符串的关系编号 样例输入 BEIjing beiJing 样例输出 3 注意:简单题目


public class Main {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
    Scanner input=new Scanner(System.in);
    String str1=input.nextLine();
    String str2=input.nextLine();
    if(str1.length()!=str2.length()){System.out.println(1);}
    else{
    if(str1.equals(str2)){System.out.println(2);}
    if(str1.toLowerCase().equals(str2.toLowerCase())){System.out.println(3);}
    else{System.out.println(4);}
    }
    }

}

“算法每日学计划”09打卡: 问题描述   给定一个N阶矩阵A,输出A的M次幂(M是非负整数)   例如:   A =   1 2   3 4   A的2次幂   7 10   15 22 输入格式   第一行是一个正整数N、M(1<=N<=30, 0<=M<=5),表示矩阵A的阶数和要求的幂数   接下来N行,每行N个绝对值不超过10的非负整数,描述矩阵A的值 输出格式   输出共N行,每行N个整数,表示A的M次幂所对应的矩阵。相邻的数之间用一个空格 隔开 样例输入 2 2 1 2 3 4 样例输出 7 10 15 22


public class Main {<!-- -->
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        Integer[][] a = new Integer[n][n];
        Integer[][] result = new Integer[n][n];  //保存结果
        for(int i=0;i &lt; n;i ++){
            for(int j=0;j &lt; n;j ++)
                a[i][j] = scanner.nextInt();
        }
        result = a;
        for(int i = 1;i &lt; m;i++)
            result = multiplyMaritx(result, a);

        printMaritx(result);
    }

    /**
     * 打印二维数组
     * @param a
     */
    public static void printMaritx(Integer[][] a){
        for(int i = 0;i &lt; a.length;i ++){
            for(int j = 0;j &lt; a[i].length;j ++)
                System.out.print(a[i][j] + " ");
            System.out.println();
        }
    }

    /**
     * 两个同阶矩阵相乘,返回结果。
     * @param a 第一个矩阵
     * @param b 第二个矩阵
     * @return 相乘的结果
     */
    public static Integer[][] multiplyMaritx(Integer[][] a,Integer[][] b){
        int n = a.length;
        Integer[][] result = new Integer[n][n];  //保存结果
        for(int i = 0;i &lt; n;i ++){
            //遍历二位数组a的行
            for(int j = 0;j &lt; n;j++){
                //遍历二位数组b的列
                Integer c = new Integer(0);
                for(int k = 0;k &lt; n;k ++)
                     //第i行j列的值为a的第i行上的n个数和b的第j列上的n个数对应相乘之和,
                    //其中n为a的列数,也是b的行数,a的列数和b的行数相等
                    c += a[i][k] * b[k][j];
                result[i][j] = c;
            }
        }

        return result;
    }

}

“算法每日学计划”10打卡: 问题描述 亚洲微软研究院所在的希格玛大厦一共有6部电梯。在高峰时间,每层都有人上下,电梯在每层都停。实习生小飞常常会被每层都停的电梯弄得很不耐烦,于是他提出了这样一个办法: 由于楼层并不算太高,那么在繁忙的上下班时间,每次电梯从一层往上走时,我们只允许电梯停在其中的某一层。所有乘客从一楼上电梯,到达某层后,电梯停下来,所有乘客再从这里爬楼梯到自己的目的层。在一楼的时候,每个乘客选择自己的目的层,电梯则自动计算出应停的楼层。 问:电梯停在哪一层楼,能够保证这次乘坐电梯的所有乘客爬楼梯的层数之和最少。 问题分析 该问题本质上是一个优化问题。   首先为这个问题找到一个合适的抽象模型。 有两个因素会影响结果:乘客的数目和乘客的目的楼层。

思路:假设电梯现在停在第i层,i层以下的人有N1个,i层有N2个,i层以上的人有N3个,当前需要走的楼梯数为Y。当电梯再往上走一层时,i层及i层以下的人一共需要多走N1+N2步,而i层以上的人则一共少走了N3步,所以当N1+N2时,电梯应该继续往上走。

Java代码:


public class Main {
    public static int stopLift(int[] to) {
        if (to.length &lt; 2) {
            return -1;
        }
        int n1 = 0, n2 = to[1], n3= 0, y = 0;
        // 计算一层及以上的人数
        for (int i = 1; i &lt; to.length; i++) {
            n3 += to[i];
            y += (i - 1) * to[i];
        }

        for(int i = 1; i &lt; to.length; i++) {
            n2 = to[i];
            n1 += to[i - 1];
            n3 = n3 - n2;
            if (n1 + n2 &gt;= n3) {
                return i;
            }
        }
        return -1;
    }


    public static void main(String[] args) {

        int[] to = {<!-- -->0, 1, 2 ,3 ,5 ,6, 7};
        System.out.format("电梯应该停在第%d层。", stopLift(to));

    }
}

原文地址:https://sihai.blog.csdn.net/article/details/80809617

本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer,已开源在github ,欢迎star!

转载声明:转载请注明出处,本技术博客是本人原创文章

本文GitHub https://github.com/OUYANGSIHAI/JavaInterview 已收录,这是我花了6个月总结的一线大厂Java面试总结,本人已拿大厂offer,欢迎star

原文链接:blog.ouyangsihai.cn >> 算法每日学打卡——java语言基础题目打卡(01-10)


 上一篇
“面试不败计划”——集合、日期、异常、序列化、其他知识点 “面试不败计划”——集合、日期、异常、序列化、其他知识点
点击上方“好好学java”,选择“置顶公众号” 优秀学习资源、干货第一时间送达! 好好学java java知识分享/学习资源免费分享 关注  精彩内容  关于集合 思考题:1、Java中的集合及其继承关系
2021-04-04
下一篇 
java实现支付宝支付完整过程(沙箱测试环境,下篇整合ssm) java实现支付宝支付完整过程(沙箱测试环境,下篇整合ssm)
点击上方“好好学java”,选择“置顶公众号” 优秀学习资源、干货第一时间送达! 好好学java java知识分享/学习资源免费分享 关注  精彩内容  源代码https://github.com/OUYANGS
2021-04-04