第6章位运算和数学 - 数学 - 《数据结构与算法》

LeetCode

剑指 Offer

剑指 Offer 17. 打印从1到最大的n位数

输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

思路：
先找到 n 位数中最大的。

class Solution {
    public int[] printNumbers(int n) {
        int max = (int) Math.pow(10, n) - 1;
        int[] res = new int[max];
        for (int i = 0; i < max; i++) {
            res[i] = i + 1;
        }
        return res;
    }
}

大数问题

class Solution {
    int[] res;
    int nine = 0, count = 0, start, n;
    char[] num, loop = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};

    public int[] printNumbers(int n) {
        this.n = n;
        res = new int[(int)Math.pow(10, n) - 1];
        num = new char[n];
        start = n - 1;
        dfs(0);
        return res;
    }

    void dfs(int x) {
        if(x == n) {
            String s = String.valueOf(num).substring(start);
            if(!s.equals("0")) res[count++] = Integer.parseInt(s);
            if(n - start == nine) start--;
            return;
        }
        for(char i : loop) {
            if(i == '9') nine++;
            num[x] = i;
            dfs(x + 1);
        }
        nine--;
    }
}

剑指 Offer 43. 1～n整数中1出现的次数

输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。
例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

思路1（超时）：
暴力搜索。

class Solution {
    public int countDigitOne(int n) {
        int count = 0;
        while (n > 0) {
            String str = String.valueOf(n);
            char[] carr = str.toCharArray();
            for (char c : carr) {
                if (c == '1') count++;
            }
            n--;
        }
        return count;
    }
}

思路2：
递归。
f(n))函数的意思是1～n这n个整数的十进制表示中1出现的次数，将n拆分为两部分，最高一位的数字high和其他位的数字last，分别判断情况后将结果相加，看例子更加简单。

例子如n=1234，high=1, pow=1000, last=234

可以将数字范围分成两部分1~999和1000~1234

1~999这个范围1的个数是f(pow-1)
1000~1234这个范围1的个数需要分为两部分：
千分位是1的个数：千分位为1的个数刚好就是234+1(last+1)，注意，这儿只看千分位，不看其他位
其他位是1的个数：即是234中出现1的个数，为f(last)
所以全部加起来是f(pow-1) + last + 1 + f(last);

例子如3234，high=3, pow=1000, last=234

可以将数字范围分成两部分1~999，1000~1999，2000~2999和3000~3234

1~999这个范围1的个数是f(pow-1)
1000~1999这个范围1的个数需要分为两部分：
千分位是1的个数：千分位为1的个数刚好就是pow，注意，这儿只看千分位，不看其他位
其他位是1的个数：即是999中出现1的个数，为f(pow-1)
2000~2999这个范围1的个数是f(pow-1)
3000~3234这个范围1的个数是f(last)
所以全部加起来是pow + high*f(pow-1) + f(last);

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：36.6 MB, 在所有 Java 提交中击败了100.00%的用户

class Solution {
    public int countDigitOne(int n) {
        return f(n);
    }

    private int f(int n ) {
        if (n <= 0)
            return 0;
        String s = String.valueOf(n);
        int high = s.charAt(0) - '0';
        int pow = (int) Math.pow(10, s.length()-1);
        int last = n - high*pow;
        if (high == 1) {
            return f(pow-1) + last + 1 + f(last);
        } else {
            return pow + high*f(pow-1) + f(last);
        }
    }
}

剑指 Offer 44. 数字序列中某一位的数字

数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。
请写一个函数，求任意第n位对应的数字。

思路：
某一位的数字_1.png 某一位的数字_2.png 某一位的数字_3.png
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：36.3 MB, 在所有 Java 提交中击败了100.00%的用户

class Solution {
    public int findNthDigit(int n) {
        // len is how many digits:1 or 2 or 3 ...
        int len = 1, i = 1;
        // range is 9 or 90 or 900 ...
        long range = 9;
        while(n > len * range){
            n -= len * range;
            len++;
            range *= 10;
            i *= 10;
        }

        i += (n - 1) / len;
        String s = Integer.toString(i);
        return Character.getNumericValue(s.charAt((n - 1) % len));
    }
}

