螺旋矩阵 II

问题描述：

给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

示例:
输入: 3
输出:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]

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

思路：

和上一个螺旋矩阵的思路基本是一样的，详情见 螺旋矩阵
不同的是，本题是通过循环次数n×n来控制循环的。

题解：

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        int u, d, l, r;
        u = 0;
        l = 0;
        d = n - 1;
        r = n - 1;
        int count = 1;
        vector<vector<int>> ret;
        ret.resize(n);
        for (int i = 0; i < n; i++) {
            ret[i].resize(n);
        }
        while (count <= n * n) {
            for (int i = l; i <= r; i++) {
                ret[u][i] = count;
                count++;
            }
            u++;
            for (int i = u; i <= d; i++) {
                ret[i][r] = count;
                count++;
            }
            r--;
            for (int i = r; i >= l; i--) {
                ret[d][i] = count;
                count++;
            }
            d--;
            for (int i = d; i >= u; i--) {
                ret[i][l] = count;
                count++;
            }
            l++;
        }
        return ret;
    }
};

子集

问题描述

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

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

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

思路

最后得到的结果是vector<vector> ret,在存进ret之前要先存入vector tmp;
因为nums的子集存在空集，所以，必须先在ret中存一个空的tmp；
然后，用深度优先，存入ret的顺序为：[1],[1,2],[1,2,3],到这里深度已经到底（因为每个元素只能用一次），返回到dfs的上一层，并将3弹出，3已经到达n-1即最后一个位置，所以再次返回到dfs的上一层，接下来存入[1,3],[2],[2,3],[3]

题解

class Solution {
public:
    vector<int> tmp;
    vector<vector<int>> ret;
    int n;
    int vis[100]={false};
    vector<vector<int>> subsets(vector<int>& nums) {
        n=nums.size();
        ret.push_back(tmp);
        dfs(nums,0);
        return ret;
    }
    void dfs(vector<int> &nums,int location){
        if(tmp.size()==n){
            return;
        }
        for(int i=location;i<n;i++){
            if(vis[i]== false){
                vis[i]=true;
                tmp.push_back(nums[i]);
                ret.push_back(tmp);
                dfs(nums,i+1);
                tmp.pop_back();
                vis[i]= false;
            }
        }
    }
};

按递增顺序显示卡牌

问题描述：

牌组中的每张卡牌都对应有一个唯一的整数。你可以按你想要的顺序对这套卡片进行排序。

最初，这些卡牌在牌组里是正面朝下的（即，未显示状态）。

现在，重复执行以下步骤，直到显示所有卡牌为止：

从牌组顶部抽一张牌，显示它，然后将其从牌组中移出。
如果牌组中仍有牌，则将下一张处于牌组顶部的牌放在牌组的底部。
如果仍有未显示的牌，那么返回步骤 1。否则，停止行动。
返回能以递增顺序显示卡牌的牌组顺序。

答案中的第一张牌被认为处于牌堆顶部。

输入：[17,13,11,2,3,5,7]
输出：[2,13,3,11,5,17,7]
解释：
我们得到的牌组顺序为 [17,13,11,2,3,5,7]（这个顺序不重要），然后将其重新排序。
重新排序后，牌组以 [2,13,3,11,5,17,7] 开始，其中 2 位于牌组的顶部。
我们显示 2，然后将 13 移到底部。牌组现在是 [3,11,5,17,7,13]。
我们显示 3，并将 11 移到底部。牌组现在是 [5,17,7,13,11]。
我们显示 5，然后将 17 移到底部。牌组现在是 [7,13,11,17]。
我们显示 7，并将 13 移到底部。牌组现在是 [11,17,13]。
我们显示 11，然后将 17 移到底部。牌组现在是 [13,17]。
我们展示 13，然后将 17 移到底部。牌组现在是 [17]。
我们显示 17。
由于所有卡片都是按递增顺序排列显示的，所以答案是正确的。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reveal-cards-in-increasing-order

思路：

倒推 第一步：17入队。队列为[17] 第二步：17出队，然后将17插入到队首，13入队。此时队列为[13,17] 第三步：17出队，然后将17插入到队首，11入队。此时队列为[11,17,13] 第四步：13出队，然后将13插入到队首，7入队。此时队列为 [7,13,11,17] 第五步：17出队，然后将17插入到队首，5入队。 此时队列为[5,17,7,13,11] 第六步：11出队，然后将11插入到队首，3入队。 此时队列为[3,11,5,17,7,13] 第七步：13出队，然后将13插入到队首，2入队。 此时队列为[3,11,5,17,7,13]

题解1：

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <stack>
#include <cmath>
#include <queue>

using namespace std;

class Solution {
public:
     static bool cmp(int a,int b){
        return a>b;
    }
    vector<int> deckRevealedIncreasing(vector<int> &deck) {
        int n = deck.size();
        sort(deck.begin(), deck.end(),cmp);
        int location = 0;
        queue<int> queue1;
        vector<int> ret(n);
        while (location < n) {
            if(!queue1.empty())
            {
                int a=queue1.front();
                queue1.pop();
                queue1.push(a);
            }
            queue1.push(deck[location]);
            location++;
        }
        for(int i=n-1;i>=0;i--){
            int tmp=queue1.front();
            ret[i]=tmp;
            queue1.pop();
        }
        return ret;
    }
};

