如何手机做网站,云存储,知名it外包公司,济南关键词优化平台一、双指针算法(快慢指针,对撞指针) 艹#xff0c;CSDN吞了我是十三题笔记#xff01;#xff01;#xff01; 二、滑动窗口(滑动窗口) 1、找到字符串中所有字母异位词 class Solution {public ListInteger findAnagrams(String s, String p) {int[] hash1 new in…
一、双指针算法(快慢指针,对撞指针) 艹CSDN吞了我是十三题笔记 二、滑动窗口(滑动窗口) 1、找到字符串中所有字母异位词 class Solution {public ListInteger findAnagrams(String s, String p) {int[] hash1 new int[26];int[] hash2 new int[26];int sl s.length();int pl p.length();ListInteger 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 ListInteger findAnagrams(String ss, String pp) {ListInteger ret new ArrayListInteger();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];// 进窗⼝ 维护 countif (hash2[in - a] hash1[in - a])count;if (right - left 1 m) // 判断{char out s[left];// 出窗⼝ 维护 countif (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 ListInteger findSubstring(String s, String[] words) {ListInteger ret new ArrayList();MapString, 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) {MapString, 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 ListInteger findSubstring(String s, String[] words) {ListInteger ret new ArrayListInteger();// 保存字典中所有单词的频次MapString, Integer hash1 new HashMapString, 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) // 执⾏次数{// 保存窗⼝内所有单词的频次MapString, Integer hash2 new HashMapString, Integer();for (int left i, right i, count 0; right len s.length(); right len) {// 进窗⼝ 维护 countString 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) {// 出窗⼝ 维护 countString 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 sl1;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 (minlensl1)return ;return ss.substring(begin,beginminlen);// 注意不要在循环里面使用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; // 进窗⼝ 维护 countwhile (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();elsereturn 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 3int left 0, right nums.length - 1; int[] ret new int[2];ret[0]-1;ret[1]-1;if(nums.length0) return ret;// 左端点while (left right) {// mid中间偏左int mid left (right - left) / 2; if (nums[mid] target) {left mid1;}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 - left1) / 2; if (nums[mid] target) {right mid-1;}else{left mid; }}ret[1]left;return ret;}
}二分查找最左边或最右边的目标值,朴素的二分查找传到目标值以后就可以返回退出循环了,所以结束条件是while(leftright),但是对于查找位于最左变或最右边的目标则不一样,当nums[mid]target时循环并不能结束,以查找最左边目标值为例: 重点: while (left right) {// mid中间偏左int mid left (right - left) / 2; if (nums[mid] target) {left mid1;}else{//因为nums[mid]target,而nums[mid-1]有可能小于target//就不会是最左边目标值了所以移动右指针为right mid; right mid; }
}while (left right) {// mid中间偏右int mid left (right - left1) / 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(targetnums[right]) return n;//吴老师的二分法是分为两个分支,将后两个合并,while循环不会提前结束,//虽然比我写的行数少且简洁,但提前结束循环理论上来说时间耗时更小一些,//但是圈复杂度比较高//补充我这样写之所以能对是因为数组是严格递增的//若不是严格递增的会因为没有找到最右侧目标值而测试失败//吴老师给的模板才是通用的对于非递减数组//或数组中无目标值(此时双指针会停在最近目标值的左侧或者右侧)都可以适用//吴老师yydswhile(leftright){mid left (right - left)/2;if(nums[mid]target){leftmid1;}else if(targetnums[mid]){rightmid;}else{break;}}if(leftright) 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;elseright mid - 1;}return (int) left;}
}怎么说呢,这是一个典型的最在右侧目标值的问题,吴老师的模板yyds,好好理解一下。 5、山脉数组的峰顶索引 class Solution {public int peakIndexInMountainArray(int[] arr) {int n arr.length;int left0;int right n-1;while(leftright){int mid left(right-left1)/2;if(arr[mid]arr[mid-1]){leftmid;}else {rightmid-1;}}return left;}
}
//用吴老师的模板写简简单单6、寻找峰值★★★ class Solution {public int findPeakElement(int[] nums) {int n nums.length;int left 0;int right n - 1;while(leftright){int mid left (right - left)/2;if(nums[mid]nums[mid1]){rightmid;}else {leftmid1;}}return left;}
}二分算法适用于具有二段性的场景本题的难点就在于分析出二段在哪里 对于数组某一位置i,如果nums[i]nums[i1]则[left,i]区间一定存在高峰反之[i1,right]区间一定存在高峰。 6、寻找旋转排序数组中的最小值★★★ 如图所示以D点为参照物数组具有二段性。 如果nums[mid]nums[right]则最低点一定在[mid1,right]区间 如果nums[mid]nums[right]则最低点一定在[left,mid]区间 根据题意不存在nums[mid]nums[right] class Solution {public int findMin(int[] nums) {int nnums.length;int left0;int rightn-1;while(leftright){//如果mid偏右就会导致当左右指针相邻是陷入死循环//所以mid要写成偏左的形式int mid left(right-left)/2;if(nums[mid]nums[right]){leftmid1;}else{rightmid;}}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(leftright){int mid left (right-left)/2;if(midrecords[mid]){leftmid1;}else{rightmid;}}return right;}
}
//数组具有二段性如果records[mid]mid,说明mid之前的名单都是正常的缺失的数位于mid之后0^1^1^2^2^3^4^4^5^53012345*(40)/2利用一个长度为n1的哈希表将名单放入哈希表为零的位置就是缺失的名单四、前缀和 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[a1];for(int i0;ia;i){arr[i]in.nextInt();//★★sum[i1]sum[i]arr[i];}while(b0){int iin.nextInt();int jin.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[n1][m1];for(int i0;in;i){for(int j0;jm;j){arr[i][j] in.nextInt();// 构造二位前缀和数组dp[i1][j1] dp[i][j1]dp[i1][j]arr[i][j]-dp[i][j];}}for(int i0;iq;i){int x1in.nextInt();int y1in.nextInt();int x2in.nextInt();int y2in.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[n1];// 构造前缀和数组for(int i1;in;i){dp[i]dp[i-1]nums[i-1];}// 构造后缀和数组可有可无频繁用到后缀和的话也可以提前构造出来// 数组不具有二段性中心下标随机分布所以老老实实遍历好了for(int i0;in;i){if(dp[i]dp[n]-dp[i1]){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 i1;in;i){f[i]f[i-1]*nums[i];}for(int in-2;i0;i--){g[i]g[i1]*nums[i];}int[] ret new int[n];ret[0]g[1];ret[n-1]f[n-2];for(int i1;in-1;i){ret[i]f[i-1]*g[i1];}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[n1];for(int i1;in;i){lpron[i]lpron[i-1]nums[i-1];}int ret0;for(int i0;in;i){for(int ji1;jn;j){if(lpron[j]-lpron[i]k){ret;}}}return ret;}
} 优化思路使用哈希表积累每个前缀和的个数 对于区间以i结尾的子数组若j(0ji)的前缀和sum[j]等于sum[i]-k则子数组[j1i]元素之和等于k。在遍历数组的时候求出每一个位置的前缀和并使用Map记录每个前缀和出现的次数即可。 // 求class Solution {public int subarraySum(int[] nums, int k) {MapInteger, Integer hash new HashMapInteger, 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)%90则a%9b%9 // 若存在ji、nums[i]%kb、num[j]%kb,则子数组[j,i]元素和为k的倍数int n nums.length;MapInteger, Integer hash new HashMap();hash.put(0,1);int sum0;int ret0;for(int x:nums){sumx;int in ((sum%k)k)%k;rethash.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-left1 子数组元素和*2int n nums.length;MapInteger,Integer hash new HashMap(); // 下标0,1数量差hash.put(0,-1);int sum0; int max0;for(int i0;in;i){sumnums[i];int cha i1-2*sum;if(hash.containsKey(cha)){maxMath.max(max,i-hash.get(cha));}else{hash.put(cha,i);}} return max;}
}class Solution {public int findMaxLength(int[] nums) {MapInteger, Integer hash new HashMapInteger, 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));elsehash.put(sum, i);}return ret;}
}
// 把0当成-1问题就变成了求元素和为0的最大子数组长度
// 和之前求元素和为0的子数组的个数不同的是MapInteger,Integer里面存的是前缀和最小下标
// 之前存的是前缀和满足条件的子数组的个数
// 我的代码和吴老师的思路本质上是一样的8、矩阵区域和 class Solution {public int[][] matrixBlockSum(int[][] mat, int k) {int m mat.length;int n mat[0].length;int[][] dp new int[m1][n1];for(int i1;im;i){for(int j1;jn;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 i1;im;i){for(int j1;jn;j){int x1 i-k1?i-k:1;int y1 j-k1?j-k:1;int x2 ikm?ik:m; // 边界值处理,一开始没写对debug之后发现的int y2 jkn?jk: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 (nx)1 这个结果就是n的第x位是0还是1并且不会改变n的大小。 c将一个数n的二进制表示第x位修改为1 n:0110101000 0000001000 将这两个数或一下就可以得到修改后的值所以我们需要构造出一个第x为1其他位为0的数字也就是1x那么最终的公式是 nn|(1x) 或者写成这样也可以 n|(1x) d将一个数n的二进制表示第x位修改为0 n:0110101000 1111110111 将这两个数一下就可以了所以我们需要构造出来一个第x位为0其他位为1的二进制数也就是~(1x) 那么最终运算的公式是 n(~(1x)) 或者写成这样也可以 nn(~(1x)) 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得到 -n1001011000 n 0110101000 -n 1001011000 n(-n) 0000001000 这个就是最终的提取结果 g 将一个二进制数n最右侧的1改为0 这个算法按理讲应该可以想出来我要改变最低为的1就代表比这一位高的都不能变比这一位低的都是0那么n-1就会是一个高位和n一致第位从1全变成1,要改变的这一位从1变成了0那么n(-n)就是最终结果 n0110101000 n-10110100111 n(n-1)0101010000 ok,这就成功把最右侧1改为了0 h运算符的优先级
自己写的时候能加括号就加括号在编程中,运算符的优先级决定了表达式中运算的执行顺序。下面是一些常见运算符的优先级:
括号 (): 最高优先级表达式会首先被求值。一元运算符: 如!、-、、--等。算术运算符: *、/、%、、-。乘、除、取模的优先级高于加、减。位运算符: ~、、|、^、、。关系运算符: 、、、、、!。逻辑运算符: 、||。赋值运算符: 、、-、*、/、%等。
当表达式中含有多个运算符时,优先级高的运算符会先被求值。如果优先级相同,则从左到右依次求值。我们可以使用括号来改变表达式的求值顺序。括号内的表达式会首先被求值。例如:
5 3 * 2 // 结果是 11, 因为 * 的优先级高于
(5 3) * 2 // 结果是 16, 因为括号内的表达式先被求值位运算符是一类特殊的运算符,它们直接对数字的二进制位进行操作。位运算符的优先级如下:
位非 (~): 最高优先级,对一个数的二进制位进行取反操作。位与 (): 对两个数的对应位进行与操作。位或 (|): 对两个数的对应位进行或操作。位异或 (^): 对两个数的对应位进行异或操作。左移 (): 将一个数的二进制位向左移动指定的位数。右移 (): 将一个数的二进制位向右移动指定的位数。
位运算符的优先级高于算术运算符,但低于一元运算符。例如:
a 5 3 // 结果为 1因为 5 的二进制是 1013 的二进制是 011按位与得到 001即 1
b 5 | 3 // 结果为 7因为 5 的二进制是 1013 的二进制是 011按位或得到 111即 7
c 5 ^ 3 // 结果为 6因为 5 的二进制是 1013 的二进制是 011按位异或得到 110即 6
d 5 1 // 结果为 10因为 5 的二进制是 101左移 1 位得到 1010即 10
e 5 1 // 结果为 2因为 5 的二进制是 101右移 1 位得到 10即 2理解位运算符的优先级和使用方法对于一些底层编程和优化很有帮助。
i异或^运算的规律 1a^0a 2a^a0 3abca(bc) 异或运算满足交换律一大堆数异或在一起计算结果和异或顺序无关。 前两个还是比较好理解的最后一个特性也是与生俱来的因为异或没有进位相加 PS7,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、使用 (bitMapx)1 的值判断是字母否出现过
// 3、使用 bitMap | (1 x); 标记该字母出现过2、丢失的数字 class Solution {public int missingNumber(int[] nums) {int retnums.length;for(int i0;inums.length;i){ret^i^nums[i];}return ret;}
}
// 借助异或运算的规律该寻找丢失的数字
// a^a^b^b^cc
// a^a0
// a^0a3、两整数之和★★★★ class Solution {public int getSum(int a, int b) {int carry 0;do{carry(ab)1;aa^b;bcarry;}while(carry!0);return a;}// 错误写法// public int getSum(int a, int b) {// int carry 0;// do{// carry(ab)1;// aa^b;// bcarry;// }while(carry0); // 进位有可能是负数// return a;// }
}
// 算法原理ab (a^b) (ab)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位比特位(0i32)的值求和取余的结果恰好等于那个只出现了一次的数字的第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位比特位置位1ret | (1 i);} else { // // 将第i位比特位置位0初始化的时候本来就是0所也可以不做处理ret (~(1 i));}}return ret;}
}5、消失的两个数字
算法原理
class Solution {public int[] missingTwo(int[] nums) {// 1、将nums中的数字以及1~N异或// 得到tempa^b,也就是缺失的两个数的异或// 因为a!b,所以temp!0int 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确定这个比特位的位置indextemp 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;elseret[1] ^ x;}for (int i 1; i N; i) {if (((i index) 1) 1)ret[0] ^ i;elseret[1] ^ i;}return ret;}
}六、模拟——比葫芦画瓢 1、替换所有问号★★★ class Solution {public String modifyString(String s) {char[] chars s.toCharArray();int n chars.length;if(n1){if(chars[0]?){return a;}else{return s;}}if(chars[0]?){if(chars[1]?){chars[0]a;}else if(n1){chars[0](char)((chars[1]-a1)%26a);}}for(int i1;in-1;i){if(chars[i]?){chars[i]getChar(chars[i-1],chars[i1]); }}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 i0;i26;i){ret (char)(ai);if(ret!c1ret!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 time0;int t0;int sum0;int left-1;int right-1;while(timetimeSeries[n-1]){if(timetimeSeries[t]){// 攻击刷新毒区left timeSeries[t];right timeSeries[t]duration-1;// t移动到下一次大于本次的攻击时间 t;while(tntimeSeries[t]timeSeries[t-1]){t;}}if(lefttime timeright){sum;}time;}return sumduration;}
}vclass Solution {public int findPoisonedDuration(int[] timeSeries, int duration) {if (duration 0)return 0;int n timeSeries.length;int sum0;for (int t 0; t n-1; t) {if(timeSeries[t]duration-1timeSeries[t1]){sumduration;}else{sumtimeSeries[t1]-timeSeries[t];}}return sumduration;}
}3、Z字形变换 class Solution {public String convert(String ss, int numRows) {if(numRows1) return ss;char[] s ss.toCharArray();int length s.length;int m numRows;int n length;char[][] arr new char[m][n];for(int i0;im;i){for(int j0;jn;j){arr[i][j] ;}}int index0;int i0;int j0;while(indexlength){// 竖着的int a0;while( anumRows indexlength){arr[i][j]s[index];}i--;// 斜着的a0;while(anumRows-2indexlength){arr[--i][j]s[index];}i--;j;}index0;for(i0;im;i){for(j0;jn;j){if(arr[i][j]! indexlength){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 i1;in;i){sRLE(s);}return s;}public static String RLE(String ss){if(ssnull || ss.length()0) return ss;StringBuilder ret new StringBuilder();char[] s ss.toCharArray();int n s.length;int num0;int i0;while(in){while(i1ns[i]s[i1]){num;i;}ret.append(num1);ret.append(s[i]);i;num0;}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.numr.numo.numa.numk.num// c r o a k// 0 1 2 3 4int[] hash new int[5];char[] s croakOfFrogs.toCharArray();int len s.length;int num0;for (char chr : s) {if(chrc){if(hash[4]0){hash[4]--; }hash[0];}else if(chrrhash[0]0){hash[0]--;hash[1];}else if(chrohash[1]0){hash[1]--;hash[2];}else if(chrahash[2]0){hash[2]--;hash[3];}else if(chrkhash[3]0){hash[3]--;hash[4];}else{return -1;}}for(int i0;i4;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]; // 数组模拟哈希表MapCharacter, 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 kclass 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;elseswap(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-l1)l];int leftl-1;int rightr1;int kl;while(kright){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 10){System.out.println(r:(r));System.out.println(l:(l));System.out.println(r-l1:(r-l1));}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;elsereturn 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;elseswap(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;elsereturn 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;elseswap(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(abk) {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][mid1,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 13、 计算右侧小于当前元素的个数hard 找每一个位置的逆序对的数量在第二题中我们利用归并排序统计了数组中逆序对的数量这会导致数组元素位置移动这就对统计每个位置逆序对的数量增加了难度。因为数组中元素并不是唯一的所以无法使用哈希表去确定某个元素的下标。解决方案是创建一个数组存储每个元素的下标 nums5、2、6、1 index0、1、2、3 在归并排序时会改变nums中元素的顺序知道将index的元素同步移动即可找到该元素的初始位置有一个小细节对nums合并排序的时候创建了辅助数组index数组要同步移动所以也要进行合并那么就也需要创建一个辅助数组来完成index的合并。如何统计每个位置的逆序对数量呢对于数组[left,right][leftxmid][mid1yright]; class Solution {int[] temp1;int[] temp2;int[] index;// 在归并排序过程中数组元素会发生移动// 使用index同步移动来存储某元素原始下标即// 对于任意下标iindex[i]是nums[i]的原始下标,i是nums[i]的当前下标public ListInteger countSmaller(int[] nums) {// 辅助数组temp1 new int[nums.length];temp2 new int[nums.length];// index数组标记nums数组元素原下标并同步与nums进行排序index new int[nums.length];// 对返回值进行初始化,也可将返回值创建成int[]最后在进行转化。ListInteger 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, ListInteger 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-j1);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 14、 翻转对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][mid1,right] 两个降序的数组// 升序也可以int l left, r mid 1;while (l mid r right) {// 5 4// 3 2 1if ((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 carry0;while(cur1!nullcur2!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!nullq.next!null){p.nextq.next;pp.next;q.nextp.next;p.nextq;pq;qq.next;}return newHead.next;}
}class Solution {public ListNode swapPairs(ListNode head) {if(headnull||head.nextnull){return head;}ListNode phead;headhead.next;p.nexthead.next;head.nextp;p.nextswapPairs(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(headnull||head.nextnull||head.next.nextnull) return;// 1、找到链表的中间结点快慢双指针// 2、将后半段链表逆序三指针头插法// 3、将两个链表合并依次出一个元素ListNode newHead new ListNode(0,head);ListNode fast newHead;ListNode slow newHead;while(fast!nullfast.next!null){fastfast.next.next;slowslow.next;}// ListNode prev new ListNode(0,slow.next);slow.nextnull;slow prev.next;ListNode pn prev.next;ListNode cur slow.next;while(cur!null){prev.nextcur;slow.nextcur.next;cur.nextpn;curslow.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指向head4、合并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].nextnull;endend.next;lists[index] next;} else {break;}}return ret.next;}
}
// 暴力解法class Solution {public ListNode mergeKLists(ListNode[] lists) {PriorityQueueListNode 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.length0) return null;return merge(lists,0,lists.length-1);}public ListNode merge(ListNode[] lists , int left,int right){if(leftright) return null;if(leftright) return lists[left];ListNode ret new ListNode();int mid left (right - left)/2;ListNode p merge(lists,left,mid);ListNode q merge(lists,mid1,right);return mergeList(p,q);}public ListNode mergeList(ListNode p,ListNode q){if(pnull) return q;if(qnull) return p;ListNode head new ListNode(0);ListNode prev head;while(p!nullq!null){if(p.valq.val){prev.nextp;prevprev.next;pp.next;}else{prev.nextq;prev q;qq.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(k1) return head;int len0;ListNode cur head;while(cur!null){len;curcur.next;}// 有n段需要逆序操作int n len/k; // 逆序ListNode newHead new ListNode(0);ListNode prev newHead;curhead;ListNode next cur.next;for(int i0;in;i){// 头插法for(int j0;jk;j){cur.next prev.next;prev.next cur;cur next;if(next!null)nextnext.next;}while(prev.next!null) prevprev.next;}prev.nextcur;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) {MapInteger,Integer hash new HashMap();for(int i0;inums.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) {SetInteger hash new HashSet();for(int i0;inums.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) {MapInteger,Integer hash new HashMap();for(int i0;inums.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 ListListString groupAnagrams(String[] strs) {ListListString ret new ArrayList();int[][] hash new int[strs.length][26];for(int i0;istrs.length;i){boolean flag true;for(int j0;jret.size();j){if(CheckPermutation(hash[j],strs[i])){ret.get(j).add(strs[i]);flagfalse;break;} }if(flag){int m ret.size();char[] s strs[i].toCharArray();for(char c:s){hash[m][c-a];}ListString 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 i0;i26;i){if(hash[i]!hash2[i]) return false;}return true;}
}class Solution {public ListListString groupAnagrams(String[] strs) {MapString, ListString 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 i0;while(is.length){boolean flag false;for(int j1;jstrs.length;j){if(!(istrs[j].length() s[i]strs[j].charAt(i))){flagtrue;}}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 i0;ia.length();i){if(a.charAt(a.length()-1-i)1){value_A(int)Math.pow(2,i);}}for(int i0;ib.length();i){if(b.charAt(b.length()-1-i)1){value_B(int)Math.pow(2,i);}}long c value_Avalue_B;StringBuffer ret new StringBuffer();if(c0) return 0;while(c0){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 carry0;StringBuffer ret new StringBuffer();while(len_a0 len_b0){carrya.charAt(len_a--)0?0:1;carryb.charAt(len_b--)0?0:1;ret.append(carry%2);carry/2; }// 10101// 10while(len_a0){carrya.charAt(len_a--)0?0:1;ret.append(carry%2);carry/2; }while(len_b0){carryb.charAt(len_b--)0?0:1;ret.append(carry%2);carry/2; }if(carry1) 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());}// 处理前导0while(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(len0){carrya*(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(slentemp.length()){slentemp.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 leftn-2,rightn-1;StringBuffer str new StringBuffer(s);while(left0){if(s.charAt(left)s.charAt(right)){str.delete(left,right1);left-2;right-2;}else{left--;right--;}}return str;}
}
// debug:
// abbaccb aab bpublic String removeDuplicates(String s){StringBuffer str new StringBuffer();for(int i0;is.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)示例 inputaaaoutputa inputabbaccaoutputa 一开始写的时候理解错题目意思了把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范围内ListString list new ArrayList();int left0,right0;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,right1);list.add(temp);left right1;}right;} list.add(s.substring(left,right).strip());StackInteger stack new Stack();char sign;for(int i0;ilist.size();i){String str list.get(i);if(str.equals()||str.equals(-)){signstr.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()){retstack.pop();}return ret;}
}
class Solution1 {public int calculate(String _s) {DequeInteger 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);elsest.push(st.pop() / tmp);} else {op s[i];i;}}// 统计结果int ret 0;while (!st.isEmpty()) {ret st.pop();}return ret;}
}题目保证表达式有结果表达式中包含空格先对字符串表达式做处理数字(112123)和运算符加到List list 中。遍历list 1、如果是数值将数值压入站内若数值前是负号则存入该数的相反数所以需要一个变量存储运算符(、-) 2、如果是、-运算符使用变量sign记录 2、如果遇到*、/运算符因为优先级比较高则需要将*、/两侧的数值进行运算将运算的结果压入栈内最后对站内的数值求和即可 // 双栈解法// 字符串表达式的通用解法,包含更多运算符及括号4、字符串解码★★★
实例
class Solution {public String decodeString(String s) {// 存在嵌套解码所以要是栈来解决由内而外解码StackString strs new Stack();StackInteger nums new Stack();strs.push();int i0;while(is.length()){// 数字if(0s.charAt(i) s.charAt(i) 9){int num 0;while(is.length()0s.charAt(i) s.charAt(i) 9){numnum*10(s.charAt(i)-0);}nums.push(num);}else if(s.charAt(i)[){i;StringBuffer str new StringBuffer();while(is.length()as.charAt(i) s.charAt(i) z){str.append(s.charAt(i));}strs.push(str.toString());}else if(as.charAt(i) s.charAt(i) z){StringBuffer str new StringBuffer(strs.pop());while(is.length()as.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) {StackStringBuffer st new Stack();st.push(new StringBuffer()); // 先放⼀个空串进去StackInteger 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();}
}
// 吴老师用了一个 StackStringBuffer strs new Stack();5、验证栈序列 class Solution {public boolean validateStackSequences(int[] pushed, int[] popped) {StackInteger stack new Stack();int j0;for(int i0;ipushed.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 ListNode children;public Node() {}public Node(int _val) {val _val;}public Node(int _val, ListNode _children) {val _val;children _children;}
};
*/class Solution {public ListListInteger levelOrder(Node root) {ListListInteger ret new ArrayList();if(root null) return ret;QueueNode queue new ArrayDeque();queue.add(root);while(!queue.isEmpty()){ int len queue.size();ListInteger list new ArrayList();for(int i0;ilen;i){Node top queue.poll();list.add(top.val);for(int j0;jtop.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 ListListInteger zigzagLevelOrder(TreeNode root) {QueueTreeNode queue new ArrayDeque();ListListInteger ret new ArrayList();if(root null) return ret;int level 1;queue.add(root);while(!queue.isEmpty()){ListInteger list new ArrayList();int qz queue.size();for(int i0;iqz;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%20) Collections.reverse(list);ret.add(list);level;}return ret;}
}3、二叉树最大宽度 思路一 层序遍历结点为null也会被加入到队列中去循环遍历队列去计算每一层的宽度取最大值,因为要存储空结点所以极端情况下根本存不下这个二叉树 根节点Node编号为x,则Node.left编号为2x,Node.right编号为2x1 给每个结点添加编号结点入队列是不需要存储空结点最大宽度使用队列两端结点编号的差值计算 细节问题结点的编号是由可能溢出的但是两个结点距离肯定是合法的根据下图可知不要对溢出的编号做任何处理计算的结果也是正确的。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) {ListPairTreeNode, Integer q new ArrayList(); // ⽤数组模拟队列q.add(new PairTreeNode, Integer(root, 1));int ret 0; // 记录最终结果while (!q.isEmpty()) {// 先更新⼀下这⼀层的宽度PairTreeNode, Integer t1 q.get(0);PairTreeNode, Integer t2 q.get(q.size() - 1);ret Math.max(ret, t2.getValue() - t1.getValue() 1);// 让下⼀层进队ListPairTreeNode, Integer tmp new ArrayList();for (PairTreeNode, Integer t : q) {TreeNode node t.getKey();int index t.getValue();if (node.left ! null) {tmp.add(new PairTreeNode, Integer(node.left, index * 2));}if (node.right ! null) {tmp.add(new PairTreeNode, 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 ListInteger largestValues(TreeNode root) {QueueTreeNode queue new ArrayDeque();ListInteger ret new ArrayList();if(rootnull) return ret;queue.add(root);while(!queue.isEmpty()){int maxInteger.MIN_VALUE;int qz queue.size();for(int i0;iqz;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) {// 创建一个大根堆将元素都放入大根堆// 将两个最大的石头碰撞碰撞的结果放入大根堆、// 重复第二步直到只剩一个石头或者没有PriorityQueueInteger 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 的⼩根堆PriorityQueueInteger 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 ListString topKFrequent(String[] words, int k) {// 创建大根堆存储键值对frequencystr// 1、预处理统计单词的频率MapString, Integer hash new HashMap();for (String word : words) {hash.put(word, hash.getOrDefault(word, 0) 1);}// 2、创建小根堆PriorityQueuePairString, Integer heap new PriorityQueue((a, b) - {if (a.getValue()b.getValue()) {return b.getKey().compareTo(a.getKey());}return a.getValue() - b.getValue();});// 3、求topKfor (Map.EntryString, Integer e : hash.entrySet()) {heap.offer(new Pair(e.getKey(), e.getValue()));if (heap.size() k) {heap.poll();}}// 4. 提取结果ListString ret new ArrayList();while (!heap.isEmpty()) {ret.add(heap.poll().getKey());}// 逆序数组Collections.reverse(ret);return ret;}
}4、数据流的中位数 class MedianFinder {PriorityQueueInteger left;PriorityQueueInteger 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;elsereturn 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 };// 队列Queueint[] 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;}}// 创建队列;Queueint[] 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;}}// 创建队列;Queueint[] 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 size0;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;Queueint[] 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};Queueint[] 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 k0;kqSize;k){int[] temp queue.poll();int x temp[0],ytemp[1];for(int i0;i4;i){int a x dx[i];int b y dy[i];if(0aam0bbnmaze[a][b].){maze[a][b] 0;queue.add(new int[]{a,b});if(a0||b0||am-1||bn-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];QueueString 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) {SetString vis new HashSet(); // ⽤来标记已经搜索过的状态SetString 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;QueueString 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, ListString wordList) {int size wordList.size();int length beginWord.length();boolean[] flag new boolean[size];QueueString queue new LinkedList();queue.add(beginWord);int step0;while(!queue.isEmpty()){step;int qSize queue.size();for(int i0;iqSize;i){String temp queue.poll();for(int j0;jsize;j){if(!wordList.get(j).equals(beginWord)flag[j]falseisMutate(temp,wordList.get(j))){flag[j]true;queue.add(wordList.get(j));if(wordList.get(j).equals(endWord)){return step1;}}}}}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, ListString wordList) {SetString hash new HashSet();for (String s : wordList)hash.add(s);SetString vis new HashSet(); // 标记已经搜索过的单词if (!hash.contains(endWord))return 0;QueueString 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(ListListInteger forest) {// 1、将要砍的树从小到大排序m forest.size();n forest.get(0).size();Listint[] 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、计算每树的最短间距BFSint sumStep 0;int length trees.size();if(length0) return 0;sumStepbfs(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;sumStepstep;}return sumStep;}// 两个坐标的最短距离public int bfs(ListListInteger forest, int[] tree1, int[] tree2) {if(tree1[0]tree2[0]tree1[1]tree2[1]) return 0;boolean[][] flag new boolean[m][n];Queueint[] 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(ListListInteger f) {m f.size();n f.get(0).size();Listint[] 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(ListListInteger f, int bx, int by, int ex, int ey) {if (bx ex by ey)return 0;Queueint[] 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];Queueint[] 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;}
}
// 我好NBint[][] 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];Queueint[] queue new LinkedList();for(int i0;im;i){for(int j0;jn;j){if((i0||j0||im-1||jn-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 i0;i4;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 sum0;for(int i0;im;i){for(int j 0;jn;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];Queueint[] 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];Queueint[] 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];Queueint[] 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、实现拓扑排序如何编程实现拓扑排序 建图在离散数学中学了 用二维数组也就是邻接矩阵建图。邻接表 ListListMapInteger,List 哈希表中Key为某个节点Value为该节点指向的结点。
1、课程表 class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {// 0、准备工作MapInteger, ListInteger 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、拓扑排序QueueInteger queue new LinkedList();// 2.1、入度为0的点进队列for(int i0;inumCourses;i){if(in[i]0){queue.add(i);}}// 一次层序遍历若a-b则a出队列b的入度减1。若b的入度为0则可以进队列// 直到队列为空说明图中没有入度为零点拓扑排序成功或者图中有环while(!queue.isEmpty()){int key queue.poll();ListInteger value hash.getOrDefault(key,new ArrayList());for(int x : value){in[x]--;if(in[x]0) queue.add(x);}}// 遍历每一个点的入度若存在入度不为的点则说明有环存在for(int i0;inumCourses;i){if(in[i]0) return false;}return true;}
}class Solution {public boolean canFinish(int n, int[][] p) {// 1. 准备⼯作int[] in new int[n]; // 统计每⼀个顶点的⼊度MapInteger, ListInteger edges new HashMap(); // 邻接表存图// 2. 建图for (int i 0; i p.length; i) {int a p[i][0], b p[i][1]; // b - aif (!edges.containsKey(b)) {edges.put(b, new ArrayList());}edges.get(b).add(a);in[a];}// 3. 拓扑排序QueueInteger q new LinkedList();// (1) 先把⼊度为 0 的点加⼊到队列中for (int i 0; i n; i) {if (in[i] 0)q.add(i);}// (2) bfswhile (!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 index0;MapInteger,ListInteger hash new HashMap();// 2、建图 for(int i0;iprerequisites.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、入度为零的结点进队列QueueInteger 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();ListInteger value hash.getOrDefault(key,new ArrayList());for(int x:value){in[x]--;if(in[x]0){queue.offer(x);ret[index] x;}}}if(indexnumCourses) 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 index0;// 1.1、因为知道有多少门课程那就一股脑把链表全部建好用得到的时候在区间写代码比较麻烦时间复杂度也高ListListInteger lists new ArrayList();for(int i0;inumCourses;i){lists.add(new ArrayList());}// 2、建图 for(int i0;iprerequisites.length;i){int key prerequisites[i][1];int value prerequisites[i][0];lists.get(key).add(value);in[value];}// 3、拓扑排序// 3.1、入度为零的结点进队列QueueInteger 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();ListInteger value lists.get(key);for(int x:value){in[x]--;if(in[x]0){queue.offer(x);ret[index] x;}}}if(indexnumCourses) 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];MapCharacter, SetCharacter hash new HashMap();MapCharacter, SetCharacter 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();QueueCharacter 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()) {SetCharacter values in.get(key);if(values.size()!0) return ;}for(int i0;iwords.length;i){String str words[i];for(int j0;jstr.length();j){char ch str.charAt(j);if(!ret.toString().contains(String.valueOf(ch))){ret.append(ch);}}}return ret.toString();}
}class Solution {MapCharacter, SetCharacter edges new HashMap(); // 邻接表【这一步我与老师写的一样】//【我用了邻接表MapCharacter, SetCharacter去存储某个节点的所有前驱结点】MapCharacter, 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. 拓扑排序QueueCharacter 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 - c2if (!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;}
}以空间换时间因为空间不值钱但是我的代码及消耗了空间又消耗了时间。 吴老师使用了MapCharacter, Integer in存储每个结点的入度存储的时候短杆多干一点存取数据的时候就方便一点这也不是绝对的看情况 我使用的是MapCharacter, Set in存储每个结点的前驱结点进而计算入度存储的时候偷懒取数据的时候就要付出代价
