盛算信息-面试经历-笔试部分-完整题目（一）

GeekLiHua

发布于 2025-01-21 13:12:29

2770

文章被收录于专栏：JavaJava

盛算信息-面试经历-完整题目-C++岗

首先是笔试题目，笔试时间一个小时，后面会更新面试部分题目讲解。面试题讲解链接：面试题讲解

题目如下

解释c++中static,const的含义与作用。

static与const的含义和作用

C++中static:首先他的作用是定义静态变量

在函数内部声明的静态变量具有静态存储持续时间，他们在程序执行期间保持存在，而不是在每次函数调用时创建和销毁，静态变量在函数调用之间保持其值不变，可以用于函数调用之间的共享数据。比如下面这个例子

void foo() {
    static int count = 0;
    count++;
    cout << "Count: " << count << endl;
}

int main() {
    foo(); // 输出 Count: 1
    foo(); // 输出 Count: 2
    foo(); // 输出 Count: 3
    return 0;
}

静态函数：在类中声明的静态函数属于类本身，而不是类的实例，静态函数可以直接通过类名调用，无需创建类的实例，静态函数可以直接通过类名调用，无需创建类的实例。静态函数只能访问静态成员变量和其他静态函数，不能访问静态成员变量和非静态函数，比如下面这个例子。

class MathUtils {
public:
    static int add(int a, int b) {
        return a + b;
    }
};

int main() {
    int result = MathUtils::add(5, 3);  // 可以直接通过类名调用
    cout << "Result: " << result << endl; // 输出 Result: 8
    return 0;
}

静态成员变量：在类中声明静态成员变量属于类本身，而不是类的实例，静态成员变量只有一份拷贝，而不是所有类的实例共享，静态成员可以通过类或实例名访问，比如下面例子。

class MyClass {
public:
    static int count;
};

int MyClass::count = 0;

int main() {
    MyClass obj1;
    MyClass obj2;
    
    obj1.count = 5;
    cout << "obj1.count: " << obj1.count << endl; // 输出 obj1.count: 5
    cout << "obj2.count: " << obj2.count << endl; // 输出 obj2.count: 5
    
    obj2.count = 10;
    cout << "obj1.count: " << obj1.count << endl; // 输出 obj1.count: 10
    cout << "obj2.count: " << obj2.count << endl; // 输出 obj2.count: 10
    
    return 0;
}

静态类：C++没有直接的关键字来定义静态类，但可以通过将所有成员声明为静态来实现静态类的效果。静态类不能实例化，只能通过类名访问静态成员。

class MathUtils {
public:
    static int add(int a, int b) {
        return a + b;
    }
    
    static int multiply(int a, int b) {
        return a * b;
    }
};

int main() {
    int result1 = MathUtils::add(5, 3);
    cout << "Result1: " << result1 << endl; // 输出 Result1: 8
    
    int result2 = MathUtils::multiply(5, 3);
    cout << "Result2: " << result2 << endl; // 输出 Result2: 15
    
    return 0;
}

个人拓展Java中static的作用

在Java中，static关键字用于声明静态成员，它可以应用于变量、方法和代码块。

静态变量：使用static关键字修饰的变量是静态变量，也称为类变量。静态变量在类加载时被初始化，且只有一份副本，被所有对象共享。

public class Circle {
    private static double pi = 3.14;
    private double radius;
    
    // 静态方法可以访问静态变量
    public static double getPi() {
        return pi;
    }
    
    public Circle(double r) {
        radius = r;
    }
    
    public double getArea() {
        return pi * radius * radius;
    }
}

public static void main(String[] args) {
    Circle c1 = new Circle(5.0);
    Circle c2 = new Circle(10.0);
    
    System.out.println(Circle.getPi()); // 输出 3.14
    System.out.println(c1.getArea());   // 输出 78.5
    System.out.println(c2.getArea());   // 输出 314.0
    
    Circle.pi = 3.14159; // 可以通过类名直接访问静态变量并修改其值
    System.out.println(Circle.getPi()); // 输出 3.14159
}

