王道考研机试指南重写

算法专栏（按时间排序）
王道考研机试指南代码合集
王道考研机试指南重写
算法分析上机作业
leetcode记录
leetcode记录2
牛客网刷题记录与企业机试记录

前言

几年前为了应付有些学校的机试，大概刷了一遍《王道考研机试指南》这本书里的代码王道考研机试指南代码合集。几年过去了想重新刷一遍，加强一下算法能力，同时也熟悉c++的新特性。以下代码不注重算法性能，而是尽可能使用一些新特性并保持代码规范（尝试规范）Google 开源项目风格指南。

代码随缘写，章节也不固定
代码环境：linux vscode

Makefile文件（改别人博客上的）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
.PHONY: all clean     # .PHONY后面的target表示的也是一个伪造的target, 而不是真实存在的文件target
SRC=$(wildcard *.cpp) 		# 获取工作目录下的所有的.cpp文件列表
BIN=$(SRC:%.cpp=%)          # 替换扩展名
CC=g++
# -Wall   生成常见的所有告警信息
# -g  用于在生成的目标可执行文件中，添加调试信息，可以使用GDB进行调试
# -o 用于连接生成可执行文件，在其后可以指定输出文件的名称
# -c 用于把源码文件编译成 .o 对象文件,不进行链接过程（之前误用了这个选项，编译完后运行显示没有权限）
CXXFLAGS=-Wall -g  -std=c++2a -o

all:$(BIN)

# $^ 指代所有前置条件，之间以空格分隔
# $@ 指代当前目标，就是Make命令当前构建的那个目标
$(BIN):%:%.cpp
	$(CC) $^  $(CXXFLAGS)  $@

clean:
	rm  $(BIN)

数据结构一章

栈的应用

括号匹配问题

题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <stack>
#include <string>

class Solution {
public:
  bool IsMatch(const std::string &s) {
    std::stack<char> symbol_stack;
    std::string left_bracket = "{[(";
    std::string right_bracket = "}])";
    char top_char;
    for (auto c : s) {
      if (left_bracket.find(c) != left_bracket.npos) { // 若为左括号
        symbol_stack.emplace(c);
      } else {
        auto pos = right_bracket.find(c);
        if (pos != right_bracket.npos) { // 若为右括号
          if (symbol_stack.empty()) {
            return false;
          }
          top_char = symbol_stack.top();
          if (top_char != left_bracket[pos]) { // 与栈顶的符号不匹配
            return false;
          }
          symbol_stack.pop();
        }
      }
    }
    return true;
  }
};

int main() {
  Solution solution;
  std::string input;
  std::cin >> input;
  bool ans = solution.IsMatch(input);
  if (ans) {
    std::cout << "true" << std::endl;
  } else {
    std::cout << "false" << std::endl;
  }
}

简单计算器

题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// simple_calculator.h
#include <iostream>
#include <stack>
#include <string>
#include <tuple>

class Solution {
 public:
  void SetExpr(const std::string &expr);
  double GetExprValue();

 private:
  auto GetNumber(std::size_t pos) const;
  int GetOpPriority(char op) const;
  void ProcessSymbol(char symbol);

