美團2024年春招第一場筆試 C++

目錄

1,小美的平衡矩陣

2,小美的數組詢問

3,小美的MT

?4,小美的朋友關系


1,小美的平衡矩陣

?【題目描述】

給定一個n*n的矩陣,該矩陣只包含數字0和1。對于 每個i(1<=i<=n),求在該矩陣中,有多少個i*i的區域滿足0的個數等于1的個數???

【題目解析】

示例演示:

?如上圖,1*1的區域結果為0,2*2的區域結果為7。

算法:前綴和+遍歷

題目中給的數據范圍是n<=200,所以可以直接遍歷數組。

維護 一個前綴和數組統計以(x,y)這個點為右下角,以(1,1)這個點為左上角,這個區域中所有元素的和,由于數組中的數要么是0,要么是1,所以前綴和就表示某個區域中1的個數。

有了前綴和數組,就可以快速 求出某個區域中1的個數,如圖:

而這個區域的大小我們是知道的,假設是k,那么這個區域的元素個數就是k*k。如果滿足這個區間中1的個數等于k*k/2,那么說明 這個區間中0和1的個數 相等。而1的個數我們可以通過前綴和來表示。

同時還有一點,如果k為奇數,那么k*k的區域中元素個數一定為奇數 ,所以0和1的個數一定不相等。直接輸出0即可。

?注意:在輸入數據的時候,如果是以整數的形式接受,那么不建議使用cin,因為cin會把第一行的所有數據讀成一個整數。就比如 上面的示例,第一行會被讀成一個整數1010,而我們期望是讀到4個整數的,這是可以使用scanf("%1d",&a),使用 %1d占位符可以確保讀到的第一行是4個整數。

【代碼】

