优选算法 - 3 （ 位运算 模拟 分治 11000 字详解 ）

一： 位运算

1.1 常见位运算总结

1.2 判断字符串是否唯一

题目链接：判断字符串是否唯一

class Solution {public boolean isUnique(String astr) {//利用位图思想判断字符是否唯一int bitMap = 0;//鸽巢原理，如果 astr 的长度大于了 26，那么这个字符串一定是会重复的if(astr.length() > 26) return false;for(int i = 0; i < astr.length(); i++){//先获取一下字符在位图中的位置int x = astr.charAt(i) - 'a';//判断一下位图的第 i 位是不是等于 1，如果等于 1 说明这个字符已经存入过了if(((bitMap >> x) & 1) == 1) return false;bitMap |= (1 << x); }return true;}
}

1.3 丢失的数字

题目链接：丢失的数字

class Solution {public int missingNumber(int[] nums) {int ret = 0;for(int i = 0; i < nums.length; i++) ret ^= nums[i];for(int i = 0; i <= nums.length; i++)ret ^= i;return ret;}
}

1.4 两整数之和

题目链接：两整数之和

class Solution {public int getSum(int a, int b) {while(b != 0){int x = a ^ b;int y = (a & b) << 1;a = x;b = y;}return a;}
}

1.5 只出现一次的数字 II

题目链接：只出现一次的数字 II

class Solution {public int singleNumber(int[] nums) {//首先定义一个 ret 用于存储结果int ret = 0;//接着我们开始判断 ret 的每一位是否需要修改成 1for(int i = 0; i < 32; i++){//用于统计数组中所有数在这一位上 1 的出现次数int sum = 0;for(int x : nums){if(((x >> i) & 1) == 1) sum++;}//统计完这一位上 1 的出现次数后开始操作sum %= 3;if(sum == 1) ret |= 1 << i; // 使用位操作将 ret 的第 i 位设置为 1}//经过对 ret 的 32 位进行判断后， ret 存储的值就是只出现一次的那个数字return ret;}
}

1.6 消失的两个数字

题目链接：消失的两个数字

class Solution {public int[] missingTwo(int[] nums) {//用 tmp 存储数组中所有元素和 0 - nums。length + 2 的所有数异或的结果int tmp = 0;//先异或上数组中的元素for(int x : nums)tmp ^= x;//接着异或 0 - nums。length + 2 中的元素for(int i = 1; i <= nums.length + 2; i++)tmp ^= i;//经过两论异或后，tmp = a ^ b，因为两个相同的数进行异或都抵消掉了，接着我们去找比特位为 1 的最右侧那一位,用 diff 标记int diff = 0;while(true){if(((tmp >> diff) & 1) == 1) break;else diff ++;}//接着我们通过 diff 来把数组中的元素和 0 - nums。length + 2 的元素分为两大类，一大类是 diff 为 0 的类，一类是 diff 为 1 的类，因为两个大类一定存在只有一个元素的（a 或 b），和存在两个相同元素的，两个相同元素异或后会抵消，所以分别把两大类的数异或在一起，就是 a 或者 b 的结果//用 ret 存储 a，b 两个数int[] ret = new int[2];for(int x : nums){if(((x >> diff) & 1) == 0) ret[0] ^= x;else ret[1] ^= x;           }for(int i = 1; i <= nums.length + 2; i++){if(((i >> diff) & 1) == 0) ret[0] ^= i;else ret[1] ^= i;   }//经过对两大类异或后，ret 存储的就是 a 和 b 两个数。return ret;        }
}

二：模拟

2.1 替换所有的问号

题目链接：替换所有的问号

class Solution {public String modifyString(String ss) {char[] s = ss.toCharArray();int n = s.length;for(int i = 0; i < n; i++){if(s[i] == '?'){for(char ch = 'a'; ch <= 'z'; ch++){//同时判断左边是否相等和右边是否相等的情况//接着再处理一下两个特殊情况，当 ？ 为开头时只需判断右边//当以 ？ 为结尾时，只判断左边if((i == 0 || ch != s[i - 1]) && (i == n - 1 || ch != s[i + 1])){s[i] = ch;break;}}}}return String.valueOf(s);}
}

2.2 提莫攻击

题目链接：提莫攻击

class Solution {public int findPoisonedDuration(int[] timeSeries, int duration) {int ret = 0;for(int i = 1; i < timeSeries.length; i++){int x = timeSeries[i] - timeSeries[i - 1];if(x >= duration) ret += duration;else ret += x;}//不要忘了最后一次攻击还有持续时间return ret += duration;}
}

2.3 N 字形变换

题目链接：N 字形变换

class Solution {public String convert(String s, int numRows) {//处理一下边界情况if(numRows == 1) return s;//先定义第一行和最后一行相邻元素的距离差值 dint d = 2 * numRows - 2, n = s.length();//因为要频繁对字符串进行操作，但是 String 是不变的，因此此处使用 StringBuilderStringBuilder ret = new StringBuilder();//先处理第一行for(int i = 0; i < n; i += d){ret.append(s.charAt(i));}//接着处理中间行for(int k = 1; k < numRows - 1; k++){//因为到最后可能不满足这个规律了，所以 i < n || j < n 之间要用或for(int i = k, j = d - i; i < n || j < n; i += d, j += d ){//要防止越界if(i < n )ret.append(s.charAt(i));if(j < n ) ret.append(s.charAt(j));}}//处理最后一行for(int i = numRows - 1; i < n; i += d){ret.append(s.charAt(i));}return ret.toString();}
}

2.4 外观数列

题目链接：外观数列

class Solution {public String countAndSay(int n) {//先初始化这个字符为 1String ret = "1";//接着开始进行 n 次循环，因为这个字符的初始值为 1，所以我们直接从第二次迭代开始循环for(int i = 1; i < n; i++){//因为需要频繁的对字符串进行操作，此处我们使用 StringBuilder,用 ret 临时存储结果StringBuilder tmp = new StringBuilder();int len = ret.length();for (int left = 0, right = 0; right < len; ) {               while(right < len && ret.charAt(right) == ret.charAt(left)) right++;//循环结束后，ret.charAt(left)存储的是字符，right - left 存储的是这个字符的个数tmp.append(Integer.toString(right - left));tmp.append(ret.charAt(left));left = right;}//一层的逻辑处理完后把 tmp 赋给 ret ，继续进行下一轮ret = tmp.toString();}return ret;        }
}

2.5 数青蛙

题目链接：数青蛙

class Solution {public int minNumberOfFrogs(String c) {char[] croakOfFrogs = c.toCharArray();String t = "croak";// 定义青蛙叫声的顺序 "croak"int n = t.length();//青蛙叫声的长度// 创建一个映射表 `index`，用于将每个字符 'c', 'r', 'o', 'a', 'k' 映射到其在 "croak" 中的顺序位置Map<Character, Integer> index = new HashMap<>(); // [字符, 该字符在 "croak" 中的索引]for(int i = 0; i < n; i++) index.put(t.charAt(i), i); // 'c' -> 0, 'r' -> 1, ..., 'k' -> 4// 使用数组 `hash` 来模拟哈希表，用于统计每个字符的进度状态,接下来开始遍历 croakOfFrogs 数组int[] hash = new int[n];for(char ch : croakOfFrogs){//先判断当前循环的字符是不是 c if(ch == 'c'){ if(hash[n - 1] != 0) hash[n - 1]--;hash[0]++;}else{//处理其他字符，首先获取当前字符在 "croak" 中的位置，方便进行判断int i = index.get(ch);if(hash[i - 1] == 0) return -1;else{hash[i - 1]--; hash[i]++;}}}// 检查前面四个字符是否已经全部匹配完成，如果有未完成的则返回 -1for(int i = 0; i < n - 1; i++){if(hash[i] != 0) return -1;}//返回 k 的值，此时的 k 值就代表最少青蛙的数return hash[n - 1];        }
}

三：分治 - 快排

3.1 颜色划分

题目链接：颜色划分

class Solution {// 辅助函数，用于交换数组 `nums` 中索引 `i` 和 `j` 的两个元素public void swap(int[] nums, int i, int j) {int t = nums[i];nums[i] = nums[j];nums[j] = t;}public void sortColors(int[] nums) {//先初始化 left 和 right ，要防止数组最左边是 0 ，最右边是 1,i 用于遍历数组int left = -1, right = nums.length, i = 0;while(i < right){if(nums[i] == 0) swap(nums, ++left, i++);else if(nums[i] == 1) i++;else swap(nums, i, --right);}}
}

3.2 排序数组 - 快速排序

题目链接：排序数组

class Solution {public int[] sortArray(int[] nums) {// 调用快速排序函数对整个数组进行排序qsort(nums, 0, nums.length - 1);return nums; // 返回排序后的数组}public void qsort(int[] nums, int l, int r){//先处理数组为空和数组只有 1 个元素的情况if(l >= r) return;//接着先获得一个数组范围内的随机基准值,[new Random(r - l + 1) 会生成一个介于 0 到 r - l 之间的随机整数，接着加上偏移量int key = nums[new Random().nextInt(r - l + 1) + l];//为了防止数组最左边是最小数和最右边是最大数的情况, i 用于遍历元素int left = l - 1, right = r + 1, i = l; while(i < right){if(nums[i] < key) swap(nums, ++left, i++);else if(nums[i] == key) i++;else swap(nums, --right, i);}// 经过三分法分区后，数组分成了三部分：// [l, left]      - 小于基准值 key 的区域// [left + 1, right - 1] - 等于基准值 key 的区域// [right, r]     - 大于基准值 key 的区域//接着继续递归处理数组的左右两个区域qsort(nums, l, left);qsort(nums, right,r);}//封装一个 swap 函数public void swap(int[] nums,int i, int j){int t = nums[i];nums[i] = nums[j];nums[j] = t;}
}

3.3 数组中第 k 个大元素

题目链接：数组中第 k 个大元素

class Solution {public int findKthLargest(int[] nums, int k) {// 调用快速选择算法return qsort(nums, 0, nums.length - 1, k);}public int qsort(int[] nums, int l, int r, int k){//先处理只有一个元素的特殊情况if(r == l) return nums[r];//接着先对数组进行升序排序，并把数组分为三个区间//left 初始化为数组的最左边再 - 1，rigth 初始化为数组的最右边 +1 ,i 用来遍历数组，从给定的 l 开始遍历int left = l - 1, right = r + 1, i = l;int key = nums[new Random().nextInt(r - l + 1) + l]; // 随机选取基准while(i < right){if(nums[i] < key) swap(nums, ++left, i++);else if(nums[i] == key) i++;else swap(nums, --right, i);}//数组排序好了接着来分情况讨论寻找第 k 大的元素int c = r - right + 1;int b = right - left - 1;if(c >= k) return qsort(nums, right, r, k);else if(b + c >= k) return key;else return qsort(nums, l, left, k - b - c);}public void swap(int[] nums, int i, int j){int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}
}

3.4 库存管理 III

题目链接：库存管理 III

class Solution {public int[] inventoryManagement(int[] stock, int cnt) {// 调用快速选择算法在数组中找到最小的 k 个数qsort(stock, 0, stock.length - 1, cnt);// 创建结果数组，存储最小的 k 个数int[] ret = new int[cnt];for (int i = 0; i < cnt; i++) {ret[i] = stock[i]; // 最小的 k 个数在排序后的前 k 个位置}return ret; // 返回结果数组}public void qsort(int[] nums, int l, int r, int k){//首先处理一下数组为空和只有一个元素的情况if(l >= r) return; //接着开始对数组排序，排序前先初始化一下 left right 和 iint left = l - 1, right = r + 1, i = l;int key = nums[new Random().nextInt(r - l + 1) + l]; // 随机选取基准while(i < right){if(nums[i] < key) swap(nums, ++left, i++);else if(nums[i] == key) i++;else swap(nums, --right, i);}//数组排序好了接下来分情况讨论如果获取前 k 个小的元素int a = left - l + 1;int b = right - left - 1;if(a > k)  qsort(nums, l, left, k);else if(a + b >= k) return;  //不用接着排序了，直接返回else qsort(nums, right, r, k - b - a);}public void swap(int[] nums, int i, int j){int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}
}

四： 分治 - 归并

4.1 排序数组 - 归并排序

题目链接：排序数组

class Solution {// 定义临时数组，用于存储合并过程中的元素int[] tmp;// 主函数，排序数组public int[] sortArray(int[] nums) {// 初始化临时数组，长度与待排序数组相同tmp = new int[nums.length];// 调用归并排序算法对整个数组进行排序mergeSort(nums, 0, nums.length - 1);// 返回排序后的数组return nums;}// 归并排序算法函数，对区间 [left, right] 进行排序public void mergeSort(int[] nums, int left, int right){//首先处理当前数组元素为空和只要有一个元素的情况，这种情况下数组无需排序了，直接返回if(left >= right) return;//如果不为空和只含有一个元素的话就开始把数组分为两部分，让两部分的数组有序int mid = left + (right - left) / 2;mergeSort(nums, left, mid);mergeSort(nums, mid + 1, right);//当数组的两个部分都有序了，我们来对数组的两个部分进行合并,把合并结果临时存储在 tmp 中//我们先用 cur1 标记数组第一部分的首元素索引，用 cur2 标记第二部分元素的首元素索引,用 i 来标记 tmp 中已有元素的个数int cur1 = left, cur2 = mid + 1, i = 0;while(cur1 <= mid && cur2 <= right)tmp[i++] = nums[cur1] < nums[cur2] ? nums[cur1++] : nums[cur2++];//先把小的数存入临时数组里//因为数组的两个部分的元素数量可能不同，所以我们接下来要把剩下的有序元素添加到 tmp 中while(cur1 <= mid)tmp[i++] = nums[cur1++];while(cur2 <= right)tmp[i++] = nums[cur2++];//最后把临时数组中的元素拷贝回原数组的 `[left, right]` 区间，只复制合并的部分for(int j = 0; j < i; j++){nums[j + left] = tmp[j];}}
}

4.2 交易逆序对的总数

题目链接：交易逆序对的总数

class Solution {// 定义临时数组，用于存储合并过程中的元素int[] tmp;// 主函数，计算数组中的逆序对个数public int reversePairs(int[] nums) {int n = nums.length;// 初始化临时数组，长度与待处理数组相同tmp = new int[n];// 调用归并排序并计算逆序对个数return mergeSort(nums, 0, n - 1);}// 归并排序函数，对区间 [left, right] 进行排序，并计算逆序对个数public int mergeSort(int[] nums, int left, int right){//先处理当数组只有一个元素或者元素为空的情况if(left >= right) return 0;//如果不是只含有一个元素或者为空，那么就开始处理这个数组的左右区间int mid = left + (right - left) / 2, ret = 0;ret += mergeSort(nums, left, mid);ret += mergeSort(nums, mid + 1, right);//当数组的左右部分都处理好了后开始合并数组,用 ret 存储逆序对的总数，i 来记录临时数组 tmp 已有元素的数量,cur1 记录左半部分数组的首元素索引， cur2 来记录右半部分的首元素索引int cur1 = left, cur2 = mid + 1, i = 0;while(cur1 <= mid && cur2 <= right){if(nums[cur1] <= nums[cur2]) tmp[i++] = nums[cur1++];//遍历的同时把元素拷贝到数组中进行数组升序else{ret += mid - cur1 + 1; tmp[i++] = nums[cur2++];}}//接着处理剩下的元素while(cur1 <= mid) tmp[i++] = nums[cur1++];while(cur2 <= right) tmp[i++] = nums[cur2++]; //最后把临时数组中的元素拷贝回原数组的 `[left, right]` 区间，只复制合并的部分for(int j = 0; j < i; j++)nums[j + left] = tmp[j];return ret;}}

4.3 计算右侧小于当前元素的个数

题目链接：计算右侧小于当前元素的个数

class Solution {// 定义辅助数组和计数数组int[] ret;         // 存储每个元素右侧比它小的元素个数int[] index;       // 标记 `nums` 中每个元素的原始下标int[] tmpIndex;    // 用于临时存储合并过程中元素的原始下标int[] tmpNums;     // 用于临时存储合并过程中元素的值// 主函数，返回每个元素右侧比它小的元素个数public List<Integer> countSmaller(int[] nums) {int n = nums.length;ret = new int[n];      // 初始化结果数组index = new int[n];    // 初始化下标数组tmpIndex = new int[n]; // 初始化临时下标数组tmpNums = new int[n];  // 初始化临时数值数组// 初始化 `index` 数组，使其指向 `nums` 中的每个元素的原始位置for (int i = 0; i < n; i++) {index[i] = i;}// 使用归并排序对 `nums` 数组进行排序，同时统计逆序对数量mergeSort(nums, 0, n - 1);// 将结果数组 `ret` 转换为列表形式并返回List<Integer> l = new ArrayList<Integer>();for (int x : ret) {l.add(x);}return l;}// 归并排序函数，对区间 [left, right] 进行排序，并统计右侧小于当前元素的个数public void mergeSort(int[] nums, int left, int right){//先处理数组为空和元素个数为一的情况if(left >= right) return;//如果不为空就开始处理数组的两个部分int mid = left + (right - left) / 2;mergeSort(nums, left, mid);mergeSort(nums, mid + 1, right);//当左右数组处理完毕后开始合并数组，并让数组降序int cur1 = left, cur2 = mid + 1, i = 0;while(cur1 <= mid && cur2 <= right){if(nums[cur1] <= nums[cur2]){tmpNums[i] = nums[cur2];//将当前右半部分的元素和它的原始位置放入临时数组 tmpIndex[i++] = index[cur2++];}else{ret[index[cur1]] += right - cur2 + 1; //index[cur1] 是当前元素 nums[cur1] 在原始数组中的下标tmpNums[i] = nums[cur1];//将当前左半部分的元素和它的原始位置放入临时数组 tmpIndex[i++] = index[cur1++];}}//接着处理剩下的元素while(cur1 <= mid){tmpNums[i] = nums[cur1];tmpIndex[i++] = index[cur1++];}while(cur2 <= right){tmpNums[i] = nums[cur2];tmpIndex[i++] = index[cur2++];}//最后把临时数组中的元素拷贝回原数组的 `[left, right]` 区间，只复制合并的部分for(int j = 0; j < i; j++){nums[j + left] = tmpNums[j];index[j + left] = tmpIndex[j];}}
}

4.4 翻转对

题目链接：翻转对

class Solution {int[] tmp; // 用于归并排序过程中存储排序的中间结果public int reversePairs(int[] nums) {int n = nums.length;tmp = new int[n]; // 初始化临时数组return mergeSort(nums, 0, n - 1); // 调用归并排序的递归函数}// 归并排序函数，同时计算翻转对的个数public int mergeSort(int[] nums, int left, int right){//先处理数组元素为空和数组元素为一的情况if(left >= right) return 0;//如果数组不为空和元素不为一，处理数组的左右两个部分，把数组左右两个部分的值累加到 ret 中int mid = left + (right - left) / 2, ret = 0;ret += mergeSort(nums, left, mid);ret += mergeSort(nums, mid + 1, right);// ret 累加完左右区间的翻转对后开始计算一左一右区间的翻转对int cur1 = left, cur2 = mid + 1;// 以 cur2 为参照，盯着 cur2 ，找当前元素后面有多少个元素的两倍比我小，数组要升序while(cur1 <= mid){while(cur2 <= right && (long)nums[cur1] > 2L * nums[cur2])  cur2++;// long 是因为两个数相乘范围太大，int可能回溢出//如果不是的话就让 ret 累加上 cur2 到 right 之间的元素，因为这些元素都满足翻转对的条件ret += cur2 - (mid + 1);; // 累加从 cur2 到 right 的元素数量cur1++;}// 当翻转和累加完毕后要开始合并左右区间了cur1 = left;cur2 = mid + 1; int i = left;while(cur1 <= mid && cur2 <= right) tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];// 接着处理剩下的元素while(cur1 <= mid) tmp[i++] = nums[cur1++];while(cur2 <= right) tmp[i++] = nums[cur2++];//最后把临时数组中的元素拷贝回原数组的 `[left, right]` 区间，只复制合并的部分for (int j = left; j <= right; j++) nums[j] = tmp[j];return ret;}
}