  std::string expr_;
  std::stack<char> symbol_stack_;
  std::stack<double> number_stack_;
  std::string operators_;
  char markup_char_{'m'};  // 特殊运算符
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
// simple_calculator.cpp
#include "simple_calculator.h"

// 从字符串pos位置开始读取数字，直到读到空格
// 返回转换的数字与空格下标
auto Solution::GetNumber(std::size_t pos) const {
  double res = 0;
  while (expr_[pos] != ' ') {
    res = res * 10 + expr_[pos] - '0';
    pos++;
  }
  return std::make_tuple(res, pos);
}
// 返回运算符的优先级
int Solution::GetOpPriority(char op) const {
  if (op == '*' || op == '/') {
    return 3;
  }
  if (op == '+' || op == '-') {
    return 2;
  }
  if (op == markup_char_) {  // 特殊运算符返回最低优先级
    return 1;
  }
  return 0;
}
// 对运算符进行处理
void Solution::ProcessSymbol(char symbol) {
  int symbol_priority = GetOpPriority(symbol);
  char top_symbol = symbol_stack_.top();
  int top_priority = GetOpPriority(top_symbol);
  if (symbol_priority > top_priority) {  // 大于栈顶运算符优先级，入栈
    symbol_stack_.emplace(symbol);
  } else {  // 将栈顶运算符出栈，进行相应的运算
    if (top_symbol == markup_char_) {  // 代表表达式字符串遍历到了末尾
      return;
    }
    double lhs, rhs, res;
    rhs = number_stack_.top();
    number_stack_.pop();
    lhs = number_stack_.top();
    number_stack_.pop();

    switch (top_symbol) {
      case '+': {
        res = lhs + rhs;
        break;
      }
      case '-': {
        res = lhs - rhs;
        break;
      }
      case '*': {
        res = lhs * rhs;
        break;
      }
      case '/': {
        res = lhs / rhs;
        break;
      }
    }
    number_stack_.emplace(res);
    symbol_stack_.pop();
    ProcessSymbol(symbol);  // 循环处理
  }
}
void Solution::SetExpr(const std::string &expr) {
  expr_ = expr + " " + markup_char_;  // 在表达式末尾加上" m"
  operators_ = "+-*/";
  operators_ += markup_char_;
  while (!symbol_stack_.empty()) {
    symbol_stack_.pop();
  }
  symbol_stack_.emplace(markup_char_);  // 将特殊运算符压入栈中
  while (!number_stack_.empty()) {
    number_stack_.pop();
  }
}
double Solution::GetExprValue() {
  std::size_t expr_len = expr_.length();
  for (std::size_t i = 0; i < expr_len; i++) {
    if (operators_.find(expr_[i]) != operators_.npos) {
      ProcessSymbol(expr_[i]);
    } else if (expr_[i] != ' ') {  // 数字部分
      auto [res, new_pos] = GetNumber(i);
      i = new_pos;
      number_stack_.emplace(res);
    }
  }
  return number_stack_.top();
}

int main() {
  Solution solution;
  std::string expr;
  double ans;

  while (getline(std::cin, expr)) {
    if (expr.length() == 1 && expr[0] == '0') {
      break;
    }
    solution.SetExpr(expr);
    ans = solution.GetExprValue();
    printf("%.2f\n", ans);
  }
  return 0;
}

在这里我将代码写成两个文件一是因为函数比较多，全部写在类里有点难看。二是因为GetNumber函数的返回类型使用的是自动类型推导，但当GetExprValue调用它时，auto还没有进行推导过程，会报错

1
use of 'auto GetNumber(std::size_t pos) const;' before deduction of 'auto'

哈夫曼树

哈夫曼树

题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <array>
#include <iostream>
#include <queue>
#include <vector>
class Solution {
 public:
  int GetWeight(const std::vector<int>& arr) {
    // 小顶堆
    std::priority_queue<int, std::vector<int>, std::greater<int>> queue;
    for (auto item : arr) {
      queue.emplace(item);
    }
    int weight = 0;
    int m, n;
    while (queue.size() > 1) {  // 取出两个最小的数字，将其和放入堆中
      m = queue.top();
      queue.pop();
      n = queue.top();
      queue.pop();
      queue.emplace(m + n);
      weight += m + n;  // 所有非叶节点权值之和即为哈夫曼树权值
    }
    return weight;
  }
};

int main() {
  Solution solution;
  int n;
  while (std::cin >> n) {
    std::vector<int> arr;
    arr.resize(n);
    for (int i = 0; i < n; i++) {
      std::cin >> arr[i];
    }
    int ans = solution.GetWeight(arr);
    std::cout << ans << std::endl;
  }
  return 0;
}

可以声明数组时直接指定大小std::vector arr(n);，但我觉得resize更好看一些。

二叉树

二叉树遍历

题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <memory>
#include <string>

class BinaryTree {
  struct Node {  // 二叉树节点
    Node(){};
    Node(std::shared_ptr<Node> lchild, std::shared_ptr<Node> rchild,
         char content)
        : lchild_(lchild), rchild_(rchild), content_(content){};
    std::shared_ptr<Node> lchild_;
    std::shared_ptr<Node> rchild_;
    char content_;
  };
  using LinkNode = std::shared_ptr<Node>;

 public:
  void BuildTree(const std::string& preorder, const std::string& inorder) {
    root_ = BuildTreeImpl(preorder, inorder);
    postorder_string_ = "";
  }
  std::string GetPostorderString() {
    PostorderVisit(root_);  // 进行后序遍历，生成相应字符串
    return postorder_string_;
  }

 private:
  LinkNode BuildTreeImpl(const std::string& preorder,
                         const std::string& inorder);
  void PostorderVisit(LinkNode node);
  LinkNode root_;                 // 二叉树根节点
  std::string postorder_string_;  // 后序遍历字符串
};

BinaryTree::LinkNode BinaryTree::BuildTreeImpl(const std::string& preorder,
                                               const std::string& inorder) {
  if (preorder.empty()) {
    return {};
  }
  auto len = preorder.length();
  char root_char = preorder[0];
  // 将前序字符串切分成根 左子树 右子树，将中序字符串切分成左子树 根 右子树
  auto pos = inorder.find(root_char);
  auto pre_left = preorder.substr(1, pos);
  auto pre_right = preorder.substr(pos + 1, len - pos - 1);
  auto in_left = inorder.substr(0, pos);
  auto in_right = inorder.substr(pos + 1, len - pos - 1);
  auto lchild = BuildTreeImpl(pre_left, in_left);    // 构建左子树
  auto rchild = BuildTreeImpl(pre_right, in_right);  // 构建右子树
  auto node = std::make_shared<BinaryTree::Node>(lchild, rchild, root_char);
  return node;
}
// 进行后序遍历，并将结果保存至字符串中
void BinaryTree::PostorderVisit(LinkNode node) {
  if (node == nullptr) {
    return;
  }
  PostorderVisit(node->lchild_);
  PostorderVisit(node->rchild_);
  postorder_string_.push_back(node->content_);
}
int main() {
  BinaryTree tree;
  std::string preorder;
  std::string inorder;
  while (std::cin >> preorder >> inorder) {
    tree.BuildTree(preorder, inorder);
    std::cout << tree.GetPostorderString() << std::endl;
  }
  return 0;
}

使用智能指针而不使用原始指针构建二叉树

二叉排序树

二叉排序树

题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <iostream>
#include <memory>
#include <vector>

class BinaryTree {
  struct Node {  // 二叉树节点
    Node(){};
    Node(std::shared_ptr<Node> lchild, std::shared_ptr<Node> rchild,
         char content)
        : lchild_(lchild), rchild_(rchild), content_(content){};
    std::shared_ptr<Node> lchild_;
    std::shared_ptr<Node> rchild_;
    int content_;
  };
  using LinkNode = std::shared_ptr<Node>;

