全局倒置与局部倒置

问题描述：

数组 A 是 [0, 1, ..., N - 1] 的一种排列，N 是数组 A 的长度。全局倒置指的是 i,j 满足 0 <= i < j < N 并且 A[i] > A[j] ，局部倒置指的是 i 满足 0 <= i < N 并且 A[i] > A[i+1] 。
当数组 A 中全局倒置的数量等于局部倒置的数量时，返回 true 。

示例 1:
输入: A = [1,0,2]
输出: true
解释: 有 1 个全局倒置，和 1 个局部倒置。

示例 2:
输入: A = [1,2,0]
输出: false
解释: 有 2 个全局倒置，和 1 个局部倒置。

注意:
A 是 [0, 1, ..., A.length - 1] 的一种排列
A 的长度在 [1, 5000]之间
这个问题的时间限制已经减少了。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/global-and-local-inversions

思路：

当一个数字与其对应的角标偏移超过1时就会出现局部倒置与全局倒置不同。

题解：

class Solution {
public:
    bool isIdealPermutation(vector<int> &A) {
        int n = A.size();
        for (int i = 0; i < n; i++) {
            if (A[i] - i > 1 || A[i] - i < -1) {
                return false;
            }
        }
        return true;
    }
};

寻找峰值

问题描述：

峰值元素是指其值大于左右相邻值的元素。
给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。
数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞。

示例 1:
输入: nums = [1,2,3,1]
输出: 2
解释: 3 是峰值元素，你的函数应该返回其索引 2。

示例 2:
输入: nums = [1,2,1,3,5,6,4]
输出: 1 或 5
解释: 你的函数可以返回索引 1，其峰值元素为 2；
  或者返回索引 5， 其峰值元素为 6。

说明:
你的解法应该是 O(logN) 时间复杂度的。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-peak-element

思路：

首先，得到数组大小n=nums.size();
因为数组的左右两边的值都为负无穷。如果数组中只有一个数，那么，唯一的数为峰值，如果，数组中有两个数，较大的数为峰值。
当数组的个数大于等于3时，第一种情况，在除两头的中间有峰值，此时峰值的位置满足nums[i] > nums[i - 1] && nums[i] > nums[i + 1]。
另外一种情况，如果中间没有峰值，那么峰值最出现在第一个位置或者最后一个位置。只需判断nums[0]是否大于nums[1]，或者 nums[n - 1]是否大于nums[n - 2]即可。

题解：

class Solution {
public:
    int findPeakElement(vector<int> &nums) {
        int n = nums.size();
        int flag = 0;
        int location;
        if(n==1){
            location=0;
        }
        else if(n==2){
            if(nums[0]>nums[1]){
                location=0;
            } else{
                location=1;
            }
        }
        else{
            for (int i = 1; i <= n - 2; i++) {
                if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
                    flag = 1;
                    location = i;
                    break;
                }
            }
            if (flag == 0) {
                if (nums[0] > nums[1]) {
                    location = 0;
                }
                if (nums[n - 2] < nums[n - 1]) {
                    location = n - 1;
                }
            }
        }

        return location;
    }
};

移动石子直到连续 II

问题描述：

在一个长度无限的数轴上，第 i 颗石子的位置为 stones[i]。如果一颗石子的位置最小/最大，那么该石子被称作端点石子。
每个回合，你可以将一颗端点石子拿起并移动到一个未占用的位置，使得该石子不再是一颗端点石子。
值得注意的是，如果石子像 stones = [1,2,5] 这样，你将无法移动位于位置 5 的端点石子，因为无论将它移动到任何位置（例如 0 或 3），该石子都仍然会是端点石子。
当你无法进行任何移动时，即，这些石子的位置连续时，游戏结束。
要使游戏结束，你可以执行的最小和最大移动次数分别是多少？ 以长度为 2 的数组形式返回答案：answer = [minimum_moves, maximum_moves] 。

示例 1：
输入：[7,4,9]
输出：[1,2]
解释：
我们可以移动一次，4 -> 8，游戏结束。
或者，我们可以移动两次 9 -> 5，4 -> 6，游戏结束。

示例 2：
输入：[6,5,4,3,10]
输出：[2,3]
解释：
我们可以移动 3 -> 8，接着是 10 -> 7，游戏结束。
或者，我们可以移动 3 -> 7, 4 -> 8, 5 -> 9，游戏结束。
注意，我们无法进行 10 -> 2 这样的移动来结束游戏，因为这是不合要求的移动。

示例 3：
输入：[100,101,104,102,103]
输出：[0,0]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/moving-stones-until-consecutive-ii

思路：

题解：

最接近的三数之和

问题描述：

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum-closest

思路：

暴力法

题解：

class Solution {
public:
    int threeSumClosest(vector<int> &nums, int target) {
        int n = nums.size();
        int a[n + 100];
        int count = 0;
        for (vector<int>::iterator m = nums.begin(); m != nums.end(); m++) {
            a[count] = *m;
            count++;
        }
        sort(a, a + n);
        int linshi;
        int min=0x3f3f3f3f;
        int flag;
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                for (int m = j + 1; m < n; m++) {
                    linshi = (a[i] + a[j] + a[m]) - target;
                    if (linshi < 0) {
                        if (0 - linshi <= min) {
                            min = 0 - linshi;
                            flag = linshi+target;
                        }
                    } else {
                        if (linshi <= min) {
                            min = linshi;
                            flag = linshi+target;
                        }
                    }

                }
            }
        }

        return flag;
    }

};

求众数 II

问题描述

给定一个大小为 n 的数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1)。

示例 1：
输入: [3,2,3]
输出: [3]

示例 2:
输入: [1,1,1,3,3,2,2,2]
输出: [1,2]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/majority-element-ii

思路

• 基本思路是用map（之前介绍过map内部实质是pair类型的）。
• 对于map中的每一项，只要它的second值大于n/3，就将其存入返回结果ret中。

题解

class Solution {
public:
    vector<int> majorityElement(vector<int> &nums) {
        map<int, int> table;
        vector<int> ret;
        int n = nums.size();
        if (n == 0) return ret;
        for (int i = 0; i < n; i++) {
            table[nums[i]]++;
        }
        for(auto each:table){
            if(each.second>n/3) ret.push_back(each.first);
        }
        return ret;
    }
};