静态方法：使用static关键字修饰的方法是静态方法，也称为类方法。静态方法属于类而不是对象，可以通过类名直接调用，无需创建对象。

public class MathUtils {
    public static int add(int a, int b) {
        return a + b;
    }
    
    public static int subtract(int a, int b) {
        return a - b;
    }
}

public static void main(String[] args) {
    int sum = MathUtils.add(5, 3);       // 直接通过类名调用静态方法
    int difference = MathUtils.subtract(5, 3);
    
    System.out.println(sum);        // 输出 8
    System.out.println(difference);  // 输出 2
}

静态代码块：使用static关键字修饰的代码块是静态代码块，它在类加载时执行，用于初始化静态变量或执行其他静态操作。

public class Circle {
    private static double pi;
    
    static {
        pi = 3.14;
        System.out.println("Static initializer block executed");
    }
    
    public Circle(double r) {
        radius = r;
    }
}

public static void main(String[] args) {
    Circle c = new Circle(5.0); // 输出 "Static initializer block executed"
}

C++中const:在C++中，`const`关键字用于声明常量，表示该变量的值在初始化后不能被修改。`const`可以用于变量、函数参数、函数返回值和成员函数。

常量变量：使用const关键字声明的变量被称为常量，其值在初始化后不能被修改。常量必须在声明时进行初始化。

const int MAX_VALUE = 100;
int main() {
    MAX_VALUE = 200; // 错误，常量不能被修改
    return 0;
}

常量函数参数：在函数声明中，使用const关键字修饰函数参数，表示该参数在函数内部不会被修改。这样做可以保证函数不会意外修改传入的参数。

void printNumber(const int num) {
    num = 10; // 错误，常量参数不能被修改
    cout << num << endl;
}

int main() {
    int value = 5;
    printNumber(value); // 输出 5
    return 0;
}

常量函数返回值：在函数声明中，使用const关键字修饰函数返回值，表示该返回值是一个常量，不能被修改。

const int getNumber() {
    return 10;
}

int main() {
    int num = getNumber(); // 错误，常量返回值不能被修改
    return 0;
}

常量成员函数：在类中声明的成员函数可以使用const关键字修饰，表示该函数不会修改类的成员变量。常量成员函数可以在常量对象上调用，但不能修改对象的状态。

// 定义一个圆类
class Circle {
private:
    double radius; // 圆的半径
public:
    // 构造函数，用于初始化圆的半径
    Circle(double r) : radius(r) {}
    
    // 常量成员函数，用于计算圆的面积
    double getArea() const {
        return 3.14 * radius * radius;
    }
};

// 主函数
int main() {
    // 创建一个常量对象c，半径为5.0
    const Circle c(5.0);
    
    // 调用常量成员函数getArea()，计算圆的面积，并将结果赋值给变量area
    double area = c.getArea();
    
    // 错误，常量对象的成员变量不能被修改
    c.radius = 10.0;
    
    return 0;
}

个人拓展Java中的常量

在Java中，没有直接的const关键字来声明常量。Java使用final关键字来声明常量，表示该变量的值在初始化后不能被修改。

常量变量：使用final关键字修饰的变量是常量，一旦被赋值后就不能再改变。

final int num = 10;
num = 20; // 错误，常量不能被修改

常量方法参数：在方法声明中，使用final关键字修饰方法参数，表示该参数是一个常量，在方法内部不能修改参数的值。

void printNumber(final int value) {
    value = 20; // 错误，常量参数不能被修改
    System.out.println(value);
}

public static void main(String[] args) {
    int num = 10;
    printNumber(num); // 输出 10
}

常量方法返回值：在方法声明中，使用final关键字修饰方法返回值，表示该返回值是一个常量，不能被修改。

