[LintCode] Fast Power

weapon 發布于2019-08-14 15:22 / 2252人閱讀

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

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

GPU云服務器云服務器 LintCode LintCode134_LRU fast Power

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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