为了保持自己的头脑能够快速的运转，今天在 leetcode.cn 上面开启了一个专栏，叫做 《面试经典 150 题》， 看自己能刷到第几天。😎

<!-- ↑ 你也可以使用 html -->
<template>
  <!-- vue 模板 -->
  <h2>todo 使用vue嵌入vuex组件实现todo列表</h2>
  ...
</template>
<script>
export default {
  // vue 组件
};
</script>
<style>
/* css 代码 */
</style>

1、合并两个有序数组（20240203 更新）

88. 合并两个有序数组

上面就是题目的链接，简单描述就是题目给了两个非递减的数组 nums1 和 nums2，将这两个数组从小到大合并，函数没有返回值，最终的结果是 num1。

num1 数组的长度是两个数组的长度总和，后面没有的以 0 占位。

这里有三种方式解决

• 就是将两个数组合并，合并之后Arrays.sort(nums1);
• 第二种就是新建一个 temp 数组和两个数组指针来动态的比较那个小，小的就先放到 temp 里面，最后把 temp 赋值给 nums1
• 第三种就是从后往前，将大的值放到 nums1 的后面（nums1 后面不是有部分是 0 占位的吗，就是这样来使用），如下图：

示例代码：

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // 从后往前比较，这样不用新建数组
        int i=m-1, j=n-1;  // 这里需要注意，m是nums1的长度，不是总长
        int index = m+n-1;
        while(i>=0 && j>=0){
            if(nums1[i] >= nums2[j]){
                nums1[index--] = nums1[i--];
            }
            else{
                nums1[index--] = nums2[j--];
            }
        }
        // 有一方不为空, 如果是i不为空，不用处理。
        if(j>=0){
            for(int t=j; t>=0;t--){
                nums1[index] = nums2[t];
                index--;
            }
        }
    }
}

2、移除元素（20240204 更新）

题目地址：27.移除元素

题目给出一个数组 nums 和一个值 val，原地移除所有数值等于 val 的值，并返回移除后数组的新长度，不要使用额外的数组空间，元素的顺序可以改变，不需要考虑后超出新长度的元素。

这个问题，最常见的解法就是遍历数组，把与 val 相等的值赋值成一个很大的数，最后在排一下顺序就可以了，但是这样的话，消耗时间较长。

我们利用双指针的原理，定义左右指针都指向数组头部，移动有指针，如果有指针的值不等于 val 的话，就把有指针的值赋值给左指针；

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;
    }
}

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        left  = 0
        for right in range(len(nums)):
            if nums[right] != val:
                nums[left] = nums[right]
                left += 1
        return left

不得不说 python 是真的慢，相同的思路，代码大致都是一样的，在 leetcode 里面，java 耗时 0ms， python 耗时 35ms。

3、删除有序数组中的重复项（20240205 更新）

今天来到了坚持的第三天，今天要解决的问题是 leetcode 的 26 题，删除有序数组中重复项

这里推荐 labuladong 写的一篇关于双指针的文章，相当醍醐灌顶 双指针技巧秒杀七道数组题目

题目给出一个非严格递增排列的数组 nums， 原地删除重复出现的元素，是每个元素只出现一次，返回删除后数组的长度，保持元素原来的相对顺序，然后返回 nums 中唯一元素的个数。

这里力扣官网给出了三个提示，我也简单说一下。

In this prosblem, the key point to focus on is the input array being sorted. As far as duplicate elements are concerned, what is their positing in the array whens the given array is sorted? Look at the image above for the answer. If we know the positing of one of the elements, do we also know the positing of all the duplicate elements?

重要的点就是相同的是挨着的。

提示 2：

We need to modify the array in-place and the size of the final array would potentially be smaller than the size of the input array. So wo ought to use a two-pointer approach here. One, that would keep track of the current element in the original array and another one for just the unique elements.

我们需要原地修改数组，最后的数组可能比输入的数组大小要小。我们应该使用双指针， 一个指向当前元素，一个指向其他不同的元素。

提示 3

Essentially, once an elements is encountered, you simply need to bypass its duplicates and move on the next unique element.

就是说一旦遇到相同的就跳过，移动到下一个不同的元素上。

所以我们用双指针来解决，两个指针起点都指向数组的头部，如果左指针和右指针指向值相同，右指针就往后移动一位，知道两者数值不同，这个时候将右指针的值赋值到 left+1 的位置，这样就实现了统一逻辑，最后返回 left+1， 表示剩余元素的长度。

