前言

题目总体难度不大，最后一题的动态规划，有不少同学反馈不会做，分割问题是可以考虑DP的，这也是一个经典的DP模型。

第一题

给定一个整数数组nums和一个整数 k，请返回其中出现频率前k高的元素。可以按 任意顺序 返回答案。

输入描述

输入:

nums = [1,1,1,2,2,3]，k = 2

输出描述

输出:

[1,2]

示例1

输入

1
1

输出

1

思路与代码

这段代码的目标是从一组整数数组中找到出现频率前k高的元素，并按照逗号分隔的形式输出这些元素。

以下是代码的主要步骤和解释：

1. 在topKFrequent方法中，首先创建一个HashMap（frequencyMap），用于存储整数元素的频率。
2. 遍历传入的整数数组nums，并使用HashMap统计每个元素的出现次数。
3. 创建一个最小堆（minHeap），该堆的元素是整数，使用Lambda表达式指定堆的排序方式，按照元素的频率升序排列。
4. 遍历frequencyMap中的键（即整数元素），将元素加入最小堆。如果堆的大小超过k，就弹出堆顶的元素，以保持堆的大小为k，因为我们只关心前k高的元素。
5. 创建一个长度为k的整数数组result，用于存储出现频率前k高的元素。
6. 使用while循环，从最小堆中依次弹出元素并存储到result数组中。
7. 调用topKFrequent方法，传入整数数组nums和整数k，得到出现频率前k高的元素。
8. 使用循环将result数组中的元素输出到标准输出，并以逗号分隔，最后输出一个换行符。

import java.util.*;

public class Main {
    public static int[] topKFrequent(int[] nums, int k) {

        Map<Integer, Integer> frequencyMap = new HashMap<>();
        for (int num : nums) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }


        PriorityQueue<Integer> minHeap = new PriorityQueue<>(
                (a, b) -> frequencyMap.get(a) - frequencyMap.get(b)
        );

        // 遍历频率Map，将元素加入最小堆
        for (int num : frequencyMap.keySet()) {
            minHeap.offer(num);
            if (minHeap.size() > k) {
                minHeap.poll(); // 如果堆的大小超过k，弹出堆顶的元素
            }
        }

        // 最小堆中剩下的元素就是出现频率前k高的元素
        
        int[] result = new int[k];
        int i = 0;
        while (!minHeap.isEmpty()) {
            result[i] = minHeap.poll();
        }
        
        return result;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        String[] num = s.split(", ");
        int[] nums = new int[num.length];
        for (int i = 0;i<num.length;i++){
            nums[i] = Integer.parseInt(num[i]);
        }
        
        int k = sc.nextInt();
        int[] result = topKFrequent(nums, k);
        for (int i = 0;i<k;i++){
            if(i!=k-1){
                System.out.print(result[i]+","); 
            }else {
                System.out.print(result[i]);
            }
        }
        
    }
}

第二题

现有2个数组，只包含整数，计算具有最小差绝对值的一对数值 (每个数组中取一个值)，并返回该对数值的差

输入描述

{1，3，15,11，2},{23,127,235，19,8}

输出描述

3

示例1

输入

1,3,15,11,2
23,127,235,19,8

输出

3

思路与代码

这段代码的目标是计算两个整数数组a和b之间的最小差值。以下是代码的主要步骤和解释：

1. 定义一个名为minDiff的函数，该函数接受两个整数向量a和b作为参数，用于计算它们之间的最小差值。

2. 对向量b进行升序排序，以便后续进行二分查找。

3. 初始化变量ans为INT_MAX，用于存储最小差值的初始值。

4. 使用for循环遍历向量a中的每个元素：

   a. 使用lower_bound函数在向量b中找到不小于当前a元素的迭代器。lower_bound函数返回的迭代器指向第一个不小于给定元素的位置。

   b. 如果找到的迭代器不等于b.end()，说明在向量b中找到了一个不小于a元素的值，计算当前a元素与该值的差的绝对值，然后与ans比较并更新ans。

   c. 如果找到的迭代器不等于b.begin()，说明在向量b中存在一个比a元素小的值，将迭代器向前移动一个位置，再次计算当前a元素与该值的差的绝对值，然后与ans比较并更新ans。

