import java.util.*; public class Solution { // 使用快速排序 public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) { ArrayList<Integer> list = new ArrayList<>(); // write code here if(k > input.length || k == 0) return list; quickSort(input,list,k,0,input.length-1); r...

import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param input int整型一维数组 * @param k int整型 * @return int整型ArrayList */ // 最优方法是使用优先队列（堆排序） // PriorityQueue，是一种内置的机遇堆排序的容器，分为大顶堆与小顶堆，大顶堆的堆顶为最大元素，其余更小的元素在堆下方，小顶堆与其刚好相反。且因为容器内部的次序基于堆排序，因此每次插入元素时间复杂度都是O(log2n)，而每次...

import java.util.*; public class Solution { // 找出数组中不去重的最小的k个数 // 思路：先排序，之后返回前k个数 // 本代码使用归并排序 public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) { // write code here ArrayList<Integer> list = new ArrayList<>(); if(k == 0 || input.length == 0) return list; int ...

import java.util.*; public class Solution { // 思路：归并排序的思想，分治之后排序合并 public int mod = 1000000007; public int mergeSort(int left, int right, int[] nums, int[] temp) { if (left >= right) { return 0; } int mid = (left + right) / 2; // 递归分治，左右划分合并 // 划分阶段：将带划分区间从中点划分成两部分，两部分进入递归继续划分，直到子数组长度为1 // 排序逻辑处理...

import java.util.*; public class Solution { // 思路：归并排序的思想，分治之后排序合并 public int mod = 1000000007; public int mergeSort(int left, int right, int[] nums, int[] temp) { if (left >= right) { return 0; } int mid = (left + right) / 2; // 递归分治，左右划分合并 int res = mergeSort(left, mid, nums, temp) + mergeSort(...

import java.util.*; public class Solution { // a->1,b->2,...z->26，给定一个数字，问有多少种译码的可能 // 思路：要注意数字范围是1-26，对于不在这个范围的不计入编码 // 如果，前一位的字符<=2，新加入的字符==0，f(n) = f(n - 1) // 如果，前一位的字符>2，新加入的字符==0，return f(n) = 0; // ------ 情况分割线 ------ // 如果，前一位的字符>=2，新加入字符，则译码的种类结果不会变，dp[i] = dp[i - 1]，这个也要写...

import java.util.*; public class Solution { // 找到字符串中最长的不包含重复字符的子字符串，返回最长子字符串的长度 // 思路：双指针遍历字符串，最后返回两个指针的差值就是最长字符串的长度 // 关键词：最长，不含重复字符 // 最长要靠双指针，重复字符要靠哈希表 // 在这段代码中，没有用到双指针，只用了一个指针回溯来遍历整个字符串，通过哈希表本身不含重复元素的性质，key为字符，value为该字符对应的index；当遇到重复的字符，就找到对应字符在当前记录的子字符串的位置，之后将该位置之前的所有字符remove。之后有一个关键点在于，当把重复位...

import java.util.*; public class Solution { public int maxValue (int[][] grid) { int[][] dp = new int[grid.length][grid[0].length]; // 处理只有一行或者一列的情况 if(grid.length == 1){ int res = 0; for(int i = 0;i<grid[0].length;i++){ res += grid[0][i]; } return res; } if(grid[0].length == 1){ int res = 0; for...

import java.util.*; public class Solution { public int[] FindGreatestSumOfSubArray (int[] array) { // write code here // 题目要求返回长度最长的一个，则需要使用left、right记录子数组的起始 // 需要更新最大值的时候（要么子数组和最大，要么子数组和相等下区间要更长）顺便更新最终的区间收尾，这样来维护子数组的长度是最长的 int[] dp = new int[array.length]; dp[0] = array[0]; int maxsum = dp[0]; // ...

import java.util.*; public class Solution { // 动态规划 public int[] dp = new int[23]; public int jumpFloorII (int number) { // write code here // 先求出动态规划方程，对于最后一级台阶，我们可以由倒数第二级台阶跳1步，也可以由倒数第三级台阶跳两步，这样就相对于将楼梯倒过来，f(n) = f(n-1) + f(n-2) + ... + f(n-n+1)+f(n-n) = f(0) + f(1) +++ f(n-1);又f(n-1) = f(n-2) +++ f...

import java.util.*; public class Solution { // 时间复杂度要求O(logn)，使用二分查找 // 因为数组原本是有序的，旋转之后，分为了两部分 // 前面部分一定都大于后面部分 // 这时使用二分查找，如果nums[mid]的值大于nums[right]，则表示测试mid在前一部分，需要将left = mid + 1 // 如果nums[mid] < nums[right]，则表示mid在后面一部分，需要将right = mid; // 如果nums[mid] == nums[right]，需要不断缩小right的值，来缩小氛围 public...

import java.util.*; public class Solution { // 数字在升序数组中出现的次数 // 思路：因为数组是升序排列的，所以只需要找到目标值的最左侧索引和最右侧索引就可以找到整个目标值出现的次数 // 因为数组中全是整数，所以可以考虑用二分查找法找到k+0.5和k-0.5出现的位置，两者相减就是k出现的次数 public int GetNumberOfK (int[] nums, int k) { // write code here return binarySearch(nums,k+0.5) - binarySearch(nums,k-0.5); } ...

import java.util.*; public class Solution { public boolean flag = false; public int lowestCommonAncestor (TreeNode root, int p, int q) { // write code here ArrayList<Integer> listP = new ArrayList<>(); ArrayList<Integer> listQ = new ArrayList<>(); dfs(root,listP,p); flag = fa...

import java.util.*; public class Solution { // 给定一颗二叉树找到对应两个节点的最近公共祖先 // 要使用路径记录的话，需要用到回溯的方法，回溯就是出栈 public boolean flag = false; public int lowestCommonAncestor (TreeNode root, int o1, int o2) { // write code here ArrayList<Integer> path1 = new ArrayList<>(); ArrayList<Integer> pat...