 public:
  void BuildTree(const std::vector<int>& arr) {
    for (int item : arr) {
      Insert(root_, item);
    }
  }
  void PrintTraversalResult() {  // 输出3种遍历结果
    PreorderVisit(root_);
    std::cout << std::endl;
    InorderVisit(root_);
    std::cout << std::endl;
    PostorderVisit(root_);
    std::cout << std::endl;
  }

 private:
  void Insert(LinkNode& node, int num);
  void PreorderVisit(LinkNode node);
  void InorderVisit(LinkNode node);
  void PostorderVisit(LinkNode node);
  LinkNode root_;  // 二叉树根节点
};

// 输入智能指针的引用，省去返回值。
// LinkNode BinaryTree::Insert(LinkNode node, int num)
void BinaryTree::Insert(LinkNode& node, int num) {
  if (node == nullptr) {
    node = std::make_shared<Node>(nullptr, nullptr, num);
    return;
  }
  if (node->content_ > num) {
    Insert(node->lchild_, num);
  } else if (node->content_ < num) {
    Insert(node->rchild_, num);
  }
}
void BinaryTree::PreorderVisit(LinkNode node) {
  if (node == nullptr) {
    return;
  }
  std::cout << node->content_ << " ";
  PreorderVisit(node->lchild_);
  PreorderVisit(node->rchild_);
}
void BinaryTree::InorderVisit(LinkNode node) {
  if (node == nullptr) {
    return;
  }
  InorderVisit(node->lchild_);
  std::cout << node->content_ << " ";
  InorderVisit(node->rchild_);
}
void BinaryTree::PostorderVisit(LinkNode node) {
  if (node == nullptr) {
    return;
  }
  PostorderVisit(node->lchild_);
  PostorderVisit(node->rchild_);
  std::cout << node->content_ << " ";
}
int main() {
  int n;
  while (std::cin >> n) {
    BinaryTree tree;
    std::vector<int> arr;
    arr.resize(n);
    for (int i = 0; i < n; i++) {
      std::cin >> arr[i];
    }
    tree.BuildTree(arr);
    tree.PrintTraversalResult();
  }
  return 0;
}
  1. 复制粘贴代码记得检查一下：由于几种遍历方式差不多，我直接复制粘贴然后改一下次序，后面debug了很久才发现函数名没改，同时写成了两个lchild_
  2. No rule to make target ‘binary_sort_tree.cpp’, needed by ‘binary_sort_tree’. Stop.
    文件名前有一个空格，导致报错，使用ls命令就能很明显看出

二叉搜索树

题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <iostream>
#include <memory>
#include <string>

class BinaryTree {
  struct Node {  // 二叉树节点
    Node(){};
    Node(std::shared_ptr<Node> lchild, std::shared_ptr<Node> rchild,
         char content)
        : lchild_(lchild), rchild_(rchild), content_(content){};
    std::shared_ptr<Node> lchild_;
    std::shared_ptr<Node> rchild_;
    char content_;
  };
  using LinkNode = std::shared_ptr<Node>;

 public:
  void BuildTree(const std::string& arr) {
    for (char item : arr) {
      Insert(root_, item);
    }
    GenerateTraversalSequence();  // 生成遍历序列
  }
  // 返回可供比较的序列
  std::string GetCompareSequence() const { return preorder_ + inorder_; }
  bool Compare(const BinaryTree& tree) {
    return GetCompareSequence() == tree.GetCompareSequence();
  }

 private:
  void Insert(LinkNode& node, char num);
  void GenerateTraversalSequence();
  void PreorderVisit(LinkNode node);
  void InorderVisit(LinkNode node);
  void PostorderVisit(LinkNode node);

