46 孩子們的遊戲（圓圈中最後剩下的數）
每年六一兒童節，牛客都會準備一些小禮物去看望孤兒院的小朋友，今年亦是如此。HF作為牛客的資深元老，自然也準備了一些小遊戲。其中，有個遊戲是這樣的：首先，讓小朋友們圍成一個大圈。然後，他隨機指定一個數m，讓編號為0的小朋友開始報數。每次喊到m-1的那個小朋友要出列唱首歌，然後可以在禮品箱中任意的挑選禮物，並且不再回到圈中，從他的下一個小朋友開始，繼續0。。。m-1報數。。。。這樣下去。。。。直到剩下最後一個小朋友，可以不用表演，並且拿到牛客名貴的“名偵探柯南”典藏版（名額有限哦！！^_^）。請你試著想下，哪個小朋友會得到這份禮品呢？（注：小朋友的編號是從0到n-1）
/*這題就是小時候上體育課玩的遊戲了老師報個數m 然後n個學生從第一位開始報數報到m的出列 然後從該同學後一個從0開始報重複 直到最後一個同學 做20俯臥撐可以用list模擬首先把陣列裝入list然後取一個位置計數器pos 用來每次模擬m而對於當前位置的記錄 取一個迭代器 開始從第一個同學開始 往後如果到最後一個了 就又從原來的開始pos——時迭代器++ 直到pos<0 然後從list中刪除該迭代器指向的元素重複以上 直到list只有一個元素由於以上方法每個需要查詢元素 資料大時 相當耗時 但是很符合正常的思路當然這題 還有其他更快的解法 就是數學歸納公式如果只求最後一個報數勝利者的話，我們可以用數學歸納法解決該問題，為了討 論方便，先把問題稍微改變一下，並不影響原意：問題描述：n個人（編號0~（n-1）），從0開始報數，報到（m-1）的退出，剩下的人 繼續從0開始報數。求勝利者的編號。我們知道第一個人（編號一定是m%n-1） 出列之後，剩下的n-1個人組成了一個新 的約瑟夫環（以編號為k=m%n的人開始）： k k+1 k+2 。。。 n-2， n-1， 0， 1， 2， 。。。 k-2並且從k開始報0。現在我們把他們的編號做一下轉換：k ——> 0k+1 ——> 1k+2 ——> 2。。。k-2 ——> n-2k-1 ——> n-1變換後就完完全全成為了（n-1）個人報數的子問題，假如我們知道這個子問題的解： 例如x是最終的勝利者，那麼根據上面這個表把這個x變回去不剛好就是n個人情 況的解嗎？！！變回去的公式很簡單，相信大家都可以推出來：x‘=（x+k）%n。令f［i］表示i個人玩遊戲報m退出最後勝利者的編號，最後的結果自然是f［n］。遞推公式f［1］=0；f［i］=（f［i-1］+m）%i； （i>1）有了這個公式，我們要做的就是從1-n順序算出f［i］的數值，最後結果是f［n］。 因為實際生活中編號總是從1開始，我們輸出f［n］+1。int LastRemaining_Solution（int n， int m） { if（n==0） return -1； if（n==1） return 0； else return （LastRemaining_Solution（n-1，m）+m）%n；}*/class Solution {public： int LastRemaining_Solution（int n， int m） { if（n == 0 || m == 0）return -1； list
47 求1+2+3+。。。+n
求1+2+3+。。。+n，要求不能使用乘除法、for、while、if、else、switch、case等關鍵字及條件判斷語句（A？B：C）。
/*不能用乘法想了好久 想不出來只能參考別人用sizeof 計算二維陣列的想法sizeof是運算子 計算連續陣列的長度 兩個指標分別指向第一個位置 和 最後一個位置二維陣列的話 相當把所有行加起來但我覺得本質上也算乘法了 或者 迴圈了程式碼 如下int Sum_Solution（int n） { bool a［n］［n+1］；//模擬n * n+1 return sizeof（a）>>1；//a的長度除2}最好的解法 是參考的使用帶兩個條件的遞迴利用與運算的特性當第一個條件不滿足直接返回*/class Solution {public： int Sum_Solution（int n） { int ans = n； // 當遞迴到n == 0 時 ans = 0 為 false //ans && （ans += Sum_Solution（n - 1）） 直接返回false 結束遞迴 ans && （ans += Sum_Solution（n - 1））； return ans； }}；
48 不用加減乘除做加法
寫一個函式，求兩個整數之和，要求在函式體內不得使用+、-、*、/四則運算子號。
class Solution {public： /** 1。兩個數異或：相當於每一位相加，而不考慮進位； 2。兩個數相與，並左移一位：相當於求得進位； 3。將上述兩步的結果相加； 如 3 + 2 11 + 10 ^ 01 & 100 01 + 100 ^ 101 & 0000 101 + 0000 return 101 = 5 **/ int Add（int n1， int n2） { if（！n2）return n1； else return Add（n1^n2，（n1&n2）<<1）； }}；
49 把字串轉換成整數
將一個字串轉換成一個整數（實現Integer。valueOf（string）的功能，但是string不符合數字要求時返回0），要求不能使用字串轉換整數的庫函式。 數值為0或者字串不是一個合法的數值則返回0。
class Solution { public： // 定義int32的最大最小邊界 int maxEdge = INT32_MAX / 10； int minEdge = INT32_MIN / 10；int maxSV = INT32_MAX % 10；int minSV = INT32_MIN % 10；int StrToInt（string str） { int n = str。size（）； if（n <= 0） return 0； int left = 0； bool is_Minus = false；//是不是負數 int res = 0； //去掉開始時的空格 while（left < n && str［left］ == ’ ‘） left ++ ； //判斷有沒有負數 if（str［left］ == ’+‘） left ++ ； else if（str［left］ == ’-‘） { left ++ ； is_Minus = true；// 是負數 } //從下標為left的數開始往後遍歷 int k = left； while（k < n） { if（str［k］ >= ’0‘ && str［k］ <= ’9‘）{ //負數計算 if（is_Minus）{ int t = （- 1） * （str［k］ - ’0‘）； //超出邊界判斷 if（res < minEdge） return INT32_MIN； if（res == minEdge） if（t < minSV） return INT32_MIN； //結果累加 res = res * 10 + t； } else//正數計算相同 { int t = str［k］ - ’0‘； if（res > maxEdge） return INT32_MAX； if（res == maxSV）{ if（t >= maxSV） return INT32_MAX； } else res = res * 10 + t； } } else return 0；//包含其他字母 說明不合法 直接返回0 //往後遍歷 k++； } return res；}}；
50 陣列中重複的數字
在一個長度為n的數組裡的所有數字都在0到n-1的範圍內。 陣列中某些數字是重複的，但不知道有幾個數字是重複的。也不知道每個數字重複幾次。請找出陣列中任意一個重複的數字。 例如，如果輸入長度為7的陣列{2，3，1，0，2，5，3}，那麼對應的輸出是第一個重複的數字2。
/*取一個map key 是陣列元素 value 是標記重複數字如果key包含元素 直接返回*/class Solution {public： bool duplicate（int numbers［］， int length， int* duplication） { map
