[LintCode] Fast Power

weapon 发布于2019-08-14 15:22 / 2136人阅读

摘要：应用求余公式使用分治法，不断分解为，最终的子问题就是求解或者的余数。唯一要注意的就是，若为奇数，要将余数和再代入求余公式，运算一次。

Problem

Calculate the a^n % b where a, b and n are all 32bit integers.

Example

For 2^31 % 3 = 2

For 100^1000 % 1000 = 0

Challenge

O(logN)

Note

应用求余公式: (a * b) % p = (a % p * b % p) % p
使用分治法，不断分解a^n为a^(n/2)，最终的子问题就是求解a^1或者a^0的余数。
唯一要注意的就是，若n为奇数，要将余数和a再代入求余公式，运算一次。

Solution

class Solution {
    public int fastPower(int a, int b, int n) {
        if (n == 0) return 1 % b;
        if (n == 1) return a % b;
        long product = fastPower(a, b, n/2);
        product = product * product % b;
        if (n % 2 == 1) product = product * a % b;
        return (int) product;
    }
}

服务器托管私有云 LintCode LintCode134_LRU fast Power

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65711.html

[LintCode] Linked List Cycle I & II

摘要：做法如果有环，快慢指针必定可以相遇。而让此时重新从起点出发，以和相同的速度，需要走非环路的直线长度，才能到达环的起点。也就是说，，就是第二个循环结束的条件。 Linked List Cycle I Problem Given a linked list, determine if it has a cycle in it. Example Given -21->10->4->5, ta...

用户83 2019-08-14 15:17 评论0 收藏0
[LintCode/LeetCode] Rotate List

摘要：而后吾当依除取余之法，化大为小，则指针不致于越界也。后欲寻右起第结点，令快指针先行数日，及至两指针相距为，便吟鞭东指，与慢指针策马共进。快慢指针亦止于其所焉。舞动长剑，中宫直入，直取首级，而一掌劈空，已鸿飞冥冥。自此，一代天骄，霸业已成。 Problem Given a list, rotate the list to the right by k places, where k is...

Blackjun 2019-08-14 15:22 评论0 收藏0
[LintCode/LeetCode] Nth to Last Node in List

摘要：依然是一道找倒数第个结点的链表题，用双指针做。先走，然后和一起走，直到为，的位置就是倒数第个位置。 Problem Find the nth to last element of a singly linked list. The minimum number of nodes in list is n. Example Given a List 3->2->1->5->null ...

Salamander 2019-08-14 15:22 评论0 收藏0
[LintCode] Reorder List [链表综合题型]

摘要：链表题目的集合双指针法找中点，分割，合并，翻转，排序。主函数对于长度为或的链表，返回找到中点分割链表并翻转后半段为与前半段合并。当移动到最后一个元素，正好移动到整个链表的头部。 Problem Given a singly linked list L: L0 → L1 → … → Ln-1 → Ln reorder it to: L0 → Ln → L1 → Ln-1 → L2 → L...

王军 2019-08-14 15:32 评论0 收藏0
[Lintcode] Nth to Last Node in List 链表倒数第N个节点

摘要：递归法复杂度时间空间思路当递归到链表尾部时返回，每次返回时长度加，一旦长度为时记录下该节点。双指针法复杂度时间空间思路用两个指针，快指针先走步，然后快慢指针同时开始走，保持的距离，这样当快指针到达末尾时，慢指针就是倒数第个。 Nth to Last Node in List Find the nth to last element of a singly linked list. ...

CoXie 2019-08-14 12:30 评论0 收藏0