  LinkNode root_;  // 二叉树根节点
  std::string preorder_;
  std::string inorder_;
  std::string postorder_;
};

// 输入智能指针的引用，省去返回值。
// LinkNode BinaryTree::Insert(LinkNode node, int num)
void BinaryTree::Insert(LinkNode& node, char num) {
  if (node == nullptr) {
    node = std::make_shared<Node>(nullptr, nullptr, num);
    return;
  }
  if (node->content_ > num) {
    Insert(node->lchild_, num);
  } else if (node->content_ < num) {
    Insert(node->rchild_, num);
  }
}
void BinaryTree::PreorderVisit(LinkNode node) {
  if (node == nullptr) {
    return;
  }
  preorder_.push_back(node->content_);
  PreorderVisit(node->lchild_);
  PreorderVisit(node->rchild_);
}
void BinaryTree::InorderVisit(LinkNode node) {
  if (node == nullptr) {
    return;
  }
  InorderVisit(node->lchild_);
  inorder_.push_back(node->content_);
  InorderVisit(node->rchild_);
}
void BinaryTree::PostorderVisit(LinkNode node) {
  if (node == nullptr) {
    return;
  }
  PostorderVisit(node->lchild_);
  PostorderVisit(node->rchild_);
  postorder_.push_back(node->content_);
}
// 只需生成前序与中序序列即可
void BinaryTree::GenerateTraversalSequence() {
  PreorderVisit(root_);
  InorderVisit(root_);
}
int main() {
  int n;
  std::string seq;
  while (std::cin >> n && n != 0) {
    std::cin >> seq;
    BinaryTree origin_tree;
    origin_tree.BuildTree(seq);
    for (int i = 0; i < n; i++) {
      std::cin >> seq;
      BinaryTree cmp_tree;
      cmp_tree.BuildTree(seq);
      bool ans = origin_tree.Compare(cmp_tree);
      if (ans) {
        std::cout << "YES" << std::endl;
      } else {
        std::cout << "NO" << std::endl;
      }
    }
  }
  return 0;
}

注意std::cin与getline函数对换行符的处理的区别

图论一章

并查集

畅通工程

题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <vector>

class UnionFind {
 public:
  UnionFind(int n) {
    size_ = n;
    tree_.resize(n + 1);
    for (int i = 1; i <= n; i++) {
      tree_[i] = i;
    }
  }
  void Union(int p, int q) {
    int p_root = Find(p);
    int q_root = Find(q);
    if (p_root != q_root) {
      // 只是将第一个值的根节点指向第二个值的根节点，没有进行子树大小判断
      tree_[p_root] = q_root;
      size_--;
    }
  }
  int GetSize() { return size_; }

 private:
  int Find(int p) {
    if (tree_[p] == p) {
      return p;
    } else {
      int root = Find(tree_[p]);
      tree_[p] = root;  // 优化访问路径
      return root;
    }
  }
  int size_; // 不互通的集合数目（子图什么的？忘了）
  std::vector<int> tree_;  
};

int main() {
  int n, m;
  while (std::cin >> n && n != 0) {
    std::cin >> m;
    UnionFind tool(n);
    int p, q;
    for (int i = 0; i < m; i++) {
      std::cin >> p >> q;
      tool.Union(p, q);
    }
    std::cout << tool.GetSize() - 1 << std::endl;
  }
  return 0;
}

这个与之前写的差不多。。。

最小生成树

还是畅通工程

题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <algorithm>
#include <iostream>
#include <vector>

class UnionFind {
 public:
  struct Edge {
    int from_;
    int to_;
    int cost_;
  };
  UnionFind(int n, std::vector<Edge>&& edge) : size_(n), sum_(0), edge_(edge) {
    tree_.resize(n + 1);
    for (int i = 1; i <= n; i++) {
      tree_[i] = i;
    }
    // 使用lamda表达式自定义排序，权值从小到大
    std::sort(edge_.begin(), edge_.end(), [](const Edge& e1, const Edge& e2) {
      return e1.cost_ < e2.cost_;
    });
  }
  void Union(Edge e) {
    int p_root = Find(e.from_);
    int q_root = Find(e.to_);
    if (p_root != q_root) {
      // 只是将第一个值的根节点指向第二个值的根节点，没有进行子树大小判断
      tree_[p_root] = q_root;
      size_--;
      sum_ += e.cost_;
    }
  }
  int GetMinSpanningTree() {
    for (const auto& e : edge_) {
      Union(e);
      if (size_ == 0) {
        return sum_;
      }
    }
    return sum_;
  }

 private:
  int Find(int p) {
    if (tree_[p] == p) {
      return p;
    } else {
      int root = Find(tree_[p]);
      tree_[p] = root;  // 优化访问路径
      return root;
    }
  }

