当前位置:   article > 正文

卡码网训练(ACM模式)-代码随想录

卡码网

一.数组

卡码网33.逛街

思路一:

                1.先将输入字符转换为int数组
                2.使用栈从0遍历数组,保存第i位之前可以连续降序的数值
                3.使用栈从n-1遍历数组,保存第i位之后可以连续降序的数值
                4.及时更新第i个位置前后存在的到达i之前连续降序的数值个数
  1. #include <iostream>
  2. #include <vector>
  3. #include <sstream>
  4. #include <stack>
  5. #include <algorithm>
  6. using namespace std;
  7. vector<int> parseIntArray(string input) {//获取高度数组
  8. vector<int> parsedArray;
  9. stringstream ss(input.substr(1, input.length() - 2));//使用字符串流stringstream处理输入字符串,并把头尾的括号去掉
  10. string item;
  11. while (getline(ss, item, ',')) {//使用getline从stringstream中按逗号分割获取每个字符串元素
  12. parsedArray.push_back(std::stoi(item));//将字符串元素转为数字
  13. }
  14. return parsedArray;
  15. }
  16. void calculateVisibleCounts(const vector<int>& heights, vector<int>& visibleCounts) {
  17. int n = heights.size();
  18. stack<int> stack1, stack2;
  19. for (int i = 0; i < n; i++) {//从左往右找(相当于看第i位左边符合条件的)
  20. visibleCounts[i] += stack1.size();//降序排列的数值,就是从当前位置起栈里的都能看到,当前位置的初始化已经加上
  21. while (!stack1.empty() && stack1.top() <= heights[i]) {//第i位元素是否大于等于前面的元素时,把前面的元素弹出
  22. stack1.pop(); //直到找到一个比当前元素大的值,或者栈空
  23. } //使得栈中的元素全是按降序排列的(从底到顶)
  24. stack1.push(heights[i]);//把当前位置加入
  25. }
  26. for (int i = n - 1; i >= 0; i--) {//从右往左找(相当于看第i位右边符合条件的
  27. visibleCounts[i] += stack2.size();//同理把从右往左能看到的都加上
  28. while (!stack2.empty() && stack2.top() <= heights[i]) {//等于的时候也要弹出,因为等于也看不见
  29. stack2.pop();//也是形成降序排列
  30. }
  31. stack2.push(heights[i]);
  32. }
  33. }
  34. int main() {
  35. string buildings;
  36. while(getline(cin, buildings)){
  37. vector<int> heights = parseIntArray(buildings);
  38. int n = heights.size();
  39. vector<int> visibleCounts(n, 1);//初始化都为1,因为在第i个位置上,必然能看到第i个位置
  40. calculateVisibleCounts(heights, visibleCounts);
  41. cout << "[";
  42. for (int i = 0; i < n; i++) {
  43. cout << visibleCounts[i];
  44. if (i < n - 1)
  45. cout << ",";
  46. }
  47. cout << "]" <<endl;
  48. }
  49. // 输出可见建筑物数量
  50. return 0;
  51. }

卡码网13.镂空三角形

