[leetcode/lintcode 題解] 算法面試真題：233矩陣 · 233 Matrix

描述

給出一個矩陣A，矩陣的第一行是0,233，2333,23333...(也就是說，A(0,0)=0,A(0,1)=233,A(0,2)=2333,A(0,3)=23333...)，除此之外，A(i,j)=A(i-1,j)+A(i,j-1)。

給出一個擁有n個整數的數組X，X[i]表示A(i+1,0)，(也就是說X[0]表示A(1,0),X[1]表示A(2,0)...),以及一個正整數m。

求A(n,m)%10000007的值。

n <=10, m <= 10^9

0 =< A(i,0) < 2^31

線上評測位址：

領扣題庫官網

樣例1
輸入: X=[1], m=1
輸出: 234
解釋:
[[0,233],
 [1,234]]           

樣例2
輸入: X=[0,0], m=2
輸出: 2799
解釋:
[[0,233,2333],
 [0,233,2566],
 [0,233,2799]]           

算法：矩陣快速幂

快速幂：

• 這是一種簡單而有效的小算法，它可以以O(logn)的時間複雜度計算乘方
• 舉個例子，我們計算7^10，我們把10寫成二進制的形式，也就是 (1010)2
  • 現在問題轉變成了計算7^(1010)2，顯然我們可以将7^(1010)2拆分成7^(1000)2，7^(10)2。實際上，對于任意的整數，我們都可以把它拆成若幹個7^(1000....)2的形式相乘。而這恰好就是7^1、7^2、7^4……我們隻需不斷把底數平方就可以算出答案
  • 我們計算a的n次

  function：qpow(a,n)

  ans=1

  while n>0:

  if n&1 //如果n的目前末位為1
    ans*=a //ans乘上目前的a
    a*=a //a自乘           

  n >>= 1 //n往右移一位

  return ans

快速幂的進一步就是矩陣快速幂，兩者的差別就是，一個是數字，一個是矩陣

對于這題，首先找到原态和現态的關系，233，2333，23333，23333， 這些數都遵循 a0=a0'10+3 a1=a0'10+3+a1' ; a2=a0'10+3+a1'+a2' ; a3=a0'10+3+a1'+a2'+a3' ;

用數學歸納法可以得出遞推式：

• f(n,m)=f(n,m-1)*10+3;
• f(n,m) = f(n-1,m)+f(n,m-1) = f(n,m-1)+f(n-1,m-1)+f(n-2,m-1)+...+f(1,m-1)+f(0,m-1)*10+3;

然後我們建立矩陣：

構造矩陣得到了，我們就可以通過矩陣快速幂快速求答案了

複雜度分析

• 時間複雜度O(logn * L^3)
  • 快速幂的複雜度為logn量級
  • L為矩陣邊長，矩陣乘法為n^3量級
• 空間複雜度O(L^2)
  • 矩陣的大小為L*L

class Solution:
    """
    @param org: a permutation of the integers from 1 to n
    @param seqs: a list of sequences
    @return: true if it can be reconstructed only one or false
    """
    def sequenceReconstruction(self, org, seqs):
        graph = self.build_graph(seqs)
        topo_order = self.topological_sort(graph)
        return topo_order == org
            
    def build_graph(self, seqs):
        # initialize graph
        graph = {}
        for seq in seqs:
            for node in seq:
                if node not in graph:
                    graph[node] = set()
        
        for seq in seqs:
            for i in range(1, len(seq)):
                graph[seq[i - 1]].add(seq[i])

        return graph
    
    def get_indegrees(self, graph):
        indegrees = {
            node: 0
            for node in graph
        }
        
        for node in graph:
            for neighbor in graph[node]:
                indegrees[neighbor] += 1
                
        return indegrees
        
    def topological_sort(self, graph):
        indegrees = self.get_indegrees(graph)
        
        queue = []
        for node in graph:
            if indegrees[node] == 0:
                queue.append(node)
        
        topo_order = []
        while queue:
            if len(queue) > 1:
                # there must exist more than one topo orders
                return None
                
            node = queue.pop()
            topo_order.append(node)
            for neighbor in graph[node]:
                indegrees[neighbor] -= 1
                if indegrees[neighbor] == 0:
                    queue.append(neighbor)
                    
        if len(topo_order) == len(graph):
            return topo_order
            
        return None           

更多題解參考：

九章官網solution