  int size_;  // 未连接子图数量
  int sum_;   // 生成树权值之和
  std::vector<int> tree_;
  std::vector<Edge> edge_;
};

int main() {
  int n;
  while (std::cin >> n && n != 0) {
    int edge_num = n * (n - 1) / 2;
    std::vector<UnionFind::Edge> edges;
    edges.resize(edge_num);
    for (int i = 0; i < edge_num; i++) {
      std::cin >> edges[i].from_ >> edges[i].to_ >> edges[i].cost_;
    }
    UnionFind tool(n, std::move(edges));
    std::cout << tool.GetMinSpanningTree() << std::endl;
  }
  return 0;
}

我不怎么喜欢在类方法中接受用户输入，故在main方法接受用户输入再传入，有些冗余。

Freckles

题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>

class UnionFind {
 public:
  struct Dot {
    double x_;
    double y_;
  };

  struct Edge {
    int from_;
    int to_;
    double cost_;
    Edge(int from, int to, double cost) : from_(from), to_(to), cost_(cost) {}
  };
  UnionFind(int n, const std::vector<Dot>& dots) : size_(n), sum_(0) {
    tree_.resize(n + 1);
    for (int i = 1; i <= n; i++) {
      tree_[i] = i;
    }
    edge_.reserve(n * (n - 1) / 2);

    double cost;  // 计算每条边的代价并加入数组中
    for (int i = 0; i < n - 1; i++) {
      for (int j = i + 1; j < n; j++) {
        cost = GetDistance(dots[i], dots[j]);
        edge_.emplace_back(Edge{i, j, cost});
      }
    }
    // 使用lamda表达式自定义排序，权值从小到大
    std::sort(edge_.begin(), edge_.end(), [](const Edge& e1, const Edge& e2) {
      return e1.cost_ < e2.cost_;
    });
  }
  void Union(Edge e) {
    int p_root = Find(e.from_);
    int q_root = Find(e.to_);
    if (p_root != q_root) {
      // 只是将第一个值的根节点指向第二个值的根节点，没有进行子树大小判断
      tree_[p_root] = q_root;
      size_--;
      sum_ += e.cost_;
    }
  }
  double GetMinSpanningTree() {
    for (const auto& e : edge_) {
      Union(e);
      if (size_ == 0) {
        return sum_;
      }
    }
    return sum_;
  }

 private:
  int Find(int p) {
    if (tree_[p] == p) {
      return p;
    } else {
      int root = Find(tree_[p]);
      tree_[p] = root;  // 优化访问路径
      return root;
    }
  }
  double GetDistance(const Dot& lhs, const Dot& rhs) {
    double res = (lhs.x_ - rhs.x_) * (lhs.x_ - rhs.x_) +
                 (lhs.y_ - rhs.y_) * (lhs.y_ - rhs.y_);
    return sqrt(res);
  }
  int size_;    // 未连接子图数量
  double sum_;  // 生成树权值之和
  std::vector<int> tree_;
  std::vector<Edge> edge_;
};

int main() {
  int n;
  while (std::cin >> n && n != 0) {
    std::vector<UnionFind::Dot> dots;
    dots.resize(n);
    for (int i = 0; i < n; i++) {
      std::cin >> dots[i].x_ >> dots[i].y_;
    }
    UnionFind tool(n, dots);
    double weight = tool.GetMinSpanningTree();
    printf("%.2f", weight);
  }
  return 0;
}

全是重复的代码。。。

最短路径

最短路

题目链接 需注册才能提交代码 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include <iostream>
#include <vector>

const int kInf = -1;
const int kMax = 1 << 30;
class Solution {
 public:
  int GetShortestPath(const std::vector<std::vector<int>>& graph) { return GetShortestPathUseDijkstraForMatrix(graph); }

