https://leetcode.cn/problems/majority-element/description/?envType=study-plan-v2&envId=top-interview-150

思路

主要有以下几种思路，因为我曾经似乎遇到过，所以很快直接想到了最佳算法。

1. 统计数量，采用哈希表存储会比较好
2. 排序后取中间位置
3. 随机算法，不稳定算法
4. Boyer-Moore 投票算法，简单来说就是消消乐，遇到和当前候选数相同的，计数值加一，不同则减一，变为0时若遇到新的数，更换候选数。

代码

代码很简单，就不需要伪代码了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    // 这道题目我有些印象，遇到不同的直接消除即可
    public int majorityElement(int[] nums) {
        int num=0;
        int maj=nums[0];
        for(int i=0;i<nums.length;i++)
        {
            if(num==0){
                maj=nums[i];
                num++;
            }else if(maj==nums[i]){//num!=0
                num++;
            }else{ // num!=0 and  maj!=nums[i]
                num--;
            }
        }
        return maj;

    }
}

本机环境 windows12.

Pycharm 安装

官网下载安装即可。

Pycharm 修改缓存目录与插件安装目录

参考：https://blog.csdn.net/qq_43541804/article/details/109369380

bin 目录中 idea.properties，文件头添加：

1
2
3
4

idea.config.path=D:/temp/.PyCharm/PyCharm2024.2/config
idea.system.path=D:/temp/.PyCharm/PyCharm2024.2/system
idea.plugins.path=D:/temp/.PyCharm/PyCharm2024.2/plugins
idea.log.path=D:/temp/.PyCharm/PyCharm2024.2/system/log

之后将原有目录直接拷贝过来到新的地址。

Miniconda 安装

1. 清华镜像源 下载 https://mirrors.tuna.tsinghua.edu.cn/anaconda/miniconda/ 或者通过 官网下载 https://repo.anaconda.com/miniconda/
2. 启动 conda 命令提示符
3. 创建一个新的环境，用于后续安装

1
2
3
4
5
6
7
8
9
10
11
12

conda create -n myenv_name python=3.8
conda activate myenv

# 后续一些可能有用的命令
pip install numpy
#或
conda install numpy
pip install -r requirements.txt
pip list
conda deactivate
conda env list
conda env remove -n myenv

注 conda 与 pip 的区别： Conda只能在conda环境中安装包，但是可以安装各种语言、各种类型的包。 pip可以在任何环境中安装包，但是只能安装Python包。 一般强烈建议两者不要混着用，建议使用 conda 进行环境管理，pip 进行包管理。

OpenCV 安装

可以在这里查看对应关系：https://pypi.tuna.tsinghua.edu.cn/simple/opencv-python/

1. 打开 conda prompt
2. 激活对应环境
3. 安装opencv 包，pip install opencv-python

Pycharm 使用

1. 在 file-settings-project interpreter 中 找到 miniconda/scripts/conda.exe 文件后 load
2. 选择环境，应用
3. 测试代码

1
2
3
4
5
6
7
8
9
10
11

# 基本IO
import cv2
# 读取版本号
print(cv2.getVersionString())
# 读取图片
image = cv2.imread("opencv_logo.jpg")
# 打印图片的形状（高度，宽度，通道数）
print(image.shape)

cv2.imshow("image", image)
cv2.waitKey()  # 让窗口暂停

其他

最后，如果需要使用人脸识别等的功能，在 opencv-python中没有，需要pip install opencv-contrib-python

思路

重点： - 有序 - 原地删除 - 出现次数超过两次的，保留两次

暴力解法-计数

从头遍历，出现一个新的数，将计数变量清零。当计数变量超过2时，删除这个元素，将后续元素前移.

快慢指针

和 26题目 本质上是类似的。

• 使用 slow 指针标记下一个需要被替换的位置，slow 之前的数列都已经满足要求
• 使用 fast 指针找到下一个需要移动到 slow 位置的值

1
2
3
4
5

// 伪代码
// 使用一个计数变量，使用一个暂存变量（当前正在计数的值）
// 首先初始化slow找到第一个可以代替的位置
// 将 fast 指针初始化为 slow，并向后边计数边寻找，如果计数变量小于2就移动，如果计数变量大于1就只移动right指针
// 每次移动完值之后，将slow与right+1

