嵊州市住房和城乡建设局网站网站图片切换js代码

当前位置： 首页 > news >正文

嵊州市住房和城乡建设局网站,网站图片切换js代码,wordpress备案号显示,网站横幅背景图目录1. 两数之和14. 最长公共前缀15. 三数之和18. 四数之和19. 删除链表的倒数第 N 个结点21. 合并两个有序链表28. 找出字符串中第一个匹配项的下标36. 有效的数独42. 接雨水43. 字符串相乘45. 跳跃游戏 II53. 最大子数组和54. 螺旋矩阵55. 跳跃游戏62. 不同路径70. 爬楼梯73.… 目录1. 两数之和14. 最长公共前缀15. 三数之和18. 四数之和19. 删除链表的倒数第 N 个结点21. 合并两个有序链表28. 找出字符串中第一个匹配项的下标36. 有效的数独42. 接雨水43. 字符串相乘45. 跳跃游戏 II53. 最大子数组和54. 螺旋矩阵55. 跳跃游戏62. 不同路径70. 爬楼梯73. 矩阵置零88. 合并两个有序数组98. 验证二叉搜索树102. 二叉树的层序遍历118. 杨辉三角121. 买卖股票的最佳时机122. 买卖股票的最佳时机 II142. 环形链表 II148. 排序链表152. 乘积最大子数组167. 两数之和 II - 输入有序数组198. 打家劫舍200. 岛屿数量202. 快乐数205. 同构字符串206. 反转链表213. 打家劫舍 II217. 存在重复元素234. 回文链表235. 二叉搜索树的最近公共祖先278. 第一个错误的版本299. 猜数字游戏328. 奇偶链表392. 判断子序列409. 最长回文串424. 替换后的最长重复字符438. 找到字符串中所有字母异位词509. 斐波那契数589. N 叉树的前序遍历621. 任务调度器692. 前K个高频单词704. 二分查找724. 寻找数组的中心下标733. 图像渲染740. 删除并获得点数746. 使用最小花费爬楼梯815. 公交路线844. 比较含退格的字符串876. 链表的中间结点896. 单调数列918. 环形子数组的最大和994. 腐烂的橘子1014. 最佳观光组合1046. 最后一块石头的重量1137. 第 N 个泰波那契数1250. 检查「好数组」1480. 一维数组的动态和1559. 二维网格图中探测环1567. 乘积为正数的最长子数组长度1706. 球会落何处2131. 连接两字母单词得到的最长回文串LCP 39. 无人机方阵1. 两数之和 给定一个整数数组 nums 和一个整数目标值 target请你在该数组中找出 和为目标值 target 的那 两个 整数并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。 思路 使用hashmap通过使用哈希的特性来完成 代码 class Solution {public int[] twoSum(int[] nums, int target) {HashMapInteger,Integer hasht new HashMapInteger,Integer();for(int i0;inums.length;i){int x target - nums[i];if(hasht.get(x) ! null){int[] res {hasht.get(x),i};return res;}hasht.put(nums[i],i);}return new int[0];} }14. 最长公共前缀 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀返回空字符串 “”。 思路 先扫描一遍找到最小长度的字符串用此字符串做板子进行扫描。其时间复杂度为 min字符串长度* n 代码 class Solution {public String longestCommonPrefix(String[] strs) {int p -1;int minp 201;for(int i 0;i strs.length;i){if(strs[i].length() minp){p i;minp strs[i].length();}}int res 0;for(int i 0;i strs[p].length();i){for(int j 0; jstrs.length; j)if(strs[p].charAt(i) ! strs[j].charAt(i)){return strs[p].substring(0, res);}res;}return strs[p].substring(0, res);} }

