LeetCode 27+LeetCode 35 讲解(姊妹篇)

简介: LeetCode 27+LeetCode 35 讲解(姊妹篇)

LeetCode 27


题目


给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。
不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。


思路分析


(1)首先可以观察到这是一个去除数组类相同元素的一个算法题,在本题中,我们可以通过for循环加上if匹配对数组进行逐项比较,最终得出想要的结果

(2)再仔细观察这题,我还想到了遍历数组长度,因为在LeetCode 1里面我们遇到过类似的情景,当时是用nums数组的值去跟目标值target作比较从而去重

(3)双指针思想


代码实现


class Solution {
    public int removeElement(int[] nums, int val) {
        int n = nums.length;
        int left = 0;
        for (int right = 0; right < n; right++) {
            if (nums[right] != val) {
                nums[left] = nums[right];
                left++;
            }
        }
        return left;
    }
}


代码详解


(1)首先定义一个n变量用于存储数组nums的长度

(2)运用双指针的思想,定义左指针left及右指针right,由于左指针较慢,右指针较快,所以采用for循环去遍历右指针,如果右指针中的元素与目标值val不一样,则进行一次赋值操作,将右指针的值赋给左指针,最终返回左指针的长度

(3)题目整体不难,主要参照LeetCode 26的思想去做,很容易就能做出来


LeetCode 35


题目


给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。


思路分析


(1)这一条仍然是一条算法题目,在数组算法的基础上,加上了索引的概念,但是这个无伤大雅,不会影响读者做题

(2)这一题本质上仍然是数组元素匹配与target的问题


代码实现


class Solution {
public int searchInsert(int[] nums, int target) {
    for(int i = 0; i < nums.length;i++){
        if(nums[i] >= target){
            return i;
        }
    }
    return nums.length;
}
}


代码详解


(1)此题方法比较新颖,运用for循环来遍历数组nums的长度

(2)如果数组nums里面的i元素比目标值要大,则返回元素i的值,如果数组nums里面的i元素比目标只要小,则返回数组nums的长度

相关文章
|
5月前
leetcode-472. 连接词
leetcode-472. 连接词
48 0
leetcode 827 最大人工岛
leetcode 827 最大人工岛
58 0
leetcode 827 最大人工岛
LeetCode 389. 找不同
给定两个字符串 s 和 t,它们只包含小写字母。
70 0
|
算法 Java
一和零(LeetCode 474)
一和零(LeetCode 474)
93 0
leetcode第54题
在 leetcode 的 solution 和 discuss 看了下,基本就是这个思路了,只是实现上有些不同,怎么用来标记是否走过,当前方向,怎么遍历,实现有些不同,但本质上是一样的。就是充分理解题意,然后模仿遍历的过程。
100 0
leetcode第54题
|
存储
leetcode第52题
可以发现对于同一条副对角线,row + col 的值是相等的。 对于同一条主对角线,row - col 的值是相等的。 我们同样可以用一个 bool 型数组,来保存当前对角线是否有元素,把它们相加相减的值作为下标。 对于 row - col ,由于出现了负数,所以可以加 1 个 n,由 [ - 3, 3 ] 转换为 [ 1 , 7 ] 。
leetcode第52题
|
存储
leetcode第57题
和上一道可以说是一个问题,只不过这个是给一个已经合并好的列表,然后给一个新的节点依据规则加入到合并好的列表。 解法一 对应 56 题的解法一,没看的话,可以先过去看一下。这个问题其实就是我们解法中的一个子问题没看的话,可以先过去看一下。这个问题其实就是我们解法中的一个子问题, 所以直接加过来就行了
leetcode第57题
|
机器学习/深度学习
leetcode第50题
求幂次方,用最简单的想法,就是写一个 for 循环累乘。 至于求负幂次方,比如 2^{-10}2−10,可以先求出 2^{10}210,然后取倒数,1/2^{10}1/210 ,就可以了 double mul = 1; if (n > 0) { for (int i = 0; i < n; i++) { mul *= x; } } else { n = -n; for (int i = 0; i < n; i++) { mul *= x; } mul = 1 / mul; }
leetcode第50题
|
人工智能 算法
leetcode第41题
对于这种要求空间复杂度的,我们可以先考虑如果有一个等大的空间,我们可以怎么做。然后再考虑如果直接用原数组怎么做,主要是要保证数组的信息不要丢失。目前遇到的,主要有两种方法就是交换和取相反数。
leetcode第41题