final int getNumber() {
    return 10;
}

public static void main(String[] args) {
    int num = getNumber(); // 错误，常量返回值不能被修改
}

常量成员变量：在类中声明的成员变量可以使用final关键字修饰，表示该变量是一个常量，一旦被赋值后就不能再改变。

public class Circle {
    private final double radius;
    
    public Circle(double r) {
        radius = r;
    }
    
    public double getArea() {
        return 3.14 * radius * radius;
    }
}

public static void main(String[] args) {
    Circle c = new Circle(5.0);
    double area = c.getArea();
    c.radius = 10.0; // 错误，常量成员变量不能被修改
}

c++的注释的演示

这个题比较特殊，演示的是c++中/**/多行注释可能遇到的坑，也就是注释嵌套容易遇到的，比如下面的例子

嵌套注释问题：C++中的注释不能嵌套。如果在一个多行注释中使用了另一个多行注释，编译器会将其视为注释的结束，导致编译错误。

/* This is a comment /* with nested comment */ */  // 错误，嵌套注释

注释中的字符串问题：在注释中使用字符串时，需要注意字符串中可能包含的注释结束符*/。如果注释结束符出现在字符串中，编译器会将其视为注释的结束，导致编译错误。

/* This is a comment with a string "This is a string */" */  // 错误，字符串中包含注释结束符

注释中的预处理指令问题：在注释中使用预处理指令时，需要注意预处理指令中可能包含的注释结束符*/。如果注释结束符出现在预处理指令中，编译器会将其视为注释的结束，导致编译错误。

/* This is a comment with a preprocessor directive #include "header.h" */  // 错误，预处理指令中包含注释结束符

注释中的代码问题：在注释中放置代码是一种常见的错误做法。注释应该用于解释代码的作用和目的，而不是放置实际的代码。如果在注释中放置了代码，编译器会将其视为实际的代码，导致编译错误。

/* This is a comment with code */
int x = 5;  // 错误，注释中放置了实际的代码

c++中++运算问题

题目：讲解a+++b的运算过程，通过代码讲解如下

#include <iostream>

int main() {
    int a = 5;
    int b = 3;
    int result = a+++b;

    std::cout << "Result: " << result << std::endl;

    return 0;
}

首先，将a的当前值（5）赋给一个临时变量，然后将a的值递增1，此时a的值变为6。
然后，将递增后的a的值（6）与b的值（3）相加，得到最终的结果9。

因此，输出结果为：

Result: 9

算法题：求1~100之间的质数

这个太熟了，方法有很多，从慢到快演示。最简单方法，这就是根据质数的特性写的。

bool is_prime(int x)
{
    if (x < 2) return false;
    for (int i = 2; i <= x / i; ++ i)
    {
        if (x % i == 0) return false;
    }
    return true;
}

比赛写法，经典算法题，筛法求质数，这个比较讲究了，如果是一般的算法比赛，可以用埃式筛法，如果是ACM这种的话，就要使用线性筛法。

埃式筛法：一句话讲解思路就是，如果一个数字他是质数，那么他的倍数一定不是质数，所以只需要把这些不是质数的筛掉就可以了。时间复杂度O(nlogn)

// 埃氏筛法

#include<iostream>
using namespace std;
const int N = 1e6 + 10;

int cnt, n;
bool st[N];

void get_primes(int n)
{
    for (int i = 2; i <= n; ++i)
    {
        if (!st[i])
        {
            cnt ++;
            for (int j = i + i; j <= n; j += i) st[j] = true;
        }
    }
}
int main()
{
    cin >> n;
    get_primes(n);
    cout << cnt << '\n';
    return 0;
}

线性筛法：这个难度就很大了，下面是我以前写一个讲解，以前我也是打过ACM的男人。

// 线性筛法 时间复杂度O(n)
// 核心思想：一个数只会被它的最小质因子 筛掉 相对于埃氏筛法而言 可以省去很多不必要的操作 每个合数只会被筛一次
// 数据越大 快的越明显

