生命游戏

问题描述:

根据百度百科,生命游戏,简称为生命,是英国数学家约翰·何顿·康威在1970年发明的细胞自动机。

给定一个包含 m × n 个格子的面板,每一个格子都可以看成是一个细胞。每个细胞具有一个初始状态 live(1)即为活细胞, 或 dead(0)即为死细胞。每个细胞与其八个相邻位置(水平,垂直,对角线)的细胞都遵循以下四条生存定律:

如果活细胞周围八个位置的活细胞数少于两个,则该位置活细胞死亡;
如果活细胞周围八个位置有两个或三个活细胞,则该位置活细胞仍然存活;
如果活细胞周围八个位置有超过三个活细胞,则该位置活细胞死亡;
如果死细胞周围正好有三个活细胞,则该位置死细胞复活;
根据当前状态,写一个函数来计算面板上细胞的下一个(一次更新后的)状态。下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的,其中细胞的出生和死亡是同时发生的。

示例:
输入:
[
  [0,1,0],
  [0,0,1],
  [1,1,1],
  [0,0,0]
]
输出:
[
  [0,0,0],
  [1,0,1],
  [0,1,1],
  [0,1,0]
]
进阶:
你可以使用原地算法解决本题吗?请注意,面板上所有格子需要同时被更新:你不能先更新某些格子,然后使用它们的更新后的值再更新其他格子。
本题中,我们使用二维数组来表示面板。原则上,面板是无限的,但当活细胞侵占了面板边界时会造成问题。你将如何解决这些问题?

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/game-of-life

思路:

题解:

螺旋矩阵

问题描述

给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素。

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

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/spiral-matrix

思路

变量说明:
vector <int> ret 为最后返回的结果,u为螺旋矩阵按照顺时针旋转时开始的上边界,d为下边界,l为左边界,r为右边界

按照顺时针旋转的顺序,向右:i从l到r,ret.push_back(matrixu),重新定义上边界,u++,如果u>d,跳出循环;向下:i从u到d, ret.push_back(matrixi),重新定义右边界,r--,如果r>l,跳出循环;向左:i从r到l,ret.push_back(matrixd),重新定义下边界,d--,如果u>d,跳出循环;向上:i从d到u,ret.push_back(matrixi),重新定义左边界,l++,如果r>l,跳出循环。

题解

class Solution {,
public:
    vector<int> spiralOrder(vector<vector<int>> &matrix) {
        vector<int> ret;
        int n = matrix.size();
        if (n == 0) return ret;
        int u, d, l, r;
        u = 0;
        l = 0;
        d = n - 1;
        r = matrix[0].size() - 1;
        while (true) {
            for (int i = l; i <= r; i++) {
                ret.push_back(matrix[u][i]);
            }
            u++;
            if(u>d) break;
            for(int i=u;i<=d;i++){
                ret.push_back(matrix[i][r]);
            }
            r--;
            if(r<l) break;
            for(int i=r;i>=l;i--){
                ret.push_back(matrix[d][i]);
            }
            d--;
            if(d<u) break;
            for(int i=d;i>=u;i--){
                ret.push_back(matrix[i][l]);
            }
            l++;
            if(l>r) break;
        }
        return  ret;
    }
};

螺旋矩阵 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<int>> ret,在存进ret之前要先存入vector<int> 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;
    }
};