概述
2021.9月4日
题解链接
1. 两数之和
1.1 暴力
package Hot100;
/**
* @author : lkw
* @data : 2021/9/4 9:47
* @description :暴力
* 时间复杂度O(n^2)
**/
public class twoSum01_1 {
public static void main(String[] args) {
int[] nums={2,7,11,15};
int target = 9;
int[] a=twoSum(nums,target);
System.out.println(a.toString());
}
public static int[] twoSum(int[] nums, int target){
int[] ans = new int[2];
for (int i = 0; i < nums.length-1; i++) {
for (int j = i+1; j < nums.length; j++) {
if (nums[i]+nums[j]==target){
ans[0]=i;
ans[1]=j;
}
}
}
return ans;
}
}
1.2 hash表（推荐）
//map<key,value>放的是<值，在nums的下标>
public static int[] twoSum(int[] nums, int target){
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(target-nums[i])){
return new int[] {map.get(target-nums[i]),i};
}
map.put(nums[i],i);
}
return new int[0];
2. 两数相加
2.1 三个样例未通过，超过long长度）
下次要看清题目的位数，
long long的最大值：9223372036854775807（19位）
long long的最小值：-9223372036854775808
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//l1 = [2,4,3], l2 = [5,6,4]
StringBuffer str1 = new StringBuffer();
StringBuffer str2 = new StringBuffer();
while (l1!=null){
str1.insert(0,l1.val);
// str1.append(l1.val);
l1=l1.next;
}
while (l2!=null){
str2.insert(0,l2.val);
// str2.append(l2.val);
l2=l2.next;
}
long num=Long.parseLong(str1.toString())+Long.parseLong(str2.toString());
String num1=String.valueOf(num);
char n=num1.charAt(0);//char型输出的是ASCII码54
//首节点
ListNode node = new ListNode(num1.charAt(num1.length()-1)-'0');
ListNode nextNode;
nextNode=node;
for (int i = num1.length()-2; i >= 0; i--) {
ListNode newNode=new ListNode(num1.charAt(i)-'0');
nextNode.next=newNode;
nextNode=nextNode.next;
}
return node;
}
2.2 考虑进位，一位一位加
题解链接
package Hot100;
import Hot100.addTwoNumbers02_1.ListNode;
/**
* @author : lkw
* @data : 2021/9/4 20:12
* @description :有进位的
**/
public class addTwoNumbers02_2 {
public static ListNode addTwoNumbers(ListNode l1,ListNode l2) {
//l1 = [2,4,3], l2 = [5,6]
//3->4->2->null + 6->5
ListNode pre=new ListNode(0);//l3为起始指针的前一个
ListNode nextNode=pre;
int carry =0;//进位
while (l1!=null || l2!=null){
int x= l1!=null ? l1.val: 0;//位数不够补零进行计算
int y= l2!=null ? l2.val: 0;
int num = x+y+carry;
int curNum=num%10;//当前位
carry=num/10;//进位
nextNode.next=new ListNode(curNum);
nextNode=nextNode.next;
if(l1!=null){
l1=l1.next;
}
if(l2!=null){
l2=l2.next;
}
}
//如果最后有进位，则在最前面添加1
if (carry==1) {
nextNode.next=new ListNode(carry);
}
return pre.next;
}
}
9月5日
3. 无重复字符的最长子串
3.1 循环两次，记录从每个元素开始的最长子串长度
时间复杂度O(n^2)
package Hot100;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;
/**
* @author : lkw
* @data : 2021/9/5 10:24
* @description :3. 无重复字符的最长子串
* 新建一个数组，放从这个词往后的不重复的长度，最后取出数组中最大的值
*
**/
public class lengthOfLongestSubstring3_01 {
public static void main(String[] args) {
String s = "pwwkew";
lengthOfLongestSubstring(s);
}
public static int lengthOfLongestSubstring(String s) {
int max =0;
int nums[]=new int[s.length()];
if (s=="") return 0;
if (s.length()==1) return 1;
if (s.length()>1){
for (int i = 0; i < s.length()-1; i++) {
Set<String> set = new HashSet<>();
set.add(s.substring(i,i+1));
int j;
for (j = i+1; j <s.length() ; j++) {
String m=s.substring(j,j+1);
if(!set.contains(m)){
set.add(m);
}else {break;}
}
nums[i]=j-i;
max =max>j-i ? max :j-i;
}
nums[s.length()-1]=1;
}
return max;
}
}
3.2 滑动窗口
https://leetcode.cn/problems/longest-substring-without-repeating-characters/solution/hua-jie-suan-fa-3-wu-zhong-fu-zi-fu-de-zui-chang-z/
- start不动，end向后移动
- 当end遇到重复字符，start应该放在上一个重复字符的位置的后一位，同时记录最长的长度
- 怎样判断是否遇到重复字符，且怎么知道上一个重复字符的位置？--用哈希字典的key来判断是否重复，用value来记录该字符的下一个不重复的位置。
时间复杂度O(n)
package Hot100;
import java.util.HashMap;
/**
* @author : lkw
* @data : 2021/9/5 11:13
* @description :可以不用循环两次，
* map中存的是<值,值的位置>，如果有重复的值出现，重新定义窗口左侧，并且重写put新的位置
**/
public class lengthOfLongestSubstring3_02 {
public static void main(String[] args) {
String s = "au";
lengthOfLongestSubstring(s);
}
public static int lengthOfLongestSubstring(String s) {
int max = 0;
int left=0;
char m;
if (s == "") return 0;
if (s.length() == 1) return 1;
if (s.length() > 1) {
HashMap<Character, Integer> map = new HashMap() ;
for (int i = 0; i < s.length() ; i++) {
m=s.charAt(i);
if (map.containsKey(m)){
left=Math.max(left,map.get(m)+1);
}
map.put(m,i);
max=Math.max(max,i-left+1);
}
}
return max;
}
}4. 寻找两个正序数组的中位数
4.1 合并数组，再找到中位数
时间复杂度：O(m+n)
空间复杂度：O(m+n)
左边界下标是：(n-1)/2
package Hot100;
/**
* @author : lkw
* @data : 2021/9/5 15:12
* @description :4. 寻找两个正序数组的中位数
* 先排序，找中位数
**/
public class findMedianSortedArrays4_01 {
public static void main(String[] args) {
int[] nums1 = {1,3};
int[] nums2 = {2};
findMedianSortedArrays(nums1,nums2);
}
public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
int[] num3= new int[nums1.length+nums2.length];
int i=0,j=0,n=0;
while (i<nums1.length && j<nums2.length){
if (nums1[i]<nums2[j]){
num3[n++]=nums1[i++];
}else {
num3[n++]=nums2[j++];
}
}
while (i<nums1.length){
num3[n++]=nums1[i++];
}
while (j<nums2.length){
num3[n++]=nums2[j++];
}
// 0 1 2 3
if ((n-1)%2==0){
return num3[(n-1)/2];
}else
return (num3[(n-1)/2]+num3[(n-1)/2+1])/2.0;
}
}
9.7日
5. 最长回文子串
中心扩展算法
题解链接：力扣
class Solution {
//从中间向两边比较好判断
public String longestPalindrome(String s) {
int len=s.length();
String s1 = "", s2="",res="";
if (len<=1) return s;
for (int i = 0; i < len; i++) {
s1=Palindrome(s,i,i);
s2=Palindrome(s,i,i+1);
res=(res.length()>s2.length())?res:s2;
res=(res.length()>s1.length())?res:s1;
}
return res;
}
private String Palindrome(String s, int left, int right) {
//向两边延伸
while (left>=0 && right<s.length() && s.charAt(left)==s.charAt(right)){
left--;
right++;
}
return s.substring(left+1,right);//substring是前闭后开区间
}
}
注意： while ( s.charAt(start)==s.charAt(end) && start>=0 && end<s.length()){ }和
while ( start>=0 && end<s.length() && s.charAt(start)==s.charAt(end) ){ }
前者会报错，因为start和end可能越界会报错，&&连接的判断，前面的不满足，后面的就不会执行。
9月11日10. 正则表达式匹配
10. 正则表达式匹配（难）
题解链接
本题未全部理解
char[] cs = s.toCharArray();//将字符串转为字符串数组
package Hot100;
/**
* @author : lkw
* @data : 2021/9/11 14:27
* @description :'.' 匹配任意单个字符 '*' 匹配零个或多个前面的那一个元素
**/
public class isMatch10_01 {
public static void main(String[] args) {
String s = "aab";
String p = "c*a*b";
isMatch(s,p);
}
public static boolean isMatch(String s, String p) {
char[] cs = s.toCharArray();
char[] cp = p.toCharArray();
// dp[i][j]:表示s的前i个字符，p的前j个字符是否能够匹配
boolean[][] dp = new boolean[cs.length + 1][cp.length + 1];
// 初期值
// s为空，p为空，能匹配上
dp[0][0] = true;
// p为空，s不为空，必为false(boolean数组默认值为false，无需处理)
// s为空，p不为空，由于*可以匹配0个字符，所以有可能为true
//减2的原因：若出现*，则要裁掉2个
// 例如：aa* c*可以匹配空裁掉之后只剩下a，若裁后的不可以匹配空dp[0][j - 2]，则dp[0][j]也不行行
for (int j = 1; j <= cp.length; j++) {
if (cp[j - 1] == '*') {//若出现*，则要裁掉2个
dp[0][j] = dp[0][j - 2];//a*b*,若a*可以匹配空dp[0][j - 2]，则b*也能匹配空dp[0][j]
}
}
// 填格子
for (int i = 1; i <= cs.length; i++) {
for (int j = 1; j <= cp.length; j++) {
// 文本串和模式串末位字符能匹配上
if (cs[i - 1] == cp[j - 1] || cp[j - 1] == '.') {
dp[i][j] = dp[i - 1][j - 1];
} else if (cp[j - 1] == '*') { // 模式串末位是*
// 模式串*的前一个字符能够跟文本串的末位匹配上
if (cs[i - 1] == cp[j - 2] || cp[j - 2] == '.') {
dp[i][j] = dp[i][j - 2] // *匹配0次的情况
|| dp[i - 1][j]; // *匹配1次或多次的情况
} else { // 模式串*的前一个字符不能够跟文本串的末位匹配
dp[i][j] = dp[i][j - 2]; // *只能匹配0次
}
}
}
}
return dp[cs.length][cp.length];
}
}
因为这边定义的dp[i][j]是表示s的前i个字符和p的前j个字符能否匹配。s一共有s.length个字符，p一共有p.length个字符。最终答案就是dp[s.length][p.length]，而数组是从下标0开始的，所以dp数组的长度是s.length+1和p.length+1。
11. 盛最多水的容器
题解链接
暴力超时
public static int maxArea(int[] height) {
//将短板忘内挪
int i = 0, j = height.length - 1, max = 0;
while (i<j){
max = height[i]<height[j]?
Math.max(max,(j-i)*height[i++]):
Math.max(max,(j-i)*height[j--]);
}
return max;
}
15. 三数之和
题解链接
public static List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
int len = nums.length;
if (nums == null || len < 3) {
return ans;
}
Arrays.sort(nums);
for (int i = 0; i < len; i++) {
if (nums[i] > 0) break;
if (i > 0 && nums[i] == nums[i - 1]) continue;//i>0只是为了让i-1不越界
int L = i + 1;
int R = len - 1;
while (L < R) {
int sum = nums[i] + nums[L] + nums[R];
if (sum == 0) {
ans.add(Arrays.asList(nums[i], nums[L], nums[R]));
while (L < R && nums[L] == nums[L + 1]) {
L++;
}
while (L < R && nums[R] == nums[R - 1]) {
R--;
}
L++;
R--;
} else if (sum < 0) L++;
else if (sum > 0) R--;
}
}
return ans;
}2021年9月20
17. 电话号码的字母组合
题解
回溯
package Hot100;
import java.security.Key;
import java.util.*;
/**
* @author : lkw
* @data : 2021/9/20 10:30
* @description :map.put("2", Arrays.asList("a", "b", "c"));//Map<String,List<String>>的写法
**/
public class letterCombinations17_01 {
private static final String[] KET ={"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
public static void main(String[] args) {
final String[] KET;
String digits = "23";
letterCombinations(digits);
}
public static List<String> letterCombinations(String digits) {
List<String> list=new ArrayList<>();
if (digits.length()==0 || digits==null) return list;
Combinations(new StringBuffer(),list,digits);
return list;
}
public static void Combinations(StringBuffer pre, List<String> list,String digits){
if (pre.length()==digits.length()){
list.add(pre.toString());
return ;
}
int curDigits=digits.charAt(pre.length())-'0';
String str= KET[curDigits];
for (char c: str.toCharArray()) {
pre.append(c);
Combinations(pre,list,digits);
pre.deleteCharAt(pre.length()-1);
}
}
}
19. 删除链表的倒数第 N 个结点
题解链接
方法一：计算长度
package Hot100;
/**
* @author : lkw
* @data : 2021/9/20 20:41
* @description :
**/
public class removeNthFromEnd19_01 {
public static class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
public static void main(String[] args) {
ListNode head = new ListNode(1);
ListNode node = head;
int n = 1;
for (int i = 2; i <= n; i++) {
node.next = new ListNode(i);
node = node.next;
}
removeNthFromEnd(head, 1);
}
public static ListNode removeNthFromEnd(ListNode head, int n) {
ListNode node = head;
int len = 0;
while (node != null) {
len++;//计算长度
node = node.next;
}
node = head;
if (len == n){
return node.next;//如果删除的是头
}
node = head;
for (int i = 1; i < len - n; i++) {
node = node.next;
}
node.next = node.next.next;//删除的是中间元素
return head;
}
}
方法二：优化方法一（哑节点）
在对链表进行操作时，一种常用的技巧是添加一个哑节点（dummy node），它的next 指针指向链表的头节点。这样一来，我们就不需要对头节点进行特殊的判断了。
public static ListNode removeNthFromEnd(ListNode head, int n) {
//哑节点，不需要考虑头
ListNode dummy = new ListNode(0, head);
ListNode cur = dummy;
int len = 0;
while (head != null) {
len++;//计算长度
head = head.next;
}
for (int i = 1; i < len-n+1; i++) {
cur=cur.next;
}
cur.next=cur.next.next;
return dummy.next;
}方法三：双指针
public static ListNode removeNthFromEnd(ListNode head, int n) {
//哑节点，不需要考虑头
ListNode dummy = new ListNode(0, head);
ListNode first =head;//first比second前挪nge
ListNode second = dummy;
//挪到要删节点的前驱
for (int i = 0; i < n; i++) {
first=first.next;
}
while (first!=null) {
first=first.next;
second=second.next;
}
second.next=second.next.next;
return dummy.next;
}9月21日
20. 有效的括号
//pop() 方法弹出栈顶元素， 调用后， 栈顶元素从栈中被永久性地删除。
//peek() 方法则只返回栈顶元素， 而不删除它。
public static boolean isValid(String s) {
Stack<Character> stack=new Stack<>();
stack.push('?');
HashMap<Character,Character> map =new HashMap<>();
map.put('(',')');
map.put('{','}');
map.put('[',']');
map.put('?','?');
for (Character c:s.toCharArray()) {
if (map.containsKey(c)){
stack.push(c);//如果是左括号则放入
}else if(c!=map.get(stack.pop())){
return false;
}
}
return stack.size()==1;
}9月22
23. 合并K个升序链表
package Hot100;
/**
* @author : lkw
* @data : 2021/10/2 9:48
* @description :每次都得比较k个中最小的
**/
public class mergeKLists23_01 {
public static class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
public ListNode mergeKLists(ListNode[] lists) {
ListNode ans = null;
int nums=lists.length;
for (int i = 0; i < nums; i++) {
ans= mergetwoLists(ans,lists[i]);
}
return ans;
}
public ListNode mergetwoLists(ListNode l1,ListNode l2) {
if (l1==null || l2==null){
return l1!=null?l1:l2;
}
ListNode dummy = new ListNode(0);
ListNode newnode = dummy;
//怎么三者比出最小的？
while (l1!=null && l2!=null){
if (l1.val<=l2.val){
newnode.next=l1;
l1=l1.next;
}else {
newnode.next=l2;
l2=l2.next;
}
newnode=newnode.next;
}
newnode.next=l1!=null?l1:l2;
return dummy.next;
}
}
21. 合并两个有序链表
package Hot100;
/**
* @author : lkw
* @data : 2021/9/22 20:11
* @description :不需要节点再记录l1和l2的位置
**/
public class mergeTwoLists21_01 {
public static class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public static void main(String[] args) {
// l1 = [1,2,4], l2 = [1,3,4];
// ListNode l1= new ListNode(1);
// l1.next=new ListNode(2);
// l1.next.next=new ListNode(4);
//
// ListNode l2= new ListNode(1);
// l2.next=new ListNode(3);
// l2.next.next=new ListNode(4);
ListNode l1= null;
ListNode l2= null;
mergeTwoLists(l1,l2);
}
public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//哑节点
ListNode ans = new ListNode(-999);
ListNode cur3 = ans;
while (l1!=null && l2!=null){
if (l1.val<=l2.val){
cur3.next= l1;
l1=l1.next;
}else {
cur3.next= l2;
l2=l2.next;
}
cur3=cur3.next;
}
// if (l1!=null){
// cur3.next=l1;
// }else cur3.next=l2;
cur3.next= l1!=null?l1:l2;
return ans.next;
}
}
9月25日
22. 括号生成
题解
回溯法：
如果左括号数量不大于 n，我们可以放一个左括号。如果右括号数量小于左括号的数量，我们可以放一个右括号。
class Solution {
public static List<String> generateParenthesis(int n) {
List<String> ans = new ArrayList<>();
backing(ans,0,0,new StringBuffer(),n);
return ans;
}
public static void backing( List<String> ans,int left,int right,StringBuffer str,int n){
if (str.length()==2*n){
ans.add(str.toString());
return;
}
//如果左括号的个数少于n，则可以加入左括号
if (left<n){
str.append("(");
backing(ans,left+1,right,str,n);
str.deleteCharAt(str.length()-1);
}
//右括号的个数少于左括号，可以加入左括号
if (right<left){
str.append(")");
backing(ans,left,right+1,str,n);
str.deleteCharAt(str.length()-1);
}
}
}10.2日
23. 合并K个升序链表
方法一：顺序合并
package Hot100;
/**
* @author : lkw
* @data : 2021/10/2 9:48
* @description :
**/
public class mergeKLists23_01 {
public static class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
public ListNode mergeKLists(ListNode[] lists) {
ListNode ans = null;
int nums=lists.length;
for (int i = 0; i < nums; i++) {
ans= mergetwoLists(ans,lists[i]);
}
return ans;
}
public ListNode mergetwoLists(ListNode l1,ListNode l2) {
if (l1==null || l2==null){
return l1!=null?l1:l2;
}
ListNode dummy = new ListNode(0);
ListNode newnode = dummy;
//怎么三者比出最小的？
while (l1!=null && l2!=null){
if (l1.val<=l2.val){
newnode.next=l1;
l1=l1.next;
}else {
newnode.next=l2;
l2=l2.next;
}
newnode=newnode.next;
}
newnode.next=l1!=null?l1:l2;
return dummy.next;
}
}
方法二：分治合并
public ListNode mergeKLists(ListNode[] lists) {
return merge(lists,0, lists.length-1);
}
public ListNode merge(ListNode[] lists,int left,int right){
if (left==right) return lists[left];
if (left>right) return null;
int mid = left+(right-left)/2;//防止溢出
return mergetwoLists(merge(lists,left,mid),merge(lists,mid+1,right));
}
public ListNode mergetwoLists(ListNode l1, ListNode l2) {
if (l1==null || l2==null){
return l1!=null?l1:l2;
}
ListNode dummy = new ListNode(0);
ListNode newnode = dummy;
//怎么三者比出最小的？
while (l1!=null && l2!=null){
if (l1.val<=l2.val){
newnode.next=l1;
l1=l1.next;
}else {
newnode.next=l2;
l2=l2.next;
}
newnode=newnode.next;
}
newnode.next=l1!=null?l1:l2;
return dummy.next;
}31. 下一个排列
思路
1.从后往前找到第一次出现升序的地方（位置是i和i+1）
2.找到i之后比i大的最小值k
3.调换i和k位置上的值
4.将i之后的数字升序排序
代码看：https://leetcode-cn.com/problems/next-permutation/solution/xia-yi-ge-pai-lie-by-leetcode-solution/
题解思路看：https://leetcode-cn.com/problems/next-permutation/solution/xia-yi-ge-pai-lie-suan-fa-xiang-jie-si-lu-tui-dao-/
package Hot100;
/**
* @author : lkw
* @data : 2021/10/2 9:57
* @description :
**/
public class nextPermutation31_01 {
public static void main(String[] args) {
int[] nums={5,4,7,5,3,2};
nextPermutation(nums);
}
public static void nextPermutation(int[] nums) {
if (nums.length<2) return;//1,3
int i;
//从后往前找到第一次出现升序 nums[i]<nums[i+1]的地方（因为是第一次出现的，因此i+1之后的都是降序的）
for (i = nums.length-2; i >=0 && nums[i]>=nums[i+1]; i--);
int k;
//如果序列本来是倒序，例如：3,2,1 则i=-1
if (i>=0){
//k是找到i后面比i大的最小值
for (k = nums.length-1; k >i && nums[k]<=nums[i]; k--);
swap(nums,i,k);
}
reverse(nums,i+1);
}
public static void swap(int[] nums,int index1,int index2){
int temp=nums[index1];
nums[index1]=nums[index2];
nums[index2]=temp;
}
//重排从start开始的元素
public static void reverse(int[] nums,int start){
int end=nums.length-1;
while (start<end){
swap(nums,start++,end--);
}
}
}
10月3日
32. 最长有效括号
题解
package Hot100;
import java.util.Stack;
/**
* @author : lkw
* @data : 2021/10/3 10:22
* @description :
**/
public class longestValidParentheses32_01 {
public static void main(String[] args) {
String s = "()(()";
longestValidParentheses(s);
}
public static int longestValidParentheses(String s) {
char[] str=s.toCharArray();
int max=0;
Stack<Integer> stack = new Stack<>();
stack.push(-1);
for (int i = 0; i < s.length(); i++) {
if (str[i]=='('){
stack.push(i);
}else {
//遇到右括号先出栈
stack.pop();
if (stack.isEmpty()){
stack.push(i);
}else
max=Math.max(i-stack.peek(),max);
}
}
return max;
}
}
10月4日
33. 搜索旋转排序数组
二分法：题解
将数组从中间分开成左右两部分的时候，一定有一部分的数组是有序的。先判断目标值是否在有序部分（因为有序的好判断，通过左右边界大小直接判断），如果不在有序这边，那一定在另一部分。
先判断目标值是否在有序的这边，如果不在搜索另一部分。
那如何判断是否为有序数组：
如果nums[left]<=nums[mid]则是有界的，判断其左右边界与target大小关系。
package Hot100;
/**
* @author : lkw
* @data : 2021/10/4 15:10
* @description :旋转排序数组，实际是想告诉我们两个升序数组
**/
public class search33_01 {
public static void main(String[] args) {
int[] nums = {3,1};
int target = 1;
search(nums,target);
}
public static int search(int[] nums, int target) {
int len=nums.length;
if (len==0) return -1;
if (len==1) return nums[0]==target?0:-1;
int left=0;
int right= len-1;
while(left<=right){
int mid = (left+right)/2;
if (nums[mid]==target) return mid;
//左侧有序
if (nums[left]<=nums[mid]){//等于的情况就是mid就是left
if (nums[left]<=target && nums[mid]>target ){
right=mid-1;
}else
left=mid+1;
}else{//右侧有序
if (nums[right]>=target && nums[mid]<target ){
left=mid+1;
}else right=mid-1;
}
}
return -1;
}
}
10月7日
34. 在排序数组中查找元素的第一个和最后一个位置
1.二分法：
题解链接
1.1容易理解，推荐
思路：
1.二分查找找到nums[mid]==target.
2.再找出mid左侧和右侧，是否还存在target.
public int[] searchRange(int[] nums, int target) {
//1.二分查找找到nums[mid]==target 2.再找出mid左侧和右侧，是否还存在target
if (nums.length==0) return new int[]{-1,-1};
int mid=0;
int left=0;
int right= nums.length-1;
while (left<=right){
mid=left+(right-left)/2;
if (nums[mid]==target) break;
else if (nums[mid]<target){
left=mid+1;
}else right=mid-1;
}
if (nums[mid]==target) {
left=right=mid;
}else return new int[]{-1,-1};
while (left>=1 && nums[left]==nums[left-1]){
left--;
}
while (right< nums.length-1 && nums[right]==nums[right+1]){
right++;
}
return new int[]{left,right};
}1.2 不易理解
public static int[] searchRange(int[] nums, int target) {
int leftNum=binary(nums,target,true);
int rightNum=binary(nums,target,false)-1;//右侧找到的是大于target的第一个元素
if (leftNum<=rightNum && leftNum>=0 && rightNum<=nums.length-1 &&nums[rightNum]==target && nums[leftNum]==target ){
return new int[]{leftNum,rightNum};
}
return new int[]{-1,-1};
}
public static int binary(int[] nums, int target,boolean le){
//le为true代表找到是最左侧元素
int left=0;
int right= nums.length-1;
int ans= nums.length;//若未找到目标元素，返回ans，在上级判断是会越界，则返回{-1，-1}
while(left<=right){
//nums[mid]<target时，查找leftNum和rightNum都找左侧区间，
//在nums[mid]=target情况下，查找leftNum时查找左侧区间，查找rightNum是查找右侧区间，
//因此使用le标记查找的是leftNum还是rightNum
int mid= left+(right-left)/2;
if (nums[mid]>target || (le==true && nums[mid]==target) ){
//查找[left,mid-1]
right=mid-1;
ans=mid;
}else{
left=mid+1;
}
}
return ans;
}2.暴力解法：
找到第一个与target相等的值为左边届，然后记录其后面，与target相等的个数，来定位右边界。
public static int[] searchRange(int[] nums, int target) {
boolean flag=false;
int count=0;
int left=-1;
for (int i = 0; i < nums.length; i++) {
if (nums[i]>target){
break;
}
if (nums[i]==target){
if (!flag){
left=i;
flag=true;
}else
count++;
}
}
return new int[]{left, left+count};
}39. 组合总和
res.add(ans);//存的是实时的ans，ans变则res中的值也变。引用的是同一个地址
因此要使用res.add(new ArrayList<>(ans));
package Hot100;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
/**
* @author : lkw
* @data : 2021/10/7 15:52
* @description :
**/
public class combinationSum39_01 {
public static void main(String[] args) {
int[] candidates = {2,3,6,7};
int target = 7;
combinationSum(candidates,target);
}
public static List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> lists =new ArrayList<>();
List<Integer> ans=new ArrayList<>();
backing(candidates,lists,ans,0,target);
return lists;
}
public static void backing(int[] candidates, List<List<Integer>> lists,
List<Integer> ans,int start,int target){
if (target ==0){
lists.add(new ArrayList<>(ans));
return;
}
for (int i = start; i < candidates.length ; i++) {
if (candidates[i]<=target){
ans.add(candidates[i]);
backing(candidates,lists,ans,i,target-candidates[i]);
ans.remove(ans.size()-1);
}
}
}
}
10月8日
42. 接雨水
题解
1.动态编程
从左往右找最大的left,从右往左找最大的right
public int trap(int[] height) {
int size=height.length;
if(size==0 || height==null){
return 0;
}
int ans=0;
int[] left_max=new int[size];
int[] right_max=new int[size];
left_max[0]=height[0];
for (int i = 1; i < size; i++) {
left_max[i]=Math.max(left_max[i-1],height[i]);
}
right_max[size-1]=height[size-1];
for (int i = size-2; i >=0 ; i--) {
right_max[i]=Math.max(right_max[i+1],height[i]);
}
for (int i = 0; i < size; i++) {
ans+=Math.min(right_max[i],left_max[i])-height[i];
}
return ans;
} public int trap(int[] height) {
int len=height.length;
//从左往右找最大的left,从右往左找最大的right
int[] left=new int[len];
int[] right=new int[len];
right[len-1]=height[len-1];
left[0]=height[0];
int sum=0;
for (int i = 1; i < len; i++) {
int j=len-1-i;
left[i]=Math.max(left[i-1],height[i]);
right[j]=Math.max(right[j+1],height[j]);
}
for (int i = 0; i < len; i++) {
sum+=Math.min(left[i],right[i])-height[i];
}
return sum;
}46. 全排列
题解
public static List<List<Integer>> permute(int[] nums) {
List<List<Integer>> lists =new ArrayList<>();
List<Integer> ans= new ArrayList<>();
boolean[] visited=new boolean[nums.length];
backing(nums,lists,ans,visited);
return lists;
}
private static void backing(int[] nums,List<List<Integer>> lists,
List<Integer> ans,boolean[] visited) {
if (ans.size()== nums.length){
lists.add(new ArrayList<>(ans));
}
for (int i = 0; i < nums.length ; i++) {
if (visited[i]){
continue;
}
visited[i]=true;
ans.add(nums[i]);
backing(nums,lists,ans,visited);
ans.remove(ans.size()-1);//移除索引位置,从0开始
visited[i]=false;
}
}48. 旋转图像
题解
1.方法一：使用辅助数组
public void rotate(int[][] matrix) {
int len = matrix.length;
int[][] max_new = new int[len][len];
for (int i = len-1; i >=0; i--) {
for (int j = 0; j < len; j++) {
max_new[j][len-i-1]=matrix[i][j];
}
}
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
matrix[i][j]=max_new[i][j];
}
}
}2.方法二：旋转
public void rotate(int[][] matrix) {
int len =matrix.length;
int temp;
//上下翻转
for (int i = 0; i < len/2; i++) {
for (int j = 0; j < len; j++) {
temp=matrix[len-i-1][j];
matrix[len-i-1][j]=matrix[i][j];
matrix[i][j]=temp;
}
}
//对称轴翻转
for (int i = 0; i < len; i++) {
for (int j = 0; j < i; j++) {
temp=matrix[j][i];
matrix[j][i]=matrix[i][j];
matrix[i][j]=temp;
}
}
}10月11日
49. 字母异位词分组
//String key=strChar.toString();//通过不了，引用的是地址 String key=new String(strChar);
package Hot100;
import java.util.*;
public class groupAnagrams_49 {
public static void main(String[] args) {
String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
groupAnagrams(strs);
}
public static List<List<String>> groupAnagrams(String[] strs) {
Map<String,List<String>> map=new HashMap<String,List<String>>();
for (String str:strs) {
char array[]=str.toCharArray();
Arrays.sort(array);
String key = new String(array);
String key1 =array.toString();//这样转字符串不对，因为数组是对象，没有重写toString方法，因此得到的是类签名
List<String> list=map.getOrDefault(key,new ArrayList<>());
list.add(str);
map.put(key,list);
}
return new ArrayList<List<String>>(map.values());
}
}
注意：
1.getOrDefault() 方法获取指定 key 对应对 value，如果找不到 key ，则返回设置的默认值。
2. new String() 和 toString()的区别
Java对象都继承于Object，Object中提供了toString方法，用于简单返回该类的类签名。在Java中，数组也可以看作是一种对象，显然byte[]也是一种继承与Object的对象，并且它没有重写Object的toString方法，因此使用byte[]的toString返回的字符串，仅仅是byte[]的类签名，而不是对应的值。
改为使用new String()构造方法，将byte[]转换为字符串，得到的就会是一个根据字节数组内容构造的字符串。
总结：new String（）一般使用字符转码的时候,例如byte[]数组的时候。
toString（）将对象打印的时候使用。
53. 最大子序和
public static int maxSubArray(int[] nums) {
int cur=nums[0];
int max=nums[0];
for (int i = 1; i < nums.length; i++) {
if(cur>0){
cur=cur+nums[i];
}else {
//如果当前值前面的和为负数，则舍弃前面的值，
cur=nums[i];
}
max=Math.max(cur,max);
}
return max;
}10月12日
55. 跳跃游戏
题解
public static boolean canJump(int[] nums) {
int n= nums.length;
if (n==1) { return nums.length>=0;}
int rightmost=nums[0];//若nums={0}，则通过不了,需要加if判断n==1
//int rightmost=0;//for循环从0开始
for (int i = 1; i < n; i++) {
if (i<=rightmost){
rightmost=Math.max(rightmost,i+nums[i]);
if (rightmost>=n-1){
return true;
}
}
}
return false;
}
}
// public boolean canJump(int[] nums) {
// int n = nums.length;
// int rightmost = 0;
// for (int i = 0; i < n; ++i) {
// if (i <= rightmost) {
// rightmost = Math.max(rightmost, i + nums[i]);
// if (rightmost >= n - 1) {
// return true;
// }
// }
// }
// return false;
// }
56. 合并区间
题解
思路： 1.按首元素排序 2.取当前遍历元素的左右边界，若列表最后一个元素右边界<左边界，则不能合并，直接插入。 3.若能合并，只修改列表最后一个元素右边界即可。merges.get(merges.size()-1)[1]=right;//取的是地址，因此直接赋值就行
public static int[][] merge(int[][] intervals) {
List<int[]> merges=new ArrayList<>();
if (intervals.length==0){
return new int[0][2];
}
//按首元素升序排序
Arrays.sort(intervals, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0]-o2[0];//o1-o2为升序，o2-o1为降序
}
});
//取当前遍历元素的左右边界，若列表最后一个元素右边界<左边界，则不能合并，直接插入
//合并，只修改列表最后一个元素右边界即可
for (int i = 0; i < intervals.length; i++) {
int left=intervals[i][0];
int right=intervals[i][1];
if (merges.size()==0|| merges.get(merges.size()-1)[1]<left){
merges.add(new int[]{left,right});
}else{
merges.get(merges.size()-1)[1]=Math.max(merges.get(merges.size()-1)[1],right);//取的是地址，因此直接赋值就行
}
}
return merges.toArray(new int[merges.size()][]);
}注意：
//按首元素升序排序
Arrays.sort(intervals, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0]-o2[0];//o1-o2为升序，o2-o1为降序
}
});return merges.toArray(new int[merges.size()][]);//括号是merges转成的int数组大小
10月13日
62. 不同路径
题解
1.动态规划
public int uniquePaths(int m, int n) {
int[][] de=new int[m][n];
for (int i = 0; i < m; i++) {
de[i][0]=1;
}
for (int i = 0; i < n; i++) {
de[0][i]=1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j <n ; j++) {
de[i][j]=de[i-1][j]+de[i][j-1];
}
}
return de[m-1][n-1];
}2.数学
public int uniquePaths(int m, int n) {
double ans=1;
for (int x = 1,y=n; x < m; x++,y++) {
ans=ans*y/x;
}
return (int)ans;
}64. 最小路径和
题解
public int minPathSum(int[][] grid) {
if (grid==null||grid.length==0){
return 0;
}
int m=grid.length;
int n=grid[0].length;
int[][] de =new int[m][n];
de[0][0]=grid[0][0];
for (int i = 1; i < m; i++) {
de[i][0]=de[i-1][0]+grid[i][0];
}
for (int i = 1; i <n; i++) {
de[0][i]=de[0][i-1]+grid[0][i];
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
de[i][j]=Math.min(de[i-1][j],de[i][j-1])+grid[i][j];
}
}
return de[m-1][n-1];
}10月14日
70. 爬楼梯
1.动态规划：动态数组
题解
public static int climbStairs(int n){
int a=1;int b=1;int c=1;
for (int i = 1; i < n; i++) {
a=b;
b=c;
c=a+b;
}
return c;
}75. 颜色分类
方法一：排序
//冒泡排序
public static void sortColors(int[] nums) {
int len= nums.length;
for (int i = len-1; i >=0; i--) {
for (int j = 0; j < i; j++) {
if (nums[j]>nums[j+1]){
int temp=nums[j+1];
nums[j+1]=nums[j];
nums[j]=temp;
}
}
}
}方法二：
此代码中： 0 的优先级> 1 的优先级 >2 的优先级
即时2先被填入，但是若最后值不为2，会被覆盖掉。
public static void sortColors(int[] nums) {
//zero表示数字0的右侧边界，one、two分别表示1 和 2 的右侧边界
int zero = 0;int one = 0;int two = 0;
int length = nums.length;
for(int i = 0; i < length; i++) {
//记录下待处理的值
int temp = nums[i];
//不管怎样，我先给你填个2
nums[two++] = 2;
// <=1的话 1的右侧边界one要向右挪一格
if(temp <= 1){
nums[one++] = 1;
}
//为0的话 0的右侧边界zero要向右挪一格
if(temp == 0) {
nums[zero++] = 0;
}
}
}10月16日
72. 编辑距离
题解
dp数组类似这样：
public int minDistance(String word1, String word2) {
int m=word1.length();
int n=word2.length();
//一个字符串为空
if (m*n==0) return m+n;
int dp[][]=new int[m+1][n+1];
for (int i = 0; i < m+1; i++) {
dp[i][0]=i;
}
for (int i = 0; i < n+1; i++) {
dp[0][i]=i;
}
for (int i = 1; i < m+1; i++) {
for (int j = 1; j < n+1; j++) {
int delete=dp[i-1][j]+1;
int insert=dp[i][j-1]+1;
int alert=dp[i-1][j-1];
//修改后前一个字符不相等，编辑距离加一
if (word1.charAt(i-1)!=word2.charAt(j-1)){
alert++;
}
dp[i][j] =Math.min(delete,Math.min(insert,alert));
}
}
return dp[m][n];
}10月19日
94. 二叉树的中序遍历
1.递归
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res=new ArrayList<>();
inord(root,res);
return res;
}
public void inord(TreeNode root,List<Integer> res){
if (root==null){
return;
}
inord(root.left,res);
res.add(root.val);
inord(root.right,res);
}2.迭代
Java中LinkedList add 是加在list尾部.
LinkedList push 施加在list头部.
res.add(root.val);的位置决定前中后序遍历
public List<Integer> inorderTraversal(TreeNode root) {
//!deque.isEmpty
List<Integer> res=new ArrayList<>();
Stack<TreeNode> deque=new Stack<>();
while(root!=null || !deque.isEmpty()){
//判断栈是否为空用：deque.isEmpty()
while (root!=null){
deque.push(root);//deque.push(root);
root=root.left;
}
root=deque.pop();
res.add(root.val);
root=root.right;
}
return res;
}3.颜色标记法
题解
class ClassNode{
TreeNode node;
boolean flag;
ClassNode(TreeNode node,boolean flag){
this.flag=flag;
this.node=node;
}
}
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res=new ArrayList<>();
Stack<ClassNode> stack =new Stack<>();
if (root==null) return new ArrayList<>();
stack.push(new ClassNode(root,false));
while (!stack.isEmpty()){
ClassNode cn=stack.pop();
if (cn.flag==false){
if (cn.node.right!=null) stack.push(new ClassNode(cn.node.right,false));
stack.push(new ClassNode(cn.node, true));
if (cn.node.left!=null)stack.push(new ClassNode(cn.node.left,false));
}else {
res.add(cn.node.val);
}
}
return res;
}10月20日
只要求形状不同，不要求节点的值。
96. 不同的二叉搜索树
题解
1.动态规划（自底向上，并且前面计算的G[i]后面会用到）
G[n]代表n个节点时的排列组合数。（中间为一个节点j，左边j-1个节点，右边i-j个）
public static int numTrees(int n) {
int G[]=new int[n+1];
G[0]=1;G[1]=1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <=i; j++) {
G[i]+=G[j-1]*G[i-j];
}
}
return G[n];
}10月21
98. 验证二叉搜索树
1.中序遍历是顺序的
//中序遍历是顺序的
public boolean isValidBST(TreeNode root) {
boolean flag=true;
List<Integer> list = new ArrayList<>();
inord(root,list);
for (int i = 0; i < list.size()-1; i++) {
for (int j = i+1; j < list.size(); j++) {
if (list.get(i)>=list.get(j)){
flag=false;
break;
}
}
}
return flag;
}
public void inord(TreeNode root,List<Integer> list){
if(root==null){return;}
inord(root.left,list);
list.add(root.val);
inord(root.right,list);
}2.判断当前节点和中序遍历的前一个节点大小
class Solution {
long pre = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
if (root==null) return true;
if (!isValidBST(root.left)){
return false;
}
if (root.val<=pre){
return false;
}
pre=root.val;
return isValidBST(root.right);
}
}101. 对称二叉树
1.递归
public boolean isSymmetric(TreeNode root) {
return check(root,root);
}
public boolean check(TreeNode left,TreeNode right){
if (left==null && right==null)return true;
if (left==null || right==null) return false;
return left.val==right.val && check(left.right,right.left) && check(left.left,right.right);
}2.迭代
Queue 中 add() 和 offer()都是用来向队列添加一个元素。
在容量已满的情况下，add() 方法会抛出IllegalStateException异常，offer() 方法只会返回 false 。Queue使用时要尽量避免Collection的add()和remove()方法，add()和remove()方法在失败的时候会抛出异常。
要使用offer()来加入元素，使用poll()来获取并移出元素。
它们的优点是通过返回值可以判断成功与否， 如果要使用前端而不移出该元素，使用element()或者peek()方法。
public boolean isSymmetric(TreeNode root) {
return check(root,root);
}
public boolean check(TreeNode left, TreeNode right){
Queue<TreeNode> que = new LinkedList<>();
que.offer(right);
que.offer(left);
while(!que.isEmpty()){
right=que.poll();
left=que.poll();
if (right==null && left==null){
continue;
}
if (right==null || left==null || right.val!= left.val){
return false;
}
que.offer(right.right);
que.offer(left.left);
que.offer(right.left);
que.offer(left.right);
}
return true;
}10月22
102. 二叉树的层序遍历
题解
层次遍历可由宽度优先遍历bfs而得。
宽度优先遍历bfs如下：
void bfs(TreeNode root) {
Queue<TreeNode> queue = new ArrayDeque<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
}本题题解：
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> list = new ArrayList<>();
Queue<TreeNode> queue =new ArrayDeque<>();
if (root!=null) queue.offer(root);
while(!queue.isEmpty()){
ArrayList<Integer> leval = new ArrayList<>();
int n=queue.size();
for (int i = 0; i < n; i++) {
TreeNode node =queue.poll();
leval.add(node.val);
if (node.left!=null) {
queue.offer(node.left);
}
if (node.right!=null) {
queue.offer(node.right);//add会抛异常，offer返回false
}
}
list.add(leval);
}
return list;
}补充
deque和queue的区别：
从上图看出，Queue以及Deque都是继承于Collection，Deque是Queue的子接口。
在java中，Queue被定义成单端队列使用，Deque被定义成双端队列使用。
而由于双端队列的定义，Deque可以作为栈或者队列使用，而Queue只能作为队列或者依赖于子类的实现作为堆使用。ArrayDeque通常作为栈或队列使用，但是栈的效率不如LinkedList高。
LinkedList通常作为栈或队列使用，但是队列的效率不如ArrayQueue高。ArrayDeque.add()方法用于在双端队列的末尾添加给定元素。
ArrayDeque.poll() 此方法检索并删除此双端队列表示的队列的头部,如果此双端队列为空,则返回null。
104. 二叉树的最大深度
题解
1.dfs深度优先遍历
//dfs深度优先遍历
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
} else {
int leftHeight = maxDepth(root.left);
int rightHeight = maxDepth(root.right);
return Math.max(leftHeight, rightHeight) + 1;
}
}2. 层次遍历
//输出上题层次遍历的size即可
public int maxDepth(TreeNode root) {
List<List<Integer>> list = new ArrayList<>();
Queue<TreeNode> queue =new ArrayDeque<>();
if (root==null) return 0;
queue.add(root);
while(!queue.isEmpty()){
List<Integer> level = new ArrayList<>();
int n=queue.size();
for (int i = 0; i < n; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left!=null) {
queue.add(node.left);
}
if (node.right!=null) {
queue.add(node.right);
}
}
list.add(level);
}
return list.size();
}3.根据bfs不存储最终结果，只输出高度
public int maxDepth(TreeNode root) {
int hight =0;
Queue<TreeNode> queue =new ArrayDeque<>();
if (root==null) return 0;
queue.add(root);
while(!queue.isEmpty()){
int n =queue.size();
while(n>0){
TreeNode node = queue.poll();
if (node.left!=null) {
queue.add(node.left);
}
if (node.right!=null) {
queue.add(node.right);
}
n--;
}
hight++;
}
return hight;
}10月24日
105. 从前序与中序遍历序列构造二叉树
题解
HashMap<Integer, Integer> map = new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
int n = preorder.length;
//为了定位root所在位置
for (int i = 0; i < n; i++) {
map.put(inorder[i], i);
}
return mybuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
}
public TreeNode mybuildTree(int[] preorder, int[] inorder, int pre_left, int pre_right, int in_left, int in_right) {
if (pre_left > pre_right) {
return null;
}
//1.找到root后，在inorder中找到索引，得到左子树长度len=(中序root定位序号-left边界) 右子树preorder[root定位+1,root+len+1]，就可以分开左右子树
//前序的第一个就是根节点
int pre_root = pre_left;
int in_root = map.get(preorder[pre_root]);
TreeNode root = new TreeNode(preorder[pre_root]);
int leftTree_len = in_root - in_left;
//2.使用递归，将前序和中序传递(前序中序都不算根节点)，此处pre_left 换为pre_root 也可
root.left = mybuildTree(preorder, inorder, pre_left + 1, pre_left + leftTree_len, in_left, in_root - 1);
root.right = mybuildTree(preorder, inorder, pre_left + leftTree_len + 1, pre_right, in_root + 1, in_right);
return root;
}10月25
114. 二叉树展开为链表
1.递归
前序遍历
public static void flatten(TreeNode root) {
List<TreeNode> list =new ArrayList<>();
preorder(root,list);
int size = list.size();
// TreeNode pre = root;
// TreeNode cur = root;
for (int i = 0; i < size-1; i++) {
TreeNode pre=list.get(i);
TreeNode cur=list.get(i+1);
pre.left=null;
pre.right=cur;
}
}
public static void preorder(TreeNode root,List<TreeNode> list) {
if (root==null){
return;
}
list.add(root);
preorder(root.left,list);
preorder(root.right,list);
}2.迭代
//poll:将首个元素从队列中弹出,如果队列是空的,就返回null
// peek:查看首个元素,不会移除首个元素
public static void flatten(TreeNode root) {
List<TreeNode> list = new ArrayList<>();
Deque<TreeNode> stack=new LinkedList<TreeNode>();
TreeNode node = root;
while (node!=null || !stack.isEmpty()){
while (node!=null){
list.add(node);
stack.push(node);
node=node.left;
}
node =stack.poll();//pop()
node=node.right;
}
int size=list.size();
for (int i = 0; i < size-1; i++) {
TreeNode pre =list.get(i);
TreeNode cur =list.get(i+1);
pre.left=null;
pre.right=cur;
}
}121. 买卖股票的最佳时机
public int maxProfit(int[] prices) {
int len = prices.length;
int min = prices[0];
int profile = 0;
for (int i = 0; i < len; i++) {
if (prices[i] < min) min = prices[i];
else profile = Math.max(profile, prices[i] - min);
}
return profile;
}11月20日
128. 最长连续序列
方法一：
sort为当前的最长连续序列长度，max为此时最长的连续序列长度。
首先给给数组排序
排序后，看num[i]与num[i+1]的关系。
如果num[i]==num[i+1]，则继续循环
若num[i]+1==num[i+1]，则说明连续，sort++；
否则就是不连续，sort清零
public static int longestConsecutive(int[] nums) {
int sort;
int max;
if (nums.length==0 || nums==null){
return 0;
}else {
sort=1;max=1;
}
Arrays.sort(nums);
for (int i = 0; i < nums.length-1; i++) {
if (nums[i]+1==nums[i+1]){
sort++;
}else if(nums[i]==nums[i+1]){
continue;
}else{
max=Math.max(sort,max);
sort=1;
}
}
return Math.max(sort,max);
}方法二：
题解链接
set集合可以去重
循环当前值时，若set集合中，存在比起小的连续值，则跳过。举例：set集合存在0、1，显然从0开始计算的最大序列长度更长。
public static int longestConsecutive(int[] nums) {
Set<Integer> nums_set = new HashSet<Integer>();
for (int num : nums) {
nums_set.add(num);//去重
}
int max, sort;
if (nums.length==0 || nums==null){
return 0;
}else {
sort=1;max=1;
}
int curNum;
for (int num : nums_set) {
sort=1;
if (nums_set.contains(num - 1)) {
continue;//如果存在比其小的连续值，则跳过
}
curNum = num;
while (nums_set.contains(curNum+1)) {
curNum++;
sort++;
}
max=Math.max(sort,max);
}
return max;
}136. 只出现一次的数字
方法一：位运算
题解
public static int singleNumber(int[] nums) {
int sin=0;
for (int num:nums) {
sin^=num;
}
return sin;
}方法二：
public static int singleNumber(int[] nums) {
Arrays.sort(nums);
for (int i = 0; i < nums.length; i=i+2) {
if (i==nums.length-1){
return nums[i];
}
if (nums[i]!=nums[i+1]){
return nums[i];
}
}
return 0;
}11月22日
139. 单词拆分
题解视频
题解文字参考
题目的含义是：能否将单词字典wordDict中每个word拼凑为s，且wordDict中的每个word可以重复使用。
单词字典wordDict中每个word相当于物品，s相当于背包。向背包中装入物品，并考虑顺序性。
//wordDict中每个word相当于物品，s相当于背包。向背包中装入物品，并考虑顺序性。
public static boolean wordBreak(String s, List<String> wordDict) {
//set去重
Set<String> wordSet=new HashSet<String>(wordDict);
int n=s.length();
boolean[] dp=new boolean[n+1];
dp[0]=true;
for (int i = 1; i < dp.length; i++) {
for (String word:wordSet) {
int len=word.length();
if (i>=len && word.equals(s.substring(i-len,i))){
//装还是不装
dp[i]=dp[i-len]||dp[i];
}
}
}
return dp[n];
}
11月23
141. 环形链表
方法一：哈希表
注意这个有错：
//四个样例未通过
public boolean hasCycle(ListNode head) {
Set<Integer> set =new HashSet<Integer>();
ListNode cur=head;
while (cur!=null){
if (set.contains(cur.val)){
return true;//有环
}else {
set.add(cur.val);
cur=cur.next;
}
}
return false;
}
错误原因：set集合中存储的是Interger类型的，若数值val一样，则视为此节点被访问过。
修改：将set集合存储的类型改为ListNode类型，val相同，但next不同，被视为不同节点。
//set中存储ListNode类型
public boolean hasCycle(ListNode head) {
Set<ListNode> set =new HashSet<ListNode>();
ListNode cur=head;
while (cur!=null){
if (set.contains(cur)){
return true;//有环
}else {
set.add(cur);
cur=cur.next;
}
}
return false;
}方法二：快慢指针
题解链接
public boolean hasCycle(ListNode head) {
if (head==null || head.next==null){
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (fast!=slow){
if (fast==null || fast.next==null){
return false;
}
slow=slow.next;
fast=fast.next.next;
}
return true;
}11月24日
142. 环形链表 II
public ListNode detectCycle(ListNode head) {
Set<ListNode> set = new HashSet<ListNode>();
ListNode cur = head;
while(cur!=null){
if (set.contains(cur)){
return cur;
}
set.add(cur);
cur=cur.next;
}
return null;
}146. LRU 缓存机制
题解链接
public class LRUCache {
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
class DLinkedNode{
int key;int value;
DLinkedNode prev;
DLinkedNode next;
public DLinkedNode(){}
public DLinkedNode(int _key,int _value){
key=_key;
value=_value;
}
}
private Map<Integer,DLinkedNode> cache = new HashMap<Integer,DLinkedNode>();
private int size;
private int capacity;
private DLinkedNode head,tail;
public LRUCache(int capacity) {
this.size=0;
this.capacity=capacity;
//两个哑节点，头部和尾部
head=new DLinkedNode();
tail=new DLinkedNode();
head.next=tail;
tail.prev=head;
}
public int get(int key) {
DLinkedNode node =cache.get(key);
if (node==null){return -1;}
//若key存在，移到头部
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
DLinkedNode node = cache.get(key);
if (node==null){
//若不存在，则先插入链表头部，判断链表长度，若大于容量，则删除尾部元素
DLinkedNode newNode= new DLinkedNode(key,value);
cache.put(key,newNode);//添加进哈希表
addToHead(newNode);//添加至双向链表头部
size++;//链表长度，初始化为0，还有头尾两个哑节点
if (size>capacity){
//如果超出容量，删除双向链表尾部节点
DLinkedNode tail =removeTail();
cache.remove(tail.key);
size--;//链表长度减一
}
} else {
node.value=value;
moveToHead(node);
}
}
private void removeNode(DLinkedNode node) {
node.prev.next=node.next;
node.next.prev=node.prev;
}
private void moveToHead(DLinkedNode node) {
//先删除，再加入至头部
removeNode(node);
addToHead(node);
}
private void addToHead(DLinkedNode newNode) {
head.next.prev=newNode;
newNode.next=head.next;
head.next=newNode;
newNode.prev=head;
}
private DLinkedNode removeTail() {
DLinkedNode res=tail.prev;
removeNode(res);
return res;
}
}
11月25日
148. 排序链表
方法一：将链表转为数组，对数组进行排序，对链表重新赋值。
时间复杂度：O(nlogn)
空间复杂度：O(n)
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; }
}
public ListNode sortList(ListNode head) {
List<Integer> list =new ArrayList<Integer>();
ListNode cur=head;
while (cur!=null){
list.add(cur.val);
cur=cur.next;
}
Object[] arr=list.toArray();
Arrays.sort(arr);
ListNode cu=head;
for (int i = 0; i < arr.length && cu!=null; i++) {
cu.val=(int)arr[i];
cu=cu.next;
}
return head;
}方法二：归并排序（快慢指针）
题解
空间复杂度：O(1)
时间复杂度：O(nlogn)
补充快慢指针：
- 寻找链表中点
起点都为head时，我们可以让快指针一次前进两步，慢指针一次前进一步，当快指针到达链表尽头时，慢指针就处于链表的中间位置。- slow起点为head，fast起点为head.next，当程序结束时，如果链表的长度是奇数时，slow 恰巧停在中点位置；如果长度是偶数，slow 最终的位置是中间偏左；可以利用这个方法去进行归并排序。
- 寻找链表的倒数第k个节点
让快指针先走 k 步，然后快慢指针开始同速前进。这样当快指针走到链表末尾 null 时，慢指针所在的位置就是倒数第 k 个链表节点（假设 k 不会超过链表长度）
参考其他博主：
slow起始点为1，fast起始点是2.如果fast在8，则slow停到了4。（偶数的话在中点左侧）
slow起始点为1，fast起始点是2.如果fast在7，则slow也停到了4。（奇数的话在中点）
public ListNode sortList(ListNode head) {
if (head==null || head.next==null) {return head;}
ListNode slow=head;
ListNode fast=head.next;
while (fast!=null && fast.next!=null){
fast=fast.next.next;
slow=slow.next;
}
ListNode tep=slow.next;//停的位置是中点（或者偶数的左侧）
slow.next=null;
ListNode left=sortList(head);
ListNode right=sortList(tep);
ListNode h=new ListNode(0);
ListNode dummy=h;
//合并
while (left!=null && right!=null){
if (left.val<=right.val){
h.next=left;
left=left.next;
}else {
h.next=right;
right=right.next;
}
h=h.next;
}
h.next=left!=null?left:right;
return dummy.next;
}最后
以上就是负责画笔为你收集整理的HOT100（一）2021.9月4日题解链接的全部内容，希望文章能够帮你解决HOT100（一）2021.9月4日题解链接所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
![[Hoot100] 416. 分割等和子集(中等)[动态规划 0-1背包,背包问题汇总]题目描述题解参考](/uploads/reation/bcimg9.png)
发表评论 取消回复