前言
计划做一系列算法题的文章，因为自己这块确实比较薄弱，但又很重要！写这篇文章前，我已经刷了一本剑指offer，leetcode top150道，牛客某题库106道这个样子吧，感觉题量算是入门了吧？个人感觉还是入门级别，因为最开始的题完全是硬刷，全是混个脸熟。到现在才开始对里面的门门道道研究，总结。
所以打算从这篇文章开始，静下心来过一遍。留下自己的足迹也算是给自己打气吧！
1 ✔ [21]合并两个有序链表 Easy 2023-02-22 222
//将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
//
//
//
// 示例 1：
//
//
//输入：l1 = [1,2,4], l2 = [1,3,4]
//输出：[1,1,2,3,4,4]
//
//
// 示例 2：
//
//
//输入：l1 = [], l2 = []
//输出：[]
//
//
// 示例 3：
//
//
//输入：l1 = [], l2 = [0]
//输出：[0]
//
//
//
//
// 提示：
//
//
// 两个链表的节点数目范围是 [0, 50]
// -100 <= Node.val <= 100
// l1 和 l2 均按 非递减顺序 排列
//
//
// Related Topics 递归 链表 👍 2826 👎 0
自测代码
public class P21_MergeTwoSortedLists{
public static void main(String[] args) {
int[] ints = {1, 2, 4};
ListNode listNode = new ListNode(ints);
int[] ints2 = {1,3,4};
ListNode listNode2 = new ListNode(ints2);
//测试代码
Solution solution = new P21_MergeTwoSortedLists().new Solution();
ListNode listNode1 = solution.mergeTwoLists(listNode, listNode2);
System.out.println(listNode1.toString());
}
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
/**
* 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 listNode = new ListNode(0);
ListNode res = listNode;
while (list1 != null || list2 != null ){
if (list1 == null){
listNode.next = list2;
return res.next;
}
if(list2 == null){
listNode.next = list1;
return res.next;
}
if (list1.val > list2.val) {
listNode.next = list2;
list2 = list2.next;
}else {
listNode.next = list1;
list1 = list1.next;
}
listNode = listNode.next;
}
return res.next;
}
}
//leetcode submit region end(Prohibit modification and deletion)
}
提交代码
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode listNode = new ListNode(0);
ListNode res = listNode;
while (list1 != null || list2 != null ){
if (list1 == null){
listNode.next = list2;
return res.next;
}
if(list2 == null){
listNode.next = list1;
return res.next;
}
if (list1.val > list2.val) {
listNode.next = list2;
list2 = list2.next;
}else {
listNode.next = list1;
list1 = list1.next;
}
listNode = listNode.next;
}
return res.next;
}
}
2 [102]二叉树的层序遍历 Medium 2022-09-21 202
//给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
//
//
//
// 示例 1：
//
//
//输入：root = [3,9,20,null,null,15,7]
//输出：[[3],[9,20],[15,7]]
//
//
// 示例 2：
//
//
//输入：root = [1]
//输出：[[1]]
//
//
// 示例 3：
//
//
//输入：root = []
//输出：[]
//
//
//
//
// 提示：
//
//
// 树中节点数目在范围 [0, 2000] 内
// -1000 <= Node.val <= 1000
//
//
// Related Topics 树 广度优先搜索 二叉树 👍 1604 👎 0
自测代码
public class P102_BinaryTreeLevelOrderTraversal{
public static void main(String[] args) {
//测试代码
Solution solution = new P102_BinaryTreeLevelOrderTraversal().new Solution();
String data = "[3,9,20,null,null,15,7]";
TreeNode treeNode = mkTree(data);
List<List<Integer>> lists = solution.levelOrder(treeNode);
for (int i = 0; i < lists.size(); i++) {
System.out.println();
List<Integer> integers = lists.get(i);
for (int i1 = 0; i1 < integers.size(); i1++) {
System.out.print(" " + integers.get(i1));
}
}
}
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
Queue<TreeNode> queue = new ArrayDeque<>();
List<List<Integer>> res = new ArrayList<>();
if(root != null){
queue.add(root);
}
if (!queue.isEmpty()) {
do {
queue = check(queue, res);
}while (!queue.isEmpty()) ;
}
return res;
}
public Queue<TreeNode> check(Queue<TreeNode> queue,List<List<Integer>> data){
Queue<TreeNode> res = new ArrayDeque<>();
ArrayList<Integer> integers = new ArrayList<>();
while (!queue.isEmpty() ){
TreeNode poll = queue.poll();
if (poll == null) {
break;
}
int val = poll.val;
integers.add(val);
TreeNode left = poll.left;
if (left != null) {
res.add(left);
}
TreeNode right = poll.right;
if (right != null) {
res.add(right);
}
}
data.add(integers);
return res;
}
}
提交代码
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
Queue<TreeNode> queue = new ArrayDeque<>();
List<List<Integer>> res = new ArrayList<>();
if(root != null){
queue.add(root);
}
if (!queue.isEmpty()) {
do {
queue = check(queue, res);
}while (!queue.isEmpty()) ;
}
return res;
}
public Queue<TreeNode> check(Queue<TreeNode> queue,List<List<Integer>> data){
Queue<TreeNode> res = new ArrayDeque<>();
ArrayList<Integer> integers = new ArrayList<>();
while (!queue.isEmpty() ){
TreeNode poll = queue.poll();
if (poll == null) {
break;
}
int val = poll.val;
integers.add(val);
TreeNode left = poll.left;
if (left != null) {
res.add(left);
}
TreeNode right = poll.right;
if (right != null) {
res.add(right);
}
}
data.add(integers);
return res;
}
}
主要是使用了队列的特性，然后通过新建一个方法更清晰的区分，每一层的数据
3 ✔ [33]搜索旋转排序数组 Medium 2023-03-08 197
//整数数组 nums 按升序排列，数组中的值 互不相同 。
//
// 在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[
//k+1], ..., 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) 的算法解决此问题。
//
//
//
// 示例 1：
//
//
//输入：nums = [4,5,6,7,0,1,2], target = 0
//输出：4
//
//
// 示例 2：
//
//
//输入：nums = [4,5,6,7,0,1,2], target = 3
//输出：-1
//
// 示例 3：
//
//
//输入：nums = [1], target = 0
//输出：-1
//
//
//
//
// 提示：
//
//
// 1 <= nums.length <= 5000
// -10⁴ <= nums[i] <= 10⁴
// nums 中的每个值都 独一无二
// 题目数据保证 nums 在预先未知的某个下标上进行了旋转
// -10⁴ <= target <= 10⁴
//
//
// Related Topics 数组 二分查找 👍 2422 👎 0
自测代码
public class P33_SearchInRotatedSortedArray{
public static void main(String[] args) {
//测试代码
Solution solution = new P33_SearchInRotatedSortedArray().new Solution();
String data = "[4,5,6,7,0,1,2]";
int[] ints = StrToIntArray(data);
System.out.println(solution.search(ints, 0));
}
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public int search(int[] nums, int target) {
int num = nums.length;
int res = -1;
if (nums.length == 0){
return res;
}
if ( num == 1 ) {
if (nums[0] == target) {
return 0;
}else {
return res;
}
}
int r = 0;
int l = num-1;
while (r <= l){
int mid = (l-r)/2 +r;
if ( nums[mid] == target ) {
return mid;
}
if (nums[r] <= nums[mid] ) {
if ( nums[r] <= target && target < nums[mid] ) {
l = mid -1 ;
}else {
r = mid +1;
}
}else{
if (target <= nums[l] && target > nums[mid] ) {
r = mid +1 ;
}else{
l = mid -1;
}
}
}
return res;
}
}
//leetcode submit region end(Prohibit modification and deletion)
}
提交代码
class Solution {
public int search(int[] nums, int target) {
int num = nums.length;
int res = -1;
if (nums.length == 0){
return res;
}
if ( num == 1 ) {
if (nums[0] == target) {
return 0;
}else {
return res;
}
}
int r = 0;
int l = num-1;
while (r <= l){
int mid = (l-r)/2 +r;
if ( nums[mid] == target ) {
return mid;
}
if (nums[r] <= nums[mid] ) {
if ( nums[r] <= target && target < nums[mid] ) {
l = mid -1 ;
}else {
r = mid +1;
}
}else{
if (target <= nums[l] && target > nums[mid] ) {
r = mid +1 ;
}else{
l = mid -1;
}
}
}
return res;
}
}
中等难度，笔者之前也刷到过，但是还是想了很久。
第一： 看错了题目，以为要求旋转之前 target的下标
第二：善用二分查找方法， 遇到查找的时候想想二分方法，二分方法有一个特性就是可以直接舍弃一半数据，用另一半数据计算，所以当有一部分条件不是有序的时候，二分还是可以使用。
第三：边界值判断， 如果直接把mind赋值给左或者右，可能会导致死循环，因为 只有两个数的时候做除法mind值可能一直和左下标相同。
所以之后在自己声明了左右指针的时候，赋值时最好把中间值+1或者-1。
另外 循环条件也需要改成<=或者>= 因为 +1 / -1之后很可能导致 两个数相等，这个时候需要有等于的条件继续循环判断
4 ✔ [20]有效的括号 Easy 2023-01-12 194
//给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
//
// 有效字符串需满足：
//
//
// 左括号必须用相同类型的右括号闭合。
// 左括号必须以正确的顺序闭合。
// 每个右括号都有一个对应的相同类型的左括号。
//
//
//
//
// 示例 1：
//
//
//输入：s = "()"
//输出：true
//
//
// 示例 2：
//
//
//输入：s = "()[]{}"
//输出：true
//
//
// 示例 3：
//
//
//输入：s = "(]"
//输出：false
//
//
//
//
// 提示：
//
//
// 1 <= s.length <= 10⁴
// s 仅由括号 '()[]{}' 组成
//
//
// Related Topics 栈 字符串 👍 3786 👎 0
自测代码
public class P20_ValidParentheses{
public static void main(String[] args) {
//测试代码
Solution solution = new P20_ValidParentheses().new Solution();
String s = "]";
solution.isValid(s);
}
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public boolean isValid(String s) {
HashMap<String, String> hashMap = new HashMap<>();
hashMap.put("(",")");
hashMap.put("{","}");
hashMap.put("[","]");
String[] split = s.split("");
int length = split.length;
Stack<String> data = new Stack<>();
try{
for (int i = 0; i < length; i++) {
String s1 = hashMap.get(split[i]);
if (s1 == null) {
String pop = data.pop();
if (pop == null || !pop.equals(split[i])) {
return false;
}
}else{
data.add(s1);
}
}
}catch (Exception e){
return false;
}
if (!data.empty()) {
return false;
}
return true;
}
}
//leetcode submit region end(Prohibit modification and deletion)
}
提交代码
class Solution {
public boolean isValid(String s) {
HashMap<String, String> hashMap = new HashMap<>();
hashMap.put("(",")");
hashMap.put("{","}");
hashMap.put("[","]");
String[] split = s.split("");
int length = split.length;
Stack<String> data = new Stack<>();
try{
for (int i = 0; i < length; i++) {
String s1 = hashMap.get(split[i]);
if (s1 == null) {
String pop = data.pop();
if (pop == null || !pop.equals(split[i])) {
return false;
}
}else{
data.add(s1);
}
}
}catch (Exception e){
return false;
}
if (!data.empty()) {
return false;
}
return true;
}
}
对我来说没有太大难度了，感觉对字符串操作的我貌似都擅长一些。
这道题目就是利用了一下栈的先进先出特性
5 ✔ [5]最长回文子串 Medium 2023-03-05 193
//给你一个字符串 s，找到 s 中最长的回文子串。
//
// 如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
//
//
//
// 示例 1：
//
//
//输入：s = "babad"
//输出："bab"
//解释："aba" 同样是符合题意的答案。
//
//
// 示例 2：
//
//
//输入：s = "cbbd"
//输出："bb"
//
//
//
//
// 提示：
//
//
// 1 <= s.length <= 1000
// s 仅由数字和英文字母组成
//
//
// Related Topics 字符串 动态规划 👍 6257 👎 0
动态规划 这个问题我其实已经写了好几遍了，但是这次再做还是做不出来，或者想到的方法非常复杂。感觉还是没有完全掌握动态规划。
因此，我特地去学习了动态规划相关的知识。
首先 动态规划是解决 有重复计算，可以拆分成子问题的一类问题的解决方案。
主要表现 求最短路径，最大回文子序列，多少种走法。
分析原问题 =》找出子问题 =》 找出子问题和原问题的关系 =》 解决子问题 并记录答案=》根据子问题 解决原问题。
正确子问题： 一般情况下都比较简单，特点 一般是 个数少，逻辑和原问题有关联
记录子问题答案 ： 通过记录子问题答案，帮助解决原问题，减少重复计算，一般通过数组，二维数组来做。
这道题目 求最长回文子序列，
首先回文子序列 如果满足，那么去调开头和结尾的字母，依然满足是回文子序列。
如果一直去除，那么就会变成单个字母或者两个相同的字母，
利用这个特性，就可以找到子问题。
因为子问题和原问题的连接点 是两边添加参数，所以一定要注意动态规划的循环顺序
然后就是边界值的判断，
只有一个的时候肯定是回文串，两个的时候只需要判断两个是否相等。
自测代码
public class P5_LongestPalindromicSubstring {
public static void main(String[] args) {
//测试代码
Solution solution = new P5_LongestPalindromicSubstring().new Solution();
String s = "bb";
System.out.println(solution.longestPalindrome(s));
}
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public String longestPalindrome(String s) {
char[] chars = s.toCharArray();
int length = chars.length;
/*简单的动态规划都是记录一个值，这个最长回文子序列可以通过记录左右两个值*/
Boolean[][] data = new Boolean[length][length];
data[0][0] = true;
int[] res = new int[2];
res[0] = 0;
res[1] = 0;
for (int i = 1; i < length; i++) {
for (int j = 0; j < i; j++) {
/*长度小于三的情况*/
if (i - j < 3) {
if (chars[i] == chars[j]) {
data[j][i] = true;
}else {
data[j][i] = false;
}
} else if (chars[i] == chars[j] && data[j+1][i-1] ) {
data[j][i] = true;
}else{
data[j][i] = false;
}
if (data[j][i]) {
if (res[1] - res[0] <= i -j) {
res[0] = j;
res[1] = i;
}
}
}
}
// 0 1 2 3 4
return s.substring(res[0],res[1]+1);
}
}
//leetcode submit region end(Prohibit modification and deletion)
}
提交代码
class Solution {
public String longestPalindrome(String s) {
char[] chars = s.toCharArray();
int length = chars.length;
/*简单的动态规划都是记录一个值，这个最长回文子序列可以通过记录左右两个值*/
Boolean[][] data = new Boolean[length][length];
data[0][0] = true;
int[] res = new int[2];
res[0] = 0;
res[1] = 0;
for (int i = 1; i < length; i++) {
for (int j = 0; j < i; j++) {
/*长度小于三的情况*/
if (i - j < 3) {
if (chars[i] == chars[j]) {
data[j][i] = true;
}else {
data[j][i] = false;
}
} else if (chars[i] == chars[j] && data[j+1][i-1] ) {
data[j][i] = true;
}else{
data[j][i] = false;
}
if (data[j][i]) {
if (res[1] - res[0] <= i -j) {
res[0] = j;
res[1] = i;
}
}
}
}
// 0 1 2 3 4
return s.substring(res[0],res[1]+1);
}
}
6 ✔ [121]买卖股票的最佳时机 Easy 2023-01-12 192
//给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
//
// 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
//
// 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
//
//
//
// 示例 1：
//
//
//输入：[7,1,5,3,6,4]
//输出：5
//解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
// 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
//
//
// 示例 2：
//
//
//输入：prices = [7,6,4,3,1]
//输出：0
//解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
//
//
//
//
// 提示：
//
//
// 1 <= prices.length <= 10⁵
// 0 <= prices[i] <= 10⁴
//
//
// Related Topics 数组 动态规划 👍 2672 👎 0
配合上一道也是动态规划问题，正好巩固一下
这道题目 相对来说简单，
还是通过找关系，
求最大收益，我就先求每天的最大收益，每天的最大收益和买入时的价格有关，就记录能够买入的最小价格，
循环的顺序从前往后，子问题就和主问题联系起来了
自测代码
public class P121_BestTimeToBuyAndSellStock{
public static void main(String[] args) {
//测试代码
Solution solution = new P121_BestTimeToBuyAndSellStock().new Solution();
String data = "[7,1,5,3,6,4]";
System.out.println(solution.maxProfit(ArrayUtil.StrToIntArray(data)));
}
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
int min = Integer.MAX_VALUE;
int res = 0;
for (int i = 0; i < len; i++) {
min = prices[i] <min ? prices[i] : min;
res = prices[i] - min > res ? prices[i] - min : res;
}
return res;
}
}
//leetcode submit region end(Prohibit modification and deletion)
}
提交代码
class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
int min = Integer.MAX_VALUE;
int res = 0;
for (int i = 0; i < len; i++) {
min = prices[i] <min ? prices[i] : min;
res = prices[i] - min > res ? prices[i] - min : res;
}
return res;
}
}
发表于 2023-3-24 10:56
发表于 2023-3-24 16:42
|
发表于 2023-3-27 18:38
