算法总结

二分法

下面是二分法的经典题目和代码：

题目描述

Problem: T35：搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

Solve

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while(left <= right)
        {
            int mid = (right - left) / 2 + left;
            if(nums[mid] == target) return mid;
            if(nums[mid] > target) right = mid - 1;
            else left = mid + 1;
        }
        return left;
    }
};

回溯法

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }
 
    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {//注意i=0,i=start的区别
        处理节点;
        backtracking(路径，选择列表); // 递归  注意(i)和(i++)的区别  后面会懂
        回溯，撤销处理结果
    }
}

下面是回溯法的经典题目和代码：

题目描述

Problem: T46：全排列
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

Solve

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
class Solution {
public:
    vector<vector<int>> res;
    vector<int> is_used;
    void back(vector<int> tmp, vector<int>& nums, vector<int> is_used)
    {
        if(tmp.size() == nums.size()) // 终止条件
        {
            res.push_back(tmp);
            return;
        }

        for(int i = 0; i < nums.size(); i++)
        {
            if(!is_used[i])
            {
                is_used[i] = 1; // 已经使用过
                tmp.push_back(nums[i]);

                back(tmp, nums, is_used);
                tmp.pop_back();
                is_used[i] = 0; // 还原回去
            }
        }

        return;
    }
    vector<vector<int>> permute(vector<int>& nums) {
        is_used = vector<int>(nums.size(), 0);
        vector<int> tmp;
        back(tmp, nums, is_used);
        return res;
    }
};

输入输出

万能库

1
#include <bits/stdc++.h>

字符串

  • 无空格字符串输入, 翻转 
    1
    2
    string s; cin >> s; 
    reverse(s.begin(), s.end());
  • 单个字符输入字符串，可以更精细的调整 
    1
    2
    3
    4
    5
    string s; char ch;
    while(cin.get(ch) && ch != '\n')
    {
        s.push_back(ch) // 或者 s += ch;
    }
  • 丢弃缓存区的字符 
    1
    2
    cin >> n;
    cin.ignore(10); // 丢弃10个字符（比如说'\n'这样的）

保留n位小数输出

  • 保留 n 位小数 
    1
    cout << fixed << setprecision(n) << c;
  • 保留 n 位有效数字 
    1
    cout << defaultfloat << setprecision(n) << c;
  • 整数右对齐，填充 0 
    1
    cout << right << setfill('0') << setw(9) << n;

最大 int 使用

一般在图中表示两个点之间没有边。

1
2
#include <bits/stdc++.h>
const int N = INT_MAX;

定义 long long 类型

1
2
using LL = long long; // 新方法
typedef long long LL; // 兼容性更好

迅速找出最大最小元素

1
2
3
vector<int> a = {1, 2, 3, 4, 5};
int maxi = *max_element(a.begin(), a.end());
int mini = *min_element(a.begin(), a.end());

Switch 写法

1
2
3
4
5
6
7
8
9
10
11
switch (n) // 注意这个n不能是string，只能是char这样
{
    case n1:
        pass;
        break;
    case n2:
        pass;
        break;
    default:
        pass;
}

String 类型

  • 转为 int，int 转为 string
    1
    2
    int num = stoi("789");
    string s = to_string(789);

栈

1
2
3
4
5
stack<int> stk;
int a = 5;
stk.push(a);
int b = stk.top(); // 返回a
stk.pop(); // 将 a 弹出

队列

1
2
3
4
5
queue<int> que;
int a = 5;
que.push(a);
int b = que.front(); // 返回a
que.pop();

链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 类定义
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* head = new ListNode(-1); // 一般来说，链表操作需要一个头节点！
ListNode* p = head->next;
// 在p后插入一个节点，值为val1
ListNode *tmp = p->next; // 保存一开始p后面的节点
ListNode *new_node = new ListNode(val1);
p->next = new_node;
new_node->next = tmp;

// 删除p后面的这个节点
ListNode* node = p->next;
p->next = p->next->next;
delete node; // 释放内存

哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
unordered_map<string, int> student_scores; // 类定义
student_scores["Li Ming"] = 95; // 插入新元素
student_scores["Li Ming"] = 98; // 修改旧元素

