劍指offer（牛客網）day3

1、剪繩子

給你一根長度為n的繩子，請把繩子剪成整數長的m段（m、n都是整數，n>1并且m>1），每段繩子的長度記為k[0],k[1],…,k[m]。請問k[0]xk[1]x…xk[m]可能的最大乘積是多少？例如，當繩子的長度是8時，我們把它剪成長度分别為2、3、3的三段，此時得到的最大乘積是18。

解題思路：

• 先舉幾個例子，可以看出規律來。
• n：f(n)
• 特殊點：帶1的
• 2: 1*1
• 3： 2*1
• 正常點：隻有2和3
• 4 ： 2*2
• 5 ： 2*3
• 6 ： 3*3
• 7 ： 223 或者4*3
• 8 ： 233
• 9 ： 333
• 10：2233 或者43*3
• 11：233*3
• 12：333*3
• 13：22333 或者433*3
• 下面是分析：
• 首先判斷k[0]到k[m]可能有哪些數字，實際上隻可能是2或者3。
• 當然也可能有4，但是4=2*2，我們就簡單些不考慮了。
• 5<23,6<33,比6更大的數字我們就更不用考慮了，肯定要繼續分。
• 其次看2和3的數量，2的數量肯定小于3個，為什麼呢？因為

  2*2*2<3*3

  ，那麼題目就簡單了。
• 直接用n除以3，根據得到的餘數判斷是一個2還是兩個2還是沒有2就行了,餘數為1，則兩個2，餘數為0，沒有2，餘數為2，則1個2。
• 由于題目規定

  m>1,n>1，是以2隻能是1*1，3隻能是2*1

  ，這兩個特殊情況直接傳回就行了。

• m>1(m=2,3,4,...n-1),2<=n<=60

# -*- coding:utf-8 -*-
class Solution:
    def cutRope(self, number):
        # write code here
        if number == 2:
            return 1
        if number == 3:
            return 2
        x = number % 3  # 取餘
        y = number // 3  # 取整
        #dp = [1]
        if (x == 0):
            return pow(3, y)  # 3^y
        elif (x == 1):
            return 2 * 2 * pow(3, y - 1)
        else:
            return 2 * pow(3, y)
        pass
    pass
pass

sr=Solution()
print(sr.cutRope(8))
           

2、資料流中的中位數

