46.孩子们的游戏
每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。
HF作为牛客的资深元老,自然也准备了一些小游戏。
其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。
然后,他随机指定一个数m,让编号为0的小朋友开始报数。
每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。
请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)
如果没有小朋友，请返回-1
这个题考察的就是抽象建模能力，我们可以把最原始的n个小朋友构造成一个环形链表，就是普通的单链表的尾结点连接上头结点即可；然后每次都走m-2步(注意不是m-1步，因为我们要删除掉第m-1个结点，所以走到第m-2个结点即可),然后使第m-2步的node，node.next=node.next.next，然后将node后移一位node = node.next即可，如此循环，循环中止的条件就是node.next = node,即只剩下一个结点了，然后输出这个结点的值，即可；
代码如下
public class Solution {
//构造链表类
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;
}
//构造环形链表
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;
//一个个删除结点，知道cur.next==cur为止
while(cur.next!=cur){
int cnt = 0;
//记得要删除结点，则走到倒数第二个结点即可
while(cnt<m-2){
cur = cur.next;
cnt++;
}
//先删除结点
cur.next = cur.next.next;
//走到下一个结点
cur = cur.next;
}
return cur.val;
}
}
47.求1+2+3+......+n
求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
第一反应不能用循环啊这些都无所谓，因为可以用递归很轻松解决，但不能用if，如何设立循环中止条件呢，递归到n==0的时候递归结束，看了大神的代码后发现可以用与运算的短路性来解决，即如果前面的判断条件不为真，那么也就不执行下一句了；意义何在呢？就是如果没有一个中止条件，那么函数就是在递归到0之后继续执行-1,-2,-3.......无穷无尽的死循环，但当有了中止条件之后，中止到n==0的时候就停止，这个条件就放在与运算的前面一句。
代码如下
public class Solution {
public int Sum_Solution(int n) {
int sum = n;
//这个boolean变量的意义只在于里面的判断和执行 sum+=这一操作
boolean a = (n>0)&&((sum+=Sum_Solution(n-1))>0);
return sum;
}
}
48.不用加减乘除做加法
写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
这题考察两点：1.学习迁移能力；2.按位操作
所谓考察学习迁移能力，就是我们平时计算十进制的加法的时候是怎么做的呢？
以15+38为例，一位位计算计算相加的结果和进位，例如5+8在这一位上结果为3，但是进位到上一位为1,1+3结果为4，进位为1，所以结果为5，最终结果为53;即每位结果+进位结果等于最终结果，再扩展下456+789，我们先计算每位结果，再计算进位，每位结果为0135，进位结果为1110（因为进位是往前扩展的，这里在程序中用位移运算符即可），相加得到1245，与最终结果相符；
那么迁移到二进制中，我们就要灵活运用位运算来得到两个结果：1.每位相加得到的结果；2.进位结果，我们一步步来分析
1.每位相加的结果，注意这里的相加结果指的是不考虑进位，随便写个10110和11010，相加结果为01100，我们仔细来分析下0+0-->0,0+1-->1,1+1-->0，相同为0，不同为1，这是什么操作？Bingo!异或！所以第一步应该用num1^num2；
2.考虑进位结果，10110和11010,记得进位要往前进哦，10010(0),只有1和1的时候才产生进位，这是什么操作？Bingo!与操作，所以第二部应该用(num1&num2)<<1;
我们相加01100和100100得到110000，验证下10110+11010=110000,证明我们的分析是正确的！
所以代码如下
public class Solution {
public int Add(int num1,int num2) {
return ((num1&num2)<<1)+(num1^num2);
}
}
49.把字符串转化成整数
将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0
这个题就是把字符串中的每一位都转化成整数然后相加即可，注意不能用库函数，所以我们需要用(int)char-(int)'0'来计算每一位的数值
代码如下
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 == '-')) /* 符号判定 */
continue;
if (c < '0' || c > '9') /* 非法输入 */
return 0;
ret = ret * 10 + (c - '0');
}
return isNegative ? -ret : ret;
}
}
50.数组中重复的数字
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。
也不知道每个数字重复几次。
请找出数组中任意一个重复的数字。
例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字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++
// 这里要特别注意~返回任意重复的一个，赋值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<>();
//统计每个数出现的次数
for(int num:numbers){
if(hashmap.containsKey(num)){
hashmap.put(num,hashmap.get(num)+1);
}else{
hashmap.put(num,1);
}
}
//检查有出现次数大于等于两次的就赋值并输出true
for(int key:hashmap.keySet()){
if(hashmap.get(key)>=2){
duplication[0]=key;
return true;
}
}
return false;
}
}