 private:
  struct Edge {
    int to_;
    int cost_;
    Edge(int to, int cost) : to_(to), cost_(cost) {}
  };
  int GetShortestPathUseFloyd(const std::vector<std::vector<int>>& graph) {
    std::vector<std::vector<int>> ans = graph;  // 拷贝邻接矩阵
    int n = static_cast<int>(ans.size() - 1);
    for (int k = 1; k <= n; k++) {
      for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
          if (ans[i][k] == kInf || ans[k][j] == kInf) {
            continue;
          }
          if (ans[i][j] == kInf || ans[i][j] > ans[i][k] + ans[k][j]) {  // 通过节点k到达节点j距离更短
            ans[i][j] = ans[i][k] + ans[k][j];
          }
        }
      }
    }
    return ans[1][n];
  }
  int GetShortestPathUseDijkstraForMatrix(const std::vector<std::vector<int>>& graph) {  // 邻接矩阵实现
    int n = static_cast<int>(graph.size() - 1);
    std::vector<bool> mark(n + 1, false);
    std::vector<int> dist(n + 1, kInf);

    int new_dist;
    int min_dist;
    int v = 1;
    dist[1] = 0;
    mark[1] = true;
    for (int times = 0; times <= n; times++) {  // 变量times仅仅控制循环次数，不作数组下标
      for (int j = 1; j <= n; j++) {            // 第一步：借助节点v刷新dist数组
        if (mark[j] || graph[v][j] == kInf) {
          continue;
        }
        new_dist = dist[v] + graph[v][j];
        if (dist[j] == kInf || dist[j] > new_dist) {  // 节点i通过节点v到达节点j距离更短
          dist[j] = new_dist;
        }
      }

      min_dist = kMax;
      for (int j = 1; j <= n; j++) {  // 第二步：选择dist数组中未标记的最小值
        if (mark[j] || dist[j] == kInf) {
          continue;
        }
        if (min_dist > dist[j]) {
          min_dist = dist[j];
          v = j;
        }
      }
      mark[v] = true;  // 标记节点v（即加入集合）
      if (v == n) {    // 找到最短距离，提前结束
        break;
      }
    }
    return dist[n];
  }
  int GetShortestPathUseDijkstraForList(const std::vector<std::vector<int>>& graph) {  // 邻接表实现
    int n = static_cast<int>(graph.size() - 1);
    std::vector<std::vector<Edge>> edges;
    std::vector<bool> mark(n + 1, false);
    std::vector<int> dist(n + 1, kInf);

    edges.resize(n + 1);
    for (int i = 1; i <= n - 1; i++) {  // 由邻接矩阵构建邻接表
      for (int j = i + 1; j <= n; j++) {
        if (graph[i][j] != kInf) {
          edges[i].emplace_back(Edge(j, graph[i][j]));
          edges[j].emplace_back(Edge(i, graph[i][j]));
        }
      }
    }

    int new_dist;
    int min_dist;
    int edges_size;
    int to;
    int cost;
    int v = 1;
    dist[1] = 0;
    mark[1] = true;
    for (int times = 0; times <= n; times++) {  // 变量times仅仅控制循环次数，不作数组下标
      edges_size = static_cast<int>(edges[v].size());
      for (int j = 0; j < edges_size; j++) {  // 第一步：借助节点v刷新dist数组
        to = edges[v][j].to_;
        cost = edges[v][j].cost_;
        if (mark[to]) {
          continue;
        }
        new_dist = dist[v] + cost;
        if (dist[to] == kInf || dist[to] > new_dist) {  // 节点i通过节点v到达节点j距离更短
          dist[to] = new_dist;
        }
      }

      min_dist = kMax;
      for (int j = 1; j <= n; j++) {  // 第二步：选择dist数组中未标记的最小值
        if (mark[j] || dist[j] == kInf) {
          continue;
        }
        if (min_dist > dist[j]) {
          min_dist = dist[j];
          v = j;
        }
      }
      mark[v] = true;  // 标记节点v（即加入集合）
      if (v == n) {    // 找到最短距离，提前结束
        break;
      }
    }
    return dist[n];
  }
};
int main() {
  Solution solution;
  int n, m;
  int p, q, cost;
  while (std::cin >> n >> m) {
    if (n == 0 && m == 0) {
      break;
    }

    std::vector<std::vector<int>> graph(n + 1, std::vector<int>(n + 1, kInf));	// n+1 * n+1的二维矩阵
    for (int i = 0; i < m; i++) {
      std::cin >> p >> q >> cost;
      if (graph[p][q] == kInf || graph[p][q] > cost) {  // 可能有重复边，选取最短一条
        graph[p][q] = cost;
        graph[q][p] = cost;
      }
    }
    int time = solution.GetShortestPath(graph);
    std::cout << time << std::endl;
  }
  return 0;
}

使用Floyd与Dijkstra算法分别求解最短路径，我之前写的代码中没有考虑重复边，所以是错的。很容易看出代码的执行效率是比较低的，但我主要追求的是好看，也就无所谓了

最短路径问题

题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <iostream>
#include <vector>
#include <tuple>