剑指 Offer 49. 丑数

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

思路：
三指针。基础丑数为1。初始分别指向三个有序链表第一个元素,这三个有序链表是想象出来的，分别就是ugly数组元素分别乘以2,3,5得到的。三个链表可能有相同元素，所以只要是最小的，都要移动指针。
执行用时：3 ms, 在所有 Java 提交中击败了78.09%的用户
内存消耗：37.9 MB, 在所有 Java 提交中击败了100.00%的用户

class Solution {
    public int nthUglyNumber(int n) {
        if(n < 7) return n;
        int[] res = new int[n];
        res[0] = 1;
        int t2 = 0, t3 = 0, t5 = 0;
        for(int i = 1; i < n; i++) {
            res[i] = Math.min(res[t2]*2, Math.min(res[t3]*3, res[t5]*5));
            if(res[i] == res[t2] * 2) t2++;
            if(res[i] == res[t3] * 3) t3++;
            if(res[i] == res[t5] * 5) t5++;
        }
        return res[n-1];
    }
}

剑指 Offer 61. 扑克牌中的顺子

从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。

思路：
两种情况可以凑成顺子，①除大小王外，所有牌无重复；②设此 55 张牌中最大的牌为 maxmax ，最小的牌为 minmin （大小王除外），则需满足最大牌 - 最小牌 < 5。
对数组进行排序，统计大小王数量。若有重复，提前返回 false。满足最大牌 - 最小牌 < 5 则可构成顺子。
执行用时：1 ms, 在所有 Java 提交中击败了88.85%的用户
内存消耗：37.2 MB, 在所有 Java 提交中击败了100.00%的用户

class Solution {
    public boolean isStraight(int[] nums) {
        int joker = 0;
        Arrays.sort(nums);
        for(int i = 0; i < 4; i++) {
            if(nums[i] == 0) joker++;
            else if(nums[i] == nums[i + 1]) return false;
        }
        return nums[4] - nums[joker] < 5;
    }
}

剑指 Offer 66. 构建乘积数组

给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B 中的元素 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。

思路：
执行用时：2 ms, 在所有 Java 提交中击败了81.52%的用户
内存消耗：52.5 MB, 在所有 Java 提交中击败了100.00%的用户

class Solution {
    public int[] constructArr(int[] a) {
        int length = a.length;
        int[] b = new int[length];
        if(length != 0 ){
            b[0] = 1;
            //计算下三角连乘
            for(int i = 1; i < length; i++){
                b[i] = b[i-1] * a[i-1];
            }
            int temp = 1;
            //计算上三角
            for(int j = length-2; j >= 0; j--){
                temp *= a[j+1];
                b[j] *= temp;
            }
        }
        return b;
    }
}

剑指 Offer 67. 把字符串转换成整数

写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。

首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。

当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。

该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。

注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。

在任何情况下，若函数不能进行有效的转换时，请返回 0。

说明：
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。

思路：
先处理前面的空格，然后符号位，然后数字。

class Solution {
    public int myAtoi(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }

        int len = str.length();
        // 处理开头的连续空字符
        int i = 0;
        while (i < len && str.charAt(i) == ' ') {
            i++;
        }

        // 处理符号位
        int sign = 1;
        if (i < len && (str.charAt(i) == '+' || str.charAt(i) == '-')) {
            sign = str.charAt(i) == '-' ? -1 : 1;
            i++;
        }

        // 处理数字字符
        long count = 0;
        while (i < len) {
            if (!Character.isDigit(str.charAt(i))) {
                break;
            }

            count = count * 10 + str.charAt(i++) - '0';
            if (count * sign > Integer.MAX_VALUE || count * sign < Integer.MIN_VALUE) {
                return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }
        }

        return (int) count * sign;
    }
}