动态规划（记忆化搜索）
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
from functools import lru_cache
import sys
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
@lru_cache(None)
def dfs(i, j):
if i == m - 1 and j == n - 1:
return grid[i][j]
if i == m or j == n:
return sys.maxsize
rst = min(dfs(i + 1, j) + grid[i][j], dfs(i, j + 1) + grid[i][j])
return rst
return dfs(0, 0)
栈与队列
单调栈
leetcode 739
请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。
可以维护一个存储下标的单调栈，从栈底到栈顶的下标对应的温度列表中的温度依次递减。如果一个下标在单调栈里，则表示尚未找到下一次温度更高的下标。
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& T) {
stack<int> s;
vector<int> ret(T.size(), 0);
for (int i = T.size() - 1; i >= 0; --i) {
while (s.size() > 0 && T[s.top()] <= T[i]) {
s.pop();
}
if (s.size() > 0) {
ret[i] = s.top() - i;
}
s.push(i);
}
return ret;
}
};
判断括号
leetcode 20
class Solution {
public:
bool isValid(string s) {
stack<char> st;
for (char c: s) {
if (c == '(' || c == '[' || c == '{') {
st.push(c);
}
else if (c == ')') {
if (!st.empty() && st.top() == '(') {
st.pop();
}
else {
return false;
}
}
else if (c == ']') {
if (!st.empty() && st.top() == '[') {
st.pop();
}
else {
return false;
}
}
else if (c == '}') {
if (!st.empty() && st.top() == '{') {
st.pop();
}
else {
return false;
}
}
}
return st.empty();
}
};
树的遍历
使用队列的BFS
/**
* Return the length of the shortest path between root and target node.
*/
int BFS(Node root, Node target) {
Queue<Node> queue; // store all nodes which are waiting to be processed
int step = 0; // number of steps neeeded from root to current node
// initialize
add root to queue;
// BFS
while (queue is not empty) {
step = step + 1;
// iterate the nodes which are already in the queue
int size = queue.size();
for (int i = 0; i < size; ++i) {
Node cur = the first node in queue;
return step if cur is target;
for (Node next : the neighbors of cur) {
add next to queue;
}
remove the first node from queue;
}
}
return -1; // there is no path from root to target
}
使用栈的DFS
/*
* Return true if there is a path from cur to target.
*/
boolean DFS(int root, int target) {
Set<Node> visited;
Stack<Node> s;
add root to s;
while (s is not empty) {
Node cur = the top element in s;
return true if cur is target;
for (Node next : the neighbors of cur) {
if (next is not in visited) {
add next to s;
add next to visited;
}
}
remove cur from s;
}
return false;
}
二叉树的后序遍历
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
stack<tuple<TreeNode*, bool>> s;
vector<int> ret;
auto n = root;
bool flag = false;
while (!s.empty() || n) {
while (n) {
s.push(make_tuple(n, false));
n = n->left;
}
tie(n, flag) = s.top();
s.pop();
if (!flag) {
s.push(make_tuple(n, true));
n = n->right;
}
else {
ret.emplace_back(n->val);
n = nullptr;
}
}
return ret;
}
};
从前序与中序遍历序列构造二叉树
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int n = preorder.size();
if (n == 0) {
return nullptr;
}
return func(preorder, inorder, 0, n - 1, 0, n - 1);
}
private:
TreeNode* func(vector<int>& preorder, vector<int>& inorder, int pStart, int pEnd, int iStart, int iEnd) {
if (iEnd < iStart) {
return nullptr;
}
auto n = new TreeNode(preorder[pStart]);
int sp = iStart;
while (sp < iEnd && inorder[sp] != n->val) {
++sp;
}
n->left = func(preorder, inorder, pStart + 1, sp - iStart + pStart, iStart, sp - 1);
n->right = func(preorder, inorder, sp - iStart + pStart + 1, pEnd, sp + 1, iEnd);
return n;
}
};
二叉树层序序列化和反序列化
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
if (root == nullptr) {
return "[]";
}
queue<TreeNode*> q;
q.push(root);
vector<string> rst;
while (!q.empty()) {
TreeNode* n = q.front();
q.pop();
if (n) {
rst.emplace_back(to_string(n->val));
q.push(n->left);
q.push(n->right);
}
else {
rst.emplace_back("null");
}
}
auto end = rst.end() - 1;
while (*end == "null") {
--end;
}
string s = "[";
for (auto it = rst.begin(); it <= end; ++it) {
if (s.size() > 1) {
s.push_back(',');
}
s.append(*it);
}
s.push_back(']');
return s;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
vector<string> d;
int p = 1, q = 1, n = data.size();
if (n < 3) {
return nullptr;
}
while (q < n) {
while (q < n - 1 && data[q] != ',') {
++q;
}
d.emplace_back(data.substr(p, q - p));
p = q + 1;
q = p;
}
int m = d.size();
if (d[0] == "null") {
return nullptr;
}
TreeNode* root = new TreeNode(stoi(d[0], nullptr));
queue<TreeNode*> qu;
qu.push(root);
int i = 1;
while (i < m) {
auto n = qu.front();
qu.pop();
if (d[i] != "null") {
auto nn = new TreeNode(stoi(d[i], nullptr));
n->left = nn;
qu.push(nn);
}
++i;
if (i == m) {
break;
}
if (d[i] != "null") {
auto nn = new TreeNode(stoi(d[i], nullptr));
n->right = nn;
qu.push(nn);
}
++i;
}
return root;
}
};
// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));
图
dijkstra算法
from collections import defaultdict
from heapq import *
heap = [(0, V)]
dists = {}
while len(heap) > 0:
d, v = heappop(heap)
if v in dists:
continue
dists[v] = d
if v == target:
break
for vv, c in rels[v].items():
heappush(heap, (d + c, vv))
floyd算法
import numpy as np
N = 4
M = 100
edge = np.mat([[0,2,6,4],[M,0,3,M],[7,M,0,1],[5,M,12,0]])
A = edge[:]
path = np.zeros((N,N))
def Floyd():
for i in range(N):
for j in range(N):
if(edge[i,j] != M and edge[i,j] != 0):
path[i][j] = i
print 'init:'
print A,'\n',path
for a in range(N):
for b in range(N):
for c in range(N):
if(A[b,a]+A[a,c]<A[b,c]):
A[b,c] = A[b,a] + A[a,c]
path[b][c] = path[a][c]
print 'result:'
print A,'\n',path
————————————————
版权声明：本文为CSDN博主「撕书」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/Lwenjiyou_/java/article/details/79548577
拓扑排序
from collections import defaultdict
inds = defaultdict(int)
for v, e in graph.items():
for vv in e:
inds[vv] += 1
for v in nodes:
if inds[v] == 0:
q.append(v)
rst = []
while len(q) > 0:
v = q.popleft()
rst.append(v)
for vv in graph[v]:
inds[vv] -= 1
if inds[vv] == 0:
q.append(vv)
最小生成树 Prim
import heapq
vs = {V}
q = {}
for v, c in edges[V].items():
heapq.heappush(q, (c, v))
while len(vs) < N:
cost, v = heapq.heappop(q)
if v in vs:
continue
vs.add(v)
for vv, c in edges[v].items():
if vv not in vs:
heapq.heappush(q, (c, vv))
最大流
SAP 算法
int gap[maxN]; //层次网络中某一层包含节点的个数
int map[maxN][maxN];//邻接矩阵
int level[maxN]; //层次
int pre[maxN]; //增广路中节点的前一个节点
//m为节点总个数
int sap(int m)
{
//一开始所有节点的层次设为0
int result = 0;
gap[0] = m;
pre[1] = 1;
int u = 1 , v;
while (level[1] < m)
{
//找可行弧
for (v = 1; v <= m; v++)
{
if (map[u][v] && level[u] == level[v] + 1) break;
}
//找到了可行弧
if (v <= m)
{
pre[v] = u;
u = v;
//找到了一条增广路，做流量调整
if (v == m)
{
int min = 1e8;
for (int i = v; i != 1; i = pre[i])
if (min > map[pre[i]][i])
min = map[pre[i]][i];
result += min;
for (int i = v; i != 1; i = pre[i])
{
map[pre[i]][i] -= min;
map[i][pre[i]] += min;
}
u = 1;
}
}
else {
//未找到可行弧，调节层次网络，将当前节点的层次设为周围所有节点层次最小值+1，
//以确保下一次能找到可行弧
int minlevel = 1e5;
for (int i = 1; i <= m; i++)
if (map[u][i] && minlevel > level[i])
minlevel = level[i];
//gap优化 如果当前这个节点的层次中只包含这个节点，在这个节点的层次做调整后，
//当前网络就不再包含具有这个层次的节点了，这个时候是一定没办法找到可行流的，
//因此算法可以终止了。
gap[level[u]]--;
if (gap[level[u]] == 0) break;
level[u] = minlevel + 1;
gap[minlevel + 1]++;
u = pre[u];
}
}
return result;
}
原文链接：https://blog.csdn.net/yjr3426619/java/article/details/82808303
欧拉路径
leetcode 332
给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 出发
from collections import defaultdict, deque
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
edges = defaultdict(dict)
for a, b in tickets:
edges[a][b] = edges[a].get(b, 0) + 1
rst = []
def go(v):
for vv in sorted(list(edges[v])):
if edges[v][vv] > 0:
edges[v][vv] -= 1
go(vv)
rst.append(v)
go('JFK')
rst.reverse()
return rst
二分图
class Solution {
public:
bool isBipartite(vector<vector<int>>& graph) {
vector<int> colors(graph.size(), 0);
for (int i = 0; i < colors.size(); ++i) {
if (colors[i] == 0) {
if (!dfs(graph, i, 1, colors)) {
return false;
}
}
}
return true;
}
private:
bool dfs(vector<vector<int>>& graph, int v, int color, vector<int>& colors) {
if (colors[v] != 0) {
return color == colors[v];
}
colors[v] = color;
for (int i = 0; i < graph[v].size(); ++i) {
int colorTo = color == 1 ? 2 : 1;
if (!dfs(graph, graph[v][i], colorTo, colors)) {
return false;
}
}
return true;
}
};
匈牙利算法
https://zhuanlan.zhihu.com/p/96229700
int M, N; //M, N分别表示左、右侧集合的元素数量
int Map[MAXM][MAXN]; //邻接矩阵存图
int p[MAXN]; //记录当前右侧元素所对应的左侧元素
bool vis[MAXN]; //记录右侧元素是否已被访问过
bool match(int i)
{
for (int j = 1; j <= N; ++j)
if (Map[i][j] && !vis[j]) //有边且未访问
{
vis[j] = true; //记录状态为访问过
if (p[j] == 0 || match(p[j])) //如果暂无匹配，或者原来匹配的左侧元素可以找到新的匹配
{
p[j] = i; //当前左侧元素成为当前右侧元素的新匹配
return true; //返回匹配成功
}
}
return false; //循环结束，仍未找到匹配，返回匹配失败
}
int Hungarian()
{
int cnt = 0;
for (int i = 1; i <= M; ++i)
{
memset(vis, 0, sizeof(vis)); //重置vis数组
if (match(i))
cnt++;
}
return cnt;
}
km算法
https://www.jianshu.com/p/c59ab6a5dbf8
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
const int MAXN = 305;
const int INF = 0x3f3f3f3f;
int love[MAXN][MAXN]; // 记录每个妹子和每个男生的好感度
int ex_girl[MAXN]; // 每个妹子的期望值
int ex_boy[MAXN]; // 每个男生的期望值
bool vis_girl[MAXN]; // 记录每一轮匹配匹配过的女生
bool vis_boy[MAXN]; // 记录每一轮匹配匹配过的男生
int match[MAXN]; // 记录每个男生匹配到的妹子 如果没有则为-1
int slack[MAXN]; // 记录每个汉子如果能被妹子倾心最少还需要多少期望值
int N;
bool dfs(int girl)
{
vis_girl[girl] = true;
for (int boy = 0; boy < N; ++boy) {
if (vis_boy[boy]) continue; // 每一轮匹配 每个男生只尝试一次
int gap = ex_girl[girl] + ex_boy[boy] - love[girl][boy];
if (gap == 0) { // 如果符合要求
vis_boy[boy] = true;
if (match[boy] == -1 || dfs( match[boy] )) { // 找到一个没有匹配的男生 或者该男生的妹子可以找到其他人
match[boy] = girl;
return true;
}
} else {
slack[boy] = min(slack[boy], gap); // slack 可以理解为该男生要得到女生的倾心 还需多少期望值 取最小值 备胎的样子【捂脸
}
}
return false;
}
int KM()
{
memset(match, -1, sizeof match); // 初始每个男生都没有匹配的女生
memset(ex_boy, 0, sizeof ex_boy); // 初始每个男生的期望值为0
// 每个女生的初始期望值是与她相连的男生最大的好感度
for (int i = 0; i < N; ++i) {
ex_girl[i] = love[i][0];
for (int j = 1; j < N; ++j) {
ex_girl[i] = max(ex_girl[i], love[i][j]);
}
}
// 尝试为每一个女生解决归宿问题
for (int i = 0; i < N; ++i) {
fill(slack, slack + N, INF); // 因为要取最小值 初始化为无穷大
while (1) {
// 为每个女生解决归宿问题的方法是 ：如果找不到就降低期望值，直到找到为止
// 记录每轮匹配中男生女生是否被尝试匹配过
memset(vis_girl, false, sizeof vis_girl);
memset(vis_boy, false, sizeof vis_boy);
if (dfs(i)) break; // 找到归宿 退出
// 如果不能找到 就降低期望值
// 最小可降低的期望值
int d = INF;
for (int j = 0; j < N; ++j)
if (!vis_boy[j]) d = min(d, slack[j]);//未匹配女孩与其他相关男孩的最小差值
for (int j = 0; j < N; ++j) {
// 所有访问过的女生降低期望值
if (vis_girl[j]) ex_girl[j] -= d;
// 所有访问过的男生增加期望值
if (vis_boy[j]) ex_boy[j] += d;
// 没有访问过的boy 因为girl们的期望值降低，距离得到女生倾心又进了一步！
else slack[j] -= d;
}
}
}
// 匹配完成 求出所有配对的好感度的和
int res = 0;
for (int i = 0; i < N; ++i)
res += love[ match[i] ][i];
return res;
}
int main()
{
while (~scanf("%d", &N)) {
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
scanf("%d", &love[i][j]);
printf("%d\n", KM());
}
return 0;
}
强连通分量，tarjan算法
#include<cstdio>
#include<algorithm>
#include<string.h>
using namespace std;
struct node {
int v,next;
}edge[1001];
int DFN[1001],LOW[1001];
int stack[1001],heads[1001],visit[1001],cnt,tot,index;
void add(int x,int y)
{
edge[++cnt].next=heads[x];
edge[cnt].v = y;
heads[x]=cnt;
return ;
}
void tarjan(int x)//代表第几个点在处理。递归的是点。
{
DFN[x]=LOW[x]=++tot;// 新进点的初始化。
stack[++index]=x;//进站
visit[x]=1;//表示在栈里
for(int i=heads[x];i!=-1;i=edge[i].next)
{
if(!DFN[edge[i].v]) {//如果没访问过
tarjan(edge[i].v);//往下进行延伸，开始递归
LOW[x]=min(LOW[x],LOW[edge[i].v]);//递归出来，比较谁是谁的儿子／父亲，就是树的对应关系，涉及到强连通分量子树最小根的事情。
}
else if(visit[edge[i].v ]){ //如果访问过，并且还在栈里。
LOW[x]=min(LOW[x],DFN[edge[i].v]);//比较谁是谁的儿子／父亲。就是链接对应关系
}
}
if(LOW[x]==DFN[x]) //发现是整个强连通分量子树里的最小根。
{
do{
printf("%d ",stack[index]);
visit[stack[index]]=0;
index--;
}while(x!=stack[index+1]);//出栈，并且输出。
printf("\n");
}
return ;
}
int main()
{
memset(heads,-1,sizeof(heads));
int n,m;
scanf("%d%d",&n,&m);
int x,y;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
add(x,y);
}
for(int i=1;i<=n;i++)
if(!DFN[i]) tarjan(1);//当这个点没有访问过，就从此点开始。防止图没走完
return 0;
}
最小费用最大流
dijkstra算法
#include "stdafx.h"
#include <iostream>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <functional>
#define MAXN 5050
#define INF 0x3f3f3f3f
#define P pair<int,int>
using namespace std;
struct edge
{
int to, cap, cost, rev;
};
int n, m, s, t;
int u, v, c, w;
int maxFlow, minCost;
vector<edge> G[MAXN];
int h[MAXN];
int dist[MAXN], prevv[MAXN], preve[MAXN];
void addedge(int from, int to, int cap, int cost)
{
edge temp1 = { to, cap, cost, (int)G[to].size() };
edge temp2 = { from, 0, -cost, (int)G[from].size() - 1 };
G[from].push_back(temp1);
G[to].push_back(temp2);
}
//Dijkstra算法实现
void MCMF(int s, int t, int f)
{
fill(h + 1, h + 1 + n, 0);
while (f > 0)
{
priority_queue<P, vector<P>, greater<P> > D;
memset(dist, INF, sizeof dist);
dist[s] = 0; D.push(P(0, s));
while (!D.empty())
{
P now = D.top(); D.pop();
if (dist[now.second] < now.first) continue;
int v = now.second;
for (int i = 0; i<(int)G[v].size(); ++i)
{
edge &e = G[v][i];
if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to])
{
dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
prevv[e.to] = v;
preve[e.to] = i;
D.push(P(dist[e.to], e.to));
}
}
}
if (dist[t] == INF) break;
for (int i = 1; i <= n; ++i) h[i] += dist[i];
int d = f;
for (int v = t; v != s; v = prevv[v])
d = min(d, G[prevv[v]][preve[v]].cap);
f -= d; maxFlow += d;
minCost += d * h[t];
for (int v = t; v != s; v = prevv[v])
{
edge &e = G[prevv[v]][preve[v]];
e.cap -= d;
G[v][e.rev].cap += d;
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
cout << "节点数为："; cin >> n;
cout << "边数为："; cin >> m;
cout << "源点编号为："; cin >> s;
cout << "汇点编号为："; cin >> t;
cout << "输入 " << m << " 条边的信息：" << endl;
while (m--)
{
cout << "起点："; cin >> u;
cout << "终点："; cin >> v;
cout << "容量："; cin >> c;
cout << "费用："; cin >> w;
cout << "-----------------" << endl;
addedge(u, v, c, w);
}
MCMF(s, t, INF);
cout << "最大流为：" << maxFlow << endl;
cout << "最小费用为" << minCost << endl;
cout << endl;
system("pause");
return 0;
}
————————————————
版权声明：本文为CSDN博主「WhiteJunior」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/lym940928/java/article/details/90209172
哈密顿回路
/*
Icosian Game A century after Euler’s discovery (see Problem 4), another
famous puzzle—this one invented by the renowned Irish mathematician Sir
William Hamilton (1805–1865)—was presented to the world under the name
of the Icosian Game.
Find a Hamiltonian circuit—a path that visits all the graph’s vertices exactly
once before returning to the starting vertex
*/
#include <iostream>
#include <vector>
using namespace std;
bool hamiltonian(vector<vector<bool>>& graph, vector<bool>& visit, int vertex, vector<int>& path) {
path.push_back(vertex);
if (path.size() == graph.size() + 1 && vertex == path[0]) {
cout << "-----begin solution-----" << endl;
for (size_t i = 0; i < path.size(); ++i) {
cout << path[i];
if (i != path.size() - 1)
cout << "-->";
}
cout << endl << "-----end solution-----" << endl;
return true;
}
if (vertex == path[0] && path.size() != 1) {
path.pop_back();
return false;
}
for (size_t i = 0; i < graph.size(); ++i) {
if (graph[vertex][i] && (!visit[i] || i == path[0])) {
visit[vertex] = true;
if (hamiltonian(graph, visit, i, path))
return true;
visit[vertex] = false;
}
}
path.pop_back();
return false;
}
int main() {
/*
(0)--(1)--(2)
| / \ |
| / \ |
| / \ |
(3)-------(4)
*/
vector<vector<bool>> graph = {
{0, 1, 0, 1, 0},
{1, 0, 1, 1, 1},
{0, 1, 0, 0, 1},
{1, 1, 0, 0, 1},
{0, 1, 1, 1, 0}
};
for (auto& g : graph) {
for (const auto& e : g) {
cout << e;
}
cout << endl;
}
vector<int> path;
vector<bool> visit(graph.size(), false);
hamiltonian(graph, visit, 0, path);
/* result:
-----begin solution-----
0-->1-->2-->4-->3-->0
-----end solution-----
*/
return 0;
}
字符串
Boyer-Moore-Horsepool
class Solution {
public:
int strStr(string haystack, string needle) {
int m = haystack.size(), n = needle.size();
if (n == 0) {
return 0;
}
if (m < n) {
return -1;
}
vector<int> badCharShift(256, n);
int last = n - 1;
for (int i = 0; i < last; ++i) {
badCharShift[needle[i]] = last - i;
}
int p = 0;
while (m - p >= n) {
for (int i = last; haystack[p + i] == needle[i]; --i) {
if (i == 0) {
return p;
}
}
// cout << p << ' ' << haystack.substr(p, n) << endl;
p += badCharShift[haystack[p + last]];
}
return -1;
}
};
排序
排序链表
Qsort
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
using namespace std;
class Solution {
public:
ListNode* sortList(ListNode* head) {
if (head == NULL) {
return NULL;
}
return get<0>(qsort(head));
}
private:
tuple<ListNode*, ListNode*> qsort(ListNode* head) {
if (head -> next == NULL) {
return make_tuple(head, head);
}
ListNode* left = NULL, *left_end = NULL, *right = NULL, *right_end = NULL;
ListNode* p = head -> next;
int k = head->val;
head -> next = NULL;
while (p != NULL) {
ListNode* next = p -> next;
p -> next = NULL;
if (p -> val < k) {
if (left == NULL) {
left = left_end = p;
}
else {
left_end -> next = p;
left_end = p;
}
}
else {
if (right == NULL) {
right = right_end = p;
}
else {
right_end -> next = p;
right_end = p;
}
}
p = next;
}
if (left != NULL) {
tie(left, left_end) = qsort(left);
}
if (right != NULL) {
tie(right, right_end) = qsort(right);
}
if (left == NULL) {
left = head;
}
else {
left_end -> next = head;
}
if (right == NULL) {
head -> next = NULL;
right_end = head;
}
else {
head -> next = right;
}
return make_tuple(left, right_end);
}
};
归并
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
using namespace std;
class Solution {
public:
ListNode* sortList(ListNode* head) {
int length = 0;
ListNode* p = head;
while (p != NULL) {
++length;
p = p -> next;
}
if (length == 0) {
return NULL;
}
auto dummpy = ListNode();
auto rst = &dummpy;
rst -> next = head;
auto rst_end = rst;
for (int step = 1; step < length; step *= 2) {
auto current = rst -> next;
auto rst_end = rst;
ListNode* left, *right;
while (current) {
left = current;
right = cut(current, step);
current = cut(right, step);
ListNode* new_end = NULL;
tie(rst_end -> next, new_end) = merge(left, right);
rst_end = new_end;
}
}
return rst -> next;
}
private:
ListNode* cut(ListNode* head, int n) {
auto p = head;
while (--n && p) {
p = p -> next;
}
ListNode* next = NULL;
if (p) {
next = p -> next;
p -> next = NULL;
}
return next;
}
tuple<ListNode*, ListNode*> merge(ListNode* left, ListNode* right) {
auto dummpy = ListNode();
auto ret = &dummpy;
ret -> next = NULL;
auto ret_end = ret;
auto p = left;
auto q = right;
while (p && q) {
if (p -> val < q -> val) {
ret_end -> next = p;
ret_end = p;
p = p -> next;
}
else {
ret_end -> next = q;
ret_end = q;
q = q -> next;
}
}
while (p) {
ret_end -> next = p;
ret_end = p;
p = p -> next;
}
while (q) {
ret_end -> next = q;
ret_end = q;
q = q -> next;
}
ret_end -> next = NULL;
return make_tuple(ret -> next, ret_end);
}
};
二分搜索
// 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int n = nums.size();
int p = 0, q = n;
while (p < q) {
int r = (p + q) >> 1;
if (nums[r] == target) {
return r;
}
else if (nums[r] < target) {
p = r + 1;
}
else {
q = r;
}
}
return p;
}
};
选择
快速选择
class Solution {
public:
int quickSelect(vector<int>& a, int l, int r, int index) {
int q = randomPartition(a, l, r);
if (q == index) {
return a[q];
} else {
return q < index ? quickSelect(a, q + 1, r, index) : quickSelect(a, l, q - 1, index);
}
}
inline int randomPartition(vector<int>& a, int l, int r) {
int i = rand() % (r - l + 1) + l;
swap(a[i], a[r]);
return partition(a, l, r);
}
inline int partition(vector<int>& a, int l, int r) {
int x = a[r], i = l - 1;
for (int j = l; j < r; ++j) {
if (a[j] <= x) {
swap(a[++i], a[j]);
}
}
swap(a[i + 1], a[r]);
return i + 1;
}
int findKthLargest(vector<int>& nums, int k) {
srand(time(0));
return quickSelect(nums, 0, nums.size() - 1, nums.size() - k);
}
};
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/solution/shu-zu-zhong-de-di-kge-zui-da-yuan-su-by-leetcode-/
