[持续更新][数据结构][算法]涵盖线性表、栈、链表、队列、图、动态规划、分治递归、回溯贪心分支限界、击穿专业课！！！
生活随笔
收集整理的這篇文章主要介紹了
[持续更新][数据结构][算法]涵盖线性表、栈、链表、队列、图、动态规划、分治递归、回溯贪心分支限界、击穿专业课！！！
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
備考考點整理
內部排序表格
樹的主要考點
\(n_0 = n_2+1\)
\(n=n_0+n_1+n_2...n_m\)
\(n=n_1+2*n_2+3*n_3...m*n_m\) +1
哈夫曼樹沒有度為1的結點，也就是\(n_1=0\)
完全二叉樹?？?/h3>
總結
最大島嶼問題（dfs模板）
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn =1000;
int grid[maxn][maxn]; //網格
int num=0;
int m,n; //m行n列
void dfs(int x,int y){
grid[x][y] = 0; //改寫成0
int dx[4]={-1,0,1, 0};
int dy[4]={ 0,1,0,-1}; //四個方向
for(int i=0;i<4;i++){
int a = x + dx[i];
int b =y + dy[i];
if(a>=0 && b >=0 && a<m && b<n && grid[a][b]==1){
num++;
dfs(a,b);
}
}
}
int maxArea(){
int ans = 0;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++){
if(grid[i][j]==1){
num=1;
dfs(i,j);
}
ans = max(ans,num); //最大島嶼面積
}
return ans;
}
int main(){
cin >>m>>n;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
cin>>grid[i][j];
cout<<"最大島嶼面積"<<maxArea();
return 0;
}
DFS的模板：
? 此處dfs模板可以背
//答案版
#include<iostream>
#include<algorithm>
using namespace std;
int amax = 0;
int n;
int a[1000][1000];
void dfs(int i,int j,int &sum)
{
if(i==-1||j==n||i==n||j==-1||a[i][j]==0) return;//走出邊界或者路走不通
else
{
a[i][j] = 0; //將走過的路標記為走不通
sum++;
}
dfs(i-1,j,sum);//搜索四個方向的路
dfs(i,j-1,sum);
dfs(i+1,j,sum);
dfs(i,j+1,sum);
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
cin>>a[i][j];
}
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
if(a[i][j]>0)
{
int sum=0;//記錄最大路
dfs(i,j,sum);
amax=max(sum,amax);
}
}
cout<<amax;
return 0;
}
計算二叉樹雙分支結點（遞歸）
雙端隊列實現
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=100;
struct deque{
int arr[maxn];
int head;
int tail;
int size=0;
};
deque que;
que.head=que.tail=0;
que.size=0;
void head_in(deque &que,int x){
if(que.size==n)
return;
que.arr[que.head] = x;
if(que.head == 0)
que.head=n-1;
else
que.head--;
}
void head_out(deque &que,int &x){
if(que.size==0)
return;
que.arr[que.head] = x;
if(que.head == n-1)
que.head=0;
else
que.head++;
}
void tail_in(deque &que,int x){
if(que.size==n)
return;
if(que.head == n-1)
que.head=0;
else
que.head++;
que.arr[que.head] = x;
}
void tail_out(deque &que,int x){
if(que.size==0)
return;
if(que.head == 0)
que.head=n-1;
else
que.head--;
que.arr[que.head] = x;
}
遞歸分治
遞歸概念
直接或間接地調???的算法稱為遞歸算法。?函數??給出定義的函數稱為遞歸函數
邊界條件與遞歸?程是遞歸函數的兩個要素
遞歸優點缺點
遞歸?結
優點：結構清晰，可讀性強，?且容易?數學歸納法來證明算法的正確性，因此它為設計算法、調試程序帶來很??便。
缺點：遞歸算法的運?效率較低，?論是耗費的計算時間還是占?的存儲空間都??遞歸算法要多。 解決?法：在遞歸算法中消除遞歸調?，使其轉化為?遞歸算法。
遞歸生成全排列
回溯法
void Perm(int list[],int i,int n)
{
if(i==n)
{
for(int i=1;i<=n;i++)
cout<<list[i];
cout<<endl;
}
for(int t=i;t<=n;t++)
{
swap(list[t],list[i]);
Perm(list,i+1,n);
swap(list[t],list[i]);
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>list[i];
Perm(list,1,n);
return 0;
}
1.樹到葉子結點sum路徑匹配
給定一個二叉樹T和一個值 sum ， 判斷是否有從根節點到葉子節點的節點值之和等于 sum的路徑。 找出一條路徑使得路徑上各個結點值的和等于sum：
int check(TreeNode *T,int sum)
{
if(T == NULL && sum == 0)
return 1;
if(T == NULL && sum !=0)
return 0;
return check(T->lchild,sum - T->data) || check(T->rchild,sum-T->data);
}
2,判斷樹是否軸對稱
如果一個樹的左子樹與右子樹鏡像對稱，那么這個樹是對稱的。因此，該問題可以轉化為：兩個樹在什么
情況下互為鏡像？
如果同時滿足下面的條件，兩個樹互為鏡像：它們的兩個根結點具有相同的值，每個樹的右子樹都與另一
個樹的左子樹鏡像對稱。
我們可以實現這樣一個遞歸函數，通過「同步移動」兩個指針的方法來遍歷這棵樹，p 指針和 q 指針一
開始都指向這棵樹的根，隨后 p 右移時，q 左移，p 左移時，q 右移。每次檢查當前 p 和 q 節點的值是否相等，如果相等再判斷左右子樹是否對稱。
int check(TreeNode *p, TreeNode *q)//初始化q,p都指向根節點
{
if (!p && !q) return true;//都為空
if (!p || !q) return false;//結構不對稱
return p->data == q->data && check(p->left, q->right) && check(p->right, q->left);
}
int isSymmetric(TreeNode* root)
{
return check(root, root);//初始時候p，q都指向根節點
}
3.整數劃分
對于正整數n的劃分，最?加數不?于m的個數記作q(n,m)
int fun(int n,int m)//表示求解
{
if(m==1) //最?加數不超過1，只有?種劃分
return 1;
if(n<m) //最?加數不能?于 要劃分的數字n
return fun(n,n);
if(n==m)
return 1+fun(n,n-1); //取n本身作為?種劃分?案 + 最?加數?于n的所有?案
return fun(n,m-1)+fun(n-m,m); //?案分為 含有最?加數 和不含最?加數兩種
}
4.二分法求冪函數
這里的二分是指減少乘法的次數，把重復的運算省去。我要求 x 的 n 次方，那么先求 x 的 n/2 次方，然
后兩個相乘起來。如此遞歸下去。
核心思想：x^n
1.遞歸結束條件
n==0;return 1;
2.遞歸轉移方程
if n%2==1;x* x^(n/2) * x^(n/2)
n%2==0 x^(n/2) * x^(n/2)
double fun(double x, int n)
{
if (n == 0)//遞歸結束條件
return 1;
double half;
if (n %2== 1)//遞歸轉移方程
{
half = fun(x, n / 2);//x的n/2次方
return x*half*half;
}
else
{
half = fun(x, n / 2);
return half * half;
}
}
5.最大字段和（分治法）
int n;
int arr[Maxn];
struct Status
{
//lSum 表示該 Status 從左端連續最大子段和，rSum 表示從右段連續最大子段和,mSum表示整段的最大子段和，iSum 表示整段求和
int lSum, rSum, mSum, iSum;
};
struct Status pushUp(struct Status l, struct Status r)
{
int iSum = l.iSum + r.iSum;
int lSum = max(l.lSum, l.iSum + r.lSum);
int rSum = max(r.rSum, r.iSum + l.rSum);
int mSum = max(max(l.mSum, r.mSum), l.rSum + r.lSum);
return (struct Status){lSum, rSum, mSum, iSum};//回溯的結果
}
struct Status get(int* a, int l, int r)
{
//遞歸的邊界條件
if (l == r)
{
return (struct Status){a[l], a[l], a[l], a[l]};
}
int m = (l + r) >> 1;
struct Status lSub = get(a, l, m);
struct Status rSub = get(a, m + 1, r);
return pushUp(lSub, rSub);//向上回溯
}
int maxSubArray(int* nums, int numsSize)
{
return get(nums, 0, numsSize - 1).mSum;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
cin>>arr[i];
cout<<maxSubArray(arr,n)<<endl;
return 0;
}
動態規劃
- dp數組含義
- 遞推公式
- dp數組初始化
- dp數組遍歷順序，先物品？先背包？
- 打印dp數組
1.硬幣湊金額問題
給你一個整數數組 coins ，表示不同面額的硬幣；以及一個整數 amount ，表示總金額。 計算并返回可以湊成總金額所需的 最少的硬幣個數 。如果沒有任何一種硬幣組合能組成總金額，返回 -1 。
int dp[maxn];//dp[i]表示用coins來湊i元需要的最少金額
int n;
int coins[maxn]={INT_MAX};
int fun(int amount)
{
dp[0]=0;
for(int i=1;i<=amount;i++)//背包
for(int j=0;j<n;j++)//物品
if(i>=coins[j] && dp[i-coins[j]]!=INT_MAX)
{
dp[i]=min(dp[i-coins[j]]+1,dp[i]);
}
if(dp[amount]==INT_MAX)
return -1;
else
return dp[amount];
}
2. 一維dp，爬樓梯最小耗費
dp[i] 到達i位置的最小耗費
dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
3.二維dp,不同路徑
//明確是走多少步還是多少種?。?dp[i][j]是走到ij格子有多少種不同的路徑
dp[i][j]=dp[i-1][j]+dp[i][j-1]
//初始化
dp[0][j]=1
dp[i][0]=1
4.二維dp，不同路徑2
//圖中有障礙
if(obs[i][j]==0)//沒有障礙
dp[i][j]=dp[i-1][j]+dp[i][j-1]
//初始化
for(int i=0;i<m && obs[i][0]==0 ;i++)
dp[i][0]=1; //遇到障礙后面全是0
for(int j=0;j<n && obs[0][j]==0 ;j++)
dp[0][j]=1; //后面全是0
5. 一維，整數拆分
dp[i] //對i進行拆分，得到最大乘積為dp[i]
//分拆成兩個數和拆成兩個數以上
for(int i=3;i<=n;i++) //n是數字
for(int j=1;j<i;j++) //j是拆
dp[i]=max(j*(i-j),j*dp[i-j],dp[i]);
6.不同形狀的二叉搜索樹
n=3 頭1+頭2+頭3
頭1 = 左子樹0結點 * 右子樹2結點
頭2 = 左子樹1結點 * 右子樹1結點
頭3 = 左子樹2結點 * 右子樹0結點
dp[3]=dp[0]*dp[2]+dp[1]*dp[1]+dp[2]*dp[0]
dp[i]:有dp[i]種不同的二叉搜索樹
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
dp[i] += dp[j-1]*dp[i-j];
7. 0-1背包
dp[i][j]
[0，i]物品任取放容量為j的背包
dp[i][j]
不放物品i:dp[i-1][j]
放物品i:dp[i-1][j-w[i]] + v[i]
初始化
最大字段和（動規）dp[i]表示，以i為結尾的數組的最大子段和是多少
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int res = nums[0];
for(int i = 1; i < nums.size(); i++) {
if (nums[i - 1] > 0) nums[i] += nums[i - 1];
if (nums[i] > res) res = nums[i];
}
return res;
}
};
int n;
int arr[Maxn];
int solve(int arr[])
{
int dp[Maxn]={0};//dp[i]表示，以i為結尾的數組的最??段和是多少
dp[1]=arr[1];
int ans=dp[1];
for(int i=2;i<=n;i++)
{
dp[i]=max(arr[i],arr[i]+dp[i-1]);
ans=max(ans,dp[i]);
}
cout<<"ans="<<ans<<endl;
}
8.分割等和子集（母體??！凡是聯想到分成兩個子集）
給你一個 只包含正整數 的 非空 數組 nums 。請你判斷是否可以將這個數組分割成兩個子集，使得兩個子集的元素和相等。
0-1背包能否裝滿問題
target = sum /2
dp[j] 容量為j,最大價值為dp[j]
判斷條件dp[target]==target
dp[j]=max(dp[j],dp[j-w[i]]+v[i])
--> dp[j]=max(dp[j-nums[i]]+nums[i]) //重量等于價值
for(i=0;i<=nums.size();i++) //先物品
for(j=target;j>=nums[i];j--) //后背包（因為做了狀態壓縮，順序不能調換）
正序倒敘的區別
9.最后一塊石頭的重量2
和上一題一樣
最后湊不成dp[target]==target也沒關系
dp[j] 容量為j,最大重量為dp[j]
dp[j]=max(dp[j],dp[j-w[i]]+v[i])
//先物品再背包
剩下sum-dp[j]-dp[j]就是剩下的最小的石頭
int lastStoneWeightII(vector<int>& stones) {
int dp[3001]={0};
int sum=0;
for(int i=0;i<stones.size();i++)
sum+=stones[i];
for(int i=0;i<stones.size();i++)
{
for(int j=sum/2;j>=stones[i];j--)
dp[j] = max(dp[j],dp[j-stones[i]]+stones[i]);
}
return sum-2*dp[sum/2];
}
10.股票買賣問題
int maxProfit(vector<int>& prices) {
int dp[100000][2]={0};
//0是持有，1是未持有
dp[0][0]=-prices[0];
dp[0][1]=0;
for(int i=1;i<prices.size();i++)
{
dp[i][0]=max(dp[i-1][0],0-prices[i]);
dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i]);
}
return dp[prices.size()-1][1];
}
11.目標和（0-1背包裝滿有多少種方法母體）
//left是正，right是負
left+right=sum
left-right=target
target=sum/2
所以left=(target+sum)/2 //如果left無法被2整除，直接返回0就行，湊不出來
dp[j] 裝滿容量j的背包有dp[j]種方法
//要湊5 =湊1的種類+湊4的種類 + 湊2的種類+湊3的種類
dp[5]=dp[1]+dp[2]+dp[3]+dp[4]
dp[j]+=dp[j-nums[i]] !!!!!(裝滿有多少種的母體)
int findTargetSumWays(vector<int>& nums, int target) {
int sum = 0;
for (int i = 0; i < nums.size(); i++) sum += nums[i];
if (abs(target) > sum) return 0; // 此時沒有方案
if ((target + sum) % 2 == 1) return 0; // 此時沒有方案
int bagSize = (target + sum) / 2;
vector<int> dp(bagSize + 1, 0);
dp[0] = 1;
for (int i = 0; i < nums.size(); i++) {
for (int j = bagSize; j >= nums[i]; j--) {
dp[j] += dp[j - nums[i]];
}
}
return dp[bagSize];
}
12. 一和零
dp[i][j] i個0，j個1 最大背了dp[i][j]個物品
每一個數有x個0、y個1
max(dp[i-x][j-y]+1,dp[i][j])
dp[0][0]=0 非0下標：0
13.完全背包
//0-1背包 一維dp從后往前遍歷
for(int i;i<weight.size();i++) //物品
for(int j=bagweight;j>=weight[i];j--) //背包
dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);
//完全背包
for(int i;i<weight.size();i++) //物品
for(int j=weight[i];j<=bagweight;i++) //背包
dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);
14.零錢兌換問題2
dp[j] 裝滿容量j的背包有dp[j]種方法
dp+=dp[j-coins[i]];
dp[0]=1;
先物品，再背包 得到組合數
for(i=0;i<coins.size;i++)//物品
for(j=coins[i];j<=amount;j++) //背包
先背包，在物品，得到排列數
for(j=coins[i];j<=amount;j++) //背包
for(i=0;i<coins.zie;i++)//物品
//先物品，再背包 得到組合數
//先背包，在物品，得到排列數
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<int> dp(1000,0);
vector<int> coins;
int n,amount;
void carryfirst(int amount)
{
dp[0]=1;
for(int i=0;i<coins.size();i++)//先物品
for(int j=coins[i];j<=amount;j++)//再背包
dp[j]+=dp[j-coins[i]];
}
void bagfirst(int amount)
{
dp[0]=1;
for(int j=0;j<=amount;j++)//先背包
for(int i=0;i<coins.size();i++)//再物品
if(j>=coins[i])
dp[j]+=dp[j-coins[i]];
}
int main()
{
cin>>n;
for(int i=0;i<n;i++){
int temp;
cin>>temp;
coins.push_back(temp);
}
cin>>amount;
bagfirst(amount);
for(int i=0;i<=amount;i++)
cout<<dp[i]<<" ";
return 0;
}
三維dp
帶有分段、逐個
for(int r=2;r<=n;r++){//區間長度
for(int i=0;i<=n-r;i++){//區間起始位置
int j=i+r-1;//區間結束位置
for(int k=i;k<=j-1;k++){//區間劃分位置
1.字母乘法表問題
//設字符串的第 i 到 第 j 位乘積為 a 的加括號法有 dp[i][j][a] 種，
//字符串的第 i 到 第 j 位乘積為 b 的加括號法有 dp[i][j][b] 種,
//字符串的第 i 到 第 j 位乘積為 c 的加括號法有 dp[i][j][c] 種。
char table[3][3]={
{'b','b','a'},
{'c','b','a'},
{'a','c','c'},
};
int dp[64][64][3]={0};
int main() {
string s;
cin>>s;
int n=s.length();
for(int i=0;i<n;i++){//1 個字母，對應 dp 值為 1
dp[i][i][s[i]-'a']=1;
}
for(int r=2;r<=n;r++){//區間長度
for(int i=0;i<=n-r;i++){//區間起始位置
int j=i+r-1;//區間結束位置
for(int k=i;k<=j-1;k++){//區間劃分位置
dp[i][j][0]+=dp[i][k][0]*dp[k+1][j][2]+dp[i][k][1]*dp[k+1][j][2]+dp[i][k][2]*dp[k+1][j][0];
dp[i][j][1]+=dp[i][k][0]*dp[k+1][j][0]+dp[i][k][0]*dp[k+1][j][1]+dp[i][k][1]*dp[k+1][j][1];
dp[i][j][2]+=dp[i][k][1]*dp[k+1][j][0]+dp[i][k][2]*dp[k+1][j][1]+dp[i][k][2]*dp[k+1][j][2];
}
}
}
cout<<dp[0][n-1][0]<<endl;
return 0;
}
貪心
簡單
1.最優裝載問題
核心思想：如何裝集裝箱才能在稱重量一定的輪船上裝的集裝箱最多。按照從輕到重對集裝箱進行排序，越輕的
就越先裝使得剩余的載重量最大那么就可以裝更多的集裝箱。
int n;//n 個集裝箱
int c;//輪船載重
struct container
{
int id;//編號
int w;//重量
int vis;//是否被裝入輪船 1被裝入輪船 0
};
container arr[Maxn];
bool cmp(container a,container b)//按照重量排序，在sort里調用一下就可以
{
return a.w<b.w;
}
void solve()
{
int sum=0;//輪船中已經裝入的重量
for(int i=1;i<=n;i++)
{
if(sum+arr[i].w<=c)//當前集裝箱可以裝入
{
sum+=arr[i].w;
arr[i].vis=1;
}
else
break;
}
}
int main()
{
cin>>n>>c;//輸入集裝箱的個數和最大載重量
for(int i=1;i<=n;i++)
{
cin>>arr[i].w;
arr[i].id=i;
arr[i].vis=0;
}
sort(arr+1,arr+n+1,cmp);//對集裝箱按照從輕到重排序
solve();
for(int i=1;i<=n;i++)
if(arr[i].vis==1)
cout<<arr[i].id<<'\t';
cout<<endl;
return 0;
}
分支限界法
（1）隊列式(FIFO)分支限界法
按照隊列先進先出（FIFO）原則選取下一個節點為擴展節點。
（2）優先隊列式分支限界法
按照優先隊列中規定的優先級選取優先級最高的節點成為當前擴展節點。
特征是使用到隊列
布線問題（典例）
布線問題。 在 m 行 n 列的網格中， 能否從一個起始位置， 布線到結束位置。 方向只能(上下左右),其中有些位置已 經布線則不能重復布線
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int grid[100][100];
int m,n;
int dir[4][2]={0,1,1,0,0,-1,-1,0};
int sx,sy,fx,fy;
typedef struct Node
{
int x;
int y;
int step;
}Node;
void func()
{
queue<Node> que;
Node now;
now.x = sx;
now.y = sy;
now.step = 0;
que.push(now);
while(!que.empty())
{
now = que.front();
que.pop();
if(now.x==fx && now.y==fy){
cout << "yes";
return ;
}
Node next;
for(int i=0;i<4;i++)
{
next.x=now.x+dir[i][0];
next.y=now.y+dir[i][1];
next.step=now.step+1;
if(next.x>0 && next.x<=m && next.y>0&&next.y<=n&&grid[next.x][next.y]==0)
{
que.push(next);
grid[next.x][next.y]=1;
}
}
}
}
int main()
{
cin>>m>>n;
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
cin>>grid[i][j];
cin>>sx>>sy>>fx>>fy;
fun();
return 0;
}
回溯法
標準c++回溯法全排列
void perm(int i,vector<int>& nums,vector<vector<int>> &result)
{
if(i==nums.size())
{
result.push_back(nums);
}
else
{
for(int t=i;t<nums.size();t++)
{
swap(nums[i],nums[t]);
perm(i+1,nums,result);
swap(nums[i],nums[t]);
}
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> vec;
perm(0,nums,vec);
return vec;
}
1.批作業調度問題
核心思想：n個作業需要先在機器1上處理再在機器2上處理，不同的處理順序所需要的最終時間不同，找出一個最小時間和的調度方案。先對作業定義一個結構體(編號、time1,time2),用回溯法的排列樹來做（每進入一層（加入一個作業）需要加上在機器1的處理時間，和機器二的處理時間(如果當前作業想在機器二上處理得先保證它在機器1上處理完成，并且前一個作業在機器2上完成了)，當回溯回來得時候需要減去在機器1的時間和機器2的時間）。當整個排列樹結束，如果所需要的時間<bestf（存儲目前的最優值，用的時間最少的順序）;bestf=當前時間
#include <iostream>
using namespace std;
int n; //作業數
int M[100][100]; //M[i][j]表示第i個作業在機器j上需要處理的時間
int x[100]; //x[i]表示第i個處理的作業為x[i]
int bestx[100]; //x[i]的最優值
int f1; //作業在機器1上完成處理的時間
int f2[100]; //f2[i]表示第i個作業在機器2上完成處理的時間
int f; //用于記錄前i個作業在機器2上完成處理的時間和
int bestf=10000; //f的最優值
void Backtrack(int i)
{
if(i>n) //每到達一個葉子結點，一定是產生了一個最優解，因此要更新之前最優解的值
{
if(f<bestf) //更新最優解
{
for(int j=1;j<=n;j++)
bestx[j]=x[j];
bestf=f;
}
}
else
{
for(int j=i;j<=n;j++) //控制展開i-1層結點的各個分支。
{
f1+=M[x[j]][1]; //計算第i層（個）作業在機器1上的完成處理的時間
if(f2[i-1]>f1) //如果第（i-1）個作業在機器2上的完成處理的時間大于第i個作業在機器1上的完成處理的時間，那么第i個作業想進入機器2，就要等第（i-1）個作業在機器2上完成后再說
f2[i]=f2[i-1]+M[x[j]][2];
else //否則，第i個作業可以在機器1上完成處理后直接進入機器2。
f2[i]=f1+M[x[j]][2];
f+=f2[i]; //計算完第i個作業在機器2上的完成處理的時間，就可以計算出前i個作業在機器2上完成處理的時間和了
if(f<bestf) //截止到這，已經得到一個前i個作業在機器2上完成處理的時間和f，如果f比之前記錄的前i個作業在機器2上的完成處理的時間和的最優值bestf都要小，就可以生成第i層結點的孩子結點，繼續探索下一層
{
Swap(x[i],x[j]);
Backtrack(i+1);
Swap(x[i],x[j]);
}
f-=f2[i];
f1-=M[x[j]][1];
}
}
}
int main()
{
cin>>n;
for(int i=1;i<=2;i++)
{
for(int j=1;j<=n;j++)
cin>>M[j][i];
}
for(int i=1;i<=n;i++)
x[i]=i; //初始化排列順序
Backtrack(1);
for(int i=1;i<=n;i++)
cout<<bestx[i]<<" ";
cout<<bestf<<endl;
return 0;
}
2.括號對數問題
數字 n 代表生成括號的對數，請你設計一個函數，用于能夠生成所有可能的并且 有效的 括號組合。 （括號僅限小括號:”()”）
關鍵點在于：從左往右來任何一個位置左括號的數量不能小于右括號的數量
#include<iostream>
#include<algorithm>
using namespace std;
int n;
char txt[1000];
bool isok(int b,int i)
{
if(i>b){
for(int t=b;t<i;t++)
if(txt[t]==txt[i])
return false;
}
return true;
}
bool check()//生成的括號是否合法
{
int left=0;
for(int i=1;i<=2*n;i++)
{
if(txt[i]=='(')
left++;
else
left--;
if(left<0)//表示出現的右括號數量大于左括號的數量
return false;
}
return true;
}
void perm(int i)
{
if(i==2*n)
{
if(check())
{
for(int i=1;i<=2*n;i++)
cout<<txt[i];
cout<<endl;
return;
}
}else{
for(int t=i;t<=2*n;t++)
{
if(isok(i,t))
{
swap(txt[i],txt[t]);
perm(i+1);
swap(txt[i],txt[t]);
}
}
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
txt[i]='(';
for(int j=n+1;j<=2*n;j++)
txt[j]=')';
perm(1);
return 0;
}
3.汽車裝載問題（兩輛汽車）
//第 i 個物品放入 1 車中
skc1[top1++]=i;
BackTrack(i+1,c1+w[i],c2);
//回溯
top1--;
//第 i 個物品放入 2 車中
skc2[top2++]=i;
BackTrack(i+1,c1,c2+w[i]);
//回溯
top2--;
#include <bits/stdc++.h>
using namespace std;
int C1,C2;
int skc1[64],skc2[64],top1=0,top2=0;
int n,w[64];
void BackTrack(int i,int c1,int c2){
//剪枝
if(c1>C1||c2>C2)return;
//如果全部貨物都已裝好
if(i==n){
cout<<"第一個貨車：";
for(int t=0;t<top1;t++){
cout<<w[skc1[t]]<<" ";
}
cout<<endl<<"第二個貨車：";
for(int t=0;t<top2;t++){
cout<<w[skc2[t]]<<" ";
}
return;
}
//第 i 個物品放入 1 車中
skc1[top1++]=i;
BackTrack(i+1,c1+w[i],c2);
//回溯
top1--;
//第 i 個物品放入 2 車中
skc2[top2++]=i;
BackTrack(i+1,c1,c2+w[i]);
//回溯
top2--;
}
int main(int argc, char** argv) {
cin>>C1>>C2;
cin>>n;
for(int i=0;i<n;i++){
cin>>w[i];
}
BackTrack(0,0,0);
return 0;
超基礎超可能考
順序表
## 順序表默認結構體
typedef struct
{
int data[maxsize];
int length;
}Sqlist;
1.順序表遞增有序，插入元素x，任然有序
void insert(Sqlist &L,int x)
{
int i=0;
while(L->data[i]<x && i<L->length) //定位到要插入的位置
{
i++;
}
for(int j=L->length-1;j>=i;j--)
{
L->data[i+1] = L->data[i];
}
L->data[i] = x;
L->length++; //不要忘記
}
2.用順序表最后一個元素覆蓋整個順序表中最小元素，并返回該最小元素
int fun(Sqlist &L)
{
int min=L->data[0];
int j;
for(int i=0;i<L->length;i++)
{
//遍歷尋找最小
if(min<L->data[i])
min=L->data[i];
j=i;
}
L->data[j]=L->data[L->length-1];
L->length--;
return L->data[j];
}
3.順序表元素逆置
void fun(Sqlist &L)
{
int i=0;
int j=L.length-1;
while(i<j)
{
swap(L.data[i],L.data[j]);
i++;
j--;
}
}
4. 刪除順序表中所有值為x的元素
void func(Sqlist &L,int x) //掃描+前移操作
{
int k=0;
for(int i=0;i<L.length;i++)//遍歷
{
if(L.data[i]!=x)
L.data[k]=L.data[i];
k++;
}
//不要忘記
L.length = k;
}
void func(Sqlist &L,int x)
{
int k=0;
for(int i=0;i<L.length;i++)
{
if(L.data[i] == x)
k++;
else
L.data[i-k]=L.data[i];
}
L.length=L.length-k;
}
5.兩個遞增有序表合成一個遞增有序表
//歸并
//直接用數組了
void fun(int arr1[],int n1,int arr2[],int n2,int temp[])
{
int i=0,j=0;
int t=0;
while(i<n1 && j<n2)
{
if(arr1[i]<arr2[j])
temp[t++]=arr1[i++];
else
temp[t++]=arr2[j++];
}
while(i<n1)
temp[t++]=arr1[i++];
while(j<n2)
temp[t++]=arr2[j++];
}
6.設計一個時間上盡可能高效的算法，找出數組中未出現的最小正整數
必做題
int find(int arr[],int n)//長度為n
{
int temp[maxn];
for(int k=0;k<n;k++)//初始化為0
temp[k]=0;
for(int i=0;i<n.i++)//遍歷arr
{
if(A[i]>0 && A[i]<=n)//序號小
temp[A[i]-1] = 1;
}
for(int i=0;i<n;i++)
if(temp[i]==0)
return i+1;
return n+1;
}
思路是掃描，超出數組大小的不管，額外開拓數組從0到n，出現標記1，沒有出現默認0
掃描完成再掃描額外數組，找沒出現的值；
鏈表
//單鏈表默認結構體
typedef struct LNode
{
int data;
struct LNode *next;
}LNode,*Linklist;
1.刪除帶頭節點單鏈表中所有值為 x 的結點
void delete(Linklist &L,int x)
{
LinkNode *p=L;
while(p->next != NULL) //不用雙指針法
{
if(p->next->data != x)
p=p->next;
else //p->next->data == x
{
LNode *q=p->next;
p->next = q->next;
free(q);
}
}
}
2.刪除帶頭結點單鏈表的第一個值為x的結點
基礎
bool delete(Linklist &L,int x)
{
LNode *p=L; //p掃描
LNode *q; //q執行刪除
while(p->next != NULL)
{
if(p->next->data == x)
break;
p=p->next;
}
if(p->next == NULL)//如果p是最后一個，也就是掃描沒掃到x
return false;
else
{
q=p->next;// p --- q
p->next = q->next;
free(q);
return ture;
}
}
3.帶頭結點單鏈表的逆置
超級重要
void func(Linklist &L)
{
LNOde *p=L->next,*q; //p指第一個數據,q是p的后面一個
L->next=NULL; //L斷開 脫離
while(p!=NULL) //重新排序
{
q=p->next;
p->next=L->next;
L->next=p;
p=q;
}
}
第二種
思路：先把后面的結點逆置了，再連接上頭結點
void reverse(Linklist &L) //先逆置每一個next
{
LNode *p=L->next,*r=p->next;
LNode *pre;
p->next = NULL;
while(r != NULL)
{
pre = p;
p=r;
r=r->next;
p->next=pre;
}
L->next=p;
}
4、在帶頭結點的單鏈表 L 中刪除最小值點的高效算法（已知最小值唯一）
//快慢指針
void delete_min(Linklist &L)
{
if(L->next ==NULL)
return ;
LNOde *p=L->next;
LNOde *min=L;
while(p->next != NULL) //快指針掃描
{
if(p->next->data < min->next>data) //慢指針維護最小
m=p;
p=p->next;
}
LNOde *u = min->next;//刪除操作
min->next = u->next;
free(u);
}
5.將一個帶頭節點單鏈表 A 分解成兩個帶頭節點的單鏈表 A 和 B，使 A 中含奇數位置元素， B 中含偶數位置元素，且相對位置不變
Linklist create(Linklist &A)
{
LNode *B = new LNode;
B->next=NULL;
LNode *ra = A;
LNode *rb = B;
LNode *p= A->next;
A->next=NULL; //斷開 分離出數據鏈
while(p!=NULL)//遍歷
{
ra->next=p;
ra=p;
p=p->next;
rb->next=p;
rb=p;
if(p!=NULL)
p=p->next;
}
ra->next=NULL; //記得補充??！
// 兩個一組兩個一組 rb的末尾肯定是NULL
return B;
}
6、兩個遞增有序的單鏈表，設計算法成一個非遞減有序的鏈表。
非遞減不是遞增
void func(Linklist &L1,Linklist &L2,Linklist &temp)
{
LinkNode *r=temp;
LinkNode *p=L1->next;
LinkNode *q=L2->next;
L1->next=NULL;
L2->next=NULL;//斷開L1,L2
while(p!=NULL && q!=NULL)
{
if(p->data <= q->data)
{
temp->next=p;
p=p->next;
temp=temp->next;
}else
{
temp->next=q;
q=q->next;
temp=temp->next;
}
if(p!=NULL)
temp->next=p;
if(q!=NULL)
temp->next=q;
}
}
7. A, B兩個單鏈表遞增有序，從 A, B 中找出公共元素產生單鏈表 C，要求不破環 A, B結點
Linklist common(Linklist A,Linklist B)
{
//充分利用A,B遞增有序這個條件
LNode *p=A->next;
LNode *q=B->next;
LNode *C = new Lnode;
LNOde *r=C,*s;
while(p!=NUll && q!=null)
{
if(p->data > q->data)
q = q->next;
else if(p->data < q->data)
p = p->next;
else //兩個相等
{
s=new LNode;
s->data = p->data;
r->next=s;
r=s;//跟隨指針，尾插法?。?！
p=p->next;
q=q->next;
}
}
r->next=NULL;
return C;
}
嘗試使用兩個for/while 來寫通用的
void common(Linklist A,Linklist B,Linklist &C)
{
LinkNode *q=A->next;
LinkNOde *p=B->next;
LinkNnode *i=C,*s;
while(q!=NULL)
{
while(p!=NULL)
{
if(q->data == p->data)
{
//不破壞AB
s = new LNOde;
s->data = q->data;
i->next=s;
i=s;
}
p=p->next;
}
q=q->next;
}
}
8、查找單鏈表中倒數第 k個結點，若成功，則輸出該節點的data，并返回 1，否則返回0
int fun(Linklist L,int k)
{
int length=0;
LNode *p = L->next;
while(p!=NULL)
{
length++;
p=p->next;
}
if(length<k)
return 0;
int m=length-k+1;
int i=0;
while(i<m){
L=L->next;
i++
}
//for(int i=0;i<length-k+1;i++)
// L=L->next;
cout<< L->data;
return 1;
}
9、用單鏈表保存 m 個整數，且|data|≤n，要求設計時間復雜度盡可能高效的算法，對于 data 絕對值相等的點，僅保留第一次出現的點（408 必會）
//時間換空間 一遍遍歷就可以
void fun(Linklist &L)
{
LinkNode *p=L;
LinkNode *r;
int arr[n+1]={0};
int k;
while(p->next != NULL)
{
if(p->next->data > 0) //不能直接改，要先檢查再改
k=p->next->data;
else
k=- p->next->data;
if(arr[k]==0)//沒出現 可以修改
{
arr[k]=1;
p=p->next;
}else//出現過了
{
r=p->next;
p->next=r->next;
free(r);
p=p->next;
}
}
}
10、判斷帶頭結點的循環雙鏈表是否對稱
//雙鏈表很方便 可以直接定位到首位
int fun(DoubleList L)
{
DNode *p=L->next;
DNode *q=L->prior;
while(p != q && q->next != p) //結點數是當雙數的情況下從首位往中間推
{
if(p->data == q->data)
{
p=p->next;
q=q->prior;
}else{
return 0;
}
}
return 1;
}
11、有兩個循環單鏈表，鏈表頭指針分別為 h1,h2, 試編寫函數將 h2 鏈表接到 h1 之后，要求鏈接后仍保持循環鏈表形式
//這種方式里面包含最后的鏈表里面包含頭結點
void link(Linklist &h1,Linklist &h2)
{
LNode *p=h1;
LNode *q=h2;
while(p->next!=h1)
p=p->next;
while(q->next!=h2)
q=q->next;
p->next=h2;
q->next=h1;
}
12、判斷單鏈表是否有環
直接背誦
//思想用快慢指針來實現
int findloop(Linklist *L)
{
LNode *fast=L;
LNode *slow=L;
while(fast && fast->next)
{
slow=slow->next;
fast=fast->next>next;
if(slow == fast)
return 1;
}
return 0;
}
棧
棧的結構體
typedef struct stack
{
int data[maxsize];
int top;
}stack;
隊列的結構體
typedef struct queue
{
int data[maxsize];
int front,rear;
}queue;
1、Q是一個隊列，S是一個空棧，編寫算法使得隊列中元素逆置
草率版本
void reverse(stack &s,queue &q)
{
while(q.front != q.rear)
{
push(s,dequeue(q));
}
while(s.top!=-1)
enqueue(q,pop(s));
}
851版本
stack<int> s;
queue<int> q;
void reverse()
{
while(!q.empty())
{
int temp=q.front();
q.pop();
s.push(temp);
}
while(!s.empty())
{
int temp=s.top();
s.pop();
q.push(temp);
}
}
2、判斷單鏈表的全部 n 個字符是否中心對稱
851版本
//已知長度為n
bool judge(Linklist L)
{
LNode *p=L->next;
LNode *q=L->next;
stack<char> s;
while(p!=NULL)//塞入棧
{
s.push(p->data);
p=p->next;
}
for(int i=0;i<n/2;i++)
{
int temp=s.top();
if(q->data != temp)
return false;
s.pop();
q=q->next;
}
return true;
}
3、判斷一個表達式中括號是否配對(假設只包含圓括號)
851
bool judge(char txt[],int n)
{
stack<char> s;
//遍歷一遍
for(int i=0;i<n,i++)
{
if(txt[i] == '(')
s.push('(');
else if(txt[i]==')')
{
//檢查棧
if(s.empty())
return false;
else
s.pop(); //找到匹配的括號了
}
}
if(s.empty())
return true;
else
return false;
}
樹
//樹的結構體：
typedef struct BTNode
{
char data;
struct BTNode *lchild, *rchild;
} BTNode, *BiTree;
//帶初始化函數
struct TreeNode
{
int data;
struct TreeNode *lchild,*rchild;
TreeNode(int x):data(x),lchild(NULL),rchild(NULL){}
};
//使用初始化函數
TreeNode t1=TreeNode(1);
TreeNode t2=TreeNode(2);
TreeNode t3=TreeNode(3);
t1.lchild=&t2;
t1.rchild=&t3;
cout<<"depth="<<depth(&t1);
1.樹的層序遍歷+分層實現
queue<TreeNode*> que;
vector<vector<int> result;
void fun(TreeNode* T)
{
if(T!=NULL)
que.push(T);
vector<int> vec;
while(!que.empty())
{
int size=que.size();
while(size--)
{
TreeNode *temp=que.front();
que.pop();
vec.push_back(temp->data);
if(temp->lchild)
que.push(temp->lchild);
if(temp->rchild)
que.push(temp->rchild);
}
}
result.push(vec);
}
2.交換樹的所有左右孩子結點
void ExchangeChild(TNode* root)
{//交換樹的左右孩子
if(root->lchild||root->rchild)//如果存在一個非空孩子，則交換左右孩子
{
TNode *mid=root->lchild;
root->lchild=root->rchild;
root->rchild=mid;
}
if(root->lchild)
{
ExchangeChild(root->lchild);
}
if(root->rchild)
{
ExchangeChild(root->rchild);
}
}
3.雙親表示法做存儲結構，求樹的深度
struct node
{
int data;
int parent;
}
以雙親表示法作樹的存儲結構，對每一結點，找其雙親和雙親的雙親，直至根結點，就可求出每一結點的
層次，取其結點的最大層次就是樹的深度。
int maxdepth=0;
void fun(node[],int n)
{
for(int i=1;i<=n;i++)
{
int temp=0,f=i;
while(f>0)
{
temp++;
f=node[f].parent;
}
if(temp>maxdepth)
maxdepth=temp;
}
}
4.二叉樹非遞歸前、中、后序遍歷
//非遞歸前序遍歷
void preOrder2(BinTree *root)
{
stack<BinTree*> s;
BinTree *p=root;
while(p!=NULL || !s.empty())
{
while(p!=NULL) //往左下一路尋找
{
cout<<p->data<<" ";
s.push(p);
p=p->lchild;
}
if(!s.empty()) //右子樹
{
p=s.top();
s.pop();
p=p->rchild;
}
}
}
//非遞歸中序遍歷
void InOrder(TreeNode *root)
{
stack<TreeNode*> s;
TreeNode *p=root;
while(p!=NULL || !s.empty())
{
while(p!=NULL) //往左下一路尋找
{
s.push(p);
p=p->left;
}
if(!s.empty()) //右子樹
{
p=s.top();
s.pop();
cout<<p->val<<" "; //唯一變動
p=p->right;
}
}
}
//非遞歸后序遍歷
void Postorder(TreeNode *T)
{
stack<TreeNode*> s;
TreeNode *tag=NULL;
while(T!=NULL || !s.empty())
{
if(T!=NULL)
{
s.push(T);
T=T->lchild;//一路往左
}else
{
T=s.top(); //取出最后一個
if(T->rchild && T->rchild != tag)//往右走的通
T=T->rchild;
else
{
T=s.top();
s.pop();
cout<<T->data<<" ";
tag=T;
T=NULL;
}
}
}
}
代碼隨想錄版本
//非遞歸前序
vector<int> preorder(TreeNode *root)
{
stack<TreeNode*> s;
TreeNode *node;
vector<int> vec;
s.push(root);
while(!s.empty())
{
node=s.top();
s.pop();
if(node!=NULL) vec.push_back(node->data);
else continue;
s.push(node->rchild); //先入棧右孩子，再入棧左孩子，這樣出棧的時候就是（中、左、右）
s.push(node->lchild);
}
return vec;
}
//非遞歸后序
vector<int> postorder(TreeNode *root)
{
stack<TreeNode*> s;
TreeNode *node;
vector<int> vec;
s.push(root);
while(!s.empty())
{
node=s.top();
s.pop();
if(node!=NULL) vec.push_back(node->data);
else continue;
s.push(node->lchild); //先入棧左孩子，再入棧右孩子，這樣出棧的時候就是（中、右、左）
s.push(node->rchild);//最后再對（中、右、左）翻轉一下得到（左、右、中）
}
reverse(vec.begin(),vec.end()); //對vector進行逆置
return vec;
}
5.算二叉樹中所有節點個數
int sum=0;
int count(TreeNode *T,int &sum)
{
if(T==NULL)
return ;
sum++;
count(T->lchild,sum);
count(T->rchild,sum);
}
int count(TreeNode *p)
{
int n1,n2;
if(p==NULL)
return 0;
else
{
n1=count(p->lchild);
n2=count(p->rchild);
return n1+n2+1;
}
}
6.計算所有葉子結點個數
int sum=0;
int count(TreeNode *T,int &sum)
{
if(T==NULL)
return ;
else
{
if(T->lchild==NULL && T->rchild==NULL)
sum++;
count(T->lchild,sum);
count(T->rchild,sum);
}
}
int count(TreeNode *T)
{
int n1,n2;
if(T==NULL)
return 0;
if(!T->lchild && !T->rchild)
return 1;
else
{
n1=count(T->lchild);
n2=count(T->rchild);
return n1+n2;
}
}
7.計算雙分支結點個數
int count(TreeNode *T)
{
int n1,n2;
if(T==NULL)
return 0;
if(p->lchild && p->rchild)
{
n1=count(p->lchild);
n2=count(p->rchild);
return n1+n2+1;
}else{
n1=count(p->lchild);
n2=count(p->rchild);
return n1+n2;
}
}
8.計算二叉樹深度
int getDepth(TreeNode *p)
{
int LD,RD;
if(p==NULL)
return 0;
else
{
LD=getDepth(p->lchild);
RD=getDepth(p->rchild);
return max(LD,RD)+1;
}
}
9.查找二叉樹中data域等于key的結點是否存在，若存在，將q指向它，否則為空
fun(TreeNode *p,TreeNode *&q,int key)
{
//在遍歷基礎上加一個
if(p->data==key)
q=p;
}
10.求二叉樹中，值為x的結點的層號
//求層號加求值
//使用的時候用fun(root,x,1)
void fun(TreeNode *p,char x,int L)
{
if(p==NULL)
return ;
else
{
if(p->data==x)
cout<<"所在層數為"<<L;
fun(p->lchild,x,L+1);
fun(p->rchild,x,L+1);
}
}
11.先序遍歷中第k個結點
// int n=0;
// trave(root,2,n);
void trave(TreeNode *p,int k,int &n)
{
if(p==NULL)
return ;
else
{
++n;
if(k==n){
cout<<p->data;
return ;
}
trave(p->lchild,k,n);
trave(p->rchild,k,n);
}
}
12.二叉樹中元素為 x 的結點，刪除以它為根的子樹
void del(TreeNode *&bt,char key)
{
if(bt==NULL)
return ;
else
{
if(bt->data==key){
bt=NULL; //就完成刪除了，連同子樹一起刪除
return;
}
del(bt->lchild,key);
del(bt->rchild,key);
}
}
13.刪除二叉排序樹的值為x的結點（刪完需要重排）
核心思想：已刪除某個結點為例，用非遞歸后序遍歷算法調用刪除某個結點的函數.
void Delete(BiTree *p)
{ /* 從二叉排序樹中刪除結點p，并重接它的左或右子樹。 */
BiTree *q,*s;
if(!p->rchild) /* 右子樹空則只需重接它的左子樹（待刪結點是葉子也走此分支） */
{
q=p;//用q結點保存p的位置
p=p->lchild;
delete q;
}
else if(!p->lchild) /* 只需重接它的右子樹 */
{
q=p;
p=p->rchild;
delete q;
}
else /* 左右子樹均不空 */
{
q=p;
s=p->lchild;
while(s->rchild) /* 轉左，然后向右到盡頭（找待刪結點的前驅） */
{
q=s;
s=s->rchild;
}
p->data=s->data; /* s指向被刪結點的＂前驅＂（將被刪結點前驅的值取代被刪結點的值）*/
if(q!=p)
q->rchild=s->lchild; /* 重接*q的右子樹 */
else
q->lchild=s->lchild; /* 重接*q的左子樹 */
delete s;
}
}
14.在二叉樹中查找值為 x 的結點，打印出值為x的所有祖先
后序遍歷就是天然的回溯過程，最先處理的一定是葉子節點。
接下來就看如何判斷一個節點是節點q和節點p的公共公共祖先呢。
「如果找到一個節點，發現左子樹出現結點p，右子樹出現節點q，或者 左子樹出現結點q，右子樹出現節點p，那么該節點就是節點p和q的最近公共祖先?！?
使用后序遍歷，回溯的過程，就是從低向上遍歷節點，一旦發現如何這個條件的節點，就是最近公共節點了。
//后序遍歷的改版
void fun(TreeNode *T,char x)
{
stack<TreeNode*> s;
TreeNode *tag=NULL;
while(T!=NULL || !s.empty())
{
if(T!=NULL)
{
s.push(T);
T=T->lchild;
}else
{
T=s.top();
if(T->data=x)//非遞歸后序遍歷中找，找到立馬把前面的全部輸出干凈
while(!s.empty())
{
cout<<s.top();
s.pop();
}
tag=T;
T=NULL;
}
}
}
15.二叉樹的最近公共祖先
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root == NULL || root == p || root == q)
return root;
TreeNode *left = lowestCommonAncestor(root->left, p, q);
TreeNode *right = lowestCommonAncestor(root->right, p, q);
if(left == NULL)
return right;
if(right == NULL)
return left;
return root;
}
16.計算二叉樹的帶權路徑長度（葉子節點）
void fun(TreeNode* T)
{
if(T!=NULL)
que.push(T);
vector<int> vec;
int deep=0;
int wpl=0;
while(!que.empty())
{
int size=que.size();
while(size--)
{
TreeNode *temp=que.front();
que.pop();
if(temp->lchild==NULL && temp->rchild==NULL)//到達葉子結點
wpl+=deep*temp->data;
if(temp->lchild)
que.push(temp->lchild);
if(temp->rchild)
que.push(temp->rchild);
}
deep++;
}
}
17.將給定二叉樹轉化為等價中綴表達式
void fun(TreeNode *p,int deep)
{
if(p==NULL)
return ;
else
{
if((p->lchild || p->rchild) && deep>1)
cout<<'(';
if(p->lchild!=NULL)
fun(p->lchild,deep+1);
cout<<p->data;
if(p->rchild!=NULL)
fun(p->rchild,deep+1);
if((p->lchild || p->rchild) && deep>1)
cout<<')';
}
}
巧妙運用中序遍歷，實現轉化。
注意括號的增加
1.左子樹有子樹加括號
2.右子樹有子樹結束加括號
3.根節點不加括號
4.葉子結點不加括號
void BtreeToExp(TreeNode *T,int deep)
{
if(T==NULL){
return ;
}
else if(T->left==NULL&&T->right==NULL){ //葉子結點
cout<<T->data;
}
else{
if(deep>1) cout<<"(";
BtreeToExp(T->left,deep+1);
cout<<T->data;
BtreeToExp(T->right,deep+1);
if(deep>1) cout<<")";
}
}
18.用孩子兄弟表示法求樹所有葉子結點個數
//左孩子右兄弟
int fun(TreeNode *p)
{
if(p==NULL)
return 0;
if(p->lchild==NULL)//無孩子——葉子結點
return fun(p->rchild)+1;
return fun(p->rchild)+fun(p->rchild);
}
圖
圖的存儲
鄰接表存儲：
struct ArcNode
{
int adjvex; //存儲邊的另一個頂點 adjList: adj是adjoin的縮寫,鄰接的意思
struct ArcNode *nextarc;
};
struct Vnode
{
int data;
struct ArcNode *firstarc;
};
struct AGraph
{
Vnode adjlist[maxsize];
int numver, numedg;
};
鄰接矩陣存儲：
typedef struct
{
char data[maxsize];
int Edge[maxsize][maxsize];
int numver, numedg; //vertex 頂點
} mgraph
圖算法 Dijkstra 迪杰斯特拉
void Dijkstra(MGraph &g,int v) //從v結點開始
{
int vis[maxn];//標記數組
int path[maxn];//v到任一結點的前項結點
int dist[maxn];//v到其他頂點的路徑長度
//初始化
for(int i=0;i<g->vernum;i++)
{
dist[i]=g->edges[v][i];//v-->其他頂點
vis[i]=0;
if(g->edges[v][i]<Maxn) //v-i之間有路徑
path[i]=v;
else
path[i]=-1;
}
vis[v]=1;
path[v]=-1; //頂點v自身
int k; //標記最小值位置
for(int i=1;i<g->vernum;i++)
{
int min =Maxn;
for(int j=0;j<g->vernum;j++)
{
if(dist[j]<min && vis[j]==0)//未訪問中找最小的一個
{
min=dist[j];
k=j;
}
}
vis[k]=1;
for(int j=0;j<g->vernum;j++)//更新最短路徑
{
if(vis[j]==0 && dist[k]+g->edges[k][j]<dist[j])//從v-k + 從k-j 小于從v-j
{
dist[j]=dist[k]+g->edges[k][j] //更新
path[j]=k;
}
}
}
}
假設中國每個省會與其他所有省會之間都有直達鐵路，prim是研究怎么用最短的里程遍歷完所有省會，dijkstra是研究從某一個省會（比如昆明）出發到其他各省會的最短路徑；可以想象昆明到哈爾濱在prim里是不會直連的因為這個邊的權值太大，而在dijkstra里一定是直連的
prim是“用最少的里程連接所有省會”
dijkstra是“兩省會最短路徑”
Dijkstra——最短路徑
prim——最小生成樹
代碼上非常接近
Dijkstra:vis[]、dist[]、path[]
prim:selected[]、minDist[]、parent[]
圖算法 kruskal克魯斯卡爾（依次加入最小邊）
#include<iostream>
#include<algorithm>
using namespace std;
int n,m; //n個點，m條邊
int pre[10000];//所有點連通圖的標志點
struct edge
{
int from,to;//邊左右連接的兩個點
int len;//邊的權值或者長度
};
edge arr[10000]; //m條邊
bool cmp(edge a,edge b)
{
return a.len<b.len;
}
int Find(int x)//找聯通圖的標志點+壓縮路徑
{
int flag=x;
while(pre[flag]!=flag)
flag=pre[flag];
int temp;
while(x!=flag)//壓縮路徑可以省
{
temp=pre[x];
pre[x]=flag;
x=temp;
}
return flag;
}
int main()
{
cin>>n>>m;
for(int i=0;i<m;i++)
cin>>arr[i].from>>arr[i].to>>arr[i].len;
sort(arr,arr+n,cmp);
for(int i=1;i<=n;i++)//初始每個點都是單獨聯通圖
pre[i]=i;
int pFrom,pTo;
int ans=0;
for(int i=0;i<m;i++)
{
pFrom=Find(arr[i].from);//出發點所在連通圖
pTo = Find(arr[i].to);
if(pFrom!=pTo) //兩個點構不成環
{
ans+=arr[i].len;
pre[pFrom]=pTo;
}
}
cout<<ans<<endl;
return 0;
}
圖算法 Floyd算法
類似于在圖里使用動態規劃思想
求解的是從任意vi--vj的最短路徑
圖論總結
1. 鄰接表從vi到vj有無路徑
int visited[MAX_NUM]={0};
void DFS(AdjList G,int v){//遍歷從v
ArcNode *p;
visited[v]=1;//已被訪問過
p=G[v].firstarc;
while(p!=NULL){
if(visited[p->adjvex]==0){//若w=p->adjvex 頂點未訪問，遞歸訪問它
DFS(G,p->adjvex);
}
p=p->nextarc;//訪問過p指向頂點v的下一個鄰接點
}
}
int main()
{
cin>>vi>>vj;
if(visit[vj]==1)
cout<<"可以";
else
cout<<"不行"
}
2.圖的廣度優先和深度優先遍歷
bool visited[MaxVerNum];//訪問標記數組，用于遍歷時的標記
//廣度遍歷函數 參數：圖G,開始結點下標start 作用：寬度遍歷
void BFS(Graph G, int start)
{
queue<int> Q;//輔助隊列
cout << G.Vex[start];//訪問結點
visited[start] = true;
Q.push(start);//入隊
while (!Q.empty())//隊列非空
{
int v = Q.front();//得到隊頭元素
Q.pop();//出隊
for (int j = 0; j<G.vexnum; j++)//鄰接點
{
if (G.Edge[v][j] <INF && !visited[j])//是鄰接點且未訪問
{
cout << "->";
cout << G.Vex[j];//訪問結點
visited[j] = true;
Q.push(j);//入隊
}
}
}//while
cout << endl;
}
//深度遍歷函數（遞歸形式）參數：圖G,開始結點下標start 作用：深度遍歷
void DFS(Graph G, int start)
{
cout << G.Vex[start];//訪問
visited[start] = true;
for (int j = 0; j < G.vexnum; j++)
{
if (G.Edge[start][j] < INF && !visited[j])//是鄰接點且未訪問
{
cout << "->";
DFS(G, j);//遞歸深度遍歷
}
}
}
3.圖的深度優先遍歷——dfs非遞歸版本
void dfs(AGraph *g,int v) //基于鄰接表的dfs非遞歸版本
{
ArcNode *p;
stack<int> s;
int i,k;
int visit[maxn];
for(i=0;i<g->vernum;i++)
visit[i]=0;
cout<<g->adjlist[v].data;
visit[v]=1;
s.push(v);
//關鍵步驟
while(!s.empty())
{
k=s.top();
p=g->adjlist[k].firstarc;
while(p!NULL && visit[p->adjvex]==1)
p=p->nextarc;
if(p==NULL)
s.pop();
else
{
cout<<p->adjvex.data;
visit[p->adjvex]=1;
s.push(p->adjce);
}
}
}
查找
1.折半查找
非遞歸
遞歸查找
int arr[maxn];
int n;
int target;
int binary_search(int arr[],int left,int right,int target){
if(left>right)
return -1;
int mid = (left + right) / 2;
if(arr[mid] == target)
return mid;
else if(arr[mid]>target)
return binary_search(arr,left,mid-1,target);
else
return binary_search(arr,mid,right,target);
}
2.分塊查找
核心思想:把一個完整的數組分成若干塊。每一個塊存儲了這個塊的起始位置和結束位置以及每個塊中數據的
最大值（塊內值的順序是無序的，塊與塊之間是按照從小到大排序）。如果我們要用分塊查找某個值我們可以先
查找值所在的塊(用順序查找值所在的塊也可以折半插入查找)，當找出所在的塊再用依次順序查找即可確定是
否能找到所查找的值.
# 1.塊的結構體大家不要忘記
# 2.要進行分塊查找先查找元素所在的塊，（塊與塊之間是有序的，可以使用折半查找之類的）
# 3.再從塊內用順序查找
struct indexElem
{
int max;//存儲塊內的最大值
int low, high;//low表示在原數組中的存儲起始下標, high表示在原數組中的結束下標
};
int block_search(indexElem index[], int k, int n, int arr[])//k是需要查找的數字，arr表示原數組，index是結構體類型的索引表 n表示有n塊
{
int i=0, j, k;
while((i<n)&&indx[i].max<k)//找到所屬的塊0--n-1
i++;
if (i>=n)
{
cout<<"not found\n";
return 0;
}
j=index[i].low;//塊內的起始下標
while(j<=indx[i].high&&arr[j]!=k)//在塊內進行查找
j++;
if(j>index[i].high)
{
cout<<"not found\n";
return 0;
}
else
return j;//返回下標
}
排序算法
1.拓撲排序
核心思想：從入度為0的結點開始刪除 判斷是否為有向無環圖(刪除的結點是否為n個)
1.首先將圖中入度為0的結點入棧，棧初始為空；
2.當棧非空時棧首元素出棧，訪問并且將與此元素相鄰頂點的入度減1；（去掉相關的邊）
3.當某個頂點在去掉相關邊后入度為0，則入棧；
4.重復執行2.3操作并且統計訪問頂點個數直到?？?。
struct ArcNode
{
int adjvex; //存儲邊的另一個頂點
struct ArcNode *nextarc;
};
struct Vnode
{
int data;
int cnt; //入度個數
struct ArcNode *firstarc;
};
struct AGraph
{
Vnode adjlist[maxsize];
int vexnum, arcnum;
};
int Puop(AGraph *G)
{
int n=0;//表示刪除頂點的個數
stack<Vode> s;
for(int i=0;i<G->vexnum;i++)
{
if(G->adjlist[i].cnt == 0)
s.push(G->adjlist[i]);//遍歷n個頂點，入度為零的入棧
}
ArcNode *p;
while(!s.empty())
{
Vnode *temp=s.top();
s.pop();
n++;
p=temp->firstarc;
while(p!=NULL)//遍歷所有的鄰接邊
{
int j=p->adjvex;
--G->adjlist[k].cnt;//入度-1
if(G->adjlist[k].cnt==0)
{
s.push(G->adjlist[k]);
}
p=p->next;
}
}
if(n == G->vexNUm)
return 1;
else
return 0;
}
2.直接插入排序
void Insertsort(int arr[],int n)
{
int i.j;
for(i=2;i<=n;i++)
{
if(arr[i]<arr[i-1])
{
arr[0]=arr[i];
for(j=i-1;arr[j]>arr[0];j--)
{
arr[j+1]=arr[j];
}
arr[j+1]=arr[0];
}
}
}
3.折半插入排序
//基于直接插入排序改編
void ZBInsertSort(int A[],int n){
int i,j,high,low,mid;
for(i=2;i<=n;i++){
A[0] = A[i];
low = 1;
high = i-1;
while(low<=high){
mid=(low+high)/2;
if(A[mid]>A[0]){
high=mid-1;
}
else{
low = mid+1;
}
}//while執行完 high+1為需要插入的位置
for(j = i-1;j>=high+1;--j){
A[j+1] = A[j];
}
A[high+1] = A[0];
}
}
4. 堆排序
堆排序利用大根堆
從小到大排序
排到的最大的放在數組末尾，就不會變動了
//以元素k為根的子樹進行調整（大根堆）
void HeadAdjust(int a[],int k,int n)
{
a[0] = a[k]; //暫時提出去
for(int i=k*2;i<=n;K*=2)
{
if(i<n && a[i]<a[i+1]) //左右子樹找更大的一個
i++;
if(a[i]<a[0])//不用調換
break;
else //需要調換
{
a[k] = a[i];
k=i;
}
}
a[k]=a[0];
}
//建立大根堆
void BuildMaxHeap(int a[],int n){
for(int i=n/2;i>=1;i--){ //除開葉子結點，都要捋一遍
HeadAdjust(a,i,n);
}
}
//堆排序
void HeapSort(int a[],int n){
BuildMaxHeap(a,n);
for(int i=n;i>1;i--){
swap(a[i],a[1]); //把第i個放到a[1]
HeadAdjust(a,1,i-1); //以a[1]為大根堆 調整
}
}
5.希爾排序
//希爾排序
//往后逐個對比
void ShellSort(int A[],int n){
int d,i,j;
for(d = n/2;d>=1;d = d/2){
for(i=d+1;i<=n;++i){
if(A[i]<A[i-d]){
A[0] = A[i];
for(j=i-d;j>0 && A[0]<A[j];j-=d)
A[j+d] = A[j];
A[j+d] = A[0];
}
}
}
}
//希爾排序
//一串捋直了再下一串
void testShellSort(int A[],int n){
int d,i,j;
for(d = n/2;d>=1;d=d/2){ //步長變化
for(i=1;i<=d;i++){ //多少組
for(i=d+1;i<=n;i+=d){ //遍歷每一組的所有數字
if(A[i] < A[i-d]){
A[0] = A[i]; //小的放在A[0]
for(j=i-d;j>0 && A[0]<A[j];j-=d){
A[j+d] = A[j];
}
A[j+d] = A[0];
}
}
}
}
}
//插入排序的復雜度都是O(n^2)
int main(){
int A[] = {NULL,49,38,65,97,76,13,27,49};
for(int i = 1;i<MaxSize;i++){
cout<<A[i];
}
testShellSort(A,8);
for(int i = 1;i<MaxSize;i++){
cout<<A[i];
}
return 0;
}
6.冒泡排序
//最簡單版冒泡
void BubbleSort(int A[],int n)
{
for(int i=0;i<n;i++)
{
for(int j=n-1;j>1;j--)
{
if(A[j-1] > A[j])
swap(A[j-1],A[j]);
}
}
}
//王道版
void BubbleSort(int A[],int n){
for(int i=0;i<n-1;i++){ //交換的趟數 = n-1
bool flag = false; //表示本趟冒泡是否發生交換的標志
for(int j=n-1;j>i;j--){ //一趟冒泡
if(A[j-1] > A[j]){ //若為逆，則交換
swap(A[j-1],A[j]);
flag = true;
}
}
if(flag == false){ //本趟遍歷之后如果沒有發生交換，則已經有序
break;
}
}
}
7.快速排序
//Partition （分割）
int Partition(int A[],int low,int high){
int pivot = A[low]; //pivot:樞軸
while(low < high){
while(low<high && A[high] >=pivot) --high; //high前推找比pivot小的
A[low] = A[high];
while(low<high && A[low] <=pivot) ++low; //low后推找比pivot大的
A[high] = A[low];
}
A[low] = pivot;
return low;
}
void QuickSort(int A[],int low,int high){
if(low<high){ //遞歸跳出的條件
int pivotpos = Partition(A,low,high); //劃分
QuickSort(A,low,pivotpos-1); //劃分左子表
QuickSort(A,pivotpos+1,high); //劃分右子表
}
}
8.簡單選擇排序
//王道版 簡單選擇排序
void SelectSort(int A[],int n){
for(int i=0;i<n-1;i++){ //一共排n-1趟
int min = i; //記錄最小元素位置
for(int j=i+1;j<n;j++)
if(A[j]<A[min])
min=j; //更新最小元素位置
if(min != i)
swap(A[i],A[min]);
}
}
9.歸并排序
int n,a[1000],b[1000];
void merge(int a[],int low,int mid,int high)
{
int i=low,j=mid+1,k=low;
while (i<=mid && j<=high)
{
if (a[i]<a[j])
b[k++]=a[i++];
else
b[k++]=a[j++];
}
while (i<=mid)
b[k++]=a[i++];
while (j<=high)
b[k++]=a[j++];
for (int i=low;i<=high;i++)
a[i]=b[i];
}
void mergesort(int a[],int low,int high)
{
if (low>=high)
return;
int mid=(low+high)/2;
mergesort(a,low,mid);
mergesort(a,mid+1,high);
merge(a,low,mid,high);
}
后綴表達式計算
思路：遍歷后綴表達式字符串，如果遇到數字就直接入棧，如果遇到操作符，先出棧第一個數字設為b，再出棧第二個元素設為a，計算 a 操作符 b（a+b或a-b或a*b或a/b），再將結果入棧。直到遍歷完表達式，棧中元素為結果。
double op(int a,char Op,int b) //op函數實現 a Op b
{
if(Op=='+') return a+b;
if(Op=='-') return a-b;
if(Op=='*') return a*b;
if(Op=='/')
{
if(b==0)
{
cout<<"Error"<<endl;
return 0;
}
return a*1.0 / (b*1.0);
}
}
int fun(char exp[])
{
int len = strlen(exp);
stack<double> s;
for(int i=0;i<len;i++)
{
if(exp[i]>='0'&&exp[i]<='9')
s.push(exp[i]-'0');
else
{
double a,b,c;
b = s.top();s.pop();
a = s.top();s.pop();
c = op(a,exp[i],b); //調用操作函數，將結果賦值給c
s.push(c);//操作結果入棧
}
}
return s.top();//最后棧頂剩的元素就是結果
}
文件處理（預防考試偷雞）
#include<fstream>
寫入文件
使用流插入運算符（ << ）向文件寫入信息，就像使用該運算符輸出信息到屏幕上一樣。唯一不同的是，在這里您使用的是 ofstream 或 fstream 對象，而不是 cout 對象。
讀取文件
使用流提取運算符（ >> ）從文件讀取信息，就像使用該運算符從鍵盤輸入信息一樣。唯一不同的是，在這里您使用的是 ifstream 或 fstream 對象，而不是 cin 對象。
讀取 & 寫入實例
下面的 C++ 程序以讀寫模式打開一個文件。在向文件 afile.dat 寫入用戶輸入的信息之后，程序從文件讀取信息，并將其輸出到屏幕上：
#include <fstream>
#include <iostream>
using namespace std;
int main ()
{
char data[100];
// 以寫模式打開文件
ofstream outfile;
outfile.open("afile.dat");
cout << "Writing to the file" << endl;
cout << "Enter your name: ";
cin.getline(data, 100);
// 向文件寫入用戶輸入的數據
outfile << data << endl;
cout << "Enter your age: ";
cin >> data;
cin.ignore();
// 再次向文件寫入用戶輸入的數據
outfile << data << endl;
// 關閉打開的文件
outfile.close();
// 以讀模式打開文件
ifstream infile;
infile.open("afile.dat");
cout << "Reading from the file" << endl;
infile >> data;
// 在屏幕上寫入數據
cout << data << endl;
// 再次從文件讀取數據，并顯示它
infile >> data;
cout << data << endl;
// 關閉打開的文件
infile.close();
return 0;
}
總結
以上是生活随笔為你收集整理的[持续更新][数据结构][算法]涵盖线性表、栈、链表、队列、图、动态规划、分治递归、回溯贪心分支限界、击穿专业课！！！的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 迅雷打不开闪退怎么办(PhotoShop
- 下一篇： 微信好友把你删了还能看朋友圈吗(微信公众