leetcode 137 && 360一面算法 &&有道一面

题目描述:给一个数组,有一个数出现了两次或者1次,而其他数都出现了三次,找出这个数。其实对应了leetcode 137。


网上的解法多是位运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int singleNumber(int[] nums) {    
int ans = 0;   
 for(int i = 0; i < 32; i++) {      
  int sum = 0;        
  for(int j = 0; j < nums.length; j++) {         
    if(((nums[j] >> i) & 1) == 1) {
                sum++;
                sum %= 3;
            }
        }      
          if(sum == 1) {
            ans |= sum << i;
        }        
        if(sum == 2) {
            ans |= sum/2 << i
        }
    }    return ans;
}

利用位运算,求每位1出现的次数,出现3次的最后加起来%3==0. !=0的要么是1次,要么是2次。分情况讨论就行。最后的| 或运算,很强哦。。。




有道给的是一个数出现了一次,其他数都出现了三次,找出这一个数,对应LeetCode137题!位运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int singleNumber(int[] nums) {
       int length = nums.length;  
        int result = 0;  
        for(int i = 0; i<32; i++){  
            //int count = 0;   
            int temp = 0;  
            for(int j=0; j<length; j++){  
                temp+=(nums[j]>>i & 1);
                    //count++;  
            }  
          //if(count %3==1)  
                result |= (temp%3)<<i;  
        }  
        return result; 
    }
}

当时写的时候出现了一点小小的问题,就是最后 | 的时候,忘记左移回来了。



本文转自 努力的C 51CTO博客,原文链接:http://blog.51cto.com/fulin0532/1957485

上一篇:[leetcode/lintcode 题解]算法面试真题详解:内积


下一篇:阿里面试真题详解:两数和-小于或等于目标值