#leetcode#
373.查找和最小的K对数字
class Solution {
/**
* 核心功能：从两个升序数组中，找出和最小的 k 个数对 (nums1[i], nums2[j])
* @param nums1 升序排列的整数数组1
* @param nums2 升序排列的整数数组2
* @param k 需要找出的最小数对的数量
* @return 包含k个最小和数对的二维列表
*/
public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
// 获取两个数组的长度，用于后续边界判断和遍历控制
int m = nums1.length;
int n = nums2.length;

/* ========== 第一阶段：二分查找 确定第k小的数对和的目标值 pairSum ========== */
// 数对和的最小值：两个数组首元素相加
int left = nums1[0] + nums2[0];
// 数对和的最大值：两个数组尾元素相加
int right = nums1[m - 1] + nums2[n - 1];
// 初始化目标和为最大值，后续二分过程中不断逼近真实值
int pairSum = right;

// 二分查找核心循环：查找满足「和 ≤ mid 的数对数量 ≥ k」的最小mid
while (left <= right) {
// 计算中间值，用位运算替代除法，避免溢出且效率更高：mid = (left + right) / 2
int mid = left + ((right - left) >> 1);
// 统计「和 ≤ mid」的数对总数，用long防止int溢出（数组规模大时计数会超int范围）
long cnt = 0;
int start = 0; // nums1的指针，从左（最小值）向右遍历
int end = n - 1;// nums2的指针，从右（最大值）向左遍历

// 双指针高效统计符合条件的数对数量：时间复杂度O(m+n)，远优于暴力枚举O(mn)
while (start < m && end >= 0) {
// 当前数对和超过mid，nums2指针左移，找更小的数匹配
if (nums1[start] + nums2[end] > mid) {
end--;
} else {
// 当前数对和≤mid：nums2[0...end] 共 end+1 个元素，都能和nums1[start]组成有效数对
cnt += end + 1;
// nums1指针右移，找下一个更大的数继续匹配
start++;
}
}

// 二分收缩边界：
if (cnt < k) {
// 符合条件的数对不足k个，需要找更大的和，左边界右移
left = mid + 1;
} else {
// 符合条件的数对≥k个，记录当前mid为候选值，右边界左移找更小的符合条件的mid
pairSum = mid;
right = mid - 1;
}
}

/* ========== 第二阶段：收集所有「和 < pairSum」的数对 ========== */
// 定义结果集合，存储最终的k个最小和数对
List<List<Integer>> ans = new ArrayList<>();
int pos = n - 1; // nums2的遍历指针，初始化为尾元素

// 遍历nums1的每个元素，匹配nums2中符合条件的元素
for (int i = 0; i < m; i++) {
// 左移pos指针，找到nums2中第一个「和nums1[i]相加 < pairSum」的位置
while (pos >= 0 && nums1[i] + nums2[pos] >= pairSum) {
pos--;
}
// 收集nums2[0...pos]的所有元素，和nums1[i]组成数对，直到收集满k个
for (int j = 0; j <= pos && k > 0; j++, k--) {
List<Integer> list = new ArrayList<>();
list.add(nums1[i]);
list.add(nums2[j]);
ans.add(list);
}
}

/* ========== 第三阶段：收集剩余「和 = pairSum」的数对，补足k个 ========== */
// 重置nums2指针，重新遍历匹配等于目标和的数对
pos = n - 1;
// 遍历nums1，且仅当还需要补充数对（k>0）时继续
for (int i = 0; i < m && k > 0; i++) {
// 记录当前nums1的起始下标，用于处理重复元素
int start1 = i;
// 跳过nums1中连续的重复元素，避免重复收集相同数对
while (i < m - 1 && nums1[i] == nums1[i + 1]) {
i++;
}

// 左移pos指针，找到nums2中第一个「和nums1[i]相加 ≤ pairSum」的位置
while (pos >= 0 && nums1[i] + nums2[pos] > pairSum) {
pos--;
}

// 若当前数对和不等于目标值，直接跳过当前nums1[i]
if (nums1[i] + nums2[pos] != pairSum) {
continue;
}

// 记录当前nums2的起始下标，用于处理重复元素
int start2 = pos;
// 跳过nums2中连续的重复元素，避免重复收集相同数对
while (pos > 0 && nums2[pos] == nums2[pos - 1]) {
pos--;
}

// 计算可收集的数对数量：取「剩余需要的k个」和「重复元素能组成的数对总数」的较小值
int count = (int) Math.min(k, (long) (i - start1 + 1) * (start2 - pos + 1));
// 补足剩余的数对，直到收集满count个 或 k个
for (int j = 0; j < count && k > 0; j++, k--) {
List<Integer> list = new ArrayList<>();
list.add(nums1[i]);
list.add(nums2[pos]);
ans.add(list);
}
}

// 返回最终收集的k个最小和数对列表
return ans;
}
}
67.二进制求和
class Solution {
/**
* 核心功能：实现两个二进制字符串的加法运算，返回结果二进制字符串
* 解题思路：模拟十进制加法的「从右到左、逢二进一」规则，双指针遍历+进位标记实现
* @param a 第一个二进制字符串（仅包含0和1）
* @param b 第二个二进制字符串（仅包含0和1）
* @return 两个二进制字符串相加后的结果二进制字符串
*/
public String addBinary(String a, String b) {
// 用StringBuilder存储计算结果，支持高效的尾部追加、反转操作，比String拼接效率高
StringBuilder ans = new StringBuilder();
int ca = 0; // 进位标记：记录二进制相加时的进位值，取值仅为0或1

// 双指针从两个字符串的末尾（最低位）开始遍历，满足任一字符串未遍历完则继续循环
// i：字符串a的遍历指针，j：字符串b的遍历指针
for(int i = a.length() - 1, j = b.length() - 1; i >= 0 || j >= 0; i--, j--) {
int sum = ca; // 初始化当前位总和 = 上一位的进位值（核心：先加进位）

// 若a的当前指针有效，取出对应字符转成数字0/1，累加到sum；否则补0
sum += i >= 0 ? a.charAt(i) - '0' : 0;
// 若b的当前指针有效，取出对应字符转成数字0/1，累加到sum；否则补0
sum += j >= 0 ? b.charAt(j) - '0' : 0;

// 二进制取余：sum%2 得到当前位的计算结果（0/1），追加到结果容器
ans.append(sum % 2);
// 二进制整除：sum/2 得到当前位相加后的新进位（0/1），更新进位标记
ca = sum / 2;
}

// 遍历结束后，若仍有剩余进位（ca=1），需追加到结果末尾（最高位进位）
ans.append(ca == 1 ? ca : "");

// 由于是从低位到高位拼接的结果，反转后得到「高位到低位」的正确二进制串，再转成String返回
return ans.reverse().toString();
}
}
191.位1的个数
public class Solution {
/**
* 核心功能：计算一个32位无符号整数的二进制表示中，数字 1 的个数（汉明重量）
* @param n 待计算的32位无符号整数
* @return 二进制中1的总个数
*/
public int hammingWeight(int n) {
// 初始化计数器，记录二进制中1的个数
int ret = 0;

// 遍历32位无符号整数的每一位（固定循环32次，覆盖所有二进制位）
for (int i = 0; i < 32; i++) {
// 核心位运算判断：检查数字n的第i位是否为1
// 1 << i ：生成第i位为1、其余位为0的掩码数
// n & (1 << i)：按位与运算，结果非0 代表n的第i位是1，否则是0
if ((n & (1 << i)) != 0) {
ret++; // 第i位是1，计数器加1
}
}

return ret; // 返回最终统计的1的个数
}
}
137.只出现一次的数字 II
class Solution {
/**
* 核心功能：找出数组中唯一一个「只出现1次」的数字，其余数字均出现多次
* 解题思路：哈希表统计法 - 先遍历统计每个数字的出现频次，再遍历哈希表筛选频次为1的数字
* @param nums 输入整数数组，满足「仅有一个数字出现1次，其余数字出现N次」的条件
* @return 数组中唯一只出现一次的数字
*/
public int singleNumber(int[] nums) {
// 定义哈希表，键：数组中的数字，值：对应数字的出现频次（计数）
Map<Integer, Integer> freq = new HashMap<Integer, Integer>();

// ========== 第一阶段：遍历数组，统计每个数字的出现次数 ==========
for (int num : nums) {
// 核心API：HashMap.getOrDefault() 安全获取键对应的值，避免空指针
// 含义：若num已在哈希表中，取其当前计数；若不存在，默认计数为0
// 计数规则：当前数字出现一次，计数+1并重新存入哈希表
freq.put(num, freq.getOrDefault(num, 0) + 1);
}

// 初始化结果变量，存储最终找到的目标数字
int ans = 0;

// ========== 第二阶段：遍历哈希表，筛选出「出现频次为1」的数字 ==========
// 遍历哈希表的键值对集合，entry包含每一个 (数字, 频次) 组合
for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
// 取出当前键值对的 数字 和 对应频次
int num = entry.getKey();
int occ = entry.getValue();

// 核心判断：找到频次严格等于1的数字，即为题目所求
if (occ == 1) {
ans = num;
break; // 找到唯一目标后直接退出循环，无需继续遍历，提升效率
}
}

// 返回最终结果
return ans;
}
}