目录

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;
}