# AlgorithmCourse

**Repository Path**: vz2/algorithm-course

## Basic Information

- **Project Name**: AlgorithmCourse
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 1
- **Forks**: 0
- **Created**: 2021-12-16
- **Last Updated**: 2022-04-14

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 程序设计与算法训练

#### 考试要求

1.  考试的判题平台为外网，请准备校园网账号用于登录和联网；
2.  考场内严禁携带任何电子设备，包括手机、手表、耳机、计算器等；
3.  必须携带 **学生证或身份证** 用于审核。

#### 201-206班

1.  考试时间为12.19下午 **13:30 ~ 15:30** ，两个小时；
2.  请提前10分钟到达考场，不允许提前交卷，不允许中途离开考场；
3.  考试结束离开考场时 **禁止在楼内讨论试题** ，一经发现当场取消成绩；
4.  201班在601、202班在602、203班在603、204班在604、205班在605，206班在6楼走廊等待监考老师分配座位。


#### 207-2012班

1.  考试时间为12.19下午 **15:40 ~ 17:40** ，两个小时；
2.  必须提前 **15分钟** 到达实验楼5楼签到并上交通讯设备，未按时到达并签到的同学取消考试资格；
3.  207班在601、208班在602、209班在603、2010班在604、2011班在605，2012班等待监考老师分配座位。

#### 总分结构

1.  平时分（20%），4次签到，每次25分；
2.  作业分（30%），7次作业取平均分；
3.  期末考（50%）。

#### 课程须知

所有分数将在12.30前统计完成，期末考的分数将在 **实验作业8** 中给到每位同学，符合以下条件的同学可以在 **2022年1月3日** 前找老师改分：

1.  作业格式完全正确但被评 0 分；
2.  作业没有抄袭他人，也没有将代码给他人抄袭但被评 60 分；
3.  期末考前 4 题AC，最后总分不及格的；
4.  期末考全部题目AC。

#### 题目构成

1.  反转链表（15%）
- C语言

```
struct Node* solve(struct Node* head)
{
    if (head == NULL) return NULL;
    struct Node* node = (*head).next;
    if (node == NULL) return head;
    struct Node* root = solve(node);
    (*node).next = head;
    (*head).next = NULL;
    return root;
}
```
- C++

```
Node* solve(Node* head)
{
    if (head == nullptr) return nullptr;
    Node* node = (*head).next;
    if (node == nullptr) return head;
    Node* root = solve(node);
    (*node).next = head;
    (*head).next = nullptr;
    return root;
}
```
- Java

```
Node solve(Node head) {
    if (head == null) return null;
    Node node = head.next;
    if (node == null) return head;
    Node root = solve(node);
    node.next = head;
    head.next = null;
    return root;
}
```

2.  大数相加取模（15%）
- C语言

```
long long parse(char* s, int l, int r) {
    long n = 0;
    for (int i = l; i < r; i++) n = n * 10 + s[i] - '0';
    return n;
}

long long mod(char* s, int n, int len) {
    if (len == 0) return 0;
    if (len <= 8) return parse(s, 0, len) % n;
    return ((mod(s, n, len - 8) * (100000000 % n)) % n + parse(s, len - 8, len) % n) % n;
}

int calc(char* s, int n) {
    int m = -1;
    while (s[++m] != '\0');
    return mod(s, n, m);
}

int solve(char* a, char* b, int nn)
{
    int i = 10000, m = -1, n = -1, k = 0;
    char* str = (char*)malloc(sizeof(char) * i);
    str[--i] = '\0';
    while (a[++m] != '\0');
    while (b[++n] != '\0');
    while (m > 0 || n > 0) {
        if (--m >= 0) k += a[m] - '0';
        if (--n >= 0) k += b[n] - '0';
        str[--i] = '0' + k % 10;
        k /= 10;
    }
    if (k > 0) str[--i] = '0' + k;
    return calc(str + sizeof(char) * i, nn);
}
```
- C++
```
long long parse(string s, int l, int r) {
    long n = 0;
    for (int i = l; i < r; i++) n = n * 10 + s[i] - '0';
    return n;
}

long long mod(string s, int n, int len) {
    if (len == 0) return 0;
    if (len <= 8) return parse(s, 0, len) % n;
    return ((mod(s, n, len - 8) * (100000000 % n)) % n + parse(s, len - 8, len) % n) % n;
}

int calc(string s, int n) {
    return mod(s, n, s.size());
}

int solve(string a, string b, int nn)
{
    int m = a.size(), n = b.size(), k = 0;
    string str;
    while (m > 0 || n > 0) {
        if (--m >= 0) k += a[m] - '0';
        if (--n >= 0) k += b[n] - '0';
        str.insert(0, 1, '0' + k % 10);
        k /= 10;
    }
    if (k > 0) str.insert(0, 1, '0' + k);
    return calc(str, nn);
}
```
- Java