const int kInf = -1;
const int kMax = 1 << 30;
class Solution {
 public:
  struct Edge {
    int to_;
    int dist_;
    int cost_;
    Edge(int to, int dist, int cost) : to_(to), dist_(dist), cost_(cost) {}
  };
  auto GetShortestPath(const std::vector<std::vector<Edge>>& edges, int start, int end) {
    int n = static_cast<int>(edges.size() - 1);
    std::vector<bool> mark(n + 1, false);
    std::vector<int> dist_matrix(n + 1, kInf);
    std::vector<int> cost_matrix(n + 1, kInf);

    int new_dist;
    int new_cost;
    int min_dist;
    int min_cost;
    int edges_size;
    int to;
    int cost;
    int dist;
    int v = start;

    dist_matrix[start] = 0;
    cost_matrix[start] = 0;
    mark[start] = true;
    for (int times = 0; times <= n; times++) {  // 变量times仅仅控制循环次数，不作数组下标
      edges_size = static_cast<int>(edges[v].size());
      for (int j = 0; j < edges_size; j++) {  // 第一步：借助节点v刷新dist/cost数组
        to = edges[v][j].to_;
        dist = edges[v][j].dist_;
        cost = edges[v][j].cost_;
        if (mark[to]) {
          continue;
        }
        new_dist = dist_matrix[v] + dist;
        new_cost = cost_matrix[v] + cost;
        if (dist_matrix[to] == kInf || dist_matrix[to] > new_dist || (dist_matrix[to] == new_dist && cost_matrix[to] > new_cost)) {  // 节点i通过节点v到达节点j距离更短
          dist_matrix[to] = new_dist;
          cost_matrix[to] = new_cost;
        }
      }

      min_dist = kMax;
      min_cost = kMax;
      for (int j = 1; j <= n; j++) {  // 第二步：选择dist/cost数组中未标记的最小值
        if (mark[j] || dist_matrix[j] == kInf) {
          continue;
        }
        if (min_dist > dist_matrix[j] || (min_dist == dist_matrix[j] && min_cost > cost_matrix[j])) {
          min_dist = dist_matrix[j];
          min_cost = cost_matrix[j];
          v = j;
        }
      }
      mark[v] = true;  // 标记节点v（即加入集合）
      if (v == end) {  // 找到最短距离，提前结束
        break;
      }
    }
    return std::make_tuple(dist_matrix[end], cost_matrix[end]);
  }
};
int main() {
  Solution solution;
  int n, m;
  int p, q, dist, cost;
  int start, end;
  std::cin >> n >> m;
  std::vector<std::vector<Solution::Edge>> edges;
  edges.resize(n + 1);

  for (int i = 0; i < m; i++) {
    std::cin >> p >> q >> dist >> cost;
    edges[p].emplace_back(Solution::Edge(q, dist, cost));
    edges[q].emplace_back(Solution::Edge(p, dist, cost));
  }
  std::cin >> start >> end;
  auto [min_dist, min_cost] = solution.GetShortestPath(edges, start, end);
  std::cout << min_dist << " " << min_cost << std::endl;

  return 0;
}

距离为一个抽象集合而非特定的变量

拓扑排序

Leagal or Not

没找到相应的oj题，不一定对

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <queue>
#include <vector>

class Solution {
 public:
  bool IsLeagal(const std::vector<std::vector<int>>& edges, std::vector<int>& indegree) {
    std::queue<int> zero_indegree_nodes;
    int n = static_cast<int>(indegree.size());

    for (int i = 0; i < n; i++) {  // 将入度为0的节点加入队列
      if (indegree[i] == 0) {
        zero_indegree_nodes.emplace(i);
      }
    }

    int node_number = 0;
    int node;
    int edge_size;
    int to;
    while (!zero_indegree_nodes.empty()) {
      node = zero_indegree_nodes.front();
      zero_indegree_nodes.pop();
      node_number++;  // 节点数加一

      edge_size = static_cast<int>(edges[node].size());
      for (int i = 0; i < edge_size; i++) {  // 去掉节点，更新入度数组
        to = edges[node][i];
        indegree[to]--;
        if (indegree[to] == 0) {  // 入度变成0，加入队列
          zero_indegree_nodes.emplace(to);
        }
      }
    }

    if (node_number == n) {
      return true;
    }
    return false;
  }
};

int main() {
  Solution solution;
  int m, n;
  int x, y;
  while (std::cin >> n >> m && n != 0) {
    std::vector<std::vector<int>> edges;
    edges.resize(n);
    std::vector<int> indegree(n, 0);
    for (int i = 0; i < m; i++) {
      // x->y,我觉得顺序无所谓，即使是y->x对该题来说也没有任何区别，毕竟是判断是否有环
      std::cin >> x >> y;
      edges[x].emplace_back(y);
      indegree[y]++;
    }
    bool ans = solution.IsLeagal(edges, indegree);
    if (ans) {
      std::cout << "YES" << std::endl;
    } else {
      std::cout << "NO" << std::endl;
    }
  }
}

动态规划一章

递推求解

N 阶楼梯上楼问题

题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>

class Solution {
 public:
  // f(n) = f(n-1) + f(n-2)
  int GetUpstairsWay(int n) {
    if (n <= 2) {
      return n;
    }

    int f1 = 2;  // n-1时上楼方式数目
    int f2 = 1;  // n-2时上楼方式数
    int tmp;
    for (int i = 3; i < n; i++) {  // 更新f(n-1),f(n-2)
      tmp = f1;
      f1 = f1 + f2;
      f2 = tmp;
    }
    return f1 + f2;
  }
};

int main() {
  Solution solution;
  int n;
  int ans;
  while (std::cin >> n) {
    ans = solution.GetUpstairsWay(n);
    std::cout << ans << std::endl;
  }
}

背包

采药

题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <vector>

class Solution {
 public:
  struct Medicine {
    int time_;
    int value_;
    Medicine(int time, int value) : time_(time), value_(value) {}
  };

  int GetMaxValue(const std::vector<Medicine>& list, int total_time) {
    int n = static_cast<int>(list.size());
    // dp[i][j]表示总时间不超过j的情况下，前i个物品能达到的最大价值
    // 为节省空间，只需记录dp[j]
    std::vector<int> dp(total_time + 1, 0);
    for (int i = 0; i < n; i++) {
      // 倒序更新dp数组，确保dp[j - list[i].time_]为上一次遍历的结果
      for (int j = total_time; j >= list[i].time_; j--) {
        // 状态转移：加入物品i或不加入
        dp[j] = std::max(dp[j - list[i].time_] + list[i].value_, dp[j]);
      }
    }
    return dp[total_time];
  }
};

