一、双指针算法(快慢指针,对撞指针)
艹，CSDN吞了我是十三题笔记！！！
二、滑动窗口(滑动窗口)
1、找到字符串中所有字母异位词
class Solution {
public List<Integer> findAnagrams(String s, String p) {
int[] hash1 = new int[26];
int[] hash2 = new int[26];
int sl = s.length();
int pl = p.length();
List<Integer> ret = new ArrayList<>();
for (int i = 0; i < pl; i++) {
hash1[p.charAt(i) - 'a']++;
}
/*
for (int j = 0; j < sl; j++) {
hash2[s.charAt(j) - 'a']++;
if (j >= pl - 1) {
if (cheak(hash1, hash2)) {
ret.add(j - pl + 1);
}
hash2[s.charAt(j - pl + 1) - 'a']--;
}
}*/
for (int left = 0, right = 0, count = 0; right < sl; right++) {
if (++hash2[s.charAt(right) - 'a'] <= hash1[s.charAt(right) - 'a']) {
count++;
}
if (right >= pl) {
hash2[s.charAt(left) - 'a']--;
if (hash2[s.charAt(left) - 'a'] < hash1[s.charAt(left) - 'a']) {
count--;
}
left++;
}
if (count == pl) {
ret.add(left);
}
}
return ret;
}
public static boolean cheak(int[] hash1, int[] hash2) {
for (int i = 0; i < 26; i++) {
if (hash1[i] != hash2[i]) {
return false;
}
}
return true;
}
// 我写代码是真的费劲啊,代码思路是一样的,老师写的就很简洁
}
class Solution {
public List<Integer> findAnagrams(String ss, String pp) {
List<Integer> ret = new ArrayList<Integer>();
char[] s = ss.toCharArray();
char[] p = pp.toCharArray();
int[] hash1 = new int[26]; // 统计字符串 p 中每⼀个字符出现的个数
for (char ch : p)
hash1[ch - 'a']++;
int[] hash2 = new int[26]; // 统计窗⼝中每⼀个字符出现的个数
int m = p.length;
for (int left = 0, right = 0, count = 0; right < s.length; right++) {
char in = s[right];
// 进窗⼝ + 维护 count
if (++hash2[in - 'a'] <= hash1[in - 'a'])
count++;
if (right - left + 1 > m) // 判断
{
char out = s[left++];
// 出窗⼝ + 维护 count
if (hash2[out - 'a']-- <= hash1[out - 'a'])
count--;
}
// 更新结果
if (count == m)
ret.add(left);
}
return ret;
}
}
题目思路:
滑动窗口遍历数组,这个窗口的长度是固定的,构造两个hash表,一个用于描述String p,一个用于藐视String s 的字串,比较比较两个hash表判断子串是否是字符串p的异位词。时间复杂度为26*O(N)；
算法优化:
在双指针遍历的时候引入变量count代表有效字符数,譬如:遍历到ccb时的有效字符数为2,遍历到ccba时的需要出窗口,即cba有效字符数3恰好等于字符串p的长度,此时子串就是p的异位词。
2、串联所有单词的字串
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> ret = new ArrayList<>();
Map<String, Integer> hash1 = new HashMap<>();
int sl = s.length();
int wl = words.length;
int len = words[0].length();
for (int i = 0; i < wl; i++) {
hash1.put(words[i], hash1.getOrDefault(words[i], 0) + 1);
}
for (int i = 0; i < len; i++) {
Map<String, Integer> hash2 = new HashMap<>();
for (int left = i, right = i, count = 0; right <= sl - len; right += len) {
String in = s.substring(right, right + len);
hash2.put(in, hash2.getOrDefault(in, 0) + 1);// 进窗口
if (hash2.get(in) <= hash1.getOrDefault(in, 0)) {
count++;
}
if (right - left >= len * wl) {
String out = s.substring(left, left + len);
hash2.put(out, hash2.get(out) - 1);
if (hash2.get(out) < hash1.getOrDefault(out, 0)) {
count--;
}
left += len;
}
if (count == wl) {
ret.add(left);
}
}
}
return ret;
}
}
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> ret = new ArrayList<Integer>();
// 保存字典中所有单词的频次
Map<String, Integer> hash1 = new HashMap<String, Integer>();
for (String str : words)
hash1.put(str, hash1.getOrDefault(str, 0) + 1);
int len = words[0].length(), m = words.length;
for (int i = 0; i < len; i++) // 执⾏次数
{
// 保存窗⼝内所有单词的频次
Map<String, Integer> hash2 = new HashMap<String, Integer>();
for (int left = i, right = i, count = 0; right + len <= s.length(); right += len) {
// 进窗⼝ + 维护 count
String in = s.substring(right, right + len);
hash2.put(in, hash2.getOrDefault(in, 0) + 1);
if (hash2.get(in) <= hash1.getOrDefault(in, 0))
count++;
// 判断
if (right - left + 1 > len * m) {
// 出窗⼝ + 维护 count
String out = s.substring(left, left + len);
if (hash2.get(out) <= hash1.getOrDefault(out, 0))
count--;
hash2.put(out, hash2.get(out) - 1);
left += len;
}
// 更新结果
if (count == m)
ret.add(left);
}
}
return ret;
}
}
包含的细节还挺多的:
老方法:两个hash表去分别表示子串和words,然后遍历两个hash表来判断子串是否串联了所有单词
优化之后:在遍历的字符串的时候借用count记录有效但此时,随着双指针的移动维护count,若count等于words中单词了数量是说明双指针子串包含了words中的所有单词。
3、最小覆盖子串
class Solution {
public String minWindow(String ss, String tt) {
char[] t = tt.toCharArray();
char[] s = ss.toCharArray();
int tl = t.length;
int sl = s.length;
int[] hash1 = new int[128];
int[] hash2 = new int[128];
int minlen = sl+1;
int begin = 0;
for (int i = 0; i < tl; i++) {
hash1[t[i]]++;
}
for (int left = 0, right = 0, count = 0; right < sl; right++) {
// 进窗口,维护有效字符数
if (++hash2[s[right]] <= hash1[s[right]]) {
count++;
}
while (count == tl && left <= right) {
if(right - left + 1 < minlen){
minlen = right - left + 1;
begin = left;
}
if (--hash2[s[left]] < hash1[s[left]]) {
count--;
}
left++;
}
}
if (minlen==sl+1)
return "";
return ss.substring(begin,begin+minlen);
// 注意不要在循环里面使用substring(),会增加时间复杂度
}
}
// count统计的是t中字符的个数
class Solution {
public String minWindow(String ss, String tt) {
char[] s = ss.toCharArray();
char[] t = tt.toCharArray();
int[] hash1 = new int[128]; // 统计字符串 t 中每⼀个字符的频次
int kinds = 0; // 统计有效字符有多少种
for (char ch : t)
if (hash1[ch]++ == 0)
kinds++;
int[] hash2 = new int[128]; // 统计窗⼝内每个字符的频次
int minlen = Integer.MAX_VALUE, begin = -1;
for (int left = 0, right = 0, count = 0; right < s.length; right++) {
char in = s[right];
if (++hash2[in] == hash1[in])
count++; // 进窗⼝ + 维护 count
while (count == kinds) // 判断条件
{
if (right - left + 1 < minlen) // 更新结果
{
minlen = right - left + 1;
begin = left;
}
char out = s[left++];
if (hash2[out]-- == hash1[out])
count--; // 出窗⼝ + 维护 count
}
}
if (begin == -1)
return new String();
else
return ss.substring(begin, begin + minlen);
}
}
// count统计的是t字符的种类,我感觉这个写法并没有优化多少,而且有点稍微难理解
双指针滑动窗口本质上是对暴力解法的优化,暴力解法中往往也是两个指针,以left指针为起点,right指针从left处开始对数组进行扫描,之后left右移,right回到left处再次开始扫描,显然这种解法的时间复杂度是O(N^2)
优化思路:right可以不需要回撤,双指针始终向右移,可以利用数组的单调性等来实现。这样的时间复杂度就是O(N)了。
三、二分算法
1、二分查找
class Solution {
public int search(int[] nums, int target) {
// 1:都读题目
// 数组升序,严格升序不存在 1 2 2 3 这种情况
// 数组具有"二段性"
int left = 0;
int right = nums.length - 1;
int index = 0;
while (left <= right) {
index = left + (right- left)/2; //防止溢出
if (nums[index] > target) {
right = index - 1;
} else if (nums[index] < target) {
left = index + 1;
} else {
return index;
}
}
return -1;
}
}
朴素二分查找
2、二分查找最左侧或最右侧目标值★★
class Solution {
public int[] searchRange(int[] nums, int target) {
// 1、读题目
// 非递减数列 存在形如 1 2 2 3
int left = 0, right = nums.length - 1;
int[] ret = new int[2];
ret[0]=-1;ret[1]=-1;
if(nums.length==0) return ret;
// 左端点
while (left < right) {
// mid中间偏左
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid+1;
}else{
//因为nums[mid]>=target,而nums[mid-1]有可能小于target，
//就不会是最左边目标值了，所以移动右指针为right = mid;
right = mid;
}
}
if(nums[left] != target) return ret;
else ret[0]=right;
// 右端点
left = right;
right = nums.length-1;
while (left < right) {
// mid中间偏右
int mid = left + (right - left+1) / 2;
if (nums[mid] > target) {
right = mid-1;
}else{
left = mid;
}
}
ret[1]=left;
return ret;
}
}
二分查找最左边或最右边的目标值,朴素的二分查找传到目标值以后就可以返回退出循环了,所以结束条件是while(left<=right),但是对于查找位于最左变或最右边的目标则不一样,当nums[mid]==target时循环并不能结束,以查找最左边目标值为例:
重点:
while (left < right) {
// mid中间偏左
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid+1;
}else{
//因为nums[mid]>=target,而nums[mid-1]有可能小于target，
//就不会是最左边目标值了，所以移动右指针为right = mid;
right = mid;
}
}
while (left < right) {
// mid中间偏右
int mid = left + (right - left+1) / 2;
if (nums[mid] > target) {
right = mid-1;
}else{
left = mid;
}
}
// 循环结束时
3、搜索插入位置
class Solution {
public int searchInsert(int[] nums, int target) {
int n = nums.length;
int left = 0;
int right = n - 1;
int mid = 0;
if(target>nums[right]) return n;
//吴老师的二分法是分为两个分支,将后两个合并,while循环不会提前结束,
//虽然比我写的行数少且简洁,但提前结束循环理论上来说时间耗时更小一些,
//但是圈复杂度比较高
//补充：我这样写之所以能对是因为数组是严格递增的，
//若不是严格递增的会因为没有找到最右侧目标值而测试失败
//吴老师给的模板才是通用的，对于非递减数组
//或数组中无目标值(此时双指针会停在最近目标值的左侧或者右侧)都可以适用
//吴老师yyds
while(left<right){
mid = left + (right - left)/2;
if(nums[mid]<target){
left=mid+1;
}else if(target<nums[mid]){
right=mid;
}else{
break;
}
}
if(left<right) return mid;
return left;
}
}
// 这也是一个二分查找最左目标值的问题
// 还是老老实实用吴老师的两分支模板吧！
4、x的平方根
// 我写的
class Solution {
public int mySqrt(int x) {
// 求算数平方根的整数部分
// 二分法
long left = 0;
long right = x;
if (x == 0)
return x;
while (left < right) {
long mid = left + (right - left) / 2;
if (mid * mid > x) {
right = mid;
} else if (mid * mid < x) {
left = mid + 1;
} else {
return (int) mid;
}
}
if (right * right == x)
return (int) right;
return (int) right - 1;
}
}
// 吴老师写的
class Solution {
public int mySqrt(int x) {
// 找最右侧目标值
if (x < 1)
return 0;
long left = 1, right = x;
while (left < right) {
long mid = left + (right - left + 1) / 2;
if (mid * mid <= x)
left = mid;
else
right = mid - 1;
}
return (int) left;
}
}
怎么说呢,这是一个典型的最在右侧目标值的问题,吴老师的模板yyds,好好理解一下。
5、山脉数组的峰顶索引
class Solution {
public int peakIndexInMountainArray(int[] arr) {
int n = arr.length;
int left=0;
int right = n-1;
while(left<right){
int mid = left+(right-left+1)/2;
if(arr[mid]>arr[mid-1]){
left=mid;
}else {
right=mid-1;
}
}
return left;
}
}
//用吴老师的模板写，简简单单
6、寻找峰值★★★
class Solution {
public int findPeakElement(int[] nums) {
int n = nums.length;
int left = 0;
int right = n - 1;
while(left<right){
int mid = left + (right - left)/2;
if(nums[mid]>nums[mid+1]){
right=mid;
}else {
left=mid+1;
}
}
return left;
}
}
二分算法适用于具有二段性的场景，本题的难点就在于分析出二段在哪里
对于数组某一位置i,如果nums[i]>nums[i+1]则[left,i]区间一定存在高峰，反之[i+1,right]区间一定存在高峰。
6、寻找旋转排序数组中的最小值★★★
如图所示，以D点为参照物数组具有二段性。
如果nums[mid]>nums[right]则最低点一定在[mid+1,right]区间
如果nums[mid]<nums[right]则最低点一定在[left,mid]区间
根据题意不存在nums[mid]==nums[right]
class Solution {
public int findMin(int[] nums) {
int n=nums.length;
int left=0;
int right=n-1;
while(left<right){
//如果mid偏右就会导致当左右指针相邻是陷入死循环
//所以mid要写成偏左的形式
int mid = left+(right-left)/2;
if(nums[mid]>nums[right]){
left=mid+1;
}else{
right=mid;
}
}
return nums[left];
}
}
7、点名
class Solution {
public int takeAttendance(int[] records) {
int n = records.length;
int left = 0;
int right = n - 1;
if(records[right]==right) return n;
while(left<right){
int mid = left + (right-left)/2;
if(mid==records[mid]){
left=mid+1;
}else{
right=mid;
}
}
return right;
}
}
//数组具有二段性：如果records[mid]==mid,说明mid之前的名单都是正常的，缺失的数位于mid之后
0^1^1^2^2^3^4^4^5^5=3
0+1+2+3+4=5*(4+0)/2
利用一个长度为n+1的哈希表，将名单放入哈希表，为零的位置就是缺失的名单
四、前缀和
1、一维数组前缀和
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int a = in.nextInt();
int b = in.nextInt();
int[] arr = new int[a];
long[] sum = new long[a+1];
for(int i=0;i<a;i++){
arr[i]=in.nextInt();
//★★
sum[i+1]=sum[i]+arr[i];
}
while(b>0){
int i=in.nextInt();
int j=in.nextInt();
// 使用一维前缀和数组
System.out.println(sum[j]-sum[i-1]);
b--;
}
}
}
2、二维数组前缀和
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int q = in.nextInt();
int[][] arr = new int[n][m];
long[][] dp = new long[n+1][m+1];
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
arr[i][j] = in.nextInt();
// 构造二位前缀和数组
dp[i+1][j+1] = dp[i][j+1]+dp[i+1][j]+arr[i][j]-dp[i][j];
}
}
for(int i=0;i<q;i++){
int x1=in.nextInt();
int y1=in.nextInt();
int x2=in.nextInt();
int y2=in.nextInt();
// 使用二位前缀和数组
System.out.println(dp[x2][y2]+dp[x1-1][y1-1]-dp[x1-1][y2]-dp[x2][y1-1]);
}
}
}
3、寻找数组的中心下标
class Solution {
public int pivotIndex(int[] nums) {
int n = nums.length;
int[] dp = new int[n+1];
// 构造前缀和数组
for(int i=1;i<=n;i++){
dp[i]=dp[i-1]+nums[i-1];
}
// 构造后缀和数组（可有可无，频繁用到后缀和的话也可以提前构造出来）
// 数组不具有二段性，中心下标随机分布，所以老老实实遍历好了
for(int i=0;i<n;i++){
if(dp[i]==dp[n]-dp[i+1]){
return i;
}
}
return -1;
}
}
4、除自身以外数组的积
class Solution {
public int[] productExceptSelf(int[] nums) {
//读题目，题目要求不能使用触发
//该位置的前缀积乘以后缀积
int n = nums.length;
//构造前置积
int[] f = new int[n];
int[] g = new int[n];
f[0]=g[0]=nums[0];
f[n-1]=g[n-1]=nums[n-1];
for(int i=1;i<n;i++){
f[i]=f[i-1]*nums[i];
}
for(int i=n-2;i>0;i--){
g[i]=g[i+1]*nums[i];
}
int[] ret = new int[n];
ret[0]=g[1];
ret[n-1]=f[n-2];
for(int i=1;i<n-1;i++){
ret[i]=f[i-1]*g[i+1];
}
return ret;
// 原数组，前缀数组，后缀数组
// 边界值
// 数值之间下标的对应关系
// 淦！！！
}
}
class Solution {
public int[] productExceptSelf(int[] nums) {
// lprod 表⽰：[0, i - 1] 区间内所有元素的乘积
// rprod 表⽰：[i + 1, n - 1] 区间内所有元素的乘积
int n = nums.length;
int[] lprod = new int[n];
int[] rprod = new int[n];
lprod[0] = 1;
rprod[n - 1] = 1;
// 预处理前缀积以及后缀积
for (int i = 1; i < n; i++)
lprod[i] = lprod[i - 1] * nums[i - 1];
for (int i = n - 2; i >= 0; i--)
rprod[i] = rprod[i + 1] * nums[i + 1];
// 处理结果数组
int[] ret = new int[n];
for (int i = 0; i < n; i++)
ret[i] = lprod[i] * rprod[i];
return ret;
}
}
[5、和为k的子数组](和为 K 的子数组)★★★★
// 暴力解法的时间复杂度是O(N^3)
// 使用前缀和数组去计算子数组和进行优化，时间复杂度O(N^2)
class Solution {
public int subarraySum(int[] nums, int k) {
int n = nums.length;
int[] lpron = new int[n+1];
for(int i=1;i<=n;i++){
lpron[i]=lpron[i-1]+nums[i-1];
}
int ret=0;
for(int i=0;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(lpron[j]-lpron[i]==k){
ret++;
}
}
}
return ret;
}
}
优化思路：使用哈希表积累每个前缀和的个数
对于区间以i结尾的子数组，若j(0<=j<=i)的前缀和sum[j]等于sum[i]-k，则子数组[j+1，i]元素之和等于k。在遍历数组的时候求出每一个位置的前缀和，并使用Map记录每个前缀和出现的次数即可。
// 求
class Solution {
public int subarraySum(int[] nums, int k) {
Map<Integer, Integer> hash = new HashMap<Integer, Integer>();
hash.put(0, 1);
int sum = 0, ret = 0;
for (int x : nums) {
sum += x; // 计算当前位置的前缀和
ret += hash.getOrDefault(sum - k, 0); // 统计结果
hash.put(sum, hash.getOrDefault(sum, 0) + 1); // 把当前的前缀和丢到哈希表⾥⾯
}
return ret;
}
}
6、和可被k整除的子数组★★★★
class Solution {
public int subarraysDivByK(int[] nums, int k) {
// 同余定理
// (a-b)%9==0，则a%9=b%9
// 若存在j<i、nums[i]%k==b、num[j]%k==b,则子数组[j,i]元素和为k的倍数
int n = nums.length;
Map<Integer, Integer> hash = new HashMap<>();
hash.put(0,1);
int sum=0;
int ret=0;
for(int x:nums){
sum+=x;
int in = ((sum%k)+k)%k;
ret+=hash.getOrDefault(in,0);
hash.put(in,hash.getOrDefault(in,0)+1);
}
return ret;
}
}
O(N^3):暴力枚举，每一个子数组，使用O(N)的方法判断这个子数组是否都满足提要求
O(N^2):构造前缀和数组，暴力枚举每一个子数组，利用前缀和求的子数组中元素之和，进而仅需O(1)的时间复杂度就能判断子数组是否满足题目要求
O(N*logN):并不需暴力枚举每一个子数组，若两个前缀和数组对k的余数相同，根据同余定理可得两前缀和数组相减得到的子数组是k的倍数，所以在遍历数组的时候统计每一种余数出现的次数，就可以直接得出以下一位置为结尾的满足题意的子数组的个数。
7、连续数组
class Solution {
public int findMaxLength(int[] nums) {
// 若[left,right],则 right-left+1 == 子数组元素和*2
int n = nums.length;
Map<Integer,Integer> hash = new HashMap<>(); // 下标，0,1数量差
hash.put(0,-1);
int sum=0;
int max=0;
for(int i=0;i<n;i++){
sum+=nums[i];
int cha = i+1-2*sum;
if(hash.containsKey(cha)){
max=Math.max(max,i-hash.get(cha));
}else{
hash.put(cha,i);
}
}
return max;
}
}
class Solution {
public int findMaxLength(int[] nums) {
Map<Integer, Integer> hash = new HashMap<Integer, Integer>();
hash.put(0, -1); // 默认存在⼀个前缀和为 0 的情况
int sum = 0, ret = 0;
for (int i = 0; i < nums.length; i++) {
sum += (nums[i] == 0 ? -1 : 1); // 计算当前位置的前缀和
if (hash.containsKey(sum))
ret = Math.max(ret, i - hash.get(sum));
else
hash.put(sum, i);
}
return ret;
}
}
// 把0当成-1，问题就变成了求元素和为0的最大子数组长度
// 和之前求元素和为0的子数组的个数不同的是，Map<Integer,Integer>里面存的是<前缀和，最小下标>
// 之前存的是<前缀和，满足条件的子数组的个数>
// 我的代码和吴老师的思路本质上是一样的
8、矩阵区域和
class Solution {
public int[][] matrixBlockSum(int[][] mat, int k) {
int m = mat.length;
int n = mat[0].length;
int[][] dp = new int[m+1][n+1];
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
dp[i][j]=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1]+mat[i-1][j-1];
}
}
int[][] ret = new int[m][n];
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
int x1= i-k>1?i-k:1;
int y1= j-k>1?j-k:1;
int x2= i+k<m?i+k:m; // 边界值处理,一开始没写对debug之后发现的
int y2= j+k<n?j+k:n; // 边界值处理
ret[i-1][j-1]=dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1];
}
}
return ret;
}
}
// 抽时间写篇debug的笔记
五、位运算
0、常见位运算总结
a，基础运算符
常见位运算符：
右移：>>
左移：<<
取反 : ~
与 ：& 有0就为0
或 ： | 有1就为1
异或：^ 相同为0，相异为1/无进位相加
b，给定一个数n,确定他的二进制表示第x位是0还是1
最低位在最右边
n:0110101000 我想要知道第x位的是0还是1，只需要让这一位和1与一下就可以了，
0110101000
(n>>x)&1 这个结果就是n的第x位是0还是1，并且不会改变n的大小。
c，将一个数n的二进制表示第x位修改为1
n:0110101000
0000001000 将这两个数或一下就可以得到修改后的值，所以我们需要构造出一个第x为1，其他位为0的数字，也就是（1<<x）那么最终的公式是：
n=n|(1<<x) 或者写成这样也可以 n|=(1<<x)
d，将一个数n的二进制表示第x位修改为0
n:0110101000
1111110111 将这两个数&一下就可以了，所以我们需要构造出来一个第x位为0，其他位为1的二进制数，也就是~(1<<x) 那么最终运算的公式是：
n&=(~(1<<x)) 或者写成这样也可以 n=n&(~(1<<x))
e，位图思想
本质就是哈希表，我们常见的哈希表是数组形式比如int[10]={0,1,2,3,4,5,6,7,8,9}，根据下标可以在O(1)时间复杂度下找到arr[i]，位图的思想就说：把一个数n的二进制表示整体看做一个哈希表，每一位0或者1可以表示两个状态。boolean数组或许就是这样。（未完待续…）
f，提取一个二进制数最右侧的1
这个怎么提取确实难想，直接上答案吧：
n&(-n) 这样一个数字就是成功提取了二进制数n的最右侧1，
n = 0110101000 ,对进行取反加1得到 -n：1001011000
n = 0110101000
-n = 1001011000
n&(-n) = 0000001000 这个就是最终的提取结果
g， 将一个二进制数n最右侧的1改为0
这个算法按理讲应该可以想出来，我要改变最低为的1，就代表比这一位高的都不能变，比这一位低的都是0，那么n-1就会是一个高位和n一致，第位从1全变成1,要改变的这一位从1变成了0，那么n&(-n)就是最终结果；
n=0110101000
n-1=0110100111
n&(n-1)=0101010000 ok,这就成功把最右侧1改为了0
h，运算符的优先级
自己写的时候能加括号就加括号
在编程中,运算符的优先级决定了表达式中运算的执行顺序。下面是一些常见运算符的优先级:
- 括号 (): 最高优先级，表达式会首先被求值。
- 一元运算符: 如
!、-、++、--等。 - 算术运算符:
*、/、%、+、-。乘、除、取模的优先级高于加、减。 - 位运算符:
~、&、|、^、<<、>>。 - 关系运算符:
<、>、<=、>=、==、!=。 - 逻辑运算符:
&&、||。 - 赋值运算符:
=、+=、-=、*=、/=、%=等。
当表达式中含有多个运算符时,优先级高的运算符会先被求值。如果优先级相同,则从左到右依次求值。
我们可以使用括号来改变表达式的求值顺序。括号内的表达式会首先被求值。
例如:
5 + 3 * 2 // 结果是 11, 因为 * 的优先级高于 +
(5 + 3) * 2 // 结果是 16, 因为括号内的表达式先被求值
位运算符是一类特殊的运算符,它们直接对数字的二进制位进行操作。位运算符的优先级如下:
- 位非 (~): 最高优先级,对一个数的二进制位进行取反操作。
- 位与 (&): 对两个数的对应位进行"与"操作。
- 位或 (|): 对两个数的对应位进行"或"操作。
- 位异或 (^): 对两个数的对应位进行"异或"操作。
- 左移 (<<): 将一个数的二进制位向左移动指定的位数。
- 右移 (>>): 将一个数的二进制位向右移动指定的位数。
位运算符的优先级高于算术运算符,但低于一元运算符。
例如:
a = 5 & 3 // 结果为 1，因为 5 的二进制是 101，3 的二进制是 011，按位与得到 001，即 1
b = 5 | 3 // 结果为 7，因为 5 的二进制是 101，3 的二进制是 011，按位或得到 111，即 7
c = 5 ^ 3 // 结果为 6，因为 5 的二进制是 101，3 的二进制是 011，按位异或得到 110，即 6
d = 5 << 1 // 结果为 10，因为 5 的二进制是 101，左移 1 位得到 1010，即 10
e = 5 >> 1 // 结果为 2，因为 5 的二进制是 101，右移 1 位得到 10，即 2
理解位运算符的优先级和使用方法对于一些底层编程和优化很有帮助。
i，异或（^）运算的规律
1，a^0=a
2，a^a=0
3，abc=a(bc) 异或运算满足交换律，一大堆数异或在一起，计算结果和异或顺序无关。
前两个还是比较好理解的，最后一个特性也是与生俱来的，因为异或没有进位相加
PS：
7,8两小节可以帮助我们完成力扣这三道题目(191,338,461)
第9可以帮助我们完成力扣这两道题目(136,260)
1、 判断字符是否唯一★★★
// 解题思路：用位图代替哈希表
class Solution {
public boolean isUnique(String astr) {
char[] s = astr.toCharArray();
int bitMap = 0;
for (int i = 0; i < s.length; i++) {
int x = s[i] - 'a';
if (((bitMap >> x) & 1) == 1) {
return false;
}else{
bitMap |= (1 << x);
}
}
return true;
}
}
// 1、使用int bitMap = 0;充当哈希表
// 2、使用 (bitMap>>x)&1 的值判断是字母否出现过
// 3、使用 bitMap |= (1 << x); 标记该字母出现过
2、丢失的数字
class Solution {
public int missingNumber(int[] nums) {
int ret=nums.length;
for(int i=0;i<nums.length;i++){
ret^=i^nums[i];
}
return ret;
}
}
// 借助异或运算的规律该寻找丢失的数字
// a^a^b^b^c=c
// a^a=0
// a^0=a
3、两整数之和★★★★
class Solution {
public int getSum(int a, int b) {
int carry =0;
do{
carry=(a&b)<<1;
a=a^b;
b=carry;
}while(carry!=0);
return a;
}
// 错误写法
// public int getSum(int a, int b) {
// int carry =0;
// do{
// carry=(a&b)<<1;
// a=a^b;
// b=carry;
// }while(carry>=0); // 进位有可能是负数
// return a;
// }
}
// 算法原理：a+b = (a^b) + (a&b)<<1 循环进行操作直到进位等于0，就避免了使用加减法。
// 数字的原码，补码，反码
- 原码：用最高位表示符号位,其余位表示数值。例如, +5 用 0b0101 表示,而 -5 用 0b1101 表示。这是最简单直观的表示方法。
- 反码：正数的反码与原码相同,负数的反码是将原码的数值位按位取反(0变1,1变0),符号位不变。例如, +5 的反码是 0b0101,而 -5 的反码是 0b1010。
- 补码：正数的补码与原码相同,负数的补码是在该数的反码的基础上加1。例如, +5 的补码是 0b0101,而 -5 的补码是 0b1011。
补码的主要优点是:
- 加法和减法统一为加法运算,即可用同样的加法电路实现加法和减法。
- 0有唯一的表示形式,即 0b0000。而在原码中,+0 和 -0 有两种表示形式。
所以在计算机中,通常会采用补码来表示有符号整数。这样可以简化电路设计,提高运算效率。
4、只出现一次的数字II★★★★
如图所示：将数组中所有数的第i位比特位(0<=i<32)的值求和取余的结果恰好等于那个只出现了一次的数字的第i位比特位，求出该数字的32个比特位即可找到这个只出现了一次的数字。
class Solution {
public int singleNumber(int[] nums) {
// 算法原理
int ret = 0;
for (int i = 0; i < 32; i++) {
int sum = 0;
for (int x : nums) {
sum += (x >> i) & 1;
}
if (sum % 3 == 1) { // 将第i位比特位置位1
ret |= (1 << i);
} else { // // 将第i位比特位置位0（初始化的时候本来就是0，所也可以不做处理）
ret &= (~(1 << i));
}
}
return ret;
}
}
5、消失的两个数字
算法原理：
class Solution {
public int[] missingTwo(int[] nums) {
// 1、将nums中的数字以及1~N异或
// 得到temp=a^b,也就是缺失的两个数的异或
// 因为a!=b,所以temp!=0
int N = nums.length + 2;
int temp = 0;
for (int x : nums)
temp ^= x;
for (int i = 1; i <= N; i++)
temp ^= i;
// 2、因为temp!=0,所以存在某个比特位等于1，确定这个比特位的位置index
temp = temp & (-temp);
int index = 0;
while (true) {
if ((temp >> index) == 1)
break;
index++;
}
// 3、将所有数分为两类，即第index位比特位为1的分为一类，为0的分为一类
// 此时缺失的两个数字会被分开，在这两个类数中只有a,b是单独存在的，其他数都是两个
// 分别将两类数进行异或得到的两值就是缺失的两个数字。
int[] ret = new int[2];
for (int x : nums) {
if (((x >> index) & 1) == 1)
ret[0] ^= x;
else
ret[1] ^= x;
}
for (int i = 1; i <= N; i++) {
if (((i >> index) & 1) == 1)
ret[0] ^= i;
else
ret[1] ^= i;
}
return ret;
}
}
六、模拟——比葫芦画瓢
1、替换所有问号★★★
class Solution {
public String modifyString(String s) {
char[] chars = s.toCharArray();
int n = chars.length;
if(n==1){
if(chars[0]=='?'){
return "a";
}else{
return s;
}
}
if(chars[0]=='?'){
if(chars[1]=='?'){
chars[0]='a';
}else if(n>1){
chars[0]=(char)((chars[1]-'a'+1)%26+'a');
}
}
for(int i=1;i<n-1;i++){
if(chars[i]=='?'){
chars[i]=getChar(chars[i-1],chars[i+1]);
}
}
if(chars[n-1]=='?')
chars[n-1]=getChar(chars[n-2],' ');
return new String(chars);
}
public static char getChar(char c1,char c2){
char ret=' ';
for(int i=0;i<26;i++){
ret = (char)('a'+i);
if(ret!=c1&&ret!=c2){
return ret;
}
}
return ret;
}
}
// 写的好丑！！！
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、提莫攻击
class Solution {
public int findPoisonedDuration(int[] timeSeries, int duration) {
int n = timeSeries.length;
int time=0;
int t=0;
int sum=0;
int left=-1;
int right=-1;
while(time<timeSeries[n-1]){
if(time==timeSeries[t]){
// 攻击，刷新毒区
left = timeSeries[t];
right = timeSeries[t]+duration-1;
// t移动到下一次大于本次的攻击时间
t++;
while(t<n&&timeSeries[t]==timeSeries[t-1]){
t++;
}
}
if(left<=time && time<=right){
sum++;
}
time++;
}
return sum+duration;
}
}v
class Solution {
public int findPoisonedDuration(int[] timeSeries, int duration) {
if (duration == 0)
return 0;
int n = timeSeries.length;
int sum=0;
for (int t = 0; t < n-1; t++) {
if(timeSeries[t]+duration-1<timeSeries[t+1]){
sum+=duration;
}else{
sum+=timeSeries[t+1]-timeSeries[t];
}
}
return sum+duration;
}
}
3、Z字形变换
class Solution {
public String convert(String ss, int numRows) {
if(numRows==1) return ss;
char[] s = ss.toCharArray();
int length = s.length;
int m = numRows;
int n = length;
char[][] arr = new char[m][n];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
arr[i][j]=' ';
}
}
int index=0;
int i=0;
int j=0;
while(index<length){
// 竖着的
int a=0;
while( a++<numRows && index<length){
arr[i++][j]=s[index++];
}
i--;
// 斜着的
a=0;
while(a++<numRows-2&&index<length){
arr[--i][++j]=s[index++];
}
i--;j++;
}
index=0;
for(i=0;i<m;i++){
for(j=0;j<n;j++){
if(arr[i][j]!=' '&&index<length){
s[index++]=arr[ii][jj];
}
}
}
return new String(s);
}
}
class Solution {
public String convert(String s, int numRows) {
// 处理⼀下边界情况
if (numRows == 1)
return s;
int d = 2 * numRows - 2, n = s.length();
StringBuilder ret = new StringBuilder();
// 1. 处理第⼀⾏
for (int i = 0; i < n; i += d)
ret.append(s.charAt(i));
// 2. 处理中间⾏
for (int k = 1; k < numRows - 1; k++) // 依次枚举中间⾏
{
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));
}
}
// 3. 处理最后⼀⾏
for (int i = numRows - 1; i < n; i += d)
ret.append(s.charAt(i));
return ret.toString();
}
}
这哪是模拟题呀，这简直是数学题找规律呀！！！
4、外观数列
class Solution {
public String countAndSay(int n) {
String s = "1";
for(int i=1;i<n;i++){
s=RLE(s);
}
return s;
}
public static String RLE(String ss){
if(ss==null || ss.length()==0) return ss;
StringBuilder ret = new StringBuilder();
char[] s = ss.toCharArray();
int n = s.length;
int num=0;
int i=0;
while(i<n){
while(i+1<n&&s[i]==s[i+1]){
num++;
i++;
}
ret.append(num+1);
ret.append(s[i]);
i++;
num=0;
}
return ret.toString();
}
}
class Solution {
public String countAndSay(int n) {
String ret = "1";
for (int i = 1; i < n; i++) // 解释 n - 1 次 ret 即可
{
StringBuilder tmp = new StringBuilder();
int len = ret.length();
for (int left = 0, right = 0; right < len;) {
while (right < len && ret.charAt(left) == ret.charAt(right))
right++;
tmp.append(Integer.toString(right - left));
tmp.append(ret.charAt(left));
left = right;
}
ret = tmp.toString();
}
return ret;
}
}
// 双指针:开始是left、right指向同一位置，然后right向右移动知道s[left]!=s[right],压缩。
// 然后left指针右移到right，重复上述操作压缩整个字符串
// 秀啊！！！
5、数青蛙★★★★(优雅)
class Solution {
public int minNumberOfFrogs(String croakOfFrogs) {
// c.num>r.num>o.num>a.num>k.num
// c r o a k
// 0 1 2 3 4
int[] hash = new int[5];
char[] s = croakOfFrogs.toCharArray();
int len = s.length;
int num=0;
for (char chr : s) {
if(chr=='c'){
if(hash[4]>0){
hash[4]--;
}
hash[0]++;
}else if(chr=='r'&&hash[0]>0){
hash[0]--;
hash[1]++;
}else if(chr=='o'&&hash[1]>0){
hash[1]--;
hash[2]++;
}else if(chr=='a'&&hash[2]>0){
hash[2]--;
hash[3]++;
}else if(chr=='k'&&hash[3]>0){
hash[3]--;
hash[4]++;
}else{
return -1;
}
}
for(int i=0;i<4;i++){
if(hash[i]!=0)
return -1;
}
return hash[4];
}
}
class Solution {
public int minNumberOfFrogs(String c) {
char[] croakOfFrogs = c.toCharArray();
String t = "croak";
int n = t.length();
int[] hash = new int[n]; // 数组模拟哈希表
Map<Character, Integer> index = new HashMap<>(); // [x, x这个字符对应的下标
for (int i = 0; i < n; i++)
index.put(t.charAt(i), i);
for (char ch : croakOfFrogs) {
if (ch == t.charAt(0)) {
if (hash[n - 1] != 0)
hash[n - 1]--;
hash[0]++;
} else {
int i = index.get(ch);
if (hash[i - 1] == 0)
return -1;
hash[i - 1]--;
hash[i]++;
}
}
for (int i = 0; i < n - 1; i++)
if (hash[i] != 0)
return -1;
return hash[n - 1];
}
}
// 蛙声是五个字母就是五个if-else，所以需要一个通用的方法
// 优雅永不过时！
七、分治-快排（分而治之）
1、颜色分类(数组分三块★★★)
class Solution {
public void sortColors(int[] nums) {
int n = nums.length, i = -1,j = -1,k = 0;
while (k < n) {
if (nums[k] == 0) {
i++;j++;
int temp = nums[k];
nums[k] = nums[j];
nums[j] = nums[i];
nums[i] = temp;
}else if(nums[k]==1){
j++;
int temp = nums[k];
nums[k]=nums[j];
nums[j]=temp;
}
k++;
}
}
}
// 000111122200210201201
// i j k
class Solution {
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) {
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, --right, i);
}
}
}
// 吴老师代码
2、排序数组★★★
class Solution {
// 快速排序
public int[] sortArray(int[] nums) {
quickSort(nums, 0, nums.length - 1);
return nums;
}
public static void quickSort(int[] nums, int l, int r) {
if (l >= r) return;
int key = nums[l + (r - l) / 2];// 使用随机数好一点
key = nems[new Random().nextInt(r-l+1)+l];
int left=l-1;
int right=r+1;
int k=l;
while(k<right){
if(nums[k]<key){
swap(nums,++left,k++);
}else if(nums[k]>key){
swap(nums,--right,k);
}else{
k++;
}
}
quickSort(nums, l,left);
quickSort(nums,right,r);
}
public static void swap(int[] nums,int x,int y){
int temp =nums[x];
nums[x]=nums[y];
nums[y]=temp;
}
}
// 选择一个基数key,将数组分为三块:{nums[i]<key}{nums[i]==key}{nums[i]>key}
// 然后对左右两块递归调用排序
分治排序思想：选择一个基数key,调整数组将小于key的元素移动到key的右侧，将大于key的元素移到key的左侧，此时key就会被移动到整个数组排序完成之后的位置，然后对key左右两部分再次递归使用分支排序。
3、快速选择算法(Top K)★★★
数组分为三部分，a、b、c代表每一部分的元素个数
[1,5,2,5]：第3大的数字是2
class Solution {
public static void swap(int[] nums, int x, int y) {
int temp = nums[x];
nums[x] = nums[y];
nums[y] = temp;
}
public int findKthLargest(int[] nums, int k) {
return quickSort(nums, 0, nums.length - 1, k);
}
public static int quickSort(int[] nums, int l, int r, int k) {
if (l == r)
return nums[l];
if(r - l + 1<=0){
System.out.println("r:"+(r));
System.out.println("l:"+(l));
System.out.println("r-l+1:"+(r-l+1));
}
int key = nums[new Random().nextInt(r - l + 1) + l];
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) {
swap(nums, --right, i);
} else {
i++;
}
}
if (r - right + 1 >= k)
return quickSort(nums, right, r, k);
else if (r - left >= k)
return key;
else
return quickSort(nums, l, left, k - r + left);
// int c = r - right + 1, b = right - left - 1;
// if (c >= k)
// return quickSort(nums, right, r, k);
// else if (c + b >= k)
// return key;
// else
// return quickSort(nums, l, left, k - b - c);
}
}
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 (l == r) {
return nums[l];
}
// 1. 按照随机选择的基准元素，将数组分三块
int key = nums[new Random().nextInt(r - l + 1) + l];
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);
}
// 2. 分情况讨论
int c = r - right + 1, b = right - left - 1;
if (c >= k)
return qsort(nums, right, r, k);
else if (c + b >= k)
return key;
else
return qsort(nums, l, left, k - b - c);
}
public void swap(int[] nums, int i, int j) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
}
指针数量太多，计算区间长度需谨慎，创建新变量记录小区间长度，大区间的长度就用小区间长度计算，避免使用下标计算出现错误
4、最小的k个数
// 排序查询最小的k个数
// 堆
//快速选择排序
class Solution {
public int[] inventoryManagement(int[] nums, int k) {
qsort(nums, 0, nums.length - 1, k);
int[] ret = new int[k];
for (int i = 0; i < k; i++) {
ret[i] = nums[i];
}
return ret;
}
public void qsort(int[] nums, int l, int r, int k) {
if (l == r) {
return ;
}
// 1. 按照随机选择的基准元素，将数组分三块
int key = nums[new Random().nextInt(r - l + 1) + l];
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);
}
// 2. 分情况讨论
int c = r - right + 1, b = right - left - 1, a = left - l + 1;
if (a > k) {
qsort(nums, l, left, k);
} else if(a+b>=k) {
return ;
}else{
qsort(nums, right, r, k - a - b);
}
}
public static void swap(int[] nums, int i, int j) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
}
八、分支-归并
1、归并排序
class Solution {
int[] temp;
// 归并排序
public int[] sortArray(int[] nums) {
temp = new int[nums.length];
mergeSort(nums, 0, nums.length-1);
return nums;
}
// 这里没有写成静态函数
public void mergeSort(int[] nums, int l, int r) {
if (l >= r)
return;
int mid = (r + l) / 2;
mergeSort(nums, l, mid);
mergeSort(nums, mid + 1, r);
// 归并排序的时候需要频繁创建临时数组，时间开销比较大，可以new一个全局的数组
// int[] temp = new int[r - l + 1];
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r) {
temp[k++]=nums[i]<=nums[j]?nums[i++]:nums[j++];
}
while (i <= mid)
temp[k++] = nums[i++];
while (j <= r)
temp[k++] = nums[j++];
for (k = 0; k < r - l + 1; k++) {
nums[l + k] = temp[k];
}
}
}
2、数组中的逆序对（hard）
暴力解法时间复杂度为O(N^2)
数组逆序对数=左半部分逆序对数+右半部分逆序对数+一左一右逆序对数
如果将两部分数组进行排序，那么在合并的时候可以利用O(1)的时间统计一左一右逆序对数，这样一来统计所有逆序对是的时间复杂度就变成了对数组归并排序的时间复杂度，即O(N*logN)
class Solution {
int[] temp;
public int reversePairs(int[] record) {
// 特殊情况 record为空
int n = record.length;
temp = new int[n];
return mergeSort(record, 0, n - 1);
}
public int mergeSort(int[] arr, int left, int right) {
if (left >= right) // 防止特殊情况 record数组为空
return 0;
int mid = left + (right - left) / 2;
int a = mergeSort(arr, left, mid);
int b = mergeSort(arr, mid + 1, right);
int c = 0;
int i = left, j = mid + 1, k = 0, n = right - left + 1;
// [left,right]=[left,mid][mid+1,right]
while (i <= mid && j <= right) {
if (arr[i] > arr[j]) {
temp[k++] = arr[i++];
c += right - j + 1;
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid)
temp[k++] = arr[i++];
while (j <= right)
temp[k++] = arr[j++];
for (int x = 0; x < n; x++) {
arr[left + x] = temp[x];
}
return a + b + c;
}
}
// 8 6 4 2 1
// 5 3 1
3、 计算右侧小于当前元素的个数（hard）
找每一个位置的逆序对的数量，在第二题中我们利用归并排序统计了数组中逆序对的数量，这会导致数组元素位置移动，这就对统计每个位置逆序对的数量增加了难度。因为数组中元素并不是唯一的，所以无法使用哈希表去确定某个元素的下标。解决方案是创建一个数组存储每个元素的下标
nums：5、2、6、1
index：0、1、2、3
在归并排序时会改变nums中元素的顺序，知道将index的元素同步移动即可找到该元素的初始位置，有一个小细节，对nums合并排序的时候创建了辅助数组，index数组要同步移动，所以也要进行合并，那么就也需要创建一个辅助数组来完成index的合并。如何统计每个位置的逆序对数量呢？对于数组[left,right]=[left<=x<=mid]+[mid+1<=y<=right];
class Solution {
int[] temp1;
int[] temp2;
int[] index;
// 在归并排序过程中，数组元素会发生移动
// 使用index同步移动来存储某元素原始下标即：
// 对于任意下标i，index[i]是nums[i]的原始下标,i是nums[i]的当前下标
public List<Integer> countSmaller(int[] nums) {
// 辅助数组
temp1 = new int[nums.length];
temp2 = new int[nums.length];
// index数组，标记nums数组元素原下标，并同步与nums进行排序
index = new int[nums.length];
// 对返回值进行初始化,也可将返回值创建成int[]，最后在进行转化。
List<Integer> arr = new ArrayList<>();
for (int i = 0; i < nums.length; i++){
index[i] = i;
arr.add(0);
}
mergeSort(nums, 0, nums.length - 1, arr);
return arr;
}
public void mergeSort(int[] nums, int left, int right, List<Integer> arr) {
if (left == right) return; // 细分到
int mid = left + (right - left) / 2;
mergeSort(nums, left, mid, arr);
mergeSort(nums, mid + 1, right, arr);
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (nums[i] > nums[j]) {
arr.set(index[i],arr.get(index[i])+right-j+1);
temp2[k] = index[i];
temp1[k++] = nums[i++];
} else {
temp2[k] = index[j];
temp1[k++] = nums[j++];
}
}
while (i <= mid) {
temp2[k] = index[i];
temp1[k++] = nums[i++];
}
while (j <= right) {
temp2[k] = index[j];
temp1[k++] = nums[j++];
}
for (int x = 0; x < right - left + 1; x++) {
nums[x + left] = temp1[x];
index[x + left] = temp2[x];
}
}
}
// 6 4 2
// 5 3 1
4、 翻转对（hard）
class Solution {
int[] temp;
public int reversePairs(int[] nums) {
temp = new int[nums.length];
return megerSort(nums, 0, nums.length - 1);
}
public int megerSort(int[] nums, int left, int right) {
if (left >= right) {
return 0;
}
int ret = 0;
int mid = left + (right - left) / 2;
ret += megerSort(nums, left, mid);
ret += megerSort(nums, mid + 1, right);
// 统计重要反转对比较难在合并排序中实现，所以可以单独处理
// [left,mid][mid+1,right] 两个降序的数组
// 升序也可以
int l = left, r = mid + 1;
while (l <= mid && r <= right) {
// 5 4
// 3 2 1
if ((long) nums[l] > (long) 2 * nums[r]) {
ret += right - r + 1;
l++;
} else {
r++;
}
}
// 合并排序,降序
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (nums[i] > nums[j]) {
temp[k++] = nums[i++];
} else {
temp[k++] = nums[j++];
}
}
while (i <= mid)
temp[k++] = nums[i++];
while (j <= right)
temp[k++] = nums[j++];
for (int x = 0; x < right - left + 1; x++) {
nums[left + x] = temp[x];
}
return ret;
}
}
归并排序过程中我们会得到两个排序的数组，在将两个数组合并排序之前，使用同向双指针统计翻转的数量。
九、链表
0、链表常用技巧和操作
常用技巧：
- 画图！！！直观、形象、便于理解
- 引入虚拟"头"节点
- 便于处理边界情况
- 方便操作链表
- 不要吝啬空间，大胆定义变量
- 快慢双指针
- 判环
- 找链表环的入口
- 找链表倒数第n个结点
链表中常见操作：
- 创建一个新的结点
- 尾插
- 头插
1、两数相加
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode ret = new ListNode();
ListNode end = ret;
ListNode cur1 = l1;
ListNode cur2 = l2;
int carry=0;
while(cur1!=null&&cur2!=null){
int a = cur1.val + cur2.val + carry;
end.next = new ListNode(a%10);
end = end.next;
carry = a/10;
cur1 = cur1.next;
cur2 = cur2.next;
}
while(cur1!=null){
int a = cur1.val + carry;
end.next = new ListNode(a%10);
end = end.next;
carry = a/10;
cur1 = cur1.next;
}
while(cur2!=null){
int a = cur2.val + carry;
end.next = new ListNode(a%10);
end = end.next;
carry = a/10;
cur2 = cur2.next;
}
if(carry!=0){
end.next = new ListNode(carry);
end = end.next;
}
return ret.next;
}
}
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode cur1 = l1, cur2 = l2;
ListNode newHead = new ListNode(0); // 创建⼀个虚拟头结点，⽅便记录结果
ListNode prev = newHead; // 尾插操作的尾指针
int t = 0; // 记录进位
while (cur1 != null || cur2 != null || t != 0) {
// 先加上第⼀个链表
if (cur1 != null) {
t += cur1.val;
cur1 = cur1.next;
}
// 加上第⼆个链表
if (cur2 != null) {
t += cur2.val;
cur2 = cur2.next;
}
prev.next = new ListNode(t % 10);
prev = prev.next;
t /= 10;
}
return newHead.next;
}
}
// 模拟加法,当链表都为null且进位为0的时候加法才结束
2、两辆交换链表中的结点
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode newHead = new ListNode(0,head);
ListNode p = newHead;
ListNode q = p.next;
while(p.next!=null&&q.next!=null){
p.next=q.next;
p=p.next;
q.next=p.next;
p.next=q;
p=q;
q=q.next;
}
return newHead.next;
}
}
class Solution {
public ListNode swapPairs(ListNode head) {
if(head==null||head.next==null){
return head;
}
ListNode p=head;
head=head.next;
p.next=head.next;
head.next=p;
p.next=swapPairs(p.next);
return head;
}
}
第一种迭代法画图会非常好理解
3、链表重排
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public void reorderList(ListNode head) {
// 将链表一分为二再进行合并
if(head==null||head.next==null||head.next.next==null) return;
// 1、找到链表的中间结点（快慢双指针）
// 2、将后半段链表逆序（三指针，头插法）
// 3、将两个链表合并（依次出一个元素）
ListNode newHead = new ListNode(0,head);
ListNode fast = newHead;
ListNode slow = newHead;
while(fast!=null&&fast.next!=null){
fast=fast.next.next;
slow=slow.next;
}
//
ListNode prev = new ListNode(0,slow.next);
slow.next=null;
slow = prev.next;
ListNode pn =prev.next;
ListNode cur = slow.next;
while(cur!=null){
prev.next=cur;
slow.next=cur.next;
cur.next=pn;
cur=slow.next;
pn = prev.next;
}
slow = prev.next;
ListNode cur1 = head;
ListNode cur2 = slow;
ListNode ret = new ListNode(0);
prev = ret;
while (cur1 != null) {
// 先放第⼀个链表
prev.next = cur1;
prev = cur1;
cur1 = cur1.next;
// 在合并第⼆个链表
if (cur2 != null) {
prev.next = cur2;
prev = cur2;
cur2 = cur2.next;
}
}
}
}
class Solution {
public void reorderList(ListNode head) {
// 处理边界情况
if (head == null || head.next == null || head.next.next == null)
return;
// 1. 找链表的中间节点 - 快慢双指针（⼀定要画图分析 slow 的落点）
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// 2. 把 slow 后⾯的部分给逆序 - 头插法
ListNode head2 = new ListNode(0);
[0]
[4,5,6,7]
ListNode cur = slow.next;
slow.next = null; // 把两个链表分离
while (cur != null) {
ListNode next = cur.next;
cur.next = head2.next;
head2.next = cur;
cur = next;
}
// 3. 合并两个链表 - 双指针
ListNode cur1 = head, cur2 = head2.next;
ListNode ret = new ListNode(0);
ListNode prev = ret;
while (cur1 != null) {
// 先放第⼀个链表
prev.next = cur1;
prev = cur1;
cur1 = cur1.next;
// 在合并第⼆个链表
if (cur2 != null) {
prev.next = cur2;
prev = cur2;
cur2 = cur2.next;
}
}
}
}
链表重排序：快慢指针将链表平分为两部分+对后半部分进行逆序+两链表合并
链表逆序：头插法，双指针
ListNode head = new ListNode(0);
ListNode p = head; // 让结点p等于head
ListNode q.next = head; // 让结点q指向head
4、合并k个升序列表
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
ListNode ret = new ListNode();
ListNode end = ret;
int index = 0;
while (true) {
index = -1;
int min = 0x3f3f3f;
for (int i = 0; i < lists.length; i++) {
if (lists[i] != null && lists[i].val < min) {
min = lists[i].val;
index = i;
}
}
if (index != -1) {
ListNode next = lists[index].next;
end.next = lists[index];
lists[index].next=null;
end=end.next;
lists[index] = next;
} else {
break;
}
}
return ret.next;
}
}
// 暴力解法
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> heap = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);
// 将所有头结点加⼊到⼩根堆中
for (ListNode l : lists)
if (l != null)
heap.offer(l);
// 合并
ListNode ret = new ListNode(0);
ListNode prev = ret;
while (!heap.isEmpty()) {
ListNode t = heap.poll();
prev.next = t;
prev = t;
if (t.next != null)
heap.offer(t.next);
}
return ret.next;
}
}
// java常见数据结构的方法
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists.length==0) return null;
return merge(lists,0,lists.length-1);
}
public ListNode merge(ListNode[] lists , int left,int right){
if(left>right) return null;
if(left==right) return lists[left];
ListNode ret = new ListNode();
int mid = left + (right - left)/2;
ListNode p = merge(lists,left,mid);
ListNode q = merge(lists,mid+1,right);
return mergeList(p,q);
}
public ListNode mergeList(ListNode p,ListNode q){
if(p==null) return q;
if(q==null) return p;
ListNode head = new ListNode(0);
ListNode prev = head;
while(p!=null&&q!=null){
if(p.val<q.val){
prev.next=p;
prev=prev.next;
p=p.next;
}else{
prev.next=q;
prev = q;
q=q.next;
}
}
if(p!=null) prev.next = p;
if(q!=null) prev.next = q;
return head.next;
}
}
5、k个一组翻转链表
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if(k==1) return head;
int len=0;
ListNode cur = head;
while(cur!=null){
len++;
cur=cur.next;
}
// 有n段需要逆序操作
int n = len/k;
// 逆序
ListNode newHead = new ListNode(0);
ListNode prev = newHead;
cur=head;
ListNode next = cur.next;
for(int i=0;i<n;i++){
// 头插法
for(int j=0;j<k;j++){
cur.next = prev.next;
prev.next = cur;
cur = next;
if(next!=null)
next=next.next;
}
while(prev.next!=null) prev=prev.next;
}
prev.next=cur;
return newHead.next;
}
}
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
// 1. 先求出需要逆序多少组
int n = 0;
ListNode cur = head;
while (cur != null) {
cur = cur.next;
n++;
}
n /= k;
// 2. 重复 n 次：⻓度为 k 的链表的逆序
ListNode newHead = new ListNode(0);
ListNode prev = newHead;
cur = head;
for (int i = 0; i < n; i++) {
ListNode tmp = cur;
for (int j = 0; j < k; j++) {
// 头插的逻辑
ListNode next = cur.next;
cur.next = prev.next;
prev.next = cur;
cur = next;
}
prev = tmp;
}
// 把后⾯不需要逆序的部分连接上
prev.next = cur;
return newHead.next;
}
}
// 吴老师这个在处理next结点的时候优雅一点
十、哈希表
0、哈希表简介
哈希表是什么？
——存储数据的容器，空间复杂度O(n)
哈希表有啥用？
——快速查找某个元素,时间复杂度O(1)
什么时候用哈希表？
——频繁的查询查找某一个数
怎么用哈希表？
——1.容器(哈希表)；2、用数组模拟简易哈希表(统计字符或数组很小时)；3、位图
1、两数之和
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> hash = new HashMap<>();
for(int i=0;i<nums.length;i++){
if(hash.containsKey(target-nums[i])){
return new int[]{hash.get(target-nums[i]),i};
}else{
hash.put(nums[i],i);
}
}
return new int[]{-1,-1};// 照顾编译器
}
}
// class Solution {
// public int[] twoSum(int[] nums, int target) {
// //双指针
// }
// }
2、判断是否为字符重新排序
class Solution {
}
3、存在重复元素
class Solution {
public boolean containsDuplicate(int[] nums) {
Set<Integer> hash = new HashSet<>();
for(int i=0;i<nums.length;i++){
if(hash.contains(nums[i])) return true;
else hash.add(nums[i]);
}
return false;
}
}
4、存在重复元素II
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Map<Integer,Integer> hash = new HashMap<>();
for(int i=0;i<nums.length;i++){
if(hash.containsKey(nums[i]) && Math.abs(hash.get(nums[i])-i)<=k){
return true;
}
hash.put(nums[i],i);
}
return false;
}
}
5、字母异位词分组
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> ret = new ArrayList<>();
int[][] hash = new int[strs.length][26];
for(int i=0;i<strs.length;i++){
boolean flag = true;
for(int j=0;j<ret.size();j++){
if(CheckPermutation(hash[j],strs[i])){
ret.get(j).add(strs[i]);
flag=false;
break;
}
}
if(flag){
int m = ret.size();
char[] s = strs[i].toCharArray();
for(char c:s){
hash[m][c-'a']++;
}
List<String> list = new ArrayList<>();
list.add(strs[i]);
ret.add(list);
}
}
return ret;
}
public boolean CheckPermutation(int[] hash, String s) {
char[] chars = s.toCharArray();
int[] hash2 = new int[26];
for(char c:chars){
hash2[c-'a']++;
}
for(int i=0;i<26;i++){
if(hash[i]!=hash2[i]) return false;
}
return true;
}
}
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> hash = new HashMap<>();
// 1. 先把所有的字⺟异位词分组
for (String s : strs) {
char[] tmp = s.toCharArray();
Arrays.sort(tmp);
String key = new String(tmp);
if (!hash.containsKey(key)) {
hash.put(key, new ArrayList());
}
hash.get(key).add(s);
}
// 2. 提取结果
return new ArrayList(hash.values());
}
}
通过对字符串的字符数组排序来优化判断两个字符串是否是异词★
十一、字符串专题
0、kmp算法
1、最长公共前缀
class Solution {
public String longestCommonPrefix(String[] strs) {
// 思路一：两两比较，每次比较得到一个公共前缀长度，取最小值即可
// 思路二：统一比较\
// 这里使用第二个思路：
char[] s = strs[0].toCharArray();
int i=0;
while(i<s.length){
boolean flag = false;
for(int j=1;j<strs.length;j++){
if(!(i<strs[j].length() && s[i]==strs[j].charAt(i))){
flag=true;
}
}
if(flag){
break;
}
i++;
}
return strs[0].substring(0,i);
}
}
2、最长回文子串
class Solution {
public String longestPalindrome(String ss) {
// 马拉车算法
// 动态规划
// 中心扩展
int left = 0;
int right = 0;
int max = 0;
char[] s = ss.toCharArray();
int len = s.length;
for (int i = 0; i < len; i++) {
int l = i - 1;
int r = i + 1;
while (l >= 0 && r < len && s[l] == s[r]) {
l--;
r++;
}
if (max < r - l - 1) {
left = l + 1;
right = r - 1;
max = r - l - 1;
}
l = i;
r = i + 1;
while (l >= 0 && r < len && s[l] == s[r]) {
// 更新结果不用写在里面，在最外面每次循环更新一即可
// if (max < r - l + 1) {
// left = l;
// right = r;
// max = r - l + 1;
// }
l--;
r++;
}
if (max < r - l - 1) {
left = l + 1;
right = r - 1;
max = r - l - 1;
}
}
return ss.substring(left, right + 1);
}
}
// 中心扩展法：利用回文字符串的对成型，时间复杂度O(N^2);
3、二进制求和
class Solution {
public String addBinary(String a, String b) {
// 思路一：
// 1、将字符串转化为十进制数值
// 2、数值求和
// 3、将十进制数值转化为二进制字符串
// 4、测试的数字太大了，long也不行，所以这个思路有局限
/*
long value_A = 0;
long value_B = 0;
for(int i=0;i<a.length();i++){
if(a.charAt(a.length()-1-i)=='1'){
value_A+=(int)Math.pow(2,i);
}
}
for(int i=0;i<b.length();i++){
if(b.charAt(b.length()-1-i)=='1'){
value_B+=(int)Math.pow(2,i);
}
}
long c = value_A+value_B;
StringBuffer ret = new StringBuffer();
if(c==0) return "0";
while(c>0){
ret.append(Long.toString(c%2));
c/=2;
}
ret.reverse();
return new String(ret);
*/
// 思路二：
// 1、直接模拟二进制数相加
int len_a = a.length()-1;
int len_b = b.length()-1;
int carry=0;
StringBuffer ret = new StringBuffer();
while(len_a>=0 && len_b>=0){
carry+=a.charAt(len_a--)=='0'?0:1;
carry+=b.charAt(len_b--)=='0'?0:1;
ret.append(carry%2);
carry/=2;
}
// 10101
// 10
while(len_a>=0){
carry+=a.charAt(len_a--)=='0'?0:1;
ret.append(carry%2);
carry/=2;
}
while(len_b>=0){
carry+=b.charAt(len_b--)=='0'?0:1;
ret.append(carry%2);
carry/=2;
}
if(carry==1) ret.append('1');
return new String(ret.reverse());
}
}
class Solution {
public String addBinary(String a, String b) {
StringBuffer ret = new StringBuffer();
int cur1 = a.length() - 1, cur2 = b.length() - 1, t = 0;
while (cur1 >= 0 || cur2 >= 0 || t != 0) {
if (cur1 >= 0)
t += a.charAt(cur1--) - '0';
if (cur2 >= 0)
t += b.charAt(cur2--) - '0';
ret.append((char) ('0' + (t % 2)));
t /= 2;
}
ret.reverse();
return ret.toString();
}
}
// 优雅永不过时
高精度加法、高精度减法、高精度乘法、高精度触除法
本质就是模拟算数的运算过程
5、字符串相乘★★★★
class Solution {
public String multiply(String num1, String num2) {
// 思路一：模拟乘法
// 1、num2的每一位乘以num1的值的求和,每一次相乘都会处理进位
// 不想处理前导0,所以加了这个边界处理
if(num1.equals("0")||num2.equals("0")) return "0";
StringBuffer ret = new StringBuffer();
StringBuffer carry = new StringBuffer();
for (int i = num2.length() - 1; i >= 0; i--) {
int a = num2.charAt(i) - '0';
StringBuffer temp = multiply(num1, a);
temp.append(carry);
carry.append('0');
ret = addBinary(ret.toString(),temp.toString());
}
// 处理前导0
while(ret.length()>1 && ret.charAt(0)=='0'){
ret.delete(0,1);
}
return ret.toString();
}
// 字符串数字*个位数
public StringBuffer multiply(String num,int a){
StringBuffer ret = new StringBuffer();
int carry = 0;
int len = num.length()-1;
while(len>=0){
carry+=a*(num.charAt(len--)-'0');
ret.append(carry%10);
carry/=10;
}
if(carry!=0) ret.append(carry);
return ret.reverse();
}
// 两字符串数字相加
public StringBuffer addBinary(String a, String b) {
StringBuffer ret = new StringBuffer();
int cur1 = a.length() - 1, cur2 = b.length() - 1, t = 0;
while (cur1 >= 0 || cur2 >= 0 || t != 0) {
if (cur1 >= 0)
t += a.charAt(cur1--) - '0';
if (cur2 >= 0)
t += b.charAt(cur2--) - '0';
ret.append((char) ('0' + (t % 10)));
t /= 10;
}
ret.reverse();
return ret;
}
}
// 1、先求无进位相加
// 2、最后处理进位
// 三个细节
// 1、高位相乘要补“0”
// 2、处理前导“0”
// 3、注意计算结果顺序
class Solution {
public String multiply(String num1, String num2) {
int m = num1.length(), n = num2.length();
char[] n1 = new StringBuffer(num1).reverse().toString().toCharArray();
char[] n2 = new StringBuffer(num2).reverse().toString().toCharArray();
int[] tmp = new int[m + n - 1];
// 1. ⽆进位相乘后相加
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
tmp[i + j] += (n1[i] - '0') * (n2[j] - '0');
// 2. 处理进位
int cur = 0, t = 0;
StringBuffer ret = new StringBuffer();
while (cur < m + n - 1 || t != 0) {
if (cur < m + n - 1)
t += tmp[cur++];
// 直接将结果添加子串去了，不需要在修改数组
ret.append((char) (t % 10 + '0'));
t /= 10;
}
// 3. 处理进位
while (ret.length() > 1 && ret.charAt(ret.length() - 1) == '0')
ret.deleteCharAt((ret.length() - 1));
return ret.reverse().toString();
}
}
// NBA!!!
十二、栈
1、删除字符中所有相邻的重复项★★★
class Solution {
public String removeDuplicates(String s) {
// 双指针
// acbbcaacc
// 两种删除方式的结果是不一样的：
// 每次删除字符串中所有的相邻重复项
// 每次只删除一个相邻重复项
// 双指针要走到头才行
int slen = s.length();
StringBuffer temp = removeDuplicate(s);
while(slen>temp.length()){
slen=temp.length();
temp = removeDuplicate(temp.toString());
}
return temp.toString();
}
// 在字符串str上一边遍历一遍删除，删除的时间复杂度为O(N),遍历一遍也是O(N)
// 整体就是O(N^2)的时间复杂度
// 反复去除重复项,所以总时间复杂度为O(K*N^2)
public StringBuffer removeDuplicate(String s){
int n = s.length();
int left=n-2,right=n-1;
StringBuffer str = new StringBuffer(s);
while(left>=0){
if(s.charAt(left)==s.charAt(right)){
str.delete(left,right+1);
left-=2;
right-=2;
}else{
left--;
right--;
}
}
return str;
}
}
// debug:
// abbaccb => aab => b
public String removeDuplicates(String s){
StringBuffer str = new StringBuffer();
for(int i=0;i<s.length();i++){
if(str.length()>0 && s.charAt(i)==str.charAt(str.length()-1)){
str.delete(str.length()-1,str.length());
}else{
str.append(s.charAt(i));
}
}
return str.toString();
}
// debug:
// abbaccb => b
// 时间复杂度为O(N),仅需遍历一遍数组即可。
class Solution {
public String removeDuplicates(String _s)
{
StringBuffer ret = new StringBuffer(); // ⽤数组来模拟栈结构
char[] s = _s.toCharArray();
for (char ch : s) {
if (ret.length() > 0 && ch == ret.charAt(ret.length() - 1)) {
// 出栈
ret.deleteCharAt(ret.length() - 1);
} else {
// 进栈
ret.append(ch);
}
}
return ret.toString();
}
}
// 熟悉每一个java常见对象的方法(String、StringBuffer、HashMap)
示例：
input：aaa，output：a
input：abbacca，output：a
一开始写的时候理解错题目意思了，把aaa当作相邻项一起给删除了
2、比较含退格的字符串
class Solution {
public boolean backspaceCompare(String s, String t) {
return fun(s).equals(fun(t));
}
public String fun(String t){
StringBuffer q = new StringBuffer();
for (int i = 0; i < t.length(); i++) {
if (t.charAt(i) == '#') {
if (q.length() > 0)
q.delete(q.length() - 1, q.length());
} else {
q.append(t.charAt(i));
}
}
return q.toString();
}
}
3、基本计算器II ★★★
class Solution {
public int calculate(String s) {
// 读题：
// 没有负数
// 无括号
// 结果在int范围内
List<String> list = new ArrayList<>();
int left=0,right=0;
while(right < s.length() ){
char ch = s.charAt(right);
if(ch=='+'||ch=='-'||ch=='*'||ch=='/'){
String temp = s.substring(left,right);
list.add(temp.strip());
temp = s.substring(right,right+1);
list.add(temp);
left = right+1;
}
right++;
}
list.add(s.substring(left,right).strip());
Stack<Integer> stack = new Stack<>();
char sign='+';
for(int i=0;i<list.size();i++){
String str = list.get(i);
if(str.equals("+")||str.equals("-")){
sign=str.equals("+")?'+':'-';
}else if(str.equals("*")){
i++;
int num = Integer.parseInt(list.get(i));
int pop = stack.pop();
stack.push(pop*num);
}else if(str.equals("/")){
i++;
int num = Integer.parseInt(list.get(i));
int pop = stack.pop();
stack.push(pop/num);
}else{
int num = Integer.parseInt(str);
if(sign=='-'){
stack.push(-num);
}else{
stack.push(num);
}
}
}
int ret = 0;
while(!stack.isEmpty()){
ret+=stack.pop();
}
return ret;
}
}
class Solution1 {
public int calculate(String _s) {
Deque<Integer> st = new ArrayDeque<>();
char op = '+';
int i = 0, n = _s.length();
char[] s = _s.toCharArray();
while (i < n) {
if (s[i] == ' ')
i++;
else if (s[i] >= '0' && s[i] <= '9') {
int tmp = 0;
while (i < n && s[i] >= '0' && s[i] <= '9') {
tmp = tmp * 10 + (s[i] - '0');
i++;
}
if (op == '+')
st.push(tmp);
else if (op == '-')
st.push(-tmp);
else if (op == '*')
st.push(st.pop() * tmp);
else
st.push(st.pop() / tmp);
} else {
op = s[i];
i++;
}
}
// 统计结果
int ret = 0;
while (!st.isEmpty()) {
ret += st.pop();
}
return ret;
}
}
题目保证表达式有结果，表达式中包含空格，先对字符串表达式做处理，数字(1，12，123)和运算符加到List list 中。遍历list：
1、如果是数值，将数值压入站内，若数值前是负号则存入该数的相反数，所以需要一个变量存储运算符(+、-)；
2、如果是+、-运算符，使用变量sign记录
2、如果遇到*、/运算符，因为优先级比较高，则需要将*、/两侧的数值进行运算，将运算的结果压入栈内，最后对站内的数值求和即可
// 双栈解法
// 字符串表达式的通用解法,包含更多运算符及括号
4、字符串解码★★★
实例：
class Solution {
public String decodeString(String s) {
// 存在嵌套解码，所以要是栈来解决，由内而外解码
Stack<String> strs = new Stack<>();
Stack<Integer> nums = new Stack<>();
strs.push("");
int i=0;
while(i<s.length()){
// 数字
if('0'<=s.charAt(i) && s.charAt(i)<= '9'){
int num = 0;
while(i<s.length()&&'0'<=s.charAt(i) && s.charAt(i)<= '9'){
num=num*10+(s.charAt(i++)-'0');
}
nums.push(num);
}else if(s.charAt(i)=='['){
i++;
StringBuffer str = new StringBuffer();
while(i<s.length()&&'a'<=s.charAt(i) && s.charAt(i)<= 'z'){
str.append(s.charAt(i++));
}
strs.push(str.toString());
}else if('a'<=s.charAt(i) && s.charAt(i)<= 'z'){
StringBuffer str = new StringBuffer(strs.pop());
while(i<s.length()&&'a'<=s.charAt(i) && s.charAt(i)<= 'z'){
str.append(s.charAt(i++));
}
strs.push(str.toString());
}else if(s.charAt(i)==']'){
i++;
int num = nums.pop();
String str = strs.pop();
StringBuffer newStr = new StringBuffer(strs.pop());
while(num-->0) newStr.append(str);
strs.push(newStr.toString());
}
}
return strs.pop();
}
}
class Solution {
public String decodeString(String _s) {
Stack<StringBuffer> st = new Stack<>();
st.push(new StringBuffer()); // 先放⼀个空串进去
Stack<Integer> nums = new Stack<>();
int i = 0, n = _s.length();
char[] s = _s.toCharArray();
while (i < n) {
if (s[i] >= '0' && s[i] <= '9') {
int tmp = 0;
while (i < n && s[i] >= '0' && s[i] <= '9') {
tmp = tmp * 10 + (s[i] - '0');
i++;
}
nums.push(tmp);
} else if (s[i] == '[') {
i++; // 把后⾯的字符串提取出来
StringBuffer tmp = new StringBuffer();
while (i < n && s[i] >= 'a' && s[i] <= 'z') {
tmp.append(s[i]);
i++;
}
st.push(tmp);
} else if (s[i] == ']') {
// 解析
StringBuffer tmp = st.pop();
int k = nums.pop();
while (k-- != 0) {
st.peek().append(tmp);
}
i++;
} else {
StringBuffer tmp = new StringBuffer();
while (i < n && s[i] >= 'a' && s[i] <= 'z') {
tmp.append(s[i]);
i++;
}
st.peek().append(tmp);
}
}
return st.peek().toString();
}
}
// 吴老师用了一个 Stack<StringBuffer> strs = new Stack<>();
5、验证栈序列
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
Stack<Integer> stack = new Stack<>();
int j=0;
for(int i=0;i<pushed.length;i++){
stack.push(pushed[i]);
while(!stack.isEmpty()&&stack.peek()==popped[j]){
j++;
stack.pop();
}
}
// while(!stack.isEmpty()&&stack.pop()==popped[j]){
// j++;
// }
return stack.isEmpty();
}
}
十三、队列+宽度优先搜索(BFS)
1、N叉树的层序遍历
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> ret = new ArrayList<>();
if(root == null) return ret;
Queue<Node> queue = new ArrayDeque<>();
queue.add(root);
while(!queue.isEmpty()){
int len = queue.size();
List<Integer> list = new ArrayList<>();
for(int i=0;i<len;i++){
Node top = queue.poll();
list.add(top.val);
for(int j=0;j<top.children.size();j++){
queue.add(top.children.get(j));
}
}
ret.add(list);
}
return ret;
}
}
//
2、二叉树的锯齿形层序遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
Queue<TreeNode> queue = new ArrayDeque<>();
List<List<Integer>> ret = new ArrayList<>();
if(root == null) return ret;
int level =1;
queue.add(root);
while(!queue.isEmpty()){
List<Integer> list = new ArrayList<>();
int qz = queue.size();
for(int i=0;i<qz;i++){
TreeNode treeNode = queue.poll();
list.add(treeNode.val);
if(treeNode.left!=null) queue.add(treeNode.left);
if(treeNode.right!=null) queue.add(treeNode.right);
}
// 这解法真暴力
if(level%2==0) Collections.reverse(list);
ret.add(list);
level++;
}
return ret;
}
}
3、二叉树最大宽度
思路一：
层序遍历，结点为null也会被加入到队列中去，循环遍历队列去计算每一层的宽度，取最大值,因为要存储空结点，所以极端情况下根本存不下这个二叉树
根节点Node编号为x,则Node.left编号为2x,Node.right编号为2x+1
给每个结点添加编号，结点入队列是不需要存储空结点，最大宽度使用队列两端结点编号的差值计算
细节问题：结点的编号是由可能溢出的，但是两个结点距离肯定是合法的，根据下图可知，不要对溢出的编号做任何处理，计算的结果也是正确的。C++因为int溢出会报错，所以可以使用无符号整型来存储下标。因为需要队列两端的结点，所以可以使用数组来模拟队列，方便查找尾结点。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int widthOfBinaryTree(TreeNode root) {
List<Pair<TreeNode, Integer>> q = new ArrayList<>(); // ⽤数组模拟队列
q.add(new Pair<TreeNode, Integer>(root, 1));
int ret = 0; // 记录最终结果
while (!q.isEmpty()) {
// 先更新⼀下这⼀层的宽度
Pair<TreeNode, Integer> t1 = q.get(0);
Pair<TreeNode, Integer> t2 = q.get(q.size() - 1);
ret = Math.max(ret, t2.getValue() - t1.getValue() + 1);
// 让下⼀层进队
List<Pair<TreeNode, Integer>> tmp = new ArrayList<>();
for (Pair<TreeNode, Integer> t : q) {
TreeNode node = t.getKey();
int index = t.getValue();
if (node.left != null) {
tmp.add(new Pair<TreeNode, Integer>(node.left, index * 2));
}
if (node.right != null) {
tmp.add(new Pair<TreeNode, Integer>(node.right, index * 2
+ 1));
}
}
// 覆盖原来的队列，这样才能求出某一层的宽度
q = tmp;
}
return ret;
}
}
4、每个树行中找最大值
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> largestValues(TreeNode root) {
Queue<TreeNode> queue = new ArrayDeque<>();
List<Integer> ret = new ArrayList<>();
if(root==null) return ret;
queue.add(root);
while(!queue.isEmpty()){
int max=Integer.MIN_VALUE;
int qz = queue.size();
for(int i=0;i<qz;i++){
TreeNode node = queue.poll();
max = Math.max(max,node.val);
if(node.left!=null) queue.add(node.left);
if(node.right!=null) queue.add(node.right);
}
ret.add(max);
}
return ret;
}
}
十四、优先级队列(堆)
1、最后一块石头的重量
class Solution {
public int lastStoneWeight(int[] stones) {
// 创建一个大根堆，将元素都放入大根堆
// 将两个最大的石头碰撞，碰撞的结果放入大根堆、
// 重复第二步，直到只剩一个石头或者没有
PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> b - a);
for(int stone:stones){
queue.add(stone);
}
while(queue.size()>1){
int m = queue.poll();
int n = queue.poll();
int t = m-n;
if(t!=0){
queue.add(t);
}
}
if(queue.isEmpty()) return 0;
return queue.poll();
}
}
2、数据流中的第k大元素
class KthLargest {
// 创建⼀个⼤⼩为 k 的⼩根堆
PriorityQueue<Integer> heap;
int _k;
public KthLargest(int k, int[] nums) {
_k = k;
heap = new PriorityQueue<>();
for (int x : nums) {
heap.offer(x);
if (heap.size() > _k) {
heap.poll();
}
}
}
public int add(int val) {
heap.offer(val);
if (heap.size() > _k) {
heap.poll();
}
return heap.peek();
}
}
/**
* Your KthLargest object will be instantiated and called as such:
* KthLargest obj = new KthLargest(k, nums);
* int param_1 = obj.add(val);
*/
算法原理：创建一个小根堆，始终保持堆中最多有k个元素，找第k大的元素只需要返回根节点即可。
PriorityQueue 是 Java 中的一种数据结构,它可以根据元素的优先级来进行存储和检索。以下是 PriorityQueue 中常用的几个方法:
- add(E element): 向队列中添加一个元素。如果添加成功,返回 true,否则抛出异常。
- offer(E element): 向队列中添加一个元素。如果添加成功,返回 true,否则返回 false。
- poll(): 获取并移除队列头部的元素。如果队列为空,返回 null。
- peek(): 获取但不移除队列头部的元素。如果队列为空,返回 null。
- remove(Object o): 从队列中移除指定的元素。如果移除成功,返回 true,否则返回 false。
- contains(Object o): 检查队列中是否包含指定的元素。
- size(): 返回队列中元素的个数。
- clear(): 移除队列中的所有元素。
- iterator(): 返回一个迭代器,用于遍历队列中的元素。
3、前k个高频词
class Solution {
public List<String> topKFrequent(String[] words, int k) {
// 创建大根堆，存储键值对<frequency，str>
// 1、预处理，统计单词的频率
Map<String, Integer> hash = new HashMap<>();
for (String word : words) {
hash.put(word, hash.getOrDefault(word, 0) + 1);
}
// 2、创建小根堆
PriorityQueue<Pair<String, Integer>> heap = new PriorityQueue<>(
(a, b) -> {
if (a.getValue()==b.getValue()) {
return b.getKey().compareTo(a.getKey());
}
return a.getValue() - b.getValue();
});
// 3、求topK
for (Map.Entry<String, Integer> e : hash.entrySet()) {
heap.offer(new Pair<>(e.getKey(), e.getValue()));
if (heap.size() > k) {
heap.poll();
}
}
// 4. 提取结果
List<String> ret = new ArrayList<>();
while (!heap.isEmpty()) {
ret.add(heap.poll().getKey());
}
// 逆序数组
Collections.reverse(ret);
return ret;
}
}
4、数据流的中位数
class MedianFinder {
PriorityQueue<Integer> left;
PriorityQueue<Integer> right;
public MedianFinder() {
left = new PriorityQueue<>((a, b) -> b - a); // 大根堆
right = new PriorityQueue<>((a, b) -> a - b);// 小根堆
}
public void addNum(int num) {
// 分情况讨论
if (left.size() == right.size()) {
if (left.isEmpty() || num <= left.peek()) {
left.offer(num);
} else {
right.offer(num);
left.offer(right.poll());
}
} else {
if (num <= left.peek()) {
left.offer(num);
right.offer(left.poll());
} else {
right.offer(num);
}
}
}
public double findMedian() {
if (left.size() == right.size())
return (left.peek() + right.peek()) / 2.0;
else
return left.peek();
}
}
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.addNum(num);
* double param_2 = obj.findMedian();
*/
大小根堆：使用大根堆存储数据流的前半部分，使用小根堆存储数据流的后半部分。
十五、BFS
1、解决 FloodFill 算法_FloodFill 算法简介
// 寻找性质相同的联通块
2、图像渲染
class Solution {
public int[][] floodFill(int[][] image, int sr, int sc, int color) {
// 宽度优先遍历
int prev = image[sr][sc];
if (prev == color)
return image;
// 方向
int[] di = new int[] { 0, 0, 1, -1 };
int[] dj = new int[] { 1, -1, 0, 0 };
// 队列
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[] { sr, sc });
int m = image.length, n = image[0].length;
while (!queue.isEmpty()) {
int[] arr = queue.poll();
int x = arr[0], y = arr[1];
image[x][y] = color;
for (int i = 0; i < 4; i++) {
int a = x + di[i];
int b = y + dj[i];
if (0 <= a && a < m && 0 <= b && b < n && image[a][b] == prev) {
queue.add(new int[] { a, b });
}
}
}
return image;
}
}
3、岛屿数量
class Solution {
public int numIslands(char[][] grid) {
// 加强版图像渲染
// 引入一个二维数组用于标记是否已经探索过，可以直接修改元素组，一般都还是建立一个标记数组
int m = grid.length;
int n = grid[0].length;
int[] dx = new int[] { 0, 0, 1, -1 };
int[] dy = new int[] { 1, -1, 0, 0 };
boolean[][] flag = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
flag[i][j] = false;
}
}
// 创建队列;
Queue<int[]> queue = new LinkedList<>();
int ret = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1' && flag[i][j] == false) {
queue.add(new int[] { i, j });
flag[i][j] = true;
while (!queue.isEmpty()) {
int[] temp = queue.poll();
int x = temp[0], y = temp[1];
for (int k = 0; k < 4; k++) {
int a = x + dx[k], b = y + dy[k];
if (0 <= a && a < m && 0 <= b && b < n && grid[a][b] == '1' && flag[a][b] == false) {
queue.add(new int[] { a, b });
flag[a][b] = true;
}
}
}
ret++;
}
}
}
return ret;
}
}
4、岛屿的最大面积
class Solution {
public int maxAreaOfIsland(int[][] grid) {
// 加强版图像渲染
// 引入一个二维数组用于标记是否已经探索过，可以直接修改元素组，一般都还是建立一个标记数组
int m = grid.length;
int n = grid[0].length;
int[] dx = new int[] { 0, 0, 1, -1 };
int[] dy = new int[] { 1, -1, 0, 0 };
boolean[][] flag = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
flag[i][j] = false;
}
}
// 创建队列;
Queue<int[]> queue = new LinkedList<>();
int max = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1 && flag[i][j] == false) {
queue.add(new int[] { i, j });
flag[i][j] = true;
int size=0;
while (!queue.isEmpty()) {
int[] temp = queue.poll();
size++;
int x = temp[0], y = temp[1];
for (int k = 0; k < 4; k++) {
int a = x + dx[k], b = y + dy[k];
if (0 <= a && a < m && 0 <= b && b < n && grid[a][b] == 1 && flag[a][b] == false) {
queue.add(new int[] { a, b });
flag[a][b] = true;
}
}
}
max = Math.max(max,size);
}
}
}
return max;
}
}
岛屿数量的基础上添加一个变量
5、被围绕的区域
对于周边的岛屿不做修改，对于中间被完全包围的岛屿进行修改；不直接去寻找中间岛屿，而是寻找周边岛屿并作标记，然后进行修改。
class Solution {
// 定义在里面的需要手动初始化
int[] dx = new int[] { 0, 0, 1, -1 };
int[] dy = new int[] { 1, -1, 0, 0 };
int m, n;
Queue<int[]> q = new LinkedList<>();
public void solve(char[][] board) {
m = board.length;
n = board[0].length;
// 1. 先处理边界的 'O' 联通块，全部修改成 '.'
for (int j = 0; j < n; j++) {
if (board[0][j] == 'O') {
bfs2(board, 0, j);
}
if (board[m - 1][j] == 'O') {
bfs2(board, m - 1, j);
}
}
for (int i = 0; i < m; i++) {
if (board[i][0] == 'O') {
bfs2(board, i, 0);
}
if (board[i][n - 1] == 'O') {
bfs2(board, i, n - 1);
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'O') {
board[i][j] = 'X';
}
if (board[i][j] == '.') {
board[i][j] = 'O';
}
}
}
}
public void bfs1(char[][] board, int i, int j) {
board[i][j] = '.';
q.add(new int[] { i, j });
while (!q.isEmpty()) {
int[] temp = q.poll();
int x = temp[0], y = temp[1];
for (int k = 0; k < 4; k++) {
int a = x + dx[k], b = y + dy[k];
if (0 <= a && a < m && 0 <= b && b < n && board[a][b] == 'O') {
board[a][b] = '.';
q.add(new int[] { a, b });
}
}
}
}
public void bfs2(char[][] board, int i, int j) {
q.add(new int[] { i, j });
while (!q.isEmpty()) {
int[] t = q.poll();
int a = t[0], b = t[1];
board[a][b] = '.';
for (int k = 0; k < 4; k++) {
int x = a + dx[k], y = b + dy[k];
if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O') {
q.add(new int[] { x, y });
}
}
}
}
}
借助队列实现层序遍历，对于遍历过的地方需要进行标记，防止死循环，标记的时机有两个。
- 当遍历到某个位置时就对其进行标记，然后该位置进队列
- 当某位置出队列的时候进行标记
虽然两种方式都能防止死循环，但是方法二会导致某一位置重复进队列，重复的部分就会进行一次向周围扩展，导致运行时间过长。所以bfs算法建议使用第一种方式即使更新已经遍历的位置。
十六、BFS解决最短路问题
0、什么是最短路径问题（单源头）
1、迷宫中离入口最近的出口
class Solution {
public int nearestExit(char[][] maze, int[] entrance) {
//
int m = maze.length;
int n = maze[0].length;
int[] dx = new int[]{0,0,1,-1};
int[] dy = new int[]{1,-1,0,0};
Queue<int[]> queue = new LinkedList<>();
queue.add(entrance);
maze[entrance[0]][entrance[1]] = '0';
int setp = 0;
while(!queue.isEmpty()){
setp++;
int qSize = queue.size();
// 本次蔓延会从qSize个节点继续向外蔓延
for(int k=0;k<qSize;k++){
int[] temp = queue.poll();
int x = temp[0],y=temp[1];
for(int i=0;i<4;i++){
int a = x + dx[i];
int b = y + dy[i];
if(0<=a&&a<m&&0<=b&&b<n&&maze[a][b]=='.'){
maze[a][b] = '0';
queue.add(new int[]{a,b});
if(a==0||b==0||a==m-1||b==n-1){
return setp;
}
}
}
}
// 此轮蔓延结束，之前的结点都已经出队列了，新蔓延的结点全都入队列了
// 然后开启下一轮蔓延，直到遇见最近的出口
}
return -1;
}
// 一步一步向外蔓延，
}
寻找最短路径的算法原理：一步一步向外蔓延，
2、最小基因变化
class Solution {
public int minMutation(String startGene, String endGene, String[] bank) {
int n = bank.length;
boolean[] flag = new boolean[n];
Queue<String> queue = new LinkedList<>();
queue.add(startGene);
int step = 0;
while (!queue.isEmpty()) {
step++;
int qSize = queue.size();
for (int i = 0; i < qSize; i++) {
String temp = queue.poll();
for (int j = 0; j < n; j++) {
// 一定要理解BFS算法为什么可行！！
// 这一定要对在突变过程中出现过的基因做一下标记，否则会死循环
if (!bank[j].equals(startGene) && flag[j] == false && isMutate(bank[j], temp)) {
flag[j] = true;
queue.add(bank[j]);
if (endGene.equals(bank[j])) {
return step;
}
}
}
}
}
return -1;
}
public boolean isMutate(String s1, String s2) {
int num = 0;
for (int i = 0; i < 8; i++) {
if (s1.charAt(i) != s2.charAt(i))
num++;
if (num > 1)
return false;
}
return num == 1;
}
}
class Solution {
public int minMutation(String startGene, String endGene, String[] bank) {
Set<String> vis = new HashSet<>(); // ⽤来标记已经搜索过的状态
Set<String> hash = new HashSet<>(); // ⽤来统计基因库⾥⾯的字符串
for (String s : bank)
hash.add(s);
char[] change = { 'A', 'C', 'G', 'T' };
if (startGene.equals(endGene))
return 0;
if (!hash.contains(endGene))
return -1;
Queue<String> q = new LinkedList<>();
q.add(startGene);
vis.add(startGene);
int step = 0;
while (!q.isEmpty()) {
step++;
int sz = q.size();
while (sz-- != 0) {
String t = q.poll();
for (int i = 0; i < 8; i++) {
char[] tmp = t.toCharArray();
for (int j = 0; j < 4; j++)
{
tmp[i] = change[j];
String next = new String(tmp);
if (hash.contains(next) && !vis.contains(next)) {
if (next.equals(endGene))
return step;
q.add(next);
vis.add(next);
}
}
}
}
}
return -1;
}
}
3、单词接龙
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
int size = wordList.size();
int length = beginWord.length();
boolean[] flag = new boolean[size];
Queue<String> queue = new LinkedList<>();
queue.add(beginWord);
int step=0;
while(!queue.isEmpty()){
step++;
int qSize = queue.size();
for(int i=0;i<qSize;i++){
String temp = queue.poll();
for(int j=0;j<size;j++){
if(!wordList.get(j).equals(beginWord)&&flag[j]==false&&isMutate(temp,wordList.get(j))){
flag[j]=true;
queue.add(wordList.get(j));
if(wordList.get(j).equals(endWord)){
return step+1;
}
}
}
}
}
return 0;
}
public boolean isMutate(String s1, String s2) {
int num = 0;
for (int i = 0; i < s1.length(); i++) {
if (s1.charAt(i) != s2.charAt(i))
num++;
if (num > 1)
return false;
}
return num == 1;
}
}
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> hash = new HashSet<>();
for (String s : wordList)
hash.add(s);
Set<String> vis = new HashSet<>(); // 标记已经搜索过的单词
if (!hash.contains(endWord))
return 0;
Queue<String> q = new LinkedList<>();
q.add(beginWord);
vis.add(beginWord);
int ret = 1;
while (!q.isEmpty()) {
ret++;
int sz = q.size();
while (sz-- != 0) {
String t = q.poll();
for (int i = 0; i < t.length(); i++) {
char[] tmp = t.toCharArray();
for (char ch = 'a'; ch <= 'z'; ch++) {
tmp[i] = ch;
String next = new String(tmp);
if (hash.contains(next) && !vis.contains(next)) {
if (next.equals(endWord))
return ret;
q.add(next);
vis.add(next);
}
}
}
}
}
return 0;
}
}
字符串进队列的思路一样，实现方法不一样：
字符串的规模：即单个字符串的长度L
字典规模：字典中字符串的个数N
- 遍历字典，查询所有符合条件的字符串,时间复杂度为O(N*L)
- 列举所有字符串可能，然后再字典中查找是否存在 ,时间复杂度为 O(26LlogN)
相比而言，当字典比较大时，第二种方法优秀。
4、为高尔夫比赛砍树
class Solution {
int m;
int n;
int[] dx = new int[] { 0, 0, 1, -1 };
int[] dy = new int[] { 1, -1, 0, 0 };
public int cutOffTree(List<List<Integer>> forest) {
// 1、将要砍的树从小到大排序
m = forest.size();
n = forest.get(0).size();
List<int[]> trees = new ArrayList<>();
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (forest.get(i).get(j) > 1)
trees.add(new int[] { i, j });
Collections.sort(trees, (a, b) -> {
return forest.get(a[0]).get(a[1]) - forest.get(b[0]).get(b[1]);
});
// 2、计算每树的最短间距（BFS）
int sumStep = 0;
int length = trees.size();
if(length==0) return 0;
sumStep+=bfs(forest,new int[]{0,0},trees.get(0));
if(sumStep == -1) return -1;
for (int i = 0; i < length - 1; i++) {
int step = bfs(forest, trees.get(i), trees.get(i + 1));
if(step == -1) return -1;
sumStep+=step;
}
return sumStep;
}
// 两个坐标的最短距离
public int bfs(List<List<Integer>> forest, int[] tree1, int[] tree2) {
if(tree1[0]==tree2[0]&&tree1[1]==tree2[1]) return 0;
boolean[][] flag = new boolean[m][n];
Queue<int[]> queue = new LinkedList<>();
// 起点入队列
queue.add(tree1);
// 标记入队列的点
flag[tree1[0]][tree1[1]] = true;
int step = 0;
while (!queue.isEmpty()) {
step++;
int qSize = queue.size();
// 从已经探索的点向外蔓延
for (int k = 0; k < qSize; k++) {
int[] temp = queue.poll();
int x = temp[0], y = temp[1];
for (int i = 0; i < 4; i++) {
int a = x + dx[i], b = y + dy[i];
if (0 <= a && a < m && 0 <= b && b < n && forest.get(a).get(b) != 0 && flag[a][b] == false) {
queue.add(new int[] { a, b });
flag[a][b] = true;
if (a == tree2[0] && b == tree2[1]) {
return step;
}
}
}
}
}
return -1;
}
}
class Solution {
int m, n;
public int cutOffTree(List<List<Integer>> f) {
m = f.size();
n = f.get(0).size();
List<int[]> trees = new ArrayList<>();
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (f.get(i).get(j) > 1)
trees.add(new int[] { i, j });
Collections.sort(trees, (a, b) -> {
return f.get(a[0]).get(a[1]) - f.get(b[0]).get(b[1]);
});
int bx = 0, by = 0;
int ret = 0;
for (int[] next : trees) {
int a = next[0], b = next[1];
int step = bfs(f, bx, by, a, b);
if (step == -1)
return -1;
ret += step;
bx = a;
by = b;
}
return ret;
}
int[] dx = { 0, 0, 1, -1 };
int[] dy = { 1, -1, 0, 0 };
public int bfs(List<List<Integer>> f, int bx, int by, int ex, int ey) {
if (bx == ex && by == ey)
return 0;
Queue<int[]> q = new LinkedList<>();
boolean[][] vis = new boolean[m][n];
q.add(new int[] { bx, by });
vis[bx][by] = true;
int step = 0;
while (!q.isEmpty()) {
int sz = q.size();
step++;
while (sz-- != 0) {
int[] t = q.poll();
int a = t[0], b = t[1];
for (int i = 0; i < 4; i++) {
int x = a + dx[i], y = b + dy[i];
if (x >= 0 && x < m && y >= 0 && y < n && f.get(x).get(y) != 0 && vis[x][y] == false) {
if (x == ex && y == ey)
return step;
q.add(new int[] { x, y });
vis[x][y] = true;
}
}
}
}
return -1;
}
}
十七、多源BFS 多源最短路问题
0、什么是多源最短路径问题
本质和单源最短路是一致的，单源最短路包含多源头最短路
如图：（去板书截个图）
1、01矩阵
// 正难则反
class Solution {
int m;
int n;
int[] dx = new int[] { 0, 0, -1, 1 };
int[] dy = new int[] { 1, -1, 0, 0 };
public int[][] updateMatrix(int[][] mat) {
m = mat.length;
n = mat[0].length;
int[][] ret = new int[m][n];
Queue<int[]> queue = new LinkedList<>();
// 1、多源入队
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (mat[i][j] == 0) {
queue.add(new int[] { i, j });
ret[i][j] = 0;
} else {
ret[i][j] = -1;
}
}
}
// 2、BFS遍历
while (!queue.isEmpty()) {
int[] arr = queue.poll();
int x = arr[0], y = arr[1];
for (int k = 0; k < 4; k++) {
int a = x + dx[k], b = y + dy[k];
if (0 <= a && a < m && 0 <= b && b < n && ret[a][b] == -1) {
queue.add(new int[] { a, b });
ret[a][b] = ret[x][y] + 1;
}
}
}
return ret;
}
}
// 我好NB
int[][] ret = new int[m][n];
之前求最短路径时会用到这几个变量：
- boolean[][] flag; 用于标记已经遍历的位置
- int step; 记录蔓延的次数
- int qSize; 循环扩展每个末端位置
从(x,y)蔓延到(a,b)时，ret[a][b]=ret[x][y]+1;计算起点到某一位置的最短距离，可以使用该位置的上一个位置的最短距离加一计算。对ret数组进行初始化，起点到起点的最短距离为零，其他位置为-1代表未遍历的位置。一个二位数组起到了三个变量的作用，该题要求返回每一个位置的最短距离，正好符合。
正难则反：
从1的位置向0蔓延，记录每个位置的最短距离不太好写，有些1是被包围起来的，当从1蔓延到0的时候，起点可能早就已经出队列了，很难将step赋值给别包围的1。也就是正这蔓延的时候最短路径是在缩短的，因为不知道起点的最短距离，所以不能用减减的形式去求每一个位置的最短距离。如果反着蔓延，终点到终点的最短距离为0，一次向起点蔓延。可以使用加加的方式来计算下一个位置的最短距离。
2、飞地的数量
class Solution {
public int numEnclaves(int[][] grid) {
// 正难则反
// 以所以边界的1为起点，进行蔓延，找到所有临边的岛屿
// 剩下的中间岛屿就是飞地
int[] dx = new int[]{0,0,-1,1};
int[] dy = new int[]{-1,1,0,0};
int m = grid.length,n = grid[0].length;
boolean[][] flag = new boolean[m][n];
Queue<int[]> queue = new LinkedList<>();
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if((i==0||j==0||i==m-1||j==n-1)&&grid[i][j]==1){
queue.add(new int[]{i,j});
flag[i][j] = true;
}
}
}
while(!queue.isEmpty()){
int[] arr = queue.poll();
int x = arr[0],y = arr[1];
for(int i=0;i<4;i++){
int a = x + dx[i],b = y + dy[i];
if(0 <= a && a < m && 0 <= b && b < n && grid[a][b]==1 && flag[a][b]==false){
queue.add(new int[]{a,b});
flag[a][b] = true;
}
}
}
int sum=0;
for(int i=0;i<m;i++){
for(int j =0;j<n;j++){
if(grid[i][j]==1 && flag[i][j]==false) sum++;
}
}
return sum;
}
}
3、地图中的最高点
class Solution {
public int[][] highestPeak(int[][] isWater) {
// 这个某个题目不要太相似
int[] dx = new int[] { 0, 0, -1, 1 };
int[] dy = new int[] { -1, 1, 0, 0 };
int m = isWater.length, n = isWater[0].length;
int[][] ret = new int[m][n];
Queue<int[]> queue = new LinkedList<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if(isWater[i][j]==1){
queue.add(new int[]{i,j});
ret[i][j]=0;
}else{
ret[i][j]=-1;
}
}
}
while (!queue.isEmpty()) {
int[] arr = queue.poll();
int x = arr[0], y = arr[1];
for (int k = 0; k < 4; k++) {
int a = x + dx[k], b = y + dy[k];
if (0 <= a && a < m && 0 <= b && b < n && ret[a][b] == -1) {
queue.add(new int[] { a, b });
ret[a][b] = ret[x][y] + 1;
}
}
}
return ret;
}
}
从值为0的位置开始蔓延，每次蔓延高度都加1，最后的结果就是 “使得矩阵中的最高高度值 **最大 **的矩阵”
为什么每次蔓延都加1？也就是这样作为什么可行。原理是贪心算法，每一步都取最优解，每一步都完成以后的解就是整体的最优解。
3.1、最高位置
寻找最高处，写完层序遍历的方法才看出来可以直接双重循环，效率可能更高
如何高效率的查找二维数组中的最大值？
class Solution {
public int[][] highestPeak(int[][] isWater) {
// 从某一个位置层序遍历是不一定能到达最高点的
// 假设从一个位置开始层序遍历到的最高点为x，则该路径上任意一个点能够遍历到的最高点就是x,这样就能省去很多遍历，并让一些遍历提前终止
int[] dx = new int[] { 0, 0, -1, 1 };
int[] dy = new int[] { -1, 1, 0, 0 };
int m = isWater.length, n = isWater[0].length;
boolean[][] flag = new boolean[m][n];
Queue<int[]> queue = new LinkedList<>();
int max = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (flag[i][j] == false) {
queue.add(new int[] { i, j });
flag[i][j] = true;
while (!queue.isEmpty()) {
int[] arr = queue.poll();
int x = arr[0], y = arr[1];
max = Math.max(max, isWater[x][y]);
for (int k = 0; k < 4; k++) {
int a = x + dx[i], b = y + dy[i];
if (0 <= a && a < m && 0 <= b && b < n && isWater[a][b] >= isWater[x][y]
&& flag[a][b] == false) {
queue.add(new int[] { a, b });
flag[a][b] = true;
}
}
}
}
}
}
return max;
}
}
4、地图分析
class Solution {
public int maxDistance(int[][] grid) {
// 还是多源最远路径
// 每一次蔓延都会有新的位置加入队列，如果某一次蔓延没有新的位置入队列，则说明
int[] dx = new int[] { 0, 0, -1, 1 };
int[] dy = new int[] { -1, 1, 0, 0 };
int m = grid.length, n = grid[0].length;
boolean[][] flag = new boolean[m][n];
Queue<int[]> queue = new LinkedList<>();
int finded = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
queue.add(new int[] { i, j });
flag[i][j] = true;
finded++;
}
}
}
if (finded == m * n) return -1;
int step = 0;
while (!queue.isEmpty()) {
step++;
int qSize = queue.size();
int prev = finded;
for (int sz = 0; sz < qSize; sz++) {
int[] arr = queue.poll();
int x = arr[0], y = arr[1];
for (int i = 0; i < 4; i++) {
int a = x + dx[i], b = y + dy[i];
if (0 <= a && a < m && 0 <= b && b < n && flag[a][b] == false) {
queue.add(new int[] { a, b });
flag[a][b] = true;
finded++;
}
}
}
if(prev == finded){
return step-1;
}
}
return -1;
}
}
十八、BFS解决拓扑排序
0、什么是拓扑排序？
a、有向无环图
b、AOV网
在有向无环图中，用顶点来表示活动，用边来表示活动先后顺序的图结构
c、拓扑排序
对上图进行拓扑排序: 1->3->2 此时因为图中有环，拓扑排序排序中止；
d、实现拓扑排序（如何编程实现拓扑排序）
建图在离散数学中学了：
- 用二维数组（也就是邻接矩阵）建图。
- 邻接表 List<List>；Map<Integer,List>；
哈希表中Key为某个节点，Value为该节点指向的结点。
1、课程表
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
// 0、准备工作
Map<Integer, List<Integer>> hash = new HashMap<>();
int[] in = new int[numCourses];
// 1、建图
for (int i = 0; i < prerequisites.length; i++) {
int key = prerequisites[i][1];
int value = prerequisites[i][0];
if (!hash.containsKey(key)) {
hash.put(key, new ArrayList<>());
}
hash.get(key).add(value);
// 因为图中key->value，所以代码是in[value]++;
in[value]++;
}
// 2、拓扑排序
Queue<Integer> queue = new LinkedList<>();
// 2.1、入度为0的点进队列
for(int i=0;i<numCourses;i++){
if(in[i]==0){
queue.add(i);
}
}
// 一次层序遍历：若a->b，则a出队列，b的入度减1。若b的入度为0则可以进队列
// 直到队列为空，说明图中没有入度为零点（拓扑排序成功或者图中有环）
while(!queue.isEmpty()){
int key = queue.poll();
List<Integer> value = hash.getOrDefault(key,new ArrayList<>());
for(int x : value){
in[x]--;
if(in[x]==0) queue.add(x);
}
}
// 遍历每一个点的入度，若存在入度不为的点则说明有环存在
for(int i=0;i<numCourses;i++){
if(in[i]>0) return false;
}
return true;
}
}
class Solution {
public boolean canFinish(int n, int[][] p) {
// 1. 准备⼯作
int[] in = new int[n]; // 统计每⼀个顶点的⼊度
Map<Integer, List<Integer>> edges = new HashMap<>(); // 邻接表存图
// 2. 建图
for (int i = 0; i < p.length; i++) {
int a = p[i][0], b = p[i][1]; // b -> a
if (!edges.containsKey(b)) {
edges.put(b, new ArrayList<>());
}
edges.get(b).add(a);
in[a]++;
}
// 3. 拓扑排序
Queue<Integer> q = new LinkedList<>();
// (1) 先把⼊度为 0 的点，加⼊到队列中
for (int i = 0; i < n; i++) {
if (in[i] == 0)
q.add(i);
}
// (2) bfs
while (!q.isEmpty()) {
int t = q.poll();
for (int a : edges.getOrDefault(t, new ArrayList<>())) {
in[a]--;
if (in[a] == 0)
q.add(a);
}
}
// 4. 判断是否有环
for (int x : in)
if (x != 0)
return false;
return true;
}
}
2、课程表II
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
// 1、准备工作
int[] in = new int[numCourses];
int[] ret = new int[numCourses];
int index=0;
Map<Integer,List<Integer>> hash = new HashMap<>();
// 2、建图
for(int i=0;i<prerequisites.length;i++){
int key = prerequisites[i][1];
int value = prerequisites[i][0];
if(!hash.containsKey(key)){
hash.put(key,new ArrayList<>());
}
hash.get(key).add(value);
in[value]++;
}
// 3、拓扑排序
// 3.1、入度为零的结点进队列
Queue<Integer> queue = new LinkedList<>();
for(int i = 0;i < numCourses;i++){
if(in[i]==0){
queue.offer(i);
ret[index++] = i;
}
}
// 3.2、层序遍历
while(!queue.isEmpty()){
int key = queue.poll();
List<Integer> value = hash.getOrDefault(key,new ArrayList<>());
for(int x:value){
in[x]--;
if(in[x]==0){
queue.offer(x);
ret[index++] = x;
}
}
}
if(index<numCourses) return new int[0];
else return ret;
}
}
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
// 1、准备工作
int[] in = new int[numCourses];
int[] ret = new int[numCourses];
int index=0;
// 1.1、因为知道有多少门课程，那就一股脑把链表全部建好，用得到的时候在区间写代码比较麻烦，时间复杂度也高
List<List<Integer>> lists = new ArrayList<>();
for(int i=0;i<numCourses;i++){
lists.add(new ArrayList<>());
}
// 2、建图
for(int i=0;i<prerequisites.length;i++){
int key = prerequisites[i][1];
int value = prerequisites[i][0];
lists.get(key).add(value);
in[value]++;
}
// 3、拓扑排序
// 3.1、入度为零的结点进队列
Queue<Integer> queue = new LinkedList<>();
for(int i = 0;i < numCourses;i++){
if(in[i]==0){
queue.offer(i);
ret[index++] = i;
}
}
// 3.2、层序遍历
while(!queue.isEmpty()){
int key = queue.poll();
List<Integer> value = lists.get(key);
for(int x:value){
in[x]--;
if(in[x]==0){
queue.offer(x);
ret[index++] = x;
}
}
}
if(index<numCourses) return new int[0];
else return ret;
}
}
3、火星词典
class Solution {
public String alienOrder(String[] words) {
// 0、先建图表
// words = ["wrt","wrf","er","ett","rftt"]
// 对于某一字符串"wrt"而言,"wrt"中的字母已按照新的字典序排序
// 对于字符串数组words而言，words中的字符串已按照新的字典排序
// 艹、这个建图有点小难啊
String LETTER = "abcdefghijklmnopqrstuvwxyz";
char[] letters = LETTER.toCharArray();// letters[letter - 'a'];
Map<Character, Set<Character>> hash = new HashMap<>();
Map<Character, Set<Character>> in = new HashMap<>();
for (int i = 0; i < words.length; i++) {
for (int j = i + 1; j < words.length; j++) {
String cur = words[i];
String next = words[j];
int c = 0, n = 0;
boolean flag = false;
while (c < cur.length() && n < next.length()) {
char cc = cur.charAt(c++);
char nc = next.charAt(n++);
if (cc != nc) {
flag = true;
if (!hash.containsKey(cc)) {
hash.put(cc, new HashSet<>());
}
hash.get(cc).add(nc);
if (!in.containsKey(nc)) {
in.put(nc, new HashSet<>());
}
in.get(nc).add(cc);
break;
}
}
if(!flag && cur.length()>next.length()) return "";
}
}
// 1、拓扑排序
StringBuffer ret = new StringBuffer();
Queue<Character> queue = new LinkedList<>();
for (Character key : hash.keySet()) {
if(!in.containsKey(key)){
queue.add(key);
}
}
while (!queue.isEmpty()) {
char key = queue.poll();
ret.append(key);
if(hash.containsKey(key)){
for(Character value : hash.get(key)){
in.get(value).remove(key);
if(in.get(value).size()==0){
queue.add(value);
}
}
}
}
for (Character key : in.keySet()) {
Set<Character> values = in.get(key);
if(values.size()!=0) return "";
}
for(int i=0;i<words.length;i++){
String str = words[i];
for(int j=0;j<str.length();j++){
char ch = str.charAt(j);
if(!ret.toString().contains(String.valueOf(ch))){
ret.append(ch);
}
}
}
return ret.toString();
}
}
class Solution {
Map<Character, Set<Character>> edges = new HashMap<>(); // 邻接表【这一步我与老师写的一样】
//【我用了邻接表Map<Character, Set<Character>>去存储某个节点的所有前驱结点】
Map<Character, Integer> in = new HashMap<>(); // 统计每个节点的⼊度
boolean check;
public String alienOrder(String[] words) {
// 1. 初始化⼊度哈希表 + 建图
//【初始化所有结点的入度为0】
for (String s : words) {
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
in.put(ch, 0);
}
}
int n = words.length;
//【建图，并计算入度】
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
add(words[i], words[j]);
if (check == true)
return "";
}
}
// 2. 拓扑排序
Queue<Character> q = new LinkedList<>();
//【入度为0的结点入队列】
for (char ch : in.keySet()) {
if (in.get(ch) == 0)
q.add(ch);
}
StringBuffer ret = new StringBuffer();
while (!q.isEmpty()) {
char t = q.poll();
//【结点出队列，说明这个结点已被排序，此时更新返回值】
ret.append(t);
//【edges中不包含t, 说明t结点不☞向任何结点】
if (!edges.containsKey(t))
continue;
//【遍历t结点指向的结点，将这些结点入度减1】
//【减去后该节点的入度等于0说明该节点的前驱结点都以排序，该节点可以入队列】
for (char ch : edges.get(t)) {
in.put(ch, in.get(ch) - 1);
if (in.get(ch) == 0)
q.add(ch);
}
}
// 3. 判断
// 【判断是否存环】
for (char ch : in.keySet()) {
if (in.get(ch) != 0)
return "";
}
return ret.toString();
}
public void add(String s1, String s2) {
int n = Math.min(s1.length(), s2.length());
int i = 0;
for (; i < n; i++) {
char c1 = s1.charAt(i), c2 = s2.charAt(i);
if (c1 != c2) {
// c1 -> c2
if (!edges.containsKey(c1)) {
edges.put(c1, new HashSet<>());
}
//【在加入之前是否已经加入过了，如果已经添加了就不更新入度，否则入度加1】
//【我是的代码属于前期偷懒，后期补坑了】
if (!edges.get(c1).contains(c2)) {
edges.get(c1).add(c2);
in.put(c2, in.get(c2) + 1);
}
break;
}
}
//【当出现"abc","ab"的情况时直接返回 "" 。】
if (i == s2.length() && i < s1.length())
check = true;
}
}
以空间换时间，因为空间不值钱；但是我的代码及消耗了空间，又消耗了时间。
吴老师使用了Map<Character, Integer> in；存储每个结点的入度；（存储的时候短杆多干一点，存取数据的时候就方便一点，这也不是绝对的，看情况）；
我使用的是Map<Character, Set> in；存储每个结点的前驱结点，进而计算入度；（存储的时候偷懒，取数据的时候就要付出代价）