// 查找元素
const string to_find = "Li Ming";
auto iter = student_scores.find(to_find);
if(iter != student_scores.end()) cout << iter->first << ' ' << iter->second;

//  遍历哈希表
for(auto& pair : student_scores) {
    cout << pair.first << ' ' << pair.second; // 注意pair不是指针！
}

// 删除哈希表元素
student_scores.erase("Li Ming");

// 显式赋值
unordered_map<char, int> score = {{'l', 4}, {'o', 3}};

图算法

  1. Dijkstra 和 最小生成树：都是贪心算法，每次寻找dis[i]最小的点，将它放到visited数组中，然后再根据这个变化去更新dis数组。下面是最小生成树示例：

    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
    int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
        // write code here
        vector<vector<int>> tab(n + 1, vector<int>(n + 1, INT_MAX));
        for(vector<int> c : cost)
        {
            tab[c[0]][c[1]] = min(tab[c[0]][c[1]], c[2]);
            tab[c[1]][c[0]] = tab[c[0]][c[1]];
        }
        vector<int> visited(n + 1, 0); // 表示一个点有没有被选中
        vector<int> dis(n + 1, INT_MAX); // dis[i]表示没选到的点离选到的点的距离
        for(int i = 1; i <= n; i++) dis[i] = tab[1][i]; // 假设第一个点是1，赋初值
        visited[1] = 1;
        int res = 0;
        for(int j = 1; j < n; j++) // 每次找出一个点来，
        {
            int mini = INT_MAX, idx = -1;
            for(int i = 1; i <= n; i++) // 找到dis[i]最小的点
            {
                if(visited[i] == 1) continue; // 已经访问过
                if(dis[i] <= mini)
                {
                    mini = dis[i];
                    idx = i;
                }
            }
            res += mini;
            visited[idx] = 1; // 标记已经访问
            for(int i = 1; i <= n; i++) // 更新与i相连节点的dis值
            {
                if(tab[idx][i] == I N) continue;
                dis[i] = min(dis[i], tab[idx][i]);
            }
        }
        return res;
    }

  2. floyd 算法：
    主要思想也是将点 kk 一个一个的加入考虑范围内，去松弛 ii jj 两点之间的距离。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    int dist[MAXN][MAXN];
    int n;

    void floyd() {
        for (int k = 0; k < n; k++) { // 加入第k个节点
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dist[i][k] != INF && dist[k][j] != INF &&
                            dist[i][j] > dist[i][k] + dist[k][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
    }

排序算法

  1. 用 STL 标准库带 lambda 函数的排序算法的写法： 
    1
    2
    3
    4
    5
    6
    7
    8
    // lambda函数写法，降序排列
    sort(a.begin(), a.end(), [](const int& a, const int& b){
        return a > b;
    })

    // cmp 独立函数的写法
    bool cmp(const int& a, const int& b) {return a > b;}
    sort(a.begin(), a.end(), cmp);

背包算法

  • 最简单 01 背包：dp[i][v]表示对于前ii个物品，在体积为vv的时候能装载的最大值。 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    int solve1_1(vector<int>& goods, vector<int>& weights, int volume)
    {
       vector<vector<int>> dp(2, vector<int>(volume + 1));
       for(int i = 0; i <= volume; i++)
       {
           if(i < goods[0]) dp[0][i] = 0;
           else dp[0][i] = weights[0];
       }
       for(int i = 1; i < goods.size(); i++)
       {
           for(int v = 0; v <= volume; v++)
           {
               if(v < goods[i]) dp[1][v] = dp[0][v];
               else dp[1][v] = max(dp[0][v], dp[0][v - goods[i]] + weights[i]);
           }
           dp[0] = dp[1]; // 给下一次循环使用
       }
       return dp[0][volume];
    }
  • 变种1，背包必须装满：在初始化的时候作出改变，dp[0][0]=0，dp[0][goods[0]]=weights[0]，其他都初始化为-inf；
  • 变种2，完全背包，即每个物品无限多个：
algorithm
#leetcode
算法总结
https://kingdom-of-warriors.github.io/2025/05/12/算法总结/
作者
Rayy
发布于
2025年5月12日
许可协议