C ++中的奇数偶跳

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个数组A。从某个起始索引开始，我们可以进行一系列跳转。系列中的位置（1、3、5，...）跳转称为奇数跳转，而系列中的位置（2、4、6，...）跳转称为偶数跳转。

现在我们可以以这种方式从索引i向前跳到索引j（i <j）-

  • 在奇数跳转中，我们可以跳转到索引j，使得A [i] <= A [j]并且A [j]是最小的可能值。当有多个这样的索引j时，我们只能跳到最小的这样的索引j。

  • 在偶数跳转中，我们可以跳转到索引j，以使A [i]> = A [j]且A [j]为最大可能值。当有多个这样的索引j时，我们只能跳到最小的这样的索引j。

  • 对于某些索引i，可能会没有合法的跳跃。

现在，从该索引开始，我们可以通过跳跃一些次数到达数组的末尾，因此将其称为好索引。

我们必须找到良好的起始索引的数量。

因此，如果输入像[10,13,12,14,15]，则输出将为2，因为从末尾可以到达的地方有两个位置索引3和4。

为了解决这个问题，我们将遵循以下步骤-

  • ret：= 1

  • n：= A的大小

  • 定义一个nextNextEqual大小为n的数组，用-1填充

  • 定义一个数组nextSmallerEqual大小为n用-1填充

  • 定义一个映射st

  • 对于初始化i：= n-1，当i> = 0时，更新（将i减1），-

    • （增加1）

    • if：=值不大于A [i]的键值对

    • nextGreaterEqual [i]：=如果(it)不是最后一个元素，则为它的值，否则为-1

    • 如果它不等于st的最后一个元素，并且第一个元素与A [i]相同，则-

    • nextSmallerEqual [i]：=如果(it)不是第一个元素，则为前一个元素的值，否则为-1

    • st [A [i]]：= i

    • 定义一个大小为nx 2的2D数组v并用false填充它

    • v [n-1，0] = v [n-1，1] = true

    • 对于初始化i：= n-2，当i> = 0时，更新（将i减1），执行-

      • （增加ret 1）

      • v [i，0]：= v [nextSmallerEqual [i]，1]

      • v [i，1]：= v [nextGreaterEqual [i]，0]

      • 如果nextGreaterEqual [i]不等于-1，则-

      • 如果nextSmallerEqual [i]不等于-1，则-

      • 如果v [i，1]不为零，则-

      • 返回ret

      让我们看下面的实现以更好地理解-

      示例

      #include <bits/stdc++.h>
      using namespace std;
      class Solution {
         public:
         int oddEvenJumps(vector<int>& A){
            int ret = 1;
            int n = A.size();
            vector<int> nextGreaterEqual(n, -1);
            vector<int> nextSmallerEqual(n, -1);
            map<int, int> st;
            for (int i = n - 1; i >= 0; i--) {
               map<int, int>::iterator it = st.lower_bound(A[i]);
               nextGreaterEqual[i] = (it != st.end()) ? it->second : -1;
               if (it != st.end() && it->first == A[i])
               it++;
               nextSmallerEqual[i] = it != st.begin() ? prev(it)->second
               : -1;
               st[A[i]] = i;
            }
            vector<vector<bool> > v(n, vector<bool>(2, false));
            v[n - 1][0] = v[n - 1][1] = true;
            for (int i = n - 2; i >= 0; i--) {
               if (nextGreaterEqual[i] != -1) {
                  v[i][1] = v[nextGreaterEqual[i]][0];
               }
               if (nextSmallerEqual[i] != -1) {
                  v[i][0] = v[nextSmallerEqual[i]][1];
               }
               if (v[i][1])
               ret++;
            }
            return ret;
         }
      };
      main(){
         Solution ob;
         vector<int> v = {10,13,12,14,15};
         cout << (ob.oddEvenJumps(v));
      }

      输入值

      {10,13,12,14,15}

      输出结果

      2

      以上是 C ++中的奇数偶跳 的全部内容， 来源链接： utcz.com/z/326866.html

      回到顶部