import java.util.LinkedList;
public class FindInteger {
/**
* 编程之美 找符合条件的整数 用字符串来表示大整数避免溢出
* 题目:任意给定一个正整数N,求一个最小的正整数M(M>1),使得N*M的十进制表示形式里只含有1和0
*
* 假设当前正在搜索由0,1组成的K位十进制数,这样的K位十进制数共有2^k个。
* 假设其中有两个数X、Y,它们模N同余,那么在搜索由0、1组成的K+1位十进制数时,
* X和Y会被扩展出四个数:10X, 10X+1, 10Y, 10Y+1。
* 因为X和Y同余(同余完全可以看作相等),所以10X与10Y同余,10X+1与10Y+1同余。
* 也就是说由Y扩展出来的子树和由X扩展产生出来的子树产生完全相同的余数,
* 如果X比Y小,那么Y肯定不是满足要求的最小的数,所以Y这棵子树可以被剪掉
*/
public static void main(String[] args) {
/*测试发现,在i=36时,方法一和方法二已经出错了
for(int i=1;i<=36;i++){
System.out.println(i+"-------------------");
System.out.println(find3(i));
System.out.println(find2(i));
System.out.println(find(i));
}
*/
for(int i=1;i<Integer.MAX_VALUE;i++){
System.out.println("("+find3(i)+" mod "+i+")=0");
}
}
/*
* 方法三:对方法二的改进
* 用字符串来表示大整数,避免溢出
* 难点在于,如何由X求得(10*X)以及(10*X+1)对n的余数:
* if X%n=q, X=n*K+q
* then (10*X)%n=(10*n*K+10*q)%n=(10*q)%n
*/
public static String find3(int n){
if(n<=0){
return null;
}
if(n==1){
return "1";
}
String[] data=new String[n]; //data[i]代表(x%n=i)的x,x用字符串表示:"1101" --> int x=1101
data[1]="1";
int k=2;
while(true){ //不必担心这是个死循环,可以证明,M是一定存在的
for(int i=0;i<n;i++){
String di=data[i];
if(di==null){
continue;
}
int len=di.length();
if((len+1)==k){ //K-->K+1
String s=di+"0"; //di*10
String t=di+"1"; //di*10+1
int rs=(i*10)%n; //(di*10)%n=(i*10)%n
int rt=(i*10+1)%n; //(di*10+1)%n=(i*10+1)%n
if(rs==0){
return s;
}else if(data[rs]==null || greaterThan(data[rs],s)){ //只保留最小的data[i]
data[rs]=s;
}
if(rt==0){
return t;
}else if(data[rt]==null || greaterThan(data[rt],t)){
data[rt]=t;
}
}
}
k++;
}
}
/*
* 比较由s和t代表的数字的大小。按位比较,从高位到低位。
* 如果s比t大,返回true,否则返回false
*/
public static boolean greaterThan(String s,String t){
if(!s.matches("[0-9]+") || !t.matches("[0-9]+")){
return false;
}
if(s.length()!=t.length()){
return s.length()>t.length();
}
int len=s.length();
char[] ss=s.toCharArray();
char[] tt=t.toCharArray();
for(int i=0;i<len;i++){
if(ss[i]!=tt[i]){
return ss[i]>tt[i];
}
}
return false;
}
//方法一:因为N*M的取值就是1,10,11,100,101,110,111,......所以直接在这个空间搜索
public static int find(int n){
if(n<=0){
return -1;
}
if(n==1){
return 1;
}
LinkedList<Integer> queue=new LinkedList<Integer>();
queue.add(1);
while(!queue.isEmpty()){
int t=queue.pollFirst(); //Retrieves and removes
if(t%n==0){
return t;
}
queue.addLast(t*10);
queue.addLast(t*10+1);
}
return -1;
}
//方法二:将方法一的搜索空间按模N余数分类,但没有解决N*M超出Integer.MAX_VALUE的溢出问题
public static int find2(int n){
if(n<=0){
return -1;
}
if(n==1){
return 1;
}
int[] data=new int[n];
data[1]=1;
int k=2;
while(true){
for(int i=0;i<n;i++){
int di=data[i];
if(di==0){
continue;
}
int len=0;
int dii=di;
while(dii!=0){ //计算是几位整数。计算K+1位时只需考虑K位
dii /=10;
len++;
}
if((len+1)==k){
int s=di*10;
int t=di*10+1;
if(s%n==0){
return s;
}else if(data[s%n]==0 || data[s%n]>s){
data[s%n]=s;
}
if(t%n==0){
return t;
}else if(data[t%n]==0 || data[t%n]>t){
data[t%n]=t;
}
}
}
k++;
}
}
}
分享到:
相关推荐
把一个字符串转化为相应的整数。特别注意符号与溢出的问题。
使用字符串解决c++中大整数加减法运算的问题,从而防止溢出。
字符串可能的余数倒整数 给定一个 32 位有符号整数,反转整数的数字。 注意:假设我们正在处理的环境只能存储 32 位有符号整数范围内的整数:[−231, 231 − 1]。 出于此问题的目的,假设您的函数在反转整数溢出时...
输入说明:函数接收两个参数,第一个参数可以是整数、字符串、列表或元组,第二个参数也可以是整数、字符串、列表或元组。 输出说明:函数返回两个参数的和,如果发生溢出,则返回None。 解题思路:定义一个名为add...
1. 空指针、空串 2. 整数溢出 3. 非法字符 4. 首字符为+、-
华为的一道机试题,两个用字符串表示的100位以内的数 相乘,结果用字符串输出
减少库的使用,解决那些需要小代码量,但苦恼于没有简易的字符串处理函数的郁闷 char *itoa_private(int val, char *buf, unsigned radix);//整数转字符串 int my_isdigit(int ch);//判断字符是否为数字 long long ...
蓝桥杯练习系统中的试题:算法训练 P0505 个人所做的答案。。。。。。。。。。。。。。。。。。。。。。。
^:匹配字符串开头 [\+\-]:代表一个+字符或-字符 ?:前面一个字符可有可无 \d:一个数字 +:前面一个字符的一个或多个 \D:一个非数字字符 *:前面一个字符的0个或多个 解法二:常规判断 需要注意的两个点: 1)在...
==strcpy拷贝的结束标志是查找字符串中的\0 因此如果字符串中没有遇到\0的话 会一直复制,直到遇到\0,上面的123都因此产生越界的情况 建议使用 strncpy 和 memcpy ---------------------------------------------...
LeetCode判断字符串是否循环 Leetcode刷题笔记 1. 题目描述 给定一个整数数组nums和一个目标值target,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。...
用数组实现的字符串和用指针实现的字符串的不同点 318 字符串数组 320 11-2 通过指针操作字符串 323 判断字符串长度 323 字符串的复制 325 不正确的字符串复制 328 返回指针的函数 329 11-3 字符串处理...
请根据这个假设,如果反转后整数溢出那么就返回 0。 分析: 我们可以一次构建反转整数的一位数字。在这样做的时候,我们可以预先检查向原整数附加另一位数字是否会导致溢出。 反转整数的方法可以与反转字符串进行...
8.1.2 整数溢出 8.1.3 格式化串攻击 8.2 文件Fuzzer 8.3 后续改进策略 8.3.1 代码覆盖率 8.3.2 自动化静态分析 第9章 Sulley 9.1 安装Sulley 9.2 Sulley中的基本数据类型 9.2.1 字符串 9.2.2 分隔符 9.2.3 静态和...
本运算库提供定长有符号大整数类的声明和基本操作的封装,实现过程仅使用基于C++98标准的基本语法,不依赖于任何标准库或者第三方库,以求最大限度保证代码的移植性(比如GCC和Visual Studio)和安全性(比如STL线程...
在 Redis 6.0 或更新的版本中,有一个整数溢出漏洞,可通过使用 STRALGO LCS 命令来破坏堆,可能导致远程代码 执行。这是由 CVE-2021-29477 的不完整修复造成的。 只适用于 Redis 6.2 以前版本的错误修复: 修复 ...
ISPR - 快速确定是否任意大的正... 然而,对于任意大的整数,你必须输入数字作为一个字符串,以避免溢出。 注意溢出错误下面倒数第二个例子。 例子: >>ispr(314159,1) 我相信 314159 是素数,但是5902958103587056
求横着读之字形的字符串 0007 Easy 给定整数反向输出,如果溢出返回0 0020 Easy Stack 0021 Easy Linked list 0026 Easy Array 0027 Easy Array 0035 Easy Array 0083 Easy 删除链表中的相同元素 0141 Easy 判断是否...
本书提供了在C编程语言中进行安全...如果统一应用这些指导方针,可帮助消除导致缓冲区溢出、格式字符串潜在风险、整数溢出和常见的软件潜在风险的关键编码错误,从而创建更健壮的高质量软件系统。以上简介来自于豆瓣。
85 <br>0130 复制字符串中指定的字符 85 <br>0131 巧截字符串的数字 86 <br>0132 如何存储变长字符串 86 <br>0133 在进行字符串比较时忽略大小写 87 <br>0134 如何去除字符串尾空格 87 ...