1. 按既定顺序创建目标数组

给你两个整数数组 nums 和 index。你需要按照以下规则创建目标数组：

目标数组 target 最初为空。
按从左到右的顺序依次读取 nums[i] 和 index[i]，在 target 数组中的下标 index[i] 处插入值 nums[i] 。
重复上一步，直到在 nums 和 index 中都没有要读取的元素。
请你返回目标数组。

题目保证数字插入位置总是存在。

示例：
输入：nums = [0,1,2,3,4], index = [0,1,2,2,1]
输出：[0,4,1,3,2]
解释：
nums index target
0 0 [0]
1 1 [0,1]
2 2 [0,1,2]
3 2 [0,1,3,2]
4 1 [0,4,1,3,2]

class Solution {
public:
    vector<int> createTargetArray(vector<int>& nums, vector<int>& index) {
        vector<int> result(index.size(),0);
        int f[index.size()];
        memset(f,0,sizeof(f));
        for(int i=0;i<index.size();++i){
            if(f[result[i]]==0){
                result[index[i]] = nums[i];
                f[index[i]] = 1;
            }else{
                for(int j=index.size()-1;j>index[i];--j){
                    result[j] = result[j-1];
                }
                result[index[i]] = nums[i];
            }
        }
        return result;
    }
};

代码优化
使用库方法

//代码链接：https://leetcode-cn.com/problems/create-target-array-in-the-given-order/solution/di-181chang-zhou-sai-jie-ti-bao-gao-by-time-limit/
class Solution {
public:
    vector<int> createTargetArray(vector<int>& nums, vector<int>& index) {
        vector<int> infoVec;
        for(int i = 0, n = nums.size(); i < n; i++) {
            infoVec.insert(infoVec.begin() + index[i], nums[i]);
        }
        return infoVec;
    }
};

2. 四因数

给你一个整数数组 nums，请你返回该数组中恰有四个因数的这些整数的各因数之和。

如果数组中不存在满足题意的整数，则返回 0 。

示例：
输入：nums = [21,4,7]
输出：32
解释：
21 有 4 个因数：1, 3, 7, 21
4 有 3 个因数：1, 2, 4
7 有 2 个因数：1, 7
答案仅为 21 的所有因数的和。

class Solution {
public:
    int sumFourDivisors(vector<int>& nums) {
        int result = 0;
        for(int i=0;i<nums.size();++i){
            int count = 2;
            vector<int> add;
            for(int j=2;j*j<=nums[i];++j){
                if(nums[i]%j==0){
                    if(j!=nums[i]/j){
                        count+=2;
                        add.emplace_back(j);
                        add.emplace_back(nums[i]/j);
                    }else{
                        ++count;
                        add.emplace_back(j);
                    }
                }
                if(count>4) break;
            }
            if(count==4){
                result +=1;
                result += nums[i];
                for(int j = 0;j<add.size();++j) result += add[j];
            }
        }
        return result;
    }
};

代码优化
思路上没有发现较好的解法，只是代码量能减少很多

class Solution {
public:
    int sumFourDivisors(vector<int>& nums) {
        int ans=0,i,j,k;
        for(auto c:nums)
        {
            for(i=1,j=k=0;i*i<=c;i++)if(c%i==0)
            {
                j++;
                k+=i;
                if(i*i<c)
                {
                    j++;
                    k+=c/i;
                }
            }
            if(j==4)ans+=k;
        }
        return ans;
    }
};

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

给你一个 m x n 的网格 grid。网格里的每个单元都代表一条街道。grid[i][j] 的街道可以是：

1 表示连接左单元格和右单元格的街道。
2 表示连接上单元格和下单元格的街道。
3 表示连接左单元格和下单元格的街道。
4 表示连接右单元格和下单元格的街道。
5 表示连接左单元格和上单元格的街道。
6 表示连接右单元格和上单元格的街道。

