现在网站做SEO怎么样,六枝特区建设局网站,短期网页制作培训学校,制作二维码的思维导图文章目录 剑指offerWeek1周日#xff1a;旋转数组的最小数字AC代码思路#xff1a;部分模拟 周日#xff1a;矩阵中的路径AC代码思路#xff1a; 剑指offerWeek1
周日#xff1a;旋转数组的最小数字
题目链接#xff1a;旋转数组的最小数字
把一个数组最开始的若干个… 文章目录 剑指offerWeek1周日旋转数组的最小数字AC代码思路部分模拟 周日矩阵中的路径AC代码思路 剑指offerWeek1
周日旋转数组的最小数字
题目链接旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾我们称之为数组的旋转。输入一个升序的数组的一个旋转输出旋转数组的最小元素。例如数组 {3,4,5,1,2}为 {1,2,3,4,5}的一个旋转该数组的最小值为 1数组可能包含重复项。注意数组内所含元素非负若数组大小为 0
请返回 −1数据范围
数组长度 [0,90]样例
输入nums [2, 2, 2, 0, 1]输出0AC代码
class Solution {
public:int findMin(vectorint nums) {if (nums.empty()) return -1;int k nums.size() - 1;while (k 0 nums[k] nums[0]) k -- ;if (nums[k] nums[0]) return nums[0];int l 0, r k;while (l r){int mid l r 1;if (nums[mid] nums[0]) r mid;else l mid 1;}return nums[l];}
};思路
整体思路
题目提到了升序满足二分条件则可以使用二分来解先在脑子里设想一个反比例函数分别位于第二、四象限
答案位于第四象限
然后在反比例函数中随即选取一个值记作x将这个值x和反比例函数第一个数值记作t对比
如果x大于t说明x位于第二象限里因此比x小的数值都舍弃
如果x小于t说明x位于第四象限因此比x大的都舍弃特别的样例不一定是一个完美的反比例函数也就是说第四象限的数据可能和反比例函数第一个值相等要先处理一下部分模拟
样例{3,4,5,1,2}
分为两组3 4 5和1 2
l 0, r 4, mid 2 nums[mid] 5这里记作xnums[5]太长了x 3因此x之前的数值都舍去包括x自身l mid 1;此时数组只剩下1 2l 3, r 4, mid 3, x 1命中
周日矩阵中的路径
题目链接旋转数组的最小数字
请设计一个函数用来判断在一个矩阵中是否存在一条路径包含的字符按访问顺序连在一起恰好为给定字符串。路径可以从矩阵中的任意一个格子开始每一步可以在矩阵中向左向右向上向下移动一个格子。如果一条路径经过了矩阵中的某一个格子则之后不能再次进入这个格子。注意输入的路径字符串不为空
所有出现的字符均为大写英文字母
数据范围
矩阵中元素的总个数 [0,900]路径字符串的总长度 [1,900]样例
matrix
[[A,B,C,E],[S,F,C,S],[A,D,E,E]
]strBCCE , return true strASAE , return falseAC代码
class Solution {
public:bool hasPath(vectorvectorchar matrix, string str) {for (int i 0; i matrix.size(); i )for (int j 0; j matrix[i].size(); j )if (dfs(matrix, str, 0, i, j))return true;return false;}bool dfs(auto matrix, auto str, int u, int x, int y){if (matrix[x][y] ! str[u]) return false;if (u str.size() - 1) return true;int dx[4] {-1, 0, 1, 0}, dy[4] {0, 1, 0, -1};auto t matrix[x][y];matrix[x][y] %;for (int i 0; i 4; i ){int a x dx[i], b y dy[i];if (a 0 b 0 a matrix.size() b matrix[a].size())if (dfs(matrix, str, u 1, a, b)) return true;}matrix[x][y] t;return false;}
};思路
整体思路
路径匹配一眼DFSDFS五步走
- 判断是否走过
- 判断是否是终点
- - 标记走过
- 按照算法走下一步
- 恢复
