网站建设公司宣传范文,长泰人才网597最新招聘信息,苏州企业网站建设制作服务,装修 设计 网站前言
计划做一系列算法题的文章#xff0c;因为自己这块确实比较薄弱#xff0c;但又很重要#xff01;写这篇文章前#xff0c;我已经刷了一本剑指offer#xff0c;leetcode top150道#xff0c;牛客某题库106道 这个样子吧#xff0c;感觉题量算是入门了吧#xff1…前言
计划做一系列算法题的文章因为自己这块确实比较薄弱但又很重要写这篇文章前我已经刷了一本剑指offerleetcode top150道牛客某题库106道 这个样子吧感觉题量算是入门了吧个人感觉还是入门级别因为最开始的题完全是硬刷全是混个脸熟。到现在才开始对里面的门门道道研究总结。 所以打算从这篇文章开始静下心来过一遍。留下自己的足迹也算是给自己打气吧 leetcode前言1 ✔ [21]合并两个有序链表 Easy 2023-02-22 2222 [102]二叉树的层序遍历 Medium 2022-09-21 2023 ✔ [33]搜索旋转排序数组 Medium 2023-03-08 1974 ✔ [20]有效的括号 Easy 2023-01-12 1945 ✔ [5]最长回文子串 Medium 2023-03-05 1936 ✔ [121]买卖股票的最佳时机 Easy 2023-01-12 1921 ✔ [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);ListListInteger lists solution.levelOrder(treeNode);for (int i 0; i lists.size(); i) {System.out.println();ListInteger 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 ListListInteger levelOrder(TreeNode root) {QueueTreeNode queue new ArrayDeque();ListListInteger res new ArrayList();if(root ! null){queue.add(root);}if (!queue.isEmpty()) {do {queue check(queue, res);}while (!queue.isEmpty()) ;}return res;}public QueueTreeNode check(QueueTreeNode queue,ListListInteger data){QueueTreeNode res new ArrayDeque();ArrayListInteger 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 ListListInteger levelOrder(TreeNode root) {QueueTreeNode queue new ArrayDeque();ListListInteger res new ArrayList();if(root ! null){queue.add(root);}if (!queue.isEmpty()) {do {queue check(queue, res);}while (!queue.isEmpty()) ;}return res;}public QueueTreeNode check(QueueTreeNode queue,ListListInteger data){QueueTreeNode res new ArrayDeque();ArrayListInteger 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 在预先未知的某个下标 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) 的算法解决此问题。 // // // // 示例 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) {HashMapString, String hashMap new HashMap();hashMap.put((,));hashMap.put({,});hashMap.put([,]);String[] split s.split();int length split.length;StackString 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) {HashMapString, String hashMap new HashMap();hashMap.put((,));hashMap.put({,});hashMap.put([,]);String[] split s.split();int length split.length;StackString 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[j1][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 4return 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[j1][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 4return 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;}
}