int main() {
    Solution solution;
    int n;
    cin >> n;
    vector<int> tmp;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        tmp.push_back(a);
    }
    vector<int> ret;
    ret=solution.deckRevealedIncreasing(tmp);
    for(int i=0;i<n;i++){
        cout<<ret[i]<<" ";
    }
    cout<<endl;

    return 0;
}

需要注意的是：

sort(deck.begin(), deck.end(),cmp);这一步中，因为cmp是在solution类里面，所以，没有对象无法调用cmp。
解决方法是在cmp比较函数前加上static。

题解2：

class Solution {
public:
    vector<int> deckRevealedIncreasing(vector<int> &deck) {
        int n = deck.size();
        sort(deck.begin(), deck.end());
        vector<int> A(n,0);
        bool flag=true;
        int cnt=0,index=0;
        while(cnt<n)
        {
            if(A[index]==0)
            {
                if(flag) A[index]=deck[cnt++];
                flag=!flag;
            }
            index=(index+1)%n;
        }
        return A;
    }
};

三数之和

问题描述：

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
本题需要注意：1、三个元素a+b+c=0
2、vector内可能存在重复元素，但是返回结果中不允许重复

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

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

思路：

1、找到a+b+c=0的组合
首先，对vector进行排序。
三个数之中必须存在至少一个小于0的数，否则无法保证三个数的和为0；
第一个数a从0到n-2遍历（因为vector已经从大到小排序，所以必须保证a<0）；第二个数b从a的下一个位置first开始；第三个数c从n-1开始。
如果a+b+c<0,b太小，所以first向后移，first++；如果a+b+c>0,c太大，所以last向前移，last--；否则，将a、b、c插入到vec中。
在first和last移动的过程中，必须保证first<last;
2、在这过程中可能会出现重复->去重
每次在进行操作的时候只取相同的数较左边的那个(右边的相同数字，跳过即可)。

题解：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int> &nums) {
        vector<int> B;
        vector<vector<int>> A;
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int first;
        int last;
        for (int i = 0; i < n - 2 && nums[i] <= 0; i++) {
            if (i != 0 && nums[i] == nums[i - 1]) continue;
            first = i + 1;
            last = n - 1;
            while (first < last) {
                if (nums[i] + nums[first] + nums[last] > 0) {
                    last--;
                } else if (nums[i] + nums[first] + nums[last] < 0) {
                    first++;
                } else {
                    B.push_back(nums[i]);
                    B.push_back(nums[first]);
                    B.push_back(nums[last]);
                    A.push_back(B);
                    B.clear();
                    first++;
                    while (first < last && nums[first] == nums[first - 1]) {
                        first++;
                    }
                }
            }

        }
        return A;
    }
};

vector

vector和数组的区别：

相同点：
1、拥有的类型是以一样的,如int，string
2、都可以用下标直接进行操作
3、都可以用迭代器进行操作（在c++中每个容器都配有各自的迭代器）
不同点：
1、（vector）长度不固定，可以随时进行扩容
（数组）在定义的长度已经固定，如int array[100]
2、（vector）用size得到长度（因为你也不知道扩容以后是多大）
（数组）不可以获取，在定义时已经确定了长度
3、（vector）可以在末尾添加vector的元素
（数组）不能增加长度以外的元素
4、（vector）可以确定长度，节约空间
（数组）不能确定长度，必须在定义时定义一个很大的空间留给数组，造成内存的浪费
5、（vector)在给二维数组赋值的时候，vector不可以用vector43= tmp直接赋值，而要用vectorA,vector<vector>B,A.push_back()...B.pushback()进行对B的赋值。
（数组）数组可以直接用array43直接赋值

关于vector的一一丢丢内部机制

初始化(根据实际，平时会经常用到的初始化vector的方法)：
1、vector vec;
默认初始化，size为0，容器中没有元素，容量也为0，还没有分配内存空间。
2、vector vec1(vec);vector vec1=vec;
vec1的类型必须与vec的类型相同。vec1将与vec有相同的容量以及元素。
3、vector vec={1,2,3,4,8.9}
其中列表中的元素不一定必须为int类型，但必须类型相容。如int型1，2，3，4可以直接拷贝，其他类型会进行转化
4、vector vec(9);
vec中将包含9个元素，每个元素进行缺省的值进行初始化，如int的初始化是0，因此vec中是9个0；
5、vector vec(9，8)
vec中将包含9个元素，每个元素初始化为8，因此vec中是9个8；

扩容

在扩容的时候，动态申请内存，如最初始的容量是1，扩容的时候，申请1×2（即2倍）的内存空间，如果不够，再次申请2×2（即2倍）的内存空间，然后将原空间元素通过复制的方式初始化新空间，再向新空间增加元素，最后析构并释放原空间。

一些基本的常用的操作

1、插入：vec.push_back(elem)
2、删除：vec.pop_back
3、获取起始数据：vec.front()
4、获取末尾元素：vec.back()
5、得到大小：vec.size()
6、设置大小：vec.resize()
7、排序：sort(vec.begin(),vec.end())
8、去重：erase(unique(vec.begin(),vec.end()),vec.end())
9、清空：vec.clear()