你最开始从左上角的单元格 (0,0) 开始出发，网格中的「有效路径」是指从左上方的单元格 (0,0) 开始、一直到右下方的 (m-1,n-1) 结束的路径。该路径必须只沿着街道走。

注意：你不能变更街道。
如果网格中存在有效的路径，则返回 true，否则返回 false 。

示例：

将该问题转化为DFS问题

//参考代码：https://leetcode-cn.com/problems/check-if-there-is-a-valid-path-in-a-grid/solution/cdfsjie-fa-rong-yi-li-jie-dai-ma-duan-zhu-shi-duo-/
class Solution {
    int m,n,dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};//0下、1右、2上、3左
    int pipe[7][4]={{-1,-1,-1,-1},{-1,1,-1,3},{0,-1,2,-1},{-1,0,3,-1},{-1,-1,1,0},{3,2,-1,-1},{1,-1,-1,2}};
    //记录各个拼图块路径的方向，0、1、2、3代表方向，-1代表不可走。
    bool dfs(int x,int y,int dir,vector<vector<int>>& grid){//(x,y,当前方向,地图)
        if(x==m-1&&y==n-1) return 1;//到达终点
        int xx=x+dx[dir];
        int yy=y+dy[dir];//得到下一个准备走的坐标
        if(xx<0||yy<0||xx>=m||yy>=n)return 0;//越界
        int nxt=grid[xx][yy];//得到下一块拼图的编号
        if(pipe[nxt][dir]!=-1)return dfs(xx,yy,pipe[nxt][dir],grid);//如果当前方向可走，则方向改变，继续走。
        return 0;//无法走，返回0
    }
    public:
    bool hasValidPath(vector<vector<int>>& grid) {    
        m=grid.size();
        n=grid[0].size();
        int sta=grid[0][0];//起点的拼图编号
        for(int i=0;i<4;++i)//朝着四个方向都试一下
            if(pipe[sta][i]!=-1)//当前方向可以走
                if(dfs(0,0,pipe[sta][i],grid))//沿着当前方向搜索
                    return 1;//拼图都有两个方向可以走，只要沿着一个初始方向走通就可以。
        return 0;
    }
};

4. 最长快乐前缀

「快乐前缀」是在原字符串中既是非空前缀也是后缀（不包括原字符串自身）的字符串。

给你一个字符串 s，请你返回它的最长快乐前缀。

如果不存在满足题意的前缀，则返回一个空字符串。

示例：
输入：s = “level”
输出：”l”
解释：不包括 s 自己，一共有 4 个前缀（”l”, “le”, “lev”, “leve”）和 4 个后缀（”l”, “el”, “vel”, “evel”）。最长的既是前缀也是后缀的字符串是 “l” 。

自己写的代码最后超时了😭

class Solution {
public:
    string longestPrefix(string s) {
        string str = "";
        int length = 0;
        for(int i=1;i<s.size();++i){
            if(s[0]==s[i]){
                int count = 0;
                char st[s.size()+5];
                bool f = false;
                for(int j = 0;i+j<s.size();++j){
                    if(s[j]==s[i+j]){
                        ++count;
                        st[j] = s[i+j];
                        if(i+j+1==s.size()){
                            f = true;
                            break;
                        }
                    }else{
                        break;
                    }
                }
                if(count>length&&f == true){
                    str.resize(count);
                    for(int p = 0;p<count;++p) str[p] = st[p];
                    length = count;
                    if(length==s.size()-1) break;
                }
            }
        }
        return str;
    }
};

//参考代码
class Solution {
    int ne[100005];
    string ans;
public:
    string longestPrefix(string s) {
        int n=s.size(),i,j;
        for(ne[1]=j=0,i=2;i<=n;i++)
        {
            while(j&&s[j]!=s[i-1])j=ne[j];
            if(s[j]==s[i-1])j++;
            ne[i]=j;
        }
        ans.clear();
        for(i=0;i<ne[n];i++)ans+=s[i];
        return ans;
    }
};