网站设计素材图片,c语言做网站后台,长沙好的网站建设公司排名,湖南seo优化服务第九周算法题
第一题
题目来源#xff1a;33. 搜索旋转排序数组 - 力扣#xff08;LeetCode#xff09;
题目描述#xff1a;整数数组 nums 按升序排列#xff0c;数组中的值 互不相同 。
在传递给函数之前#xff0c;nums 在预先未知的某个下标 k#xff08;0 …第九周算法题
第一题
题目来源33. 搜索旋转排序数组 - 力扣LeetCode
题目描述整数数组 nums 按升序排列数组中的值 互不相同 。
在传递给函数之前nums 在预先未知的某个下标 k0 k nums.length上进行了 旋转使数组变为 [nums[k], nums[k1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]下标 从 0 开始 计数。例如 [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target 如果 nums 中存在这个目标值 target 则返回它的下标否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1
输入nums [4,5,6,7,0,1,2], target 0
输出4解题代码
class Solution {
public:int search(vectorint nums, int target) {int r nums.size() - 1;int l 0;while (l r) {int mid l r 1;int idx -1;if (nums[l] nums[mid] (targetnums[l] || targetnums[mid])) {l mid 1;idx 0;continue;}else {if (nums[l] nums[mid]) {r mid;continue;}}if (nums[mid 1] nums[r] (targetnums[mid 1] || targetnums[r])) {r mid;idx 1;continue;}else {if (nums[mid 1] nums[r]) l mid 1;}}if (nums[l] target) return l;else return -1;}
};解题思路
本题主要的难度在于如何在O(log n) 的时间复杂度内完成本题而看到这个时间复杂度我们能自然而然地想到二分。而我们知道在一个有序数组内用二分查找是很简单的而对于本题不是一个有序的数组怎么办呢
我们观察规律可知我们把数组分为任意的两个区间对于两个区间至少有一个区间是有序的。而如果左边有序但target不在区间中或者右边有序但是target又不在右边的区间中那我们直接搜索另一半即可。注意我们判断的是nums[l] nums[mid] (targetnums[l] || targetnums[mid])它是判断是否有序且不在区间内如果有序且在区间内我们就搜索左边的区间所以我们补上一手else当然在每次满足条件的情况下记得即使break出循环哦不然会进入到后面的判断里去。
第二题
题目来源36. 有效的数独 - 力扣LeetCode
题目描述
请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。请参考示例图
注意
一个有效的数独部分已被填充不一定是可解的。只需要根据以上规则验证已经填入的数字是否有效即可。空白格用 . 表示。
示例 1 输入board
[[5,3,.,.,7,.,.,.,.]
,[6,.,.,1,9,5,.,.,.]
,[.,9,8,.,.,.,.,6,.]
,[8,.,.,.,6,.,.,.,3]
,[4,.,.,8,.,3,.,.,1]
,[7,.,.,.,2,.,.,.,6]
,[.,6,.,.,.,.,2,8,.]
,[.,.,.,4,1,9,.,.,5]
,[.,.,.,.,8,.,.,7,9]]
输出true示例 2
输入board
[[8,3,.,.,7,.,.,.,.]
,[6,.,.,1,9,5,.,.,.]
,[.,9,8,.,.,.,.,6,.]
,[8,.,.,.,6,.,.,.,3]
,[4,.,.,8,.,3,.,.,1]
,[7,.,.,.,2,.,.,.,6]
,[.,6,.,.,.,.,2,8,.]
,[.,.,.,4,1,9,.,.,5]
,[.,.,.,.,8,.,.,7,9]]
输出false
解释除了第一行的第一个数字从 5 改为 8 以外空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。提示
board.length 9board[i].length 9board[i][j] 是一位数字1-9或者 .
解题代码
class Solution {
public:
vectorpairint,intg[10];bool isValidSudoku(vectorvectorchar board) {
bool rettrue;
for(int i0;iboard.size();i){
for(int j0;jboard[0].size();j){
if(board[i][j].){
continue;
}
int numboard[i][j]-0;
if(g[num].empty()){
g[num].push_back(make_pair(i,j));
continue;
}
else{
for(int k0;kg[num].size();k){
if(g[num][k].firsti||g[num][k].secondj){
retfalse;
return ret;
}
int x1i,x2g[num][k].first,y1j,y2g[num][k].second;
if(x1/3x2/3 y1/3y2/3){
retfalse;
return ret;
}
}
if(ret){
g[num].push_back(make_pair(i,j));
}
}
}
}return ret;}
};解题思路
这段代码的主要思想是使用哈希表在这里是 g来跟踪每个数字的位置然后通过检查新位置是否与已存在的位置冲突来判断数独是否有效。这是一种常见的空间换时间的策略通过使用额外的空间来减少时间复杂度。在这个问题中时间复杂度和空间复杂度都是O(1)因为无论数独的大小如何我们都只检查81个单元格且哈希表的大小也是固定的。这是一种非常高效的解决方案。
vectorpairint,intg[10];这是一个包含10个向量对的数组用于存储每个数字1-9在数独中的位置。每个数字的所有位置都存储在一个向量对中。bool isValidSudoku(vectorvectorchar board)这是主函数输入是一个二维字符向量表示数独的布局。在主函数中首先定义了一个布尔变量 ret并初始化为 true。这个变量用于记录数独是否有效。然后使用两个嵌套循环遍历数独的每个单元格。如果单元格为空即 board[i][j].则跳过当前循环。如果单元格不为空则将字符转换为数字int numboard[i][j]-0。然后检查该数字是否已经在数独中出现过。如果这是数字的第一次出现即 g[num].empty() 为 true则将其位置添加到 g[num] 中。如果数字已经出现过则遍历 g[num] 中的每个位置检查当前位置是否与任何已存在的位置在同一行、同一列或同一个3x3的子方格中。如果是则将 ret 设置为 false 并立即返回。如果当前位置与 g[num] 中的所有位置都不冲突则将当前位置添加到 g[num] 中。在遍历完所有单元格后返回 ret。如果 ret 仍为 true则数独有效否则数独无效。
第三题
题目来源854. Floyd求最短路 - AcWing题库
题目描述
给定一个n个点 m 条边的有向图图中可能存在重边和自环边权可能为负数。
再给定 k 个询问每个询问包含两个整数 x 和 y表示查询从点 x 到点 y 的最短距离如果路径不存在则输出 impossible。
数据保证图中不存在负权回路。
输入格式
第一行包含三个整数 n,m,k。
接下来 m 行每行包含三个整数 x,y,z表示存在一条从点 x 到点 y 的有向边边长为 z。
接下来 k 行每行包含两个整数 x,y表示询问点 x 到点 y 的最短距离。
输出格式
共 k 行每行输出一个整数表示询问的结果若询问两点间不存在路径则输出 impossible。
数据范围
1≤n≤200 1≤k≤n^2 1≤m≤20000 图中涉及边长绝对值均不超过 10000。
输入样例
3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3输出样例
impossible
1解题代码
#includeiostream
#includestdio.h
#define N 2000005
using namespace std;
int n,m,k,qb,qe;
int matrix[205][205];
void init(){for(int i1;in;i){for(int j1;jn;j){if(ij){matrix[i][j]0;continue;}matrix[i][j]N;}}return ;
}
void floyd_deal(){for(int k1;kn;k){for(int i1;in;i){for(int j1;jn;j){if(ik||jk){continue;}else{matrix[i][j]min(matrix[i][j],matrix[i][k]matrix[k][j]);}}}}
}
int main(){cinnmk;init();int b,e,val;for(int i0;im;i){scanf(%d %d %d,b,e,val);matrix[b][e]min(matrix[b][e],val);}floyd_deal();for(int i0;ik;i){scanf(%d %d,qb,qe);if(matrix[qb][qe]200000) printf(%d\n,matrix[qb][qe]);else printf(impossible\n);}
return 0;
}解题思路
初始化在init()函数中我们首先将所有的路径长度设为一个非常大的数在这里是N然后将每个节点到自身的路径长度设为0。这是因为在开始时我们假设所有的节点之间都没有直接的路径或者说路径非常长只有节点自身到自身的路径长度是0。输入数据在main()函数中我们首先输入节点的数量n边的数量m以及查询的数量k。然后我们输入每条边的信息包括起点b终点e以及这条边的长度val。我们将matrix[b][e]设为val表示节点b到节点e的路径长度为val。Floyd-Warshall算法在floyd_deal()函数中我们使用Floyd-Warshall算法来找出所有节点之间的最短路径。这个算法的基本思想是对于每一个节点k我们尝试通过k来更新所有其他节点对之间的路径长度。具体来说对于任意的两个节点i和j如果通过k的路径比当前的路径更短那么我们就更新matrix[i][j]为matrix[i][k]matrix[k][j]。查询最后在main()函数中我们进行k次查询。每次查询输入两个节点qb和qe然后输出matrix[qb][qe]即节点qb到节点qe的最短路径长度。如果这个长度小于200000那么我们就输出这个长度否则我们输出impossible表示节点qb到节点qe之间没有路径。
最后详细的讲一讲floyd算法
什么是floyd算法
首先有一件事值得我们肯定至少它不是那个著名心理学家西格蒙德·弗洛伊德所提出的算法哈哈事实上该算法Floyd’s algorithm是一种用于寻找图中所有节点之间最短路径的算法。它通过动态规划的方式来计算所有节点之间的最短路径具体步骤如下
初始化一个二维数组来存储节点之间的距离如果两个节点之间有直接连接则存储它们之间的距离否则用无穷大表示。对于每一对节点i和j遍历所有节点k如果从节点i到节点j经过节点k的路径比直接从i到j的路径更短则更新节点i到节点j的距离为经过节点k的路径长度。重复以上步骤直到所有节点之间的最短路径都被计算出来。
Floyd算法的时间复杂度为O(n^3)其中n为节点的个数。它适用于有向图和无向图并且可以处理带有负权边的图。因此Floyd算法是一种非常常用的最短路径算法。
让我们再用一张图来具体看看 纯手画字丑见谅
对于初始邻接矩阵我们对他进行初始化把自身到自身的长度初始化为0把不存在的边初始化为无穷意为无法到达对于每一次录入一条边我们都要比较本次两点直接路径的长度和已有两点直接路径的长度并取最小值保存。(为了防止有些阴间测试点比如一条边多次录入值不一样的情况)这就完成了预处理阶段。
然后开始使用Floyd算法开始处理处理途径一号点到n号点的情况即循环n次对于第i次循环我们忽略行i列i的情况而对于其他节点(x,y)我们将当前值与(x,i)(i,y)比较并取最小值。如第二次循环的(1,3)它原本的值是87是1到3的直接结果根据向量的运算1-31-22-3所以我们前面说我们将当前值与(x,i)(i,y)比较并取最小值这里取最小值53即成功的记录了一次更短路。
而对于最后的询问的阶段我们可以用o(1)的时间复杂度直接输出答案。
以上就是本周的分享感谢您的阅读。
