對資料結構和演算法感興趣的可以關注一下https://github.com/MCQ1999/Datastructure_Algorithm_Solutions，分享演算法題的解題思路和代碼~
1.壓縮演算法（堆疊模擬）
題意
鏈接：https://www.nowcoder.com/questionTerminal/c27561e5b7e0441493adb9a54071888d
來源：牛客網
小Q想要給他的朋友發送一個神秘字串，但是他發現字串的過于長了，于是小Q發明了一種壓縮演算法對字串中重復的部分進行了壓縮，對于字串中連續的m個相同字串S將會壓縮為m|S，例如字串ABCABCABC將會被壓縮為[3|ABC]，現在小Q的同學收到了小Q發送過來的字串，你能幫助他進行解壓縮么？
輸入描述:
輸入第一行包含一個字串s，代表壓縮后的字串，
S的長度<=1000;
S僅包含大寫字母、[、]、|;
解壓后的字串長度不超過100000;
壓縮遞回層數不超過10層;
輸出描述:
輸出一個字串，代表解壓后的字串，
示例1
輸入
HG[3|B[2|CA]]F
輸出
HGBCACABCACABCACAF
說明
HG[3|B[2|CA]]F?>HG[3|BCACA]F?>HGBCACABCACABCACAF
思路
堆疊模擬，
代碼
#include<bits/stdc++.h>
using namespace std;
int main(){
stack<char> st;
string s;
cin>>s;
int n=s.length();
for(int i=0;i<n;i++){
if(s[i]!=']'){
st.push(s[i]);
}else {
string tmp="";
while(st.top()!='|'){
tmp+=st.top();
st.pop();
}
reverse(tmp.begin(),tmp.end());
string num="";
st.pop();
while(st.top()!='['){
num+=st.top();
st.pop();
}
st.pop();
reverse(num.begin(),num.end());
int x=stoi(num);
string t="";
while(x--){
for(char c:tmp){
st.push(c);
}
}
}
}
string ans;
while(!st.empty()){
ans+=st.top();
st.pop();
}
reverse(ans.begin(),ans.end());
cout<<ans<<endl;
return 0;
}
2.逛街 （單調堆疊）
題意
鏈接：https://www.nowcoder.com/questionTerminal/35fac8d69f314e958a150c141894ef6a
來源：牛客網
小Q在周末的時候和他的小伙伴來到大城市逛街，一條步行街上有很多高樓，共有n座高樓排成一行，
小Q從第一棟一直走到了最后一棟，小Q從來都沒有見到這么多的樓，所以他想知道他在每棟樓的位置處能看到多少棟樓呢？（當前面的樓的高度大于等于后面的樓時，后面的樓將被擋住）
輸入描述:
輸入第一行將包含一個數字n，代表樓的棟數，接下來的一行將包含n個數字wi(1<=i<=n)，代表每一棟樓的高度，
1<=n<=100000;
1<=wi<=100000;
輸出描述:
輸出一行，包含空格分割的n個數字vi，分別代表小Q在第i棟樓時能看到的樓的數量，
示例1
輸入
6
5 3 8 3 2 5
輸出
3 3 5 4 4 4
說明
當小Q處于位置3時，他可以向前看到位置2,1處的樓，向后看到位置4,6處的樓，加上第3棟樓，共可看到5棟樓，當小Q處于位置4時，他可以向前看到位置3處的樓，向后看到位置5,6處的樓，加上第4棟樓，共可看到4棟樓，
思路
單調堆疊，
維護從堆疊底到堆疊頂遞減的堆疊，這么做的意義是正著遍歷可以求出每個點往左邊能看到的個數，倒著遍歷求出每個點往右能看到的個數，比如正著遍歷，因為堆疊里面元素是單減的，那么每個點往左看，堆疊里面都是大于這個點的，所以每次堆疊的大小就是對應的個數，最后再加上1就是答案了，
代碼
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N],b[N];
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
stack<int> st;
for(int i=1;i<=n;i++){
b[i]+=st.size();
while(!st.empty()&&a[i]>=st.top()){
st.pop();
}
st.push(a[i]);
}
while(!st.empty()) st.pop();
for(int i=n;i>=1;i--){
b[i]+=st.size();
while(!st.empty()&&a[i]>=st.top()){
st.pop();
}
st.push(a[i]);
}
for(int i=1;i<=n;i++){
printf("%d ",b[i]+1);
}
puts("");
return 0;
}
3.逆序對
題意
鏈接：https://www.nowcoder.com/questionTerminal/8fe007e54fc04b5e82089aaa71ba3553
來源：牛客網
作為程式員的小Q，他的數列和其他人的不太一樣，他有2n2^n2n個數，
老板問了小Q一共 m次，每次給出一個整數qi(1<=i<=m)q_i (1 <= i <= m)qi?(1<=i<=m), 要求小Q把這些數每2qi2^{q_i}2qi?分為一組，然后把每組進行翻轉，小Q想知道每次操作后整個序列中的逆序對個數是多少呢？
例如:
對于序列1 3 4 2，逆序對有(4, 2),(3, 2),總數量為2，
翻轉之后為2 4 3 1，逆序對有(2, 1),(4, 3), (4, 1), (3, 1),總數量為4，
輸入描述:
第一行一個數n(0≤n≤20)n(0 \leq n \leq 20)n(0≤n≤20)
第二行2n2^n2n個數，表示初始的序列(1≤初始序列≤1091 \leq 初始序列 \leq 10^91≤初始序列≤109)
第三行一個數m(1≤m≤106)m(1 \leq m \leq 10^6)m(1≤m≤106)
第四行m個數表示qi(0≤qi≤n)q_i(0 \leq q_i \leq n)qi?(0≤qi?≤n)
輸出描述:
m行每行一個數表示答案，
示例1
輸入
2
2 1 4 3
4
1 2 0 2
輸出
0
6
6
0
說明
初始序列2 1 4 3
2q1=22^{q_1} = 22q1?=2 ->
第一次：1 2 3 4 -> 逆序對數為0
2q2=42^{q_2} = 42q2?=4 ->
第二次：4 3 2 1 -> 逆序對數為6
2q3=12^{q_3} = 12q3?=1 ->
第三次：4 3 2 1 -> 逆序對數為6
2q4=42^{q_4} = 42q4?=4 ->
第四次：1 2 3 4 -> 逆序對數為0
思路
咕咕咕
4.假期（動態規劃）
題意
鏈接：https://www.nowcoder.com/questionTerminal/7cd9a140387e455a972e8fea0e74be2c
來源：牛客網
由于業績優秀，公司給小Q放了 n 天的假，身為作業狂的小Q打算在在假期中作業、鍛煉或者休息，他有個奇怪的習慣：不會連續兩天作業或鍛煉，只有當公司營業時，小Q才能去作業，只有當健身房營業時，小Q才能去健身，小Q一天只能干一件事，給出假期中公司，健身房的營業情況，求小Q最少需要休息幾天，
輸入描述:
第一行一個整數 n(1≤n≤100000)n(1\leq n\leq 100000)n(1≤n≤100000) 表示放假天數
第二行 n 個數 每個數為0或1,第 i 個數表示公司在第 i 天是否營業
第三行 n 個數 每個數為0或1,第 i 個數表示健身房在第 i 天是否營業
（1為營業 0為不營業）
輸出描述:
一個整數，表示小Q休息的最少天數
示例1
輸入
4
1 1 0 0
0 1 1 0
輸出
2
說明
小Q可以在第一天作業，第二天或第三天健身，小Q最少休息2天
思路
dp(i,0)表示在到第i天作業所能休息的最少天數，dp(i,1)表示在到第i天健身所能休息的最少天數，dp(i,2)表示在到第i天休息所能休息的最少天數，
那么
如果第i天能作業，肯定是從第i-1天不作業轉移過來
如果第i天能健身，肯定是從第i-1天不健身轉移過來
第i天休息，則是從第i-1天三種狀態轉移過來，因為沒有要求不能連續休息兩天，
代碼
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N],b[N],dp[N][3];
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++){
scanf("%d",&b[i]);
}
memset(dp,0x3f3f3f3f,sizeof(dp));
if(a[1]){
dp[1][0]=0;
}
if(b[1]){
dp[1][1]=0;
}
dp[1][2]=1;
for(int i=2;i<=n;i++){
if(a[i]){
dp[i][0]=min(dp[i-1][1],dp[i-1][2]);
}
if(b[i]){
dp[i][1]=min(dp[i-1][0],dp[i-1][2]);
}
dp[i][2]=min(dp[i-1][0],min(dp[i-1][1],dp[i-1][2]))+1;
}
printf("%d\n",min(dp[n][0],min(dp[n][1],dp[n][2])));
return 0;
}
5.視野爭奪 （貪心）
題意
鏈接：https://www.nowcoder.com/questionTerminal/61e1e66e39f348cdb6495de91ac36a41
來源：牛客網
小Q在進行一場競技游戲,這場游戲的勝負關鍵就在于能否能爭奪一條長度為L的河道,即可以看作是[0,L]的一條數軸，
這款競技游戲當中有n個可以提供視野的道具?真視守衛,第i個真視守衛能夠覆寫區間[xi,yi]，現在小Q想知道至少用幾個真視守衛就可以覆寫整段河道，
輸入描述:
輸入包括n+1行，
第一行包括兩個正整數n和L(1<=n<=105,1<=L<=109)
接下來的n行,每行兩個正整數xi,yi(0<=xi<=yi<=109),表示第i個真視守衛覆寫的區間，
輸出描述:
一個整數，表示最少需要的真視守衛數量, 如果無解, 輸出-1，
示例1
輸入
4 6
3 6
2 4
0 2
4 7
輸出
3
思路
按左端點從小到大，右端點從大到小排序，每次看一個區間能里的點往右最大能延伸到哪（mx），下次更新上限（up）的時候就用這個mx，這個程序和leetcode跳躍游戲那題很像，
代碼
#include<bits/stdc++.h>
using namespace std;
struct node{
int l,r;
bool operator<(node b){
if(l==b.l){
return r>b.r;
}
return l<b.l;
}
}g[100005];
int main(){
int n,L;
scanf("%d%d",&n,&L);
for(int i=0;i<n;i++){
scanf("%d%d",&g[i].l,&g[i].r);
}
sort(g,g+n);
int up=g[0].r,mx=g[0].r,cnt=1;
if(g[0].l>0) {
printf("-1\n");
return 0;
}
for(int i=1;i<n;i++){
if(g[i].l<=up){
mx=max(g[i].r,mx);
if(mx>=L){
printf("%d\n",cnt+1);
return 0;
}
}else {
cnt++;
up=max(up,mx);
i--;
}
}
if(mx<L){
printf("-1\n");
return 0;
}
printf("%d\n",cnt);
return 0;
}
總結
騰訊的筆試題做起來還是有點難度的，考察點也比較全（貪心、dp、資料結構），題目也很有價值，值得反復做，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/85170.html
標籤：其他
上一篇：二叉樹中和為某一值的路徑