LeetCode 1389 - 1392

按既定顺序创建目标数组

 

 

给出两个数组 nums 和 index，要按规则创建 target 数组，target 数组一开始为空

注意：如果要插入的位置上有数，会把这个数往后挪，把当前位置空出来，再把要插入的数据插到当前位置上 

保证数字插入的位置总是存在的，插入数据的下标在数组中一定是存在的

开一个数组从前往后遍历 nums 和 index

①先把 target[ i ] ~ 最后 分别往后移动一位，空出 target[ i ] 上的位置

②再把nums[ i ] 插到 target [ i ] 上即可

class Solution {
public:
    vector createTargetArray(vector& nums, vector& index) {
        //定义答案
        vector target;
        //从前往后遍历整个数组
        for(int i = 0;i < nums.size();i++ ) {
            //错位之前需要先给target[i]插入一个新的位置
            target.push_back(0);
            //将target[i]以及后面的数往移动一位-> 从最后一位开始
            for(int j = target.size() - 1;j > index[i];j-- )
                target[j] = target[j - 1];
            //把num[i]插到target[i]上即可
            target[index[i]] = nums[i];
        }
        return target;
    }
};

使用 vector 数组的 api

class Solution {
public:
    vector createTargetArray(vector& nums, vector& index) {
        //定义答案
        vector target;
        //从前往后遍历整个数组
        for(int i = 0;i < nums.size();i++ ) {
            //要插入的位置:迭代器支持偏移量操作 要插入的数
            target.insert(target.begin() + index[i],nums[i]);  
         }
         return target;
    }
};

四因数

 

给出一个数组，判断数组当中有哪些数恰好包含四个因数(约数)，求出所有满足要求的数的 所有约数之和 1 + 3 + 7 + 21 == 32

如果不存在，和为 0，输出 0

判断一个数的约数个数是不是四个：如果 d 是 n 的约数，那么 n / d 也是 n 的约数

详见：第十二届蓝桥杯省赛第二场C++B组真题_菜徐鸭的博客-CSDN博客

约数都是成对出现的，只需要枚举较小的一段就可以了，枚举到 √n 即可，时间复杂度为O (√n)

d ≤ n / d → d^2 ≤ n → d ≤ √n

试除法依次枚举到 √n，判断每个数的约数个数是不是有四个，如果是的话就把所有约数相加

class Solution {
public:
    int sumFourDivisors(vector& nums) {
        int res = 0;
        //枚举所有的数判断这些数的约数个数是多少
        for(auto x:nums) {
            //总和sum 个数cnt
            int sum = 0,cnt = 0;
            for(int i = 1;i <= x/i;i++ ) {
                //满足条件说明i是x的约数
                if(x % i == 0) {
                    sum += i,cnt++;
                    //另外一个约数是x / i 另外一个约数不一样才加进来,否则会重复计算
                    //x可能是一个平方数 36 / 6 == 6 和 6匹配的约数也是6,但是作为答案6只能出现一次 需要特判
                    if(x / i != i) sum += x / i,cnt++;
                }
            }
            //满足条件
            if(cnt == 4) res +=sum;
        }
        return res;
    }
};

 检查网格中是否存在有效路径

 

 

 

 

给出 6 种街道，可以连接两个路口  

每一个格子有 4 条路，C42 = 6

Street 1形状可以连接左右两个街道

Street 3形状可以连接左边和下边的街道

能不能通过街道从左上角走到右下角？

判断从一个格子走到它旁边的格子(两个格子之间能不能互通)，需要满足两个条件：①格子本身可以往右走 ②右边的格子要和左边的格子连接起来

用DFS或者BFS把从左上角所有可以遍历到的格子都遍历一遍，注意不能重复遍历，如果能遍历到右下角的格子就输出 true，否则输出 false，这里采用DFS

判断当前格子可以走到哪些格子(能不能往上、左、下、右走)：打表，存储这六条街道连接的是哪两个入口

①是 1 说明可以走，是 0 说明不能走   

②枚举偏移量

让 i 异或 2 ( ^ 2) 可以求 i 的反方向 1 - - 3  0 - - 2

判断当前格子（x，y）沿着 第 i 个方向能不能走到（a，b）

 

class Solution {
public:
    bool hasValidPath(vector>& grid) {
        //从(0,0)开始
        return dfs(0,0,grid);
    }
    //4个方向
    int dx[4] = {-1,0,1,0},dy[4]= {0,1,0,-1};
    //6个街道 每个街道有4个数-> 表示4个方向能不能走
    int state[6][4] = {
        {0, 1, 0, 1},
        {1, 0, 1, 0},
        {0, 0, 1, 1},
        {0, 1, 1, 0},
        {1, 0, 0, 1},
        {1, 1, 0, 0},
    };
    bool dfs(int x,int y,vector>& grid) {
        //用 n 和 m 表示矩阵的长和宽|行数和列数
        int n = grid.size(),m = grid[0].size();
        //如果已经到右下角就返回true
        if(x == n - 1 && y == m - 1) return true; 
        //存储当前街道的形状
        int k = grid[x][y];
        //为了避免重复遍历需要一个判重数组-> 直接把grid数组当作判重数组 如果被遍历过了就把它赋值为0
        grid[x][y] = 0;
        //枚举4个方向看能不能走过去
        for(int i = 0;i < 4;i++) {
            //求相邻格子的下标
            int a = x + dx[i],b = y + dy[i];
            //判断是否越界 | 格子已经被走过了
            if(a < 0 || a >= n || b < 0 || b >= m || !grid[a][b]) continue;
            if(!state[k - 1][i] || !state[grid[a][b] - 1][i ^ 2]) continue;
            //当前街道满足要求
            if(dfs(a,b,grid)) return true;
        }
        return false;
    }
};

最长快乐前缀