#include<iostream>
using namespace std;
const int N = 1e6 + 10;

int prime[N], cnt, n;
bool st[N];

void get_primes(int n)
{
    for (int i = 2; i <= n; ++i)
    {
        if (!st[i]) prime[cnt ++] = i;
        for (int j = 0; prime[j] <= n / i; ++j)         // 一个个的求出的质数达到枚举 这里的判断条件中是不需要写上 j < cnt的 
                                                        // 因为下面的条件那个break 如果 i是合数 下面那个条件一定会成立 如果i 是质数 下面的那个条件也会成立
                                                        //  prime[]中含有所有合数的质因子 i是质数的话 prime中会有和i相等的一个数
        {
            st[prime[j] * i] = true;                    // prime[j] 是合数 prime[j] * i的最小质因子    
            if (i % prime[j] == 0)  break;              // 这里是最能理解的地方
                                                        // 由于prime[j]是按照从小到大的质数进行的 所以 如果这个语句成立的话 那么prime[j] 一定是 i的最小质因子
                                                        // 这个时候就符合算法思想了 每个合数只会被它的最小质因子筛掉 这个时候就要停下来了
                                                        // 如果继续的话会有 prime[j + 1]来筛下一个合数 i * prime[j + 1]
                                                        // 因为prime[j] 是 i的最小质因子 所以i * prime[j + 1] = k * prime[j] * prime[j + 1]
                                                        // 然后这个合数应该是要被 prime[j] 筛掉的 但是此时是被prime[j + 1] 筛掉的 然后违背了 这个算法的核心
        }
    }
}
int main()
{
    cin >> n;
    get_primes(n);
    cout << cnt << '\n';
    return 0;
}

讲解C语言里面指针与数组的关系

我当时写的是数组的本质就是指针，指针被分配了内存之后就成了数组，下面是更详细的解释：

数组名作为指针：在C语言中，数组名可以被视为指向数组首元素的指针。例如，对于一个整型数组int arr[5]，arr可以被视为指向arr[0]的指针。因此，可以通过arr来访问数组的元素，如arr[0]、arr[1]等。
指针和数组的关系：由于数组名是指向数组首元素的指针，因此可以使用指针的方式来操作数组。例如，可以使用指针算术运算来访问数组的其他元素。比如，可以使用arr + 1来访问数组的第二个元素，使用arr + 2来访问数组的第三个元素，以此类推。
指针与数组的传递：当将数组作为参数传递给函数时，实际上是将数组的首地址（即数组名）传递给函数。在函数内部，可以使用指针的方式来访问数组的元素。这样可以避免在函数调用时复制整个数组，提高了效率。
数组指针：在C语言中，还可以定义指向数组的指针。例如，可以使用int* ptr来定义一个指向整型数组的指针。通过指针，可以对数组进行遍历和操作。

拓展内容，python,java,golang中指针是如何体现的

python：在python中没有指针，但是处处都体现出来了指针，为啥python可以不用定义数据的类型了，正是用了指针的特性，python是万物皆对象，我们也可以说是万物皆指针，所以当然不需要定义具体的类型，因为所有的变量本质都是一个地址，js的设计思路应该也是一样的，不需要定义具体的数据类型。

java:java中也是没有指针的概念的，但是有了引用的概念来实现，指针的功能，在Java中，尽管没有像C语言那样直接的指针概念，但是通过引用类型和对象引用的方式，可以实现类似于指针的功能，比如下面的例子。

对象引用：在Java中，变量存储的是对象的引用。当我们创建一个对象时，实际上是在堆内存中分配了一块内存空间，并将对象的引用赋给变量。这个引用可以看作是指向对象的指针。

