1389 按既定顺序创建目标数组
略
1390 四因数
题目描述:
给定一个整数数组nums,返回该数组中恰有四个因数的这些整数的各因数之和。如果数组中不存在满足题意的整数，则返回 0 。
题解：
暴力枚举即可。注意枚举因数的时候sqrt()一下就行。
AC代码：
vector<int> get(int x) { vector<int> tmp; for(int i=1;i*i<=x;i++) { int res = x/i; if(res * i == x) { tmp.push_back(res); if(res != i) tmp.push_back(i); } } return tmp; } int sumFourDivisors(vector<int>& nums) { int ans = 0; int Len = nums.size(); for(int i=0;i<Len;i++) { vector<int> tmp = get(nums[i]); if(tmp.size() == 4) { for(int j=0;j<4;j++) ans += tmp[j]; } } return ans; }
1391. 检查网格中是否存在有效路径
题目描述：
给你一个 m x n 的网格 grid。网格里的每个单元都代表一条街道。grid[i][j] 的街道可以是：
1 表示连接左单元格和右单元格的街道。
2 表示连接上单元格和下单元格的街道。
3 表示连接左单元格和下单元格的街道。
4 表示连接右单元格和下单元格的街道。
5 表示连接左单元格和上单元格的街道。
6 表示连接右单元格和上单元格的街道。
你最开始从左上角的单元格 (0,0) 开始出发，网格中的「有效路径」是指从左上方的单元格 (0,0) 开始、一直到右下方的 (m-1,n-1) 结束的路径。该路径必须只沿着街道走。如果网格中存在有效的路径，则返回 true，否则返回 false 。
题解：
规则不少，可以仿照一般迷宫题目的DFS中dir数组来设计状态。对于每个gird，需要关注的是进入该格子的方向以及出这个格子的方向。
这里设定int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; // up down left right
再根据题目的意思设定街道的状态 int street[7][2][2] = {{{-1,-1},{-1,-1}},{{3,3},{2,2}},{{1,1},{0,0}},{{3,1},{0,2}},{{0,3},{2,1}},{{3,0},{1,2}},{{1,3},{2,0}}}; //这里street[0]没有实际意义只是用来凑位置。
规则设定好之后就是一般的DFS了。
AC代码：
class Solution { public: int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; // up down left right int street[7][2][2] = {{{-1,-1},{-1,-1}},{{3,3},{2,2}},{{1,1},{0,0}},{{3,1},{0,2}},{{0,3},{2,1}},{{3,0},{1,2}},{{1,3},{2,0}}}; void dfs(int sta,int x,int y,vector<vector<int>>& grid,int n,int m) { if(flag == 1) return; int now = grid[x][y]; for(int i=0;i<2;i++) { // cout << i <<endl; int In = street[now][i][0]; int Out = street[now][i][1]; if(x == n-1 && y == m-1) { if(sta == In || sta == -1) flag = 1; } if(sta == -1 || sta == In) { int xx = x + dir[Out][0]; int yy = y + dir[Out][1]; if(xx >=0 && xx <n && yy >=0 && yy < m) { // cout << sta <<" "<< In <<" " << Out << endl; // cout << xx << " " << yy <<endl; // cout << "------" <<endl; dfs(Out,xx,yy,grid,n,m); } } } if(x == n-1 && y == m-1) return; } bool hasValidPath(vector<vector<int>>& grid) { flag = 0; int n = grid.size(); int m = grid[0].size(); // cout << n << " " << m <<endl; dfs(-1,0,0,grid,n,m); if(flag == 1) return true; return false; } private: int flag; };
1392. 最长快乐前缀
题目描述：
「快乐前缀」是在原字符串中既是 非空 前缀也是后缀（不包括原字符串自身）的字符串。给你一个字符串 s，请你返回它的 最长快乐前缀。
如果不存在满足题意的前缀，则返回一个空字符串。
题解:
em...kmp next数组裸题。一开始写的时候一直在想dp,卡了一会一拍脑袋这不是板子题么。。。
扩展：
对于求不同字符串公共前缀的情况可以用扩展kmp算法，很久没写也忘记了..留个坑以后补
AC代码：
string longestPrefix(string s) { int i,j; i=0; j=-1; int len=s.length(); string ans=""; if(len == 1) return ans; int Next[len+10]; Next[0]=-1; while(i<len && j<len) { if(j==-1 || s[i]==s[j]) Next[++i]=++j; else j=Next[j]; } int tmp_len = Next[len]; ans = s.substr(len-tmp_len,tmp_len); return ans; }
在家宅太久了，注意力专注度都有一定程度的下降，慢慢调整状态吧~