github地址：https://github.com/ciecus/leetcode_answers/tree/master/jianzhi_offer

題目一：找出數(shù)組中重復(fù)的數(shù)字

書P39

github代碼名稱：t1_duplicated_numbers.py

在一個(gè)長度為n的數(shù)組里的所有數(shù)字都在0～n-1的范圍內(nèi)。數(shù)組中某些數(shù)字是重復(fù)的，但不知道有幾個(gè)數(shù)字重復(fù)了，也不知道每個(gè)數(shù)字重復(fù)了幾次。請找出數(shù)組中任意一個(gè)重復(fù)的數(shù)字。例如，如果輸入長度為7的數(shù)組{2,3,1,0,2,5,3},那么對應(yīng)的輸出是重復(fù)的數(shù)字2或者3.

解題思路

思路一：先排序，排序的時(shí)間復(fù)雜度為O(nlogn),然后從頭到尾掃描 思路二：利用哈希表，字典結(jié)構(gòu)，時(shí)間復(fù)雜度O(n),空間復(fù)雜度O(n) 思路三【比較復(fù)雜】：數(shù)組中的數(shù)字都在0~n-1的范圍內(nèi)。如果這個(gè)數(shù)字中沒有重復(fù)的數(shù)字，排序之后數(shù)字i將出現(xiàn)在下標(biāo)為i的位置。 所以可以從頭到尾掃描這個(gè)數(shù)組的每個(gè)數(shù)字，當(dāng)掃描到下標(biāo)為i的數(shù)字時(shí)，首先比較這個(gè)數(shù)字是不是等于i，如果不是就拿它和第m個(gè)數(shù)字進(jìn)行比較。如果它和m個(gè)數(shù)字相等就找到了一個(gè)重復(fù)數(shù)字。如果和第m個(gè)數(shù)字不想等，就和第m個(gè)數(shù)字交換。【太復(fù)雜了，暫緩】

測試用例

（1）長度為n的數(shù)組里包含一個(gè)或者多個(gè)重復(fù)的數(shù)字。

（2）數(shù)組中不包含重復(fù)的數(shù)字

（3）無效測試用例（輸入空指針：長度為n的數(shù)組中包含0～n-1之外的數(shù)字）

==輸入格式 == 數(shù)組長度n 輸入數(shù)組 長度為n的列表 例如： 3 1 2 2

代碼

方法一：

            
              import sys

def duplicated_number_1(n,values):
    if (len(values) != n) |(len(values)==0):
        print('the wrong input')
    else:
        values.sort()
        dup_list = []
        for i in range(n-1):
            if values[i] == values[i+1]:
                dup_list.append(values[i])
        dup_list = set(dup_list)
        if len(dup_list)>0:
            string = ''
            for dup in dup_list:
                string += str(dup)+'\t'
            print(string)
        else:
            print('no duplicates')

if __name__ == "__main__":
    n = input()
    values = [int(x) for x in sys.stdin.readline().strip().split()]
    duplicated_number_1(n, values)  

            
          

方法二：

            
              def duplicated_number_2(n,values):
    if (len(values) != n) | (len(values) == 0):
        print('the wrong input')
    else:
        value_dict = {}
        dup_list = set([])
        for value in values:
            if value in value_dict:
                dup_list.appen(value)
        dup_list = set(dup_list)
        if len(dup_list) > 0:
            string = ''
            for dup in dup_list:
                string += str(dup) + '\t'
            print(string)
        else:
            print('no duplicates')

            
          

題目二：不修改數(shù)組找出重復(fù)數(shù)字

書P41

在一個(gè)長度為n+1的數(shù)組里的所有數(shù)字都在1～n的范圍內(nèi)，所以數(shù)組中至少有一個(gè)數(shù)字時(shí)重復(fù)的。請找出數(shù)組中任意一個(gè)重復(fù)的數(shù)字，但不能修改輸入的數(shù)組。例如，如果輸入長度為8的數(shù)組{2,3,5,4,3,2,6,7}，那么對應(yīng)的輸出時(shí)重復(fù)的數(shù)字2或者3。

思路分析

