欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

十道简单算法题

程序员文章站 2022-11-02 12:46:40
前言 最近在回顾以前使用C写过的数据结构和算法的东西,发现自己的算法和数据结构是真的薄弱,现在用Java改写一下,重温一下。 只能说慢慢积累吧~下面的题目难度都是简单的,算法的大佬可直接忽略这篇文章了~入门或者算法薄弱的同学可参考一下~ 很多与排序相关的小算法(合并数组、获取数字每位值的和),我都没 ......

前言

最近在回顾以前使用C写过的数据结构和算法的东西,发现自己的算法和数据结构是真的薄弱,现在用Java改写一下,重温一下。

只能说慢慢积累吧~下面的题目难度都是简单的,算法的大佬可直接忽略这篇文章了~入门或者算法薄弱的同学可参考一下~

很多与排序相关的小算法(合并数组、获取数字每位值的和),我都没有写下来了,因为只要会了归并排序(合并数组),会了桶排序(获取数字每位的值),这些都不成问题了。如果还不太熟悉八大基础排序的同学可看:【八大基础排序总结

由于篇幅问题,每篇写十道吧~

如果有错的地方,或者有更好的实现,更恰当的理解方式希望大家不吝在评论区留言哦~大家多多交流

十道简单算法题

题目的总览

  1. 1-n阶乘之和
  2. 获取二维数组每列最小的值
  3. 求"1!+4!(2的平方)+9!(3的平方)+...+n的值
  4. 数组对角线元素之和
  5. 打印杨辉三角形
  6. 猴子吃桃子问题
  7. 计算单词的个数
  8. 判断字母是否完全一样
  9. 判断一个数是不是2的某次方
  10. 判断一个数字是不是ugly number

一、1-n阶乘之和

1-n阶乘之和怎么算?

  • 1的阶乘是1
  • 2的阶乘是1*2
  • 3的阶乘是1*2*3
  • 4的阶乘是1*2*3*4
  • .........

现在我们要求这些阶乘的和。思路:

  • 3阶乘的和其实上就是2阶乘的和+3的阶乘
  • 4阶乘的和其实上就是3阶乘的和+4的阶乘
  • .......

    /**
     * 1-n的阶乘之和
     */
    public static void Factorial(int n) {

        //总和
        double sum = 0;

        //阶乘值,初始化为1
        double factorial = 1;

        for (int i = 1; i <= n; i++) {

            factorial = factorial * i;


            sum = (int) (sum + factorial);

        }

        System.out.println("公众号:Java3y" + "     " + sum);

    }

二、获取二维数组每列最小的值

获取二维数组每列最小的值

思路:遍历列,再遍历列中行

我们一般操作数组都是从行开始,再到列的。这次要求的是每列的最小值,因此需要在内部for循环遍历的是行

    /**
     * 求出二维数组每列的最小值
     */
    public static void minArray() {


        //二维数组
        int[][] arrays = {
            {23, 106, 8, 234},
            {25, 9, 73, 19},
            {56, 25, 67, 137}
        };


        //获取列数
        int maxColLength = arrays[0].length;



        //使用一个数组来装载每列最小的值
        int[] minArray = new int[maxColLength];


        //控制列数
        for (int i = 0; i < maxColLength; i++) {

            //假设每列的第一个元素是最小的
            int min = arrays[0][i];

            //控制行数
            for (int j = 1; j < arrays.length; j++) {


                //找到最小值
                if (arrays[j][i] < min) {
                    min = arrays[j][i];
                }
            }

            //赋值给装载每列最小的值的数组
            minArray[i] = min;
        }


        System.out.println("公众号:Java3y" + "     " + minArray);

    }

三、求"1!+4!(2的平方)+9!(3的平方)+...+n的值

求"1!+4!(2的平方)+9!(3的平方)的值

思路:先求平方,后求阶乘,最后相加即可~


    /**
     * 求"1!+4!(2的平方)+9!(3的平方)+...+n的值
     */
    public static void calculate() {

        double sum = 0;

        for (int i = 1; i <= 3; i++) {

            //得到平方数
            int square = i * i;

            //阶乘值,从1开始
            double factorial = 1;

            //求阶乘
            for (int j = 1; j <= square; j++) {
                factorial = factorial * j;
            }

            sum = sum + factorial;

        }

        System.out.println("公众号:Java3y" + "     " + sum);
        
    }

四、数组对角线元素之和

数组对角线元素之和

思路:

  • 只要行和列相等,即是对角线的元素
    /**
     * 数组对角线之和
     */
    public static void arraySum() {

        int[][] arrays = {
                {23, 106, 8, 234},
                {25, 9, 73, 19},
                {56, 25, 67, 137},
                {33, 22, 11, 44},
        };

        //和
        int sum = 0;

        for (int i = 0; i < arrays.length; i++) {

            for (int j = 0; j < arrays[i].length; j++) {

                if (i == j) {

                    sum = sum + arrays[i][j];

                }
            }
        }


        System.out.println("公众号:Java3y" + sum);
        
    }

