由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 问道题leetcode的题,关于bit运算的
相关主题
Leetcode 最简单的题目怎么 compile error?贡献一道面试题
leetcode: integer to roman 结果不同问个最近面试里的题目
amazon背靠背电面问几个关于hash, map, set的问题
关于leetcode的combinationSum题a problem from leetcode: high efficiency algorithm for combinations problem
Search for a Range - leetcodeleetcode 大侠,把 C++11 support 加上吧
这个是不是leetcode的bug?Leetcode上Two sum只能过3个case, VS能过,大牛进来看看是怎么回事
leetcode single number ii 怎么做?leetcode似乎c++11支持不完全?
再来一道简单的bit运算题请教:这个10来行的leetcode程序有什么问题?
相关话题的讨论汇总
话题: int话题: bits话题: res话题: 计数
进入JobHunting版参与讨论
1 (共1页)
m*********a
发帖数: 3299
1
Given an array of integers, every element appears three times except for
one. Find that single one. Your algorithm should have a linear runtime
complexity.
用额为空间的,建立一个hastable就行了,相同的数计数,返回计数是一个的值
int singleNumber(int A[], int n) {
unordered_mapnummap;
for (int i=0;i nummap[A[i]]++;
for (auto it=nummap.begin();it!=nummap.end();it++){
if (it->second==1) return it->first;
}
}
但是如果只能用固定的额为空间的话,只能用位运算。
int是32位的数,每次把计数的位移到个位,然后计数,3的倍数的话,用%3清零,最后
得到就是要找的那个数的在这个位置的bit(0或1)。计数好后,移动到以前的bit位置,
用|总结所有的位。但是下面的程序的结果就是不对。不知道为啥?
int singleNumber(int A[], int n) {
int bits[32],res=0;
for (int i=0;i<32;i++){
bits[i]=0;
for (int j=0;j if ((A[j]>>i)&1) bits[i]=(bits[i]+1)%3;
}
res|=(bits[i]< }
return res;
}
p*********j
发帖数: 47
2
正确的代码,请参考:
static int singleNumber(int A[], int n) {
int[] bits = new int[32];
int res = 0;
for (int i = 0; i < 32; i++) {
bits[i] = 0;
for (int j = 0; j < n; j++) {
bits[i] += (A[j] >> i) & 1;
bits[i] %= 3;
}
res |= (bits[i] << i);
}
return res;
}
m*********a
发帖数: 3299
3
你的这个和我的是一样,我递交了leetcode都能通过。
居然通不过我的笔记本的测试,太让人抓狂了
但是第一个写的居然都能过测试。 其实Bit[i]是0的时候不用加了,加了和原来的数一样

【在 p*********j 的大作中提到】
: 正确的代码,请参考:
: static int singleNumber(int A[], int n) {
: int[] bits = new int[32];
: int res = 0;
: for (int i = 0; i < 32; i++) {
: bits[i] = 0;
: for (int j = 0; j < n; j++) {
: bits[i] += (A[j] >> i) & 1;
: bits[i] %= 3;
: }

f****n
发帖数: 208
4
int size might not be 32 bits on the running platform?
r*****3
发帖数: 27
5
我用你的代码提交了一次leetcode 没错啊 0.0

【在 m*********a 的大作中提到】
: 你的这个和我的是一样,我递交了leetcode都能通过。
: 居然通不过我的笔记本的测试,太让人抓狂了
: 但是第一个写的居然都能过测试。 其实Bit[i]是0的时候不用加了,加了和原来的数一样

m*********a
发帖数: 3299
6
这个我知道了,我的电脑上通不过,估计是code::block的问题
code::block还不能用 for (auto it:myVector) cout<<*it;

【在 r*****3 的大作中提到】
: 我用你的代码提交了一次leetcode 没错啊 0.0
1 (共1页)
进入JobHunting版参与讨论
相关主题
请教:这个10来行的leetcode程序有什么问题?Search for a Range - leetcode
请问下leetcode的two sum题目这个是不是leetcode的bug?
关于Hash_mapleetcode single number ii 怎么做?
一道题目再来一道简单的bit运算题
Leetcode 最简单的题目怎么 compile error?贡献一道面试题
leetcode: integer to roman 结果不同问个最近面试里的题目
amazon背靠背电面问几个关于hash, map, set的问题
关于leetcode的combinationSum题a problem from leetcode: high efficiency algorithm for combinations problem
相关话题的讨论汇总
话题: int话题: bits话题: res话题: 计数