和上一題類似，但是不能修改數(shù)組，所以就不能直接排序了。 但是使用哈希表的空間復(fù)雜度為o(n) 如果優(yōu)化的話，可以從二分查找的角度出發(fā)，調(diào)用countrange函數(shù)，調(diào)用O(logn)次，每次需要O(n)的時(shí)間，總時(shí)間復(fù)雜度為O(nlongn),空間復(fù)雜度為O(1)。和哈希表相比的空間換時(shí)間。

題目三：二維數(shù)組中的查找

書p44

github代碼名稱：t3_find_index.py

在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個(gè)函數(shù)，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷數(shù)組匯總是否含有該整數(shù)。 例如下面數(shù)組

1	2	8	9
2	4	9	12
4	7	10	13
6	8	11	15

思路分析

這道題比較巧妙的技巧應(yīng)該從右上角搜索。

如果搜索數(shù)字7:

對于右上角的數(shù)字9，9是第四列最小的數(shù)字，因?yàn)?大于7，所以7不可能在第4列， 同理不在第三列，所以應(yīng)在在第2列或者第1列，

然后從最右上角的數(shù)字2往下搜索。 因?yàn)?是第一行現(xiàn)在剩下的最大的數(shù)字，所以不在第一行， 然后4是第二行剩下的最大數(shù)字，所以不在第二行，

然后就搜索到了7。

假如搜索數(shù)字5，從4往下接著搜索，然后發(fā)現(xiàn)7大于5，所以5不在第二列。

往左走到4，發(fā)現(xiàn)4小于5，所以往下走。 然后是6大于5，往左走，發(fā)現(xiàn)不可以了。

就結(jié)束，找不到。

思路總結(jié)

從右上角開始遍歷，如果待比較的數(shù)字小于右上角的數(shù)字，就往左走，如果大于右上角的數(shù)字就往下走，直到out of index終結(jié)。

測試用例

（1）二維數(shù)組中包含查找的數(shù)字

（2）二維數(shù)組中沒有查找的數(shù)字

（3）特殊輸入用例，輸入空指針

輸入格式：

待查找的數(shù)組num
行數(shù)n，
列數(shù)m，
數(shù)組

輸出格式：如果找到輸出yes 否則輸出none 例如 7 3 2 1 2 2 4 4 6
代碼

            
              import sys

def find_number(num,n,m,matrix):
   y = 0
   x = m-1
   while num != matrix[y][x]:
       if num < matrix[y][x]:
           if x-1<0:
               return "None"
           else:
               x-=1
       if num >matrix[y][x]:
           if y+1
              
            
          

題目四：替換空格

書p51
github代碼名稱：jianzhi_offer/t4_replace_space.py
請實(shí)現(xiàn)一個(gè)函數(shù)，把字符串中的每個(gè)空格替換成"%20"，例如，輸入“we are happy。”則輸出"we%20are%20happy."

思路分析

（1）如果一個(gè)空格替換成"%",“2”,"0"這3個(gè)字符，因此字符串會(huì)變長。所以如果沒有測試用例應(yīng)該提問面試官是不是覆蓋。

（2）替換操作就是每次往后移動(dòng)兩個(gè)字節(jié)，但是復(fù)雜度為 $O(n^2)$

(3)可以先遍歷數(shù)空格個(gè)數(shù)，然后進(jìn)行替換。使用兩個(gè)指針，p1和p2，p1指向原字符串的末尾，p2指向替換之后的字符串的末尾，然后直到p1和p2位置相等為止。 圖例： 測試用例

（1）輸入字符串包含空格。空格位于最前面，空格位于最后面，空格位于中間，連續(xù)有多個(gè)空格

（2）輸入的字符串中沒有空格

（3）特殊用例，輸入為空字符串，輸入只有一個(gè)空格

代碼

            
              import sys

def replace_space(string):
    p1 = len(string)-1
    if p1 <0:
        return "None"
    else:
        i = 0
        for char in string:
            if char == " ":
                i += 1
        p2 = p1+2*i
        string_new = ['0' for i in range(p2)]
        while p2!=p1:
            char = string[p1-1]
            if char != " ":
                string_new[p2-1] = string[p1-1]
                p2-=1
                p1-=1
            else:

                string_new[p2-3:p2] = ['%','2','0']
                p2-=3
                p1-=1
        string_new[:p2] = string[:p1]

    return string_new

if __name__ == "__main__":
    string = list(sys.stdin.readline())
    print("".join(replace_space(string)))