8.30美团技术岗算法第一题

题目

说明

福利题也不白给，算术题肯定考大数处理，求余题肯定靠找规律

技术积累

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

StringTokenizer st = new StringTokenizer(br.readLine());

这种方法和new Scanner(System.in)有什么区别？

代码

import java.util.*;
import java.math.BigInteger;
import java.io.*;

public class NumberOperations {
    
    /**
     * 高效的数字操作算法
     * 规则：偶数除以2，奇数乘以3加1
     * 使用BigInteger处理大数，并进行优化避免超时
     */
    public static BigInteger solve(BigInteger n, long k) {
        // 如果k为0，直接返回n
        if (k == 0) {
            return n;
        }
        
        // 使用记忆化存储已计算的结果，避免重复计算
        Map<BigInteger, BigInteger> memo = new HashMap<>();
        
        // 优化：如果n变成1，后续操作会形成循环 1->4->2->1
        // 可以直接计算最终结果
        BigInteger current = n;
        long operations = k;
        
        while (operations > 0) {
            // 检查是否进入1-4-2-1循环
            if (current.equals(BigInteger.ONE)) {
                return handleCycle(operations);
            }
            if (current.equals(BigInteger.valueOf(2))) {
                return handleCycleFrom2(operations);
            }
            if (current.equals(BigInteger.valueOf(4))) {
                return handleCycleFrom4(operations);
            }
            
            // 检查记忆化
            if (memo.containsKey(current)) {
                current = memo.get(current);
                operations--;
                continue;
            }
            
            BigInteger original = current;
            
            // 执行操作
            if (current.remainder(BigInteger.valueOf(2)).equals(BigInteger.ZERO)) {
                // 偶数：除以2
                current = current.divide(BigInteger.valueOf(2));
            } else {
                // 奇数：乘以3加1
                current = current.multiply(BigInteger.valueOf(3)).add(BigInteger.ONE);
            }
            
            // 存储到记忆化表
            memo.put(original, current);
            operations--;
            
            // 优化：连续除以2的情况
            if (operations > 0 && current.remainder(BigInteger.valueOf(2)).equals(BigInteger.ZERO)) {
                // 计算可以连续除以2多少次
                long consecutiveDivisions = Math.min(operations, countTrailingZeros(current));
                if (consecutiveDivisions > 0) {
                    current = current.shiftRight((int)consecutiveDivisions);
                    operations -= consecutiveDivisions;
                }
            }
        }
        
        return current;
    }
    
    /**
     * 计算BigInteger末尾有多少个0（即可以被2整除多少次）减少上下文额外开销 将主循环20次除以二循环变成主循环一次辅助循环20次,减少其他判断逻辑19次
     */
    private static long countTrailingZeros(BigInteger n) {
        if (n.equals(BigInteger.ZERO)) return 0;
        
        long count = 0;
        BigInteger temp = n;
        while (temp.remainder(BigInteger.valueOf(2)).equals(BigInteger.ZERO)) {
            temp = temp.divide(BigInteger.valueOf(2));
            count++;
            // 限制最大连续除法次数，避免无限循环
            if (count > 60) break;
        }
        return count;
    }
    
    /**
     * 处理从1开始的循环：1->4->2->1
     */
    private static BigInteger handleCycle(long operations) {
        long remainder = operations % 3;
        if (remainder == 0) return BigInteger.ONE;
        if (remainder == 1) return BigInteger.valueOf(4);
        return BigInteger.valueOf(2);
    }
    
    /**
     * 处理从2开始的循环：2->1->4->2
     */
    private static BigInteger handleCycleFrom2(long operations) {
        long remainder = operations % 3;
        if (remainder == 0) return BigInteger.valueOf(2);
        if (remainder == 1) return BigInteger.ONE;
        return BigInteger.valueOf(4);
    }
    
    /**
     * 处理从4开始的循环：4->2->1->4
     */
    private static BigInteger handleCycleFrom4(long operations) {
        long remainder = operations % 3;
        if (remainder == 0) return BigInteger.valueOf(4);
        if (remainder == 1) return BigInteger.valueOf(2);
        return BigInteger.ONE;
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        // 读取输入
        BigInteger n = new BigInteger(st.nextToken());
        long k = Long.parseLong(st.nextToken());
        
        // 计算结果
        BigInteger result = solve(n, k);
        
        // 输出结果
        System.out.println(result.toString());
        
        br.close();
    }
}