代码拉取完成,页面将自动刷新
leetcode给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
int singleNumber(vector<int>& nums) {
sort(nums.begin(), nums.end());
for (int i = 0; i + 2 < nums.size(); i+=2) {
if (nums[i] != nums[i + 1]) {
return nums[i];
}
}
return nums[nums.size()-1];
}
int singleNumber(vector<int>& nums) {
int res = 0;
for (auto it : nums) {
res ^= it;
}
return res;
}
leetcode 给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现了三次。找出那个只出现了一次的元素。
00-> 01-> 10
来表达任意位三种不同的状态。int数字有32位组成,所以需要两个整型变量one和two来状态转换。one表示1出现0次和1次,two表示1出现2次,因为出现第三次会变为0,所以最终的结果就是返回one异或运算:x ^ 0 = x , x ^ 1 = ~x 与运算:x & 0 = 0 , x & 1 = x
if two == 0:
if n == 0:
one = one
if n == 1:
one = ~one
if two == 1:
one = 0
if two == 0:
one = one ^ n
if two == 1:
one = 0
one = one ^ n & ~two
int singleNumber(vector<int>& nums) {
int one = 0, two = 0;
for (int num : nums) {
one = ~two & one ^ num);
two = ~one & two ^ num);
}
return one
}
leetcode给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。
输入: [1,2,1,3,2,5]
输出: [3,5]
int diff = mask & (-mask);
找到最右边的1那个位来区分他俩,n & diff
,这次只有那一位为1的数字才加入异或,通过这样就一定可以剔除掉另一个数字, vector<int> singleNumber(vector<int>& nums) {
int mask = 0;
for (auto n : nums) {
mask ^= n;
}
int diff = mask & (-mask);
int x = 0;
for (auto n : nums) {
if (n & diff) {
x ^= n;
}
}
int y = mask ^ x;
return {x, y};
}
leetcode编写一个函数,输入是一个无符号整数,返回其二进制表达式中数字位数为 ‘1’ 的个数(也被称为汉明重量)。
mask <<= 1
注意掩码必须使用无符号类型。n &= (n - 1)
,直到原码变为0,最后统计反转的次数 int hammingWeight(uint32_t n) {
uint32_t mask = 1;
int cnt = 0;
for (int i = 0; i < 32; ++i) {
if (n & mask) cnt++;
mask <<= 1;
}
return cnt;
}
int hammingWeight(uint32_t n) {
int cnt = 0;
while (n) {
if (n & 1) cnt++;
n >>= 1;
}
return cnt;
}
int hammingWeight(uint32_t n) {
int cnt = 0;
while (n) {
n &= n - 1;
cnt++;
}
return cnt;
}
leetcode给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ,计算其二进制数中的 1 的数目并将它们作为数组返回。
输入: 2
输出: [0,1,1]
输入: 5
输出: [0,1,1,2,1,2]
i
的二进制数1的个数,数组大小一定是num+1,因为包含了数字0。i % 2 == 0
还可以用i & 1 ==0
来判断偶数。 vector<int> countBits(int num) {
vector<int> dp(num + 1);
dp[0] = 0;
for (int i = 1; i <= num; i++) {
if((i & 1) == 0) dp[i] = dp[i / 2];
else dp[i] = dp[i - 1] + 1;
}
return dp;
}
leetcode颠倒给定的 32 位无符号整数的二进制位。
int rev = 0;
while (n) {
rev = rev * 10 + n % 10;
n /=10;
}
int rev = 0;
while (n) {
rev = rev * 2 + n % 2;
n /=2;
}
uint32_t reverseBits(uint32_t n) {
uint32_t rev = 0;
for (int i = 0; i < 32; ++i) {
rev = (rev << 1) + (n & 1);
n >>= 1;
}
return rev;
}
leetcode n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
皇后,是国际象棋中的棋子,意味着国王的妻子。皇后只做一件事,那就是“吃子”。当她遇见可以吃的棋子时,就迅速冲上去吃掉棋子。当然,她横、竖、斜都可走一或 N-1 步,可进可退。(引用自 百度百科 - 皇后 )
(1 << n) - 1
:申请n个1,代表每行可以放皇后得位置col | ld | rd
代码每行col、ld、rd这三个位置由于受上一行得影响而这一行不能在放了~(col | ld | rd) & ((1 << n) - 1)
考虑这三个位置后,这一行还能放皇后得位置,1代表还能放,0代表不能bit & -bit
只取最后一位1其他位清零,pick代表选择这一位col | pick
选择过哪一行就将那一行置为1,(ld | pick) << 1
例如选择第1行2列,那么2行的1列也就不能放置了bit &= (bit - 1);
清零最后一位1,遍历过就清零 int cnt;
int totalNQueens(int n) {
dfs(n, 0, 0, 0, 0);
return cnt;
}
void dfs(int n, int row, int col, int ld, int rd) {
if (row == n) {
cnt++;
return;
}
int bit = ~(col | ld | rd) & ((1 << n) - 1);
while (bit) {
int pick = bit & -bit;
dfs(n, row + 1, col | pick, (ld | pick) << 1, (rd | pick) >> 1);
bit &= (bit - 1);
}
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。