【笔试强训day37】
目录
第一题：旋转字符串
描述
示例1
示例2
第二题：合并k个已排序的链表
描述
示例1
示例2
第三题：滑雪
描述
示例1
第一题：旋转字符串
题目链接：旋转字符串
描述
给定两字符串A和B，如果能将A从中间某个位置分割为左右两部分字符串（可以为空串），并将左边的字符串移动到右边字符串后面组成新的字符串可以变为字符串B时返回true。
例如：如果A=‘youzan’，B=‘zanyou’，A按‘you’‘zan’切割换位后得到‘zanyou’和B相同，返回true。
再如：如果A=‘abcd’，B=‘abcd’，A切成‘abcd’和''（空串），换位后可以得到B，返回true。
数据范围：A,B字符串长度满足 𝑛≤1000n≤1000，保证字符串中仅包含小写英文字母和阿拉伯数字
进阶： 时间复杂度 𝑂(𝑛)，空间复杂度 𝑂(𝑛)
示例1
输入：
"youzan","zanyou"
返回值：
true
示例2
输入：
"youzan","zyouan"
返回值：
false
倍增字符串。倍增得到的字符串里，有字符串经过旋转后得到的字符串的所有情况，其实也就是另一种方式的暴力枚举，然后在倍增得到的字符串中查找是否有字符串B。
class Solution {
public:bool solve(string A, string B) {if (A.size() != B.size()) return false;string tmp = A + A; //倍增字符串return tmp.find(B) != -1;//找到返回起始下标，否则返回npos，也就是-1}
};第二题：合并k个已排序的链表
题目链接：合并k个已排序的链表
描述
合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。
数据范围：节点总数 0≤𝑛≤5000，每个节点的val满足 ∣𝑣𝑎𝑙∣<=1000
要求：时间复杂度 𝑂(𝑛𝑙𝑜𝑔𝑛)
示例1
输入：
[{1,2,3},{4,5,6,7}]
返回值：
{1,2,3,4,5,6,7}
示例2
输入：
[{1,2},{1,4,5},{6}]
返回值：
{1,1,2,4,5,6}
利用小堆，把所有链表的头结点全部丢到堆里边。当然也可以把所有的结点全部丢到小堆里面。
class Solution {
public:struct cmp {bool operator()(ListNode *node1, ListNode *node2) {return node1->val > node2->val;}};ListNode* mergeKLists(vector<ListNode*>& lists) {priority_queue<ListNode*, vector<ListNode*>, cmp> heap;for (auto &head : lists) {if (head != nullptr) {heap.push(head);}}ListNode *newhead = new ListNode(0);ListNode *tail = newhead;while (!heap.empty()) {ListNode *top = heap.top();heap.pop();tail->next = top;tail = top;if (top->next != nullptr) {heap.push(top->next);}}return newhead->next;}
};第三题：滑雪
题目链接：滑雪
描述
给定一个𝑛×𝑚 n×m 的矩阵，矩阵中的数字表示滑雪场各个区域的高度，你可以选择从任意一个区域出发，并滑向任意一个周边的高度严格更低的区域（周边的定义是上下左右相邻的区域）。请问整个滑雪场中最长的滑道有多长？(滑道的定义是从一个点出发的一条高度递减的路线）。
(本题和矩阵最长递增路径类似，该题是当年NOIP的一道经典题)
数据范围： 1≤𝑛,𝑚≤100 1≤n,m≤100 ，矩阵中的数字满足 1≤𝑣𝑎𝑙≤1000 1≤val≤1000
输入描述：
第一行输入两个正整数 n 和 m 表示矩阵的长宽。
后续 n 行输入中每行有 m 个正整数，表示矩阵的各个元素大小。
输出描述：
输出最长递减路线。
示例1
输入：
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
输出：
25
说明：
从25出发，每次滑向周边比当前小 1 的区域。 25->24->23->22->......->1
记忆化搜素。枚举每一个位置的最长递减路径，在枚举的过程中，发现有大量重复，所以就可以记录下来，避免重复操作。
#include <iostream>
using namespace std;int arr[110][110];//存储矩阵
int memo[110][110];//记录
int dx[4] = { 0, 0, 1, -1};
int dy[4] = { 1, -1, 0, 0};
int row, col;int dfs(int i, int j) {if (memo[i][j] != 0) return memo[i][j];int len = 1;for (int k = 0; k < 4; k++) {int x = i + dx[k], y = j + dy[k];if (x >= 0 && x < row && y >= 0 && y < col && arr[x][y] < arr[i][j]) {len = max(len, dfs(x, y) + 1);}}memo[i][j] = len;return len;
}
int main()
{cin >> row >> col;for (int i = 0; i < row; i++) {for (int j = 0; j < col; j++) {cin >> arr[i][j];}}int ans = 1;for (int i = 0; i < row; i++) {for (int j = 0; j < col; j++) {ans = max(ans, dfs(i, j));}}cout << ans << endl;return 0;
}