数据结构与算法应用（浙大，算法题）

一、 线性表

1.1 最大子列和问题

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

  • 算法一 O(N^3)

    int maxSubSeqSum1(int a[], int n) {
    int tmpSum = 0, maxSum = a[0];
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            tmpSum = 0;
            for (int k = i; k <= j; k++) {
                tmpSum += a[k];
            }
            maxSum = tmpSum > maxSum ? tmpSum : maxSum;
        }
    }
    return maxSum;
}

  • 算法二 O(N^2)

    int maxSubSeqSum2(int a[], int n) {
    int tmpSum = 0, maxSum = a[0];
    for (int i = 0; i < n; i++) {
        tmpSum = 0;
        for (int j = i; j < n; j++) {
            tmpSum += a[j];
            maxSum = tmpSum > maxSum ? tmpSum : maxSum;
        }
    }
    return maxSum;
}

  • 算法三 O(N*logN)

    int Max3(int A, int B, int C) {   /* 返回3个整数中的最大值 */
    return A > B ? A > C ? A : C : B > C ? B : C;
}

int DivideAndConquer(int List[], int left, int right) {   /* 分治法求List[left]到List[right]的最大子列和 */
    int MaxLeftSum, MaxRightSum; /* 存放左右子问题的解 */
    int MaxLeftBorderSum, MaxRightBorderSum; /*存放跨分界线的结果*/
    int LeftBorderSum, RightBorderSum;
    int center, i;

    if (left == right)  /* 递归的终止条件，子列只有1个数字 */
        if (List[left] > 0) return List[left];
        else return 0;

    /* 下面是"分"的过程 */
    center = (left + right) / 2; /* 找到中分点 */
    /* 递归求得两边子列的最大和 */
    MaxLeftSum = DivideAndConquer(List, left, center);
    MaxRightSum = DivideAndConquer(List, center + 1, right);

    /* 下面求跨分界线的最大子列和 */
    MaxLeftBorderSum = 0;
    LeftBorderSum = 0;
    for (i = center; i >= left; i--) { /* 从中线向左扫描 */
        LeftBorderSum += List[i];
        if (LeftBorderSum > MaxLeftBorderSum)
            MaxLeftBorderSum = LeftBorderSum;
    } /* 左边扫描结束 */
    MaxRightBorderSum = 0;
    RightBorderSum = 0;
    for (i = center + 1; i <= right; i++) { /* 从中线向右扫描 */
        RightBorderSum += List[i];
        if (RightBorderSum > MaxRightBorderSum)
            MaxRightBorderSum = RightBorderSum;
    } /* 右边扫描结束 */

    /* 下面返回"治"的结果 */
    return Max3(MaxLeftSum, MaxRightSum,
                MaxLeftBorderSum + MaxRightBorderSum);
}

int maxSubSeqSum3(int List[], int N) {   /* 保持与前2种算法相同的函数接口 */
    return DivideAndConquer(List, 0, N - 1);
}

  • 算法四 O(N)

    int maxSubSeqSum4(int a[], int n) {
    int tmpSum = 0, maxSum = a[0];
    for (int i = 0; i < n; i++) {
        tmpSum += a[i];
        if (tmpSum > maxSum) {
            maxSum = tmpSum;
        }
        if (tmpSum < 0) {
            tmpSum = 0;
        }
    }
    return maxSum;
}

二、 堆栈

2.1 后缀表达式求值

从左到右读入后缀表达式的各项（运算符或运算数）；

  1. 运算数：入栈；
  2. 运算符：从堆栈中弹出适当数量的运算数，计算并结果入栈；
  3. 最后，堆栈顶上的元素就是表达式的结果值。

2.2 中缀表达式求值

将中缀表达式转换为后缀表达式，然后求值

#include <iostream>
#include <string>

#define MAXSIZE 400
using namespace std;

template<class T>
class Stack {
public:
    T data[MAXSIZE];
    int head;

    Stack() : head(-1) {}

    void push(T val) {
        if (head == MAXSIZE - 1) {
            return;
        }
        data[++head] = val;
    }

    T pop() {
        return data[head--];
    }

    bool empty() {
        return head == -1;
    }

    T top() {
        return data[head];
    }

};

bool judgeOpeEqual(char c1, char c2) {
    if (c1 == '(') {
        return true;
    }
    if (c1 == '-' || c1 == '+') {
        if (c2 == '*' || c2 == '/') {
            return true;
        } else if (c2 == '-' || c2 == '+') {
            return false;
        }
    } else if (c1 == '*' || c1 == '/') {
        return false;
    }
    return false;
}

int operate(Stack<char> stack) {
    Stack<int> numStack;
    for (int i = 0; i <= stack.head; i++) {
        char c = stack.data[i];
        int num = c - '0';
        if (num >= 0 && num <= 9) {
            numStack.push(num);
        } else {
            int a = numStack.pop();
            int b = numStack.pop();
            switch (c) {
                case '+':
                    numStack.push(b + a);
                    break;
                case '-':
                    numStack.push(b - a);
                    break;
                case '*':
                    numStack.push(b * a);
                    break;
                case '/':
                    numStack.push(b / a);
                    break;
            }
        }
    }
    return numStack.pop();
}

