leetcode 403. 田鸡过河

题目：403. 田鸡过河 - 力扣（LeetCode）
O(n^2)水题

1. class Solution {
2. public:
3.     bool canCross(vector<int>& stones) {
4.         int n = (int) stones.size();
5.         vector<vector<int>> f;
6.         f.resize(n);
7.         f[0].push_back(1);
8.         int64_t temp;
9.         for (int i = 0; i < n - 1; i++) {
10.             vector<int>& t = f[i];
11.             sort(t.begin(), t.end());
12.             int j = i + 1;
13.             for (int k = 0; k < t.size(); k++) {
14.                 if (k > 0 && t[k] == t[k - 1]) {
15.                     continue;
16.                 }
17.                 temp = stones[i];
18.                 temp += t[k];
19.                 if (temp > stones[j]) {
20.                     while (j < n - 1 && temp >= stones[j + 1]) {
21.                         j++;
22.                     }
23.                 }
24.                 if (stones[i] + t[k] == stones[j]) {
25.                     if (j == n - 1) {
26.                         return true;
27.                     }
28.                     if (t[k] > 1) {
29.                         f[j].push_back(t[k] - 1);
30.                     }
31.                     f[j].push_back(t[k]);
32.                     f[j].push_back(t[k] + 1);
33.                     continue;
34.                 }
35.             }
36.         }
37.         return false;
38.     }
39. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。