第49題：把字符串轉(zhuǎn)換成整數(shù)
難易度：?
題目描述:
將一個(gè)字符串轉(zhuǎn)換成一個(gè)整數(shù)，要求不能使用字符串轉(zhuǎn)換整數(shù)的庫(kù)函數(shù)。
數(shù)值為0或者字符串不是一個(gè)合法的數(shù)值則返回0
輸入一個(gè)字符串,包括數(shù)字字母符號(hào),可以為空
如果是合法的數(shù)值表達(dá)則返回該數(shù)字，否則返回0
示例:
輸入
"+2147483647"
輸出
2147483647
輸入
"1a33"
輸出
0
這個(gè)代碼寫(xiě)的很爛上沐，沒(méi)時(shí)間改了，二刷的時(shí)候一定改進(jìn) ( - - )
需要注意幾點(diǎn)：
- 允許有正負(fù)號(hào)
- 注意越界
代碼如下：
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題：數(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毛嫉。
本題有兩種思路：
- 用空間換時(shí)間
不難想到诽俯，本題使用哈希表這種數(shù)據(jù)結(jié)構(gòu)，就可以很快找到重復(fù)的數(shù)字承粤，代碼如下：
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++
// 這里要特別注意~返回任意重復(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) {
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;
}
}
- 不使用額外的數(shù)據(jù)結(jié)構(gòu)，即要求額外空間復(fù)雜度為O(1),概念上屬于拿時(shí)間換空間的做法
類似二分法的思路:將n個(gè)數(shù)字中間數(shù)字m分為兩個(gè)部分辛臊，前一半為0～m,后一半為m+1～n仙粱。如果0～m的數(shù)字的數(shù)目超過(guò)了m,那么這一版的區(qū)間一定包含重復(fù)的數(shù)字，否則彻舰，量一般m+1 ~ n的區(qū)間里伐割，一定包含重復(fù)的數(shù)字。我們可以一直講包含重復(fù)數(shù)字的區(qū)間一分為二淹遵，直到找到重復(fù)的數(shù)字為止口猜，因?yàn)槎植呗缘臅r(shí)間復(fù)雜度為O(logn),每次我們還要遍歷數(shù)組，時(shí)間復(fù)雜度為O(nlogn),但是額外空間復(fù)雜度則為O(1),所以這是一種時(shí)間換空間的策略透揣。
代碼如下：
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(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;
}
}
