算法趣题第一天

川长思鸟来 2022-12-05 12:10 230阅读 0赞

# 本篇简介 #

本篇博客的题目来源于《程序员的算法趣题》。

这是一本非常有意思的算法书，不像其他的算法书从链表，二叉树等数据结构原理入手，通过一道道的题目，从实际问题出发，来使读者了解算法的运用。不过唯一不足之处在于书中的算法源码多用Ruby与JavaScript来实现，对于刚上手学习编程的读者来说，这两种语言不会是首选的编程语言。因此，博主使用Java对书中的源码进行重构实现，对使用Java的初学者能够明白其中的算法。

PS：博主的技术水平有限，可能代码会比较的臃肿冗余，在时间复杂度和空间复杂度上无法做到最优，也欢迎在评论区讨论留言，共同进步。

# 系列链接 #

[算法趣题 第一天][Link 1]  
[算法趣题 第二天][Link 2]  
[算法趣题 第三天][Link 3]  
[算法趣题 第四天][Link 4]

# Q1 回文的十进制数 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDAxODU0MA_size_16_color_FFFFFF_t_70_pic_center]

## 难点 ##

这道题的难点在于如何编写**回文数的判定条件**以及**进制转换函数**的使用。

## 源码 ##

public class Test01 {
        
    
    	public static void main(String[] args) {
        
    		//定义初始值
    		int num =11;
    		//根据题意是寻找满足条件的最小值，直接给个死循环，找到满足的跳出即可
    		while(true){
        
    			//String类型没有reverse函数，但StringBuffer有，偷懒直接用StringBuffer实现回文数
    			//进行进制转换，用String类型接收方便下一步转换为StringBuffer类型对象
    			String numInTen = Integer.toString(num);
    			String numInTwo = Integer.toBinaryString(num).toString();
    			String numInEight = Integer.toOctalString(num);
    			//转换为StringBuffer
    			StringBuffer bufferInTen = new StringBuffer(numInTen);
    			StringBuffer bufferInTwo = new StringBuffer(numInTwo);
    			StringBuffer bufferInEight = new StringBuffer(numInEight); 
    			//这里要注意equals()函数与==之间的区别
    			if(numInTen.equals(bufferInTen.reverse().toString()) && numInTwo.equals(bufferInTwo.reverse().toString()) && numInEight.equals(bufferInEight.reverse().toString())) {
        
    				break;
    			}
    			//这里直接+2是因为偶数二进制末尾是0，回文后变成开头为0，必然无法实现条件，可以直接略去
    			num +=2;
    		}
    		//输出结果
    		System.out.print(num);
    	}
    }

## 要点 ##

1.  进制转换方法

<table> 
 <thead> 
  <tr> 
   <th>方法</th> 
   <th>作用</th> 
   <th>参数解释</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>Integer.toBinaryString(int i)</td> 
   <td>转换为二进制</td> 
   <td>i 待转换的十进制数</td> 
  </tr> 
  <tr> 
   <td>Integer.toOctalString(int i)</td> 
   <td>转换为八进制</td> 
   <td>i 待转换的十进制数</td> 
  </tr> 
  <tr> 
   <td>Integer.toHexString(int i)</td> 
   <td>转换为十六进制</td> 
   <td>i 待转换的十进制数</td> 
  </tr> 
  <tr> 
   <td>Integer.parseInt(String a, int n)</td> 
   <td>转换为十进制</td> 
   <td>a 带转换的数(字符型) <br> n 数的进制类型（二进制为2，八进制为8，十六进制为16）</td> 
  </tr> 
 </tbody> 
</table>

1.  equals()函数与==的区别  
    一般我们在比较值是否相同时习惯用 == 来表示，但是字符串的比较中并不能这么做。
    
    == 在字符串的比较中，表示判断两个字符串所存储的内存地址是否相同，这明显与我们想要判断的目的不一致
    
    因此我们要使用equals()函数来判断字符串内容是否相同。

