集团公司网站建设品牌,广州网站制作多少钱,自己怎么开网站,网站优化的学习文章目录 p1.1. 两数之和p2.2. 两数相加p3.3. 无重复字符的最长子串p4. 4.寻找两个正序数组的中位数p5.5. 最长回文子串p7.11. 盛最多水的容器p8.15. 三数之和p9.17. 电话号码的字母组合p10.19. 删除链表的倒数第 N 个结点p11.20. 有效的括号p12.21. 合并两个有序链表p13.22. 括… 文章目录 p1.1. 两数之和p2.2. 两数相加p3.3. 无重复字符的最长子串p4. 4.寻找两个正序数组的中位数p5.5. 最长回文子串p7.11. 盛最多水的容器p8.15. 三数之和p9.17. 电话号码的字母组合p10.19. 删除链表的倒数第 N 个结点p11.20. 有效的括号p12.21. 合并两个有序链表p13.22. 括号生成p14.23.合并 K 个升序链表p15.31. 下一个排列p16.32. 最长有效括号p17.33. 搜索旋转排序数组p18.34. 在排序数组中查找元素的第一个和最后一个位置p19.39. 组合总和p20.42. 接雨水p21.46.全排列p22 48. 旋转图像p24 49. 字母异位词分组p25 53. 最大子数组和p26 55. 跳跃游戏p27 56. 合并区间p28 62. 不同路径p29 64. 最小路径和p20 70. 爬楼梯p31 72. 编辑距离p32 75. 颜色分类p33 76. 最小覆盖子串p34 78. 子集p35 79. 单词搜索p36 84. 柱状图中最大的矩形p37 85. 最大矩形p38 94. 二叉树的中序遍历p39 96. 不同的二叉搜索树p40 98. 验证二叉搜索树p41 101. 对称二叉树p42 102. 二叉树的层序遍历p43 104. 二叉树的最大深度p44 105. 从前序与中序遍历序列构造二叉树p45 114. 二叉树展开为链表p46 121. 买卖股票的最佳时机p47 124. 二叉树中的最大路径和p48 128. 最长连续序列p49136. 只出现一次的数字p50 139. 单词拆分 p1.1. 两数之和
给定一个整数数组 nums 和一个整数目标值 target请你在该数组中找出 和为目标值 target 的那 两个 整数并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。
示例 1
输入nums [2,7,11,15], target 9 输出[0,1] 解释因为 nums[0] nums[1] 9 返回 [0, 1] 。
1、暴力解法
class Solution {public int[] twoSum(int[] nums, int target) {//暴力解法//遍历数组因为答案中不能出现重复元素因此第二层遍历从i1开始for (int i 0; i nums.length - 1; i) {for (int j i 1; j nums.length; j) {if (nums[i] nums[j] target) {return new int[] {i, j};}}}return null;}
}2、哈希表
class Solution {public int[] twoSum(int[] nums, int target) {//哈希表MapInteger, 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中//此处map的key表示数组的值便于后续获取map的value得到数的位置map.put(nums[i], i);}return null;}
}p2.2. 两数相加
给你两个 非空 的链表表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的并且每个节点只能存储 一位 数字。
请你将两个数相加并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外这两个数都不会以 0 开头。 /*** 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 l3 new ListNode(0);//返回的新链表ListNode cur l3;int carry 0;//表示进位while (l1 ! null || l2 ! null) {//如果l1或l2为空设其值为0保证l1 l2是同样的长度相加int x l1 ! null ? l1.val : 0;int y l2 ! null ? l2.val : 0;int sum x y carry;//两数和为两数值加进位值carry sum / 10;//求得当前的进位值sum % 10;//求得当前的两数和cur.next new ListNode(sum);//创建一个新的节点放入新链表cur cur.next;//如果l1 l2不为空指针往后移if (l1 ! null) {l1 l1.next;}if (l2 ! null) {l2 l2.next;}}//如果最后一位的两数相加和是两位数有进位且进位只能是1因此创建节点放入链表中if (carry 1) {cur.next new ListNode(1);}return l3.next;}
}p3.3. 无重复字符的最长子串
给定一个字符串 s 请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”所以其长度为 3。
class Solution {public int lengthOfLongestSubstring(String s) {int N 40000;char[] a new char[s.length()];for (int i 0; i s.length(); i ) {a[i] s.charAt(i);}//记录序列长度int res 0;//记录序列中a[i]的值的个数char[] b new char[N];//双指针遍历i是移动指针j指针用于保证在序列的最左位置使得[j,i]之间的序列不重复for (int i 0, j 0; i s.length(); i ) {b[a[i]] ;//a[i]的值个数1//序列中出现重复值j指针后移while (b[a[i]] 1) {b[a[j]] --;//删除序列中j最初指向的值j ;//j指针后移}//res记录序列的最长长度res Math.max(res, i - j 1);}return res;}
}p4. 4.寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序从小到大数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (mn)) 。
示例 1
输入nums1 [1,3], nums2 [2] 输出2.00000 解释合并数组 [1,2,3] 中位数 2
class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {int i 0, j 0, k 0;double res;int[] newNums new int[nums1.length nums2.length];//新建一个数组表示合并nums1和nums2的有序数组//同时遍历nums1 nums2比较大小将较小的值保存到newNumswhile (i nums1.length j nums2.length) {if (nums1[i] nums2[j]) {newNums[k ] nums1[i ];} else {newNums[k ] nums2[j ];}}//此时nums1数组还有值直接放入newNums后while (i nums1.length) {newNums[k ] nums1[i ];}//此时nums2数组还有值直接放入newNums后while (j nums2.length) {newNums[k ] nums2[j ];}int len newNums.length;//合并数组长度//当合并数组为偶数个时返回值为resif (newNums.length % 2 0) {res (newNums[len / 2 - 1] newNums[len / 2]) / 2.00000;//注意此处要除以2.00000,如果除以2就是double值/int值得到的结果为int不符合条件} else {res newNums[len / 2];}return res;}
}p5.5. 最长回文子串
给你一个字符串 s找到 s 中最长的回文子串。
示例 1
输入s “babad” 输出“bab” 解释“aba” 同样是符合题意的答案。
public class Solution {public String longestPalindrome(String s) {int len s.length();if (len 2) {return s;}int maxLen 1;int begin 0;// dp[i][j] 表示 s[i..j] 是否是回文串boolean[][] dp new boolean[len][len];// 初始化所有长度为 1 的子串都是回文串for (int i 0; i len; i) {dp[i][i] true;}char[] charArray s.toCharArray();// 递推开始// 先枚举子串长度for (int L 2; L len; L) {// 枚举左边界左边界的上限设置可以宽松一些for (int i 0; i len; i) {// 由 L 和 i 可以确定右边界即 j - i 1 L 得int j L i - 1;// 如果右边界越界就可以退出当前循环if (j len) {break;}if (charArray[i] ! charArray[j]) {dp[i][j] false;} else {if (j - i 3) {dp[i][j] true;} else {dp[i][j] dp[i 1][j - 1];}}// 只要 dp[i][L] true 成立就表示子串 s[i..L] 是回文此时记录回文长度和起始位置if (dp[i][j] j - i 1 maxLen) {maxLen j - i 1;begin i;}}}return s.substring(begin, begin maxLen);}
}p7.11. 盛最多水的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明你不能倾斜容器。
class Solution {public int maxArea(int[] height) {//双指针int res 0, i 0, j height.length - 1;while (i j) {res height[i] height[j] ?Math.max(res, (j - i) * height[i]):Math.max(res, (j - i) * height[j--]);}return res;}
}p8.15. 三数之和
给你一个包含 n 个整数的数组 nums判断 nums 中是否存在三个元素 abc 使得 a b c 0 请你找出所有和为 0 且不重复的三元组。
注意答案中不可以包含重复的三元组。
示例 1
输入nums [-1,0,1,2,-1,-4] 输出[[-1,-1,2],[-1,0,1]] 示例 2
输入nums [] 输出[] 示例 3
输入nums [0] 输出[]
class Solution {public ListListInteger threeSum(int[] nums) {ListListInteger res new ArrayList();//1.初始判断如果nums为空或小于三个数 直接返回if (nums null || nums.length 3) {return res;}//2.对数组进行排序Arrays.sort(nums);//3.开始遍历 首先固定一个数nums[i],再用两个指针分别指向nums[i]后面的两端计算三数之和是否为0for (int i 0; i nums.length; i) {if (nums[i] 0) {//如果当前数字大于0则三数之和一定大于0所以结束循环break;}if (i 0 nums[i] nums[i - 1]) { // 去重continue;}int L i 1;int R nums.length - 1;while (L R) {int sum nums[i] nums[L] nums[R];if (sum 0) {res.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 res;}
}p9.17. 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。
示例 1
输入digits “23” 输出[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”] 示例 2
输入digits “” 输出[]
class Solution {ArrayListString res new ArrayList();//数字与字母的对应关系放在map中MapString, String phoneMap new HashMapString, String() {{put(2, abc);put(3, def);put(4, ghi);put(5, jkl);put(6, mno);put(7, pqrs);put(8, tuv);put(9, wxyz);}};public ListString letterCombinations(String digits) {if (digits.length() ! 0)addLetter(, digits);return res;}public void addLetter(String letter, String nextLetter) {if (nextLetter.length() 0) {res.add(letter);} else {String digit String.valueOf(nextLetter.charAt(0));String letters phoneMap.get(digit);for (int i 0; i letters.length(); i) {String c String.valueOf(letters.charAt(i));addLetter(letter c, nextLetter.substring(1));}}}
}p10.19. 删除链表的倒数第 N 个结点
给你一个链表删除链表的倒数第 n 个结点并且返回链表的头结点。
示例1
输入head [1,2,3,4,5], n 2
输出[1,2,3,5]示例 2
输入head [1], 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 removeNthFromEnd(ListNode head, int n) {ListNode pre new ListNode(0);pre.next head;ListNode p pre, q pre;//p指针先走n步while (n ! 0) {p p.next;n --;}//p q指针同时遍历当p指针到达链表尾部时停止此时q指针指向倒数第n-1个结点while (p.next ! null) {p p.next;q q.next;}//删除倒数第n个结点q.next q.next.next;return pre.next;}
}p11.20. 有效的括号
给定一个只包括 ‘(’‘)’‘{’‘}’‘[’‘]’ 的字符串 s 判断字符串是否有效。
有效字符串需满足
左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。
示例 1
输入s “()” 输出true
class Solution {public boolean isValid(String s) {//如果字符串为空返回trueif (s.isEmpty()) {return true;}StackCharacter stack new StackCharacter();//创建一个栈//遍历每个字符如果是左括号就其对应的右括号入栈如果栈不为空且此时为右括号则出栈看是否匹配for (int i 0; i s.length(); i ) {char c s.charAt(i);if (c () {stack.push());} else if (c {) {stack.push(});} else if (c [) {stack.push(]);} else if (stack.isEmpty() || c ! stack.pop()) {return false;}}//如果最后栈为空说明恰好匹配返回true否则返回falsereturn stack.isEmpty();}
}p12.21. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例1
输入l1 [1,2,4], l2 [1,3,4]
输出[1,1,2,3,4,4]/*** 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 mergeTwoLists(ListNode list1, ListNode list2) {//双指针法此方法与合并两个有序数组类似ListNode list3 new ListNode(-1), p list3;//两个链表同时都有数值比较将较小的值放入新链表中while (list1 ! null list2 ! null) {if (list1.val list2.val) {p.next list1;list1 list1.next;} else {p.next list2;list2 list2.next;}p p.next;}//如果最后只有list1或者list2其中一个链表有值将p指向有值的链表p.next list1 null ? list2 : list1;return list3.next;}
}p13.22. 括号生成
数字 n 代表生成括号的对数请你设计一个函数用于能够生成所有可能的并且 有效的 括号组合。
示例 1
输入n 3 输出[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]
class Solution {public ListString generateParenthesis(int n) {ListString res new ArrayList();//存放返回字符串List//初始条件判断if (n 0) {return res;}dfs(, n, n, res);return res;}public void dfs(String curStr, int left, int right, ListString res) {//递归终止条件左右两边括号数为0时结算if (left 0 right 0) {res.add(curStr);return;}//剪枝左边括号数大于右边if (left right) {return;}//进行深度优先遍历对应加上左、右括号if (left 0) {dfs(curStr (, left - 1, right, res);}if (right 0) {dfs(curStr ), left, right - 1, res);}}
}p14.23.合并 K 个升序链表
p15.31. 下一个排列
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
例如arr [1,2,3] 以下这些都可以视作 arr 的排列[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地如果数组的所有排列根据其字典顺序从小到大排列在一个容器中那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列那么这个数组必须重排为字典序最小的排列即其元素按升序排列。
例如arr [1,2,3] 的下一个排列是 [1,3,2] 。类似地arr [2,3,1] 的下一个排列是 [3,1,2] 。而 arr [3,2,1] 的下一个排列是 [1,2,3] 因为 [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 nums 找出 nums 的下一个排列。
必须** 原地 **修改只允许使用额外常数空间。
class Solution {public void nextPermutation(int[] nums) {int len nums.length;//1.从后往前找第一个后大于前的位置 nums[i]nums[i-1]for (int i len - 1; i 0; i --) {if (nums[i] nums[i - 1]) {//2.对i之后的元素排序 [i, len)左闭右开Arrays.sort(nums, i, len);//3.排序后找到[i, len)中第一个大于i-1位置的元素并与其交换返回结果for (int j i; j len; j ) {if (nums[j] nums[i - 1]) {int temp nums[j];nums[j] nums[i - 1];nums[i - 1] temp;return;}}}}//最后[3,2,1]的情况下一个排列就是按从后小到大排列Arrays.sort(nums);return;}
}
p16.32. 最长有效括号
p17.33. 搜索旋转排序数组
整数数组 nums 按升序排列数组中的值 互不相同 。
在传递给函数之前nums 在预先未知的某个下标 k0 k nums.length上进行了 旋转使数组变为 [nums[k], nums[k1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]下标 从 0 开始 计数。例如 [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target 如果 nums 中存在这个目标值 target 则返回它的下标否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
class Solution {public int search(int[] nums, int target) {//使用二分法搜索//将旋转数组分为两段有序数组分别使用二分法查找int left 0, right nums.length - 1;while(left right){// if(nums[left] target) return left;// if(nums[right] target) return right;int mid left (right - left) / 2;if(nums[mid] target) return mid;// 右边有序if(nums[mid] nums[right]){// 目标值在右边if(target nums[mid] target nums[right]){left mid 1;// 目标值在左边}else{right mid - 1;}// 左边有序}else{// 目标值在左边if(target nums[left] target nums[mid]){right mid - 1;// 目标值在右边}else{left mid 1;}}}return -1;}
}p18.34. 在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
class Solution {public int[] searchRange(int[] nums, int target) {int[] res {-1, -1};//初始条件判断if (nums.length 0) {return res;}//1.找 target 的第一个位置int l 0, r nums.length - 1;while (l r) {int mid l r 1;if (nums[mid] target) {r mid;} else {l mid 1;}}//没找到目标值targetif (nums[l] ! target) {return res;} else {//确定开始位置lres[0] l;//2.找 x 的最后一个位置l 0;r nums.length - 1;while (l r) {int mid l r 1 1;if (nums[mid] target) {l mid;} else {r mid - 1;}}//确定最后位置rres[1] r;}return res;}
}p19.39. 组合总和
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target 找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同则两种组合是不同的。
对于给定的输入保证和为 target 的不同组合数少于 150 个。
示例 1
输入candidates [2,3,6,7], target 7
输出[[2,2,3],[7]]
解释
2 和 3 可以形成一组候选2 2 3 7 。注意 2 可以使用多次。
7 也是一个候选 7 7 。
仅有这两种组合。class Solution {ListListInteger res new ArrayList();//存放结果集ListInteger path new ArrayList();//存放符合条件的结果public ListListInteger combinationSum(int[] candidates, int target) {//剪枝需要先排序Arrays.sort(candidates);backtracking(candidates, target, 0, 0);return res;}void backtracking(int[] candidates, int target, int sum, int startIndex) {//终止条件:1、sum target终止if (sum target) {return;}//2、sum target满足题目要求if (sum target) {res.add(new ArrayList(path));return;}//剪枝如果sum candidates[i] target就提前退出并且剪枝需要排序for (int i startIndex; i candidates.length sum candidates[i] target; i ) {//处理节点sum candidates[i];path.add(candidates[i]);//递归backtracking(candidates, target, sum, i);//注意此处不用取i1,因为所取的元素是可以重复的//回溯sum - candidates[i];path.remove(path.size() - 1);}}
}p20.42. 接雨水 class Solution {public int trap(int[] height) {int res 0, n height.length;// leftMax:左边最高 rightMax右边最高int[] leftMax new int[n], rightMax new int[n];leftMax[0] height[0];rightMax[n - 1] height[n - 1];// 找左边最高for (int i 1; i n; i ) {leftMax[i] Math.max(leftMax[i - 1], height[i]);}// 找右边最高for (int i n - 2; i 0; i --) {rightMax[i] Math.max(rightMax[i 1], height[i]);}// 遍历算接水量for (int i 0; i n; i ) {// 两端较小的当前高度就会接水int min Math.min(leftMax[i], rightMax[i]);if (min height[i]) {res (min - height[i]);}}return res;}
}p21.46.全排列
给定一个不含重复数字的数组 nums 返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1
输入nums [1,2,3]
输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]class Solution {public ListListInteger permute(int[] nums) {ListListInteger res new ArrayList();int[] visited new int[nums.length];ListInteger path new ArrayList();dfs(nums, res, path, visited);return res;}public void dfs(int[] nums, ListListInteger res, ListInteger path, int[] visited) {if (path.size() nums.length) {res.add(new ArrayList(path));return;}for (int i 0; i nums.length; i ) {if (visited[i] 1) continue; // 已被访问// 未访问visited[i] 1;path.add(nums[i]);dfs(nums, res, path, visited);visited[i] 0;path.remove(path.size() - 1);}}
}p22 48. 旋转图像
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在** 原地** 旋转图像这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
示例 1 class Solution {public void rotate(int[][] matrix) {//原地旋转int n matrix.length;//四个点刚好旋转一圈找到四个点的位置关系用临时变量来保存for (int i 0; i n / 2; i) {for (int j 0; j (n 1) / 2; j) {int temp matrix[i][j];matrix[i][j] matrix[n - j - 1][i];matrix[n - j - 1][i] matrix[n - i - 1][n - j - 1];matrix[n - i - 1][n - j - 1] matrix[j][n - i - 1];matrix[j][n - i - 1] temp;}}}
}p24 49. 字母异位词分组
给你一个字符串数组请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例 1:
输入: strs [eat, tea, tan, ate, nat, bat]
输出: [[bat],[nat,tan],[ate,eat,tea]]class Solution {public ListListString groupAnagrams(String[] strs) {MapString, ArrayListString map new HashMap();for (int i 0; i strs.length ; i) {char[] chars strs[i].toCharArray();Arrays.sort(chars);String key String.valueOf(chars);if (!map.containsKey(key)) {map.put(key, new ArrayList());}map.get(key).add(strs[i]);}return new ArrayList(map.values());}
}p25 53. 最大子数组和
给你一个整数数组 nums 请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。
子数组 是数组中的一个连续部分。
示例 1
输入nums [-2,1,-3,4,-1,2,1,-5,4]
输出6
解释连续子数组 [4,-1,2,1] 的和最大为 6 class Solution {public int maxSubArray(int[] nums) {int sum 0, res Integer.MIN_VALUE;for (int i 0; i nums.length; i ) {sum nums[i];if (sum res) res sum; // res保存当前和的最大值if (sum 0) sum 0; // 如果求和0则舍去前面的序列重新计算}return res;}
}p26 55. 跳跃游戏
给你一个非负整数数组 nums 你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标如果可以返回 true 否则返回 false 。
示例 1
输入nums [2,3,1,1,4]
输出true
解释可以先跳 1 步从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。class Solution {public boolean canJump(int[] nums) {if (nums.length 1) return true;int coverRange 0;for (int i 0; i coverRange; i ) { // 注意此处是coverRange Math.max(coverRange, i nums[i]);if (coverRange nums.length - 1) {return true; // 当覆盖范围能够到达数组尾端即可}}return false;}
}p27 56. 合并区间
以数组 intervals 表示若干个区间的集合其中单个区间为 intervals[i] [starti, endi] 。请你合并所有重叠的区间并返回 一个不重叠的区间数组该数组需恰好覆盖输入中的所有区间 。
示例 1
输入intervals [[1,3],[2,6],[8,10],[15,18]]
输出[[1,6],[8,10],[15,18]]
解释区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].class Solution {public int[][] merge(int[][] intervals) {// 先按照区间起始位置排序Arrays.sort(intervals, (v1, v2) - v1[0] - v2[0]);// 遍历区间int[][] res new int[intervals.length][2];int idx -1;for (int[] interval: intervals) {// 如果结果数组是空的或者当前区间的起始位置 结果数组中最后区间的终止位置// 则不合并直接将当前区间加入结果数组。if (idx -1 || interval[0] res[idx][1]) {res[idx] interval;} else {// 反之将当前区间合并至结果数组的最后区间res[idx][1] Math.max(res[idx][1], interval[1]);}}return Arrays.copyOf(res, idx 1);}
}p28 62. 不同路径
一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为 “Start” 。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish” 。
问总共有多少条不同的路径 /*** 思路DP 优化空间O(n) 利用滚动数组*/
var uniquePaths function (m, n) {// 定义状态数组:dp,初始化为1const dp Array.from({length: n}, () 1)for (let i 1; i m; i) {for (let j 1; j n; j) {dp[j] dp[j - 1]}}return dp[n - 1]
};p29 64. 最小路径和
给定一个包含非负整数的 *m* x *n* 网格 grid 请找出一条从左上角到右下角的路径使得路径上的数字总和为最小。
**说明**每次只能向下或者向右移动一步。
class Solution {public int minPathSum(int[][] grid) {int m grid.length, n grid[0].length;for (int i 0; i m; i ) {for (int j 0; j n; j ) {if (i 0 j 0) continue;else if (i 0) grid[i][j] grid[i][j - 1];else if (j 0) grid[i][j] grid[i - 1][j];else grid[i][j] Math.min(grid[i - 1][j], grid[i][j - 1]);}}return grid[m - 1][n - 1];}
}p20 70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢
示例 1
输入n 2
输出2
解释有两种方法可以爬到楼顶。
1. 1 阶 1 阶
2. 2 阶class Solution {public int climbStairs(int n) {if (n 2) return n;int[] dp new int[n 1];dp[1] 1;dp[2] 2;for (int i 3; i n; i ) {// 到达n阶有两种方法最后走一步dp[i - 1];最后走两步dp[i - 2]dp[i] dp[i - 1] dp[i - 2];}return dp[n];}
}p31 72. 编辑距离
给你两个单词 word1 和 word2 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作
插入一个字符删除一个字符替换一个字符
示例 1
输入word1 horse, word2 ros
输出3
解释
horse - rorse (将 h 替换为 r)
rorse - rose (删除 r)
rose - ros (删除 e)class Solution {public int minDistance(String word1, String word2) {int n word1.length(), m word2.length();int[][] dp new int[n 1][m 1];word1 word1;word2 word2;// 若a长度为ib长度为0则需要进行i次删除操作for (int i 0; i n; i ) {dp[i][0] i;} // 若a长度为0b长度为i则需要进行i次添加操作for (int i 0; i m; i) {dp[0][i] i;}for (int i 1; i n; i ) {for (int j 1; j m; j ) {// 添加和删除dp[i][j] Math.min(dp[i - 1][j], dp[i][j - 1]) 1;// 修改if (word1.charAt(i) word2.charAt(j)) {dp[i][j] Math.min(dp[i][j], dp[i - 1][j - 1]);} else {dp[i][j] Math.min(dp[i][j], dp[i - 1][j - 1] 1);}}}return dp[n][m];}
}p32 75. 颜色分类
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums **原地**对它们进行排序使得相同颜色的元素相邻并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。
示例 1
输入nums [2,0,2,1,1,0]
输出[0,0,1,1,2,2]class Solution {public void sortColors(int[] nums) {int p0 0, p1 0;for (int i 0; i nums.length; i) {if (nums[i] 1) {int temp nums[i];nums[i] nums[p1];nums[p1] temp;p1;} else if (nums[i] 0) {int temp nums[i];nums[i] nums[p0];nums[p0] temp;if (p0 p1) {temp nums[i];nums[i] nums[p1];nums[p1] temp;}p0;p1;}}}
}p33 76. 最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串则返回空字符串 。
注意
对于 t 中重复字符我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。如果 s 中存在这样的子串我们保证它是唯一的答案。
示例 1
输入s ADOBECODEBANC, t ABC
输出BANC
解释最小覆盖子串 BANC 包含来自字符串 t 的 A、B 和 C。class Solution {public String minWindow(String s, String t) {//创建两个哈希表hw ht用于记录每个字符的出现次数,hw是记录滑动窗口的字符串ht是记录t字符串HashMapCharacter, Integer hw new HashMap(), ht new HashMap();int cnt 0;String res ;//初始化htfor (int i 0; i t.length(); i ) {char ct t.charAt(i);//判断字符出现的次数如果没出现过就设为1出现过就1ht.put(ct, ht.containsKey(ct) ? ht.get(ct) 1 : 1);}for (int i 0, j 0; i s.length(); i ) {//初始化hwchar cs s.charAt(i);hw.put(cs, hw.containsKey(cs) ? hw.get(cs) 1 : 1);//如果ht中有当前字符同时滑动窗口中字符数t中字符数说明该字符无效i指针后移if (ht.containsKey(cs) hw.get(cs) ht.get(cs)) {cnt ;}//1)t中没有该字符2)滑动窗口中字符数t中该字符数 说明该字符是有效的需要将该字符加入t中while (j i (! ht.containsKey(s.charAt(j)) || hw.get(s.charAt(j)) ht.get(s.charAt(j)))) {hw.put(s.charAt(j), hw.get(s.charAt(j )) - 1);}//更新resi-j1为长度if (cnt t.length() (i - j 1 res.length() || res.length() 1)) {res s.substring(j, i 1);}}return res;}
}p34 78. 子集
给你一个整数数组 nums 数组中的元素 互不相同 。返回该数组所有可能的子集幂集。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1
输入nums [1,2,3]
输出[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]集合的二进制
class Solution {public ListListInteger subsets(int[] nums) {ListListInteger res new ArrayList();int n nums.length;//1n 2^n 枚举2^n个数for (int i 0; i (1 n); i ) {ListInteger temp new ArrayList();//每个数枚举n次for (int j 0; j n; j ) {//判断这个数的第j位是否为1判断是否选if ((i j 1) 1) {temp.add(nums[j]);//可选就加入temp中}}res.add(temp);}return res;}
}回溯
class Solution {ListListInteger res new ArrayList();ListInteger path new ArrayListInteger();public ListListInteger subsets(int[] nums) {backtracking(nums, 0);return res;}void backtracking(int[] nums, int startIndex) {res.add(new ArrayList(path));//收集子集if (startIndex nums.length) {//终止条件return;}for (int i startIndex; i nums.length; i ) {path.add(nums[i]);//处理节点backtracking(nums, i 1);//递归注意从i1开始元素不重复path.remove(path.size() - 1);//回溯撤销处理的节点}}
}p35 79. 单词搜索
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中返回 true 否则返回 false 。
单词必须按照字母顺序通过相邻的单元格内的字母构成其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。 class Solution {static int n, m;//网格的长、宽static int[] dx new int[]{0,-1,0,1};//方向数组static int[] dy new int[]{-1,0,1,0};public boolean exist(char[][] board, String word) {n board.length;m board[0].length;//遍历网格for (int i 0; i n; i ) {for (int j 0; j m; j ) {//将单词的第一个字符开始与网格的字符进行匹配匹配成功进行下一个匹配即进入dfs全部匹配成功返回trueif (board[i][j] word.charAt(0)) {if (dfs(board, word, 0, i, j)) {return true;}}}}return false;}/*** 判断单词的字符是否与网格的字符匹配* param board 网格* param word 单词* param depth 单词的第depth个字符* param x x y表示起始点* param y* return 匹配结果*/boolean dfs(char[][] board, String word, int depth, int x, int y) {//递归退出条件:当前位置上的字符与word的对应匹配的字符不相等返回falseif (board[x][y] ! word.charAt(depth)) {return false;}//匹配到达了word的最后一个字符返回trueif (word.length() - 1 depth) {return true;}char c board[x][y];//记录当前位置的字符便于后面使用之后恢复现场board[x][y] .;//每个字符需要保证是不重复的使用之后需要被标记//四个方向u v用于记录网格中往哪个方向移动for (int i 0; i 4; i ) {int u x dx[i];int v y dy[i];//u 0 || u n || v 0 || v m:判断当前位置是否越界//board[u][v] .:判断当前位置的字符是否被使用过if (u 0 || u n || v 0 || v m || board[u][v] .) {continue;//部分和条件跳出当期循环}if (dfs(board, word, depth 1, u, v)) {return true;}}board[x][y] c;//恢复现场return false;}
}p36 84. 柱状图中最大的矩形
给定 n 个非负整数用来表示柱状图中各个柱子的高度。每个柱子彼此相邻且宽度为 1 。
求在该柱状图中能够勾勒出来的矩形的最大面积。 class Solution {public int largestRectangleArea(int[] heights) {int n heights.length;//left:存放从当前元素位置往做左直到比当前元素小//right:存放从当前元素位置往右直到比当前元素小或到达右边界//用数组表示队列int[] stk new int[n], left new int[n], right new int[n];int tt -1;//初始时栈指针 -1表示栈为空//从左往右遍历:找左边第一个小于当前位置的元素for (int i 0; i n; i ) {//如果栈不为空同时栈顶元素当前元素出栈保证栈是一个单调递增的序列while (tt ! -1 heights[stk[tt]] heights[i]) {tt --;//出栈}//如果栈不为空记录栈顶元素否则为-1left[i] tt ! -1 ? stk[tt] : -1;//当前元素入栈stk[ tt] i;}//注意清空栈tt -1;//从右往左遍历找右边第一个小于当前位置的元素没有则是右边界for (int i n - 1; i 0; i --) {while (tt ! -1 heights[stk[tt]] heights[i]) {tt --;}right[i] tt ! -1 ? stk[tt] : n;stk[ tt] i;}int res 0;//遍历上边界找面积最大值for (int i 0; i n; i ) {res Math.max(res, heights[i] * (right[i] - left[i] - 1));}return res;}
}p37 85. 最大矩形
给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵找出只包含 1 的最大矩形并返回其面积。 class Solution {public int maximalRectangle(char[][] matrix) {if (matrix.length 0 || matrix[0].length 0) {return 0;}int n matrix.length, m matrix[0].length;int[][] h new int[n][m];for (int i 0; i n; i ) {for (int j 0; j m; j ) {if (matrix[i][j] 1) {if (i ! 0) {h[i][j] 1 h[i - 1][j];} else {h[i][j] 1;}}}}int res 0;for (int i 0; i n; i ) {res Math.max(res, largestRectangleArea(h[i]));}return res;}public int largestRectangleArea(int[] heights) {int n heights.length;//left:存放从当前元素位置往做左直到比当前元素小//right:存放从当前元素位置往右直到比当前元素小或到达右边界//用数组表示栈int[] stk new int[n], left new int[n], right new int[n];int tt -1;//初始时栈指针 -1表示栈为空//从左往右遍历:找左边第一个小于当前位置的元素for (int i 0; i n; i ) {//如果栈不为空同时栈顶元素当前元素出栈保证栈是一个单调递增的序列while (tt ! -1 heights[stk[tt]] heights[i]) {tt --;//出栈}//如果栈不为空记录栈顶元素否则为-1left[i] tt ! -1 ? stk[tt] : -1;//当前元素入栈stk[ tt] i;}//注意清空栈tt -1;//从右往左遍历找右边第一个小于当前位置的元素没有则是右边界for (int i n - 1; i 0; i --) {while (tt ! -1 heights[stk[tt]] heights[i]) {tt --;}right[i] tt ! -1 ? stk[tt] : n;stk[ tt] i;}int res 0;//遍历上边界找面积最大值for (int i 0; i n; i ) {res Math.max(res, heights[i] * (right[i] - left[i] - 1));}return res;}
}p38 94. 二叉树的中序遍历
栈
/*** 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 inorderTraversal(TreeNode root) {ListInteger res new ArrayList();StackTreeNode s new Stack();while (root ! null || !s.isEmpty()) {if (root ! null) {s.push(root);root root.left;} else {root s.pop();res.add(root.val);root root.right;}}return res;}
}递归
class Solution {//递归public ListInteger inorderTraversal(TreeNode root) {ListInteger res new ArrayList();dfs(root, res);return res;}void dfs(TreeNode root, ListInteger res) {if (root null) {return;}dfs(root.left, res);res.add(root.val);dfs(root.right, res);}
}p39 96. 不同的二叉搜索树
给你一个整数 n 求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种返回满足题意的二叉搜索树的种数。 class Solution {public int numTrees(int n) {int[] dp new int[n 1];dp[0] 1; // 初始条件for (int i 1; i n; i ) {for (int j 1; j i; j ) {// 动态方程 left*rightdp[i] dp[j - 1] * dp[i - j];}}return dp[n];}
}p40 98. 验证二叉搜索树
给你一个二叉树的根节点 root 判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下
节点的左子树只包含 小于 当前节点的数。节点的右子树只包含 大于 当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。
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); // 右}
}p41 101. 对称二叉树
给你一个二叉树的根节点 root 检查它是否轴对称。
递归
class Solution {public boolean isSymmetric(TreeNode root) {if (root null) return true;return compare(root.left, root.right);}boolean compare(TreeNode left, TreeNode right) {// 判断节点为空的情况if (left null right ! null) return false;else if (left ! null right null) return false;else if (left null right null) return true;// 判断节点不为空的情况else if (left.val ! right.val) return false;// 节点不为空且节点值相等递归遍历else return compare(left.left, right.right) compare(left.right, right.left);}
}迭代
class Solution {public boolean isSymmetric(TreeNode root) {QueueTreeNode q new LinkedList();if (root null) return true;q.add(root.left);q.add(root.right);while (!q.isEmpty()) {TreeNode leftNode q.poll(), rightNode q.poll();if (leftNode null rightNode null) continue;// false情况合集if (leftNode null || rightNode null || leftNode.val ! rightNode.val) return false;q.add(leftNode.left);q.add(rightNode.right);q.add(leftNode.right);q.add(rightNode.left);}return true;}
}p42 102. 二叉树的层序遍历
给你二叉树的根节点 root 返回其节点值的 层序遍历 。 即逐层地从左到右访问所有节点
迭代
class Solution {public ListListInteger levelOrder(TreeNode root) {ListListInteger res new ArrayList();QueueTreeNode q new ArrayDeque();// 1. 处理根节点if (root ! null) q.add(root);// 2.遍历每层while (!q.isEmpty()) {int n q.size(); // 记录当层节点数ListInteger level new ArrayList(); // 记录当层节点值// 处理当层节点1.出栈并访问 2.左节点入队 3.右节点入队 for (int i 0; i n; i ) {TreeNode node q.poll();level.add(node.val);if (node.left ! null) q.add(node.left);if (node.right ! null) q.add(node.right);}res.add(level);}return res;}
}p43 104. 二叉树的最大深度
给定一个二叉树 root 返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
递归
class Solution {public int maxDepth(TreeNode root) {if (root null) return 0;else {int left maxDepth(root.left);int right maxDepth(root.right);return Math.max(left, right) 1;}}
}层次遍历
class Solution {public int maxDepth(TreeNode root) {int level 0;QueueTreeNode q new LinkedList();if (root ! null) q.add(root);while (!q.isEmpty()) {int n q.size();for (int i 0; i n; i ) {TreeNode node q.poll();if (node.left ! null) q.add(node.left);if (node.right ! null) q.add(node.right);}level ;}return level;}
}p44 105. 从前序与中序遍历序列构造二叉树
给定两个整数数组 preorder 和 inorder 其中 preorder 是二叉树的先序遍历 inorder 是同一棵树的中序遍历请构造二叉树并返回其根节点。
class Solution {// 前根左右 中左根右MapInteger, Integer map;public TreeNode buildTree(int[] preorder, int[] inorder) {map new HashMap();for (int i 0; i inorder.length; i ) {map.put(inorder[i], i);}return findNode(preorder, 0, preorder.length, inorder, 0, inorder.length);}public TreeNode findNode(int[] preorder, int preBegin, int preEnd, int[] inorder, int inBegin, int inEnd) {if (preBegin preEnd || inBegin inEnd) return null;int rootIndex map.get(preorder[preBegin]);TreeNode root new TreeNode(inorder[rootIndex]);int lenOfleft rootIndex - inBegin;root.left findNode(preorder, preBegin 1, preBegin 1 lenOfleft, inorder, inBegin, rootIndex);root.right findNode(preorder, preBegin 1 lenOfleft, preEnd, inorder, rootIndex 1, inEnd);return root;}
}p45 114. 二叉树展开为链表
给你二叉树的根结点 root 请你将它展开为一个单链表
展开后的单链表应该同样使用 TreeNode 其中 right 子指针指向链表中下一个结点而左子指针始终为 null 。展开后的单链表应该与二叉树 先序遍历 顺序相同。 p46 121. 买卖股票的最佳时机
给定一个数组 prices 它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润返回 0 。
示例 1
输入[7,1,5,3,6,4]
输出5
解释在第 2 天股票价格 1的时候买入在第 5 天股票价格 6的时候卖出最大利润 6-1 5 。注意利润不能是 7-1 6, 因为卖出价格需要大于买入价格同时你不能在买入前卖出股票class Solution {public int maxProfit(int[] prices) {int res 0, min Integer.MAX_VALUE;for (int i 0; i prices.length; i ) {res Math.max(res, prices[i] - min);min Math.min(min, prices[i]);}return res;}
}p47 124. 二叉树中的最大路径和
二叉树中的 路径 被定义为一条节点序列序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root 返回其 最大路径和 。
class Solution {int res Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {dfs(root);return res;}public int dfs (TreeNode root) {if (root null) return 0;int left Math.max(0, dfs(root.left));int right Math.max(0, dfs(root.right));res Math.max(res, left root.val right);return root.val Math.max(left, right);}
}p48 128. 最长连续序列
给定一个未排序的整数数组 nums 找出数字连续的最长序列不要求序列元素在原数组中连续的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1
输入nums [100,4,200,1,3,2]
输出4
解释最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。class Solution {public int longestConsecutive(int[] nums) {SetInteger set new HashSet();for(int num : nums) set.add(num);int res 0;for(int i 0; i nums.length; i) {int x nums[i];if(!set.contains(x - 1)) {int y x;while(set.contains(y 1)) y;res Math.max(res, y - x 1);}}return res;}
}p49136. 只出现一次的数字
给你一个 非空 整数数组 nums 除了某个元素只出现一次以外其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题且该算法只使用常量额外空间。
示例 1
输入nums [2,2,1]
输出1class Solution {public int singleNumber(int[] nums) {int temp nums[0];for (int i 1; i nums.length; i ) {temp ^ nums[i];}return temp;}
}p50 139. 单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
**注意**不要求字典中出现的单词全部都使用并且字典中的单词可以重复使用。
示例 1
输入: s leetcode, wordDict [leet, code]
输出: true
解释: 返回 true 因为 leetcode 可以由 leet 和 code 拼接成。class Solution {public boolean wordBreak(String s, ListString wordDict) {int n s.length();boolean[] dp new boolean[n 1];dp[0] true;for (int i 0; i n; i) {if (!dp[i]) {continue;}for (String word : wordDict) {if (s.startsWith(word, i)) {dp[i word.length()] true;}}}return dp[n];}
}
