算法 leetcode Hot100
刷完剑指Offer ，最近再刷一刷 Hot100
本贴记录一些刷 hot 100的心得（只要是没有思路的题目我基本都会记录以下，或者非常巧妙思路的题目）
4 两个有序数组的中位数
难度：困难
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
用了一个“类暴力算法”，结果意外的不错
就是空间复杂度高了点，除了合并数组（其实最多只需要两个数就可以），不知道哪里可以再降一降，如果想到了更有的解法会再补充。
class Solution {
public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len1 = nums1.length;
int len2 = nums2.length;
// 排除一些意外情况
if ((nums1 == null || len1 == 0) && (nums2 == null || len2 == 0)) {
return 0;
}
if (nums1 == null || len1 == 0) {
if (len2 % 2 == 1) { // 奇数
return nums2[len2 / 2];
} else {
return (nums2[len2 / 2 -1] + nums2[len2 / 2])/2.0;
}
}
if (nums2 == null || len2 == 0) {
if (len1 % 2 == 1) { // 奇数
return nums1[len1 / 2];
} else {
return (nums1[len1 / 2 -1] + nums1[len1 / 2 ])/2.0;
}
}
// 真正排序
// 先合并 (妹说应该可以重复)
//
int i = 0;
int j = 0;
int L = len1 + len2;
int l = 0;
int[] nums = new int[L];
while (l <= (L + 1) / 2) {
if (i<len1 &&(j >= len2 || nums1[i] <= nums2[j] )) { //
nums[l++] = nums1[i++];
}
else if (j<len2&&(i >= len1 || nums1[i] > nums2[j])) { //
nums[l++] = nums2[j++];
}
}
if (L % 2 == 1) { // 奇数
return nums[L / 2];
} else {
return (nums[L / 2 -1] + nums[L / 2 ])/2.0;
}
}
}5 最长回文串
难度：中等
示例 1：
输入：s = “babad”
输出：”bab”
解释：”aba” 同样是符合题意的答案。
示例 2：
输入：s = “cbbd”
输出：”bb”
1 <= s.length <= 1000s仅由数字和英文字母组成
1、暴力解：
先定义一个判断是否是回文的函数（O(n)），在主方法内遍历整个字符串保存最长的（O(n^2)），这必然有很多冗余计算，想了想算了。
2、最大公共字符串
借用求两个字符串的最大公共字符串的方案
1.1 首先求最大公共字符串
基本原理就是，构建一个二维矩阵记录当前点最大公共字符串的长度，当前点对应字符不相等那就不是，当前点相等，长度应该为斜上角（没有就是0）元素加一
1.2 这样记录的只是最长公共字符串，并非回文，还需要根据下标是否为对应关系来判断
如判断 下面 abc‘(s中首下标0 翻转过下标为9-0-1=8，应该和s’尾下标（2）对应，却没有 ；尾下标为2 ,翻转过来下表应该为9-2-1=6 ，应该和s’首下标（0）对应,却没有；)这里判断一处即可
这种求最大公共字符串的解法感觉还是挺有用的
public String longestPalindrome(String s) {
public static String longestPalindrome(String s) {
if(s.equals("")){
return "";
}
String origin =s;
String reverse = new StringBuffer(s).reverse().toString(); //反转后的字符串
int len = s.length();
int[][] arr = new int[len][len];
int max_PalindLen = 0;
int location = 0;
for(int i = 0 ;i<len ;i++){
for(int j =0 ;j<len;j++){
if(origin.charAt(i)!=reverse.charAt(j)){
arr[i][j] =0;
}
else{ // 公共部分出现啦
if (i==0||j==0){
arr[i][j]=1;
}
else {
arr[i][j] = arr[i-1][j-1]+1;
}
if ( (arr[i][j]>max_PalindLen) &&( (len-i-1)== (j-(arr[i][j]-1)) ) ) {
//判断是否是回文,
// (len-i-1) i尾 颠倒的位置 （j-（arr[i][j]））头的位置
max_PalindLen = arr[i][j];
location = i;
}
}
}
}
return origin.substring(location-(max_PalindLen-1),location+1);
}
}优化
我们分析一下循环，i=0，j=0，1，2…8 更新一行，然后 i=1，再更新一行，而更新的时候我们其实只需要上一行列的信息，更新第 3 行的时候，第 1 行的信息是没有用的。所以我们只需要一个一维数组就可以了。
但是更新 arr [i] 的时候我们需要 arr[i-1] 的信息，假设 a[3]=a[2]]+1，更新 a[4] 的时候， 我们需要 a[3] 的信息，但是 a[3] 在之前已经被更新了，所以 j 不能从0到 8，应该倒过来，a[8]=a[7]+1，a[7]=a[6]+1, 这样更新 a[8] 的时候用 a[7]，用完后才去更新 a[7]，保证了不会出错。
3、扩展中心(推荐)
我们知道回文串一定是对称的，所以我们可以每次循环选择一个中心，进行左右扩展，判断左右字符是否相等即可。
我们知道回文串一定是对称的，所以我们可以每次循环选择一个中心，进行左右扩展，判断左右字符是否相等即可。
public static String longestPalindrome(String s){
if(s==null||s.length()<1) return "";
int start =0;
int end =0;
for(int i = 0; i<s.length();i++){
int[] res1 = expendAroundCenter(s,i,i);
int[] res2 = expendAroundCenter(s,i,i+1);
int[] res = (res1[1]-res1[0] >= res2[1]-res2[0])? res1:res2;
if(res[1]-res[0] > end-start){
start = res[0];
end = res[1];
}
}
return s.substring(start+1,end);
}
private static int[] expendAroundCenter(String s, int left, int right) {
while (
(left>=0) && (right<s.length()) // 越界
&& (s.charAt(left)==s.charAt(right))
){
left--;
right++;
}
int[] res = {left,right};
return res ;
}4、Manacher’s Algorithm
好难不建议
10 正则表达式匹配
难度 困难
给你一个字符串 s 和一个字符规律p，请你来实现一个支持'.'和'*'的正则表达式匹配。
'.'匹配任意单个字符'*'匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
示例 1：
输入：
s="aa",p="a"
输出：false
解释："a"无法匹配"aa"整个字符串。
示例 2:
输入：
s="aa",p="a*"
输出：true
解释：因为'*'代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是'a'。因此，字符串"aa"可被视为'a'重复了一次。
示例 3：
输入：s =
"ab", p =".*"
输出：true
解释：".*"表示可匹配零个或多个（'*'）任意字符（'.'）。
提示：
1 <= s.length <= 20
1 <= p.length <= 20
- s 只包含从 a-z 的小写字母。
- p 只包含从 a-z 的小写字母，以及字符 . 和 *。
- 保证每次出现字符 * 时，前面都匹配到有效的字符
第一反应：动态规划
设：dp[i][j]为s的前i（下标0到i-1）个字符与p的前j(下标:0到j-1)个字符是否匹配的上
dp[0][0]=true;
分情况讨论：
如果
p.charAt(j-1) == s.charAt(i-1)则dp[i][j]完全取决于dp[i-1][j-1]如果
p.charAt(j-1)='.'同上如果
p.charAt(j-1) != s.charAt(i-1)如果
s.charAt(i-1)='*'如果
p.charAt(j-2) != s.charAt(i-2) and p.charAt(j-2)!='.''a*'匹配零个字符 ：则
dp[i][j]完全取决于dp[i][j-2](这种情况相当于a*是一个空字符)`p.charAt(j-2)==s.charAt(i-1) or p.charAt(j-2)='.''a*'匹配多个（>=0）字符 （分三种情况讨论，只要有一个满足就是 true）匹配零个字符
dp[i][j]完全取决于dp[i][j-2]虽然我能匹配但是我就不想匹配，和上面还是有区别的，上面不能匹配
匹配一个字符
dp[i][j]完全取决于dp[i-1][j-2]匹配多个字符
dp[i][j]完全取决于dp[i-1][j]
s.charAt(i)!='*',没救了直接false
public static boolean isMatch(String s, String p) { int slen = s.length(); int plen = p.length(); boolean[][] dp = new boolean[slen+1][plen+1]; dp[0][0] = true; // 考虑 dp[0][j]为true的情况 // 由于 a* 作为 空字符比较特殊，提前处理一遍 // 因为 * 必定能匹配所以不用考虑 第一个就是 ‘*’的情况 for (int j = 1; j <= plen ; j++) { if (p.charAt(j-1) == '*') dp[0][j] = dp[0][j - 2]; } // 如 abac a* dp[0]={true, true ,false, false,false} // 如 aaa a* dp[0]={true, true,true,true} for(int i =1;i<=s.length();i++){ for(int j = 1;j<=p.length() ;j++){ if (p.charAt(j-1)== s.charAt(i-1) || p.charAt(j-1)=='.' ){ dp[i][j]=dp[i-1][j-1]; } else{ //p.charAt(j-1)!= s.charAt(i-1) if(p.charAt(j-1)=='*'){ if ((p.charAt(j-2)==s.charAt(i-1)) || (p.charAt(j-2)=='.')){ dp[i][j]=dp[i][j-2] || dp[i-1][j-2] || dp[i-1][j] ; } else { dp[i][j]=dp[i][j-2]; } } // else{ // dp[i][j]=false; 默认 // } } } } return dp[slen][plen]; }
11. 盛最多水的容器
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
输入：[1,8,6,2,5,4,8,3,7]
输出：49
1、暴力解 超时
class Solution {
public int maxArea(int[] height) {
int Maxcontain = 0 ;
for(int i = 0 ;i <height.length-1;i++){
for(int j = i+1 ;j<height.length;j++){
Maxcontain = Math.max(Maxcontain,Math.min(height[i],height[j])*(j-i));
}
}
return Maxcontain;
}
}2、找规律
在每个状态下，无论长板或短板向中间收窄一格，都会导致水槽 底边宽度 −1−1 变短：
若向内 移动短板 ，水槽的短板 min(h[i],h[j]) 可能变大，因此下个水槽的面积 可能增大 。
若向内 移动长板 ，水槽的短板 min(h[i],h[j]) 不变或变小，因此下个水槽的面积 一定变小 。
因此，初始化双指针分列水槽左右两端，循环每轮将短板向内移动一格，并更新面积最大值，直到两指针相遇时跳出；即可获得最大面积。
class Solution {
public int maxArea(int[] height) {
int Maxcontain = 0 ;
int left = 0;
int right = height.length-1;
while(left<right){
Maxcontain = Math.max(Maxcontain, Math.min(height[left],height[right])*(right-left));
if (height[left]<height[right]){
left++;
}else{
right--;
}
}
return Maxcontain;
}
}20 有效的括号
给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
示例
输入：s = "()[]{}"
输出：true输入：s = "(]"
输出：false思路：
判定有点像栈的顺序，所以采用栈结构
判定对应的括号时，采用HashMap
class Solution {
public boolean isValid(String s) {
if(s.length()%2!=0) return false;
Map<Character,Character> map =new HashMap<>();
map.put('(',')');
map.put('[',']');
map.put('{','}');
map.put('?','?');
Stack<Character> stack = new Stack<>();
stack.push('?');
for(int i=0;i<s.length();i++){
char p = s.charAt(i);
if(map.containsKey(p)){ // 有左括号
stack.push(p);
}else{ // 右括号
char q = stack.peek();
if(map.get(q)==p) {
stack.pop();
}else{
return false;
}
}
}
if(stack.pop()!='?') return false;
else return true;
}
}23. 合并 K 个升序链表
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
1、前置知识：合并两个有序链表
需要三个特殊变量：
- 1、需要设置一个虚拟的“头变量”方便最后返回 head
- 2、需要一个探测指针，每次找最小的（还没遍历过的）元素节点 ptr
- 3、探测指针的上一个节点 pre
代码如下：
public ListNode mergeTwoLists(ListNode a, ListNode b) {
if (a == null || b == null) {
return a != null ? a : b;
}
ListNode head = new ListNode(0);
ListNode pre = head, aPtr = a, bPtr = b;
while (aPtr != null && bPtr != null) {
if (aPtr.val < bPtr.val) {
pre.next = aPtr;
aPtr = aPtr.next;
} else {
pre.next = bPtr;
bPtr = bPtr.next;
}
pre = pre.next;
}
pre.next = (aPtr != null ? aPtr : bPtr);
return head.next;
}
2、分治合并
类似于归并排序，两个两个排序， 排序后的数组再两个两个排序（用递归实现）
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
return merge(lists, 0, lists.length - 1);
}
public ListNode merge(ListNode[] lists, int l, int r) {
if (l == r) {
return lists[l];
}
if (l > r) {
return null;
}
int mid = (l + r) >> 1;
return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
}
public ListNode mergeTwoLists(ListNode a, ListNode b) {
if (a == null || b == null) {
return a != null ? a : b;
}
ListNode head = new ListNode(0);
ListNode pre = head, aPtr = a, bPtr = b;
while (aPtr != null && bPtr != null) {
if (aPtr.val < bPtr.val) {
pre.next = aPtr;
aPtr = aPtr.next;
} else {
pre.next = bPtr;
bPtr = bPtr.next;
}
pre = pre.next;
}
pre.next = (aPtr != null ? aPtr : bPtr);
return head.next;
}
}
3、优先队列（大根堆、小根堆）实现
首先介绍优先队列
- 优先队列的特性是，需要指定比较的方法（即元素是可比较的），每次出队都会按照指定的比较方案出队
- java中优先队列的书写方式
1、方案一：
建立优先队列采用 lambda表达式的方式 重写 比较器对象中的compare方法(比较器的泛型必须是队列元素的类型)
// 以下方式 初始容量可以省略
PriorityQueue<ListNode> queue = new PriorityQueue<>( initialSize , new Comparator<ListNode>(){
@Override
public int compare(ListNode o1,ListNode o2){
return o1.val-o2.val;
}
})2、方案二：
队列元素本身就是可比较对象一般的数值类型都可以直接用优先队列 ，如果不是数值类型，而是自定义类型，就必须实现Comparable接口 ，但这样，往往需要改动新建类，把原始类帮装起来，不推荐
class Status implements Comparable<Status> {
int val;
ListNode ptr;
Status(int val, ListNode ptr) {
this.val = val;
this.ptr = ptr;
}
public int compareTo(Status status2) {
return this.val - status2.val;
}
}
PriorityQueue<Status> queue = new PriorityQueue<Status>();3、此外，在不使用根堆（不需要添加元素仅需排序的时候）采用如下方式对一个数组进行排序
用Arrays.sort
public class Test {
public static void main(String[] args) {
Random random = new Random();
A[] list=new A[5];
for (int i = 0; i < list.length; i++) {
list[i]=new A(Math.abs(random.nextInt())%20);
}
printList(list);
System.out.println();
Arrays.sort(list, new Comparator<A>() {
@Override
public int compare(A o1, A o2) {
return (o1.a_id-o2.a_id);
}
});
printList(list);
}
private static void printList(A[] list) {
for (A a : list) {
System.out.print(a.a_id+" ");
}
}
}
class A {
public int a_id;
public A(int id){
this.a_id=id;
}
}一个优雅的回答
public ListNode mergeKLists(ListNode[] lists) {
// 维护一个优先队列，每次从队列中取出最小的 元素来重新排列
if(lists==null) return null;
PriorityQueue<ListNode> queue = new PriorityQueue<>( new Comparator<ListNode>(){
@Override
public int compare(ListNode o1,ListNode o2){
return o1.val-o2.val;
}
});
for(ListNode list:lists){
if(list!=null)
queue.add(list);
}
ListNode head = new ListNode(0);
ListNode pre_ptr=head;
while(!queue.isEmpty()){
ListNode ptr=queue.poll();
pre_ptr.next=ptr;
pre_ptr=ptr;
if(ptr.next!=null){queue.add(ptr.next);}
}
return head.next;
}
}72 编辑距离
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
示例
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')经典的动态规划问题
dp[i][j] 代表 word1 到 i 位置转换成 word2 到 j 位置需要最少步数
所以，
当 word1[i] == word2[j]，dp[i][j] = dp[i-1][j-1]；
当 word1[i] != word2[j]，dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
其中，dp[i-1][j-1] 表示替换操作，dp[i-1][j] 表示删除操作，dp[i][j-1] 表示插入操作。
注意，针对第一行，第一列要单独考虑，我们引入 '' 下图所示：
题解：
class Solution {
public int minDistance(String word1, String word2) {
// dp[i][j]=Math.max(dp[i-1][j-1], //匹配 当 位置字符相同
// dp[i][j-1]+1, //删除 不同
// dp[i-1][j]+1,//添加 不同
// dp[i-1][i+1]);//替换 不同
int m=word1.length();
int n=word2.length();
int[][] dp= new int[m+1][n+1];
dp[0][0]=0;
for(int i=1;i<m+1;i++){ //第一行 //把word2 始终视为空字符串
dp[i][0]=i;
}
for(int j=1;j<n+1;j++){ //第一列
dp[0][j]=j;
}
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(word1.charAt(i-1)==word2.charAt(j-1)){
dp[i][j]=dp[i-1][j-1];
}
else{
dp[i][j]=Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
}
}
}
return dp[m][n];
}
}76 最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
示例：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。解题思路：
滑动窗口的思想：
用i,j表示滑动窗口的左边界和右边界，通过改变i,j来扩展和收缩滑动窗口，可以想象成一个窗口在字符串上游走，当这个窗口包含的元素满足条件，即包含字符串T的所有元素，记录下这个滑动窗口的长度j-i+1，这些长度中的最小值就是要求的结果。
步骤一
不断增加j使滑动窗口增大，直到窗口包含了T的所有元素
步骤二
不断增加i使滑动窗口缩小，因为是要求最小字串，所以将不必要的元素排除在外，使长度减小，直到碰到一个必须包含的元素，这个时候不能再扔了，再扔就不满足条件了，记录此时滑动窗口的长度，并保存最小值
步骤三
让i再增加一个位置，这个时候滑动窗口肯定不满足条件了，那么继续从步骤一开始执行，寻找新的满足条件的滑动窗口，如此反复，直到j超出了字符串S范围。
但是请注意，三者管理并非顺序或者独立，需要缕清条件关系
class Solution {
public String minWindow(String s, String t) {
int[] need = new int[128];
for(int i=0;i<t.length();i++){
need[t.charAt(i)]+=1; // 当前需要字符表
}
int left=0;int l=0;
int right=0;int r=0;
int min=s.length()+1;
int count=t.length(); // 当前需要字符的个数
while(right<s.length()){
// 步骤一 ，right++
char ch= s.charAt(right);
if(need[ch]>0){
count--;
}
need[ch]--;
// 判断是否满足 窗内包含所有t(count==0)，如果满足 步骤二
// 如果满足 ，right就是窗口的最有边界 是包含关系
if(count==0){
// 步骤二 ，left ++ 直到遇到第一个 不能是窗口包含的 字符
// 这个不能使窗口完全包含 怎么表示？
// 首先 count==0表示 能完全包含
// need[ch] 表示欠缺的，如果使负数，表示不缺，如果是正数表示还在缺
// 那么 我们在 left++ 时， 相应的 need 一定是加回来的，
//如果need加回来之后等于0，就表示 加回来的值 不影响 “窗口包含所有”的条件可以继续左移
// 如果need 加回来 >0 表示已经开始缺了。。。 影响条件了
while(left<right && need[s.charAt(left)]<0){
need[s.charAt(left)]++;
left++;
}
// 此时，可能 left=right（不会吧？） 或者 need[ch_l]=0
// need【ch】 =0 表示 ch已经“不多余”了，但是你当前符号仍然是ch，
// 这个ch只能使 t中的字符（想想为什么？如果不是t中的，needch的取值遍历到这只能是负的 不可能出现0或者正数）
// 好了我们已经确定 这个ch就是 “窗口包含所有的” 条件的最后一个ch
// 计算当前窗口的大小
// 如果如果比之前的窗口小记录 窗口起止位置
if(right-left+1<min){
min=right-left+1;
l=left;
r=right;
}
// ok ，现在破环“包含条件”，重新回到步骤1
need[s.charAt(left)]++; // 现在 这个 need【ch_l】 一定使负数
left++;
count++;
}
right++; //别忘了右边界也要往后
}
if(min>s.length()) return "";
else{
return s.substring(l,r+1);
}
}
}96. 不同的二叉搜索树
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
如 n=3
输入：n = 3
输出：5
输入：n = 1
输出：1思路：
- 标签：动态规划
- 假设
n个节点存在二叉排序树的个数是G (n)，令f(i)为以i为根的二叉搜索树的个数，则
G(n)=f(1)+f(2)+f(3)+f(4)+…+f(n)
- 当
i为根节点时，其左子树节点个数为i-1个，右子树节点为n-i，则
f(i)=G(i−1)∗G(n−i)
- 综合两个公式可以得到 卡特兰数 公式
G(n)=G(0)∗G(n−1)+G(1)∗(n−2)+…+G(n−1)∗G(0)
class Solution {
public int numTrees(int n) {
int[] dp = new int[n+1];
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i < n + 1; i++)
for(int j = 1; j < i + 1; j++)
dp[i] += dp[j-1] * dp[i-j];
return dp[n];
}
}
