- 浏览: 174147 次
- 性别:
- 来自: 济南
文章分类
最新评论
在位运算这篇文章中已经介绍了关于位运算的一些知识,这里主要介绍leetcode中出现的有关位运算的题目。
有关找单独元素的有三道题,要求空间复杂度为O(n),空间复杂度为O(1),我们都可以通过位运算来解决。
1,Single Number
给定一个数组,每个元素都出现了两次,只有一个元素出现了一次,找出这个元素.
我们将所有的元素进行异或操作,最终的结果就是单独的元素,相同元素异或为0. 代码如下:
2,Single Number II
给定一个数组,每个元素都出现了三次,只有一个元素出现了一次,找出这个元素。
我们将数组中每个元素都按位操作,通过一个长度为32的数组记录每个位置上1的个数,然后通过与3取余,结果就为单独的元素。代码实现如下:
3,Single Number III
给定一个数组,每个元素都出现了两次,有两个元素只出现了一次,找出这两个元素。
解决这道题的办法是我们将数组中所有元素进行异或操作,得到一个数字,这个数字为1的位置,代表要找的两个数在这个位置的数字不同,肯定一个为0,一个为1。我们可以取其中一个1,将数组元素依次与它位与&,结果为0的分到一组,结果为1的分到一组,这样我们可以把数组划分为两部分,这两个数分别在不同的组,具体代码实现如下:
4,Missing Number
给定一个包含n个数的不含重复元素的数组,元素的范围为0....n,找出数组没有包含的那个元素。
例如:给定 nums[] = {0, 1, 3} 输出:2
将数组里的元素异或,再将结果与0....n异或,结果就是缺少的元素。代码如下:
接下篇 Bit Manipulation总结(二)
有关找单独元素的有三道题,要求空间复杂度为O(n),空间复杂度为O(1),我们都可以通过位运算来解决。
1,Single Number
给定一个数组,每个元素都出现了两次,只有一个元素出现了一次,找出这个元素.
我们将所有的元素进行异或操作,最终的结果就是单独的元素,相同元素异或为0. 代码如下:
public class Solution { public int singleNumber(int[] nums) { int result = 0; for(int i = 0; i < nums.length; i++) { result ^= nums[i]; } return result; } }
2,Single Number II
给定一个数组,每个元素都出现了三次,只有一个元素出现了一次,找出这个元素。
我们将数组中每个元素都按位操作,通过一个长度为32的数组记录每个位置上1的个数,然后通过与3取余,结果就为单独的元素。代码实现如下:
public class Solution { public int singleNumber(int[] nums) { int[] digits = new int[32]; int result = 0; int mask = 1; for(int i = 0; i < 32; i++) { for(int j = 0; j < nums.length; j++) { if((mask & (nums[j] >> i)) == 1) { digits[i] ++; } } result |= (digits[i] % 3) << i; } return result; } }
3,Single Number III
给定一个数组,每个元素都出现了两次,有两个元素只出现了一次,找出这两个元素。
解决这道题的办法是我们将数组中所有元素进行异或操作,得到一个数字,这个数字为1的位置,代表要找的两个数在这个位置的数字不同,肯定一个为0,一个为1。我们可以取其中一个1,将数组元素依次与它位与&,结果为0的分到一组,结果为1的分到一组,这样我们可以把数组划分为两部分,这两个数分别在不同的组,具体代码实现如下:
public class Solution { public int[] singleNumber(int[] nums) { int helper = 0; for(int i = 0; i < nums.length; i++) { helper ^= nums[i]; } int tell = helper & (~(helper - 1)); int single1 = 0; int single2 = 0; for(int j = 0; j < nums.length; j++) { if((nums[j] & tell) == 0) single1 ^= nums[j]; else single2 ^= nums[j]; } int[] result = {single1, single2}; return result; } }
4,Missing Number
给定一个包含n个数的不含重复元素的数组,元素的范围为0....n,找出数组没有包含的那个元素。
例如:给定 nums[] = {0, 1, 3} 输出:2
将数组里的元素异或,再将结果与0....n异或,结果就是缺少的元素。代码如下:
public class Solution { public int missingNumber(int[] nums) { int result = 0; for(int i = 0; i < nums.length; i++) { result ^= i ^ nums[i]; } return result ^ nums.length; } }
接下篇 Bit Manipulation总结(二)
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 228Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 231You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 344Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 337Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 456Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 519Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 434Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 623Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 432The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 390Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 522Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 537Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 374All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 866Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 884Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 558Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 604Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 766Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 738You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 633For a undirected graph with tre ...
相关推荐
python实现: 二进制和运算符 二进制计数设置位 二进制计数尾随零 二进制或运算符 二进制移位 二进制二进制补码 二进制异或运算符 计数 1S 布赖恩·克尼汉方法 计算 1 位数 ... Highest Set Bit
前端大厂最新面试题-bit-manipulation.docx
ruby_使用ruby进行位操作_bit_manipulation
C++、MFC源代码bit_manipulation_undef_type_source
some bit manipulation python codes
A Mathematical Introduction to Robotic Manipulation Richard M. Murray, Zexiang Li and S. Shankar Sastry
每日一题 简体中文 | 介绍 记录 每日一题 使用 Java 语言完成解答 题目 序号 题解 标签 难度 Depth-first Search, Breadth-first Search, Hash Table 简单 Hash Table 中等 Math 简单 Dynamic Programming 困难 ...
idea 插件 StringManipulation 可以对String 进行编码 大小写 去除空格
A Mathematical Introduction to Robotic Manipulation 超清晰完整大字打印版
java a算法的源码 Bit-Manipulation-Algorithms Java Source Code Representation of Bit manipulation Algorithms
Robotic Grasping and Fine Manipulation
Image_manipulation_detection-master.zip
内含缺失软件包,解压至工作空间scr目录下即可
Data Manipulation with R
Hogan - Impedance Control: An Approach to Manipulation: Part III-Applications
Image-manipulation-detection 图片篡改检测项目的训练权重,基于tensorflow1.X。 使用VOC2007数据集生成5000张待训练图像使用VGG16预训练权重,使用GPU进行训练,经过40000迭代,得到的权重文件。 已放入百度网盘,...
Phil Spector Data Manipulation R
介绍R语言用于数据处理,数据分析。这是一本经典的R语言数据操作典范