五、打印杨辉三角形

杨辉三角形

杨辉三角形长的是这个样子:

十道简单算法题

ps:图片来源网上,侵删~

规律:

  • 每行的第一个和最后一个都是1
    • 进一步推算:第1列全部为1,第一行全都是1,当列数等于行数为1
  • 当前值等于头上的值加头上的左边的值
  • 第一行一列,第二行两列,第三行三列.......

十道简单算法题

代码实现:

    /**
     * 打印杨辉三角形
     */
    public static void PascalTriangle() {


        //打印十行的杨辉三角形
        int[][] arrays = new int[10][];


        //行数
        for (int i = 0; i < arrays.length; i++) {


            //初始化第二层的大小
            arrays[i] = new int[i + 1];

            //列数
            for (int j = 0; j <= i; j++) {

                //是第一列,第一行,行数等于列数,那么通通为1
                if (i == 0 || j == 0 || j == i) {
                    arrays[i][j] = 1;
                } else {

                    //当前值等于头上的值+头上左边的值
                    arrays[i][j] = arrays[i - 1][j] + arrays[i - 1][j - 1];
                }

            }
        }

        System.out.println("公众号:Java3y" + "-------------------------------");

        for (int[] array : arrays) {
            for (int value : array) {
                System.out.print(value + "\t");
            }
            System.out.println();

        }


        System.out.println("公众号:Java3y" + "-------------------------------");


    }

结果:

十道简单算法题

六、猴子吃桃子问题

猴子摘下了n个桃子,当天吃掉一半多一个,第二天也是吃掉剩下桃子的一半多一个,到了第十天,桃子只剩下了1个。问:猴子第一天摘了多少个桃子

思路:

  • 假设当天有n个桃子,它是前一天桃子的一半少1个,f(n - 1) = f(n)/2 - 1,
  • 我们就可以推出当天桃子的个数:根据递推公式:f(n) = 2 * f(n - 1) + 2

用递归和循环都可解决:

递归方式:

    /**
     * 猴子吃桃问题
     * @param x 天数
     */
    public static int monkeyQue(int x) {

        if (x <= 0) {
            return 0;

        } else if (x == 1) {
            return 1;

        } else {
            return 2 * monkeyQue(x - 1) + 2;
        }

    }

循环方式:

        int x = 1;
        for (int i = 1; i <= 9; i++) {
            x = (x + 1) * 2;
        }

结果:

十道简单算法题

七、计算单词的个数

输入一段字符,计算出里面单词的个数,单词之间用空格隔开 ,一个空格隔开,就代表着一个单词了

思路:

  • 把字符遍历一遍,累计由空格串转换为非空格串的次数,次数就是单词的个数
  • 定义一个标志性变量flag,0表示的是空格状态,1表示的是非空格状态
    /**
     * 输入一段字符,计算出里面单词的个数
     *
     * @param str 一段文字
     */
    public static int countWord(String str) {


        // 0 表示空格状态,1 表示非空格状态
        int flag = 0;

        // 单词次数
        int num = 0;


        for (int i = 0; i < str.length(); i++) {

            if (String.valueOf(str.charAt(i)).equals(" ") ) {
                flag = 0;
            } else if (flag == 0) {
                num++;
                flag = 1;
            }

        }

        return num ;

    }

结果:

十道简单算法题

八、判断字母是否完全一样

给定两个字符串s和t,判断这两个字符串中的字母是不是完全一样(顺序可以不一样)

思路:

  • 遍历这两个字符串,用每个字符减去'a',将其分别存入到数组中去,随后看这两个数组是否相等即可

要点:

  • 'c'-'a'=2即可计算出存储的位置,如果有多个,则+1即可,后面我们来比较数组大小

代码实现:



    /**
     * 给定两个字符串s和t,判断这两个字符串中的字母是不是完全一样(顺序可以不一样) 
     */
    public static void isAnagram() {

        //分别存储字符串的字符
        char[] array1 = new char[26];
        char[] array2 = new char[26];


        String s1 = "pleasefollowthewechatpublicnumber";
        String s2 = "pleowcnumberthewechatpubliasefoll";


        for (int i = 0; i < s1.length(); i++) {
            char value = s1.charAt(i);

            // 算出要存储的位置
            int index = value - 'a';

            array1[index]++;
        }

        for (int i = 0; i < s2.length(); i++) {
            char value = s2.charAt(i);

            // 算出要存储的位置
            int index = value - 'a';

            array2[index]++;
        }

        for (int i = 0; i < 26; i++) {
            if (array1[i] != array2[i]) {
                System.out.println("不相同");
                return;
            }
        }

        System.out.println("相同");

    }

结果:

十道简单算法题

九、判断一个数是不是2的某次方

判断一个数是不是2的某次方

