Global and Local Inversions

Dec 02, 2019

第26天

今天的题目是Global and Local Inversions

看上去挺复杂的题目,但是我们可以从题目中知道,输入的数组是一个 [0,1,...,N-1] 的一个排列,所以A中的元素是有限定的,

多举几个例子就可以发现如果一个排列要满足 local inversionglobal inversion 个数相同的话,必须满足:

  • A[i] == i
  • A[i] == i+1 && A[i+1] == i

所以我们就可以写出这段代码:

bool isIdealPermutation(vector<int>& A) {
    int minLimit = INT_MIN;
    for(int i = 0, size = A.size() - 1; i < size; i++) {
        if (A[i] == i) ;
        else if (A[i] == i + 1 && A[i+1] == i) {
            i++;
        } else return false;
    }
    return true;
}
LeetCodeLeetCode

Longest Palindromic Subsequence

Insert into a binary search tree

comments powered by Disqus