JAVA语言之10道简单算法题
白羽 2018-07-09 来源 :网络 阅读 18 评论 0

摘要:本文将带你了解JAVA语言之10道简单算法题,希望本文对大家学JAVA有所帮助。




题目的总览

1. 删除下标为k的元素

2. 找出常用的数字

3. 丢失的数字

4. 将0放在数组最后

5. 找出数组的单个数字

6. 画三角形星星

7. 罗马数字倒转成阿拉伯数字

8. 啤酒与饮料

9. 简单凯撒密码

10. 求最大公约数

一、删除下标为k的元素

删除下标为k的元素

思路:数组后一位往前覆盖即可~

 

 

    /**

     * 删除下标为k的元素

     */

    public static void deleteK() {

 

 

        //固定的常量(比数组元素的个数要大)

        int N = 10;

 

        int[] arrays = new int[N];

 

        //对数组进行初始化

        for (int i = 0; i < 8; i++) {

            arrays[i] = i;

        }

 

 

        //要删除下标

        int k = 7;

 

        for (int i = k; i < N - 1; i++) {

            arrays[i] = arrays[i + 1];

        }

 

 

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

 

 

    }

二、找出常用的数字

给你一个长度为n的数组,其中有一个数字出现的次数至少为n/2,找出这个数字

这道题可以用栈的思想来做:

· 如果栈是空的,那么先把数据存进去

· 然后继续遍历其他的数据,只要发现栈中的数据和遍历中的数据不一样,那么就出栈

· 如果是相同的,那么就入栈

· 其实就是捉住数字出现的次数多于数组一半的长度这里入手。如果这个数出现的次数是大于这个数组长度的2/1,那么最后留下的肯定是这个数

1

 

    /**

     * 找出常用的数字:

     * 给你一个长度为n的数组,其中有一个数字出现的次数至少为n/2,找出这个数字

     */

 

    public static void findMajorityElement(int[] arrays) {

 

 

        //构建一个静态栈

        int[] stack = new int[arrays.length];

 

        // 栈的front指针

        int front = -1;

 

 

        // 遍历给出的数组

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

 

 

            // 判断该栈为空,那么直接将元素入栈

            if (front == -1) {

                stack[++front] = arrays[i];

            } else if (stack[front] == arrays[i]) { // 该元素是否与栈的元素一致-->继续入栈

 

                stack[++front] = arrays[i];

            } else {

                // 只要不一致,就出栈

                front--;

 

            }

        }

 

        // 只要该数字出现次数大于数组长度的2/1,那么留下来的数字肯定在栈顶中

        System.out.println("关注公众号:Java3y--->" + stack[0]);

    }

优化:

· 其实没必要用整个栈来装载数组,因为我们就使用栈顶元素(出现次数最多的那个),而栈的大小也可以通过一个变量就可以来确定了

· 只要元素相同->入栈(长度+1)。元素不相同-->出栈(长度-1)

· 最终留下来的肯定是出现最频繁的那个数字!

 

 

    public static void findMajorityElement2(int[] arrays) {

 

        // 装载栈的元素

        int candidate = -1;

 

        // 栈的大小(长度)

        int count = 0;

 

 

        // 遍历给出的数组

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

 

 

            // 判断该栈为空,那么直接将元素入栈

            if (count == 0) {

 

                candidate = arrays[i];

                count++;

 

            } else if (candidate == arrays[i]) { // 该元素是否与栈的元素一致-->入栈(栈多一个元素)

                count++;

            } else {

                // 只要不一致-->出栈(栈少一个元素)

                count--;

 

            }

        }

 

        // 只要该数字出现次数大于数组长度的2/1,那么留下来的数字肯定在栈顶中

        System.out.println("关注公众号:Java3y--->" + candidate);

 

    }

三、丢失的数字

给你一个数组{0,1,2,3,....n},其中有一个数字缺失,请把缺失的数字找出来

思路:

· 创建一个数组(题目数组的长度+1,因为题目的数组缺失了一个)

· 创建的数组元素用特殊的符号(数字)来进行填满

· 将题目给出的数组遍历并填充到创建的数组上,用index(0,1,2,3..)替代

