加个“星标★”,每日 7:15,好文必达! 前文传送门: C# 刷遍 Leetcode 面试题系列连载(1) - 入门与工具简介 C#刷遍Leetcode面试题系列连载(2): No.38 - 报数 C#刷遍Leetcode面试题系列连载(3): No.728 - 自除数 C#刷遍Leetcode面试题系列连载(4): No.633 - 平方数之和 C#刷遍Leetcode面试题系列连载(5):No.593 - 有效的正方形 上一篇 LeetCode 面试题中,我们分析了一道难度为 Medium 的数学题 - 有效的正方形,提供了3种方法。今天我们继续来分析一道难度为 Medium 的面试题吧。 今天要给大家分析的面试题是 LeetCode 上第 372 号问题, LeetCode - 372. 超级次方 https:///problems/super-pow/ 题目描述你的任务是计算 对 1337 取模,a 是一个正整数,b 是一个非常大的正整数且会以数组形式给出。 示例 1: a = 2 b = [3]
结果: 8 示例 2: a = 2 b = [1,0]
结果: 1024 示例 3: a = 2147483647 b = [2,0,0] 结果: 1198 致谢: 特别感谢 @Stomach_ache 添加这道题并创建所有测试用例。
相关知识与思路:理解题意: 本题要求计算 % 1337,输入中a是以十进制形式给出,而b是以数组的形式给出的,数组中依次存有十进制下的每位数字。 解法1: 直接用字符串处理 public class Solution { public int SuperPow(int a, int[] b) { int res = 0; StringBuilder sb = new StringBuilder(); foreach (var item in b) sb.Append(item); int.TryParse(sb.ToString(), out int p); var val = (int) Math.Pow(a, p); res = val - (val / 1337)*1337;
return res; } } 会发现,对数b较大时(示例3)会越界。因此需利用模运算的性质来优化~ 而模运算的常用性质如下: 分配率: (a + b) mod n = [(a mod n) +(b mod n) ] mod n。 mod n = [(a mod n) (b mod n) ] mod n。 d mod() =(d mod a) + a [(d \ a) mod b] + [(d \ a \ b) mod c],其中\是欧几里德除法的商的算子。 c mod(a + b) =(c mod a) + [ (a + b) ] mod b - [ (a + b) ] mod a。 除法 :A/B mod n = [(a mod n) ( mod n) ] mod n,当b和n互质时,右边被定义。反之亦然。 相乘后的逆(Inverse multiplication): [( mod n) ( mod n) ] mod n = a mod n。 特殊性质:x % == x & () 另外,与之相关的一个概念是同余(Congruence relation)。 此题需用到分配率中的: mod n = [(a mod n) (b mod n) ] mod n 解法2 已AC代码: public class Solution { const int Mod0 = 1337; public int SuperPow(int a, int[] b) { if (b.Length == 0) return 1;
var res = 1; for (int i = b.Length - 1; i >= 0; i--) { res = powMod(a, b[i]) * res % Mod0; a = powMod(a, 10); }
return res; }
private int powMod(int a, int m) { a %= Mod0; int result = 1; for (int i = 0; i < m; i++) result = result * a % Mod0;
return result; } } Rank: 执行用时: 按理说,如果将a%m改为a-(a/m)*m,代码运行速度会变快些,直接进行模运算确实会慢一些。 解法3 已AC代码: public class Solution { const int Mod0 = 1337; public int SuperPow(int a, int[] b) { if (b.Length == 0) return 1;
var res = 1; for (int i = b.Length - 1; i >= 0; i--) { var powModResult = powMod(a, b[i]) * res; res = powModResult - (powModResult / Mod0) * Mod0; a = powMod(a, 10); }
return res; }
private int powMod(int a, int m) { a = a - (a / Mod0) * Mod0; int result = 1; for (int i = 0; i < m; i++) result = result * a - (result * a / Mod0) * Mod0;
return result; } } Rank:执行用时: 示例代码: https://github.com/yanglr/Leetcode-CSharp/tree/master/leetcode372 . 欢迎提出更佳的解决思路~ 最近正在看百度前副总裁的《俞军产品方法论》,提升一下自己的产品思维。这本书2019年12月才由中信出版社出版,良心好书,推荐给大家~ End |
|