大数处理

2021-07-04

大数的处理是算法中很常见的问题，关键是笔试也容易考，记录一下常见的考法

快速幂

leetcode 5802. 统计好数字的数目

题目

我们称一个数字字符串是好数字当它满足（下标从 0 开始）偶数下标处的数字为偶数且奇数下标处的数字为质数（2，3，5 或 7）。

比方说，”2582” 是好数字，因为偶数下标处的数字（2 和 8）是偶数且奇数下标处的数字（5 和 2）为质数。但 “3245” 不是好数字，因为 3 在偶数下标处但不是偶数。
给你一个整数 n ，请你返回长度为 n 且为好数字的数字字符串总数。由于答案可能会很大，请你将它对 10^9 + 7 取余后返回。

一个数字字符串是每一位都由 0 到 9 组成的字符串，且可能包含前导 0 。

思路

关键是题目给的n特别大，遇到这种数字特别大的情况，需要考虑快速幂求解。

对于偶数下标处的数字，它可以为 0,2,4,6,8 共计 5 种，而长度为 n 的数字字符串有 ⌊(n+1)/2⌋个偶数下标.

对于奇数下标处的数字，它可以为 2,3,5,7 共计 4 种，而长度为 n 的数字字符串有 ⌊n/2⌋个奇数下标。

因此长度为 n 的数字字符串中，好数字的总数即为：5^⌊(n+1)/2⌋*4^⌊n/2⌋

在本题中，由于 n 的取值最大可以到 10^15，如果通过普通的乘法运算直接求出上式中的幂，会超出时间限制，因此我们需要使用快速幂算法对幂的求值进行优化。

题解

class Solution {
    public int countGoodNumbers(long n) {
        return (int) ((quickMul(5,(n+1)/2)*quickMul(4,n/2))%(1000000000+7));
    }

    public long quickMul(int x,long n) {
        if(n==0) return 1;
        long y = quickMul(x, n / 2);
        return n % 2 == 0 ? y * y%(1000000000+7) : y * y * x%(1000000000+7);
    }
}

全排列

leetcode 面试题17. 打印从 1 到最大的 n 位数

题目

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

思路

本身其实不难，因为简单题所以时间复杂度要求不高，但是面试中多半会考虑大数的情况，所以需要使用全排列。

题解

public class Solution {

    private List<Integer> list;

    public int[] printNumbers(int n) {
        list = new ArrayList<>();
        dfs(n, 0, new StringBuilder());
        int[] res = new int[list.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = list.get(i);
        }
        return res;
    }

    private void dfs(int n, int i, StringBuilder sb) {
        if (i == n) {
            while (sb.length() != 0 && sb.charAt(0) == '0') {
                sb.deleteCharAt(0);
            }
            if (sb.length() != 0) {
                list.add(Integer.valueOf(sb.toString()));
            }
            return;
        }
        for (int j = 0; j < 10; j++) {
            sb.append(j);
            dfs(n, i + 1, sb);
            if (sb.length() != 0) {
                sb.deleteCharAt(sb.length() - 1);
            }
        }
    }
}

利用链表实现大数相加

leetcode2 两数相加

题目

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

思路

注意是逆序存储，考虑进位即可。

如果是正序，可以先原地反转链表。

题解

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode p = l1, q = l2; // 原链表的两个遍历指针
        ListNode resultHead = new ListNode(-1); // 结果链表的头结点head
        ListNode curr = resultHead; // 结果链表的遍历指针，代表当前操作的节点
        int carry = 0; // 进位
        // 1.遍历两个链表
        while (p != null || q != null) { // 以⻓链表为准
            // 获取当前节点的值：链表较短，已⽆节点，取0
            int x = p != null ? p.val : 0;
            int y = q != null ? q.val : 0;
            // 2.对应位置的节点数值相加
            int sum = x + y + carry;
            carry = sum / 10; // 如何得到进位：和对10求整，得到此次计算的进位
            int num = sum % 10; // 存放到新链表节点中的数值
            // 3.将计算结果插⼊新链表尾部
            curr.next = new ListNode(num); // 创建新节点
            curr = curr.next;
            p = p == null ? p : p.next;
            q = q == null ? q : q.next;
        }
        if (carry > 0) { // 处理进位节点
            curr.next = new ListNode(carry);
        }
        return resultHead.next;
    }
}

本文作者： xiaoyuyu
本文链接： http://woaixiaoyuyu.github.io/2021/07/04/%E5%A4%A7%E6%95%B0%E5%A4%84%E7%90%86/
版权声明： 本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。转载请注明出处！