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

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