思路:根据题意,可以把结果分成四个部分
                1.打印空格(空格的数量是递减的,且最后一行不需要)
                2.打印字符(相当于左侧字符,前n-1行都只需打印一个,最后一行需打印n个)
                3.打印空格(属于中间空格,发现符合2*i-1的规律递增,最后一行无需打印)
                4.打印字符(相当于右侧字符,第一行无需打印,2到n-1行打印一个,最后一行打印n-1个
  1. #include<iostream>
  2. #include<sstream>
  3. using namespace std;
  4. int main() {
  5. string str;
  6. while (getline(cin, str)) {
  7. stringstream ss(str);
  8. char midC;
  9. int midI;
  10. ss >> midC;
  11. if (midC == '@')
  12. break;
  13. ss >> midI;
  14. for (int i = 0; i < midI; i++) {
  15. //打印空格
  16. int midP = midI - i-1;
  17. while (midP--)
  18. cout << ' ';
  19. //打印字符
  20. int midS = midI;
  21. if (i != midI - 1)
  22. cout << midC;
  23. else {
  24. while (midS--)
  25. cout << midC;
  26. }
  27. //打印空格
  28. if (i != midI - 1 && i!=0) {
  29. int midC1 = 2 * i-1 ;
  30. while (midC1--)
  31. cout << ' ';
  32. }
  33. //打印字符
  34. if (i == 0) {
  35. cout << endl;
  36. continue;
  37. }
  38. int midC2 = midI;
  39. if (i != midI - 1)
  40. cout << midC;
  41. else {
  42. midC2--;
  43. while (midC2--)
  44. cout << midC;
  45. }
  46. cout << endl;
  47. }
  48. cout << endl;
  49. }
  50. return 0;
  51. }

 二.字符串

卡码网14.句子缩写

思路一:直接使用字符串流接收数据,然后赋给string
注意:使用cin获取n之后需要使用getchar() 吸收一个回车,因为第一行只需要一个n
  1. #include<iostream>
  2. #include<sstream>
  3. using namespace std;
  4. int main() {
  5. int n;
  6. cin>>n;
  7. getchar();
  8. string str;
  9. while (n--) {
  10. getline(cin, str);
  11. string res;
  12. stringstream ss(str);
  13. string mid;
  14. while (ss >> mid) {
  15. //大写字母65-90 小写字母97-122
  16. if (mid[0] - 'a' >= 0)//为小写字母
  17. res.push_back(mid[0] - 32);
  18. else
  19. res.push_back(mid[0]);
  20. }
  21. cout << res << endl;
  22. }
  23. return 0;
  24. }

卡玛网15.神秘字符

思路:使用双指针把第一个字符的后半部分往后移,腾出第二个字符的位置
  1. #include<iostream>
  2. using namespace std;
  3. string displayString(string& first,string& second){
  4. int lenF=first.size();
  5. int lenS=second.size();
  6. first.resize(lenF+lenS);
  7. int left=lenF-1,right=lenF+lenS-1;//相当于把后一半的字符移动到后面,腾出second的位置
  8. while(left>=(lenF/2)){
  9. first[right--]=first[left--];
  10. }
  11. for(auto it:second){
  12. first[++left]=it;
  13. }
  14. return first;
  15. }
  16. int main(){
  17. int n;
  18. cin>>n;
  19. getchar();
  20. while(n--){
  21. string fisrt;
  22. getline(cin,fisrt);
  23. string second;
  24. getline(cin,second);
  25. cout<<displayString(fisrt,second)<<endl;
  26. }
  27. return 0;
  28. }

卡码网16.位置交换

思路:简单的奇偶交换,使用双指针指向,然后每次递增2
  1. #include<iostream>
  2. using namespace std;
  3. int main(){
  4. int n;
  5. cin>>n;
  6. getchar();
  7. while(n--){
  8. string str;
  9. getline(cin,str);
  10. int i=0,j=1;
  11. while(i<str.size()-1 && j<str.size()){
  12. char temp=str[i];
  13. str[i]=str[j];
  14. str[j]=temp;
  15. i+=2;
  16. j+=2;
  17. }
  18. cout<<str<<endl;
  19. }
  20. return 0;
  21. }

三.栈和队列

卡码网17.出栈合法性

思路:
遍历每一个出栈的数字,遍历到i时,就判断栈中是否入栈到i。
1.还没有入栈到i,先入栈到i,此时出栈合法
2.已经入栈到i后面,判断栈顶元素是否等于出栈元素
  • 等于时出栈合法
  • 不等于时出栈不合法
  1. #include<iostream>
  2. #include<stack>
  3. #include<sstream>
  4. using namespace std;
  5. int main() {
  6. int n;
  7. while (cin >> n) {
  8. if (n == 0)
  9. break;
  10. getchar();//换到下一行
  11. string str;
  12. getline(cin, str);
  13. stringstream ss(str);
  14. int outNum, intNum = 1;//出栈和入栈下标
  15. stack<int> st;
  16. bool judge = true;//判断是否出栈成功
  17. while (ss >> outNum) {
  18. //cout << outNum << endl;
  19. while (outNum >= intNum) {
  20. st.push(intNum++);
  21. }
  22. //出栈
  23. //cout << st.top() << endl;
  24. if (st.top() == outNum)//当前元素可以出栈成功
  25. st.pop();
  26. else {//当前元素无法出栈
  27. judge = false;
  28. break;
  29. }
  30. }
  31. if (!judge)
  32. cout << "No" << endl;
  33. else
  34. cout << "Yes" << endl;
  35. }
  36. return 0;
  37. }

四.链表

卡码网18.链表的基本操作

问题:本地编译器和运行都没问题,但是提交之后(show和delete)会多出空格

  1. #include<iostream>
  2. #include<string>
  3. #include<sstream>
  4. #include<vector>
  5. #include<stack>
  6. using namespace std;
  7. struct TreeNode {
  8. int val;
  9. TreeNode* next;
  10. TreeNode() {
  11. val = 0;
  12. next = nullptr;
  13. }
  14. TreeNode(int _val) {
  15. val = _val;
  16. next = nullptr;
  17. }
  18. };
  19. TreeNode* newRoot = new TreeNode();
  20. int List_size = 0;
  21. string get(TreeNode* root, int index) {//获取指定位置元素
  22. if (index > List_size)
  23. return "get fail";
  24. TreeNode* cur = root;
  25. while (--index) {
  26. if (cur->next)
  27. cur = cur->next;
  28. else
  29. return "get fail";
  30. }
  31. return to_string(cur->val);
  32. }
  33. TreeNode* insert(TreeNode* root, int index, int val) {//在指定位置之前插入元素
  34. if (index == 1) {
  35. TreeNode* node = new TreeNode(val);
  36. node->next = newRoot->next;
  37. newRoot->next = node;
  38. cout << "insert OK";
  39. List_size++;
  40. return node;
  41. }
  42. if (index <= 0 || index > List_size) {
  43. cout << "insert fail";
  44. return root;
  45. }
  46. TreeNode* node = new TreeNode(val);
  47. TreeNode* pre = newRoot, * cur = root;
  48. while (--index) {
  49. if (cur->next) {
  50. pre = cur;
  51. cur = cur->next;
  52. }
  53. else {
  54. cout << "insert fail";
  55. return root;
  56. }
  57. }
  58. node->next = pre->next;
  59. pre->next = node;
  60. cout << "insert OK";
  61. List_size++;
  62. return newRoot->next;
  63. }
  64. TreeNode* deleteNode(TreeNode* root, int index) {//删除指定位置的元素
  65. if (index <= 0 || index > List_size) {
  66. cout << "delete fail";
  67. return root;
  68. }
  69. TreeNode* pre = newRoot, * cur = root;
  70. while (--index) {
  71. if (cur->next) {
  72. pre = cur;
  73. cur = cur->next;
  74. }
  75. else {
  76. cout << "delete fail";
  77. return root;
  78. }
  79. }
  80. if (cur->next)
  81. pre->next = cur->next;
  82. else
  83. pre->next = nullptr;
  84. cur = nullptr;
  85. cout << "delete OK";
  86. List_size--;
  87. return newRoot->next;
  88. }
  89. void showNodes(TreeNode* root) {//打印链表中所有元素
  90. if (List_size == 0){
  91. cout << "Link list is empty";
  92. return;
  93. }
  94. TreeNode* cur = root;
  95. while (cur) {
  96. cout << cur->val;
  97. if (cur->next)
  98. cout << " ";
  99. cur = cur->next;
  100. }
  101. }
  102. int main() {
  103. TreeNode* cur = newRoot;
  104. int n, midNum;
  105. cin >> n;
  106. stack<int>st;
  107. while (n--) {//初始化链表
  108. cin >> midNum;
  109. st.push(midNum);
  110. }
  111. List_size = st.size();
  112. while (!st.empty()) {
  113. TreeNode* node = new TreeNode(st.top());
  114. st.pop();
  115. cur->next = node;
  116. cur = node;
  117. }
  118. getchar();//换行
  119. cin >> n;
  120. getchar();
  121. int index, val;
  122. while (n--) {
  123. string mid;
  124. cin >> mid;
  125. if (mid == "get")
  126. {
  127. cin >> index;
  128. cout << get(newRoot->next, index);
  129. }
  130. else if (mid == "insert")
  131. {
  132. cin >> index;
  133. cin >> val;
  134. newRoot->next = insert(newRoot->next, index, val);
  135. }
  136. else if (mid == "delete") {
  137. cin >> index;
  138. newRoot->next = deleteNode(newRoot->next, index);
  139. }
  140. else if (mid == "show") {
  141. showNodes(newRoot->next);
  142. }
  143. cout << endl;
  144. }
  145. return 0;
  146. }

卡码网19.单链表反转

思路:创建,递归反转
  1. #include<iostream>
  2. using namespace std;
  3. struct ListNode {
  4. int val;
  5. ListNode* next;
  6. ListNode() {
  7. val = 0;
  8. next = nullptr;
  9. }
  10. ListNode(int _val) {
  11. val = _val;
  12. next = nullptr;
  13. }
  14. };
  15. ListNode* newHead = new ListNode(1);
  16. ListNode* judge(ListNode* root) {
  17. if (root->next == nullptr) return root;
  18. ListNode* newRoot = judge(root->next);
  19. root->next->next = root;
  20. root->next = nullptr;
  21. return newRoot;
  22. }
  23. void display(ListNode* root) {
  24. ListNode* cur = root;
  25. while (cur) {
  26. cout << cur->val;
  27. if (cur->next)
  28. cout << " ";
  29. cur = cur->next;
  30. }
  31. }
  32. int main() {
  33. ListNode* cur = newHead;
  34. int n;
  35. while (cin >> n) {
  36. if (n == 0) {
  37. cout << "list is empty" << endl;
  38. continue;
  39. }
  40. int midNum;
  41. while (n--) {//构建链表
  42. cin >> midNum;
  43. //cout << midNum;
  44. ListNode* node = new ListNode(midNum);
  45. cur->next = node;
  46. cur = node;
  47. }
  48. ListNode* head = newHead->next;
  49. ListNode* n1 = head;
  50. newHead = nullptr;
  51. delete newHead;
  52. //display(head);
  53. head=judge(head);
  54. display(head);
  55. cout << endl;
  56. }
  57. return 0;
  58. }

20.删除重复元素

 思路:双指针

  1. #include<iostream>
  2. using namespace std;
  3. struct ListNode {
  4. int val;
  5. ListNode* next;
  6. ListNode() {
  7. val = 0;
  8. next = nullptr;
  9. }
  10. ListNode(int _val) {
  11. val = _val;
  12. next = nullptr;
  13. }
  14. };
  15. void display(ListNode* root) {
  16. ListNode* cur = root;
  17. while (cur) {
  18. cout << cur->val;
  19. if(cur->next)
  20. cout<<" ";
  21. cur = cur->next;
  22. }
  23. cout << endl;
  24. }
  25. void deleteNode(ListNode* root) {
  26. ListNode* p = root, * cur = root->next;
  27. while (cur) {
  28. if (p->val == cur->val) {
  29. if (cur->next) {
  30. p->next = cur->next;
  31. cur = p->next;
  32. }
  33. else {
  34. p->next = nullptr;
  35. cur=nullptr;
  36. }
  37. }
  38. else {
  39. p = cur;
  40. cur = cur->next;
  41. }
  42. }
  43. }
  44. int main() {
  45. int n;
  46. while (cin >> n) {
  47. if (n == 0){
  48. cout<<"list is empty";
  49. break;
  50. }
  51. ListNode* head = new ListNode(0);
  52. ListNode* pre = head;
  53. int midNum;
  54. while (n--) {//创建链表
  55. cin >> midNum;
  56. ListNode* node = new ListNode(midNum);
  57. pre->next = node;
  58. pre = node;
  59. }
  60. display(head->next);
  61. deleteNode(head);
  62. display(head->next);
  63. }
  64. return 0;
  65. }

五.二叉树 

卡码网21.构造二叉树

思路一:根据前序遍历找出中间节点,然后把两个字符串切割递归遍历
  1. #include<iostream>
  2. #include<sstream>
  3. using namespace std;
  4. struct TreeNode {
  5. char val;
  6. TreeNode* left;
  7. TreeNode* right;
  8. TreeNode() {
  9. val = 0;
  10. left = nullptr;
  11. right = nullptr;
  12. }
  13. TreeNode(int _val) {
  14. val = _val;
  15. left = nullptr;
  16. right = nullptr;
  17. }
  18. };
  19. TreeNode* buildTree(string& PreSort, string& MidSort) {
  20. if (PreSort.size() == 0) return nullptr;
  21. int midValue = PreSort[0];
  22. TreeNode* midNode = new TreeNode(midValue);//中间节点
  23. //找到中间节点下标
  24. int midIndex = 0;
  25. while (MidSort[midIndex] != midValue)
  26. midIndex++;
  27. //分割中序数组(左闭右开)
  28. string leftMidSort(MidSort.begin(), MidSort.begin() + midIndex);
  29. string rightMidSort(MidSort.begin() + midIndex + 1, MidSort.end());
  30. //分割前序数组(左闭右开)
  31. string leftPreSort(PreSort.begin() + 1, PreSort.begin() + leftMidSort.size() + 1);
  32. string rightPreSort(PreSort.begin() + leftMidSort.size() + 1, PreSort.end());
  33. midNode->left = buildTree(leftPreSort, leftMidSort);
  34. midNode->right = buildTree(rightPreSort, rightMidSort);
  35. return midNode;
  36. }
  37. void display(TreeNode* root) {
  38. if (root == nullptr) return;
  39. display(root->left);
  40. display(root->right);
  41. cout << root->val;
  42. }
  43. int main() {
  44. string str;
  45. while (getline(cin, str)) {
  46. stringstream ss(str);
  47. string PreSort, MidSort;
  48. ss >> PreSort >> MidSort;
  49. TreeNode* root = buildTree(PreSort, MidSort);
  50. display(root);
  51. cout << endl;
  52. }
  53. return 0;
  54. }

卡码网22.二叉树的遍历

思路:使用make_pair组合左右节点的下标对应的字符
  1. #include<iostream>
  2. #include<vector>
  3. #include<unordered_map>
  4. #include<sstream>
  5. using namespace std;
  6. struct TreeNode{
  7. char val;
  8. TreeNode*left;
  9. TreeNode*right;
  10. TreeNode(char _val){
  11. val=_val;
  12. left=nullptr;
  13. right=nullptr;
  14. }
  15. };
  16. //节点连接
  17. TreeNode* connectTree(unordered_map<char, pair<char, char>>& nodeMap, char rootValue){
  18. if (rootValue == '0') {
  19. return nullptr;
  20. }
  21. TreeNode* root = new TreeNode(rootValue);
  22. int leftChild = nodeMap[rootValue].first;
  23. int rightChild = nodeMap[rootValue].second;
  24. root->left = connectTree(nodeMap, leftChild);
  25. root->right =connectTree(nodeMap, rightChild);
  26. return root;
  27. }
  28. //遍历
  29. void predisplay(TreeNode*root){
  30. if(root==nullptr) return;
  31. cout<<root->val;
  32. predisplay(root->left);
  33. predisplay(root->right);
  34. }
  35. void middisplay(TreeNode*root){
  36. if(root==nullptr) return;
  37. middisplay(root->left);
  38. cout<<root->val;
  39. middisplay(root->right);
  40. }
  41. void lastdisplay(TreeNode*root){
  42. if(root==nullptr) return;
  43. lastdisplay(root->left);
  44. lastdisplay(root->right);
  45. cout<<root->val;
  46. }
  47. int main(){
  48. int n;
  49. cin >> n;
  50. unordered_map<char, pair<char, char>> nodeMap;
  51. // 先保存输入的数据
  52. vector<char> index = vector<char>(n + 1, '0'); //保存坐标
  53. vector<vector<int>> nums = vector<vector<int>>(n + 1, vector<int>(2, 0));
  54. for (int i = 1; i <= n; i++) {
  55. cin >> index[i] >> nums[i][0] >> nums[i][1];
  56. }
  57. // 生成二叉树
  58. for (int i = 1; i <= n; i++) {
  59. nodeMap[index[i]] = make_pair(index[nums[i][0]], index[nums[i][1]]);
  60. }
  61. TreeNode*root=connectTree(nodeMap, index[1]);
  62. predisplay(root);
  63. cout<<endl;
  64. middisplay(root);
  65. cout<<endl;
  66. lastdisplay(root);
  67. cout<<endl;
  68. return 0;
  69. }

卡码网23.二叉树的高度

思路一:截取区间创建二叉树,遍历二叉树获取高度
  1. #include<iostream>
  2. using namespace std;
  3. struct TreeNode {
  4. char val;
  5. TreeNode* left;
  6. TreeNode* right;
  7. TreeNode() :val(0), left(nullptr), right(nullptr) {};
  8. TreeNode(int _val) :val(_val), left(nullptr), right(nullptr) {};
  9. };
  10. TreeNode* buildTree(string& strPre, string& strMid) {
  11. if (strPre.size() == 0) return nullptr;
  12. int midValue = strPre[0];
  13. int midIndex = 0;//获取中间节点的下标
  14. while (strMid[midIndex] != midValue)
  15. midIndex++;
  16. //创建中间节点
  17. TreeNode* root = new TreeNode(midValue);
  18. if (strPre.size() == 1) return root;
  19. //分割中序
  20. string leftMid(strMid.begin(), strMid.begin() + midIndex);
  21. string rightMid(strMid.begin() + midIndex+1, strMid.end());
  22. strPre.erase(strPre.begin());
  23. //分割前序
  24. string leftPre(strPre.begin(), strPre.begin() + leftMid.size());
  25. string rightPre(strPre.begin() + leftMid.size(), strPre.end());
  26. root->left = buildTree(leftPre, leftMid);
  27. root->right = buildTree(rightPre, rightMid);
  28. return root;
  29. }
  30. int heightMax = 0;
  31. void sumheight(TreeNode* root, int height) {
  32. if (root == nullptr) return;
  33. heightMax = max(height, heightMax);
  34. sumheight(root->left, height + 1);
  35. sumheight(root->right, height + 1);
  36. }
  37. int main() {
  38. int n;
  39. while (cin >> n) {
  40. int midn = n;
  41. string strPre, strMid;
  42. char mid;
  43. while (n--) {
  44. cin >> mid;
  45. strPre.push_back(mid);
  46. }
  47. while (midn--) {
  48. cin >> mid;
  49. strMid.push_back(mid);
  50. }
  51. TreeNode* root = buildTree(strPre, strMid);
  52. sumheight(root, 1);
  53. cout << heightMax << endl;
  54. }
  55. return 0;
  56. }

本文内容由网友自发贡献,转载请注明出处:【wpsshop博客】
推荐阅读
相关标签
  

闽ICP备14008679号