說明：
本文中出現(xiàn)的所有算法題皆來自牛客網(wǎng)-劍指Offer在線編程題连茧，在此只是作為轉(zhuǎn)載和記錄客扎，用于本人學習使用宅楞，不允許轉(zhuǎn)載厌衙。多謝牛客網(wǎng)提供的資源。前面是所有的編程題筒饰，后面都是相關(guān)知識點補充和本人實現(xiàn)的解答。僅供參考谬晕！
一娘汞、 查找
二維數(shù)組中的查找
在一個二維數(shù)組中，每一行都按照從左到右遞增的順序排序禽作，每一列都按照從上到下遞增的順序排序。請完成一個函數(shù)萍程，輸入這樣的一個二維數(shù)組和一個整數(shù)兔仰，判斷數(shù)組中是否含有該整數(shù)茫负。
做題思路
最簡單的遍歷方式，不停的for循環(huán)就可以實現(xiàn)了
def find1(array, target):
for row in array:
if target in row:
return True
return False
更優(yōu)解
關(guān)鍵這個二維數(shù)組中乎赴，是一個從左到右、從上到下的遞增序列榕吼，是有序的饿序。
從左下角元素往上查找，這個元素比target小就往上找羹蚣，這個元素比target大就往右找,如果查詢不到戈抄，則說明二維數(shù)組中不存在這個元素戚哎。
def find2(array, target):
rows_length = len(array)
cols_length = len(array[0]) -1
i = rows_length - 1
j = 0
while i >= 0 and j <= cols_length:
if target < array[i][j]:
i -= 1
elif target > array[i][j]:
j += 1
else:
return True
return False
二、字符串
替換空格
請實現(xiàn)一個函數(shù)函似，將一個字符串中的空格替換成“%20”牌废。例如，當字符串為We Are Happy.則經(jīng)過替換之后的字符串為We%20Are%20Happy。
做題思路
最簡單的是用python的話一行代碼搞定
def replace_space1(s):
return '%20'.join(s.split(' '))
但是如果考慮傳入的字符串是個非常大的字符傳那個該如何處理咖祭，這一題出題的本意大概也是如此吧浩嫌。這個問題值得深究骚腥。
def replace_space2(s):
pass
正則表達式匹配
請實現(xiàn)一個函數(shù)用來匹配包括'.'和''的正則表達式。模式中的字符'.'表示任意一個字符浓利，而''表示它前面的字符可以出現(xiàn)任意次（包含0次）。 在本題中，匹配是指字符串的所有字符匹配整個模式且轨。例如，字符串"aaa"與模式"a.a"和"abaca"匹配筑煮，但是與"aa.a"和"ab*a"均不匹配碑宴。
做題思路
首先考慮特殊情況，當有字符串為空的時候公黑，如果兩個都為空影锈，則是正確匹配桅狠，則返回True一喘；如果pattern為空了戳粒，str不為空苔咪，那么顯然匹配失敗了，就返回False故响。
然后考慮 ‘*’ 和‘.’ 的情況寂汇，這里我們分兩種情況：
pattern下一個字符為‘’或 不為‘’：
- pattern下一個字符不為‘*’：
這種情況比較簡單式曲，直接匹配當前字符符衔。如果匹配成功，繼續(xù)匹配下一個水慨；如果匹配失敗，直接返回false打掘。
-
pattern下一個字符為‘’時祠够，稍微復雜一些，因為‘’可以代表0個或多個。這里把這些情況都考慮到：
- 當匹配0個字符時，str當前字符不變，pattern當前字符后移兩位，跳過這個‘’符號
- 當‘*’匹配1個或多個時，str當前字符移向下一個胸私，pattern當前字符不變。（這里匹配1個或多個可以看成一種情況，因為：當匹配一個時鸠信，由于str移到了下一個字符琳袄，而pattern字符不變权均，就回到了上邊的情況
- 當匹配多于一個字符時，相當于從str的下一個字符繼續(xù)開始匹配）
def match(s, pattern):
if not s and not pattern:
return True
if s and not pattern:
return False
if len(pattern) > 1 and pattern[1] == '*':
if s and (pattern[0] == s[0] or pattern[0] == '.' and s):
return match(s, pattern[2:]) or match(s[1:], pattern)
else:9
return match(s, pattern[2:])
if s and (pattern[0] == s[0] or pattern[0] == '.' and s):
return match(s[1:], pattern[1:])
else:
return False
表示數(shù)值的字符串
請實現(xiàn)一個函數(shù)用來判斷字符串是否表示數(shù)值（包括整數(shù)和小數(shù)）读存。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示數(shù)值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是弄兜。
字符流中第一個不重復的字符
請實現(xiàn)一個函數(shù)用來找出字符流中第一個只出現(xiàn)一次的字符廊驼。例如喳坠，當從字符流中只讀出前兩個字符"go"時，第一個只出現(xiàn)一次的字符是"g"笙各。當從該字符流中讀出前六個字符“google"時钉答，第一個只出現(xiàn)一次的字符是"l"。
輸出描述:
如果當前字符流沒有存在出現(xiàn)一次的字符杈抢，返回#字符数尿。
做題思路
這里有一個問題就是值只輸出第一個只出現(xiàn)一次的字符，從而考慮將字符與其出現(xiàn)的次數(shù)可以做一個關(guān)聯(lián)惶楼。
所以定義兩個變量右蹦，第一個用來存儲輸入的字符，另外一個來記錄字符與出現(xiàn)的次數(shù)歼捐。
class Solution:
def __init__(self):
self.s = ''
self.dict1 = {}
def FirstAppearingOnce(self):
for i in self.s:
if self.dict1[i] == 1: # 如果出現(xiàn)的次數(shù)為1何陆， 就返回
return i
return '#'
def Insert(self, char):
self.s = self.s + char
if char in self.dict1:
self.dict1[char] = self.dict1[char] + 1 # 字符再次出現(xiàn)，就將計數(shù)加1
else:
self.dict1[char] = 1 # 否則就是首次出現(xiàn)
三豹储、鏈表
從尾到頭打印鏈表
輸入一個鏈表贷盲，從尾到頭打印鏈表每個節(jié)點的值。
鏈表中環(huán)的入口結(jié)點
一個鏈表中包含環(huán)剥扣，請找出該鏈表的環(huán)的入口結(jié)點
刪除鏈表中重復的結(jié)點
在一個排序的鏈表中巩剖，存在重復的結(jié)點，請刪除該鏈表中重復的結(jié)點朦乏，重復的結(jié)點不保留球及，返回鏈表頭指針。 例如呻疹，鏈表1->2->3->3->4->4->5 處理后為 1->2->5
四吃引、樹
重建二叉樹
輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請重建出該二叉樹刽锤。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復的數(shù)字镊尺。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹并返回并思。
二叉樹的下一個結(jié)點
給定一個二叉樹和其中的一個結(jié)點庐氮，請找出中序遍歷順序的下一個結(jié)點并且返回。注意宋彼，樹中的結(jié)點不僅包含左右子結(jié)點弄砍，同時包含指向父結(jié)點的指針仙畦。
對稱的二叉樹
請實現(xiàn)一個函數(shù)，用來判斷一顆二叉樹是不是對稱的音婶。注意慨畸，如果一個二叉樹同此二叉樹的鏡像是同樣的，定義其為對稱的衣式。
按之字形順序打印二叉樹
請實現(xiàn)一個函數(shù)按照之字形打印二叉樹寸士，即第一行按照從左到右的順序打印，第二層按照從右至左的順序打印碴卧，第三行按照從左到右的順序打印弱卡，其他行以此類推。
把二叉樹打印成多行
從上到下按層打印二叉樹住册，同一層結(jié)點從左至右輸出婶博。每一層輸出一行。
序列化二叉樹
請實現(xiàn)兩個函數(shù)荧飞，分別用來序列化和反序列化二叉樹
二叉搜索樹的第k個結(jié)點
給定一顆二叉搜索樹凡蜻，請找出其中的第k大的結(jié)點。例如垢箕， 5 / \ 3 7 /\ /\ 2 4 6 8 中，按結(jié)點數(shù)值大小順序第三個結(jié)點的值為4兑巾。
數(shù)據(jù)流中的中位數(shù)
如何得到一個數(shù)據(jù)流中的中位數(shù)条获？如果從數(shù)據(jù)流中讀出奇數(shù)個數(shù)值，那么中位數(shù)就是所有數(shù)值排序之后位于中間的數(shù)值蒋歌。如果從數(shù)據(jù)流中讀出偶數(shù)個數(shù)值帅掘，那么中位數(shù)就是所有數(shù)值排序之后中間兩個數(shù)的平均值。
五堂油、 棧和隊列
用兩個棧實現(xiàn)隊列
用兩個棧來實現(xiàn)一個隊列修档，完成隊列的Push和Pop操作。 隊列中的元素為int類型府框。
滑動窗口的最大值
給定一個數(shù)組和滑動窗口的大小吱窝，找出所有滑動窗口里數(shù)值的最大值。例如迫靖，如果輸入數(shù)組{2,3,4,2,6,2,5,1}及滑動窗口的大小3院峡，那么一共存在6個滑動窗口，他們的最大值分別為{4,4,6,6,6,5}系宜； 針對數(shù)組{2,3,4,2,6,2,5,1}的滑動窗口有以下6個： {[2,3,4],2,6,2,5,1}照激， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}盹牧， {2,3,4,[2,6,2],5,1}俩垃， {2,3,4,2,[6,2,5],1}励幼， {2,3,4,2,6,[2,5,1]}。
六口柳、查找和排序
旋轉(zhuǎn)數(shù)組的最小數(shù)字
把一個數(shù)組最開始的若干個元素搬到數(shù)組的末尾苹粟，我們稱之為數(shù)組的旋轉(zhuǎn)。 輸入一個非遞減排序的數(shù)組的一個旋轉(zhuǎn)啄清，輸出旋轉(zhuǎn)數(shù)組的最小元素六水。 例如數(shù)組{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉(zhuǎn)，該數(shù)組的最小值為1辣卒。 NOTE：給出的所有元素都大于0掷贾，若數(shù)組大小為0，請返回0荣茫。
七想帅、遞歸和循環(huán)
斐波那契數(shù)列
大家都知道斐波那契數(shù)列，現(xiàn)在要求輸入一個整數(shù)n啡莉，請你輸出斐波那契數(shù)列的第n項港准。
n<=39
跳臺階
一只青蛙一次可以跳上1級臺階，也可以跳上2級咧欣。求該青蛙跳上一個n級的臺階總共有多少種跳法浅缸。
變態(tài)跳臺階
一只青蛙一次可以跳上1級臺階，也可以跳上2級……它也可以跳上n級魄咕。求該青蛙跳上一個n級的臺階總共有多少種跳法衩椒。
矩形覆蓋
我們可以用21的小矩形橫著或者豎著去覆蓋更大的矩形。請問用n個21的小矩形無重疊地覆蓋一個2*n的大矩形哮兰，總共有多少種方法毛萌？
八、位運算
二進制中1的個數(shù)
輸入一個整數(shù)喝滞，輸出該數(shù)二進制表示中1的個數(shù)阁将。其中負數(shù)用補碼表示。
九右遭、 代碼的完整性
數(shù)值的整數(shù)次方
給定一個double類型的浮點數(shù)base和int類型的整數(shù)exponent做盅。求base的exponent次方
調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面
輸入一個整數(shù)數(shù)組，實現(xiàn)一個函數(shù)來調(diào)整該數(shù)組中數(shù)字的順序窘哈，使得所有的奇數(shù)位于數(shù)組的前半部分言蛇，所有的偶數(shù)位于位于數(shù)組的后半部分，并保證奇數(shù)和奇數(shù)宵距，偶數(shù)和偶數(shù)之間的相對位置不變腊尚。
鏈表中倒數(shù)第k個結(jié)點
輸入一個鏈表，輸出該鏈表中倒數(shù)第k個結(jié)點满哪。
合并兩個排序的鏈表
輸入兩個單調(diào)遞增的鏈表婿斥，輸出兩個鏈表合成后的鏈表劝篷，當然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則。
樹的子結(jié)構(gòu)
輸入兩棵二叉樹A民宿，B娇妓，判斷B是不是A的子結(jié)構(gòu)。（ps：我們約定空樹不是任意一個樹的子結(jié)構(gòu)）
十活鹰、 面試思路
二叉樹的鏡像
操作給定的二叉樹哈恰，將其變換為源二叉樹的鏡像。
十一志群、 畫圖讓抽象形象化
順時針打印矩陣
輸入一個矩陣着绷，按照從外向里以順時針的順序依次打印出每一個數(shù)字，例如锌云，如果輸入如下矩陣： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 則依次打印出數(shù)字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
十二荠医、舉例讓抽象具體化
包含min函數(shù)的棧
定義棧的數(shù)據(jù)結(jié)構(gòu)，請在該類型中實現(xiàn)一個能夠得到棧最小元素的min函數(shù)桑涎。
棧的壓入彬向、彈出序列
輸入兩個整數(shù)序列，第一個序列表示棧的壓入順序攻冷，請判斷第二個序列是否為該棧的彈出順序娃胆。假設(shè)壓入棧的所有數(shù)字均不相等。例如序列1,2,3,4,5是某棧的壓入順序等曼，序列4缕棵，5,3,2,1是該壓棧序列對應的一個彈出序列，但4,3,5,1,2就不可能是該壓棧序列的彈出序列涉兽。（注意：這兩個序列的長度是相等的）
從上往下打印二叉樹
從上往下打印出二叉樹的每個節(jié)點，同層節(jié)點從左至右打印篙程。
二叉搜索樹的后序遍歷序列
輸入一個整數(shù)數(shù)組枷畏，判斷該數(shù)組是不是某二叉搜索樹的后序遍歷的結(jié)果。如果是則輸出Yes,否則輸出No虱饿。假設(shè)輸入的數(shù)組的任意兩個數(shù)字都互不相同拥诡。
二叉樹中和為某一值的路徑
輸入一顆二叉樹和一個整數(shù)，打印出二叉樹中結(jié)點值的和為輸入整數(shù)的所有路徑氮发。路徑定義為從樹的根結(jié)點開始往下一直到葉結(jié)點所經(jīng)過的結(jié)點形成一條路徑渴肉。
十三、 分解讓復雜問題簡單
復雜鏈表的復制
輸入一個復雜鏈表（每個節(jié)點中有節(jié)點值爽冕，以及兩個指針仇祭，一個指向下一個節(jié)點，另一個特殊指針指向任意一個節(jié)點）颈畸，返回結(jié)果為復制后復雜鏈表的head乌奇。（注意没讲，輸出結(jié)果中請不要返回參數(shù)中的節(jié)點引用，否則判題程序會直接返回空）
二叉搜索樹與雙向鏈表
輸入一棵二叉搜索樹礁苗，將該二叉搜索樹轉(zhuǎn)換成一個排序的雙向鏈表爬凑。要求不能創(chuàng)建任何新的結(jié)點，只能調(diào)整樹中結(jié)點指針的指向试伙。
字符串的排列
輸入一個字符串,按字典序打印出該字符串中字符的所有排列嘁信。例如輸入字符串a(chǎn)bc,則打印出由字符a,b,c所能排列出來的所有字符串a(chǎn)bc,acb,bac,bca,cab和cba。
輸入描述:
輸入一個字符串,長度不超過9(可能有字符重復),字符只包括大小寫字母疏叨。
十四潘靖、 時間效率
數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字
數(shù)組中有一個數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半，請找出這個數(shù)字考廉。例如輸入一個長度為9的數(shù)組{1,2,3,2,2,2,5,4,2}秘豹。由于數(shù)字2在數(shù)組中出現(xiàn)了5次，超過數(shù)組長度的一半昌粤，因此輸出2既绕。如果不存在則輸出0。
最小的K個數(shù)
輸入n個整數(shù)涮坐，找出其中最小的K個數(shù)凄贩。例如輸入4,5,1,6,2,7,3,8這8個數(shù)字，則最小的4個數(shù)字是1,2,3,4,袱讹。
連續(xù)子數(shù)組的最大和
HZ偶爾會拿些專業(yè)問題來忽悠那些非計算機專業(yè)的同學疲扎。今天測試組開完會后,他又發(fā)話了:在古老的一維模式識別中,常常需要計算連續(xù)子向量的最大和,當向量全為正數(shù)的時候,問題很好解決。但是,如果向量中包含負數(shù),是否應該包含某個負數(shù),并期望旁邊的正數(shù)會彌補它呢捷雕？例如:{6,-3,-2,7,-15,1,2,2},連續(xù)子向量的最大和為8(從第0個開始,到第3個為止)椒丧。你會不會被他忽悠住救巷？(子向量的長度至少是1)
整數(shù)中1出現(xiàn)的次數(shù)（從1到n整數(shù)中1出現(xiàn)的次數(shù)）
求出113的整數(shù)中1出現(xiàn)的次數(shù),并算出1001300的整數(shù)中1出現(xiàn)的次數(shù)壶熏？為此他特別數(shù)了一下1~13中包含1的數(shù)字有1、10浦译、11棒假、12、13因此共出現(xiàn)6次,但是對于后面問題他就沒轍了精盅。ACMer希望你們幫幫他,并把問題更加普遍化,可以很快的求出任意非負整數(shù)區(qū)間中1出現(xiàn)的次數(shù)帽哑。
把數(shù)組排成最小的數(shù)
輸入一個正整數(shù)數(shù)組，把數(shù)組里所有數(shù)字拼接起來排成一個數(shù)叹俏，打印能拼接出的所有數(shù)字中最小的一個妻枕。例如輸入數(shù)組{3，32，321}佳头，則打印出這三個數(shù)字能排成的最小數(shù)字為321323鹰贵。
十五、 時間空間效率的平衡
丑數(shù)
把只包含因子2康嘉、3和5的數(shù)稱作丑數(shù)（Ugly Number）碉输。例如6、8都是丑數(shù)亭珍，但14不是敷钾，因為它包含因子7。 習慣上我們把1當做是第一個丑數(shù)肄梨。求按從小到大的順序的第N個丑數(shù)阻荒。
第一個只出現(xiàn)一次的字符位置
在一個字符串(1<=字符串長度<=10000，全部由字母組成)中找到第一個只出現(xiàn)一次的字符,并返回它的位置
數(shù)組中的逆序?qū)?/a>
在數(shù)組中的兩個數(shù)字众羡，如果前面一個數(shù)字大于后面的數(shù)字侨赡，則這兩個數(shù)字組成一個逆序?qū)Α］斎胍粋€數(shù)組,求出這個數(shù)組中的逆序?qū)Φ目倲?shù)P粱侣。并將P對1000000007取模的結(jié)果輸出羊壹。 即輸出P%1000000007
輸入描述:
題目保證輸入的數(shù)組中沒有的相同的數(shù)字
數(shù)據(jù)范圍：
對于%50的數(shù)據(jù),size<=10^4
對于%75的數(shù)據(jù),size<=10^5
對于%100的數(shù)據(jù),size<=2*10^5
示例1
輸入
1,2,3,4,5,6,7,0
輸出
7
兩個鏈表的第一個公共結(jié)點
輸入兩個鏈表，找出它們的第一個公共結(jié)點齐婴。
十六油猫、 知識遷移能力
數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)
統(tǒng)計一個數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)。
二叉樹的深度
輸入一棵二叉樹柠偶，求該樹的深度情妖。從根結(jié)點到葉結(jié)點依次經(jīng)過的結(jié)點（含根、葉結(jié)點）形成樹的一條路徑诱担，最長路徑的長度為樹的深度毡证。
平衡二叉樹
輸入一棵二叉樹，判斷該二叉樹是否是平衡二叉樹蔫仙。
數(shù)組中只出現(xiàn)一次的數(shù)字
一個整型數(shù)組里除了兩個數(shù)字之外料睛，其他的數(shù)字都出現(xiàn)了兩次。請寫程序找出這兩個只出現(xiàn)一次的數(shù)字匀哄。
和為S的連續(xù)正數(shù)序列
小明很喜歡數(shù)學,有一天他在做數(shù)學作業(yè)時,要求計算出9~16的和,他馬上就寫出了正確答案是100。但是他并不滿足于此,他在想究竟有多少種連續(xù)的正數(shù)序列的和為100(至少包括兩個數(shù))雏蛮。沒多久,他就得到另一組連續(xù)正數(shù)和為100的序列:18,19,20,21,22∠呀溃現(xiàn)在把問題交給你,你能不能也很快的找出所有和為S的連續(xù)正數(shù)序列? Good Luck!
和為S的兩個數(shù)字
輸入一個遞增排序的數(shù)組和一個數(shù)字S，在數(shù)組中查找兩個數(shù)挑秉，是的他們的和正好是S法梯，如果有多對數(shù)字的和等于S，輸出兩個數(shù)的乘積最小的。
輸出描述:
對應每個測試案例立哑，輸出兩個數(shù)夜惭，小的先輸出。
左旋轉(zhuǎn)字符串
匯編語言中有一種移位指令叫做循環(huán)左移（ROL）铛绰，現(xiàn)在有個簡單的任務诈茧，就是用字符串模擬這個指令的運算結(jié)果。對于一個給定的字符序列S捂掰，請你把其循環(huán)左移K位后的序列輸出敢会。例如，字符序列S=”abcXYZdef”,要求輸出循環(huán)左移3位后的結(jié)果这嚣，即“XYZdefabc”鸥昏。是不是很簡單？OK姐帚，搞定它吏垮！
翻轉(zhuǎn)單詞順序列
牛客最近來了一個新員工Fish罐旗，每天早晨總是會拿著一本英文雜志膳汪，寫些句子在本子上。同事Cat對Fish寫的內(nèi)容頗感興趣尤莺，有一天他向Fish借來翻看旅敷，但卻讀不懂它的意思。例如颤霎，“student. a am I”媳谁。后來才意識到，這家伙原來把句子單詞的順序翻轉(zhuǎn)了友酱，正確的句子應該是“I am a student.”晴音。Cat對一一的翻轉(zhuǎn)這些單詞順序可不在行，你能幫助他么缔杉？
十七锤躁、 抽象建模能力
撲克牌順子
LL今天心情特別好,因為他去買了一副撲克牌,發(fā)現(xiàn)里面居然有2個大王,2個小王(一副牌原本是54張_)...他隨機從中抽出了5張牌,想測測自己的手氣,看看能不能抽到順子,如果抽到的話,他決定去買體育彩票,嘿嘿！或详！“紅心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是順子.....LL不高興了,他想了想,決定大\小 王可以看成任何數(shù)字,并且A看作1,J為11,Q為12,K為13系羞。上面的5張牌就可以變成“1,2,3,4,5”(大小王分別看作2和4),“So Lucky!”。LL決定去買體育彩票啦霸琴。 現(xiàn)在,要求你使用這幅牌模擬上面的過程,然后告訴我們LL的運氣如何椒振。為了方便起見,你可以認為大小王是0。
孩子們的游戲(圓圈中最后剩下的數(shù))
每年六一兒童節(jié),盼喑耍客都會準備一些小禮物去看望孤兒院的小朋友,今年亦是如此澎迎。HF作為怕睿客的資深元老,自然也準備了一些小游戲。其中,有個游戲是這樣的:首先,讓小朋友們圍成一個大圈夹供。然后,他隨機指定一個數(shù)m,讓編號為0的小朋友開始報數(shù)灵份。每次喊到m-1的那個小朋友要出列唱首歌,然后可以在禮品箱中任意的挑選禮物,并且不再回到圈中,從他的下一個小朋友開始,繼續(xù)0...m-1報數(shù)....這樣下去....直到剩下最后一個小朋友,可以不用表演,并且拿到牛客名貴的“名偵探柯南”典藏版(名額有限哦!!_)哮洽。請你試著想下,哪個小朋友會得到這份禮品呢填渠？(注：小朋友的編號是從0到n-1)
十八、 發(fā)散思維能力
求1+2+3+...+n
求1+2+3+...+n袁铐，要求不能使用乘除法揭蜒、for、while剔桨、if屉更、else、switch洒缀、case等關(guān)鍵字及條件判斷語句（A?B:C）瑰谜。
不用加減乘除做加法
寫一個函數(shù)，求兩個整數(shù)之和树绩，要求在函數(shù)體內(nèi)不得使用+萨脑、-、*饺饭、/四則運算符號渤早。
十九、 綜合
把字符串轉(zhuǎn)換成整數(shù)
將一個字符串轉(zhuǎn)換成一個整數(shù)瘫俊，要求不能使用字符串轉(zhuǎn)換整數(shù)的庫函數(shù)鹊杖。 數(shù)值為0或者字符串不是一個合法的數(shù)值則返回0
二十、數(shù)組
數(shù)組中重復的數(shù)字
在一個長度為n的數(shù)組里的所有數(shù)字都在0到n-1的范圍內(nèi)扛芽。 數(shù)組中某些數(shù)字是重復的骂蓖，但不知道有幾個數(shù)字是重復的。也不知道每個數(shù)字重復幾次川尖。請找出數(shù)組中任意一個重復的數(shù)字登下。 例如，如果輸入長度為7的數(shù)組{2,3,1,0,2,5,3}叮喳，那么對應的輸出是第一個重復的數(shù)字2被芳。
構(gòu)建乘積數(shù)組
給定一個數(shù)組A[0,1,...,n-1],請構(gòu)建一個數(shù)組B[0,1,...,n-1],其中B中的元素B[i]=A[0]A[1]...A[i-1]A[i+1]...A[n-1]。不能使用除法馍悟。
二十一畔濒、回溯法
矩陣中的路徑
請設(shè)計一個函數(shù)，用來判斷在一個矩陣中是否存在一條包含某字符串所有字符的路徑赋朦。路徑可以從矩陣中的任意一個格子開始篓冲，每一步可以在矩陣中向左，向右宠哄，向上壹将，向下移動一個格子。如果一條路徑經(jīng)過了矩陣中的某一個格子毛嫉，則該路徑不能再進入該格子。 例如 a b c e s f c s a d e e 矩陣中包含一條字符串"bcced"的路徑，但是矩陣中不包含"abcb"路徑祖今，因為字符串的第一個字符b占據(jù)了矩陣中的第一行第二個格子之后懦趋，路徑不能再次進入該格子。
機器人的運動范圍
地上有一個m行和n列的方格辛臊。一個機器人從坐標0,0的格子開始移動仙粱，每一次只能向左，右彻舰，上伐割，下四個方向移動一格，但是不能進入行坐標和列坐標的數(shù)位之和大于k的格子刃唤。 例如隔心，當k為18時，機器人能夠進入方格（35,37）尚胞，因為3+5+3+7 = 18硬霍。但是，它不能進入方格（35,38）笼裳，因為3+5+3+8 = 19唯卖。請問該機器人能夠達到多少個格子？
