- 7.整數(shù)反轉(zhuǎn)
- 12.整數(shù)轉(zhuǎn)羅馬數(shù)字
- 13.羅馬數(shù)字轉(zhuǎn)整數(shù)
- 29.兩數(shù)相除
- 50.Pow(x,y)
- 60.第k個(gè)排列
- 231.2的冪
- 371.兩整數(shù)之和
- 754.到達(dá)終點(diǎn)數(shù)字
7
整數(shù)反轉(zhuǎn)
描述
給出一個(gè) 32 位的有符號(hào)整數(shù)泌辫，你需要將這個(gè)整數(shù)中每位上的數(shù)字進(jìn)行反轉(zhuǎn)柠衍。
示例 1:
輸入: 123
輸出: 321
示例 2:
輸入: -123
輸出: -321
示例 3:
輸入: 120
輸出: 21
注意:
假設(shè)我們的環(huán)境只能存儲(chǔ)得下 32 位的有符號(hào)整數(shù)乳丰，
則其數(shù)值范圍為 [?2^31, 2^31 ? 1]尺栖。請(qǐng)根據(jù)這個(gè)假設(shè)，如果反轉(zhuǎn)后整數(shù)溢出那么就返回 0补疑。
分析
需要注意的是班利，整型溢出的處理
實(shí)現(xiàn)
解法1：
public int reverse(int x) {
long reX = 0;
long num = x;
while (num!=0){
reX = reX*10+num%10;
num/=10;
}
if (reX>Integer.MAX_VALUE||reX<Integer.MIN_VALUE){
return 0;
}
return (int) reX;
}
解法2：
//使用局部變量的解法
public int reverse(int x){
int num = x;
int reverseNum = 0;
while (num!=0){
//確保newReverseNum不會(huì)整型溢出
if (reverseNum>Integer.MAX_VALUE/10||reverseNum<Integer.MIN_VALUE/10){
return 0;
}
int newReverseNum = 10*reverseNum+num%10;
reverseNum = newReverseNum;
num/=10;
}
return reverseNum;
}
12
整數(shù)轉(zhuǎn)羅馬數(shù)字
描述
羅馬數(shù)字包含以下七種字符： I洞豁， V窗看， X简卧， L，C烤芦，D 和 M。
字符 數(shù)值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如析校， 羅馬數(shù)字 2 寫做 II 构罗，即為兩個(gè)并列的 1铜涉。12 寫做 XII ，即為 X + II 遂唧。 27 寫做 XXVII, 即為 XX + V + II 芙代。
通常情況下，羅馬數(shù)字中小的數(shù)字在大的數(shù)字的右邊盖彭。但也存在特例纹烹，例如 4 不寫做 IIII，而是 IV召边。數(shù)字 1 在數(shù)字 5 的左邊铺呵，所表示的數(shù)等于大數(shù) 5 減小數(shù) 1 得到的數(shù)值 4 。同樣地隧熙，數(shù)字 9 表示為 IX片挂。這個(gè)特殊的規(guī)則只適用于以下六種情況：
I 可以放在 V (5) 和 X (10) 的左邊，來表示 4 和 9贞盯。
X 可以放在 L (50) 和 C (100) 的左邊音念，來表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左邊躏敢，來表示 400 和 900闷愤。
給定一個(gè)整數(shù)，將其轉(zhuǎn)為羅馬數(shù)字件余。輸入確保在 1 到 3999 的范圍內(nèi)讥脐。
示例 1:
輸入: 3
輸出: "III"
示例 2:
輸入: 4
輸出: "IV"
示例 3:
輸入: 9
輸出: "IX"
示例 4:
輸入: 58
輸出: "LVIII"
解釋: L = 50, V = 5, III = 3.
示例 5:
輸入: 1994
輸出: "MCMXCIV"
解釋: M = 1000, CM = 900, XC = 90, IV = 4.
分析
10以內(nèi)的羅馬數(shù)字都由V(5)、IV(4)蛾扇、I(1)組成攘烛，所以同理拓展到10-100和100-1000，可構(gòu)造出1-3999之間的整數(shù)镀首。
實(shí)現(xiàn)
public String intToRoman(int num) {
//設(shè)置兩個(gè)數(shù)組 使得數(shù)字和符號(hào)一一對(duì)應(yīng)
String[] dict={"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
int[] nums={1000,900,500,400,100,90,50,40,10,9,5,4,1};
StringBuilder sb = new StringBuilder();
for (int i = 0; i<nums.length; i++) {
//從大到小搜索可以匹配的數(shù)字坟漱，每次使用盡量較大的數(shù)字
while (num>=nums[i]){
num-=nums[i];
sb.append(dict[i]);
}
}
//從左向右添加符號(hào)
return sb.toString();
}
13
羅馬數(shù)字轉(zhuǎn)整數(shù)
描述
羅馬數(shù)字包含以下七種字符: I， V更哄， X芋齿， L，C成翩，D 和 M觅捆。
字符 數(shù)值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 羅馬數(shù)字 2 寫做 II 麻敌，即為兩個(gè)并列的 1栅炒。12 寫做 XII ，即為 X + II 。 27 寫做 XXVII, 即為 XX + V + II 赢赊。
通常情況下乙漓，羅馬數(shù)字中小的數(shù)字在大的數(shù)字的右邊。但也存在特例释移，例如 4 不寫做 IIII叭披，而是 IV。數(shù)字 1 在數(shù)字 5 的左邊玩讳，所表示的數(shù)等于大數(shù) 5 減小數(shù) 1 得到的數(shù)值 4 涩蜘。同樣地，數(shù)字 9 表示為 IX熏纯。這個(gè)特殊的規(guī)則只適用于以下六種情況：
I 可以放在 V (5) 和 X (10) 的左邊同诫，來表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左邊豆巨，來表示 40 和 90剩辟。
C 可以放在 D (500) 和 M (1000) 的左邊，來表示 400 和 900往扔。
給定一個(gè)羅馬數(shù)字贩猎，將其轉(zhuǎn)換成整數(shù)。輸入確保在 1 到 3999 的范圍內(nèi)萍膛。
示例 1:
輸入: "III"
輸出: 3
示例 2:
輸入: "IV"
輸出: 4
示例 3:
輸入: "IX"
輸出: 9
示例 4:
輸入: "LVIII"
輸出: 58
解釋: L = 50, V= 5, III = 3.
示例 5:
輸入: "MCMXCIV"
輸出: 1994
解釋: M = 1000, CM = 900, XC = 90, IV = 4.
實(shí)現(xiàn)
public int romanToInt(String s) {
if (s==null||s.length()==0){
return 0;
}
char[] dict={'M','D','C','L','X','V','I'};
int[] nums={1000,500,100,50,10,5,1};
Map<Character,Integer> map = new HashMap<>();
for (int i = 0; i < dict.length; i++) {
map.put(dict[i],nums[i]);
}
int res=0;
//從左向右遍歷吭服，當(dāng)前的符號(hào)的值不小于右邊符號(hào)的值的時(shí)候加上當(dāng)前值
//反之，小于的時(shí)候蝗罗，則減去當(dāng)前值
for (int i = 0; i < s.length()-1; i++) {
char cur = s.charAt(i);
char right = s.charAt(i + 1);
if (map.get(cur)>=map.get(right)){
res+=map.get(cur);
}else {
res-=map.get(cur);
}
}
res+=map.get(s.charAt(s.length()-1));
return res;
}
29*
描述
給定兩個(gè)整數(shù)艇棕，被除數(shù) dividend 和除數(shù) divisor。將兩數(shù)相除串塑，要求不使用乘法沼琉、除法和 mod 運(yùn)算符。
返回被除數(shù) dividend 除以除數(shù) divisor 得到的商桩匪。
示例 1:
輸入: dividend = 10, divisor = 3
輸出: 3
示例 2:
輸入: dividend = 7, divisor = -3
輸出: -2
說明:
被除數(shù)和除數(shù)均為 32 位有符號(hào)整數(shù)打瘪。
除數(shù)不為 0。
假設(shè)我們的環(huán)境只能存儲(chǔ) 32 位有符號(hào)整數(shù)傻昙，其數(shù)值范圍是 [?2^31, 2^31 ? 1]闺骚。本題中，如果除法結(jié)果溢出妆档，則返回 2^31 ? 1僻爽。
實(shí)現(xiàn)
//時(shí)間復(fù)雜度：O(log(N))
public int divide(int dividend, int divisor) {
if (dividend==0){
return 0;
}
long ldiv = dividend;
long ldsor = divisor;
boolean flag=false;
if ((ldiv<0&&ldsor>0)||(dividend>0&&ldsor<0)){
flag=true; //-1
}
ldiv=Math.abs(ldiv);
ldsor=Math.abs(ldsor);
long res = div(ldiv, ldsor);
if (flag){
res=-res;
}
if (res>Integer.MAX_VALUE||res<Integer.MIN_VALUE){
return Integer.MAX_VALUE;
}
return (int) res;
}
//除法的輔助函數(shù)
//利用加法去求解 除法
private long div(long dividend,long divisor){
//遞歸終止條件
if (dividend<divisor){
return 0;
}
long sum = divisor;
//倍數(shù)
long count = 1;
//二分搜索
while (sum+sum<=dividend){
sum+=sum;
count+=count;
}
return count+div(dividend-sum,divisor);
}
60
描述
給出集合 [1,2,3,…,n]，其所有元素共有 n! 種排列贾惦。
按大小順序列出所有排列情況纺念，并一一標(biāo)記，當(dāng) n = 3 時(shí), 所有排列如下：
"123"
"132"
"213"
"231"
"312"
"321"
給定 n 和 k吃谣，返回第 k 個(gè)排列。
說明：
給定 n 的范圍是 [1, 9]绞惦。
給定 k 的范圍是[1, n!]。
示例 1:
輸入: n = 3, k = 3
輸出: "213"
示例 2:
輸入: n = 4, k = 9
輸出: "2314"
分析
方法一：
可以使用回溯法洋措，如同求全排列一樣，但是效率很低杰刽。
方法二：
通過數(shù)學(xué)推導(dǎo)法菠发，利用數(shù)學(xué)推導(dǎo), 對(duì)于n=4, k=15 找到k=15排列的過程:
1 + 對(duì)2,3,4的全排列 (3!個(gè))
2 + 對(duì)1,3,4的全排列 (3!個(gè)) 3, 1 + 對(duì)2,4的全排列(2!個(gè))
3 + 對(duì)1,2,4的全排列 (3!個(gè))-------> 3, 2 + 對(duì)1,4的全排列(2!個(gè))-------> 3, 2, 1 + 對(duì)4的全排列(1!個(gè))-------> 3214
4 + 對(duì)1,2,3的全排列 (3!個(gè)) 3, 4 + 對(duì)1,2的全排列(2!個(gè)) 3, 2, 4 + 對(duì)1的全排列(1!個(gè))
確定第一位:
k = 14(從0開始計(jì)數(shù))
index = k / (n-1)! = 2, 是候選數(shù)字（1,2,3,4）中的第3個(gè)，說明第15個(gè)數(shù)的第一位是3
更新k
k = k - index*(n-1)! = 2
確定第二位:
k = 2
index = k / (n-2)! = 1, 是候選數(shù)字（1,2,4）中的第2個(gè)贺嫂，說明第15個(gè)數(shù)的第二位是2
更新k
k = k - index*(n-2)! = 0
確定第三位:
k = 0
index = k / (n-3)! = 0, 是候選數(shù)字（1,4）中的第1個(gè)滓鸠，說明第15個(gè)數(shù)的第三位是1
更新k
k = k - index*(n-3)! = 0
確定第四位:
k = 0
index = k / (n-4)! = 0, 是候選數(shù)字（4）中的第1個(gè)，說明第15個(gè)數(shù)的第四位是4
最終確定n=4時(shí)第15個(gè)數(shù)為3214
實(shí)現(xiàn)
回溯法+剪枝：
private boolean[] used;
private int[] memo;
//回溯法+剪枝
public String getPermutation(int n, int k) {
memo=new int[n+1];
used=new boolean[n+1];
factorial(n,memo);
int[] nums=new int[n];
for (int i = 0; i < n; i++) {
nums[i]=i+1;
}
return generate(nums,0,n,k,"");
}
private String generate(int[] nums,int index,int n,int k,String s){
if (index==n){
return s;
}
//獲取當(dāng)前節(jié)點(diǎn)中葉子結(jié)點(diǎn)的個(gè)數(shù)
int ps=memo[n-index-1];
for (int i = 0; i < n; i++) {
if (used[i]) continue;
//若當(dāng)前葉子總數(shù)小于k直接跳過
if (ps<k){
k-=ps;
continue;
}
s=s+nums[i];
used[i]=true;
return generate(nums,index+1,n,k,s);
}
return "";
}
private void factorial(int n,int[] memo){
int f=1;
memo[0]=1;
for (int i = 1; i <=n; i++) {
f*=i;
memo[i]=f;
}
}
數(shù)學(xué)推導(dǎo)法：
public String getPermutation(int n, int k){
//用來記錄階乘
int[] memo=new int[n+1];
//候選數(shù)字集合
List<Integer> cands=new ArrayList<>();
k-=1;
StringBuilder sb = new StringBuilder();
factorial(n,memo,cands);
//
for (int i = n-1; i >=0; i--) {
//待加入的候選數(shù)字
int index=k/memo[i];
sb.append(cands.remove(index));
k-=index*memo[i];
}
return sb.toString();
}
//預(yù)處理第喳，先計(jì)算出階乘
private void factorial(int n,int[] memo,List<Integer> cands){
int f=1;
memo[0]=1;
for (int i = 1; i <=n ; i++) {
cands.add(i);
f*=i;
memo[i]=f;
}
}
50
Pow(x,y)
描述
實(shí)現(xiàn) pow(x, n) 糜俗，即計(jì)算 x 的 n 次冪函數(shù)。
示例 1:
輸入: 2.00000, 10
輸出: 1024.00000
示例 2:
輸入: 2.10000, 3
輸出: 9.26100
示例 3:
輸入: 2.00000, -2
輸出: 0.25000
解釋: 2-2 = 1/22 = 1/4 = 0.25
說明:
-100.0 < x < 100.0
n 是 32 位有符號(hào)整數(shù)曲饱，其數(shù)值范圍是 [?231, 231 ? 1] 悠抹。
分析
使用二分查找
實(shí)現(xiàn)
//時(shí)間復(fù)雜度：O（logN）
public double myPow(double x, int n) {
if (n==0){
return 1.0;
}
if(n==1)
return x;
if(n==-1)
return 1/x;
//先折半
double half = myPow(x,n/2);
//若n為偶數(shù)則將折半值直接相乘即可
if (n%2==0) return half*half;
//n%2==1:若n為奇數(shù)的情況
//要分成n為正數(shù)和負(fù)數(shù)的情況來討論
if (n<0) return half*half/x;
return half*half*x;
}
69
X的平方根
描述
實(shí)現(xiàn) int sqrt(int x) 函數(shù)。
計(jì)算并返回 x 的平方根扩淀，其中 x 是非負(fù)整數(shù)楔敌。
由于返回類型是整數(shù)，結(jié)果只保留整數(shù)的部分驻谆，小數(shù)部分將被舍去卵凑。
示例 1:
輸入: 4
輸出: 2
示例 2:
輸入: 8
輸出: 2
說明: 8 的平方根是 2.82842...,
由于返回類型是整數(shù)，小數(shù)部分將被舍去胜臊。
實(shí)現(xiàn)
//使用二分查找的方法
public int mySqrt(int x) {
int l=0,h=x;
while (l<=h){
int mid=l+(h-l)/2;
//為了避免整型的溢出勺卢，
if (mid<x/mid){
l=mid+1;
}else if (mid==x/mid){
return mid;
}else {
h=mid-1;
}
}
return h;
}
754**
描述
在一根無限長的數(shù)軸上，你站在0的位置象对。終點(diǎn)在target的位置黑忱。
每次你可以選擇向左或向右移動(dòng)。第 n 次移動(dòng)（從 1 開始）织盼，可以走 n 步杨何。
返回到達(dá)終點(diǎn)需要的最小移動(dòng)次數(shù)。
示例 1:
輸入: target = 3
輸出: 2
解釋:
第一次移動(dòng)沥邻，從 0 到 1 危虱。
第二次移動(dòng)，從 1 到 3 唐全。
示例 2:
輸入: target = 2
輸出: 3
解釋:
第一次移動(dòng)埃跷，從 0 到 1 蕊玷。
第二次移動(dòng)，從 1 到 -1 弥雹。
第三次移動(dòng)垃帅，從 -1 到 2 。
注意:
target是在[-10^9, 10^9]范圍中的非零整數(shù)剪勿。
分析
分析 首先考慮一種比較極端的情況 即一直向正方向移動(dòng)n步 贸诚，剛好達(dá)到target，那么target的值就等于前n步的和 厕吉，也就是1+2+.....+n = n*(n+1)/2
如果n(n+1)/2>target ,那么所需要的步數(shù)肯定要比n多酱固，而且肯定有向左走的步子，也就是求和的時(shí)候肯定是有負(fù)數(shù)的头朱，至于哪個(gè)或者哪些個(gè)為負(fù)运悲，下面開始討論：
- n(n+1)/2 - target 為偶數(shù)時(shí)，所以要想到達(dá) target 需要向左走 n(n+1)/2 - target 偶數(shù)步 项钮，就是把前n項(xiàng)中第( n(n+1)/2 - target)/2 步變?yōu)樨?fù)號(hào)就行了班眯，總步數(shù)不用增加
- 當(dāng)n(n+1)/2 - target 為奇數(shù)時(shí)，就要分類討論：
- 若n為奇數(shù)烁巫，那n+1就是偶數(shù) 無論向左還是向右 都不會(huì)產(chǎn)生一個(gè)奇數(shù)的差來因此需要再走一步署隘，故要n+2步；
- 若n為偶數(shù)程拭，n+1則為奇數(shù)定踱，可以產(chǎn)生一個(gè)奇數(shù)的差，故要n+1步
實(shí)現(xiàn)
public int reachNumber(int target) {
int t=Math.abs(target);
if(t==0){
return 0;
}
int i=0;
while(i*(i+1)<2*t){
i++;
}
int sum=i*(i+1)/2;
if(sum==t){
return i;
}
//若差值為偶數(shù)恃鞋，則令1,2,...,i之間是一個(gè)為負(fù)數(shù)即可
if((sum-t)%2==0){
return i;
}else{
//若差值為奇數(shù)崖媚，需要向左移動(dòng)奇數(shù)位
//若i為偶數(shù)，那么i+1為奇數(shù)恤浪，可以產(chǎn)生一個(gè)奇數(shù)差畅哑；
if(i%2==0){
return i+1;
}else{
//若i為奇數(shù)，那么i+1為偶數(shù)水由，i+2為奇數(shù)荠呐，產(chǎn)生奇數(shù)差，必須需要i+2步
return i+2;
}
}
}
位運(yùn)算
位運(yùn)算即是在位級(jí)別進(jìn)行操作的技術(shù)砂客，合適的位運(yùn)算能夠幫助我們得到更快地運(yùn)算速度與更小的內(nèi)存使用泥张。下面列舉一些常見使用方法：
- 測(cè)試第 k 位:
s & (1 << k) - 設(shè)置第 k 位:
s |= (1 << k) - 第 k 位置零:
s &= ~(1 << k) - 切換第 k 位值:
s ^= ~(1 << k) - 乘以 2n:
s << n - 除以 2n:
s >> n - 交集:
s & t - 并集:
s | t - 減法:
s & ~t - 交換
x = x ^ y ^ (y = x) - 取出最小非 0 位（Extract lowest set bit）:
s & (-s) - 取出最小 0 位（Extract lowest unset bit）:
~s & (s + 1) - 交換值:
x ^= y; y ^= x; x ^= y;
231
2的冪
描述
給定一個(gè)整數(shù)，編寫一個(gè)函數(shù)來判斷它是否是 2 的冪次方鞠值。
示例 1:
輸入: 1
輸出: true
解釋: 20 = 1
示例 2:
輸入: 16
輸出: true
解釋: 24 = 16
示例 3:
輸入: 218
輸出: false
分析
使用位運(yùn)算媚创，因?yàn)?的次冪的二進(jìn)制表示中，最高位為1彤恶，其余位均為0钞钙；例如：n=4（100）鳄橘，n-1=3(011),
將n和n-1做與運(yùn)算結(jié)果為0，通過這個(gè)性質(zhì)來判斷一個(gè)數(shù)是否為2的次冪芒炼，即可瘫怜。
實(shí)現(xiàn)
//位運(yùn)算
public boolean isPowerOfTwo(int n){
if (n<=0){
return false;
}
//例如：1000 & 0111 = 0
return (n&(n-1))==0;
}
371
兩整數(shù)之和
描述
不使用運(yùn)算符 + 和 - ，計(jì)算兩整數(shù) a 本刽、b 之和鲸湃。
示例 1:
輸入: a = 1, b = 2
輸出: 3
示例 2:
輸入: a = -2, b = 3
輸出: 1
分析
使用二進(jìn)制的加法
實(shí)現(xiàn)
//兩個(gè)整數(shù)a, b; a ^ b是無進(jìn)位的相加； a&b得到每一位的進(jìn)位盅安；
// 讓無進(jìn)位相加的結(jié)果與進(jìn)位不斷的異或唤锉， 直到進(jìn)位為0；
public int getSum(int a, int b) {
int sum,carry;
do{
sum=a^b;
carry=(a&b)<<1;
a=sum;
b=carry;
}while(carry!=0);
return sum;
}
只出現(xiàn)一次的數(shù)字
相關(guān)題目：
136
描述
給定一個(gè)非空整數(shù)數(shù)組别瞭，除了某個(gè)元素只出現(xiàn)一次以外，其余每個(gè)元素均出現(xiàn)兩次株憾。找出那個(gè)只出現(xiàn)了一次的元素蝙寨。
說明：
你的算法應(yīng)該具有線性時(shí)間復(fù)雜度。 你可以不使用額外空間來實(shí)現(xiàn)嗎嗤瞎？
示例 1:
輸入: [2,2,1]
輸出: 1
示例 2:
輸入: [4,1,2,1,2]
輸出: 4
實(shí)現(xiàn)
//利用異或運(yùn)算的性質(zhì)
// ^:為異或運(yùn)算（性質(zhì)：對(duì)于任何數(shù)x墙歪，都有x^x=0，x^0=x）
public int singleNumber(int[] nums){
int res=0;
for (int i : nums) {
res^=i;
}
return res;
}
137
描述
給定一個(gè)非空整數(shù)數(shù)組贝奇，除了某個(gè)元素只出現(xiàn)一次以外虹菲，其余每個(gè)元素均出現(xiàn)了三次。找出那個(gè)只出現(xiàn)了一次的元素掉瞳。
說明：
你的算法應(yīng)該具有線性時(shí)間復(fù)雜度毕源。 你可以不使用額外空間來實(shí)現(xiàn)嗎？
示例 1:
輸入: [2,2,3,2]
輸出: 3
示例 2:
輸入: [0,1,0,1,0,1,99]
輸出: 99
分析
這個(gè)題其實(shí)就是求陕习，在其他數(shù)都出現(xiàn)k次的數(shù)組中有一個(gè)數(shù)只出現(xiàn)一次霎褐，求出這個(gè)數(shù)。
而上面那個(gè)k次的是有通用解法的该镣。
使用一個(gè)32維的數(shù)組冻璃，用這個(gè)32維的數(shù)組存儲(chǔ)所有數(shù)里面第0位1的總數(shù)，第1位1的總數(shù)损合。省艳。。第31位1的總數(shù)嫁审。
假如第0位1的個(gè)數(shù)是k的倍數(shù)跋炕，那么要求的這個(gè)數(shù)在該位一定是0，若不是k的倍數(shù)土居，那么要求的這個(gè)數(shù)在該位一定是1枣购，第1位的1一直到第31位的1的個(gè)數(shù)同理嬉探。
為什么呢？因?yàn)榧偃缯f數(shù)組中的某些數(shù)在該位置是1棉圈，那么因?yàn)檫@個(gè)數(shù)要么出現(xiàn)k次涩堤，那么出現(xiàn)1次。
因此分瘾，該位置一定可以表示成km或者km+1胎围，m代表該位是1的數(shù)的種類。
當(dāng)表示成km的時(shí)候代表該位為1的數(shù)都是出現(xiàn)k次的德召，而當(dāng)表示為km+1的時(shí)候代表該位為1的數(shù)還有只出現(xiàn)一次的白魂。
我甚至覺得這個(gè)和“n瓶藥有1瓶有毒，求最少的老鼠數(shù)來試毒”是一個(gè)原理上岗。
實(shí)現(xiàn)
public int singleNumber(int[] nums){
int res=0;
for(int i=0;i<32;i++){
int bit=1<<i;
int bitCount=0;
for(int num:nums){
if((num&bit)!=0){
bitCount++;
}
}
if(bitCount%3!=0){
res|=bit;
}
}
return res;
}
260
描述
給定一個(gè)整數(shù)數(shù)組 nums福荸，其中恰好有兩個(gè)元素只出現(xiàn)一次，其余所有元素均出現(xiàn)兩次肴掷。 找出只出現(xiàn)一次的那兩個(gè)元素敬锐。
示例 :
輸入: [1,2,1,3,2,5]
輸出: [3,5]
注意：
結(jié)果輸出的順序并不重要，對(duì)于上面的例子呆瞻， [5, 3] 也是正確答案台夺。
你的算法應(yīng)該具有線性時(shí)間復(fù)雜度。你能否僅使用常數(shù)空間復(fù)雜度來實(shí)現(xiàn)痴脾？
分析
第一步： 把所有的元素進(jìn)行異或操作颤介，最終得到一個(gè)異或值。因?yàn)槭遣煌膬蓚€(gè)數(shù)字赞赖，所以這個(gè)值必定不為0滚朵；
int xor = 0;
for (int num : nums) {
xor ^= num;
}
第二步： mask使用取異或值最后一個(gè)二進(jìn)制位為1的數(shù)字，如果是1則表示兩個(gè)數(shù)字在這一位上不同薯定。
int mask=1;
//取異或值最后一個(gè)二進(jìn)制位為1的數(shù)字作為mask始绍，如果是1則表示兩個(gè)數(shù)字在這一位上不同
while ((diff&1)==0){
mask=mask<<1;
diff=diff>>1;
}
第三步： 通過與這個(gè)mask進(jìn)行與操作，如果為0的分為一個(gè)數(shù)組话侄，為1的分為另一個(gè)數(shù)組亏推。這樣就把問題降低成了：“有一個(gè)數(shù)組每個(gè)數(shù)字都出現(xiàn)兩次，有一個(gè)數(shù)字只出現(xiàn)了一次年堆，求出該數(shù)字”吞杭。對(duì)這兩個(gè)子問題分別進(jìn)行全異或就可以得到兩個(gè)解。也就是最終的數(shù)組了变丧。
int[] ans = new int[2];
for (int num : nums) {
if ( (num & mask) == 0) {
ans[0] ^= num;
} else {
ans[1] ^= num;
}
}
復(fù)雜度分析： 時(shí)間復(fù)雜度O(N),空間復(fù)雜度O(1)
來源于：https://leetcode-cn.com/problems/two-sum/solution/cai-yong-fen-zhi-de-si-xiang-jiang-wen-ti-jiang-w
實(shí)現(xiàn)
public int[] singleNumber(int[] nums){
int diff=0;
for (int i:nums){
diff^=i;
}
int mask=1;
//取異或值最后一個(gè)二進(jìn)制位為1的數(shù)字作為mask芽狗，如果是1則表示兩個(gè)數(shù)字在這一位上不同
while ((diff&1)==0){
mask=mask<<1;
diff=diff>>1;
}
int[] res=new int[2];
//利用mask將原數(shù)組分成兩個(gè)只有一個(gè)數(shù)字是出現(xiàn)一次其余都是出現(xiàn)兩次的數(shù)組
for(int i:nums){
if ((i&mask)==0){
res[0]^=i;
}else {
res[1]^=i;
}
}
return res;
}