int main() {
    Stack<char> opeStack;
    Stack<char> ansStack;

    string str;
    cin >> str;
    for (int i = 0; i < str.size(); i++) {
        int num = str[i] - '0';
        if (num >= 0 && num <= 9) {
            ansStack.push(str[i]);
        } else {
            char ope = str[i];
            if (opeStack.empty()) {
                opeStack.push(ope);
            } else {
                char topOpe = opeStack.top();
                if (ope == '(') {
                    opeStack.push(ope);
                } else if (ope == ')') {
                    while (opeStack.top() != '(')
                        ansStack.push(opeStack.pop());
                    opeStack.pop();
                } else {
                    while (!opeStack.empty() && !judgeOpeEqual(topOpe, ope)) {
                        ansStack.push(opeStack.pop());
                        topOpe = opeStack.top();
                    }
                    opeStack.push(ope);
                }
            }
        }
    }

    while (!opeStack.empty()) {
        ansStack.push(opeStack.pop());
    }

    cout << operate(ansStack) << endl;
}

三、 队列

3.1 多项式加法运算

算法思路：两个指针P1和P2分别指向这两个多项式第一个结点，不断循环

P1->expon==P2->expon: 系数相加，若结果不为0，则作为结果多项式对应项 的系数。同时，P1和P2都分别指向下一项；

P1->expon>P2->expon: 将P1的当前项存入结果多项式，并使P1指向下一项；

P1->exponexpon: 将P2的当前项存入结果多项式，并使P2指向下一项；

class Node {
public:
    int coef; //系数
    int expon; // 指数
    Node *next;

    Node(int coef, int expon) : coef(coef), expon(expon), next(nullptr) {}
};

class Queue {
public:
    Node *front;
    Node *rear;

    Queue() : front(nullptr), rear(nullptr) {}

    void push(Node *node) {
        if (rear == nullptr) { /*队列为空*/
            front = rear = node;
            return;
        }
        rear->next = node;
        rear = rear->next;
    }

    Node *pop() {
        if (front == nullptr) {
            throw "队列为空";
        }

        Node *ans = front;
        if (front == rear) { /*只有一个元素*/
            front = rear = nullptr;
        } else {
            front = front->next;
        }
        return ans;
    }
};

Queue add(Node *q1, Node *q2) {
    Queue ans;
    Node *tmp;

    while (q1 && q2) {
        if (q1->expon - q2->expon > 0) {
            ans.push(q1);
            q1 = q1->next;
        } else if (q1->expon - q2->expon < 0) {
            ans.push(q2);
            q2 = q2->next;
        } else {
            int sum = q1->coef + q2->coef;
            tmp = new Node(sum, q1->expon);
            ans.push(tmp);
            q1 = q1->next;
            q2 = q2->next;
        }
    }

    for (; q1; q1 = q1->next) ans.push(q1);
    for (; q2; q2 = q2->next) ans.push(q2);

    return ans;
}

四、 图

4.1 旅游问题（改造最短路）

const int INF = 2147413647;
const int MAXN = 1e5 + 6;

struct Node {
    int endIndex, weight, cost;

    Node(int endIndex, int weight, int cost) : endIndex(endIndex), weight(weight), cost(cost) {}
};

vector<Node *> Adj[MAXN]; //Adj为图的邻接表
int n; //n为顶点数，MAXN为最大顶点数
int dist[MAXN], path[MAXN], vis[MAXN], price[MAXN];

int getLeastPos() {
    int minDist = INF, minCost = INF, ans = -1;
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            if (dist[i] < minDist || (dist[i] == minDist && price[i] < minCost)) {
                minDist = dist[i];
                minCost = price[i];
                ans = i;
            }
        }
    }
    return ans;
}

void Dijkstra(int start) {
    dist[start] = 0;
    while (true) {
        int leastPos = getLeastPos();
        if (leastPos == -1) break;

        vis[leastPos] = 1;
        for (int i = 0; i < Adj[leastPos].size(); i++) {
            int endIndex = Adj[leastPos][i]->endIndex;
            int weight = dist[leastPos] + Adj[leastPos][i]->weight;
            int cost = price[leastPos] + Adj[leastPos][i]->cost;
            if (!vis[endIndex]) {
                if (dist[endIndex] > weight) {
                    dist[endIndex] = weight;
                    path[endIndex] = leastPos;
                    price[endIndex] = cost;
                } else if (dist[endIndex] == weight) {
                    if (price[endIndex] > cost) {
                        dist[endIndex] = weight;
                        path[endIndex] = leastPos;
                        price[endIndex] = cost;
                    }
                }
            }
        }
    }
}

void init() {
    cin >> n;
    int edgeNum;
    cin >> edgeNum;

    while (edgeNum--) {
        int s, e, w, cost;
        scanf("%d%d%d%d", &s, &e, &w, &cost);
        Adj[s].push_back(new Node(e, w, cost));
    }

    fill(path, path + n + 1, -1);
    fill(dist, dist + n + 1, INF);
}

其他类似问题

hhhhh