本文主要是介绍C++笔试强训day37，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
1.旋转字符串
2.合并k个已排序的链表
3.滑雪
1.旋转字符串
链接
https://www.nowcoder.com/practice/80b6bb8797644c83bc50ac761b72981c?tpId=196&tqId=37172&ru=/exam/oj
如果 A 字符串能够旋转之后得到 B 字符串的话，在 A 字符串倍增之后的新串中，⼀定是可以找到 B 字符串的。因此，我们仅需让 A 字符串倍增，然后查找 B 字符串即可。
class Solution
{
public:bool solve(string A, string B){if (A.size() != B.size()) return false;return (A + A).find(B) != -1;}
};2.合并k个已排序的链表
链接https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6?tpId=196&tqId=37081&ru=/exam/oj
我的想法是将所有链表的值存入数组中，然后排序完后再一个一个插入回新链表。
class Solution {
public:vector<int> st;ListNode* mergeKLists(vector<ListNode*>& lists) {for (int i = 0; i < lists.size(); ++i){ListNode* tmp = lists[i];while (tmp != nullptr){st.push_back(tmp->val);tmp = tmp->next;}}sort(st.begin(), st.end());ListNode* head = new ListNode(0);ListNode* cur = head;for (int i = 0; i < st.size(); ++i){ListNode* tmp = new ListNode(st[i]);cur->next = tmp;cur = cur->next;}return head->next;}
};方法二：
建堆，将每个节点存入堆中，自动排序，然后链接起来。
class Solution
{struct cmp{bool operator()(ListNode* l1, ListNode* l2){return l1->val > l2->val;}};public:ListNode* mergeKLists(vector<ListNode*>& lists){priority_queue<ListNode*, vector<ListNode*>, cmp> heap; // ⼩根堆for (auto head : lists){if (head != nullptr){heap.push(head);}}ListNode* ret = new ListNode(0);ListNode* prev = ret;while (heap.size()){ListNode* t = heap.top();heap.pop();prev = prev->next = t;if (t->next != nullptr){heap.push(t->next);}}return ret->next;}
};3.滑雪
链接https://www.nowcoder.com/practice/36d613e0d7c84a9ba3af3ab0047a35e0?tpId=230&tqId=39760&ru=/exam/oj
DFS每个点即可，因为不确定从哪出发最好，因此每个点都出发一遍
#include <iostream>
using namespace std;const int N = 110;
int n, m;
int ret;
int arr[N][N];
bool vis[N][N];
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };bool Check(int x, int y)
{for (int i = 0; i < 4; ++i){int a = x + dx[i];int b = y + dy[i];if (a >= 1 && a <= n && b >= 1 && b <= m && !vis[a][b] && arr[x][y] > arr[a][b])return true;}return false;
}void DFS(int x, int y, int path)
{if (!Check(x, y)){ret = max(ret, path);return;}for (int i = 0; i < 4; ++i){int a = x + dx[i];int b = y + dy[i];if (a >= 1 && a <= n && b >= 1 && b <= m && !vis[a][b] && arr[x][y] > arr[a][b]){DFS(a, b, path + 1);}}
}int main() {cin >> n >> m;for (int i = 1; i <= n; ++i)for (int j = 1; j <= m; ++j)cin >> arr[i][j];for (int i = 1; i <= n; ++i)for (int j = 1; j <= m; ++j)DFS(i, j, 1);cout << ret << endl;return 0;
}递归也可以进行优化 (即记忆化搜索)：
加个备忘录：
#include <iostream>
using namespace std;
const int N = 110;
int n, m;
int arr[N][N];
int dp[N][N];
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
int dfs(int i, int j)
{if (dp[i][j]) return dp[i][j];int len = 1;for (int k = 0; k < 4; k++){int x = i + dx[k], y = j + dy[k];if (x >= 1 && x <= n && y >= 1 && y <= m && arr[x][y] < arr[i][j]){len = max(len, 1 + dfs(x, y));}}dp[i][j] = len;return len;
}
int main()
{cin >> n >> m;for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){cin >> arr[i][j];}}int ret = 1;for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){ret = max(ret, dfs(i, j));}}cout << ret << endl;return 0;
}这篇关于C++笔试强训day37的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
