每日一题之《剑指offer》49,50题

第49题：把字符串转换成整数

难易度：⭐

题目描述:
将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 
数值为0或者字符串不是一个合法的数值则返回0
输入一个字符串,包括数字字母符号,可以为空
如果是合法的数值表达则返回该数字，否则返回0
示例:
输入
"+2147483647"
输出
2147483647

输入
"1a33"
输出
0

这个代码写的很烂，没时间改了，二刷的时候一定改进 ( - - )
需要注意几点：

允许有正负号
注意越界

代码如下：

public class Solution {
    public int StrToInt(String str) {
        if(str == null || str.length() == 0){
            return 0;
        }
        char[] chs = str.toCharArray();
        int len = str.length();
        int lenTemp = len;
        boolean isPositive = true;
        long res = 0L;
        for(int i = 0;i < len;i++){
            if(i == 0){
                if(chs[i] == '-'){
                    isPositive = false;
                    lenTemp--;
                }else if(chs[i] == '+'){
                    lenTemp--;
                }else{
                    if(chs[i] < '0' || chs[i] > '9'){
                        return 0;
                    }else{
                        res += (int)((chs[i] - '0') * Math.pow(10,lenTemp - 1));
                        lenTemp--;
                    }
                    
                }
            }else{
                if(chs[i] < '0' || chs[i] > '9'){
                        return 0;
                }else{
                    res += (int)((chs[i] - '0') * Math.pow(10,lenTemp - 1));
                    lenTemp--;
                }
            }
        }
        if(isPositive){
            return res > Integer.MAX_VALUE ? 0 : (int)res;
        }else{
            return -res < Integer.MIN_VALUE ? 0 : (int)(-1 * res);
        }
    }
}

第50题：数组中重复的数字

难易度：⭐⭐

题目描述
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 
数组中某些数字是重复的，但不知道有几个数字是重复的。
也不知道每个数字重复几次。
请找出数组中任意一个重复的数字。
 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

本题有两种思路：

用空间换时间
不难想到，本题使用哈希表这种数据结构，就可以很快找到重复的数字，代码如下：

import java.util.HashSet;
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) {
        HashSet<Integer> set = new HashSet<>();
        for(int i = 0;i < length;i++){
            if(set.contains(numbers[i])){
                duplication[0] = numbers[i];
                return true;
            }else{
                set.add(numbers[i]);
            }
        }
        return false;
    }
}

不使用额外的数据结构，即要求额外空间复杂度为O(1),概念上属于拿时间换空间的做法
类似二分法的思路:将n个数字中间数字m分为两个部分，前一半为0～m,后一半为m+1～n。如果0～m的数字的数目超过了m,那么这一版的区间一定包含重复的数字，否则，量一般m+1 ~ n的区间里，一定包含重复的数字。我们可以一直讲包含重复数字的区间一分为二，直到找到重复的数字为止，因为二分策略的时间复杂度为O(logn),每次我们还要遍历数组，时间复杂度为O(nlogn),但是额外空间复杂度则为O(1),所以这是一种时间换空间的策略。
代码如下：

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(numbers == null){
            return false;
        }
        int start = 0;
        int end = length - 1;
        while(end >= start){
            int middle = ((end - start) >> 1) + start;
            int count = count(numbers,length,start,middle);
            if(end == start){
                if(count > 1){
                    duplication[0] = start;
                    return true;
                }else{
                    break;
                }
            }
            if(count > (middle - start + 1)){
                end = middle;
            }else if(count == (middle - start + 1)){
                start = start + 1;
            }else{
                start = middle + 1;
            }
        }
        return false;
    }
    
    public static int count(int numbers[],int length,int start,int middle){
        if(numbers == null){
            return 0;
        }
        int res = 0;
        for(int i = 0;i < length;i++){
            if(numbers[i] >= start && numbers[i] <= middle){
                res++;
            }
        }
        return res;
    }
}