```
int len = 9;
int mod(String s, int n) {
    int val = Integer.parseInt(s.substring(Math.max(s.length() - len, 0))) % n;
    if (s.length() <= len) return val;
    return (int)(((long)Math.pow(10, len) % n * mod(s.substring(0, s.length() - len), n) % n + val) % n);
}

int solve(String a, String b, int nn) {
    StringBuilder s = new StringBuilder();
    int m = a.length(), n = b.length(), k = 0;
    while (m > 0 || n > 0) {
        if (--m >= 0) k += a.charAt(m) - '0';
        if (--n >= 0) k += b.charAt(n) - '0';
        s.insert(0, k % 10);
        k /= 10;
    }
    if (k > 0) s.insert(0, k);
    return mod(s.toString(), nn);
}
```

3.  矩阵中第k小的数（15%）
- C语言

```
int numSmallerThanMid(int** matrix, int n, int mid) {
    int i = n - 1;
    int j = 0;
    int k = 0;
    while (i >= 0 && j < n) {
        if (matrix[i][j] > mid) i--;
        else {
            k += i + 1;
            j++;
        }
    }
    return k;
}

//matrix 是 n x n 的二维矩阵
int solve(int** matrix, int n, int k) {
    int l = matrix[0][0], r = matrix[n - 1][n - 1];
    while (l < r) {
        int mid = (r - l) / 2 + l;
        if (numSmallerThanMid(matrix, n, mid) < k) l = mid + 1;
        else r = mid;
    }
    return l;
}
```
- C++

```
int numSmallerThanMid(vector<vector<int>>& matrix, int mid) {
    int n = matrix.size();
    int i = n - 1;
    int j = 0;
    int k = 0;
    while (i >= 0 && j < n) {
        if (matrix[i][j] > mid) i--;
        else {
            k += i + 1;
            j++;
        }
    }
    return k;
}

int solve(vector<vector<int>>& matrix, int k) {
    int n = matrix.size();
    int l = matrix[0][0], r = matrix[n - 1][n - 1];
    while (l < r) {
        int mid = (r - l) / 2 + l;
        if (numSmallerThanMid(matrix, mid) < k) l = mid + 1;
        else r = mid;
    }
    return l;
}
```
- Java

```
int numSmallerThanMid(int[][] matrix, int mid) {
    int i = matrix.length - 1;
    int j = 0;
    int k = 0;
    while (i >= 0 && j < matrix[i].length) {
        if (matrix[i][j] > mid) i--;
        else {
            k += i + 1;
            j++;
        }
    }
    return k;
}
	
int solve(int[][] matrix, int k) {
    int l = matrix[0][0], r = matrix[matrix.length - 1][matrix[0].length - 1];
    while (l < r) {
        int mid = (r - l) / 2 + l;
        if (numSmallerThanMid(matrix, mid) < k) l = mid + 1;
        else r = mid;
    }
    return l;
}
```

4.  矩阵中最大正方形的边长（15%）
- C语言

```
//matrix是m x n的二维矩阵
int solve(int** matrix, int m, int n) {
    int** a = malloc(sizeof(int*)* m);
    int max = 0;
    for (int i = 0; i < m; i++) {
        a[i] = malloc(sizeof(int) * n);
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == 0) continue;
            if (i == 0 || j == 0 || matrix[i - 1][j - 1] == 0) a[i][j] = 1;
            else {
                a[i][j] = a[i - 1][j - 1] + 1;
                for (int k = 1; k <= a[i - 1][j - 1]; k++) {
                    if (matrix[i - k][j] == 0 || matrix[i][j - k] == 0) {
                        a[i][j] = k;
                        break;
                    }
                }
            }
            if (a[i][j] > max) max = a[i][j];
        }
    }
    return max;
}
```
- C++

```
int solve(vector<vector<int>>& matrix) {
    vector<vector<int>> a;
    int max = 0;
    for (int i = 0; i < matrix.size(); i++) {
        vector<int> b;
        for (int j = 0; j < matrix[i].size(); j++) {
            int v = 1;
            if (matrix[i][j] == 0) v = 0;
            else if (i > 0 && j > 0 && matrix[i - 1][j - 1] == 1) {
                v = a[i - 1][j - 1] + 1;
                for (int k = 1; k <= a[i - 1][j - 1]; k++) {
                    if (matrix[i - k][j] == 0 || matrix[i][j - k] == 0) {
                        v = k;
                        break;
                    }
                }
            }
            if (v > max) max = v;
            b.push_back(v);
        }
        a.push_back(b);
    }
    return max;
}
```
- Java

```
int solve(int[][] matrix) {
    int[][] a = new int[matrix.length][matrix[0].length];
    int max = 0;
    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix[i].length; j++) {
            if (matrix[i][j] == 0) continue;
            if (i == 0 || j == 0 || matrix[i - 1][j - 1] == 0) a[i][j] = 1;
            else {
                a[i][j] = a[i - 1][j - 1] + 1;
                for (int k = 1; k <= a[i - 1][j - 1]; k++) {
                    if (matrix[i - k][j] == 0 || matrix[i][j - k] == 0) {
                        a[i][j] = k;
                        break;
                    }
                }
            }
            if (a[i][j] > max) max = a[i][j];
        }
    }
    return max;
}
```

5.  汉诺塔（20%）

6.  [搜索题]（20%）