突然想到完全没必要使用计数变量，因为是有序的，所以直接使用 nums[i-2]?=nums[i] 就可以了

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums.length<=2) return nums.length;

        int slow=2, fast=2;

        while(fast<nums.length){
            if(nums[slow-2]!=nums[fast]){// 快指针
                nums[slow]=nums[fast];
                ++slow;
            }
            ++fast;
        }
        return slow;

    }
}

https://leetcode.cn/problems/remove-duplicates-from-sorted-array/?envType=study-plan-v2&envId=top-interview-150

思路

重点：非严格递增、原地删除、相对顺序一致

使用双指针，left 指针表示当前去重结果，right 指针找到下一个替换位置。因为要保持相对顺序，我们从左向右查找

伪代码：

1
2
3
4
5
6
7
8

left=1 right=1
while right<len:
    if nums[left-1]==nums[right]:
        right++
    else: 
        swap(nums[left],nums[right])
        left++;right++;
return left

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
    public int removeDuplicates(int[] nums) {
        int left =1,right=1;
        while(right<nums.length){
            if(nums[left-1]==nums[right]){
                right++;
            }else{
              // 这里没必要交换
                // int temp=nums[left];
                nums[left]=nums[right];
                // nums[right]=temp;
                right++;
                left++;
            }
        }
        return left;
    }
}

https://leetcode.cn/problems/remove-element/description/?envType=study-plan-v2&envId=top-interview-150

思路

暴力解法

双重循环：每次找到一个 val ，就从前向后找到第一个不是 val 的数进行替换。

正向指针

上述暴力循环中，内层循环不必从头寻找，保留一个索引，每次从索引开始向后寻找

两侧双指针

因为我们只需要将非 val 数值存放在前半部分，不需要管后半部分是什么，所以我们可以使用双指针： - 指针1：从后向前，找到第一个非val 数 - 指针2：从前向后，找到第一个val数 - 进行交换，之后先移动指针1，再移动指针2，如果指针1与指针2相遇，结束

细节分析： 1. 全是非 val，指针2会在最后一个非val 位置碰上指针1。而凡是指针2碰上指针1，都是成功的，说明前面没有val 2. 如果是指针1碰上指针2，意味着非val 数没有在后半部分了。 3. 全是 val ，需要判断相遇处的值是不是val才能兼容前述情况。所以我们需要在“指针1与指针2相遇后”，判断一次值

上述分析乱七八糟，能看出来我今天状态不行。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        p=len(nums)
        if p == 0:
            return 0
        q,p=0,p-1
        # 相遇
        while p > q:
            while nums[p]== val and p >q: # 找从后向前第一个非 val
                p-=1
            while nums[q]!=val and  q <p: # 从前向后找到第一个 val
                q+=1
            # swqp
            temp = nums[q]
            nums[q]=nums[p]
            nums[p]=temp
        # 检查
        if nums[p]== val:
            return p
        else:
            return p+1

进一步优化代码，参考Leetcode官方题解，另外我的命名不太好，应该使用 right left：

我们更应该关注左侧的元素，应该首先从左向右找到 val:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
    public int removeElement(int[] nums, int val) {
        int left = 0, right=nums.length;
        while(left < right){
            if(nums[left]==val){
                nums[left]=nums[right-1];
                right--;
            }else{
                left++;
            }
        }
        return left;
    }
}

https://leetcode.cn/problems/merge-sorted-array/description/?envType=study-plan-v2&envId=top-interview-150

按照非递减顺序将两个有序数组合并到第一个数组中。

思路

暴力解法

循环比较

双指针

双指针移动向后，但存在一个问题，第二个数组插入第一个数组可能会挤占原有数组中还未换出的元素，所以需要比较A、B、挤占出的元素三者。

逆序双指针

采用逆序，就能避免挤占A中未处理元素。因为B最多就直接放在A后面。

Hexo-Next 我主要的配置需求：

1. 基础的美化与功能
2. 数学公式
3. 公益404
4. 图片插入

注：强烈不建议在文章文件名称与图片名称中出现空格，我们可以在md文件名称中不使用空格，在文件中 title 字段中，使用包含空格的文章标题。

本文说明 windows 环境下的 Hexo + github pages+ Next 的建站流程。以及备份 Github Pages 相关配置与文档。