👉引言
| 铭记于心 | ||
| 🎉✨🎉我唯一知道的，便是我一无所知🎉✨🎉 |
💖 ❄️我们的算法之路❄️💖
众所周知，作为一名合格的程序员，算法 能力 是不可获缺的，并且在算法学习的过程中我们总是能感受到算法的✨魅力✨。
☀️🌟短短几行代码，凝聚无数前人智慧；一个普通循环，即是解题之眼🌟☀️
💝二分，💝贪心，💝并查集，💝二叉树，💝图论，💝深度优先搜索(dfs) ，💝宽度优先搜索（bfs） ，💝数论，💝动态规划等等， 路漫漫其修远兮，吾将上下而求索！ 希望在此集训中与大家共同进步，有所收获！！！🎉🎉🎉
今日主题：字符串
👉⭐️第一题💎
✨题目
✨思路：
简单的字符串模拟题，简单来说就是翻转前K个字符,前后指针边向中间遍历边交换,可以自定义一个swap(),对于C++来说可以直接用STL的reverse函数
✨代码：
class Solution { public String reverseStr(String s, int k) { char[] cs = s.toCharArray(); int n = s.length(); for (int l = 0; l < n; l = l + 2 * k) { int r = l + k - 1; reverse(cs, l, Math.min(r, n - 1)); } return String.valueOf(cs); } void reverse(char[] cs, int l, int r) { while (l < r) { char c = cs[l]; cs[l] = cs[r]; cs[r] = c; l++; r--; } } }
👉⭐️第二题💎
✨题目
✨思路：
数字字符串都是等长的，把索引拼接到数据上。比较大小时,传入。nums[0].length()-queries[i][1]就是从截取位置之后开始比较。这样好处是在不稳定的排序中后面拼接的索引确保了，每一个数据的唯一性，所以即使不稳定，它也可以正确的找出第k小。这就为选用选择排序铺平了道路。这里我们选择归并排序。
✨代码：
class Solution { public: vector<int> smallestTrimmedNumbers(vector<string> &nums, vector<vector<int>> &queries) { vector<int> ans(queries.size()); int n = nums.size(), m = nums[0].length(); int idx[n]; for (int i = 0; i < queries.size(); ++i) { auto &q = queries[i]; iota(idx, idx + n, 0); stable_sort(idx, idx + n, [&](int a, int b) { auto &s = nums[a], &t = nums[b]; for (int j = m - q[1]; j < m; ++j) if (s[j] != t[j]) return s[j] < t[j]; return false; }); ans[i] = idx[q[0] - 1]; } return ans; } };
👉⭐️第三题💎
✨题目
✨思路：
用两个栈模拟光标的移动,右边的栈，下标顺序是逆序的，这样，往右边放入或取字符时，才可以直接在栈顶位置进行操作,左边的栈顶位置，记得补充一个结束符，这样，在光标左移、右移的操作过程中，需要返回左侧至多10个字符时，可以直接返回子字符串的开始下标，到结束符为止即可输出
✨代码：
#define MAX_STACKSIZE 800000 #define ATMOST_LENGTH 10 #define MIN_VALUE(x, y) (((x) < (y)) ? (x) : (y)) /* leftSize表示左侧栈已用空间，left表示左侧栈，rightSize表示右侧栈已用空间，right表示右侧栈。 */ typedef struct { int leftSize; int rightSize; char *left; char *right; } TextEditor; /* 创建对象，并初始化。 */ TextEditor *textEditorCreate() { TextEditor *obj = (TextEditor *)malloc(sizeof(TextEditor)); obj->leftSize = 0; obj->rightSize = 0; obj->left = (char *)malloc(sizeof(char) * MAX_STACKSIZE); obj->right = (char *)malloc(sizeof(char) * MAX_STACKSIZE); return obj; } /* 从光标所在位置开始，插入文本。 */ void textEditorAddText(TextEditor *obj, char *text) { int x = 0; /* 此时只需要操作左侧栈。 */ while('\0' != text[x]) { obj->left[obj->leftSize] = text[x]; obj->leftSize++; x++; } /* 栈顶位置用结束符补充。 */ obj->left[obj->leftSize] = '\0'; return; } /* 删除k个字符。 */ int textEditorDeleteText(TextEditor *obj, int k) { /* 左侧栈不足k个时，全部删光。 */ int x = MIN_VALUE(obj->leftSize, k); obj->leftSize -= x; /* 栈顶位置用结束符补充。 */ obj->left[obj->leftSize] = '\0'; return x; } /* 光标向左移动k次。 */ char *textEditorCursorLeft(TextEditor *obj, int k) { int index = 0; /* 每移动一次，左侧栈顶的字符就移动到右侧栈顶。 */ while(0 < k && 0 < obj->leftSize) { obj->leftSize--; obj->right[obj->rightSize] = obj->left[obj->leftSize]; obj->rightSize++; k--; } /* 栈顶位置用结束符补充。 */ obj->left[obj->leftSize] = '\0'; /* 返回左侧长度最多为10的子字符串。 */ if(ATMOST_LENGTH < obj->leftSize) { index = obj->leftSize - ATMOST_LENGTH; } return &obj->left[index]; } /* 光标向右移动k次。 */ char *textEditorCursorRight(TextEditor *obj, int k) { int index = 0; /* 每移动一次，右侧栈顶的字符就移动到左侧栈顶。 */ while(0 < k && 0 < obj->rightSize) { obj->rightSize--; obj->left[obj->leftSize] = obj->right[obj->rightSize]; obj->leftSize++; k--; } /* 栈顶位置用结束符补充。 */ obj->left[obj->leftSize] = '\0'; /* 返回左侧长度最多为10的子字符串。 */ if(ATMOST_LENGTH < obj->leftSize) { index = obj->leftSize - ATMOST_LENGTH; } return &obj->left[index]; } /* 释放对象。 */ void textEditorFree(TextEditor *obj) { free(obj->left); free(obj->right); free(obj); return; }
👉⭐️第四题💎
✨题目
✨代码：
#include<bits/stdc++.h> using namespace std; int main() { int t; cin >> t; while(t--) { int n; cin >> n; int k = 0; while((1 << (k + 1)) <= n - 1) ++k; for(int i = (1 << k) - 1; i >= 0; i--) { cout << i << ' '; } for(int i = (1 << k); i < n; i++) { cout << i << ' '; } cout << '\n'; } }
🌹写在最后💖：
相信大家对今天的集训内容的理解与以往已经有很大不同了吧，或许也感受到了算法的魅力,当然这是一定的，路漫漫其修远兮，吾将上下而求索！伙伴们，明天见！🌹🌹🌹