5. 最后，函数返回ans，它包含了向量a和b之间的最小差值。

6. 在main函数中，从标准输入中读取两行字符串，分别代表整数数组a和b，然后将它们解析成整数向量a和b。

7. 调用minDiff函数计算最小差值，并将结果输出到标准输出。

#include<bits/stdc++.h>
using namespace std;
int minDiff(vector<int> &a,vector<int> &b) {
    sort(b.begin(),b.end());
    int ans = INT_MAX;
    for(int num : a) {
        auto lower = lower_bound(b.begin(),b.end(),num);
        if(lower != b.end()) {
            ans = min(ans,abs(*lower-num));
        }
        if(lower != b.begin()) {
            lower--;
            ans = min(ans,abs(*lower-num));
        }
    }
    return ans;
}
int main() {
    string as,bs;
    getline(cin,as);
    getline(cin,bs);
    vector<int> a,b;
    for(int i = 0;i < as.size();i++) {
        int j = i;
        while(j < as.size() && as[j] != ','){
            j++;
        }
        a.push_back(stoi(as.substr(i,j-i)));
        i = j;
    }
    for(int i = 0;i < bs.size();i++) {
        int j = i;
        while(j < bs.size() && bs[j] != ','){
            j++;
        }
        b.push_back(stoi(bs.substr(i,j-i)));
        i = j;
    }
    cout << minDiff(a,b) << endl;                        
}

第三题

给定一个字符串s，请将分割成一些子串，使每个子串都是回文串。返回符合要求的 最少分割次数。

1 <= s.length <= 2000

s仅由小写英文字母组成

输入描述

s = "aab“

输出描述

1

示例1

输入

aab

输出

1

思路与代码这段代码的目标是计算将一个字符串分割成回文子字符串所需的最小切割次数。

以下是代码的主要步骤和解释：

1. 定义一个名为minCount的函数，该函数接受一个字符串s作为参数，用于计算将字符串s分割成回文子字符串所需的最小切割次数。

2. 获取字符串s的长度，记为n。

3. 创建一个二维布尔向量isPa，大小为nxn，用于存储字符串s中从位置i到位置j是否为回文子字符串。初始时，所有元素都设置为false。

4. 使用两个嵌套的for循环遍历字符串s的每一个字符，以i作为中心，向左右扩展，检查是否形成回文子字符串。如果是，将isPa[i][j]设置为true。

5. 初始化一个整数向量dp，大小为n+1，用于存储从位置0到位置i的最小切割次数。初始时，将所有元素设置为一个较大的数，例如0x3f3f3f3f。

6. 将dp[0]初始化为0，表示从位置0开始不需要切割。

7. 使用两个嵌套的for循环，分别遍历i和j，其中i表示结束位置，j表示起始位置。对于每一对i和j，如果从j到i的子字符串是回文字符串（即isPa[j-1][i-1]为true），则更新dp[i]，将其设为dp[j-1] + 1的较小值。

8. 最终，dp[n]存储了从位置0到位置n的最小切割次数，但需要减去1，因为初始状态的dp[0]已经包含了一个分割。

9. 在main函数中，从标准输入读取字符串s，然后调用minCount函数计算最小切割次数，并将结果输出到标准输出。

#include<bits/stdc++.h>
using namespace std;
int minCount(string &s) {
    int n = s.size();
    vector<vector<bool>> isPa(n,vector<bool>(n,false));
    for(int i = 0;i < n;i++) {
        int l = i,r = i;
        while(l >= 0 && r < n && s[l] == s[r]) {
            isPa[l][r] = true;
            l--,r++;
        }
        l = i,r = i + 1;
        while(l >= 0 && r < n && s[l] == s[r]) {
            isPa[l][r] = true;
            l--,r++;
        }
    }
    vector<int> dp(n + 1,0x3f3f3f3f);
    dp[0] = 0;
    for(int i = 1;i <= n;i++) {
        for(int j = i;j >= 1;j--) {
            if(isPa[j-1][i-1]) dp[i] = min(dp[i],1 + dp[j-1]);
        }
    }
    return dp[n] - 1;
}
int main() {
    string s;
    cin >> s;
    cout << minCount(s) << endl;
}