简单代码如下：

class Solution {
    public int removeDuplicates(int[] nums) {
        // 快慢指针来解决
        int left=0, right = 0;
        int n = nums.length;
        while(right<n){
            if(nums[left] == nums[right]){
                right++;
            }
            else{
                nums[++left] = nums[right++];
            }
        }
        return left+1;  //这里判断不出来的话，可以带入简单的实际数据看一下，就知道这里返回left 还是left+1；
    }
}

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        left, right = 0, 0
        n = len(nums)
        while right<n:
            if nums[left] == nums[right]:
                right+=1
            else:
                left += 1
                nums[left] = nums[right]
                right += 1
        return left +1

4、删除有序数组中的重复项 II（20240206 更新）

删除有序数组中的重复项 II

想在是第二天早上 00:28， 昨天飘了一天，出去跑步了，没顾上算法，现在忙急忙慌的做一下。

今天做昨天的升级版。这回重复数字要保留两个了，还是使用双指针，之前比较的是左指针当前位置的数，这道题需要比较左指针前两个位置的数，代码如下。

class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        if(n<=2){
            return n;
        }
        int left=2, right=2;
        while(right<n){
            if(nums[left-2] != nums[right]){  // 这里left-2就是判断right值与left前两个值是否相同，如果不同就替换，如果不同right++，然后继续比较。
                nums[left] = nums[right];
                left++;
            }
            right++;
        }
        return left;
    }
}

5、多数元素（20240207 更新）

169. 多数元素

题目给出一个数组 nums，返回数组中多数元素，就是元素出现的次数大于 n/2 的元素？

（为什么排序后， nums[n/2]是从数？）

求众数之 Boyer-Moore 投票算法

后面待补充！！

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }
}

6、轮转数组（20240208 更新）

189. 轮转数组

今天来处理一下 leetcode 第 189 题，轮转数组。

题目的大概意思就是，给定一个数组 nums， 将数组中所有的元素先右轮转 k 个位置，然后给出了实例，可以到 leetcode 上面查看。

最简单的办法就是新建一个临时数组来存放轮转后的结果，然后在赋值给 nums。

class Solution {
    public void rotate(int[] nums, int k) {
        // 计算出来下标
        int n = nums.length;
        int[] tmp = new int[n];

        for(int i=0;i<n;i++){
            // index
            int index = (i + k) % n;
            tmp[index] = nums[i];
        }
        System.arraycopy(tmp, 0, nums, 0, n);
    }
}

还有一种方式就是先将 nums 反转，然后在反转 nums[0, k-1]的元素，最后反转 nums[k, n-1]这样就实现了轮转 nums 的目的。

class Solution {
    public void rotate(int[] nums, int k) {
        k %= nums.length;  // 去掉倍数k的影响
        reverse(nums, 0, nums.length-1);
        reverse(nums, 0, k-1);
        reverse(nums, k, nums.length-1);

    }

    public void reverse(int[] nums, int start, int end){
        while(start<end){
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start += 1;
            end -= 1;
        }
    }
}

7、买卖股票的最佳时机（20240209 更新）

121.买卖股票的最佳时机

今天是 10 号，今天来认真学习一下这个买卖股票的最佳时机。

题目大概的意思就是给定一个数组 price， 他的第 i 个元素 price[i]表示一支股票第 i 天的价格。

只能选择某一天买入这只股票，并选择在未来的某个不同的日子卖出该股票，设计一个算法获取最大的利润。像是题目给出的 prices 为[7,1,5,3,6,4], 最大的利润就是在第 1 天买入股票，价格为 1，在第 4 天的时候卖出股票杰价格为 6，例如为 6-1 等于 5 为最大利润。

定义 dp 三位数组 dp[n-1][k][0]、dp[n-1][k][1]

dp[n-1][k][0] 表示第 n-1 天还有 k 次交易计划的情况下我们不持有股票

dp[n-1][k][1] 表示第 n-1 天还有 k 次交易机会的情况下我们持有股票

状态转换方程：

dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i])

表示第 i 天还有 1 次交易机会的情况下我们不持有股票，这个时候我们可能昨天就没有持有，或者是昨天我们持有，但是我们今天卖出去了，这个时候就获得了第 i 天的钱， 去最大值。

dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][0][0] - prices[i])

表示第一天持有股票，有两种可能，第 i-1 天我们就持有股票，或者是昨天么有持有今天购入。

base case：

dp[-1][...][0]= 0 因为 i 是从 0 开始的，所以 i=-1 以为着还么有开始，这个时候利润当然为 0

dp[-1][...][1] = -infnity 还没有开始，求最大值，初始化为最小值

dp[...][0][0] k 从 1 开始，所以 k 为 0 时根本不允许交易，这个时候利润为 0

dp[...][0][1] 不允许交易情况下，不可能持有股票，初始化为最小值。

class Solution {
    public int maxProfit(int[] prices) {
        int k = 1;
        int n = prices.length;
        int[][] dp = new int[n][2];

        for(int i = 0;i<n;i++){
            if(i==0){
                dp[0][0] = 0;  // 如果i=0 i-1是不合格下标
                dp[0][1] = -prices[i];  // i=0 时持有股票初始化最小
                continue;
            }
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i-1][1], -prices[i]);
        }
        return dp[n-1][0];

    }
}

知识点

1、什么是状态机？

2、什么是 DP table？

参考

一个方法团灭 leetcode 股票问题

8、 买卖股票的最佳时机 II（20240210 更新）

122. 买卖股票的最佳时机 II

与买卖股票的最佳时机 1 的最大的不同就是，我们的交易次数是没有限制的。

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][2];
        for(int i=0;i<n;i++){
            if(i == 0){
                dp[0][0] =0;
                dp[0][1] = -prices[i];
                continue;
            }
            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[n-1][0];

    }
}

为什么两个状态转换是一样的，但是写出来的代码有一点点的差距，就是dp[i-1][0]为什么在 1 中就是 0， 在 2 中就需要写出来？

9、跳跃游戏（20240211 更新）

leetcode 原题目地址 55. 跳跃游戏

题目给出一个非负整数 nums， nums[i]表示能跳的距离，最初位于数组的第一个下标，判断是否能达到最后一个下标，如果可以返回 true，否则返回 false

遍历数组，每次判断能跳的最远距离。

class Solution {
    public boolean canJump(int[] nums) {
        // 动态规划
        // 判断最多能跳多远，是否超过nums的最后一个下标
        int n  = nums.length;
        int faster = 0;
        for(int i=0;i<n-1;i++){  // 为什么这里要n-1？  最后一个下标没含义，能到最后一个就直接返回ture了
            faster = Math.max(faster, i + nums[i]); // 为什么这里要i+nums[i]? 因为是判断能跳的最远的距离，是从当前下标开始往后跳nums[i]
            if(faster<=i){  // 这里为什么要<= i? 如果faster等于i表示最远就能当i这里，没办法在跳了，也需要返回false
                return false;
            }
        }
        return faster>=n-1; //
    }
}

11、H 指数（20240213 更新）

原题目地址：274. H 指数

昨天的题目做了，但是没有总结出来，是一个动态规划的题目，算是比较难，后面有时间在补充，今天说说 H 指数这道题。

这道题的话，对于题目的理解需要花一点精力。题目给出一个整数数组 citation， citation[i]表示 i 处论文的引用次数，求最大的 h 指数。

h 指数的定义：一名科研人员的 h 指数是指他至少发表 h 篇论文，并且至少 h 篇论文被引用次数大于等于 h，如果 h 有多种可能，h 指数是其中最大的那个。

我们先将给出的 citation 进行排序，初始化 h 为 1，然后从后往前遍历，如果 citation[i] >= h，就表示至少有 h 篇论文，被引用的次数不小于 h， 然后 h 加 1， 继续往前遍历，返回 h-1

class Solution {
    public int hIndex(int[] citations) {
        Arrays.sort(citations);
        // 初始化h为1，最后返回h-1
        // 从后往前遍历
        int i = citations.length-1, h=1;
        while(i>=0 && citations[i]>=h){
            h++;
            i--;
        }
        return h-1;  // 返回h-1
    }
}

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        citations = sorted(citations)
        i, h = len(citations)-1, 1
        while i>=0 and citations[i]>=h:
            h, i = h+1, i-1
        return h-1

/**
 * @param {number[]} citations
 * @return {number}
 */
