笔试时间：2024年10月08日 秋招

历史笔试传送门：2023秋招笔试合集

第一题

题目：查找非递减子序列的个数

给你一个整数数组nums，找出并返回所有该数组中不同的递增子序列个数，递增子序列中至少有两个元素。数组中可能含有重复元素，如果出现两个整数相等，也可以视作递增序列的一种特殊情况。

其他时间限制：1000ms内存限制：256MB

样例输入一

[0,2,7]

样例输出一

4

说明：序列：[[0,2],[0,2,7],[0,7],[2,7]]

样例输入二

[3,5,7,1]

样例输出二

4

说明：序列：[[3,5],[3,5,7],[3,7],[5,7]]

样例输入三

[4,6,7,7]

样例输出三

8

说明：序列 [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

参考题解

DFS+回溯，枚举所有可能的情况。需要注意的是去重，dfs的每一层需要用一个set存储已经枚举过的数字，避免出现重复。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <vector>
#include <unordered_set>
class Solution {
public:
    int res = 0;
    /**
     * Note: 类名、方法名、参数名已经指定，请勿修改
     *
     * 
     * 
     * @param arr int整型 vector 
     * @return int整型
     */
    int find(vector<int>& arr) {
        // write code here
        dfs(arr, -100000000, 0, 0);
        return res;
    }
 
    // 参数的含义如下：
    // (数组，当前序列的最大数，当前层从数组的第几个数开始枚举，当前序列的长度)
    void dfs(vector<int>& arr, int curmax, int start, int len) {
        // 序列长度大于1就把答案加一
        if (len > 1) res++;
        if (start == arr.size()) return;
        // 用来存该层已经枚举过的数字
        unordered_set<int> s;
        for (int i = start; i < arr.size(); i++) {
            // 大于等于最大数且访问过该数才枚举
            if (arr[i] >= curmax && s.find(arr[i]) == s.end()) {
                s.insert(arr[i]);
                dfs(arr, arr[i], i + 1, len + 1);
            }
        }
    }
};

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.HashSet;
import java.util.List;

class Solution {
    public int res = 0;

    public int find(List<Integer> arr) {
        dfs(arr, -100000000, 0, 0);
        return res;
    }

    // 参数的含义如下：
    // (数组，当前序列的最大数，当前层从数组的第几个数开始枚举，当前序列的长度)
    public void dfs(List<Integer> arr, int curmax, int start, int len) {
        // 序列长度大于1就把答案加一
        if (len > 1) res++;
        if (start == arr.size()) return;

        // 用来存该层已经枚举过的数字
        HashSet<Integer> s = new HashSet<>();
        for (int i = start; i < arr.size(); i++) {
            // 大于等于最大数且访问过该数才枚举
            if (arr.get(i) >= curmax && !s.contains(arr.get(i))) {
                s.add(arr.get(i));
                dfs(arr, arr.get(i), i + 1, len + 1);
            }
        }
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

class Solution:
    def __init__(self):
        self.res = 0

    def find(self, arr):
        self.dfs(arr, -100000000, 0, 0)
        return self.res

    # 参数的含义如下：
    # (数组，当前序列的最大数，当前层从数组的第几个数开始枚举，当前序列的长度)
    def dfs(self, arr, curmax, start, length):
        # 序列长度大于1就把答案加一
        if length > 1:
            self.res += 1
        if start == len(arr):
            return

        # 用来存该层已经枚举过的数字
        s = set()
        for i in range(start, len(arr)):
            # 大于等于最大数且访问过该数才枚举
            if arr[i] >= curmax and arr[i] not in s:
                s.add(arr[i])
                self.dfs(arr, arr[i], i + 1, le