如何得到一個資料流中的中位數？如果從資料流中讀出奇數個數值，那麼中位數就是所有數值排序之後位于中間的數值。如果從資料流中讀出偶數個數值，那麼中位數就是所有數值排序之後中間兩個數的平均值。我們使用Insert()方法讀取資料流（1個1個值給你），使用GetMedian()方法擷取目前讀取資料的中位數。

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.num=[]
    def Insert(self, num):
        # write code here
        self.num.append(num)
    def GetMedian(self):
        # write code here
        self.num.sort()
        n=len(self.num)
        if n%2==0:
            m=int(n//2)
            return int((self.num[m]+self.num[m-1])/2)
        else:
            m=int(n//2)
            return self.num[m]
        pass
    pass
pass

zws=Solution()
zws.Insert(2)
zws.Insert(1)
zws.Insert(4)
zws.Insert(8)
print(zws.GetMedian())
           

3、整數中1出現的個數（1到n的整數中）

求出1-13的整數中1出現的次數,并算出100-1300的整數中1出現的次數？為此他特别數了一下1~13中包含1的數字有1、10、11、12、13是以共出現6次,但是對于後面問題他就沒轍了。ACMer希望你們幫幫他,并把問題更加普遍化,可以很快的求出任意非負整數區間中1出現的次數（從1 到 n 中1出現的次數）。

解題思路：

分别除以10 ，将數拆分開，例如12143，除以10取餘分别為3,4,1,2,1

# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        if n<1:
            return 0
        Count = []
        for c in list(range(1, n+1)):
            # print(n)
            l = []
            count = 0
            while (c > 0):
                l.append(c % 10)
                c = c // 10
            # print(l)
            for num in range(0, len(l)):
                if l[num] == 1:
                    count += 1
                else:
                    count = count
                    pass
                pass
            # print(count)
            Count.append(count)
            pass
        return sum(Count)
        pass
    pass
pass
gs=Solution()
print(gs.NumberOf1Between1AndN_Solution(50))
           

優化：

class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        if n < 1:
            return 0
        num=list(range(1,n+1))
        num2=[]
        for i in num:
            x=list(map(int,str(i)))  # 12-->[1,2]
            for j in x:
                if j==1:
                    num2.append(1)
                else:
                    num2.append(0)
        return sum(num2)
gs=Solution()
print(gs.NumberOf1Between1AndN_Solution(50))
           

4、連續子數組的最大和

HZ偶爾會拿些專業問題來忽悠那些非計算機專業的同學。今天測試組開完會後,他又發話了:在古老的一維模式識别中,常常需要計算

連續子向量的最大和

,當向量全為正數的時候,問題很好解決。但是,如果向量中包含負數,是否應該包含某個負數,并期望旁邊的正數會彌補它呢？例如:{6,-3,-2,7,-15,1,2,2},連續子向量的最大和為8(從第0個開始,到第3個為止，其他連續的和小于8)。給一個數組，傳回它的最大連續子序列的和，你會不會被他忽悠住？(子向量的長度至少是1)

解題思路：

6+（-3）=3<6,3>(-3),目前最大值是6，但是3比從-3開始往後面好；

3+（-2）=1<6,1>(-2),最大值6,1比（-2）開始好；

1+7=8>6,7,替換最大值6變成最大值8，比7開始好；

8-15=-7<8,-7>-15,最大值8，比-15開始好；

-7+1=-6<1,最大值8，沒有1開始好，是以從1開始繼續操作第一步；

1+2=3>2,比2開始好，最大值3；

3+2=5>2,3，比2開始好，最大值5；

比較兩個最大值：8>5，左移最大值為8

集合會自動排序，是以本題不能輸入集合。

# -*- coding:utf-8 -*-
class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        maxnum=None
        tmpnum=0
        for i in array:
            if maxnum==None:
                maxnum=i
                pass
            if tmpnum+i<i:  # 比較有沒有不加好
                tmpnum=i
            else:
                tmpnum+=i
                pass
            if maxnum<tmpnum:
                maxnum=tmpnum
                pass
        return maxnum
zds=Solution()
print(zds.FindGreatestSumOfSubArray([6,-3,-2,7,-15,1,2,2]))
           

5、孩子們的遊戲（圓圈中最後剩下的數）

每年六一兒童節,牛客都會準備一些小禮物去看望孤兒院的小朋友,今年亦是如此。HF作為牛客的資深元老,自然也準備了一些小遊戲。其中,有個遊戲是這樣的:首先,讓小朋友們圍成一個大圈。然後,他随機指定一個數m,讓編号為0的小朋友開始報數。每次喊到m-1的那個小朋友要出列唱首歌,然後可以在禮品箱中任意的挑選禮物,并且不再回到圈中,從他的下一個小朋友開始,繼續0…m-1報數…這樣下去…直到剩下最後一個小朋友,可以不用表演,并且拿到牛客名貴的“名偵探柯南”典藏版(名額有限哦!!_)。請你試着想下,哪個小朋友會得到這份禮品呢？(注：小朋友的編号是從0到n-1)。如果沒有小朋友，請傳回-1

這道題的背景是約瑟夫環：

約瑟夫環（約瑟夫問題）是一個數學的應用問題：已知n個人（以編号1，2，3…n分别表示）圍坐在一張圓桌周圍。從編号為k的人開始報數，數到m的那個人出列；他的下一個人又從1開始報數，數到m的那個人又出列；依此規律重複下去，直到圓桌周圍的人全部出列。

在約瑟夫環中，隻是需要求出最後的一個出列者最初的序号，而不必要去模拟整個報數的過程。是以，為了追求效率，可以考慮從數學角度進行推算，找出規律然後再編寫程式即可。

上面編寫的解約瑟夫環的程式模拟了整個報數的過程，因為N和M都比較小，程式運作時間還可以接受，很快就可以出計算結果。可是，當參與的總人數N及出列值M非常大時，其運算速度就慢下來。例如，當N的值有上百萬，M的值為幾萬時，到最後雖然隻剩2個人，也需要循環幾萬次（由M的數量決定）才能确定2個人中下一個出列的序号。顯然，在這個程式的執行過程中，很多步驟都是進行重複無用的循環。

那麼，能不能設計出更有效率的程式呢？

辦法當然有。其中，在約瑟夫環中，隻是需要求出最後的一個出列者最初的序号，而不必要去模拟整個報數的過程。是以，為了追求效率，可以考慮從數學角度進行推算，找出規律然後再編寫程式即可。

為了讨論友善，先根據原意将問題用數學語言進行描述。

問題：将編号為0～（N–1）這N個人進行圓形排列，按順時針從0開始報數，報到M–1的人退出圓形隊列，剩下的人繼續從0開始報數，不斷重複。求最後出列者最初在圓形隊列中的編号。

下面首先列出0~(N-1)這N個人的原始編号如下：

0 1 2 3 … N-3 N-2 N-1

根據前面曾經推導的過程可知，第一個出列人的編号一定是(M–1)%N。例如，在13個人中，若報到3的人出列，則第一個出列人的編号一定是(4–1)%13=3，注意這裡的編号是從0開始的，是以編号3實際對應以1為起點中的編号4。根據前面的描述，m的前一個元素(M–1)已經出列，則出列1人後的清單如下：

0 1 2 3 … M-3 M-2 ○ M M+1 M+2 … N-3 N-2 N-1

注意，上面的圓圈表示被删除的數。

根據規則，當有人出列之後，下一個位置的人又從0開始報數，則以上清單可調整為以下形式（即以M位置開始，N–1之後再接上0、1、2……，形成環狀）：

M M+1 M+2 … N-2 N-1 0 1 … M-3 M-2

按上面排列的順序從0開始重新編号，可得到下面的對應關系：

M M+1 M+2 … N-2 N-1 0 1 … M-3 M-2

0 1 2 … N-(M+2) N-(M+1) N-M N-(M-1) … N-3 N-2

這裡，假設上一行的數為x，下一行的數為y，則對應關系為:

x = (y + M) % N      公式【1】  相當于前移了M位置，防止過區間，是以取餘
           

通過上表的轉換，将出列1人後的資料重新組織成了0～（N–2）共N–1個人的清單，繼續求N–1個參與人員，按報數到M–1即出列，求解最後一個出列者最初在圓形隊列中的編号。

看出什麼規律沒有？通過一次處理，将問題的規模縮小了。即對于N個人報數的問題，可以分解為先求解（N–1）個人報數的子問題；而對于（N–1）個人報數的子問題，又可分解為先求[(N-1)-1]個人報數的子問題，……。

問題中的規模最小時是什麼情況？就是隻有1個人時（N=1），報數到（M–1）的人出列，這時最後出列的是誰？當然隻有編号為0這個人。是以，可設有以下函數：

F(1) = 0
           

那麼，當N=2，報數到（M–1）的人出列，最後出列的人是誰？應該是隻有一個人報數時得到的最後出列的序号加上M，因為報到M-1的人已出列，隻有2個人，則另一個出列的就是最後出列者，利用公式【1】，可表示為以下形式：

F(2) = [F(1) + M] % N = [F(1) + M] % 2
           

于是，咱們可以得到遞推公式：

F(1) = 0
F(N) = [F(N - 1) + M] % N      (N>1)
           

設計程式設計：

# -*- coding:utf-8 -*-
class Solution:
    def LastRemaining_Solution(self, n, m):
        # write code here
        if n is None or m is None or n < 1 or m < 1:
            return -1
        if n==1:
            return 0
        last_out=0 # 最後出的人的編号
        for index in range(2,n+1):  # n從2開始到n結束
            last_out=(last_out+m)%index  #遞歸，F(n)=(F(n-1)+m)%n,n>1
        return last_out
isv=Solution()
print(isv.LastRemaining_Solution(5,2))
           

6、數組中出現次數超過一半的數字

數組中有一個數字出現的次數超過數組長度的一半，請找出這個數字。例如輸入一個長度為9的數組{1,2,3,2,2,2,5,4,2}。由于數字2在數組中出現了5次，超過數組長度的一半，是以輸出2。如果不存在則輸出0。

# -*- coding:utf-8 -*-
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        for item in set(numbers):
            if numbers.count(item) > len(numbers)/2:
                return item
        return 0
tj= Solution()
print(tj.MoreThanHalfNum_Solution([1,2,3,2,2,2,5,4,2]))
           

7、數值的整數次方

給定一個double類型的浮點數base和int類型的整數exponent。求base的exponent次方。保證base和exponent不同時為0

# -*- coding:utf-8 -*-
class Solution:
    '''
    給定一個double類型的浮點數base和int類型的整數exponent。
    求base的exponent次方。
    保證base和exponent不同時為0
    '''
    def Power(self, base, exponent):
        # write code here
        if base == 0:
            return 0
        elif base == 1:
            return 1
        elif exponent == 0:
            return 1
        elif exponent == 1:
            return base
        else:
            return pow(base, exponent)

cf=Solution()
print(cf.Power(1.5,2))
           

8、斐波那契數列

大家都知道斐波那契數列，現在要求輸入一個整數n，請你輸出斐波那契數列的第n項（從0開始，第0項為0，第1項是1）。n<=39

# -*- coding:utf-8 -*-
class Solution:
    '''
    菲波那切數列
    F(1)=1，F(2)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*）
    1、1、2、3、5、8、13、21、34
    '''
    def Fibonacci(self, n):
        # write code here
        if n==0:
            return 0
        if n==1 or n==2:
            return 1
        if 2<n<=39:
            s = [] * n
            s.append(1) #s[0]
            s.append(1) #s[1]
            for i in range(2, n):
                s.append(s[i - 2] + s[i - 1])
            return s[n - 1]


fbnq=Solution()
print(fbnq.Fibonacci(6))