【必备算法】杂记：求一个数的各位、约数

左手的ㄟ右手 2022-12-20 02:06 121阅读 0赞

## 1.求一个数的各位的两种思路 ##

比如说求int类型1234的各位怎么求？

### 方案一：转为字符串后charAt ###

int i = 1234;
    String s = "" + i; // 数组转字符串：num+“”
    
    char cChar = s.charAt(0) 			   // '1'  ==> charAt获取的各位为char型
    int cASC = (int) cChar 	 			   // 49   ==> ‘1’ 的ASCII码为 49
    boolean eq = ((cASC - 48) == 1) 	   // true ==> ‘1’ - 48 = 49 - 48 = 1  ==> 字符运算实际上是ASCII码运算
    int cSub = s.charAt(2) - s.charAt(0)   // 2    ==> '3' - '1' = 51 - 49 = 2 ==> 字符运算实际上是ASCII码运算
    boolean bigger = '3' > '1'             // true ==> ‘1’ - ‘9’ 依次递增，可以进行大小比较

**衍生题1**： 0-2019包含9的数字个数

public static void main(String[] args) {
        
            int ans = 0;
            for (int i = 1; i <= 2019; i++) {
        
                String s = "" + i;
                if (s.contains("9")) {
        
                    ans++;
                }
            }
            System.out.println(ans);
    }

**衍生题2**：数位递增的数

一个正整数如果任何一个数位不大于右边相邻的数位，则称为一个数位递增的数，例如1135是一个数位递增的数，而1024不是一个数位递增的数。  
给定正整数 n，请问在整数 1 至 n 中有多少个数位递增的数？

【输入格式】
    输入的第一行包含一个整数 n。
    【输出格式】
    输出一行包含一个整数，表示答案。
    【样例输入】
    30
    【样例输出】
    26

public static void main(String[] args) {
        
            int ans = 0;
            for (int i = 1; i < 30; i++) {
        
                String s = "" + i;
                boolean flag = true;
                for (int j = 0; j < s.length()-1; j++) {
        
                    if (s.charAt(j) > s.charAt(j+1) ) {
        
                        flag = false;
                        break;
                    }
                }
                if (flag) {
        
                    ans++;
                }
            }
            System.out.println(ans);
    }

### 方案二：具体算出各位 ###

通过取模运算，算出各位，代码如下：

public static void main(String[] args) {
        
    		// 待求数字
            int i = 1234;
        	// 保存各位的数字
            int[] nums = new int[10];
        	
        	// 1.计算这个数字的位数,4
        	// !!!注意：这里一定不能直接拿i计算，否则i=0
            int len = 0;
            for (int j = i; j != 0; len++)
                j /= 10;
        	
        	// 2.pow最初要除的数，1000
            int pow = (int)Math.pow((double)10,len-1);
        
        	// 3.分别计算每位
            for (int idx = 0; len > 0; len--,idx++) {
        
                // 3.1 除pow得到当前位，1
                nums[idx] = i / pow;
                // 3.2 取模pow得到下一个要算的数，234
                i %= pow;
                // 3.3 计算下一个pow，100
                pow /= 10;
            }
    
            System.out.println(Arrays.toString(nums));
        }

**衍生题**：求1-2019有多少个数字包含9

public static void main(String[] args) {
        
            int res = 0;
        	// i表示每个要求的数字
            for(int i = 0; i<=2019;i++) {
        
                
                // 计算位数
                // !!!注意：int j = i
                int len = 0;
                for (int j = i; j != 0; len++)
                    j /= 10;
    		   
                // pow
                int pow = (int)Math.pow((double)10,len-1);
    		   
                // 求每个i的各位
                // !!1注意：int j = i；因为i还控制着循环，这里用i会将i=0，死循环
                for (int j = i; len > 0; len--) {
        
                    if (j/pow == 9) {
        
                        res++;
                        break;
                    }
    
                    j %= pow;
                    pow /= 10;
                }
            }
            System.out.println(res);
        }

## 2 求一个数的约数 ##

**1.Time：(O(n))**

public static void main(String[] args) {
        
            Scanner in = new Scanner(System.in);
            int num = in.nextInt();
            int res = 0;
        	// 求平方根，注意强转int
            for (int i = 1; i <= n; i++) {
        
                if (num % i == 0) res ++;
            }
            System.out.println(res);
    }

**2.Time：O(根号n)**

其实是没有把所有数都遍历一遍的，因为当有一个约数时，其实代表有了一对约数。

public static void main(String[] args) {
        
            Scanner in = new Scanner(System.in);
            int num = in.nextInt();
            int res = 0;
        	// 求平方根，注意强转int
            for (int i = 1; i <= (int)Math.sqrt(num); i++) {
        
                if (num % i == 0) res +=2;
            }
            System.out.println(res);
    }