剑指offer 46-50

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;
    }
}