思路:

  • 除2取余数,直至余数不为0【针对2的倍数这种情况】,看是不是等于1就可以判断是不是2的某次方了
    /**
     * 判断是否是2的某次方
     */
    public static void isPowerOfTwo() {

        int num = 3;

        if (num == 0) {
            System.out.println("不是");
        }

        while (num % 2 == 0) {
            num = num / 2;
        }

        if (num == 1) {
            System.out.println("是");
        } else {
            System.out.println("不是");

        }

    }

结果:

十道简单算法题

这题还有另一种解决方式,就是位运算:

  • 2的n次方都有一个特点,二进制都是1000000
  • 如果 2的n次方的二进制-1和2的n次方二进制做按位与运算,那么得出的结果肯定是0
    if(num <= 0){
        System.out.println("不是");
    }
    else if(num == 1){
        System.out.println("是");
    }
    else{
        if( (num & (num-1) ) == 0){
            System.out.println("是");
        }
        else{
            System.out.println("不是");
        }
    }

十、判断一个数字是不是ugly number

判断一个数字是不是ugly number(分解出来的质因数只有2、3、5这3个数字)

思路:

  • 如果是由2,3,5组成的,那么这个数不断除以2,3,5,最后得出的是1,这个数就是纯粹用2,3,5组成的
    • 跟之前判断该数是否2的某次方是一样的思路~

代码:

    /**
     * 判断一个数字是不是ugly number(分解出来的质因数只有2、3、5这3个数字)
     * @param num
     */
    public static void isUgly(int num) {
        if (num <= 0) {
            System.out.println("不是");
        } else {
            while (num % 2 == 0) {
                num = num / 2;
            }
            while (num % 3 == 0) {
                num = num / 3;
            }
            while (num % 5 == 0) {
                num = num / 5;
            }
            if (num == 1) {
                System.out.println("是");

            } else {
                System.out.println("是");

            }
        }
    }

结果:

十道简单算法题

总结

没错,你没看错,简单的小算法也要总结!

其实我觉得这些比较简单的算法是有"套路"可言的,你如果知道它的套路,你就很容易想得出来,如果你不知道它的套路,那么很可能就不会做了(没思路)。

积累了一定的"套路"以后,我们就可以根据经验来推断,揣摩算法题怎么做了。

举个很简单的例子:

  • 乘法是在加法的基础之上的,那乘法我们是怎么学的?背(积累)出来的,9*9乘法表谁没背过?比如看到2+2+2+2+2,会了乘法(套路)以后,谁还会慢慢加上去。看见了5个2,就直接得出2*5

  1. 1-n阶乘之和
    • 求n的阶乘就用1*2*3*4*...n,实际上就是一个循环的过程,求和就套个sum变量即可!
  2. 获取二维数组每列最小的值
    • 外层循环控制列数,内层循环控制行数,这就是遍历每列的方法~
  3. 求"1!+4!(2的平方)+9!(3的平方)+...+n的值
    • 先求平方,再求阶乘,最后套个sum变量
  4. 数组对角线元素之和
    • 行和列的位置相等,即是对角线上的元素
  5. 打印杨辉三角形
    • 找出杨辉三角形的规律:第一行、第一列和列值等于行值时上的元素都是1,其余的都是头上的值加头上的左边的值
  6. 猴子吃桃子问题
    • 根据条件,我们可以推算出前一天桃子,进而推出当天桃子(规律)。猴子都是在相等的条件(剩下桃子的一半多一个),因此就应该想到循环或者递归
  7. 计算单词的个数
    • 利用每个单词间会有个空格的规律,用变量来记住这个状态(字母与空格)的转换,即可计算出单词的个数!
  8. 判断字母是否完全一样
    • 将每个字母都分别装载到数组里面去,'c-a'就是字母c数组的位置了(也就是2)。由于字母出现的次数不唯一,因此我们比较的是数组的值(如果出现了两次,那么值为2,如果出现了3次,那么值为3)。只要用于装载两个数组的值都吻合,那么字母就是一样!
  9. 判断一个数是不是2的某次方
    • 最佳方案:2的某次方在二进制都有个特点:10000(n个0)--->ps:程序员的整数~..........那么比这个数少一位的二进制肯定是01111,它俩做&运算,那么肯定为0。用这个特性就非常好判断该数是否是2的某次方了
    • 次方案:2的某次方的数不断缩小(只要number % 2 == 0就可以缩小,每次number / 2),最后的商必然是1。
  10. 判断一个数字是不是ugly number
    • 分解出来的质因数只有2、3、5这3个数字,这题其实就是判断该数是否为2的某次方的升级版。将这个数不断缩小(只要number%2||%3||%5==0,每次number / 2 | / 3 /5),最后的商必然是1

如果文章有错的地方欢迎指正,大家互相交流。习惯在微信看技术文章,想要获取更多的Java资源的同学,可以关注微信公众号:Java3y