int[] arr = new int[3];  // 创建一个整型数组对象
int[] arr2 = arr;       // 将arr的引用赋给arr2
arr2[0] = 1;            // 修改arr2，也会影响到arr
System.out.println(arr[0]);  // 输出 1

方法参数传递：在Java中，方法参数传递方式是通过对象引用来实现的。当我们将一个对象作为参数传递给方法时，实际上是将对象的引用传递给了方法。这意味着在方法内部对参数的修改会影响到原始对象。

public static void modifyArray(int[] arr) {
    arr[0] = 1;   // 修改arr，也会影响到原始数组
}

int[] arr = new int[3];
modifyArray(arr);
System.out.println(arr[0]);  // 输出 1

对象的等价性：在Java中，可以使用==运算符来比较两个对象的引用是否相等。如果两个对象的引用指向同一个内存地址，则它们被认为是相等的。

int[] arr1 = new int[3];
int[] arr2 = arr1;
System.out.println(arr1 == arr2);  // 输出 true，arr1和arr2引用同一个对象

golang:在Go语言中，指针的功能和C语言非常的像，甚至操作符的含义都一样。

声明指针：在Go语言中，可以使用*来声明一个指针变量。例如，var ptr *int声明了一个指向整型变量的指针。
获取变量的地址：可以使用&操作符获取变量的内存地址。例如，x := 10; ptr := &x将变量x的地址赋给指针变量ptr。
解引用指针：可以使用*操作符来解引用指针，即获取指针指向的变量的值。例如，*ptr表示获取指针ptr指向的整型变量的值。
修改变量的值：通过指针，可以直接修改变量的值。例如，*ptr = 20表示将指针ptr指向的整型变量的值修改为20。
空指针：Go语言中的空指针表示一个指针变量未指向任何有效的内存地址。可以使用nil关键字表示空指针。

package main

import "fmt"

func main() {
    x := 10
    fmt.Println("x =", x)  // 输出 x = 10

    ptr := &x
    fmt.Println("ptr =", ptr)  // 输出 ptr = 0xc0000180b8
    fmt.Println("*ptr =", *ptr)  // 输出 *ptr = 10

    *ptr = 20
    fmt.Println("x =", x)  // 输出 x = 20

    var nilPtr *int
    fmt.Println("nilPtr =", nilPtr)  // 输出 nilPtr = <nil>
}

讲解你知道的所有排序方法，讲解他们的原理和对应的时间空间复杂度，还有快速排序是哪个排序转换而来的

我整理了一下，如下（默认都是升序排列）：

冒泡排序（Bubble Sort）：
- 原理：通过比较相邻元素的大小，将较大的元素逐步向右移动，从而将最大的元素移动到最右边。重复这个过程，直到整个数组排序完成。
- 时间复杂度：平均情况和最坏情况下的时间复杂度都为O(n^2)。
- 空间复杂度：O(1)。

void bubbleSort(vector<int>& arr)
{
    int n = arr.size();
    for (int i = 0; i < n - 1; ++ i)
    {
        for (int j = 0; j < n - 1 - i; ++ j)
        {
            if (arr[j] > arr[j + i]){
                swap(arr[j], arr[j + 1]);
            } 
        }
    }
}

选择排序（Selection Sort）：
- 原理：每次从未排序的部分中选择最小（或最大）的元素，然后将其放置在已排序部分的末尾。重复这个过程，直到整个数组排序完成。
- 时间复杂度：平均情况和最坏情况下的时间复杂度都为O(n^2)。
- 空间复杂度：O(1)。

void selectionSort(vector<int>& arr) {
    int n = arr.size();
    
    // 遍历数组，执行n-1轮选择操作
    for (int i = 0; i < n - 1; i++) {
        
        // 假设当前最小元素的索引为i
        int minIndex = i;
        
        // 在未排序部分中找到最小元素的索引
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        
        // 将最小元素与未排序部分的第一个元素交换位置
        swap(arr[i], arr[minIndex]);
    }
}