int main() {
  Solution solution;
  int T, M;
  int time, value;
  while (std::cin >> T >> M) {
    std::vector<Solution::Medicine> list;
    for (int i = 0; i < M; i++) {
      std::cin >> time >> value;
      list.emplace_back(Solution::Medicine(time, value));
    }
    int ans = solution.GetMaxValue(list, T);
    std::cout << ans << std::endl;
  }
}

Piggy-Bank

没找到相应的题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <vector>

const int kInf = -1;
class Solution {
 public:
  struct Coin {
    int value_;
    int weight_;
    Coin(int value, int weight) : value_(value), weight_(weight) {}
  };
  int GetMinAmount(const std::vector<Coin>& coins, int total_weight) {
    int n = static_cast<int>(coins.size());
    std::vector<int> dp(total_weight + 1, kInf);  // 初始值不同
    dp[0] = 0;
    for (int i = 0; i < n; i++) {
      for (int j = coins[i].weight_; j <= total_weight; j++) {  // 顺序遍历
        if (dp[j - coins[i].weight_] != kInf) {
          if (dp[j] != kInf) {
            dp[j] = std::min(dp[j - coins[i].weight_] + coins[i].value_, dp[j]);
          } else {
            dp[j] = dp[j - coins[i].weight_] + coins[i].value_;
          }
        }
      }
    }
    return dp[total_weight];
  }
};
int main() {
  Solution solution;
  int T;
  int E, F;
  int N;
  int P, W;
  std::cin >> T;
  while (T--) {
    std::cin >> E >> F >> N;
    std::vector<Solution::Coin> coins;
    coins.reserve(N);
    for (int i = 0; i < N; i++) {
      std::cin >> P >> W;
      coins.emplace_back(Solution::Coin(P, W));
    }
    int min_value = solution.GetMinAmount(coins, F - E);
    if (min_value == kInf) {
      std::cout << "This is impossible." << std::endl;
    } else {
      std::cout << "The minimum amount of money in the piggy-bank is " << min_value << "." << std::endl;
    }
  }
}

/*
测试数据
3
10 110
2
1 1
30 50
10 110
2
1 1
50 30
1 6
2
10 3
20 4

测试结果
The minimum amount of money in the piggy-bank is 60.
The minimum amount of money in the piggy-bank is 100.
This is impossible.
*/

珍惜现在，感恩生活

没找到题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>
#include <vector>

class Solution {
 public:
  struct Rice {
    int price_;
    int weight_;
    Rice(int price, int weight) : price_(price), weight_(weight) {}
  };
  int GetMaxWeight(const std::vector<Rice>& rices, int money) {
    int n = static_cast<int>(rices.size());
    std::vector<int> dp(money + 1, 0);
    for (int i = 0; i < n; i++) {
      for (int j = money; j >= rices[i].price_; j--) {
        dp[j] = std::max(dp[j - rices[i].price_] + rices[i].weight_, dp[j]);
      }
    }
    return dp[money];
  }
};
int main() {
  Solution solution;
  int C;
  int n, m;
  int p, h, c;
  std::cin >> C;
  while (C--) {
    std::cin >> n >> m;
    std::vector<Solution::Rice> rices;
    rices.reserve(5 * m);  // 预订5*m的空间
    for (int i = 0; i < m; i++) {
      std::cin >> p >> h >> c;
      // 二进制拆分
      int k = 1;
      while (c - k > 0) {
        rices.emplace_back(Solution::Rice(p * k, h * k));
        c -= k;
        k *= 2;
      }
      if (c != 0) {
        rices.emplace_back(Solution::Rice(p * c, h * c));
      }
    }
    int max_weight = solution.GetMaxWeight(rices, n);
    std::cout << max_weight << std::endl;
  }
}


/*
测试数据
2
42 6
10 1 15
19 79 5
6 65 3
8 82 6
16 92 2
17 28 3
8 2
2 100 4
4 100 2

测试结果
441
400
*/

二进制拆分相关博客：多重背包 证明二进制拆分n[i]得到的数能够组成0~n[i]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
一个数n拆成小于它的所有二的次方的和(指数递增的)加上剩下一个数。实际上就是将这个数的二进制的每一位选或者不选就可以组成一个范围在0~n的数
 举个例子：13可以拆成 2^0 、 2^1 、 2^2、和 6（6是剩下的那个数），也就是拆分成 1 2 4 6，那么通过选择这4个数的就可以表示0~13的任意数。
 如：
0：一个都不选。
1：选1；
2：选2；
3：选1和2；
4: 选4；
5：选1和4；
6：选2和4；
7：选1和2和4；
8：选2和6；
9：选1和2和6；
10: 选4和6；
11：选1和4和6；
12：选2和4和6；
13：全选；