算法刷题周记03

1.买卖股票的最佳时机 II（中等）

给你一个整数数组 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 。

解法（贪心）

class Solution {
public:
    int maxProfit(vector& prices) {
        if(prices.size() <= 1)
        {
            return 0;
        }
        int interest = 0;
        for(int i = 1; i < prices.size();i++)
        {
            if(prices[i] - prices[i - 1] > 0){
                interest += prices[i] - prices[i - 1];
            }
        }
        return interest;
    }
};

2.比较版本号（中等）

给你两个版本号 version1 和 version2 ，请你比较它们。

版本号由一个或多个修订号组成，各修订号由一个 . 连接。每个修订号由 多位数字 组成，可能包含 前导零 。每个版本号至少包含一个字符。修订号从左到右编号，下标从 0 开始，最左边的修订号下标为 0 ，下一个修订号下标为 1 ，以此类推。例如，2.5.33 和 0.1 都是有效的版本号。

比较版本号时，请按从左到右的顺序依次比较它们的修订号。比较修订号时，只需比较 忽略任何前导零后的整数值 。也就是说，修订号 1 和修订号 001 相等 。如果版本号没有指定某个下标处的修订号，则该修订号视为 0 。例如，版本 1.0 小于版本 1.1 ，因为它们下标为 0 的修订号相同，而下标为 1 的修订号分别为 0 和 1 ，0 < 1 。

返回规则如下：

• 如果 version1 > version2 返回 1，
• 如果 version1 < version2 返回 -1，
• 除此之外返回 0。

示例 1：

输入：version1 = "1.01", version2 = "1.001"
输出：0
解释：忽略前导零，"01" 和 "001" 都表示相同的整数 "1"

示例 2：

输入：version1 = "1.0", version2 = "1.0.0"
输出：0
解释：version1 没有指定下标为 2 的修订号，即视为 "0"

示例 3：

输入：version1 = "0.1", version2 = "1.1"
输出：-1
解释：version1 中下标为 0 的修订号是 "0"，version2 中下标为 0 的修订号是 "1" 。0 < 1，所以 version1 < version2

解法（字符串转整型）

public class Solution {
    public int compareVersion(String version1, String version2) {
        int[] v1 = Arrays.stream(version1.split("\\.")).mapToInt(Integer::parseInt).toArray();// Java8写法 直接将string[] 转为int[]
        int[] v2 = Arrays.stream(version2.split("\\.")).mapToInt(Integer::parseInt).toArray();
        int pc = 0; // 计数器
        while(v1.length > pc || v2.length > pc){
            int Num1 = pc < v1.length ? v1[pc] : 0;
            int Num2 = pc < v2.length ? v2[pc] : 0;
            if (Num1 < Num2){
                return -1;
            }else if (Num1 > Num2){
                return 1;
            }
            pc++;
        }
        return 0;
    }
}

3.根据身高重建队列（中等）

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

示例 1：

输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解释：
编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。

示例 2：

输入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
输出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

解法

思路：假设这样一个数组

{7,0},{4,4},{7,1},{5,0},{6,1},{5,2}

对 h 升序排序，对k降序排序。然后插入

[4,4],[5,2],[5,0],[6,1],[7,1],[7,0]

[x,x,x,x,4,x]

[x,x,5,x,4,x]

[5,x,5,x,4,x]

[5,x,5,6,4,x]

[5,x,5,6,4,7]

[5,7,5,6,4,7]

代码如下：

class Solution
{
public:
    vector> reconstructQueue(vector> &people)
    {
        int len = people.size();
        vector pos; // 索引数组
        for (int i = 0; i < len; i++)
        {
            pos.push_back(i);
        }
        sort(people.begin(), people.end(), [](vector &p1, vector &p2)
             {
            if(p1[0] == p2[0]){
                return p1[1] > p2[1];
            }
            return p1[0] < p2[0]; });
        vector> res(len,vector(2));
        for (int i = 0; i < len; i++)
        {
            int indx = pos[people[i][1]]; // 获取索引数组 下标对应的 值
            res[indx] = people[i]; 
            pos.erase(pos.begin() + people[i][1]);
        }
        return res;
    }
};

4.串联所有单词的子串

给定一个字符串 s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符 ，但不需要考虑 words 中单词串联的顺序。

示例 1：

输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。

示例 2：

输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：[]

示例 3：

输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出：[6,9,12]

前言：滑动窗口

这类题是属于滑动窗口的题，很有技巧性，也很经典，

具体可以看看这篇文章:聊聊滑动窗口

解法（滑动窗口）