插入排序（Insertion Sort）：
- 原理：将数组分为已排序和未排序两部分，每次将未排序部分的第一个元素插入到已排序部分的正确位置。重复这个过程，直到整个数组排序完成。
- 时间复杂度：平均情况和最坏情况下的时间复杂度都为O(n^2)。
- 空间复杂度：O(1)。

void insertionSort(vector<int>& arr) {
  int n = arr.size();
  
  // 从第二个元素开始，依次插入到已排序部分的正确位置
  for (int i = 1; i < n; i++) {
      int key = arr[i];
      int j = i - 1;
      
      // 将比key大的元素向后移动
      while (j >= 0 && arr[j] > key) {
          arr[j + 1] = arr[j];
          j--;
      }
      
      // 将key插入到正确位置
      arr[j + 1] = key;
  }
}

快速排序（Quick Sort）：
- 原理：选择一个基准元素，将数组分为两部分，一部分小于基准元素，一部分大于基准元素。然后对这两部分分别进行递归排序。通过不断地划分和排序，最终实现整个数组的排序。
- 时间复杂度：平均情况下的时间复杂度为O(nlogn)，最坏情况下的时间复杂度为O(n^2)。但是，通过使用随机化的快速排序和优化的分区算法，可以减少最坏情况的出现概率。
- 空间复杂度：平均情况下的空间复杂度为O(logn)，最坏情况下的空间复杂度为O(n)。
- 来源：快速排序是由冒泡排序改进而来的，它采用了分治法的思想，通过选择一个基准元素将数组分为两部分，然后对这两部分进行递归排序。

#include<iostream>
using namespace std;

const int N = 1e6 + 10;
int q[N];

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;
    int i = l - 1, j = r + 1, x = q[(l + r) >> 1];
    while(i < j)
    {
        do i ++; while (q[i] < x);
        do j --; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j); quick_sort(q, j + 1, r);
}

int main()
{
    int n;
    scanf ("%d", &n);
    for (int i = 0; i < n; ++ i) scanf("%d", &q[i]);
    quick_sort(q, 0, n - 1);
    for (int i = 0; i < n; ++ i) printf("%d ", q[i]);
    return 0;
}

归并排序（Merge Sort）：
- 原理：将数组分成两个子数组，分别对这两个子数组进行递归排序，然后将排好序的子数组合并成一个有序的数组。通过不断地分割和合并，最终实现整个数组的排序。
- 时间复杂度：平均情况和最坏情况下的时间复杂度都为O(nlogn)。
- 空间复杂度：O(n)。

#include<iostream>
using namespace std;

const int N = 1e6 + 10;
int tmp[N], q[N];
int n;

void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;
    
    int mid = l + r >> 1;
    merge_sort(q, l, mid), merge_sort(q, mid + 1, r);
    
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r) 
    {
        if (q[i] <= q[j]) tmp[k ++] = q[i ++];
        else tmp[k ++] = q[j ++];
    }
    while (i <= mid) tmp[k ++] = q[i ++];
    while (j <= r) tmp[k ++] = q[j ++];
    
    for (i = l, j = 0; i <= r; i ++, j ++) q[i] = tmp[j];
}

int main()
{
    scanf ("%d", &n);    
    for (int i = 0; i < n; ++i) scanf ("%d", &q[i]);
    
    merge_sort(q, 0, n - 1);
    
    for (int i = 0; i < n; ++i) printf("%d ", q[i]);
    return 0;
}

堆排序（Heap Sort）：
- 原理：将数组构建成一个最大堆（或最小堆），然后将堆顶元素与堆的最后一个元素交换，并将堆的大小减1。重复这个过程，直到堆为空。通过这种方式，最大（或最小）的元素会被依次放置到数组的末尾，从而实现排序。
- 时间复杂度：平均情况和最坏情况下的时间复杂度都为O(nlogn)。
- 空间复杂度：O(1)。

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 100010;
int h[N], mysize, n, m;