var hIndex = function (citations) {
  // 排序
  citations.sort((a, b) => a - b);
  let i = citations.length - 1,
    h = 1;
  while (i >= 0 && citations[i] >= h) {
    h++;
    i--;
  }
  return h - 1;
};

12、O(1)时间插入、删除和获取随机元素

原题目地址：380. O(1) 时间插入、删除和获取随机元素

题目要求在时间复杂度O(1)的情况下实现功能插入、删除、获取随机元素

这样的话一种数据结构是没办法完成的，数组在插入、获取随机元素是可以做到O(1)，但是删除的话，会移动后面的元素到当前位置，这个没办法，可以用Map来实现，定义元素与下标的关系。

插入：正常插入到数组尾部

删除：删除元素与最后一个元素进行交换，然后删除最后一个元素

获取：获取指定随机数下标元素

class RandomizedSet {
    // 存储元素的值
    List<Integer> nums;
    // 记录每个元素对应在nums中的索引
    Map<Integer, Integer> valToIndex;

    public RandomizedSet() {
        nums = new ArrayList<>();
        valToIndex = new HashMap<>();
    }
    
    public boolean insert(int val) {
        // 如果val存在就返回false
        if(valToIndex.containsKey(val)){
            return false;
        }
        // 如果不存在就插入到nums尾部， 并记录val对应的索引值。
        valToIndex.put(val, nums.size());
        nums.add(val);
        return true;
    }
    
    public boolean remove(int val) {
        if(!valToIndex.containsKey(val)){
            return false;
        }
        int index = valToIndex.get(val);
        // 把最后一个元素的索引修改成index
        valToIndex.put(nums.get(nums.size()-1), index);  
        // 把nums最后一个和index两个元素进行交换
        Collections.swap(nums, index, nums.size()-1);
        nums.remove(nums.size()-1);  // remove掉最后一个元素
        valToIndex.remove(val); // 把Map里面key为val的也删掉
        return true;
    }
    
    public int getRandom() {
        int index = (int)(Math.random()*nums.size());
        return nums.get(index);
    }
}

class RandomizedSet:

    def __init__(self):
        self.nums = []
        self.val_to_index = {}

    def insert(self, val: int) -> bool:
        if val in self.val_to_index:
            return False
        n = len(self.nums)
        self.val_to_index[val] = n
        self.nums.append(val)
        return True

    def remove(self, val: int) -> bool:
        if val not in self.val_to_index:
            return False
        index = self.val_to_index.get(val)
        self.val_to_index[self.nums[-1]] = index
        # 交换两个的位置
        self.nums[index], self.nums[-1] = self.nums[-1], self.nums[index]
        self.nums.pop()
        del self.val_to_index[val]
        return True

    def getRandom(self) -> int:
        return random.choice(self.nums)

var RandomizedSet = function() {
    this.nums = [];
    this.valToIndex = {};
};

/** 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.insert = function(val) {
    if(this.valToIndex[val] !== undefined){
        return false;
    }
    this.valToIndex[val] = this.nums.length;
    this.nums.push(val);
    return true;
};

/** 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.remove = function(val) {
    if(this.valToIndex[val] === undefined){
        return false;
    }
    var index = this.valToIndex[val];
    this.valToIndex[this.nums[this.nums.length-1]] = index;
    [this.nums[index], this.nums[this.nums.length-1]] = [this.nums[this.nums.length-1], this.nums[index]];
    this.nums.pop();
    delete this.valToIndex[val];
    return true;
};

/**
 * @return {number}
 */
RandomizedSet.prototype.getRandom = function() {
    return this.nums[Math.floor(Math.random() * this.nums.length)];
};

注意点

在使用python解题的时候，有几个方便的知识点需要掌握

1、就是我们获取最后一个元素，不用获取到数组长度在-1， 比如nums[len(nums)-1], 可以直接使用nums[-1]来获取最后一个元素

2、python数组中交换两个变量的值，可以直接 a,b = b,a

3、数组删除最后一个元素nums.pop(), 字典删除key del val_to_index[key]

在使用js解题的时候，掌握这几个知识点

1、var obj， 用this指向当前类， 例如this.nums = []; 在获取的时候也用this指向。

2、判断为空是用undefined来表示

3、向数组里面添加数据用nums.push(val), 删除和python一样，this.nums.pop()

4、添加对象属性this.valToIndex[val] = value, 删除对象属性 delete this.valToIndex[val];

13、除自身以外数组的乘积（20240215更新）