#include <iostream>
#include <vector>
using namespace std;const int N = 205;
int arr[N][N], s[N][N];
//s為前綴和數組
//統計矩形(1,1)到(n,n)中1的數量int main()
{int n = 0;cin >> n;for(int  i=1;i<=n;i++)for (int j = 1; j <= n; j++){scanf("%1d", &arr[i][j]);s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + arr[i][j];}cout << 0 << endl;for (int k = 2; k <= n; k++){if (k & 1){cout << 0 << endl;continue;}int ans = 0;for(int i=1;i+k-1<=n;i++)for (int j = 1; j+k-1 <= n; j++){//(i,j)是左上角,需要我們計算出k*k這個區域右下角的坐標int x = i + k - 1;int y = j + k - 1;if (s[x][y] - s[i - 1][y] - s[x][j - 1] + s[i - 1][j - 1] == k * k / 2)ans++;}cout << ans << endl;}return 0;
}

2,小美的數組詢問

?直接遍歷即可?

#include <iostream>
using namespace std;const int N=1e5+10;
int arr[N];
int main()
{int n=0,q=0;cin>>n>>q;long long sum=0,count=0;for(int i=1;i<=n;i++){cin>>arr[i];sum+=arr[i];if(arr[i]==0)count++;}int l,r;while(q--){cin>>l>>r;cout<<sum+count*l<<" "<<sum+count*r<<endl;}return 0;
}

3,小美的MT

統計元字符中 有多少個M和T,再加上最多可以修改 多少個即可。

//小美的MT
#include <iostream>
#include <string>
using namespace std;int main()
{int n = 0, k = 0;cin >> n >> k;string str;cin >> str;int ans = 0;for (int i = 0; i < n; i++){if (str[i] == 'M' || str[i] == 'T')ans++;}if (k > n - ans)cout << n << endl;elsecout << ans + k << endl;return 0;
}

?4,小美的朋友關系

?【題目描述】

總人數為n,編號u和v的人之間存在朋友關系,在這n個人中,存在m個朋友關系。

對于這些關系,進行q次事件,格式為【op,u,v】,其中u和v表示人的編號。op表示要進行哪種操作,當op==1時,u和v的朋友關系淡忘,也就是斷開u和v的朋友關系。當op==2時,表示查詢u和v是否可以建立朋友關系,可以通過第三方或者本來就是朋友關系。

針對每次的op==2操作,返回一個結果Yes or No,表示是否可以建立朋友關系 。

【思路】

這n個人中存在許多的朋友關系,比如編號1-5是朋友,編號6-10是朋友,這兩個關系是獨立的集合,所以可以想到的是使用并查集來記錄朋友關系。

并查集傳送門:

【算法與數據結構】并查集詳解+題目_并查集結構體-CSDN博客

?并查集中的每個集合可以看成是一棵樹,獨立多個集合,就是多個獨立的樹。每個樹的根節點也就是每個集合的父節點。


剛開始我的思路是將這m個朋友關系,使用并查集來存儲。

但是在q次操作中,op=2是查詢是否可以 建立朋友關系的操作,這個簡單,只需判斷這兩個人是否在同一個集合中,也就是這兩個人的父節點是否相同。但是對于op=1刪除朋友關系操作,比較困難,因為并查集擅于進行 添加關系操作的,不好處理刪除節點關系所以在刪除朋友關系這里出現了問題。

我們可以試著把刪除朋友關系變成添加朋友關系。這樣并查集就可以做了。那么怎么實現呢?

我們可以先將這m個朋友關系用特定的容器存儲下來,首先遍歷q次操作,遇到刪除操作(u,v),在容器中刪除(u,v)。

注意:這里刪除的時候,要刪除的朋友關系是(u,v),有可能存儲的時候,朋友關系是(u,v),也有可能是(v,u),這些都是要刪除的。

遇到op=2時,不進行操作。一次操作完成后,將該次操作用數組記錄下來【op,u,v】。


順序遍歷完后,此時將容器中剩余的朋友關系,構建并查集。?然后逆序遍歷記錄操作的數組,遇到op=1時,就添加朋友關系,遇到op=2時,就查詢朋友關系,判斷父節點是否相等即可。

?【代碼】

//小美的朋友關系
#include <iostream>
#include <vector>
#include <set>
using namespace std;
const int N = 1e5;//總人數,初始的朋友關系數,事件數量
int n, m, q;
vector<int> parent;//并查集
set<pair<int, int>> st;//存儲初始的朋友關系
//存儲事件
struct node
{int op, u, v;
}arr[N+5];
//找父節點,路徑壓縮
int find(int x)
{if (parent[x] != x)parent[x] = find(parent[x]);return parent[x];
}
//合并
void unite(int x, int y)
{int rootX = find(x);int rootY = find(y);if (rootX == rootY)return;parent[rootX] = rootY;
}
int main()
{cin >> n >> m >> q;//初始化并查集parent.resize(n + 1);for (int i = 1; i <= n; i++)parent[i] = i;//存儲關系int op,u, v;while (m--){cin >> u >> v;st.insert({ u,v });}int num = 0;while (q--){cin >> op >> u >> v;//處理刪除操作if (op == 1){if (st.find({ u,v }) != st.end())st.erase({ u,v });else if (st.find({ v,u }) != st.end())st.erase({ v,u });elsecontinue;//說明u和v表示朋友關系,此次刪除操作無意義,不需要存儲下來}//記錄操作arr[num++] = { op,u,v };}//刪除關系完成后,剩余的元素是沒有進行操作的//構建并查集for (auto [u, v] : st)unite(u, v);vector<bool> ans;//記錄最終結果//逆序遍歷操作//如果是刪除就進行合并//如果是查詢就進行判斷是否在同一個集合for (int i = num - 1; i >= 0; i--){op = arr[i].op, u = arr[i].u, v = arr[i].v;if (op == 1){//合并unite(u, v);}else{//判斷ans.emplace_back(find(u) == find(v));}}for (int i = ans.size() - 1; i >= 0; i--)if (ans[i])cout << "Yes" << endl;elsecout << "No" << endl;return 0;
}

上述代碼是使用vector來實現并查集的,題目中的數據范圍n是1e9,如果使用vector,就需要開辟1e9個空間,會超出內存限制。所以這里實現并查集的時候,需要使用map來替代。存儲當前節點和它的父節點。具體原因,看下方:

初始時,每個節點的父節點就是自己本身。比如mp[1]=1。


當我們逆序遍歷時,當遇到op=2,查詢朋友關系時,給的兩個朋友編號u和v,之前可能沒初始化。比如n=10,給了3個朋友關系(1,3),(3,2),(4,6),當我們查詢的時候,可能查詢的是(5,7),這兩個節點沒有初始化,也就是mp[5]=0,mp[7]=0,可以發現這兩個節點的父節點都是0,如果直接判斷,得到的結果是可以構成朋友關系,但本質是不能構成朋友關系的。


也可以看下方代碼的初始化部分,我們只初始化了存在朋友關系的節點,其他的節點沒有初始化,他們的父節點默認就是0。如果我們開始將所有節點都初始化好,那么就會超出內存限制,那么就和使用vector一樣了,甚至占用的內存比vector還要大,所以我們不能一次性就初始還所有節點。而是當遇到一個沒初始化的節點,就初始化即可。


所以在查詢操作的時候,如果mp[u]=0,或者mp[v]=0,就把這兩個值做一下初始化mp[u]=u或者mp[v]=v,這樣在判斷的時候就不會出錯了。


而如果使用的是vector來表示并查集,是不需要考慮這個問題的,因為vector會開辟n個空間,將所有人都初始化好,父節點就是自己。而使用map來存儲,只會存儲存在朋友關系的節點,如果出現一個新的節點,需要我們自己再初始化。這也就是map不會超出內存限制而vector會超出內存限制的原因

?【代碼】

//小美的朋友關系
#include <iostream>
#include <vector>
#include <map>
#include <set>
using namespace std;
const int N = 1e5;//總人數,初始的朋友關系數,事件數量
int n, m, q;
map<int,int> parent;//并查集
set<pair<int, int>> st;//存儲初始的朋友關系//存儲事件
struct node
{int op, u, v;
}arr[N + 5];
//找父節點,路徑壓縮
int find(int x)
{if (parent[x] != x)parent[x] = find(parent[x]);return parent[x];
}
//合并
void unite(int x, int y)
{int rootX = find(x);int rootY = find(y);if (rootX == rootY)return;parent[rootX] = rootY;
}
int main()
{cin >> n >> m >> q;//初始化并查集和關系集合int op, u, v;for (int i = 0; i < m; i++){cin >> u >> v;parent[u] = u;parent[v] = v;st.insert({ u,v });}int num = 0;while (q--){cin >> op >> u >> v;//處理刪除操作if (op == 1){if (st.find({ u,v }) != st.end())st.erase({ u,v });else if (st.find({ v,u }) != st.end())st.erase({ v,u });elsecontinue;//說明u和v表示朋友關系,此次刪除操作無意義,不需要存儲下來}//記錄操作arr[num++] = { op,u,v };}//刪除關系完成后,剩余的元素是沒有進行操作的//構建并查集for (auto [u, v] : st)unite(u, v);vector<bool> ans;//記錄最終結果//逆序遍歷操作//如果是刪除就進行合并//如果是查詢就進行判斷是否在同一個集合for (int i = num - 1; i >= 0; i--){op = arr[i].op, u = arr[i].u, v = arr[i].v;if (op == 1){//合并unite(u, v);}else{//parent[u]==0,說明該節點第一次出現,初始化為uif (parent[u] == 0)parent[u] = u;if (parent[v] == 0)parent[v] = v;//判斷ans.emplace_back(find(u) == find(v));}}for (int i = ans.size() - 1; i >= 0; i--)if (ans[i])cout << "Yes" << endl;elsecout << "No" << endl;return 0;
}

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/diannao/80240.shtml
繁體地址,請注明出處:http://hk.pswp.cn/diannao/80240.shtml
英文地址,請注明出處:http://en.pswp.cn/diannao/80240.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

09-DevOps-Jenkins實現CI持續集成

前面已經把harbor搭建好了&#xff0c;也可以向harbor中推送自定義鏡像。 原計劃是在Jenkins這臺服務器上&#xff0c;完成鏡像構建&#xff0c;然后把鏡像推送的harbor倉庫中。現在改變計劃了&#xff0c;Jenkins所在的服務器&#xff08;192.168.1.10&#xff09;不負責鏡像…

Postman設置了Cookies但是請求不攜帶Cookie

1 問題說明 使用Postman工具往往要向本地服務器發送請求攜帶Cookie便于測試接口&#xff0c;但是在Send下面的Cookies選項中設置域名127.0.0.1&#xff0c;并添加Cookie&#xff0c;發現發送的請求怎么都不會攜帶Cookie&#xff1a; 通過Fiddler抓包發現并沒有Cookie&#xff1…

【unity】Vulkan模式下部分Android機型使用VideoPlayer組件播放視頻異常問題

一、問題背景 考慮到Vulkan高性能的優勢&#xff0c;項目組決定打包設置為vulkan優先&#xff0c;opengl es次之的方案&#xff1b;但由于部分低端設備或者部分模擬器對Vulkan的兼容性良莠不齊&#xff0c;導致諸如使用VideoPlayer組件無法正常播放視頻等問題頻發&#xff0c;而…

0802api設計和實戰-網絡ajax請求1-react-仿低代碼平臺項目

文章目錄 1 API設計1.1 用戶功能1.1.1 獲取用戶信息1.1.2 注冊1.1.3 登錄 1.2 問卷功能1.2.1 獲取單個問卷1.2.2 獲取問卷列表1.2.3 創建問卷1.2.4 更新問卷1.2.5 批量徹底刪除問卷1.2.6 復制問卷 1.3 小結 2 實戰2.1配置axios2.2 封裝API和測試2.3 新建問卷2.4 自定義hooks封裝…

Android Kotlin AIDL 完整實現與優化指南

本文將詳細介紹如何在Android中使用Kotlin實現AIDL&#xff08;Android Interface Definition Language&#xff09;&#xff0c;并提供多種優化方案。 一、基礎實現 1. 創建AIDL文件 在src/main/aidl/com/example/myapplication/目錄下創建&#xff1a; IMyAidlInterface.…

【數據結構】_棧和隊列相關面試題

&#x1f525; 數據結構修煉場 &#x1f525; &#x1f4a5; 棧與隊列 終極試煉 &#x1f4a5; &#x1f680; 理論已加載完畢&#xff0c;代碼之魂覺醒時刻&#xff01; ?? 是時候用實戰點燃你的算法之力了—— 「題目風暴&#xff0c;來襲&#xff01;」 &#xff08;握…

精益數據分析(8/126):從Airbnb案例看精益創業與數據驅動增長

精益數據分析&#xff08;8/126&#xff09;&#xff1a;從Airbnb案例看精益創業與數據驅動增長 大家好&#xff01;一直以來&#xff0c;我都堅信在創業和技術的領域里&#xff0c;持續學習與分享是不斷進步的關鍵。今天&#xff0c;咱們繼續深入學習《精益數據分析》&#x…

專題二十:路由策略與策略路由

一、路由策略 1.1 路由策略的概念 路由策略是通過修改路由表的路由條目來控制數據流量的可達性。即對接受和發布的路由進過濾。這種方式稱為路由策略 路由策略功能相關作用控制路由的發布可通過路由策略對所要發布的路由信息進行過濾&#xff0c;只允許發布滿足條件的路由信…

VSCode 擴展離線下載方法

學習自該文章&#xff0c;感謝作者&#xff01; 2025 年 VSCode 插件離線下載攻略&#xff1a;官方渠道一鍵獲取 - 知乎 獲取擴展關鍵信息 方法一&#xff1a;官網獲取 打開 VSCode 擴展官方網站 搜索要下載的擴展&#xff0c;以 CodeGeeX 為例&#xff0c;網址為&#xf…

一 、環境的安裝 Anaconda + Pycharm + PaddlePaddle

《從零到一實踐&#xff1a;系統性學習生成式 AI(NLP)》 一 、環境的安裝 Anaconda Pycharm PaddlePaddle 1. Anaconda 軟件安裝 Anaconda 軟件安裝有大量的教程&#xff0c;此處不在說明&#xff0c;安裝完成之后界面如下&#xff1a; 2. 創建 Anaconda 虛擬環境 Paddl…

軟考教材重點內容 信息安全工程師 第23章 云計算安全需求分析與安全保護工程

23.1.云計算基本概念 云計算就是在這樣的需求驅動下而產生的一種計算模式。云計算通過虛擬化及網絡通信技術&#xff0c;提供一種按需服務、彈性化的 IT 資源池服務平臺。云計算的主要特征如下。 1. IT 資源以服務的形式提供 IT 資源以一種服務產品的形式提供&#xff0c;滿…

藍橋杯 19. 最大比例

最大比例 原題目鏈接 題目描述 X 星球的某個大獎賽設了 M 級獎勵。每個級別的獎金是一個正整數。 并且&#xff0c;相鄰兩個級別間的比例是一個固定值&#xff0c;也就是說&#xff1a;所有級別的獎金構成一個等比數列。 例如&#xff1a; 獎金數列為 16, 24, 36, 54&…

基于 Python 的自然語言處理系列(82):Transformer Reinforcement Learning

&#x1f517; 本文所用工具&#xff1a;trl、transformers、peft、bitsandbytes &#x1f4d8; 官方文檔參考&#xff1a;https://huggingface.co/docs/trl 一、引言&#xff1a;從有監督微調到 RLHF 全流程 隨著語言大模型的發展&#xff0c;如何在大規模預訓練模型基礎上更精…

JAVA猜數小游戲

import java.util.Random; import java.util.Scanner;public class HelloWorld {public static void main(String[] args) {Random rnew Random();int luck_number r.nextInt(100)1;while (true){System.out.println("輸入猜數字");Scanner sc new Scanner(System…

GPU渲染階段介紹+Shader基礎結構實現

GPU是什么 &#xff08;CPU&#xff09;Center Processing Unit:邏輯編程 &#xff08;GPU&#xff09;Graphics Processing Unit&#xff1a;圖形處理&#xff08;矩陣運算&#xff0c;數據公式運算&#xff0c;光柵化&#xff09; 渲染管線 渲染管線也稱為渲染流水線&#x…

Spring Boot + MyBatis 動態字段更新方法

在Spring Boot和MyBatis中&#xff0c;實現動態更新不固定字段的步驟如下&#xff1a; 方法一&#xff1a;使用MyBatis動態SQL&#xff08;適合字段允許為null的場景&#xff09; 定義實體類 包含所有可能被更新的字段。 Mapper接口 定義更新方法&#xff0c;參數為實體對象&…

單例模式:確保唯一實例的設計模式

單例模式&#xff1a;確保唯一實例的設計模式 一、模式核心&#xff1a;保證類僅有一個實例并提供全局訪問點 在軟件開發中&#xff0c;有些類需要確保只有一個實例&#xff08;如系統配置類、日志管理器&#xff09;&#xff0c;避免因多個實例導致狀態混亂或資源浪費。 單…

UnoCSS原子CSS引擎-前端福音

UnoCSS是一款原子化的即時按需 CSS 引擎&#xff0c;其中沒有核心實用程序&#xff0c;所有功能都是通過預設提供的。默認情況下UnoCSS應用通過預設來實現相關功能。 UnoCSS中文文檔&#xff1a; https://www.unocss.com.cn 前有很多種原子化的框架&#xff0c;例如 Tailwind…

【Qwen2.5-VL 踩坑記錄】本地 + 海外賬號和國內賬號的 API 調用區別(阿里云百煉平臺)

API 調用 阿里云百煉平臺的海內外 API 的區別&#xff1a; 海外版&#xff1a;需要進行 API 基礎 URL 設置國內版&#xff1a;無需設置。 本人的服務器在香港&#xff0c;采用海外版的 API 時&#xff0c;需要進行如下API端點配置 / API基礎URL設置 / API客戶端配置&#xf…

C語言筆記(鵬哥)上課板書+課件匯總(結構體)-----數據結構常用

結構體 目錄&#xff1a; 1、結構體類型聲明 2、結構體變量的創建和初始化 3、結構體成員訪問操作符 4、結構體內存對齊*****&#xff08;重要指數五顆星&#xff09; 5、結構體傳參 6、結構體實現位段 一、結構體類型聲明 其實在指針中我們已經講解了一些結構體內容了&…