这些算法都可以在leetcode中找到
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
**注意：**最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
示例 1：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
示例 2：
输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。
示例 3：
输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
提示：
nums1.length == m + nnums2.length == n0 <= m, n <= 2001 <= m + n <= 200-109 <= nums1[i], nums2[j] <= 109**进阶：**你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗？
该算法的时间复杂度为O(m+n)，其中m和n分别为nums1和nums2的长度。
该算法的空间复杂度为O(m+n)，需要额外创建一个长度为m+n的数组来存储合并后的数组。
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
// 方法一：分析法（双指针）
int[] nums3 = new int[m + n];
int p1 = 0, p2 = 0, p3 = 0;
while (p1 < m && p2 < n) {
if (nums1[p1] <= nums2[p2]) {
nums3[p3] = nums1[p1];
p1++;
} else {
nums3[p3] = nums2[p2];
p2++;
}
p3++;
}
while (p1 < m) {
nums3[p3] = nums1[p1];
p1++;
p3++;
}
while (p2 < n) {
nums3[p3] = nums2[p2];
p2++;
p3++;
}
for (int i = 0; i < m + n; i++) {
nums1[i] = nums3[i];
}
}
}
该算法的时间复杂度为O((m+n)log(m+n))，其中m和n分别为nums1和nums2的长度，主要是排序算法的时间复杂度。
该算法的空间复杂度为O(1)，只需要常数级别的额外空间来进行数组操作。
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
// 方法二：直接合并后排序
for(int i = 0 ; i != n ; ++i){
nums1[m + i] = nums2[i];
}
Arrays.sort(nums1);
}
}
该算法的时间复杂度为O(m+n)，其中m和n分别为nums1和nums2的长度。
该算法的空间复杂度为O(1)，只需要常数级别的额外空间来进行双指针操作。
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
// 方法三：逆向双指针 (不需要多余的空间)
// 如果m和n都不为0的话，那nums1数组里面除了m个数后面全是0，肯定会多，
int p1 = m - 1 , p2 = n - 1;
int tail = m + n - 1;
int cur;
// 当二者元素都便利完之后才退出循环
while(p1 >= 0 || p2 >= 0){
// 当p1为-1也就是m为0，这时两种情况
// 1.特殊情况，二者都为空
// 2.当nums1的前m个元素遍历完
if(p1 == -1){
cur = nums2[p2--];
}else if(p2 == -1){
// 当nums2的前n个元素遍历完
cur = nums1[p1--];
}else if(nums1[p1] > nums2[p2]){
// 当我们的nums1的从后面遍历的元素比nums2后面遍历的元素大时
cur = nums1[p1--];
}else{
cur = nums2[p2--];
}
// 把两者中最大的或者没有遍历完毕的从nums1的后面往前放，这样不会覆盖原来的元素。
nums1[tail--] = cur;
}
}
}
给你一个数组 nums 和一个值 val，你需要 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以**「引用」**方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
示例 1：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
示例 2：
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
提示：
0 <= nums.length <= 1000 <= nums[i] <= 500 <= val <= 100该算法的时间复杂度为O(n)，其中n为数组的长度。
该算法的空间复杂度为O(1)，只需要常数级别的额外空间来进行双指针操作。
class Solution {
public int removeElement(int[] nums, int val) {
// 方法一：双指针
// 1.我们定义两个指针，两个都从0开始遍历，
// 2.使用左指针记录不为val的个数，
// 3.右指针来寻找val，当找到时我们的左指针停止移动，然后让右指针继续移动
// 4.这时把右指针遍历的值赋值给左指针，将会把所有的val覆盖掉，也会得到我们想要的结果
int len = nums.length , l = 0;
for(int r = 0 ; r < len ; ++r){
if(nums[r] != val){
nums[l] = nums[r];
++l;
}
}
return l;
}
}
该算法的时间复杂度为O(n)，其中n为数组的长度。
该算法的空间复杂度为O(1)，只需要常数级别的额外空间来进行双指针操作。
class Solution {
public int removeElement(int[] nums, int val) {
// 方法二：双指针优化
// 1.定义两个指针，两个指针分别在数组的两端
// 2.判断停止条件为左指针大于等于右指针
// 3.当左边的值等于val，就把右边的值对左边进行覆盖，然后把右边指针移动一步
// 4.当不等于时左边移动一位，用来记录不为value的值
int l = 0 , r = nums.length;
while(l < r){
if(nums[l] == val){
nums[l] = nums[r - 1];
r--;
}else{
l++;
}
}
return l;
}
}
给你一个 非严格递增排列 的数组 nums ，请你**** 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。k 。判题标准:
系统会用下面的代码来测试你的题解:
int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案
int k = removeDuplicates(nums); // 调用
assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}
如果所有断言都通过，那么您的题解将被 通过。
示例 1：
输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
示例 2：
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
提示：
1 <= nums.length <= 3 * 104-104 <= nums[i] <= 104nums 已按 非严格递增 排列该算法的时间复杂度为O(n)，其中n为数组的长度。
该算法的空间复杂度为O(1)，只需要常数级别的额外空间来进行双指针操作。
class Solution {
public int removeDuplicates(int[] nums) {
// 方法一：双指针
// 1.我们定义两个指针，左右指针都从1开始遍历
// 2.我们遍历一遍数组，
// 3.拿我们当前的遍历的值与上一个值做比较，不相等的时候让两个指针都往前移动，并且把右指针的值赋值给左指针
// 4.当相等的时候只让右指针移动，不做任何操作，
// 5.重点在于当相等之后遇到不相等的值就会出现把相等的值覆盖，让整个数组都没有相等的值
int n = nums.length;
if(n == 0){
return 0;
}
int r = 1 , l = 1;
while(r < n){
if(nums[r] != nums[r - 1]){
nums[l] = nums[r];
++l;
}
++r;
}
return l;
}
}
该算法的时间复杂度为O(n)，其中n为数组的长度。
该算法的空间复杂度为O(1)，只需要常数级别的额外空间来进行双指针操作。
class Solution {
public int removeDuplicates(int[] nums) {
// 方法二：双指针
// 1.首先判断数组是否为空或长度为 0，如果是，则直接返回 0，因为不会有重复元素需要移除。
// 2.初始化两个指针 p 和 q，初始值分别为 0 和 1。
// 3.进入循环，循环条件是 q 小于数组长度。
// 4.在循环中，判断当前左指针 p 指向的元素是否与右指针 q 指向的元素相等。如果相等，说明该元素是一个重复元素，可以直接跳过。
// 5.如果不相等，则说明该元素是一个新的非重复元素。将该非重复元素赋值给左指针下一个位置，并将左指针向右移动一位。
// 6.将右指针向右移动一位。
// 7.循环结束后，返回左指针 p 加 1 的值作为新数组的长度。
if(nums.length == 0 || nums == null){
return 0;
}
int p = 0 , q = 1;
while(q < nums.length){
if(nums[p] != nums[q]){
nums[p + 1] = nums[q];
++p;
}
++q;
}
return p + 1;
}
}
给你一个有序数组 nums ，请你**** 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
说明：
为什么返回数值是整数，但输出的答案是数组呢？
请注意，输入数组是以**「引用」**方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
示例 1：
输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]
解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3。 不需要考虑数组中超出新长度后面的元素。
示例 2：
输入：nums = [0,0,1,1,1,1,2,3,3]
输出：7, nums = [0,0,1,1,2,3,3]
解释：函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3。不需要考虑数组中超出新长度后面的元素。
提示：
1 <= nums.length <= 3 * 104-104 <= nums[i] <= 104nums 已按升序排列该算法的时间复杂度为O(n)，其中n为数组的长度。
该算法的空间复杂度为O(1)，只需要常数级别的额外空间来进行双指针操作。
class Solution {
public int removeDuplicates(int[] nums) {
// 方法一：双指针
// 1.首先判断数组的长度 n 是否小于等于 2，如果是，则直接返回数组的长度，因为不会有重复元素需要移除。
// 2.初始化两个指针 l 和 r，初始值都为 2。这是因为数组中的前两个元素是允许重复的。
// 3.进入循环，循环条件是 r < n，即右指针 r 小于数组长度。
// 4.在循环中，判断当前右指针指向的元素是否与左指针前两个位置的元素相等。如果不相等，说明该元素是一个新的非重复元素。
// 5.将该非重复元素赋值给左指针指向的位置，并将左指针向右移动一位。
// 6.不论是否相等，都将右指针向右移动一位。
// 7.循环结束后，返回左指针的值作为新数组的长度。
int n = nums.length;
if(n <= 2){
return n;
}
int l = 2 , r = 2;
while(r < n){
if(nums[r] != nums[l-2]){
nums[l] = nums[r];
++l;
}
++r;
}
return l;
}
}
该算法的时间复杂度为O(n)，其中n为数组的长度。
该算法的空间复杂度为O(1)，只需要常数级别的额外空间来进行数组操作。
class Solution {
public int removeDuplicates(int[] nums) {
// 方法二：通用保留k个相同数字
// 1.在 removeDuplicates 方法中，直接调用了 process 方法，并传入了数组 nums 和数字 2，表示保留两个相同数字。
// 2.process 方法中，使用了一个指针 u 来记录新数组中不重复元素的个数，并进行循环遍历原数组。
// 3.在循环中，首先判断指针 u 是否小于保留的相同数字个数 k，如果是，则直接将当前元素赋值给新数组的对应位置，并将指针 u 向右移动一位。
// 4.如果指针 u 大于等于 k，则需要判断当前元素是否与新数组中的前 k 个元素相等。如果不相等，则说明该元素是一个新的非重复元素，可以将其赋值给新数组的对应位置，并将指针 u 向右移动一位。
// 5.如果相等，则说明该元素是一个重复元素，可以直接跳过。
// 6.循环结束后，返回指针 u 的值作为新数组的长度。
return process(nums , 2);
}
private int process(int[] nums , int k){
int u = 0;
for(int x : nums){
if(u < k || nums[u-k] != x){
nums[u++] = x;
}
}
return u;
}
}
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：nums = [3,2,3]
输出：3
示例 2：
输入：nums = [2,2,1,1,1,2,2]
输出：2
提示：
n == nums.length1 <= n <= 5 * 104-109 <= nums[i] <= 109**进阶：**尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
该算法的时间复杂度为O(nlogn)，其中n为数组的长度，主要是排序算法的时间复杂度。
该算法的空间复杂度为O(logn)，主要是排序算法的空间复杂度。
class Solution {
public int majorityElement(int[] nums) {
// 方法一：随机排序
Arrays.sort(nums);
return nums[nums.length / 2];
}
}
该算法的时间复杂度为O(n)，其中n为数组的长度。
该算法的空间复杂度为O(1)，只需要常数级别的额外空间来存储计数器和候选元素。
class Solution {
public int majorityElement(int[] nums) {
// 方法二：投票算法
int count = 0 ;
Integer candidate = null;
for(int x : nums){
if(count == 0){
candidate = x;
}
count += candidate == x ? +1 : -1;
}
return candidate;
}
}
该算法的时间复杂度为O(n)，其中n为数组的长度。
该算法的空间复杂度为O(n)，需要额外创建一个Map来存储元素出现的次数。
class Solution {
public int majorityElement(int[] nums) {
// 方法三：计数法
// 使用了流式操作
// Arrays.stream(nums): 将int类型的数组转换为IntStream流对象
// .boxed(): 将IntStream流对象转换为Stream<Integer>流对象
// Collectors.groupingBy() 方法是 Stream API 中的一个收集器（Collector），它用于对流中的元素进行分组操作。
// Function.identity() 表示分组的依据为元素本身，即将流中的每个元素作为分组的键。
// Collectors.counting() 表示对每个分组进行计数，即统计每个分组中有多少个元素。
Map<Integer , Long> map = Arrays.stream(nums).boxed().collect(Collectors.groupingBy(Function.identity(),Collectors.counting()));
long mid = nums.length >> 1;
for(Map.Entry<Integer , Long> entry : map.entrySet()){
if(entry.getValue() > mid){
return entry.getKey();
}
}
return -1;
}
}
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
示例 2:
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]
提示：
1 <= nums.length <= 105-231 <= nums[i] <= 231 - 10 <= k <= 105进阶：
O(1) 的 原地 算法解决这个问题吗？该算法的时间复杂度为O(n)，其中n为数组的长度。
该算法的空间复杂度为O(n)，需要额外创建一个新的数组来存储旋转后的元素。
class Solution {
public void rotate(int[] nums, int k) {
// 方法一：创建一个新的数组
int n = nums.length;
int[] newArr = new int[n];
for(int i = 0 ; i < n ; ++i){
newArr[(i + k) % n] = nums[i];
}
System.arraycopy(newArr , 0 , nums , 0 , n);
}
}
该算法的时间复杂度为O(n)，其中n为数组的长度。
该算法的空间复杂度为O(1)，只需要常数级别的额外空间来进行翻转操作。
class Solution {
public void rotate(int[] nums, int k) {
// 方法二：数组翻转（举例 1 2 3 4 5）k = 2
k = k % nums.length;
// 1.第一步是我们让整个数组进行翻转（5 4 3 2 1）
reverse(nums , 0 , nums.length - 1);
// 2.第二步我们让k左边的所有数翻转（4 5 3 2 1）
reverse(nums , 0 , k-1);
// 3.第三步我们让k右边的所有数翻转（4 5 1 2 3）
reverse(nums , k , nums.length - 1);
}
public void reverse(int[] nums , int l , int r){
while(l < r){
int temp = nums[l];
nums[l] = nums[r];
nums[r] = temp;
++l;
--r;
}
}
}
给定一个数组 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 <= 1050 <= prices[i] <= 104该算法的时间复杂度为O(n)，其中n为数组的长度。
该算法的空间复杂度为O(1)，只需要常数级别的额外空间来存储最小价格和最大利润。
class Solution {
public int maxProfit(int[] prices) {
// 1.方法一：一次遍历,动态规划
int minpri = Integer.MAX_VALUE;
int maxpro = 0;
for(int i = 0 ; i < prices.length ; ++i){
if(prices[i] < minpri){
minpri = prices[i];
}else if(prices[i] - minpri > maxpro){
maxpro = prices[i] - minpri;
}
}
return maxpro;
}
}
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
示例 1：
输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
总利润为 4 + 3 = 7 。
示例 2：
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
总利润为 4 。
示例 3：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。
提示：
1 <= prices.length <= 3 * 1040 <= prices[i] <= 104该算法的时间复杂度为O(n)，其中n为数组的长度。
该算法的空间复杂度为O(1)，只需要常数级别的额外空间来存储最大利润和最小买入价格。
动态规划有时候确实难以理解，我们可以用其他方法，或者多做一些相关的题
class Solution {
public int maxProfit(int[] prices) {
// 动态规划
// 1.首先获取给定股票价格数组的长度，并初始化两个变量 p 和 p1，分别表示当前持有股票和当前不持有股票时的最大利润。
// 2.进入循环，循环变量 i 从 1 开始，遍历股票价格数组。
// 3.在循环中，计算当前持有股票时的最大利润 newP，取当前不持有股票时的最大利润 p 和上一次持有股票时的最大利润 p1 加上当前股票价格 prices[i] 的较大值。
// 4.计算当前不持有股票时的最大利润 newP1，取当前持有股票时的最大利润 p1 和上一次不持有股票时的最大利润 p 减去当前股票价格 prices[i] 的较大值。
// 5.更新持有股票和不持有股票时的最大利润，将 newP 赋值给 p，将 newP1 赋值给 p1。
// 6.循环结束后，返回持有股票时的最大利润 p。
int n = prices.length;
int p = 0 , p1 = -prices[0];
for(int i = 1 ; i < n ; ++i){
int newP = Math.max(p , p1 + prices[i]);
int newP1 = Math.max(p1 , p - prices[i]);
p = newP;
p1 = newP1;
}
return p;
}
}
该算法的时间复杂度为O(n)，其中n为数组的长度。
该算法的空间复杂度为O(1)，只需要常数级别的额外空间来存储最大利润和最小买入价格。
class Solution {
public int maxProfit(int[] prices) {
// 2.贪心算法
// 对于这个算法，求的解是只要有在右边的比左边的数大，那就可以算作买的股票，
// 所以此时我们就可以聚焦于前后两个相邻的数只要右边比左边大就在左边买，在右边卖
// 这样的效果和隔几个再卖有着相同的效果
int mark = 0;
int n = prices.length;
for(int i = 1 ; i < n ; ++i){
mark = mark + Math.max(0 , prices[i] - prices[i - 1]);
}
return mark;
}
}
给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
提示：
1 <= nums.length <= 1040 <= nums[i] <= 105时间复杂度：O(n) 遍历一次数组，对每个位置进行常数时间的操作。
空间复杂度：O(1) 代码中只使用了常数额外的空间，即int类型的变量n和r。
class Solution {
public boolean canJump(int[] nums) {
// 方法一：贪心算法
// 1.首先获取给定数组的长度，并初始化一个变量 temp 为 0，用于记录当前能够到达的最远位置。
// 2.进入循环，循环变量 i 从 0 开始，遍历数组。
// 3.在循环中，首先判断当前位置 i 是否小于等于 temp，如果是，则说明当前位置是可以到达的。更新 temp 的值为当前位置 i 和当前位置的值 nums[i] 相加的较大值。
// 4.接着判断是否已经到达了数组的最后一个位置 n - 1，即判断 n - 1 是否小于等于 temp。如果是，则说明能够到达最后一个位置，返回 true。
// 5.循环结束后，如果没有返回 true，则说明无法到达最后一个位置，返回 false。
int n = nums.length;
// 能够到达的最远距离
int r = 0;
for(int i = 0 ; i < n ; ++i){
// 如果i <= r 也就证明i这个位置是可达的，然后通过这个位置更新能够到达的最远距离
if(i <= r){
r = Math.max(r , i + nums[i]);
}
if(r >= n - 1){
return true;
}
}
return false;
}
}
时间复杂度：O(n) 在代码中，通过一个for循环遍历整个数组，从后往前进行处理。
空间复杂度：代码中只使用了常数额外的空间，即int类型的变量len和mark。
class Solution {
public boolean canJump(int[] nums) {
// 方法二：从后往前遍历，如果该位置数为0或者跳不过下一个元素 就会让标记++，来与下一位也就是左边一位元素继续比较，如果左边的都跳不过去那么标记就不会置于0，
int len = nums.length , mark = 0;
if(len == 1) return true;
for(int i = len - 2 ; i >= 0 ; --i){
if(mark < nums[i]){
// 这个判断表示能够跳过当前大坑
mark = 0;
}else{
// 这个判断表示当前位置跳不过这个大坑
mark++;
}
}
return mark == 0;
}
}
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
0 <= j <= nums[i]i + j < n返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
示例 1:
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
示例 2:
输入: nums = [2,3,0,1,4]
输出: 2
提示:
1 <= nums.length <= 1040 <= nums[i] <= 1000nums[n-1]时间复杂度：O(n^2) 在代码中，使用了两个嵌套的循环。外层循环的次数最多为n，内层循环的次数最多也为n。
空间复杂度：O(1) 代码中只使用了常数额外的空间，即int类型的变量mark和step。
通过这段代码，可以计算出到达数组末尾所需的最少步数。从左往右找到第一个能够到达当前位置的数作为第一步，然后依次遍历数组，就可以找到最短的距离。
class Solution {
public int jump(int[] nums) {
// 方法一：贪心（反向查找出出发位置）
// 1.首先获取给定数组的长度，并初始化变量 mark 为数组最后一个位置的索引，初始化步数 step 为 0。
// 2.进入循环，循环条件是 mark 大于 0，即还没有到达数组的起始位置。
// 3.在循环中，通过遍历数组从左往右，找到第一个能够到达 mark 位置的数作为第一步。
// 4.判断当前位置 i 加上当前位置的值 nums[i] 是否大于等于 mark。如果是，则说明该位置可以到达 mark，更新 mark 的值为当前位置 i，增加步数 step，并跳出内层循环。
// 5.内层循环结束后，继续外层循环，直到 mark 为 0，即到达数组的起始位置。
// 6.循环结束后，返回步数 step。
int mark = nums.length - 1;
int step = 0;
while(mark > 0){
for(int i = 0 ; i < mark ; ++i){
// 从左往右找到第一个到达mark位置的数作为第一步，然后依次遍历，就可以找到最短的距离
if(i + nums[i] >= mark){
mark = i;
step++;
break;
}
}
}
return step;
}
}
时间复杂度：O(n) 代码中使用了一个循环来遍历数组，循环次数最多为n-1次，其中n是数组的长度。
空间复杂度：O(1) 代码中只使用了常数额外的空间，即int类型的变量len、stepEnd、maxPosition和step。
通过这段代码，可以计算出到达数组末尾所需的最少步数。每次找到当前步长内最大的步数来作为下次步长来更新，并记录为走一步，依次遍历数组。
class Solution {
public int jump(int[] nums) {
// 方法二：贪心算法（正向查找出可到达的最大位置）
// 1.首先获取给定数组的长度，并初始化变量 stepEnd、maxPosition 和 step，分别表示当前步长结束位置、当前能够到达的最远位置和步数。
// 2.进入循环，循环变量 i 从 0 开始，遍历数组，循环条件为 i < len - 1，因为最后一个位置不需要再走步数。
// 3.在循环中，通过比较当前位置 i 加上当前位置的值 nums[i] 和当前能够到达的最远位置 maxPosition 的大小，更新maxPosition 的值为较大者。
// 4.接着判断是否需要进行下一步，即判断当前位置 i 是否等于步长结束位置 stepEnd。如果相等，则说明已经走完当前步长，需要更新下一步的步长和增加步数。
// 5.更新下一步的步长 stepEnd 为当前能够到达的最远位置 maxPosition。
// 6.增加步数 step。
// 7.循环结束后，返回步数 step。
int len = nums.length;
int stepEnd = 0 , maxPosition = 0 , step = 0;
// 我们从第一步开始，找到第一步步长内最大的步数作为下次步长来更新，并记录为走一步，依次遍历
for(int i = 0 ; i < len - 1 ; ++i){
// 还是找最大值来判断
maxPosition = Math.max(i + nums[i] , maxPosition);
// 如果到前一步所能到达的位置的话执行这个条件（找最小的步数）
if(i == stepEnd){
// 更新下一步的步长
stepEnd = maxPosition;
// 最少需要的步数
step++;
}
}
return step;
}
}
给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。
根据维基百科上 ：h 代表“高引用次数” ，一名科研人员的 h 指数 是指他（她）至少发表了 h 篇论文，并且每篇论文 至少 被引用 h 次。如果 h 有多种可能的值，h 指数 是其中最大的那个。
示例 1：
输入：citations = [3,0,6,1,5]
输出：3
解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。
由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3。
示例 2：
输入：citations = [1,3,1]
输出：1
这段代码的时间复杂度为 O(nlogn)，其中 n 是引用次数数组的长度。排序的时间复杂度为 O(nlogn)。而后面的循环需要遍历整个数组，时间复杂度为 O(n)。因此，总的时间复杂度为 O(nlogn)。
空间复杂度为 O(1)，没有使用额外的空间，只使用了常数级别的额外变量。
class Solution {
public int hIndex(int[] citations) {
// 方法一：排序
// 1.首先对引用次数数组进行排序，使用 Arrays.sort(citations) 方法将数组按照升序进行排序。
// 2.初始化变量 h 为 0，表示当前的 H 指数，初始化变量 len 为引用次数数组的长度减 1。
// 3.进入循环，循环条件是 len 大于等于 0 并且当前位置的引用次数大于 h。
// 4.在循环中，每次将 h 增加 1，表示当前的 H 指数增加 1，并将 len 减少 1，向前移动一位。
// 5.循环结束后，返回最终的 H 指数 h。
Arrays.sort(citations);
int h = 0, len = citations.length - 1;
while(len >= 0 && citations[len] > h){
++h;
--len;
}
return h;
}
}
这段代码的时间复杂度为 O(nlogn)，其中 n 是引用次数数组的长度。二分查找的时间复杂度为 O(logn)，而在每次查找中需要遍历整个引用次数数组，时间复杂度为 O(n)。因此，总的时间复杂度为 O(nlogn)。
空间复杂度为 O(1)，没有使用额外的空间，只使用了常数级别的额外变量。
class Solution {
public int hIndex(int[] citations) {
// 方法二：二分搜索
// 1.初始化变量 l 为 0，表示 H 指数的最小可能值（初始为 0），初始化变量 r 为引用次数数组的长度，表示 H 指数的最大可能值（初始为数组长度）。
// 2.进入循环，循环条件是 l 小于 r。
// 3.在循环中，首先计算中间值 mid，通过 (r + l + 1) >> 1 计算得到。这里使用位运算右移一位，相当于除以 2，这样可以取到中间偏右的值。
// 4.初始化变量 mark 为 0，表示引用次数大于等于 mid 的文章数量。
// 5.遍历引用次数数组，对每个引用次数进行判断，如果大于等于 mid，则将 mark 增加 1。
// 6.判断 mark 是否大于等于 mid，如果是，则说明当前的 mid 是一个有效的 H 指数，将 l 更新为 mid。否则，说明当前的 mid 不是一个有效的 H 指数，将 r 更新为 mid - 1。
// 7.循环结束后，返回最终的 H 指数 l。
int l = 0 , r = citations.length;
int mid = 0 , mark = 0;
while(l < r){
mid = (r + l + 1)>>1;
mark = 0;
for(int i = 0 ; i < citations.length ; ++i){
if(citations[i] >= mid) mark++;
}
if(mark >= mid){
l = mid;
}else{
r = mid - 1;
}
}
return l;
}
}
实现RandomizedSet 类：
RandomizedSet() 初始化 RandomizedSet 对象bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。
示例：
输入
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
输出
[null, true, false, true, 2, true, false, 2]
解释
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomizedSet.remove(2); // 返回 false ，表示集合中不存在 2 。
randomizedSet.insert(2); // 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomizedSet.getRandom(); // getRandom 应随机返回 1 或 2 。
randomizedSet.remove(1); // 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
randomizedSet.insert(2); // 2 已在集合中，所以返回 false 。
randomizedSet.getRandom(); // 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。
通过这段代码，可以实现插入、删除和随机获取元素的操作，并且可以保证插入和删除操作的时间复杂度为 O(1)。
时间复杂度：初始化和各项操作的时间复杂度都是 O(1)。
空间复杂度：O(n)，其中 n 是集合中的元素个数。存储元素的数组和哈希表需要 O(n) 的空间。
1.定义变量 nums 为保存元素的数组列表，定义变量 map 为保存元素和其在数组中的索引的键值对，定义变量 random 为随机数生成器。
2.在构造函数中进行初始化，将 nums 初始化为空列表，将 map 初始化为空映射，将 random 初始化为随机数生成器。
3.实现插入元素操作 insert，首先判断是否已经存在该元素，如果存在，则返回 false。如果不存在，则将该元素添加到 nums 列表的末尾，并将其在列表中的索引保存到 map 集合中，并返回 true。
4.实现删除元素操作 remove，首先判断是否存在该元素，如果不存在，则返回 false。如果存在，则获取该元素在 nums 列表中的索引，将 nums 列表中该索引位置的元素替换为列表最后一个元素，并将最后一个元素在列表中的索引更新到 map 集合中。然后删除 nums 列表的最后一个元素，并从 map 集合中删除该元素，并返回 true。
5.实现随机获取元素操作 getRandom，通过调用 random.nextInt(nums.size()) 方法随机获取一个在 [0, nums.size()) 范围内的整数，然后通过该整数获取对应位置的元素，并返回该元素。
class RandomizedSet {
// 方法一：变长数组+哈希表
List<Integer> nums;
Map<Integer , Integer> map;
Random random ;
public RandomizedSet() {
// 利用单例的懒汉进行初始化
nums = new ArrayList<Integer>();
map = new HashMap<Integer , Integer>();
random = new Random();
}
public boolean insert(int val) {
// 如果插入元素已经存在，就返回false
if(map.containsKey(val)){
return false;
}
// 如果不存在就保存到map集合的末尾,也添加到nums中为了获取元素的个数
// 由于map集合没法获取
int index = nums.size();
nums.add(val);
map.put(val , index);
return true;
}
public boolean remove(int val) {
if(!map.containsKey(val)){
return false;
}
//
int index = map.get(val);
int last = nums.get(nums.size() - 1);
nums.set(index , last);
map.put(last , index);
nums.remove(nums.size() - 1);
map.remove(val);
return true;
}
public int getRandom() {
// 获取元素个数的长度，然后再这个长度之间随机获取一个数，然后获取对应下表的key值
int randomIndex = random.nextInt(nums.size());
return nums.get(randomIndex);
}
}
/**
* Your RandomizedSet object will be instantiated and called as such:
* RandomizedSet obj = new RandomizedSet();
* boolean param_1 = obj.insert(val);
* boolean param_2 = obj.remove(val);
* int param_3 = obj.getRandom();
*/
因篇幅问题不能全部显示，请点此查看更多更全内容
Copyright © 2019- huatuo0.cn 版权所有 湘ICP备2023017654号-2
违法及侵权请联系：TEL:199 18 7713 E-MAIL:2724546146@qq.com
本站由北京市万商天勤律师事务所王兴未律师提供法律服务