[LintCode] Fast Power

weapon 發(fā)布于2019-08-14 15:22 / 2259人閱讀

摘要：應(yīng)用求余公式使用分治法，不斷分解為，最終的子問題就是求解或者的余數(shù)。唯一要注意的就是，若為奇數(shù)，要將余數(shù)和再代入求余公式，運(yùn)算一次。

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

應(yīng)用求余公式: (a * b) % p = (a % p * b % p) % p
使用分治法，不斷分解a^n為a^(n/2)，最終的子問題就是求解a^1或者a^0的余數(shù)。
唯一要注意的就是，若n為奇數(shù)，要將余數(shù)和a再代入求余公式，運(yùn)算一次。

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;
    }
}

云服務(wù)器 GPU云服務(wù)器 LintCode LintCode134_LRU fast Power

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/65711.html

相關(guān)文章

[LintCode] Linked List Cycle I & II

摘要：做法如果有環(huán)，快慢指針必定可以相遇。而讓此時重新從起點(diǎn)出發(fā)，以和相同的速度，需要走非環(huán)路的直線長度，才能到達(dá)環(huán)的起點(diǎn)。也就是說，，就是第二個循環(huán)結(jié)束的條件。 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

摘要：而后吾當(dāng)依除取余之法，化大為小，則指針不致于越界也。后欲尋右起第結(jié)點(diǎn)，令快指針先行數(shù)日，及至兩指針相距為，便吟鞭東指，與慢指針策馬共進(jìn)?？炻羔樢嘀褂谄渌?。舞動長劍，中宮直入，直取首級，而一掌劈空，已鴻飛冥冥。自此，一代天驕，霸業(yè)已成。 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

摘要：依然是一道找倒數(shù)第個結(jié)點(diǎn)的鏈表題，用雙指針做。先走，然后和一起走，直到為，的位置就是倒數(shù)第個位置。 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 [鏈表綜合題型]

摘要：鏈表題目的集合雙指針法找中點(diǎn)，分割，合并，翻轉(zhuǎn)，排序。主函數(shù)對于長度為或的鏈表，返回找到中點(diǎn)分割鏈表并翻轉(zhuǎn)后半段為與前半段合并。當(dāng)移動到最后一個元素，正好移動到整個鏈表的頭部。 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 鏈表倒數(shù)第N個節(jié)點(diǎn)

摘要：遞歸法復(fù)雜度時間空間思路當(dāng)遞歸到鏈表尾部時返回，每次返回時長度加，一旦長度為時記錄下該節(jié)點(diǎn)。雙指針法復(fù)雜度時間空間思路用兩個指針，快指針先走步，然后快慢指針同時開始走，保持的距離，這樣當(dāng)快指針到達(dá)末尾時，慢指針就是倒數(shù)第個。 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