[LintCode] Fast Power

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

摘要：應(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;
    }
}

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

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/65711.html

相關(guān)文章

[LintCode] Linked List Cycle I & II

摘要：做法如果有環(huán)，快慢指針必定可以相遇。而讓此時(shí)重新從起點(diǎn)出發(fā)，以和相同的速度，需要走非環(huán)路的直線長(zhǎng)度，才能到達(dá)環(huán)的起點(diǎn)。也就是說，，就是第二個(gè)循環(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 評(píng)論0 收藏0
[LintCode/LeetCode] Rotate List

摘要：而后吾當(dāng)依除取余之法，化大為小，則指針不致于越界也。后欲尋右起第結(jié)點(diǎn)，令快指針先行數(shù)日，及至兩指針相距為，便吟鞭東指，與慢指針策馬共進(jìn)。快慢指針亦止于其所焉。舞動(dòng)長(zhǎng)劍，中宮直入，直取首級(jí)，而一掌劈空，已鴻飛冥冥。自此，一代天驕，霸業(yè)已成。 Problem Given a list, rotate the list to the right by k places, where k is...

Blackjun 2019-08-14 15:22 評(píng)論0 收藏0
[LintCode/LeetCode] Nth to Last Node in List

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

摘要：鏈表題目的集合雙指針法找中點(diǎn)，分割，合并，翻轉(zhuǎn)，排序。主函數(shù)對(duì)于長(zhǎng)度為或的鏈表，返回找到中點(diǎn)分割鏈表并翻轉(zhuǎn)后半段為與前半段合并。當(dāng)移動(dòng)到最后一個(gè)元素，正好移動(dòng)到整個(gè)鏈表的頭部。 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 評(píng)論0 收藏0
[Lintcode] Nth to Last Node in List 鏈表倒數(shù)第N個(gè)節(jié)點(diǎn)

摘要：遞歸法復(fù)雜度時(shí)間空間思路當(dāng)遞歸到鏈表尾部時(shí)返回，每次返回時(shí)長(zhǎng)度加，一旦長(zhǎng)度為時(shí)記錄下該節(jié)點(diǎn)。雙指針法復(fù)雜度時(shí)間空間思路用兩個(gè)指針，快指針先走步，然后快慢指針同時(shí)開始走，保持的距離，這樣當(dāng)快指針到達(dá)末尾時(shí)，慢指針就是倒數(shù)第個(gè)。 Nth to Last Node in List Find the nth to last element of a singly linked list. ...

CoXie 2019-08-14 12:30 評(píng)論0 收藏0