46.孩子們的游戲
每年六一兒童節(jié),潘圃客都會(huì)準(zhǔn)備一些小禮物去看望孤兒院的小朋友,今年亦是如此咐刨。
HF作為哦瘢客的資深元老,自然也準(zhǔn)備了一些小游戲联予。
其中,有個(gè)游戲是這樣的:首先,讓小朋友們圍成一個(gè)大圈沸久。
然后,他隨機(jī)指定一個(gè)數(shù)m,讓編號(hào)為0的小朋友開始報(bào)數(shù)卷胯。
每次喊到m-1的那個(gè)小朋友要出列唱首歌,然后可以在禮品箱中任意的挑選禮物,并且不再回到圈中,從他的下一個(gè)小朋友開始,繼續(xù)0...m-1報(bào)數(shù)....這樣下去....直到剩下最后一個(gè)小朋友,可以不用表演,并且拿到乓ふ觯客名貴的“名偵探柯南”典藏版(名額有限哦!!^_^)卵慰。
請(qǐng)你試著想下,哪個(gè)小朋友會(huì)得到這份禮品呢裳朋？(注：小朋友的編號(hào)是從0到n-1)
如果沒(méi)有小朋友吓著，請(qǐng)返回-1
這個(gè)題考察的就是抽象建模能力绑莺，我們可以把最原始的n個(gè)小朋友構(gòu)造成一個(gè)環(huán)形鏈表，就是普通的單鏈表的尾結(jié)點(diǎn)連接上頭結(jié)點(diǎn)即可诫肠；然后每次都走m-2步(注意不是m-1步栋豫，因?yàn)槲覀円獎(jiǎng)h除掉第m-1個(gè)結(jié)點(diǎn)丧鸯，所以走到第m-2個(gè)結(jié)點(diǎn)即可),然后使第m-2步的node丛肢，node.next=node.next.next，然后將node后移一位node = node.next即可穆刻，如此循環(huán)蛹批，循環(huán)中止的條件就是node.next = node,即只剩下一個(gè)結(jié)點(diǎn)了，然后輸出這個(gè)結(jié)點(diǎn)的值试躏，即可颠蕴；
代碼如下
public class Solution {
//構(gòu)造鏈表類
private class ListNode{
int val = 0;
ListNode next = null;
ListNode(int val){
this.val = val;
}
}
public int LastRemaining_Solution(int n, int m) {
//兩種特殊情況
if(n==0){
return -1;
}
if(n==1){
return 0;
}
//構(gòu)造環(huán)形鏈表
ListNode pHead = new ListNode(0);
ListNode cur = pHead;
for(int i = 1;i<n;i++){
ListNode tmp = new ListNode(i);
cur.next = tmp;
cur = cur.next;
}
//首尾相連
cur.next = pHead;
cur = cur.next;
//一個(gè)個(gè)刪除結(jié)點(diǎn)，知道cur.next==cur為止
while(cur.next!=cur){
int cnt = 0;
//記得要?jiǎng)h除結(jié)點(diǎn)寡键，則走到倒數(shù)第二個(gè)結(jié)點(diǎn)即可
while(cnt<m-2){
cur = cur.next;
cnt++;
}
//先刪除結(jié)點(diǎn)
cur.next = cur.next.next;
//走到下一個(gè)結(jié)點(diǎn)
cur = cur.next;
}
return cur.val;
}
}
47.求1+2+3+......+n
求1+2+3+...+n西轩，要求不能使用乘除法藕畔、for注服、while、if瞭郑、else可很、switch、case等關(guān)鍵字及條件判斷語(yǔ)句（A?B:C）凰浮。
第一反應(yīng)不能用循環(huán)啊這些都無(wú)所謂我抠，因?yàn)榭梢杂眠f歸很輕松解決苇本，但不能用if，如何設(shè)立循環(huán)中止條件呢菜拓，遞歸到n==0的時(shí)候遞歸結(jié)束瓣窄，看了大神的代碼后發(fā)現(xiàn)可以用與運(yùn)算的短路性來(lái)解決，即如果前面的判斷條件不為真纳鼎，那么也就不執(zhí)行下一句了俺夕；意義何在呢？就是如果沒(méi)有一個(gè)中止條件贱鄙，那么函數(shù)就是在遞歸到0之后繼續(xù)執(zhí)行-1,-2,-3.......無(wú)窮無(wú)盡的死循環(huán)，但當(dāng)有了中止條件之后，中止到n==0的時(shí)候就停止，這個(gè)條件就放在與運(yùn)算的前面一句引有。
代碼如下
public class Solution {
public int Sum_Solution(int n) {
int sum = n;
//這個(gè)boolean變量的意義只在于里面的判斷和執(zhí)行 sum+=這一操作
boolean a = (n>0)&&((sum+=Sum_Solution(n-1))>0);
return sum;
}
}
48.不用加減乘除做加法
寫一個(gè)函數(shù)导帝，求兩個(gè)整數(shù)之和荞雏，要求在函數(shù)體內(nèi)不得使用+、-、*还绘、/四則運(yùn)算符號(hào)。
這題考察兩點(diǎn)：1.學(xué)習(xí)遷移能力；2.按位操作
所謂考察學(xué)習(xí)遷移能力，就是我們平時(shí)計(jì)算十進(jìn)制的加法的時(shí)候是怎么做的呢？
以15+38為例珍促，一位位計(jì)算計(jì)算相加的結(jié)果和進(jìn)位仁卷，例如5+8在這一位上結(jié)果為3，但是進(jìn)位到上一位為1,1+3結(jié)果為4，進(jìn)位為1，所以結(jié)果為5垛叨，最終結(jié)果為53;即每位結(jié)果+進(jìn)位結(jié)果等于最終結(jié)果，再擴(kuò)展下456+789珍手，我們先計(jì)算每位結(jié)果稚补，再計(jì)算進(jìn)位乍惊，每位結(jié)果為0135，進(jìn)位結(jié)果為1110（因?yàn)檫M(jìn)位是往前擴(kuò)展的，這里在程序中用位移運(yùn)算符即可）涂佃，相加得到1245，與最終結(jié)果相符；
那么遷移到二進(jìn)制中，我們就要靈活運(yùn)用位運(yùn)算來(lái)得到兩個(gè)結(jié)果：1.每位相加得到的結(jié)果；2.進(jìn)位結(jié)果氨肌，我們一步步來(lái)分析
1.每位相加的結(jié)果考婴，注意這里的相加結(jié)果指的是不考慮進(jìn)位屁使，隨便寫個(gè)10110和11010酬蹋，相加結(jié)果為01100，我們仔細(xì)來(lái)分析下0+0-->0,0+1-->1,1+1-->0朗涩，相同為0覆履，不同為1召廷，這是什么操作？Bingo!異或！所以第一步應(yīng)該用num1^num2劫扒；
2.考慮進(jìn)位結(jié)果沟饥，10110和11010,記得進(jìn)位要往前進(jìn)哦，10010(0),只有1和1的時(shí)候才產(chǎn)生進(jìn)位糜颠，這是什么操作？Bingo!與操作袱贮，所以第二部應(yīng)該用(num1&num2)<<1;
我們相加01100和100100得到110000鲤氢，驗(yàn)證下10110+11010=110000,證明我們的分析是正確的搀擂！
所以代碼如下
public class Solution {
public int Add(int num1,int num2) {
return ((num1&num2)<<1)+(num1^num2);
}
}
49.把字符串轉(zhuǎn)化成整數(shù)
將一個(gè)字符串轉(zhuǎn)換成一個(gè)整數(shù)，要求不能使用字符串轉(zhuǎn)換整數(shù)的庫(kù)函數(shù)卷玉。 數(shù)值為0或者字符串不是一個(gè)合法的數(shù)值則返回0
這個(gè)題就是把字符串中的每一位都轉(zhuǎn)化成整數(shù)然后相加即可哨颂，注意不能用庫(kù)函數(shù)，所以我們需要用(int)char-(int)'0'來(lái)計(jì)算每一位的數(shù)值
代碼如下
public class Solution {
public int StrToInt(String str) {
if (str == null || str.length() == 0)
return 0;
boolean isNegative = str.charAt(0) == '-';
int ret = 0;
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (i == 0 && (c == '+' || c == '-')) /* 符號(hào)判定 */
continue;
if (c < '0' || c > '9') /* 非法輸入 */
return 0;
ret = ret * 10 + (c - '0');
}
return isNegative ? -ret : ret;
}
}
50.數(shù)組中重復(fù)的數(shù)字
在一個(gè)長(zhǎng)度為n的數(shù)組里的所有數(shù)字都在0到n-1的范圍內(nèi)相种。 數(shù)組中某些數(shù)字是重復(fù)的威恼，但不知道有幾個(gè)數(shù)字是重復(fù)的。
也不知道每個(gè)數(shù)字重復(fù)幾次。
請(qǐng)找出數(shù)組中任意一個(gè)重復(fù)的數(shù)字箫措。
例如腹备，如果輸入長(zhǎng)度為7的數(shù)組{2,3,1,0,2,5,3}，那么對(duì)應(yīng)的輸出是第一個(gè)重復(fù)的數(shù)字2斤蔓。
用hashmap解決
代碼如下
import java.util.*;
public class Solution {
// Parameters:
// numbers: an array of integers
// length: the length of array numbers
// duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
// Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
// 這里要特別注意~返回任意重復(fù)的一個(gè)植酥，賦值duplication[0]
// Return value: true if the input is valid, and there are some duplications in the array number
// otherwise false
public boolean duplicate(int numbers[],int length,int [] duplication) {
if(length<=0||numbers==null){
return false;
}
HashMap<Integer,Integer> hashmap = new HashMap<>();
//統(tǒng)計(jì)每個(gè)數(shù)出現(xiàn)的次數(shù)
for(int num:numbers){
if(hashmap.containsKey(num)){
hashmap.put(num,hashmap.get(num)+1);
}else{
hashmap.put(num,1);
}
}
//檢查有出現(xiàn)次數(shù)大于等于兩次的就賦值并輸出true
for(int key:hashmap.keySet()){
if(hashmap.get(key)>=2){
duplication[0]=key;
return true;
}
}
return false;
}
}
