thetheOrange的笔记

发表于 分类于 本文字数： 89 阅读时长 ≈ 1 分钟

对一个数进行向上取整，对于cpp来说，可以使用库函数ceil进行取整。对于非负数来说，可以使用下面的方法进行方便的取整。公式如下：

(a + b - 1) / b

证明思路如下图所示：

向上取整的证明思路

发表于 分类于 本文字数： 1.1k 阅读时长 ≈ 2 分钟

基本步骤

  1. 定义全局变量 where
  2. 递归函数f(i) 从i位置出发，遇到字符串终止或者嵌套条件终止就返回
  3. 返回值是f(i) 负责的这一段结果
  4. f(i)在返回前更新where，目的是让上级函数通过where知道解析到了什么位置，进而继续

例题分析

394. 字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

字符串中一共会出现四种情况：1.数字 2.字母 3.左括号 4.右括号

遇到数字和字母，我们可以记录下来。遇到左括号，说明我们进入到了一个嵌套，需要重复括号内的字符串，直到i扫描到右括号。

这个时候，上游的函数就可以接收下游函数传递的嵌套结果，进而通过数字进行重复。

代码如下：

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 where = 0;

// 重复字符串
string repeat(int times, string s) {
	string res;
	for (int i = 0; i < times; ++i) {
		res += s;
	}
	return res;
}

string f(int i, string s) {
	int d = 0; // 用于记录数字
	string path; // 用于记录子串
	while (i < s.size() && s[i] != ']') {
		// 遇到数字
		if (s[i] >= '0' && s[i] <= '9') {
			d = d * 10 + (s[i++] - '0');
		}
		// 遇到字母
		else if (s[i] >= 'a' && s[i] <= 'z') {
			path.push_back(s[i++]);
		}
		// 遇到左括号
		else {
			path += repeat(d, f(i + 1, s));
			i = where + 1;
			d = 0;
		}
	}
	// 把当前的位置传给上游函数
	where = i;
	return path;
}

感谢

本文整理自左神的算法讲解039【必备】嵌套类问题的递归解题套路

发表于 更新于 分类于 本文字数： 188 阅读时长 ≈ 1 分钟

模版

cpp版本

1
2
3
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

python版本

1
2
def gcd(a: int, b: int) -> int:
    return a if b == 0 else gcd(b, a % b);

补充

求最小公倍数

1
2
3
int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}

发表于 本文字数： 831 阅读时长 ≈ 2 分钟

题目描述

155 最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

思路

使用两个栈，一个栈用于存储数据，一个栈用于存储当前的最小值，分别记作a, b。当push的val大于b中的栈顶元素时，就再次向b压入栈顶元素，否则压入val。

实现代码

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
class MinStack {
public:
    stack<int> st;
    stack<int> mi;
    MinStack() {
        
    }
    
    void push(int val) {
        st.push(val);
        if (mi.empty() || val < mi.top()) {
            mi.push(val);
        }
        else {
            mi.push(mi.top());
        }
    }
    
    void pop() {
        st.pop();
        mi.pop();
    }
    
    int top() {
        return st.top();
    }
    
    int getMin() {
        return mi.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

发表于 分类于 本文字数： 1.1k 阅读时长 ≈ 2 分钟

基本步骤

  1. 创建一个indegree数组，用于记录各个节点的入度情况。以入度为0的节点作为拓扑排序的起点。
  2. 将起点压入队列中。
  3. 取队头元素，如果没有visited过，则visited[cur] = true。如果存在重复visited，则说明成环。
  4. 处理各边，依次对相邻节点的入度值-1，将入度为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
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
	// 建图
	vector<vector<int>> graph{ {1, 2}, {3}, {3}, {4}, {} };
	vector<int> path;
	// 拓扑排序
	queue<int> q;
	q.push(0);
	vector<int> indegree(5, 0);// 记录入度
	for (auto i : graph) {
		for (auto j : i) {
			indegree[j]++;
		}
	}
	vector<bool> visited(5, false);
	// 成环标志
	bool isCircle = false;
	while (!q.empty()) {
		int size = q.size();
		while (size--) {
			int cur = q.front();
			if (visited[cur]) isCircle = true;
			visited[cur] = true;
			q.pop();
			path.push_back(cur);
			// 处理各边
			for (auto neighbor : graph[cur]) {
				// 如果入度为0则加入队列中
				if (--indegree[neighbor] == 0) {
					q.push(neighbor);
				}
			}
		}
	}
	// 打印path
	for (auto i : path) {
		cout << i << ' ';
	}
	// 是否成环
	cout << endl;
	cout << isCircle;
	return 0;
}

时间复杂度

O(E+V)

0%