原题目地址：238. 除自身以外数组的乘积

最开始的想法就是先整体算出来每个元素的乘积结果，然后在除以对应坐标的值，但是如果有0的存在这样就不好使了，况且题目中提到不能使用除法。

初始化两个空数组 L 和 R。对于给定索引 i，L[i] 代表的是 i 左侧所有数字的乘积，R[i] 代表的是 i 右侧所有数字的乘积。 我们需要用两个循环来填充 L 和 R 数组的值。对于数组 L，L[0] 应该是 1，因为第一个元素的左边没有元素。对于其他元素：L[i] = L[i-1] * nums[i-1]。 同理，对于数组 R，R[length-1] 应为 1。length 指的是输入数组的大小。其他元素：R[i] = R[i+1] * nums[i+1]。 当 R 和 L 数组填充完成，我们只需要在输入数组上迭代，且索引 i 处的值为：L[i] * R[i]。

来源：力扣官方题解

class Solution {
    public int[] productExceptSelf(int[] nums) {
        // 不是使用除法
        // 将i两边的数据分开计算， answer[i] = L[i] * R[i]
        int length = nums.length;
        
        int[] L = new int[length];  
        int[] R = new int[length];

        int[] answer = new int[length];
        L[0] = 1;
        for(int i=1;i<length;i++){
            L[i] = L[i-1] * nums[i-1];
        }
        R[length-1] = 1;
        for(int i=length-2;i>=0;i--){  // 这里需要从后往前遍历，因为base case 在最后
            R[i] = R[i+1] * nums[i+1];
        }
        for(int i=0;i<length;i++){
            answer[i] = L[i]*R[i];
        }
        return answer;
    }
}

14、加油站（20240216更新）

题目原地址： 134. 加油站

对于这道题理解就是，题目给出一个gas数组，gas[i]表示到加油站了可以加的油量；一个cost数组，cost[i] 表示到到i+1个加油站需要花费cost[i]的油。

我们可以得出一个新数组，用来存放当前加油站到下一个加油站剩余的油量sum = gas[i] - cost[i]

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int sum = 0;
        for(int i=0;i<n;i++){
            sum += (gas[i] - cost[i]);
        }
        if(sum<0){
            return -1;
        }
        int tank = 0;
        int start = 0;
        // 如果从i不能开到j的话，k属于[i,j]就不能走到j
        for(int i=0;i<n;i++){
            tank += (gas[i] - cost[i]);
            if(tank<0){
                tank = 0;
                start = i + 1;
            }
        }
        return start == n? 0: start;
    }
}

15、（20240217更新）

16、（20240218更新）

17、罗马数字转整数（20240219更新）

原题目地址：13. 罗马数字转整数 简单

这个题目就是将罗马数据转化成整数。给大家看一张图，大家应该大致就懂了。

当s[i] 对应值小于s[i+1]的时候， 加上负对应值，然后将逻辑实现出来就可以了。

class Solution:
    def romanToInt(self, s: str) -> int:
        convert = {
            'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000
        }
        n = len(s)
        ans = 0
        for i in range(n-1, -1, -1):
            if i == n-1:
                ans += convert[s[i]]
                continue
            pv = convert[s[i]]
            bv = convert[s[i+1]]
            if pv<bv:
                ans -= pv
            else:
                ans += pv
        return ans

18、整数转罗马数字

原题目地址：12. 整数转罗马数字

昨天做的是罗马数字转整数，只需要判断每一位字符后后一位字符的大小，s[i-1]>s[i] 就加上s[i-1]对应的值，反之这减去s[i-1]对应的值。

对于整数转罗马数字的话，一个整数唯一对应一个罗马数字，这是为什么呢？因为每次是取最大的罗马字符来构建的。

比如说整数140， 是先取100， 然后在去40， 最后返回的就是CXL

所以我们可以从大到小维护所有基础罗马字符，然后遍历， 如果nums小于遍历值，我们就减掉，依次类推。

class Solution {
    int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

    public String intToRoman(int num) {
        StringBuffer roma = new StringBuffer();
        for(int i=0;i<values.length;i++){ // 就是每次去最大的值相减
            int value = values[i];
            String symbol = symbols[i];
            while(num>=value){
                num -= value;
                roma.append(symbol);
            }
            if(num == 0){
                break;
            }
        }
        return roma.toString(); 
    }
}