做微信公众号网站源码,网站群建设讲话,江西省建设三类人员系统网站,一级建造师培训机构排名前十目录
技巧类题目
136 只出现一次的数字
191 位1的个数
231. 2 的幂
169 多数元素
75 颜色分类 #xff08;双指针#xff09;
287. 寻找重复数
136 只出现一次的数字
给你一个 非空 整数数组 nums #xff0c;除了某个元素只出现一次以外#xff0c;其余每个元素均…目录
技巧类题目
136 只出现一次的数字
191 位1的个数
231. 2 的幂
169 多数元素
75 颜色分类 双指针
287. 寻找重复数
136 只出现一次的数字
给你一个 非空 整数数组 nums 除了某个元素只出现一次以外其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题且该算法只使用常量额外空间。 这里就可以运用异或运算的性质
一个数和它本身做异或运算结果为 0即 a ^ a 0一个数和 0 做异或运算的结果为它本身即 a ^ 0 a。
对于这道题目我们只要把所有数字进行异或成对儿的数字就会变成 0落单的数字和 0 做异或还是它本身所以最后异或的结果就是只出现一次的元素。
class Solution {public int singleNumber(int[] nums) {int res 0;for (int n : nums) {res ^ n; //落单的数字和 0 做异或还是它本身}return res;}
}
191 位1的个数
n (n-1) 这个操作是算法中常见的作用是消除数字 n 的二进制表示中的最后一个 1 不断消除数字 n 中的 1直到 n 变为 0。
public class Solution {// 你需要将 n 视为一个无符号值public int hammingWeight(int n) {int res 0; // 结果变量用于存储1的个数 // 当 n 不为0时继续循环while (n ! 0) {// n (n - 1) 每次操作都会将 n 的最右边的一个1置为0// 这一步可以消除最右边的一个1n n (n - 1); // 每次消除一个1计数器加1res;}// 返回1的个数return res;}
}
231. 2 的幂
给你一个整数 n请你判断该整数是否是 2 的幂次方。如果是返回 true 否则返回 false 。
如果存在一个整数 x 使得 n 2(x) 则认为 n 是 2 的幂次方。 一个数如果是 2 的指数那么它的二进制表示一定只含有一个 1。
位运算 n(n-1) 在算法中挺常见的作用是消除数字 n 的二进制表示中的最后一个 1用这个技巧可以判断 2 的指数。
2^0 1二进制表示为 0001。2^1 2二进制表示为 0010。2^2 4二进制表示为 0100。2^3 8二进制表示为 1000。
class Solution {public boolean isPowerOfTwo(int n) {// 如果 n 小于等于 0则 n 不是 2 的幂if (n 0) return false;// 位操作判断 n 是否是 2 的幂// 对于 2 的幂二进制表示中只有一个 1其余全是 0// 比如2 (10), 4 (100), 8 (1000), 等等// n (n - 1) 将会移除 n 最右边的 1如果 n 是 2 的幂结果将是 0// 例如n 8, 二进制表示为 1000// n - 1 7, 二进制表示为 0111// n (n - 1) 1000 0111 0000return (n (n - 1)) 0;}
}
169 多数元素
给定一个大小为 n的数组 nums 返回其中的多数元素。多数元素是指在数组中出现次数 大于⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的并且给定的数组总是存在多数元素。 计数逻辑
计数器为0如果 count 为0说明当前没有候选元素或者之前的候选元素已经被其他元素抵消掉了。因此更新 target 为当前元素并将 count 设为1。当前元素等于目标元素如果当前元素 nums[i] 等于 target说明当前元素依旧是多数元素的候选计数器加1。当前元素不等于目标元素如果当前元素 nums[i] 不等于 target说明遇到了一个不同的元素计数器减1。
class Solution {public int majorityElement(int[] nums) {// 定义目标元素和计数器int target 0;int count 0;// 遍历数组for (int i 0; i nums.length; i) {// 如果计数器为0表示需要选择一个新的目标元素if (count 0) {// 将当前元素设为目标元素target nums[i];// 计数器重置为1count 1;} else if (nums[i] target) {// 如果当前元素等于目标元素计数器加1count;} else {// 如果当前元素不等于目标元素计数器减1count--;}}// 返回最后确定的目标元素return target;}
}
75 颜色分类 双指针
给定一个包含红色、白色和蓝色、共 n个元素的数组 nums 原地对它们进行排序使得相同颜色的元素相邻并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。 class Solution {public void sortColors(int[] nums) {int n0 0, n1 0;// 遍历数组for (int i 0; i nums.length; i) {int num nums[i]; // 获取当前元素nums[i] 2; // 默认将当前元素置为 2// 如果当前元素小于 2则需要处理 1 的插入if (num 2) {nums[n1] 1; // 将 1 插入到 n1 的位置并将 n1 向前移动一位}// 如果当前元素小于 1则需要处理 0 的插入 如果是0 前面设置过一次会被覆盖if (num 1) {nums[n0] 0; // 将 0 插入到 n0 的位置并将 n0 向前移动一位}}}
}
287. 寻找重复数
给定一个包含 n 1 个整数的数组 nums 其数字都在 [1, n] 范围内包括 1 和 n可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 返回 这个重复的数 。
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
class Solution {public int findDuplicate(int[] nums) {// 使用快慢指针初始化指向数组的起始位置int slow 0;int fast 0;// 第一阶段寻找快慢指针的相遇点// 这部分利用了快慢指针其中快指针移动速度是慢指针的两倍do {slow nums[slow]; // 慢指针移动一步fast nums[nums[fast]]; // 快指针移动两步} while (slow ! fast);// 此时 slow 和 fast 相遇表明存在一个循环环// 第二阶段找到环的入口即重复的元素int a 0; // a 从头开始int b fast; // b 从相遇点开始while (a ! b) {a nums[a]; // a 和 b 同时以相同速度前进b nums[b];}// 当 a 和 b 再次相遇时相遇点即为环的入口也就是重复的数字return a;}
}