public List<Integer> findSubstring(String s, String[] words) {
    List<Integer> res = new ArrayList<>(); // 存放结果
    int ls = s.length(); // 字符串长度
    int m = words.length; // 所有单词的个数
    int n = words[0].length(); // 单词长度（都相等）
    int size = m * n;// 拆分s的长度
    // 划分单词组
    for (int i = 0; i < n; i++) {
        // 遍历长度超过了整个字符串的长度，退出循环
        if (i + m * n > ls) {
            break;
        }
        // 初始化differ，表示窗口中的单词频次和words中的单词频次之差
        Map<String, Integer> differ = new HashMap<>();

        // 初始化窗口，窗口长度为 单词长度 * 单词个数, 依次计算窗口里每个切分的单词频次
        for (int j = 0; j < m; j++) {
            String word = s.substring(i + j * n, i + (j + 1) * n);//获取窗口里面的每个单词
            // 每个单词放入differ中
            differ.put(word, differ.getOrDefault(word, 0) + 1);
        }
        // 遍历words中的单词，与窗口里的单词比对
        for (String word : words) {
            // 用words中的单词对进行匹配，如果匹配成功则differ中以word为key的value减1
            differ.put(word, differ.getOrDefault(word, 0) - 1);
            if (differ.get(word) == 0) // 如果差值为0时，则删除这个word
            {
                differ.remove(word);
            }
        }
        // 开始滑动窗口（每次滑动一个单词：右边单词进来，左边单词就要出去）
        for (int start = i; start < ls - m * n + 1; start += n) {
            if (start != i) {
                // 右边的单词滑进来
                String word = s.substring(start + (m - 1) * n, start + m * n);
                differ.put(word, differ.getOrDefault(word, 0) + 1);
                if (differ.get(word) == 0) {
                    differ.remove(word);
                }
                // 左边单词就滑出去
                word = s.substring(start - n, start);
                differ.put(word, differ.getOrDefault(word, 0) - 1);
                if (differ.get(word) == 0) {
                    differ.remove(word);
                }
            }
            if (differ.isEmpty()) {
                res.add(start);
            }
        }
    }
    return res;
}

5.矩阵置零

给定一个 *m* x *n* 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

示例 1：

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

示例 2：

输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

解法（两个标记变量）

class Solution
{
public:
    void setZeroes(vector> &matrix)
    {
        // rowFlag,colFlag 如果为true 代表首行/列存在0
        bool rowFlag = false;
        for (int i = 0; i < matrix[0].size(); i++) // 遍历首行
        {
            if (matrix[0][i] == 0)
            {
                rowFlag = true;
                break;
            }
        }
        bool colFlag = false;
        for (int i = 0; i < matrix.size(); i++) // 遍历首列
        {
            if (matrix[i][0] == 0)
            {
                colFlag = true;
                break;
            }
        }
        for (int i = 1; i < matrix.size(); i++)
        {
            for (int j = 1; j < matrix[0].size(); j++)
            {
                if (matrix[i][j] == 0)
                {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        for (int i = 1; i < matrix[0].size(); i++)
        {
            if (matrix[0][i] == 0)
            { // 把对应列置为0
                for (int j = 0; j < matrix.size(); j++)
                {
                    matrix[j][i] = 0;
                }
            }
        }
        for (int i = 1; i < matrix.size(); i++)
        {
            if (matrix[i][0] == 0) //把对应行置为0
            {
                for (int j = 0; j < matrix[i].size(); j++)
                {
                    matrix[i][j] = 0;
                }
            }
        }
        if (rowFlag)
        { // 如果首行中有元素为0，把首行都置为0
            for (int i = 0; i < matrix[0].size(); i++)
            {
                matrix[0][i] = 0;
            }
        }
        if (colFlag)
        { // 如果首列中有元素为0，把首行都置为0
            for (int i = 0; i < matrix.size(); i++)
            {
                matrix[i][0] = 0;
            }
        }
    }
};

6.零钱兑换 II

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

示例 1：

输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2：

输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。

示例 3：

输入：amount = 10, coins = [10] 
输出：1

提示

• 1 <= coins.length <= 300
• 1 <= coins[i] <= 5000
• coins 中的所有值 互不相同
• 0 <= amount <= 5000

前言：背包问题

背包问题有很多：01背包、完全背包、多重背包、分组背包、混合背包。对于准备大厂面试的话，其实用的最多就是01背包和完全背包了。其中01背包是基础，很重要。

01背包：简单说就是n种物品，每种物品只能有0个或者1个。

完全背包：n种物品，每种物品有无限个。

多重背包：n种物品，每种物品的个数各不相同。

有关资源可以看看这个大佬写的一篇文章：背包问题理论基础完全背包

解法（dp，背包问题）

class Solution {
public:
    int change(int amount, vector& coins) {
        vector dp(amount + 1, 0);
        dp[0] = 1;
        for (auto coin : coins)
        {
            for (int i = 1; i <= amount; i++)
            {
                if(i < coin)continue;
                dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }
};