· 最后遍历创建的数组,哪个还是特殊的符号就是缺失的数字,返回index(缺失的数字)即可

 

    /**

     * 找到缺失的数字

     *

     * @param arrays

     */

    public static void missingNumber(int[] arrays) {

 

 

        // 定义要填充到新数组的数字(随意)

        int randomNumber = 89898980;

 

 

        // 创建一个新的数组(比已缺失的数组多一个长度)

        int[] newArrays = new int[arrays.length + 1];

 

        // 填充特殊的数字进新数组中

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

 

            // 随意填充数组到新数组中

            newArrays[i] = randomNumber;

        }

 

        // 遍历题目的数组并使用index替代掉新数组的元素

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

 

            // 题目数组的值[0,1,2,3,4,...n]其中有一个缺失

            int index = arrays[i];

 

            // 重新填充到新数组上,index对应着题目数组的值

            newArrays[index] = 3333333;

            

        }

 

        // 遍历新数组,只要还有值为89898980,那么那个就是缺失的数字

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

 

 

            if (newArrays[i] == randomNumber) {

 

                System.out.println("关注公众号:Java3y---->缺失的数字是:" + i);

 

            }

 

 

        }

 

 

    }

结果:

2

优化:

· 题目给出的数组{0,1,2,3,4,5,....n}其中缺失一个数字,要把缺失的数字找出来...我们可以回顾一下高中学过的等差求和公式:Sn=(a1+an)n/2

· 3

· 假设我们没有缺失数字,等差求和公式可以快速得出答案。比如:{0,1,2,3}--->(0+3)*4/2--->6,如果此时缺失的是2呢,就是说题目的给出的数组是:{0,1,3},我们利用等差公式求和之后减去数组每个元素,最后剩下的数就是缺失的数字!6-1-3-0--->2

所以,我们可以写出这样的代码:

    /**

     * 利用等差公式找到缺失的数字

     *

     * @param arrays

     */

    public static void missingNumber2(int[] arrays) {

 

        // 套用等差求和公式

        int sum = (arrays[0] + arrays[arrays.length - 1]) * (arrays.length + 1) / 2;

 

 

        // 遍历数组,得出的sum减去数组每一位元素,最后即是缺失的数字

 

        for (int value : arrays) {

            sum = sum - value;

        }

 

 

        System.out.println("关注公众号:Java3y---->缺失的数字是:" + sum);

 

 

    }

结果:

4

四、将0放在数组最后

将一个数组的元素,其中是0的,放在数组的最后

思路:

· 使用一个变量zero来记住该数组有多少个0

· 遍历这个数组,如果发现不是0的,就往数组前面移动,如果发现是0就zero++

· 数组移动的位置刚好是arr[i-zero]的

代码实现:

 

    /**

     * 移动元素0到数组最后

     *

     * @param arrays

     */

    public static void moveZero(int[] arrays) {

 

        // 记录该数组有多少个0元素

        int zero = 0;

 

 

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

 

            // 只要元素不为0,那么就往前面移动

            if (arrays[i] != 0) {

                arrays[i - zero] = arrays[i];

            } else {

                // 如果为0,那么zero ++

                zero++;

            }

        }

 

 

        // 1. 前面已经将非0的元素移动到数组的前面了

        // 2. 将为0的元素填满数组,填充的位置就从length - zero开始

 

 

        int j = arrays.length - zero;

        while (j < arrays.length) {

            arrays[j] = 0;

            j++;

        }

 

        System.out.println("关注公众号:Java3y---->" + arrays);

 

 

    }

结果:

5

还可以换种思路(差别不大):将数组分成几个部分:在j之前的没有0,j到i全是0,i后面还没有遍历

· 如果遍历到的数字不是0,那么跟j进行交换,j++(保证j前面没有0和j到i全是0)

· 直至i遍历完毕后,j前面都不是0,j-i都是0(这就完成我们的任务了)

代码实现:

 

    /**

     * 移动元素0到数组最后

     *

     * @param arrays

     */

    public static void moveZero2(int[] arrays) {

 

 

        // 在j前面的元素都不是0

        int j = 0;

 

 

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

 

            if (arrays[i] != 0) {

 

                // 跟j进行交换,保证j的前面都不是0

                int temp = arrays[i];

                arrays[i] = arrays[j];

                arrays[j]  = temp;

 

                j++;

            }

        }

 

        // 直至i遍历完毕后,j前面都不是0,j-i都是0(这就完成我们的任务了)

 

 

        System.out.println("关注公众号:Java3y---->" + arrays);

 

 

 

    }

结果还是一样的:

6

五、找出数组的单个数字

给你一个数组,除了一个数字外,其他的数字都出现了两次,请把这个只出现一次的数字找出来。

思路:

· 将该数组遍历一次,记录每个数字出现的次数

