十道简单算法题

叁歲伎倆 2021-09-15 03:18 454阅读 0赞

# 前言 #

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

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

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

由于篇幅问题，每篇写十道吧～

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

# 十道简单算法题 #

## 题目的总览 ##

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);
    
        }

### 五、打印杨辉三角形 ###

> 杨辉三角形

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

![16274b1587562e4d_w_500_h_304_f_jpeg_s_17912][]

ps：图片来源网上，侵删～

**规律：**

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

![16274b1576ea34f9_w_891_h_602_f_jpeg_s_30083][]

代码实现：

/** * 打印杨辉三角形 */
        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" + "-------------------------------");
    
    
        }

结果：

![16274b157c8ac035_w_813_h_437_f_png_s_9033][]

### 六、猴子吃桃子问题 ###

> 猴子摘下了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;
            }

结果：

![16274b15d66247ab][]

### 七、计算单词的个数 ###

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

思路：

*  **把字符遍历一遍，累计由空格串转换为非空格串的次数，次数就是单词的个数**
 *  定义一个标志性变量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 ;
    
        }

结果：

![16274b15ee66ba81_w_1224_h_588_f_png_s_18210][]

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

> 给定两个字符串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("相同");
    
        }

结果：

![16274b15e5a35d6f_w_954_h_651_f_png_s_18368][]

### 九、判断一个数是不是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("不是");
    
            }
    
        }

结果：

![16274b1332da6e9e_w_895_h_232_f_png_s_8517][]

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

*  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("是");
    
                }
            }
        }

结果：

![16274b1332ce7beb][]

# 总结 #

没错，你没看错，简单的小算法也要总结！

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

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

举个很简单的例子：

*  乘法是在加法的基础之上的，那乘法我们是怎么学的？**背(积累)**出来的，`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**

[Link 1]: https://mp.weixin.qq.com/s?__biz=MzI4Njg5MDA5NA==&mid=2247484081&idx=1&sn=5ea6ecbcbd41c2cc0b948adf6888f60b&chksm=ebd743b0dca0caa68db0ed08a710506d60e129c8d64508c5ce1e123eafb5eaabdf35fbbed28b#rd
[16274b1587562e4d_w_500_h_304_f_jpeg_s_17912]: https://user-gold-cdn.xitu.io/2018/3/30/16274b1587562e4d?w=500&h=304&f=jpeg&s=17912
[16274b1576ea34f9_w_891_h_602_f_jpeg_s_30083]: https://user-gold-cdn.xitu.io/2018/3/30/16274b1576ea34f9?w=891&h=602&f=jpeg&s=30083
[16274b157c8ac035_w_813_h_437_f_png_s_9033]: https://user-gold-cdn.xitu.io/2018/3/30/16274b157c8ac035?w=813&h=437&f=png&s=9033
[16274b15d66247ab]: https://user-gold-cdn.xitu.io/2018/3/30/16274b15d66247ab
[16274b15ee66ba81_w_1224_h_588_f_png_s_18210]: https://user-gold-cdn.xitu.io/2018/3/30/16274b15ee66ba81?w=1224&h=588&f=png&s=18210
[16274b15e5a35d6f_w_954_h_651_f_png_s_18368]: https://user-gold-cdn.xitu.io/2018/3/30/16274b15e5a35d6f?w=954&h=651&f=png&s=18368
[16274b1332da6e9e_w_895_h_232_f_png_s_8517]: https://user-gold-cdn.xitu.io/2018/3/30/16274b1332da6e9e?w=895&h=232&f=png&s=8517
[16274b1332ce7beb]: https://user-gold-cdn.xitu.io/2018/3/30/16274b1332ce7beb