Java语言基础
标识符
标识符是用来命名变量、方法、类等的名称。其中：
首字符必须以字母（A-Z 或 a-z）、下划线_或美元符号$开头。
后续字符可以是字母、下划线_、美元符号$或数字。
Java是区分大小写的，即identifier和Identifier被视为不同的标识符。
不能使用Java的关键字作为标识符。例如，this是关键字，不能用作标识符。
Java关键字如下：
基本数据类型
基本数据类型是 Java 语言操作数据的基础，包括 boolean、char、byte、short、int、long、float 和 double，共 8 种。
注意，变量可以分为局部变量、成员变量和静态变量。
当变量是局部变量时（比如在方法中定义的变量）必须先初始化再使用。否则会报错：The local variable xxx may not have been initialized。
当变量时成员变量或者静态变量时，可以不进行初始化，此时会有默认值，如下所示：
基本数据类型
默认值
大小
boolean
false
1 比特
char
'\u0000'
2 字节
byte
0
1 ...
两整数之和
题目
371. 两整数之和 - 力扣（LeetCode）
给你两个整数 a 和 b ，不使用 运算符 + 和 - ，计算并返回两整数之和。
示例 1：
12输入：a = 1, b = 2输出：3
示例 2：
12输入：a = 2, b = 3输出：5
提示：
-1000 <= a, b <= 1000
解题
不使用+、-算术运算符，通过位运算可以实现加法：
1234567891011// 0+0=0，0+1=1，1+0=1，1+1=0（进位）class Solution { public int getSum(int a, int b) { while (b != 0){ int carry = (a & b) << 1; // 计算所有需要进位的 bit a ^= b; // 异或操作，相当于无进位加法 b = carry; // 将进位应用于下一位相加 } return a; } ...
4的幂
题目
342. 4的幂 - 力扣（LeetCode）
给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。
整数 n 是 4 的幂次方需满足：存在整数 x 使得 n == 4x
示例 1：
12输入：n = 16输出：true
示例 2：
12输入：n = 5输出：false
示例 3：
12输入：n = 1输出：true
提示：
-2^31 <= n <= 2^31 - 1
**进阶：**你能不使用循环或者递归来完成本题吗？
解题
在位运算章节中我们讲过，要想判断给定数 n 是否为 2 的正整数次幂，只需这样：
123public static boolean isPowerOfTwo(int n){ return n > 0 && (n & (n - 1)) == 0;}
其中，位运算技巧n & (n - 1)可以直接将 n 二进制表示的最低位 1 移除。
现在，我们要来判断一个数n是否是 4 的幂次方。这该怎么算？
通过观察我们发现，如果n是 4 ...
数字范围按位与
题目
201. 数字范围按位与 - 力扣（LeetCode）
给你两个整数 left 和 right ，表示区间 [left, right] ，返回此区间内所有数字 按位与 的结果（包含 left 、right 端点）。
示例 1：
12输入：left = 5, right = 7输出：4
示例 2：
12输入：left = 0, right = 0输出：0
示例 3：
12输入：left = 1, right = 2147483647输出：0
提示：
0 <= left <= right <= 2^31 - 1
解题
这道题如果按照迭代区间的每一个元素，然后按位进行与运算，会超时。因此需要优化。
我们观察发现，将每个数字用二进制表示后对齐，逐位遍历比特位上的值，只要某一列上出现一个0，那么与运算之后的结果在该位上也一定是0。
因此，这个问题就转换为：给定两个整数，找到它们对应的二进制字符串的公共前缀，然后将剩余位补零。
在实际编码中，我们让两个数字不断右移，直到相等，就得到了公共前缀，此时再左移补零。
1234567891011class Solution & ...
翻转矩阵后的得分
题目
861. 翻转矩阵后的得分 - 力扣（LeetCode）
给你一个大小为 m x n 的二元矩阵 grid ，矩阵中每个元素的值为 0 或 1 。
一次 移动 是指选择任一行或列，并转换该行或列中的每一个值：将所有 0 都更改为 1，将所有 1 都更改为 0。
在做出任意次数的移动后，将该矩阵的每一行都按照二进制数来解释，矩阵的 得分 就是这些数字的总和。
在执行任意次 移动 后（含 0 次），返回可能的最高分数。
示例 1：
123输入：grid = [[0,0,1,1],[1,0,1,0],[1,1,0,0]]输出：39解释：0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39
示例 2：
12输入：grid = [[0]]输出：1
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 20
grid[i][j] 为 0 或 1
解题
这道题使用了贪心策略。
首先我们知道，矩阵有m行n列。这里我们设首列（最左边的列）是第0列。
贪心思路是这样的：
将首列全部变为1（为了 ...
找到两个数组的前缀公共数组
题目
2657. 找到两个数组的前缀公共数组 - 力扣（LeetCode）
给你两个下标从 0 开始长度为 n 的整数排列 A 和 B 。
A 和 B 的 前缀公共数组 定义为数组 C ，其中 C[i] 是数组 A 和 B 到下标为 i 之前公共元素的数目。
请你返回 A 和 B 的 前缀公共数组 。
如果一个长度为 n 的数组包含 1 到 n 的元素恰好一次，我们称这个数组是一个长度为 n 的 排列 。
示例 1：
123456输入：A = [1,3,2,4], B = [3,1,2,4]输出：[0,2,3,4]解释：i = 0：没有公共元素，所以 C[0] = 0 。i = 1：1 和 3 是两个数组的前缀公共元素，所以 C[1] = 2 。i = 2：1，2 和 3 是两个数组的前缀公共元素，所以 C[2] = 3 。i = 3：1，2，3 和 4 是两个数组的前缀公共元素，所以 C[3] = 4 。
示例 2：
12345输入：A = [2,3,1], B = [3,1,2]输出：[0,1,3]解释：i = 0：没有公共元素，所以 C[0] = 0 。i = 1：只有 3 是公 ...
使数组异或和等于 K 的最少操作次数
题目
2997. 使数组异或和等于 K 的最少操作次数 - 力扣（LeetCode）
给你一个下标从 0 开始的整数数组 nums 和一个正整数 k 。
你可以对数组执行以下操作 任意次 ：
选择数组里的 任意 一个元素，并将它的 二进制 表示 翻转 一个数位，翻转数位表示将 0 变成 1 或者将 1 变成 0 。
你的目标是让数组里 所有 元素的按位异或和得到 k ，请你返回达成这一目标的 最少 操作次数。
注意，你也可以将一个数的前导 0 翻转。比方说，数字 (101)2 翻转第四个数位，得到 (1101)2 。
示例 1：
1234567输入：nums = [2,1,3,4], k = 1输出：2解释：我们可以执行以下操作：- 选择下标为 2 的元素，也就是 3 == (011)2 ，我们翻转第一个数位得到 (010)2 == 2 。数组变为 [2,1,2,4] 。- 选择下标为 0 的元素，也就是 2 == (010)2 ，我们翻转第三个数位得到 (110)2 == 6 。数组变为 [6,1,2,4] 。最终数组的所有元素异或和为 (6 XOR 1 XOR 2 XOR 4) ...
统计一致字符串的数目
题目
1684. 统计一致字符串的数目 - 力扣（LeetCode）
给定一个由不同字符组成的字符串 allowed 和一个字符串数组 words，如果一个字符串的每一个字符都在 allowed 中，就称这个字符串是一致字符串。请你返回 words 数组中一致字符串的数目。
示例 1：
123输入：allowed = "ab", words = ["ad","bd","aaab","baa","badab"]输出：2解释：字符串 "aaab" 和 "baa" 都是一致字符串，因为它们只包含字符 'a' 和 'b' 。
示例 2：
123输入：allowed = "abc", words = ["a","b","c","ab","ac","bc",&qu ...
操作后的最大异或和
题目
2317. 操作后的最大异或和 - 力扣（LeetCode）
给你一个下标从 0 开始的整数数组 nums 。一次操作中，选择 任意 非负整数 x 和一个下标 i ，更新 nums[i] 为 nums[i] AND (nums[i] XOR x) 。
注意，AND 是逐位与运算，XOR 是逐位异或运算。
请你执行 任意次 更新操作，并返回 nums 中所有元素 最大 逐位异或和。
示例 1：
123456输入：nums = [3,2,4,6]输出：7解释：选择 x = 4 和 i = 3 进行操作，num[3] = 6 AND (6 XOR 4) = 6 AND 2 = 2 。现在，nums = [3, 2, 4, 2] 且所有元素逐位异或得到 3 XOR 2 XOR 4 XOR 2 = 7 。可知 7 是能得到的最大逐位异或和。注意，其他操作可能也能得到逐位异或和 7 。
示例 2：
12345输入：nums = [1,2,3,9,2]输出：11解释：执行 0 次操作。所有元素的逐位异或和为 1 XOR 2 XOR 3 XOR 9 XOR 2 = 11 。可知 11 是能得到的 ...
位运算
前言
概述
位运算符
移位运算
位运算操作
判断给定数 n 是否为 2 的正整数次幂
计算给定数字的二进制表示形式中 1 的数量
生成一个集合中所有可能的子集
位运算遍历
取出整数 n 在二进制表示下的第 k 位
将整数 n 在二进制表示下的第 k 位取反
获取整数的低位部分
位赋值1操作
位赋值0操作
成对变换
返回整数 n 的二进制表示形式中最右边的1
再谈异或
基本运算
某个数出现奇数次
两个数出现奇数次
交换两个数
学习资料
前言
Powers of Two
Logical
Bit Manipulation
Mask Creation
概述
“bit是度量信息的单位，包含 0 和 1 两种状态。计算机的各种运算最后无不归结为一个个bit的变化。”
位运算速度更快，更接近系统，有时可以将程序优化到一个很好的水平。
我们约定，在 m 位二进制数中，最低位称为第 0 位，从右到左依次类推，则最高位是第 m-1 位。
位运算符
下面，复习一下位运算符：
与
或
非
异或
&
|
~
^
如果相对应位都是1，则结 ...