· 如果该数字出现的次数只有1,那么该数字就是单个数字~

 

 

 

 

 

    /**

     * 找出数组的单个数字

     * @param nums

     * @return

     */

    public static void singleNumber(int[] nums) {

 

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

 

            int count = countNumber(nums, nums[i]);

 

 

            // 如果该元素只出现一次,那么就是它了!

            if (count == 1) {

                System.out.println("关注公众号:Java3y--->单一的元素是:" + nums[i]);

 

                return ;

 

 

            }

 

 

        }

    }

 

    /**

     * 找出每个元素出现的次数

     * @param nums 数组

     * @param value 想知道出现次数的元素

     */

 

    public static int countNumber(int[] nums,int value) {

 

 

        int count = 0;

 

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

            if (value == nums[i]) {

                count++;

            }

        }

        // 返回该元素出现的次数

        return count;

    }

 

 

结果:

7

优化:

这个问题最佳的解法是用到了位运算的异或操作:

· 如果5^5=0

· 如果5^7^5 = 7

· 如果5^6^6^5^7^8^7 = 8

从上面的例子可以看出:一堆数字做异或运算^,俩俩相同数字就会被抵消掉~,所以这个特性对于这个题目而言就再适合不过的了:

 

    /**

     * 找出数组的单个数字

     * @param nums

     * @param numsSize

     * @return

     */

    public static int singleNumber(int[] nums, int numsSize) {

 

        // 第一个数和数组后面的数做^运算,留下的必然是单个数字

        int k = nums[0];

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

            k = (k ^ nums[i]);

        }

        return k;

    }

六、画三角形星星

画三角形星星

8

就是要画上面那种三角形星星,那怎么画呢??

思路:

· 首先,我们可以发现:每行星星的个数是(2*行数-1),每行的空格数就是最大行数减去第n行(最大4行,第4行没有空格,最大4行,第三行1个空格)

· 有了上面的规律,套个for循环即可生成三角形星星~

实现代码:

 

 

    /**

     * 画星星

     */

    public static void drawStar() {

 

        // 我要画5行的星星

        int row = 5;

 

 

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

 

            // 空格数等于最大行数 - 当前行数

            for (int j = 1; j <= row - i; j++) {

                System.out.print(" ");

            }

 

            // 星星数等于(当前行数*2-1)

            for (int j = 1; j <= i * 2 - 1; j++) {

 

                System.out.print("*");

 

            }

 

            // 每画一行就换一次行

            System.out.println();

        }

    }

 

结果:

9

七、罗马数字倒转成阿拉伯数字

罗马数字倒转成阿拉伯数字

罗马数字我们可能在英语的题目中看得是比较多的,一般常用的我们是阿拉伯数字,那怎么转成阿拉伯数字呢??我们先来了解一下罗马数字:

10

ps:来源360百科

规则在图上已经说得挺明白的了,我举几个例子:

· 左边的数比右边小,则是用右边的数减去左边的

· 左边的数比右边大,则是用右边的数加上左边的

11

12

看了上面的例子估计我们会手算将罗马数字转成阿拉伯数字了,那么用程序怎么写呢???

思路是这样的:

· 先找到罗马数字最大的那个数字

· 要是左边的数比右边小,则是用右边的数减去左边的

· 左边的数比右边大,则是用右边的数加上左边的

· .....如此循环则最后获取阿拉伯数字

首先,我们先定义罗马数字和对应的阿拉伯数字(相当于查表)

 

    // 定义罗马数字

    char digits[] = {'I', 'V', 'X', 'L', 'C', 'D', 'M'};

 

    // 罗马数字对应的阿拉伯数字

    int  values[] = { 1,  5, 10, 50, 100, 500, 1000};

随后,我们得找到罗马数字当前的最大值,找到最大值之前就先得把罗马数字转成是阿拉伯数字

    /**

     * 将罗马数字转成阿拉伯数字,实际上就是一个查表的过程

     *

     * @param roman

     * @return

     */

    public static int digitsToValues(char roman) {

 

        // 定义罗马数字

        char digits[] = {'I', 'V', 'X', 'L', 'C', 'D', 'M'};

 

        // 罗马数字对应的阿拉伯数字

        int values[] = {1, 5, 10, 50, 100, 500, 1000};

 

 

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

 

            if (digits[i] == roman) {

                return values[i];

            }

        }

 

        return 0;

 

    }