void down(int u)
{
    int t = u;
    if (2 * u <= mysize && h[t] > h[2 * u]) t = 2 * u;
    if (2 * u + 1 <= mysize && h[t] > h[2 * u + 1]) t = 2 * u + 1; 
    if (u != t)
    {
        swap(h[u], h[t]);
        down(t);
    }
}

int main()
{
    cin >> n >> m;
    mysize = n;
    for (int i = 1; i <= n; ++ i)
        cin >> h[i];
    for (int i = n / 2; i; i --)   // 如果i > n / 2 那么上面的 2 * u > size 那么 u = t 会进行很多没有意义的计算
        down(i);
    while (m --)
    {
        cout << h[1] << ' ';
        h[1] = h[mysize --];
        down(1);
    }
    return 0;
}

后面就是计算机组成原理的了，选择题记不清了，我计算机组成原理很差，所以就讲解一下简答题

辅存（辅助存储器）：辅存是计算机系统中最慢但容量最大的存储层次。它通常指的是硬盘、固态硬盘（SSD）等外部存储设备。辅存具有较大的存储容量，能够长期保存数据，但是访问速度较慢。辅存主要用于存储操作系统、应用程序、文件和其他数据。
主存（主存储器）：主存是计算机系统中位于辅存和Cache之间的存储层次。它通常指的是随机访问存储器（RAM）或动态随机访问存储器（DRAM）。主存具有较快的访问速度和较大的存储容量，用于存储当前正在运行的程序和数据。CPU通过地址总线和数据总线与主存进行通信，可以读取和写入主存中的数据。
Cache（高速缓存）： Cache是计算机系统中位于CPU和主存之间的存储层次。它是一种速度非常快、容量较小但比主存大的存储器。Cache的作用是通过存储最近使用的数据和指令，提高CPU对数据的访问速度。当CPU需要读取数据时，首先在Cache中查找，如果找到了，则称为“命中”，可以直接从Cache中获取数据，这样可以大大减少访问主存的时间。如果在Cache中没有找到需要的数据，则称为“未命中”，CPU需要从主存中读取数据，并将其存储到Cache中，以供后续访问使用。

Cache-主存-辅存结构的设计是为了在存储层次结构中实现高效的数据访问。Cache作为CPU与主存之间的缓冲区域，可以快速提供数据，减少CPU等待数据的时间。主存作为临时存储区域，存储当前正在运行的程序和数据。辅存作为永久存储区域，用于长期保存数据和程序。通过合理设计和管理这三个层次的存储结构，可以提高计算机系统的性能和效率。

二分查找代码实现

这个不难，就是算法导论里面的原题。

int binarySearch(const std::vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

最长连续不重复子序列

这个也是算法导论上面的题目，算法思路是双指针法.双指针算法最经典的题目

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;

int a[N], s[N];
int n, res;

int main()
{
    cin >> n;
    for (int i = 0; i < n; ++ i) cin >> a[i];
    for (int i = 0, j = 0; i < n; ++ i)
    {
        s[a[i]] ++; // 记录下a[i]出现的次数
        while(s[a[i]] > 1)   // 一点碰见两个重复的元素后
        {  
            s[a[j]] --;  // 这里要主要的一点是这个算法是没有回溯的
                         // 不要被for循环里面的条件误导以为会回溯、
                         // 现在遇到两个相同的元素了
                         // ！！！ 现在是这个算法最厉害的地方 
                         // 这个j代表的是 j可以到达最左的地方 所以在j左边的
                         // 元素的个数就需要都-- 这点很妙
            j ++;        // 然后j++
        }
        res = max(res, i - j + 1);  // 这个res的含义是 在i这个位置、
        // 可以达到的符合题目条件的最大长度
    }
    cout << res;
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-10-28，如有侵权请联系 cloudcommunity@tencent.com 删除

面试

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度