# Q2 数列的四则运算 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDAxODU0MA_size_16_color_FFFFFF_t_70_pic_center 1]

## 难点 ##

本题的难点在于如何对**数字插入符号后进行运算**得出结果。

## 源码 ##

import javax.script.ScriptEngine;
    import javax.script.ScriptEngineManager;
    
    public class Test02 {
        
    
    	public static void main(String[] args) throws Exception {
        
    		//定义可插入的运算符（分析可发现只有连乘的形式能够实现题意）
            String[] op = {
        "*", ""};
            //本题需要调用JavaScript库的eval()函数，因此声明对象
            ScriptEngineManager manager = new ScriptEngineManager();
            ScriptEngine se = manager.getEngineByName("js");
            //循环遍历
            for (int i = 1000; i < 10000; i++) {
        
                char[] num = Integer.toString(i).toCharArray();
                //遍历插入运算符
                for (String j : op) {
        
                    for (String k : op) {
        
                        for (String l : op) {
        
                            //组合表达式
                            String val = num[3] + j + num[2] + k + num[1] + l + num[0];
                            //判断是否有插入运算符
                            if (val.length() > 4) {
        
                            	//通过eval()函数计算表达式	
                                if (i == (int) se.eval(val)) {
        
                                	//将满足题意的值输出
                                    StringBuffer res = new StringBuffer(Integer.toString(i));
                                    System.out.print(res.reverse().toString());
                                }
                            }
                        }
                    }
                }
            }
        }
    }

## 要点 ##

1.  本题比较有意思的是Java对于JavaScript函数的调用方法以及eval()函数的使用

ScriptEngineManager manager = new ScriptEngineManager();
    ScriptEngine se = manager.getEngineByName("js");

至于其他的属于常规操作啦！如果有啥不明白的可以评论区留言哦！

# Q3 翻牌 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDAxODU0MA_size_16_color_FFFFFF_t_70_pic_center 2]

## 难点 ##

这道题的难点在于**一维数组的操作**

## 源码 ##

public class Test03 {
        
    	
    	public static void main(String[] args) {
        
    		//初始化数组，大小为100
    		int[] num = new int[100];
    		//为数组赋值1
    		for(int i =0;i<100;i++) {
        
    			num[i] = 1;
    		}
    		//模拟翻牌过程，-1为正面，1为反面（通过相反数转换来模拟翻牌）
    		for(int j = 2;j<100;j++) {
        
    			for(int k = j;k<100;k+=j) {
        
    				//由于数组从0开始，而牌从1开始，k-1来保证翻牌的位置
    				num[k-1] = -num[k-1];
    			}
    		}
    		//遍历输出结果
    		for(int l = 0;l<100;l++) {
        
    			//寻找反面的牌
    			if(num[l]==1) {
        
    				//l+1为输出牌上的数而不是位置
    				System.out.println(l+1);
    			}
    		}
    	}
    }

## 要点 ##

1.  数组的操作属于比较难理解的部分了，由于数组的第一位是从0开始的，而我们日常都是从1开始的，初学者很容易搞混。而且数组可以进行的操作太多了，要熟练掌握也不容易，要多加练习哦！

# 结语 #

如果说这篇文章有让你学到一定的知识的话，不妨点个赞和关注，让博主能够看到。如果讲解中有什么错误和疏忽，也劳烦在评论中指出或提问，博主会第一时间进行更新和答复，谢谢！

[Link 1]: https://blog.csdn.net/weixin_44018540/article/details/108510424
[Link 2]: https://blog.csdn.net/weixin_44018540/article/details/108532431
[Link 3]: https://blog.csdn.net/weixin_44018540/article/details/108554156
[Link 4]: https://blog.csdn.net/weixin_44018540/article/details/108596376
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDAxODU0MA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/2b43d018472d474da9aeaf2c23b947fb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDAxODU0MA_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/7f60b4fa63424585bf0a8dc38ecdfa64.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDAxODU0MA_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/e101e738328f42b8ab0b3ffd26177583.png