上面的方法已经可以将罗马数字转成阿拉伯数字了,接下来我们要查找出最大值了

 

    /**

     * 找到当前罗马数字最大值的角标

     *

     * @param digits

     * @return

     */

    public static int findMaxIndex(String digits, int L, int R) {

 

        // 假设第一个是最大的

        int max = digitsToValues(digits.charAt(L));

        int maxIndex = L;

 

        for (int i = L; i < R; i++) {

            // 将罗马数字转成是阿拉伯数字

            int num = digitsToValues(digits.charAt(i));

            if (max < num) {

                max = num;

                maxIndex = i;

            }

        }

 

        return maxIndex;

    }

找到了当前罗马数字的最大值那要怎么做???

· 左边的比右边的要小,则右边的减去左边的值

· 左边的比右边的要大,则右边的加上左边的值

· ....///实际上是一个递归的过程

于是乎,我们可以写出下面的代码:

 

 

    /**

     * 将罗马数字转成阿拉伯数字

     *

     * @param romanNumber

     * @param L

     * @param R

     */

    public static int romanToNumber(String romanNumber, int L, int R) {

 

        // 如果只有一个罗马数字,那么可以直接返回了(递归出口)

        if (L == R) {

            return digitsToValues(romanNumber.charAt(L));

        } else if (L > R) { // 如果L和R已经越界了,那么说明没有值了

            return 0;

        } else {

 

            // 找到当前罗马数字最大值的角标

            int maxIndex = findMaxIndex(romanNumber, L, R);

 

            // 得到最大值

            int max = digitsToValues(romanNumber.charAt(maxIndex));

 

            // 在最大值左边的,则用最大值减去左边的

            int left = romanToNumber(romanNumber, L, maxIndex - 1);

 

            // 在最大值右边的,则用最大值加上右边的

            int right = romanToNumber(romanNumber, maxIndex + 1, R);

 

            return max - left  + right;

        }

    }

测试一下:

13

八、啤酒与饮料

啤酒每罐2.3元,饮料每罐1.9元。小明买了若干啤酒和饮料,一共花了82.3元。我们还知道他买的啤酒比饮料的数量少,请你计算他买了几罐啤酒。

这是蓝桥杯的一道题,我们可以使用暴力搜索即可解出:

· 如果82.3全买啤酒最多能买82.3/2.3=35瓶

· 如果82.3全买饮料最多能买82.3/1.9=43瓶

· 以此作为控制条件

    /**

     * 啤酒与饮料题目

     */

    public static void beerAndDrink() {

        

        // 啤酒

        for (int i = 0; i < 36; i++) {

            

            // 饮料

            for (int j = 0; j < 44; j++) {

                

                // 钱刚好花光了,并且啤酒比饮料少

                if (2.3 * i + j * 1.9 == 82.3 && i < j) {

                    System.out.println("关注公众号:Java3y--------------->啤酒买了" + i);

                }

            }

        }

    }

测试:

14

九、简单凯撒密码

简单凯撒密码

凯撒密码是啥?简单来说:就是通过移位来进行加密

· 比如,A-->B,B-->C,C-->D.......

上面就是最简单的凯撒密码,将所有的字母进行移一位,实现加密

15

下面我们也来玩一下吧~

左移动和右移动:

    /**

     * 右移

     */

    public static int rotateRight(int ch) {

        if (ch >= 'A' && ch <= 'Y') {

            return ch + 1;

        } else if (ch >= 'a' && ch <= 'y') {

            return ch + 1;

        } else if (ch == 'Z') {

            return 'A';

        } else if (ch == 'z') {

            return 'a';

        } else {

            return ch;

        }

    }

 

    /**

     * 左移

     */

    public static int rotateLeft(int ch) {

        if (ch >= 'B' && ch <= 'Z') {

            return ch - 1;

        } else if (ch >= 'b' && ch <= 'z') {

            return ch - 1;

        } else if (ch == 'A') {

            return 'Z';

        } else if (ch == 'a') {

            return 'z';

        } else {

            return ch;

        }

    }

加密:

 

    /**

     * 加密

     * @param ch

     * @param shift

     * @return

     */

    public static int encode(int ch, int shift) {

 

        // 如果没有移动,则直接返回

        if (shift == 0) {

            return ch;

        } else if (shift > 0) {

 

            // 如果shift移动的是正数,那么就向右移动

            for (int i = 0; i < shift; i++) {

                ch = rotateRight(ch);

            }

            return ch;

        } else {

 

            // 如果shift移动的是负数,那么就向左移动

            for (int i = 0; i < -shift; i++) {

                ch = rotateLeft(ch);

            }

            return ch;

        }

    }