1. 三数之和 给你一个整数数组 nums 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。请 你返回所有和为 0 且不重复的三元组。 注意答案中不可以包含重复的三元组。 思路 跟两数之和一样这里我们先进行排序然后遍历数组 设置left i1right为长度-1。得出所求。 代码 class Solution {public ListListInteger threeSum(int[] nums) {ListListInteger res new ArrayList();Arrays.sort(nums);for(int i 0;i nums.length;i){if(nums[i] 0) return res;if(i 0 nums[i] nums[i-1]) continue;int l i 1;int r nums.length - 1;while(lr){if(nums[l]nums[r]nums[i]0){r–;}else if(nums[l]nums[r]nums[i]0){l;}else{ListInteger list new ArrayList();list.add(nums[i]);list.add(nums[l]);list.add(nums[r]);res.add(list);while(l r nums[l1] nums[l]) l;while (l r nums[r-1] nums[r]) –r;l;–r;}}}return res;}}18. 四数之和 给你一个由 n 个整数组成的数组 nums 和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] 若两个四元组元素一一对应则认为两个四元组重复 0 a, b, c, d n a、b、c 和 d 互不相同 nums[a] nums[b] nums[c] nums[d] target 你可以按 任意顺序 返回答案 。 思路 同三数之和这里不过是多加了一层循环注意要使用一些剪枝策略来避免无效计算。 代码 class Solution {public ListListInteger fourSum(int[] nums, int target) {ListListInteger quadruplets new ArrayListListInteger();if (nums null || nums.length 4) {return quadruplets;}Arrays.sort(nums);int length nums.length;for (int i 0; i length - 3; i) {if (i 0 nums[i] nums[i - 1]) {continue;}if ((long) nums[i] nums[i 1] nums[i 2] nums[i 3] target) {break;}if ((long) nums[i] nums[length - 3] nums[length - 2] nums[length - 1] target) {continue;}for (int j i 1; j length - 2; j) {if (j i 1 nums[j] nums[j - 1]) {continue;}if ((long) nums[i] nums[j] nums[j 1] nums[j 2] target) {break;}if ((long) nums[i] nums[j] nums[length - 2] nums[length - 1] target) {continue;}int left j 1, right length - 1;while (left right) {long sum (long) nums[i] nums[j] nums[left] nums[right];if (sum target) {quadruplets.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));while (left right nums[left] nums[left 1]) {left;}left;while (left right nums[right] nums[right - 1]) {right–;}right–;} else if (sum target) {left;} else {right–;}}}}return quadruplets;} }
2. 删除链表的倒数第 N 个结点 给你一个链表删除链表的倒数第 n 个结点并且返回链表的头结点。 思路 递归方法我们递归遍历整个链表并定义一个int类型的数用来判断删除哪一个结点每次return时该数当与给定的值相等时则返回next结点。 代码 /*** 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 {int cur 0;public ListNode removeNthFromEnd(ListNode head, int n) {if(headnull) return null;head.next removeNthFromEnd(head.next,n);cur;if(n cur) return head.next;return head;} }
3. 合并两个有序链表 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 思路 看到题目以后立马想到递归的方法对于该题我们递归最底层为判断list1或者list2是否为空返回剩下的list1或者list2。通过对比当前list1和list2的值来判断指针是否要前进一步即.next。 代码 /*** 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) {if(list1 null){return list2;}if(list2 null){return list1;}if(list1.val list2.val){list1.next mergeTwoLists(list1.next,list2);return list1;}else{list2.next mergeTwoLists(list1,list2.next);return list2;}} }28. 找出字符串中第一个匹配项的下标 给你两个字符串 haystack 和 needle 请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标下标从 0 开始。如果 needle 不是 haystack 的一部分则返回 -1 。 思路 一个个遍历 代码 class Solution {public int strStr(String ss, String pp) {int n ss.length(), m pp.length();char[] s ss.toCharArray(), p pp.toCharArray();for (int i 0; i n - m; i) {int a i, b 0;while (b m s[a] p[b]) {a;b;}if (b m) return i;}return -1;} }
4. 有效的数独 请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 验证已经填入的数字是否有效即可。 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。请参考示例图 注意 一个有效的数独部分已被填充不一定是可解的。 只需要根据以上规则验证已经填入的数字是否有效即可。 空白格用 ‘.’ 表示。
   思路 设置三个布尔数组分别记录某行/某列/3*3宫格某位数字是否已经被摆放记录某列。然后分别进行判断。 代码 class Solution {public boolean isValidSudoku(char[][] board) {boolean[][] row new boolean[9][9];boolean[][] col new boolean[9][9];boolean[][] block new boolean[9][9];for (int i 0; i 9; i) {for (int j 0; j 9; j) {if (board[i][j] ! .) {int num board[i][j] - 1;int blockIndex i / 3 * 3 j / 3;if (row[i][num] || col[j][num] || block[blockIndex][num]) {return false;} else {row[i][num] true;col[j][num] true;block[blockIndex][num] true;}}}}return true;} }42. 接雨水 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。 思路 动态规划题感觉不像是一个困难题我们对列进行操作我们只需要记住每一列左边的最大值和右边的最大值就好了其水为他们两者之间最小值减去本身带的值。 代码 class Solution {public int trap(int[] height) {if(height.length 1){return 0;}int sum 0;int[] left new int[height.length];int[] right new int[height.length];for(int i 1; i height.length -1;i){left[i] Math.max(left[i-1], height[i-1]);}for (int i height.length - 2; i 0; i–) {right[i] Math.max(right[i 1], height[i 1]);}for (int i 1; i height.length - 1; i) {int min Math.min(left[i], right[i]);if (min height[i]) {sum sum (min - height[i]);}}return sum;} }43. 字符串相乘 给定两个以字符串形式表示的非负整数 num1 和 num2返回 num1 和 num2 的乘积它们的乘积也表示为字符串形式。 注意不能使用任何内置的 BigInteger 库或直接将输入转换为整数。 思路 注意本题只能用数组存储因为其他整数类型存不下。所以我们得考虑进位问题按照之前学的竖式乘法。 代码 class Solution {public String multiply(String num1, String num2) {char[] arr1 num1.toCharArray();char[] arr2 num2.toCharArray();int n arr1.length, m arr2.length;int[] res new int[m n];// 每次相乘得到的结果直接添加到最后的结果数组中需要注意进位和结果数组下标for(int i m - 1; i 0; i –){int index res.length - 1 - (m - 1 - i);int carry 0;// carry存储进位for(int j n - 1; j 0; j –){int temp toNum(arr2[i]) * toNum(arr1[j]) carry res[index];res[index –] temp % 10;carry temp / 10;}while(index 0 carry ! 0){int temp res[index] carry;res[index –] temp % 10;carry temp / 10;}}int index 0;// 去除前导0while(index res.length res[index] 0){index ;}StringBuffer buffer new StringBuffer();for( ; index res.length; index ){buffer.append(res[index]);}return buffer.length() 0 ? 0 : buffer.toString();}private int toNum(char c){return c - 0;} }
5. 跳跃游戏 II 给你一个非负整数数组 nums 你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 你的目标是使用最少的跳跃次数到达数组的最后一个位置。 假设你总是可以到达数组的最后一个位置。 思路 注意到走到最后一个位置所以最后一个位置的值我们不用管。我们可以贪心选取在步数内可以走的最远的位置 即maxpos Math.max(maxpos, inums[i]);然后我们选取这个值接着走。以此取到最小的step值 代码 class Solution {public int jump(int[] nums) {int end 0;int step 0;int maxpos 0;for(int i 0;inums.length-1;i){maxpos Math.max(maxpos, inums[i]);if(i end){end maxpos;step;}}return step;} }53. 最大子数组和 给你一个整数数组 nums 请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。 子数组 是数组中的一个连续部分。 思路 使用动态规划。目标是找到动态规划表达式我们考虑到如果都是正整数的话那我们为fn fn nums[i]但不是这样的。但是存在负数 又考虑到是连续的则表达式改为maxfn nums[i]nums[i]如果nums[i]大于fn nums[i] 即fn为负值我们可以完全舍弃另考虑到我需要有个变量 存储最大的值。则有res max(fn,res)。 代码 class Solution {public int maxSubArray(int[] nums) {int fn -1;int res Integer.MIN_VALUE;for(int s:nums){fn Math.max(fns,s);res Math.max(fn,res);}return res;} }54. 螺旋矩阵 给你一个 m 行 n 列的矩阵 matrix 请按照 顺时针螺旋顺序 返回矩阵中的所有元素。 思路 我们可以计算旋转几次即花几个圈然后以此向左走向下走向右走向上走。这里要注意边界条件巧用旋转几次 代码 class Solution {public ListInteger spiralOrder(int[][] matrix) {ListInteger res new ArrayList();int m matrix.length;int n matrix[0].length;int mnlen Math.min(m, n) % 2 Math.min(m, n) / 2;for(int i 0; i mnlen; i){// 向左for(int j i;j n-i;j){res.add(matrix[i][j]);}for(int j i1; j m-i; j){res.add(matrix[j][n-i-1]);}for(int j n-i-2;j i (m-1-i ! i); j–){res.add(matrix[m-1-i][j]);}for(int j m-i-2;j i1 (n-1-i) ! i; j–){res.add(matrix[j][i]);}}return res;} }55. 跳跃游戏 给定一个非负整数数组 nums 你最初位于数组的 第一个下标 。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标。 思路 这题我们可以进行遍历。假设有个机器人我们先把机器人放在nums[0]其能量也为nums[0]然后机器人进行行走(这里使用i进行计数每走一步能量减一如果当前点的nums[i]的能量大于机器人的能量我们则进行更换。然后继续走 如果走不到了 则返回false不然返回true。 代码 class Solution {public boolean canJump(int[] nums) {int cur nums[0];int i 1;for(i 1;inums.length;i){if(cur!0){cur–;if(curnums[i]){cur nums[i];}}else{return false;}}return inums.length;} }62. 不同路径 一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为 “Start” 。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish” 。 问总共有多少条不同的路径 思路 使用动态规划考虑到最后一个只能由上面 或者左边过来则方法是这两个的和。即a[i][j] a[i-1][j] a[i][j-1];考虑边界条件只要ij其中一个为0则方法只有一种。 优化 其实可以只用m的空间 即可完成。 代码 class Solution {public int uniquePaths(int m, int n) {int[][] a new int[m][n];if(m1||n1){return 1;}for(int i0;im;i){a[i][0]1;}for(int i0;in;i){a[0][i]1;}for(int i1;im;i){for(int j1;jn;j){a[i][j] a[i-1][j] a[i][j-1];}}return a[m-1][n-1];} }优化代码 class Solution {public int uniquePaths(int m, int n) {int[] a new int[n];if(m1||n1){return 1;}a[0] 1;for(int i1;in;i){a[i]1;}for(int i1;im;i){a[0] 1;for(int j1;jn;j){a[j] a[j-1] a[j];}}return a[n-1];} }70. 爬楼梯 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢 思路 动态规划题想到当你走到最后一个楼梯时要么是从n-1上来要么就是从n-2上来 则有表达式fn fn-1 fn-2初值即为一层和二层楼梯次数。我们使用数组遍历想一想其实只需要三个变量即可 代码 class Solution {public int climbStairs(int n) {int[] a new int[n];if(n 2){return n;}a[0] 1;a[1] 2;for(int i2;in;i){a[i] a[i-1]a[i-2];}return a[n-1];} }优化代码 class Solution {public int climbStairs(int n) {if(n 2){return n;}int a 1;int b 2;int c 0;for(int i2;in;i){c a b;a b;b c; }return c;} }73. 矩阵置零 给定一个 m x n 的矩阵如果一个元素为 0 则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。 思路 我们使用第一行和第一列来存储出现的0另外我们设置两个变量用来存储判断第一行或者第一列中是否出现0。 代码 class Solution {public void setZeroes(int[][] matrix) {Boolean flag1 false;Boolean flag2 false;for(int i 0;imatrix.length;i){if(matrix[i][0] 0){flag1 true;}}for(int i 0;imatrix[0].length;i){if(matrix[0][i] 0){flag2 true;}}for(int i 1; i matrix.length; i){for(int j 1; j matrix[0].length; j){if(matrix[i][j] 0){matrix[i][0] matrix[0][j] 0;}}}for(int i 1; i matrix.length; i){for(int j 1; j matrix[0].length; j){if (matrix[i][0] 0 || matrix[0][j] 0) {matrix[i][j] 0;}}}if(flag1){for(int i 0;imatrix.length;i){matrix[i][0] 0;}}if(flag2){for(int i 0;imatrix[0].length;i){matrix[0][i] 0;}}} }88. 合并两个有序数组 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2另有两个整数 m 和 n 分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中使合并后的数组同样按 非递减顺序 排列。 注意最终合并后数组不应由函数返回而是存储在数组 nums1 中。为了应对这种情况nums1 的初始长度为 m n其中前 m 个元素表示应合并的元素后 n 个元素为 0 应忽略。nums2 的长度为 n 。 思路 从后排就好每次把最大值放后面。我们设置n0这样的话num2排完了那我们就不用排了因为num1的数组就存在当中。 代码 class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int last mn-1;while(n 0){if(m0||nums1[m-1]nums2[n-1]){nums1[last–]nums2[–n];}else{nums1[last–]nums1[–m];}}} }98. 验证二叉搜索树 给你一个二叉树的根节点 root 判断其是否是一个有效的二叉搜索树。 有效 二叉搜索树定义如下 节点的左子树只包含 小于 当前节点的数。 节点的右子树只包含 大于 当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 思路 使用中序遍历递归方法和栈方法都可以。 代码 /*** 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 {double pre -Double.MAX_VALUE;public boolean isValidBST(TreeNode root) {return inOrder(root);}public boolean inOrder(TreeNode root){if(root null){return true;}boolean left inOrder(root.left);if(root.val pre){return false;}pre root.val;boolean right inOrder(root.right);return left right;}}102. 二叉树的层序遍历 给你二叉树的根节点 root 返回其节点值的 层序遍历 。 即逐层地从左到右访问所有节点。 思路 其实就是BFS我们可以用队列实现先进先出。 代码 /** 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) {ListListInteger res new ArrayList();QueueTreeNode queue new ArrayDeque();if(root null){return res;}queue.add(root);while(!queue.isEmpty()){ListInteger listRes new ArrayList();int n queue.size();for(int i 0;in;i){TreeNode node queue.poll();listRes.add(node.val);if(node.left!null){queue.add(node.left);}if(node.right!null){queue.add(node.right);}}res.add(listRes);}return res;} }118. 杨辉三角 给定一个非负整数 numRows生成「杨辉三角」的前 numRows 行。 在「杨辉三角」中每个数是它左上方和右上方的数的和。 思路 利用其性质每个数是它左上方和右上方的数的和 代码 class Solution {public ListListInteger generate(int numRows) {ListListInteger res new ArrayList();int[][] arnew int[numRows][numRows];for (int i 0; i numRows; i) {ar[i][0]1;}for(int i 0; inumRows;i){ListInteger reslist new ArrayList();reslist.add(1);for(int j 1; j i; j){ar[i][j] ar[i-1][j] ar[i-1][j-1];reslist.add(ar[i][j]);}res.add(reslist);}return res;} }121. 买卖股票的最佳时机 给定一个数组 prices 它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润返回 0 。 思路 巧用最大最小值最大值级利润即0和当前值减去最小值考虑到不能在买入前卖出股票。我们先求最大值再求最小值。最小值即比较两两直接的最小值。 代码 class Solution {public int maxProfit(int[] prices) {if(prices.length 1){return 0;}int maxl 0;int minl prices[0];for(int i0; iprices.length; i){maxl Math.max(maxl,prices[i]-minl);minl Math.min(minl,prices[i]);}return maxl;} }122. 买卖股票的最佳时机 II 给你一个整数数组 prices 其中 prices[i] 表示某支股票第 i 天的价格。 在每一天你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买然后在 同一天 出售。 返回 你能获得的 最大 利润 。 思路 动态规划题在这里设置两个状态0是持有现金1是持有股票。我们不断更新这两个状态得到最终解。 代码 public class Solution {public int maxProfit(int[] prices) {int len prices.length;if (len 2) {return 0;}// 0持有现金// 1持有股票int[][] dp new int[len][2];dp[0][0] 0;dp[0][1] -prices[0];for (int i 1; i len; i) {dp[i][0] Math.max(dp[i - 1][0], dp[i - 1][1] prices[i]);dp[i][1] Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);}return dp[len - 1][0];} }
6. 环形链表 II 给定一个链表的头节点 head 返回链表开始入环的第一个节点。 如果链表无环则返回 null。 如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。如果 pos 是 -1则在该链表中没有环。注意pos 不作为参数进行传递仅仅是为了标识链表的实际情况。 不允许修改 链表。 思路 双指针题我们设置一个快指针fast 和一个慢指针slow设定fast每次走两个slow每次走一格 假设slow走x格以后他们相遇 此时fast走了2x格 设置 a为未进入循环的步长 b为循环步长 z为当前进入循环以后走的步长 有 x az2x anbz n为循环的次数 我们暂时设置为1 则有 x a z 2x abz 因为相遇 易知 x b 又有 b az 我们目前要求出a 我们利用头结点同速度和slow跑易知a步以后他们会相遇 为什么 因为 当走了a 步以后 此时 head a slow aaz 即a b b为循环则可求 此外对于 没有循环 我们只需要判断fast 和fast的next是否为空即可 代码 /*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }/ public class Solution {public ListNode detectCycle(ListNode head) {ListNode fast head;ListNode slow head;while(true){if(fast null|| fast.next null){return null;}fast fast.next.next;slow slow.next;if(fast slow){break;}}while(head ! slow){head head.next;slow slow.next;}return head;}}148. 排序链表 给你链表的头结点 head 请将其按 升序 排列并返回 排序后的链表 。 思路 直接用快速排序就好了 平均复杂度为Onlogn 代码 /** 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 sortList(ListNode head) {return quickSort(head);}public ListNode quickSort(ListNode head) {if (headnull || head.nextnull) {return head;}ListNode h1 new ListNode();ListNode h2 new ListNode();ListNode h3 new ListNode();ListNode t1 h1;ListNode t2 h2;ListNode t3 h3;ListNode curr head;int pivot getMid(head).val; while (curr!null) {ListNode next curr.next;if (curr.val pivot) {curr.next null;t1.next curr;t1 t1.next;} else if (curr.val pivot) {curr.next null;t2.next curr;t2 t2.next;} else {curr.next null;t3.next curr;t3 t3.next;}curr next;}h1 quickSort(h1.next);h3 quickSort(h3.next);h2 h2.next;t2.next h3;if (h1null) {return h2;} else {t1 h1;while (t1.next!null) {t1 t1.next;}t1.next h2;return h1;}}public ListNode getMid(ListNode head) {ListNode fast head;ListNode slow head;while (fast!null fast.next!null) {fast fast.next.next;slow slow.next;}return slow;}}152. 乘积最大子数组 给你一个整数数组 nums 请你找出数组中乘积最大的非空连续子数组该子数组中至少包含一个数字并返回该子数组所对应的乘积。 测试用例的答案是一个 32-位 整数。 子数组 是数组的连续子序列。 思路 这里相比于之前 fmax max{fmaxai,ai}我们还需要考虑fmin的值因为存在负数那我们更改方程。fmax max{fmaxaifminaiai}同时有fmin min{fmaxaifmin*aiai}每次存储fmin的值 因为负数不一定是坏事 代码 class Solution {public int maxProduct(int[] nums) {int fmin nums[0];int fmax nums[0];int res fmax;for(int i 1; i nums.length; i){int mx fmax, mn fmin; fmax Math.max(Math.max(mx*nums[i],mn*nums[i]),nums[i]);fmin Math.min(Math.min(mx*nums[i],mnnums[i]),nums[i]);res Math.max(fmax, res);}return res;} }167. 两数之和 II - 输入有序数组 给你一个下标从 1 开始的整数数组 numbers 该数组已按 非递减顺序排列 请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] 则 1 index1 index2 numbers.length 。 以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。 你可以假设每个输入 只对应唯一的答案 而且你 不可以 重复使用相同的元素。 你所设计的解决方案必须只使用常量级的额外空间。 思路 只使用常量级的额外空间。且排序好的立马想到使用双指针left和right分别只想0和length-1。如果大了则r指针左移小了则l指针右移。 代码 class Solution {public int[] twoSum(int[] numbers, int target) {int l 0;int r numbers.length - 1;while(lr){if(numbers[l]numbers[r]target){r–;}else if(numbers[l]numbers[r]target){l;}else{return new int[]{l1,r1};}}return new int[]{l1,r1};} }198. 打家劫舍 你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组计算你 不触动警报装置的情况下 一夜之内能够偷窃到的最高金额。 思路 动态规划题我们先找到表达式很容易得出fn fn-2 fn-3 cost[n]。我们分别求出其初值。最后我们取最后两个数的最大值。这里是因为 考虑到 最后的解肯定是从倒数两个数来的因为倒数第三个数还可以加上倒数第一个数 代码 class Solution {public int rob(int[] nums) {int n nums.length;if(n 1){return nums[0]; }else if(n 2){return Math.max(nums[0],nums[1]);}else if(n 3){return Math.max(nums[0]nums[2],nums[1]);}int[] a new int[n];a[0] nums[0];a[1] nums[1];a[2] nums[0]nums[2];for(int i3;in;i){a[i] Math.max(a[i-2],a[i-3])nums[i];}return Math.max(a[n-1],a[n-2]);} }200. 岛屿数量 给你一个由 ‘1’陆地和 ‘0’水组成的的二维网格请你计算网格中岛屿的数量。 岛屿总是被水包围并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 此外你可以假设该网格的四条边均被水包围。 思路 基于dfs来做巧用标记标记好已经走过的。然后我们遍历整个数组当岛没有访问过即存在为1。 我们res然后进行dfs使得这块岛全部被标记。 代码 class Solution {public int numIslands(char[][] grid) {int res 0;for(int i0;igrid.length;i){for(int j0;jgrid[0].length;j){if(grid[i][j] 1){dfs(grid,i,j);res;}}}return res;}public void dfs(char[][] grid,int x,int y){if(x 0||y 0||xgrid.length||ygrid[0].length) return ;if(grid[x][y] ! 1) return;grid[x][y] 2;dfs(grid,x-1,y);dfs(grid,x1,y);dfs(grid,x,y-1);dfs(grid,x,y1);} }202. 快乐数 编写一个算法来判断一个数 n 是不是快乐数。 「快乐数」 定义为 对于一个正整数每一次将该数替换为它每个位置上的数字的平方和。 然后重复这个过程直到这个数变为 1也可能是 无限循环 但始终变不到 1。 如果这个过程 结果为 1那么这个数就是快乐数。 如果 n 是 快乐数 就返回 true 不是则返回 false 。 思路 使用快慢指针如果是循环的 那fast指针一定可以追上slow指针跟之前检查环一样。然后我们判断是否为1. 代码 class Solution {public boolean isHappy(int n) {int fast n;int slow n;do{slow square(slow);fast square(fast);fast square(fast);}while(fast!slow);if(fast 1){return true;}else{return false;}}public int square(int fs){int squaresum 0;while(fs!0){squaresum (fs%10)(fs%10);fs / 10;}return squaresum;} }205. 同构字符串 给定两个字符串 s 和 t 判断它们是否是同构的。 如果 s 中的字符可以按某种映射关系替换得到 t 那么这两个字符串是同构的。 每个出现的字符都应当映射到另一个字符同时不改变字符的顺序。不同字符不能映射到同一个字符上相同字符只能映射到同一个字符上字符可以映射到自己本身。 思路 首先想到的就是用HashMap因为用到唯一性可以先判断元素是否存在 如果存在 判断映射是否和t中元素相等。考虑到s和t都是唯一性我们建立两个hashmap 改进思路 可以类似用find函数indexof查找每个字符首次的出现的位置如果相等则继续不相等判断false。 代码 class Solution {public boolean isIsomorphic(String s, String t) {HashMapCharacter, Character sHash new HashMapCharacter, Character ();HashMapCharacter, Character tHash new HashMapCharacter, Character ();for(int i0;i s.length();i){if(sHash.get(s.charAt(i)) null){sHash.put(s.charAt(i), t.charAt(i));}else{if(sHash.get(s.charAt(i))!t.charAt(i)){return false;}}}for(int i0;i s.length();i){if(tHash.get(t.charAt(i)) null){tHash.put(t.charAt(i), s.charAt(i));}else{if(tHash.get(t.charAt(i))!s.charAt(i)){return false;}}}return true;} }class Solution {public boolean isIsomorphic(String s, String t) {for(int i 0;is.length();i){if(s.indexOf(s.substring(i,i1))!t.indexOf(t.substring(i,i1))){return false;}}return true;} }206. 反转链表 给你单链表的头节点 head 请你反转链表并返回反转后的链表。 思路 考虑到利用两个指针一个prenext。分别用于存储之前的值和后一个值我们通过不断移动 得到想要的结果。 代码 /*** 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 reverseList(ListNode head) {ListNode prev null;while(head ! null){ListNode next head.next;head.next prev;prev head;head next;}return prev;} }213. 打家劫舍 II 你是一个专业的小偷计划偷窃沿街的房屋每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 这意味着第一个房屋和最后一个房屋是紧挨着的。同时相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警 。 给定一个代表每个房屋存放金额的非负整数数组计算你 在不触动警报装置的情况下 今晚能够偷窃到的最高金额 思路 依旧是fn maxfn-1fn-2cost【n】这里我们要做两次 一次从2开始 一次走到n-1结束 取最大值 代码 class Solution {public int rob(int[] nums) {int n nums.length;if(n 1){return nums[0];}int[] dp1 new int[n];dp1[0] 0;dp1[1] nums[1];for(int i 2 ;i n;i){dp1[i] Math.max(dp1[i-1],(dp1[i-2]nums[i]));}int[] dp2 new int[n];dp2[0] nums[0];dp2[1] Math.max(nums[0],nums[1]);for(int i 2 ;i n-1;i){dp2[i] Math.max(dp2[i-1],(dp2[i-2]nums[i]));}return Math.max(dp2[n-2],dp1[n-1]);} }217. 存在重复元素 给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 返回 true 如果数组中每个元素互不相同返回 false 。 思路 使用哈希表就可以 class Solution {public boolean containsDuplicate(int[] nums) {HashMapInteger, Integer res new HashMapInteger, Integer();for(int i 0;inums.length;i){if(res.get(nums[i]) null){res.put(nums[i],i);}else{return true;}}return false;} }234. 回文链表 给你一个单链表的头节点 head 请你判断该链表是否为回文链表。如果是返回 true 否则返回 false 。 思路 使用快慢指针双指针先使用快慢指针找到中间的位置对中间后面的进行倒转。然后方便进行比较。 代码 /** 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 boolean isPalindrome(ListNode head) {ListNode slow head,fast head,prev null;while(fast ! null fast.next ! null){slow slow.next;fast fast.next.next;}while(slow ! null){ListNode temp slow.next;slow.next prev;prev slow;slow temp;}while(head!nullprev!null){if(head.val ! prev.val){return false;}head head.next;prev prev.next;}return true;} }235. 二叉搜索树的最近公共祖先 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为“对于有根树 T 的两个结点 p、q最近公共祖先表示为一个结点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。” 例如给定如下二叉搜索树: root [6,2,8,0,4,7,9,null,null,3,5] 思路 因为是二叉搜索树从root开始进行判断就好了。 代码 /** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val x; }* }/class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {while(true){if(root.valp.val root.valq.val){root root.left;}else if(root.valp.val root.valq.val){root root.right;}else{break;}}return root;} }278. 第一个错误的版本 你是产品经理目前正在带领一个团队开发新的产品。不幸的是你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的所以错误的版本之后的所有版本都是错的。 假设你有 n 个版本 [1, 2, …, n]你想找出导致之后所有版本出错的第一个错误的版本。 你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数 思路 二分查找 代码 / The isBadVersion API is defined in the parent class VersionControl.boolean isBadVersion(int version); /public class Solution extends VersionControl {public int firstBadVersion(int n) {int left 0;int right n;while(leftright){int mid left (right - left)/2;if(isBadVersion(mid)){right mid - 1;}else{left mid 1;}}return left;} }299. 猜数字游戏 你在和朋友一起玩 猜数字Bulls and Cows游戏该游戏规则如下 写出一个秘密数字并请朋友猜这个数字是多少。朋友每猜测一次你就会给他一个包含下述信息的提示 猜测数字中有多少位属于数字和确切位置都猜对了称为 “Bulls”公牛 有多少位属于数字猜对了但是位置不对称为 “Cows”奶牛。也就是说这次猜测中有多少位非公牛数字可以通过重新排列转换成公牛数字。 给你一个秘密数字 secret 和朋友猜测的数字 guess 请你返回对朋友这次猜测的提示。 提示的格式为 “xAyB” x 是公牛个数 y 是奶牛个数A 表示公牛B 表示奶牛。 请注意秘密数字和朋友猜测的数字都可能含有重复数字。 思路 新建一个大小为10的数组 来计算出奶牛和公牛的数量。最后我们在一个个比较得到公牛的数量得到答案。 代码 class Solution {public String getHint(String secret, String guess) {int s secret.length();int[] scount new int[10];for(int i0; i s; i){scount[Character.getNumericValue(secret.charAt(i))];scount[Character.getNumericValue(guess.charAt(i))]–;}int step 0;for(int i0; i 10; i){if(scount[i]0){step scount[i];}}// 奶牛个数 sstepint bull 0;for(int i0; is; i){if(secret.charAt(i) guess.charAt(i)) {bull;}}int sbull s step - bull;return bull A sbull B;} }328. 奇偶链表 给定单链表的头节点 head 将所有索引为奇数的节点和索引为偶数的节点分别组合在一起然后返回重新排序的列表。 第一个节点的索引被认为是 奇数 第二个节点的索引为 偶数 以此类推。 请注意偶数组和奇数组内部的相对顺序应该与输入时保持一致。 你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。 思路 确定好奇数和偶数头尾指针我们分别进行操作。 代码 /** 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 oddEvenList(ListNode head) {if (head null || head.next null) {return head;}// 奇链表尾节点ListNode l head;// 偶链表头结点ListNode r head.next;// 偶链表尾节点ListNode e r;while (l.next ! null e.next ! null) {l.next e.next;l l.next;e.next l.next;e e.next;}l.next r;return head;} }392. 判断子序列 给定字符串 s 和 t 判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些也可以不删除字符而不改变剩余字符相对位置形成的新字符串。例如ace是abcde的一个子序列而aec不是。 进阶 如果有大量输入的 S称作 S1, S2, … , Sk 其中 k 10亿你需要依次检查它们是否为 T 的子序列。在这种情况下你会怎样改变代码 思路 双指针思路一个指针j指向s另一个指针i指向t遍历移动t但s[j]等于t[i]时移动j即j。得出结果。 代码 class Solution {public boolean isSubsequence(String s, String t) {int j 0;if(s.length()0){return true;}if(t.length()0){return false;}for(int i 0;it.length();i){if(t.charAt(i)s.charAt(j)){j;}if(j s.length()){return true;}}return false;} }409. 最长回文串 给定一个包含大写字母和小写字母的字符串 s 返回 通过这些字母构造成的 最长的回文串 。 在构造过程中请注意 区分大小写 。比如 “Aa” 不能当做一个回文字符串。 思路 可以使用哈希表也可以新建一个128的数组。对此进行计数。考虑到偶数一定可以组成回文。我们可以巧用先除二在乘二来得到偶数注意除此以外我们还需要加入一次单个字母奇数如果有的话 代码 class Solution {public int longestPalindrome(String s) {int[] count new int[128];for(int i0;is.length();i){char c s.charAt(i);count[c];}int ans 0;for(int j:count){ans j/22;if(j%21 ans%20){ans;}}return ans;} }424. 替换后的最长重复字符 给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。 在执行上述操作后返回包含相同字母的最长子字符串的长度。 思路 使用滑动窗口思想我们使用left和right双指针不断移动另我们适用一个int型的historyMax记录最大值注意判断条件right-left1 historyMaxk即指针最大长度是否大于历史最大值k如果大于那我们移动left指针。 代码 class Solution {public int characterReplacement(String s, int k) {int left 0,right 0;int historyMax 0;int n s.length();int[] nums new int[26];for(right 0; right n ; right){nums[s.charAt(right) - A];historyMax Math.max(historyMax, nums[s.charAt(right) - A]);if(right-left1 historyMaxk){nums[s.charAt(left) - A]–;left;}}return right-left;} }438. 找到字符串中所有字母异位词 给定两个字符串 s 和 p找到 s 中所有 p 的 异位词 的子串返回这些子串的起始索引。不考虑答案输出的顺序。 异位词 指由相同字母重排列形成的字符串包括相同的字符串。 思路 利用滑动窗口思想设置左右指针。我们new两个数组进行计数通过不断移动窗口得到想到的答案。 代码 class Solution {public ListInteger findAnagrams(String s, String p) {ListInteger ans new ArrayListInteger();int m s.length();int n p.length();if(m n){return ans;}int[] count1 new int[26];int[] count2 new int[26];for(int i0;in;i) count2[p.charAt(i)-a];for(int left0,right0;rightm;right){count1[s.charAt(right)-a];if(right-left1n){count1[s.charAt(left)-a]–;left;}if(Arrays.equals(count1,count2)){ans.add(left);}}return ans;} }509. 斐波那契数 斐波那契数 通常用 F(n) 表示形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始后面的每一项数字都是前面两项数字的和。也就是 F(0) 0F(1) 1 F(n) F(n - 1) F(n - 2)其中 n 1 给定 n 请计算 F(n) 。 思路 这题可以用递归或者for循环来解这里使用循环因为递归太烂大街了。 优化事实上 我们只需要三个变量就可以了 因为用到的也只是三个变量 代码 class Solution {public int fib(int n) {if(n 2){return n;}int[] a new int[n1];a[0] 0;a[1] 1;for(int i2;in;i){a[i] a[i-1] a[i-2];}return a[n];} }优化代码 class Solution {public int fib(int n) {if(n 2){return n;}int a 0;int b 1;int c 0;for(int i2;in;i){c a b;a b;b c; }return c;} }589. N 叉树的前序遍历 给定一个 n 叉树的根节点 root 返回 其节点值的 前序遍历 。 n 叉树 在输入中按层序遍历进行序列化表示每组子节点由空值 null 分隔请参见示例。 思路 就是简单的前序遍历我们用递归方法。考虑到返回一个数组我们新建一个list用来添加每次的node 代码 / // Definition for a Node. class Node {public int val;public ListNode children;public Node() {}public Node(int _val) {val _val;}public Node(int _val, ListNode _children) {val _val;children _children;} }; */class Solution {public ListInteger preorder(Node root) {ListInteger res new ArrayList();forList(root,res);return res;}public void forList(Node root, ListInteger res) {if (root null) {return;}res.add(root.val);for (Node ch : root.children) {forList(ch, res);}}}621. 任务调度器 给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间CPU 可以完成一个任务或者处于待命状态。 然而两个 相同种类 的任务之间必须有长度为整数 n 的冷却时间因此至少有连续 n 个单位时间内 CPU 在执行不同的任务或者在待命状态。 你需要计算完成所有任务所需要的 最短时间 。 思路 感觉像是智力题对于这题我们只要判断(maxl - 1) * (n 1) 1如果另有等于maxl的数那我们加一。 代码 class Solution {public int leastInterval(char[] tasks, int n) {int[] cs new int[26];int l tasks.length;for(int i 0; i l; i){cs[tasks[i] - A];}Arrays.sort(cs);int maxl cs[25];int retl (maxl - 1) * (n 1) 1;int i 24;while (i 0 cs[i] maxl) {retl;i–;}return Math.max(retl,l);} }692. 前K个高频单词 给定一个单词列表 words 和一个整数 k 返回前 k 个出现次数最多的单词。 返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率 按字典顺序 排序。 思路 哈希表排序 代码 class Solution {public ListString topKFrequent(String[] words, int k) {HashMapString,Integer hasht new HashMapString,Integer();for(int i 0;i words.length; i){if(hasht.get(words[i]) null){hasht.put(words[i],1);}else{int x hasht.get(words[i]) 1;hasht.put(words[i],x);}}ListString candidates new ArrayList(hasht.keySet());// 此处为使用 lambda 写法candidates.sort((a, b) - {if (hasht.get(a).equals(hasht.get(b))) {return a.compareTo(b);} else { return hasht.get(b) - hasht.get(a);}});return candidates.subList(0, k); }
   }704. 二分查找 给定一个 n 个元素有序的升序整型数组 nums 和一个目标值 target 写一个函数搜索 nums 中的 target如果目标值存在返回下标否则返回 -1。 思路 使用二分查找 注意判断条件 我们使用两个指针left和rightmid left (right-left)/2如果mid值小于target则说明目标值在右边我们令left mid 1指针多移动一位因为其mid值已经小于了同样rightmid-1.通过使用leftright这个while判断。 代码 class Solution {public int search(int[] nums, int target) {int left 0;int right nums.length - 1;while(leftright){int mid left (right-left)/2;if(nums[mid]target){left mid 1;}else if(nums[mid]target){right mid - 1;}else{return mid;}}return -1;} }724. 寻找数组的中心下标 给你一个整数数组 nums 请计算数组的 中心下标 。 数组 中心下标 是数组的一个下标其左侧所有元素相加的和等于右侧所有元素相加的和。 如果中心下标位于数组最左端那么左侧数之和视为 0 因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。 如果数组有多个中心下标应该返回 最靠近左边 的那一个。如果数组不存在中心下标返回 -1 。 思路 中心下标 即其中心下标左边的值等于等于右边的值 则有 左边的值2中心下标的值 总的值 我们可以先求出总的值然后遍历找到中心下标。即把中心下标当作指针其左边的值求和2加上此指针代表的值求和如果等于总的值则return 此指针。如果遍历完还没有 那么返回-1 复杂度分析 内存 O(1)O(1)O(1) 时间 O(n)O(n)O(n) 代码 class Solution {public int pivotIndex(int[] nums) {int numsSum 0;int sumLeft 0;int numsLen nums.length;for(int i0;inumsLen;i){numsSum nums[i];} for(int i0;inumsLen;i){if(sumLeft2nums[i] numsSum){return i;}sumLeft nums[i];} return -1;} }733. 图像渲染 有一幅以 m x n 的二维整数数组表示的图画 image 其中 image[i][j] 表示该图画的像素值大小。 你也被给予三个整数 sr , sc 和 newColor 。你应该从像素 image[sr][sc] 开始对图像进行 上色填充 。 为了完成 上色工作 从初始像素开始记录初始坐标的 上下左右四个方向上 像素值与初始坐标相同的相连像素点接着再记录这四个方向上符合条件的像素点与他们对应 四个方向上 像素值与初始坐标相同的相连像素点……重复该过程。将所有有记录的像素点的颜色值改为 newColor 。 最后返回 经过上色渲染后的图像 。 思路 使用dfs我们只需判断该点是不是满足要求才进行上色。 代码 class Solution {public void dfs(int[][] image, int x, int y, int color, int newColor){if(image[x][y] newColor||image[x][y] ! color){return;}image[x][y] newColor;if (x 0) dfs(image, x-1, y, color, newColor);if (x image.length-1) dfs(image, x1, y, color, newColor);if (y 0) dfs(image, x, y-1, color, newColor);if (y image[0].length-1) dfs(image, x, y1, color, newColor);}public int[][] floodFill(int[][] image, int sr, int sc, int color) {int oldcolor image[sr][sc];dfs(image, sr, sc, oldcolor, color);return image;}}740. 删除并获得点数 给你一个整数数组 nums 你可以对它进行一些操作。 每次操作中选择任意一个 nums[i] 删除它并获得 nums[i] 的点数。之后你必须删除 所有 等于 nums[i] - 1 和 nums[i] 1 的元素。 开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。 思路 跟打家劫舍一样详情可以看。我们新建一个数组用来存储每个数的收益从0到max的值。 代码 class Solution {public int deleteAndEarn(int[] nums) {int maxnums 0;for(int x:nums){maxnums Math.max(maxnums,x);}int[] dp new int[maxnums1];for(int x:nums){dp[x] x;}int[] dp2 new int[maxnums1];dp2[0] dp[0];dp2[1] Math.max(dp[0],dp[1]);for(int i 2 ;i maxnums1;i){dp2[i] Math.max(dp2[i-1],(dp2[i-2]dp[i]));}return dp2[maxnums];} }746. 使用最小花费爬楼梯 给你一个整数数组 cost 其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用即可选择向上爬一个或者两个台阶。 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。 请你计算并返回达到楼梯顶部的最低花费。
   思路 动态规划跟之前爬楼梯类似这里我们考虑到爬到某一楼梯需要加上这个楼梯本身的代价就好了。 代码 class Solution {public int minCostClimbingStairs(int[] cost) {int n cost.length;if(n 2){return Math.min(cost[0],cost[1]);}int[] dp new int[n1];dp[0] cost[0];dp[1] cost[1];for(int i2;in;i){dp[i] Math.min(dp[i-1],dp[i-2])cost[i];}dp[n] Math.min(dp[n-1],dp[n-2]);return dp[n];} }815. 公交路线 给你一个数组 routes 表示一系列公交线路其中每个 routes[i] 表示一条公交线路第 i 辆公交车将会在上面循环行驶。 例如路线 routes[0] [1, 5, 7] 表示第 0 辆公交车会一直按序列 1 - 5 - 7 - 1 - 5 - 7 - 1 - … 这样的车站路线行驶。 现在从 source 车站出发初始时不在公交车上要前往 target 车站。 期间仅可乘坐公交车。 求出 最少乘坐的公交车数量 。如果不可能到达终点车站返回 -1 。 思路 采用 站点-路线 hashmap。用集合避免重复计算陷入死循环使用bfs求解 代码 class Solution {public int numBusesToDestination(int[][] routes, int source, int target) {MapInteger, SetInteger cs new HashMap();// 创建站点 路线hashmapfor (int i 0; i routes.length; i) {for (int j 0; j routes[i].length; j) {cs.computeIfAbsent(routes[i][j], k - new HashSet()).add(i 1);}}if (source target) return 0;if (!cs.containsKey(source) || !cs.containsKey(target)) return -1;// BFSDequeInteger deque new ArrayDeque();SetInteger vis new HashSet();for (Integer s : cs.get(source)) {for (int i : routes[s - 1]) {// 集合判重if (vis.add(i)) deque.addLast(i);}}int level 1;while (!deque.isEmpty()) {int size deque.size();while (size– 0) {int cur deque.pollFirst();if (cur target) return level;SetInteger s cs.getOrDefault(cur, null);if (s null) continue;for (Integer ss : s) {for (int i : routes[ss - 1]) {if (vis.add(i)) deque.addLast(i);}}}level;}return -1;} }844. 比较含退格的字符串 给定 s 和 t 两个字符串当它们分别被输入到空白的文本编辑器后如果两者相等返回 true 。# 代表退格字符。 注意如果对空文本输入退格字符文本继续为空。 思路 我们可以从后往前读遇到#我们则记下来然后进行跳过以此比较每一个字符 如果均没有问题则返回true 否则返回false 代码 class Solution {public boolean backspaceCompare(String s, String t) {int i s.length() - 1, j t.length() - 1;int skipS 0, skipT 0;while (i 0 || j 0) {while (i 0) {if (s.charAt(i) #) {skipS;i–;} else if (skipS 0) {skipS–;i–;} else {break;}}while (j 0) {if (t.charAt(j) #) {skipT;j–;} else if (skipT 0) {skipT–;j–;} else {break;}}if (i 0 j 0) {if (s.charAt(i) ! t.charAt(j)) {return false;}} else {if (i 0 || j 0) {return false;}}i–;j–;}return true;} }876. 链表的中间结点 给定一个头结点为 head 的非空单链表返回链表的中间结点。 如果有两个中间结点则返回第二个中间结点。 思路 先遍历计算链表的长度然后遍历到长度的一半输出其值。 代码 /** 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 middleNode(ListNode head) {int listLength 0;ListNode cur head;while(cur ! null){listLength;cur cur.next;}for(int i 0; ilistLength/2; i){head head.next;}return head;} }896. 单调数列 如果数组是单调递增或单调递减的那么它是 单调 的。 如果对于所有 i jnums[i] nums[j]那么数组 nums 是单调递增的。 如果对于所有 i jnums[i] nums[j]那么数组 nums 是单调递减的。 当给定的数组 nums 是单调数组时返回 true否则返回 false。 思路 根据判断nums[0] nums[nums.length-1]确定是否单调递增或者递减然后进行遍历判断。 代码 class Solution {public boolean isMonotonic(int[] nums) {if(nums.length 1) return true;if(nums[0] nums[nums.length-1]){for(int i 1; i nums.length; i){if(nums[i] nums[i-1]){return false;}}}else{for(int i 1; i nums.length; i){if(nums[i] nums[i-1]){return false;}}}return true;} }918. 环形子数组的最大和 给定一个长度为 n 的环形整数数组 nums 返回 nums 的非空 子数组 的最大可能和 。 环形数组 意味着数组的末端将会与开头相连呈环状。形式上 nums[i] 的下一个元素是 nums[(i 1) % n] nums[i] 的前一个元素是 nums[(i - 1 n) % n] 。 子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上对于子数组 nums[i], nums[i 1], …, nums[j] 不存在 i k1, k2 j 其中 k1 % n k2 % n 。 思路 没做出来 思路借鉴别别人的 跟之前最大子数组和类似在这里我们考虑到环状形状我们只需要在求一个最小数组和就好了 我们只需要考虑总的值减去最小数组和和最大数组和的较大值。为什么 证明一下最大子数组是环形的情况 max(前缀数组后缀数组) max(数组总和 - subarray) subarray指的是前缀数组和后缀数组中间的数组 数组总和 max(-subarray) 数组总和是不变的直接提出来 数组总和 - min(subarry) 。。。这个都懂吧把负号提出来max变成min 极端情况如果说这数组的所有数都是负数那么上面的公式还需要变一下因为这种情况对于上面的第一种情况sum会等于数组中的最大值而对二种情况sum0最小的子数组就是本数组total-total0。所以多加一个case判断最大子数组和是否小于0小于0直接返回该maxSubArray 代码 class Solution {public int maxSubarraySumCircular(int[] nums) {int fn -1;int res Integer.MIN_VALUE;int total 0, minSum nums[0], curMin 0;for(int a:nums){fn Math.max(fna,a);res Math.max(fn,res);curMin Math.min(curMin a, a);minSum Math.min(minSum, curMin);total a;}return res 0 ? Math.max(res, total - minSum) : res; } }994. 腐烂的橘子 在给定的 m x n 网格 grid 中每个单元格可以有以下三个值之一 值 0 代表空单元格 值 1 代表新鲜橘子 值 2 代表腐烂的橘子。 每分钟腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。 返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能返回 -1 。 思路 使用bfs再采用一个变量记橘子的个数就行了 。 代码 class Solution {public int orangesRotting(int[][] grid) {int m grid.length,n grid[0].length;QueueInteger queue new LinkedList();int countOrange 0;for(int i 0; i m; i){for(int j 0; j n; j){if(grid[i][j] 2){queue.add(i * n j);}else if(grid[i][j] 1){countOrange;}}}int time 0;while( !queue.isEmpty() countOrange 0 ){time;int size queue.size();for (int i 0; i size; i){int p queue.poll();int x p / n, y p % n;if (x - 1 0 grid[x - 1][y] 1) { // 上countOrange–; grid[x - 1][y] 2;queue.offer((x - 1) * n y);}if (x 1 m grid[x 1][y] 1) { // 下countOrange–;grid[x 1][y] 2;queue.offer((x 1) * n y);}if (y - 1 0 grid[x][y - 1] 1) { // 左countOrange–;grid[x][y - 1] 2;queue.offer(x * n y - 1);}if (y 1 n grid[x][y 1] 1) { // 右countOrange–;grid[x][y 1] 2;queue.offer(x * n y 1);}}}if(countOrange 0){return -1;}else{return time;}} }1014. 最佳观光组合 给你一个正整数数组 values其中 values[i] 表示第 i 个观光景点的评分并且两个景点 i 和 j 之间的 距离 为 j - i。 一对景点i j组成的观光组合的得分为 values[i] values[j] i - j 也就是景点的评分之和 减去 它们两者之间的距离。 返回一对观光景点能取得的最高分。 思路 跟买卖彩票类似 这里我们添加或减去j值即可 代码 class Solution {public int maxScoreSightseeingPair(int[] values) {int left values[0], res Integer.MIN_VALUE;for (int j 1; j values.length; j) {res Math.max(res, left values[j] - j);left Math.max(left, values[j] j);}return res;} }1046. 最后一块石头的重量 有一堆石头每块石头的重量都是正整数。 每一回合从中选出两块 最重的 石头然后将它们一起粉碎。假设石头的重量分别为 x 和 y且 x y。那么粉碎的可能结果如下 如果 x y那么两块石头都会被完全粉碎 如果 x ! y那么重量为 x 的石头将会完全粉碎而重量为 y 的石头新重量为 y-x。 最后最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下就返回 0。 思路 很简单第一想到的是排序做但其实这样的复杂度为n2logn因为你每次都要排序虽然后面是排序一个值就好了 但是算法复杂度也是n后面觉得最大堆更好但是我没用 代码 class Solution {public int lastStoneWeight(int[] stones) {Arrays.sort(stones);int len stones.length - 1;for (int i len; i 0; i–) {stones[len] stones[len] - stones[len - 1];stones[len - 1] 0;Arrays.sort(stones);}return stones[len];} }1137. 第 N 个泰波那契数 泰波那契序列 Tn 定义如下 T0 0, T1 1, T2 1, 且在 n 0 的条件下 Tn3 Tn Tn1 Tn2 给你整数 n请返回第 n 个泰波那契数 Tn 的值。 思路 同斐波那契数这里使用四个变量 代码 class Solution {public int tribonacci(int n) {int a 0,b 1,c 1,d 0;if(n 0){return 0;}if(n 2){return 1;}for(int i 3;i n;i){d a b c;a b;b c;c d;}return d;} }1250. 检查「好数组」 给你一个正整数数组 nums你需要从中任选一些子集然后将子集中每一个数乘以一个 任意整数并求出他们的和。 假如该和结果为 1那么原数组就是一个「好数组」则返回 True否则请返回 False。 思路 求最大公约数是否为1. 裴蜀定理: 若a,b是整数,且gcd(a,b)d那么对于任意的整数x,y,axby都一定是d的倍数 特别地一定存在整数x,y使axbyd成立。 a,b互质的充要条件是存在整数x,y使axby1. 代码 class Solution {public boolean isGoodArray(int[] nums) {int div nums[0];for(int num:nums){div gcd(div, num);if(div 1){return div 1;}}return div 1;}public int gcd(int num1,int num2){while (num2 ! 0) {int temp num1;num1 num2;num2 temp % num2;}return num1;} }1480. 一维数组的动态和 给你一个数组 nums 。数组「动态和」的计算公式为runningSum[i] sum(nums[0]…nums[i]) 。 请返回 nums 的动态和。 思路 这题我们遍历就好了 使用nums[n] nums[n-1]求出和即前缀和 复杂度分析 内存 O(1)O(1)O(1) 时间 O(n)O(n)O(n) 代码 class Solution {public int[] runningSum(int[] nums) {if(nums.length 1){return nums;}for(int i1;inums.length;i){nums[i] nums[i] nums[i-1];}return nums;} }1559. 二维网格图中探测环 给你一个二维字符网格数组 grid 大小为 m x n 你需要检查 grid 中是否存在 相同值 形成的环。 一个环是一条开始和结束于同一个格子的长度 大于等于 4 的路径。对于一个给定的格子你可以移动到它上、下、左、右四个方向相邻的格子之一可以移动的前提是这两个格子有 相同的值 。 同时你也不能回到上一次移动时所在的格子。比方说环 (1, 1) - (1, 2) - (1, 1) 是不合法的因为从 (1, 2) 移动到 (1, 1) 回到了上一次移动时的格子。 如果 grid 中有相同值形成的环请你返回 true 否则返回 false 。 思路 对于这道题我一开始考虑的是dfs然后我们标记一下以及访问的点如果重新回到访问的点。那我们判断为true否则为false。我们遍历整个数组得到所求。但是超时了。然后只能借鉴官方的做法–基于并查集的判断方法从左上角顶点开始同时向右和向下搜索若字母相同则合并。合并时若发现 x 和 y 的 parent 相同即形成环。 代码 dfs求解 class Solution {public boolean containsCycle(char[][] grid) {for(int i 0; i grid.length; i){for(int j 0; j grid[0].length; j){if(dfs(grid,grid[i][j],i,j,0)){return true;}}}return false;// 0 右 1 下 2 左 3 上}public boolean dfs(char[][] grid, char ch, int x, int y, int f){if(x 0 || y 0 || x grid.length || y grid[0].length) return false;// 查看 当前字母与初始字母是否相同if(grid[x][y] ! ch) return (char)(ch - 32) grid[x][y];// 将字符转换为大写表示这个点来过grid[x]y(ch - 32);return (f ! 2 dfs(grid,ch,x1,y,0)) || (f ! 3 dfs(grid,ch,x,y1,1)) ||(f ! 0 dfs(grid,ch,x-1,y,2)) || (f ! 1 dfs(grid,ch,x,y-1,3));} }并查集 class Solution { public boolean containsCycle(char[][] grid) {int h grid.length;int w grid[0].length;DSU dsu new DSU(w * h);for (int i 0; i h; i) {for (int j 0; j w; j) {char cur grid[i][j];// 向右搜索if (j 1 w cur grid[i][j 1]) {if (dsu.union(i * w j, i * w j 1)) {return true;}}// 向下搜索if (i 1 h cur grid[i 1][j]) {if (dsu.union(i * w j, (i 1) * w j)) {return true;}}}}return false;}class DSU {int[] parent;public DSU(int N) {parent new int[N];for (int i 0; i N; i) {parent[i] i;}}public int find(int x) {if (parent[x] ! x) {parent[x] find(parent[x]);}return parent[x];}public boolean union(int x, int y) {int parentX find(x);int parentY find(y);if (parentX parentY) {return true;}if (parentX parentY) {parent[parentY] parentX;} else {parent[parentX] parentY;}return false;}} }1567. 乘积为正数的最长子数组长度 给你一个整数数组 nums 请你求出乘积为正数的最长子数组的长度。 一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。 请你返回乘积为正数的最长子数组长度。 思路 我们可以使用0来分隔因为必须要正数然后我们分别统计每个子数组负数出现的次数以及最小舍去代价如果我们次数不为偶数那我们要舍去最小舍去代价的值 来得到子数组的正数长度最后求最大长度。 代码 class Solution {public int getMaxLen(int[] nums) {int pos 0;int res 0;for(int i0; inums.length; i){if(nums[i] 0){res Math.max(res, maxlen(nums, pos, i));pos i1;}}res Math.max(res,maxlen(nums, pos, nums.length));return res;}public int maxlen(int[] nums,int pos,int i){int ns 0;int posns Integer.MAX_VALUE;for(int jpos;ji;j){if(nums[j] 0){ns;posns Math.min(Math.min(j-pos1,posns),i-j);}}if(ns%2 0){return i-pos;}else{return i-pos-posns;}} }1706. 球会落何处 用一个大小为 m x n 的二维网格 grid 表示一个箱子。你有 n 颗球。箱子的顶部和底部都是开着的。 箱子中的每个单元格都有一个对角线挡板跨过单元格的两个角可以将球导向左侧或者右侧。 将球导向右侧的挡板跨过左上角和右下角在网格中用 1 表示。 将球导向左侧的挡板跨过右上角和左下角在网格中用 -1 表示。 在箱子每一列的顶端各放一颗球。每颗球都可能卡在箱子里或从底部掉出来。如果球恰好卡在两块挡板之间的 “V” 形图案或者被一块挡导向到箱子的任意一侧边上就会卡住。 返回一个大小为 n 的数组 answer 其中 answer[i] 是球放在顶部的第 i 列后从底部掉出来的那一列对应的下标如果球卡在盒子里则返回 -1 。 思路 这题看起来挺麻烦的但是做起来然后很容易的我们首先要判断怎么样才能卡住要么就是在边界要么就是两个相邻的不相等。那我们可以进行模拟设置rc值r值不断增加如果grid当前值唯一 则c1 否则c-1 代码 class Solution {int[][] g;int m;int n;public int[] findBall(int[][] grid) {g grid;m grid.length;n grid[0].length;int[] res new int[n];for(int i 0; i n; i){res[i] helpFindBall(i);}return res;}public int helpFindBall(int i){int c 0, r i;while(c m){int temp g[c][r] r;if(temp 0||temp n) return -1;if(g[c][r] ! g[c][temp]) return -1;r temp;c; }return r;} }2131. 连接两字母单词得到的最长回文串 给你一个字符串数组 words 。words 中每个元素都是一个包含 两个 小写英文字母的单词。 请你从 words 中选择一些元素并按 任意顺序 连接它们并得到一个 尽可能长的回文串 。每个元素 至多 只能使用一次。 请你返回你能得到的最长回文串的 长度 。如果没办法得到任何一个回文串请你返回 0 。 回文串 指的是从前往后和从后往前读一样的字符串。 思路 之前就想到哈希表来做我们只需要判断他的倒着的存不存在如果存在边4如果不存在则不管。除此之外需要考虑自身是否回文只需要考虑一个即可。这个对于不仅仅两个也适用考虑到优化我们使用一个26*26的数组即可 代码 class Solution {public int longestPalindrome(String[] words) {char[][] ch new char[26][26];int c1, c2;int l 0;for(String w : words) {c1 w.charAt(0) - a;c2 w.charAt(1) - a;if(ch[c2][c1] 0) {ch[c2][c1]–;l 4;continue;} ch[c1][c2];}for(int i 0; i 26; i) {if(ch[i][i] 0) {l 2;break;}}return l;} }LCP 39. 无人机方阵 在 「力扣挑战赛」 开幕式的压轴节目 「无人机方阵」中每一架无人机展示一种灯光颜色。 无人机方阵通过两种操作进行颜色图案变换 调整无人机的位置布局 切换无人机展示的灯光颜色 给定两个大小均为 N*M 的二维数组 source 和 target 表示无人机方阵表演的两种颜色图案由于无人机切换灯光颜色的耗能很大请返回从 source 到 target 最少需要多少架无人机切换灯光颜色。 注意 调整无人机的位置布局时无人机的位置可以随意变动。 思路 建立一个数组进行计数即可。 代码 class Solution {public int minimumSwitchingTimes(int[][] source, int[][] target) {int[] s new int[10001];for(int i0; isource.length; i){for(int j0;jsource[0].length; j){s[source[i][j]];}}for(int i0; isource.length; i){for(int j0;jsource[0].length; j){s[target[i][j]]–;}}int sumk 0;for(int k0;k10001;k){if(s[k]0){sumk - s[k];}}return sumk;} }