测试:

 

        String s = "HELLO WORLD";

        char[] ch = new char[s.length()];

 

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

           ch[i] = (char) encode(s.charAt(i), 3);

        }

 

        System.out.println("关注公众号:Java3y" + ch);

结果:

16

十、求最大公约数

求一个数的最大公约数

算法:是两个数相余,直到余数为0,如果余数不为0,就用除数和余数求余

· 若发现余数为0,那么当前的除数就是最大公约数

 

    /**

     * 求最大公约数

     *

     * @param num1

     * @param num2

     */

    public static int gcd(int num1, int num2) {

 

 

        // 求余数

        int r = num1 % num2;

 

        // 如果余数为0,那么除数就是最大公约数

        if (r == 0) {

            return num2;

        } else {

 

            // 否则,则用除数和余数来进行运算

            return gcd(num2, r);

        }

 

    }

结果:

17

总结

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

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

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

举个很简单的例子:

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

 

1. 

删除下标为k的元素

2. 

o 后一位往前一位覆盖即可

3. 

找出常用的数字

4. 

o 利用栈的思想,只要该数组出现的次数大于2分之1,那么他肯定是在栈里面

5. 

丢失的数字

6. 

o 实现1:两个数组进行遍历,如果某一个不存在,利用数组的角标就可以找到~

o 实现2:使用等差求和公式,缺失的数字可以减出来!

7. 

将0放在数组最后

8. 

o 实现1:使用变量zero来记住有多少个0,只要不是0就往前面移动,最后将zero补全!

o 实现2:将数组分成3个部分;在j之前的没有0,j到i全是0,i后面还没有遍历,直至i遍历完毕后,j前面都不是0,j-i都是0(这就完成我们的任务了)

9. 

找出数组的单个数字

10. 

o 实现1:遍历数组计算某个元素出现的次数,外层再遍历数组,只要该元素出现的次数是1,那么它就是单个的!

o 实现2:位运算的异或操作,相同的两个数字会抵消掉!

11. 

画三角形星星

12. 

o 找到画星星和空格的规律!星星和空格都与行数有关联!

13. 

罗马数字倒转成阿拉伯数字

14. 

o 将罗马数组和阿拉伯数字对应起来,“查表”进行转换!找到最大的值,左边比右边要小,则右减左。反之右加左!

15. 

啤酒与饮料

16. 

o 使用暴力查询的方式来将具体的值搜索出来!

17. 

简单凯撒密码

18. 

o char本质上就是int,移动时要主要Z,A这些字符~

19. 

求最大公约数

20. 

o 如果余数为0,那么除数就是最大公约数,否则就是除数和余数再继续运算!

 

以上就介绍了JAVA的相关知识,希望对JAVA有兴趣的朋友有所帮助。了解更多内容,请关注职坐标编程语言JAVA频道!


本文由 @白羽 发布于职坐标。未经许可,禁止转载。
喜欢 | 0 不喜欢 | 0
看完这篇文章有何感觉?已经有0人表态,0%的人喜欢 快给朋友分享吧~
评论(0)
后参与评论
加入IT交流圈
JAVA工程师交流群 +加入
大数据架构师交流群 +加入
人工智能Python交流群 +加入
WEB/H5前端交流群 +加入
大数据岗位高薪定向就业名额  提前锁定高薪职位
编程语言直通车

  • 资料索取

  • 答疑解惑

  • 技术交流

  • 职业测评

  • 面试技巧

  • 高薪秘籍
海同名师推荐 更多>>
张军 联系TA
10年项目开发经验,精通pc、mobile平台软件开发主流技术和框架
杨成江 联系TA
青春为马 不负韶华
翟健 联系TA
熟悉系大型项目开发业务流程,精通C、Java语言
黄骈 联系TA
认证System Analyst,System Architect
程光淼 联系TA
精通C、C++等语言、智能芯片开发
热门就业培训班 更多>>
【零基础】人工智能+Python全栈开发课程
登顶技术风口浪潮巅峰 年薪百万不是梦
【零基础】JavaEE高级开发工程师课程
小白0基础入学 8000起薪轻松进名企
【零基础】大数据与分布式架构师课程
掌握大数据分布式架构 冲击年薪50W+
JAVA30天热搜词 更多>>
X
免费获取海同IT培训资料
验证码手机号,获得海同独家IT培训资料
获取验证码
提交

版权所有 职坐标-一站式IT培训就业服务领导者 沪ICP备13042190号-4
上海海同信息科技有限公司 Copyright ©2015 www.zhizuobiao.com,All Rights Reserved.
沪公网安备 31011502005948号