第九周算法题（哈希映射，二分，Floyd算法 (含详细讲解) ）

第九周算法题

第一题

题目来源：33. 搜索旋转排序数组 - 力扣（LeetCode）

题目描述：整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., 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(vector<int>& 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] && (target<nums[l] || target>nums[mid])) {
                l = mid + 1;
                idx = 0;
                continue;
            }
            else {
                if (nums[l] <= nums[mid]) {
                    r = mid;
                    continue;
                }
            }
            if (nums[mid + 1] <= nums[r] && (target<nums[mid + 1] || target>nums[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] && (target<nums[l] || target>nums[mid])，它是判断是否有序且不在区间内，如果有序且在区间内，我们就搜索左边的区间，所以我们补上一手else，当然，在每次满足条件的情况下，记得即使break出循环哦，不然会进入到后面的判断里去。

第二题

题目来源：36. 有效的数独 - 力扣（LeetCode）

题目描述：

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 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 == 9
• board[i].length == 9
• board[i][j] 是一位数字（1-9）或者 '.'

解题代码：

class Solution {
public:
?    vector<pair<int,int>>g[10];
  bool isValidSudoku(vector<vector<char>>& board) {
?    bool ret=true;
?      for(int i=0;i<board.size();i++){
?        for(int j=0;j<board[0].size();j++){
?          if(board[i][j]=='.'){
?            continue;
?          }
?          int num=board[i][j]-'0';          
?          if(g[num].empty()){
?          g[num].push_back(make_pair(i,j));
?            continue;
?          }
?          else{
?            for(int k=0;k<g[num].size();k++){
?              if(g[num][k].first==i||g[num][k].second==j){
?                ret=false;
?                return ret;
?              }
?              int x1=i,x2=g[num][k].first,y1=j,y2=g[num][k].second;
?              if(x1/3==x2/3 && y1/3==y2/3){
?                ret=false;
?                return ret;
?              }
?            }
?            if(ret){
?            g[num].push_back(make_pair(i,j));
?            }
?          }
?        }
?      }return ret;
  }
};

解题思路：

这段代码的主要思想是使用哈希表（在这里是 g）来跟踪每个数字的位置，然后通过检查新位置是否与已存在的位置冲突来判断数独是否有效。这是一种常见的空间换时间的策略，通过使用额外的空间来减少时间复杂度。在这个问题中，时间复杂度和空间复杂度都是O(1)，因为无论数独的大小如何，我们都只检查81个单元格，且哈希表的大小也是固定的。这是一种非常高效的解决方案。

1. vector<pair<int,int>>g[10];：这是一个包含10个向量对的数组，用于存储每个数字（1-9）在数独中的位置。每个数字的所有位置都存储在一个向量对中。
2. bool isValidSudoku(vector<vector<char>>& board)：这是主函数，输入是一个二维字符向量，表示数独的布局。
3. 在主函数中，首先定义了一个布尔变量 ret，并初始化为 true。这个变量用于记录数独是否有效。
4. 然后，使用两个嵌套循环遍历数独的每个单元格。如果单元格为空（即 board[i][j]=='.'），则跳过当前循环。
5. 如果单元格不为空，则将字符转换为数字（int num=board[i][j]-'0'）。然后检查该数字是否已经在数独中出现过。
6. 如果这是数字的第一次出现（即 g[num].empty() 为 true），则将其位置添加到 g[num] 中。
7. 如果数字已经出现过，则遍历 g[num] 中的每个位置，检查当前位置是否与任何已存在的位置在同一行、同一列或同一个3x3的子方格中。如果是，则将 ret 设置为 false 并立即返回。
8. 如果当前位置与 g[num] 中的所有位置都不冲突，则将当前位置添加到 g[num] 中。
9. 在遍历完所有单元格后，返回 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

解题代码：

#include<iostream>
#include<stdio.h>
#define N 2000005
using namespace std;
int n,m,k,qb,qe;
int matrix[205][205]; 
void init(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j){
                matrix[i][j]=0;
                continue;
            }
            matrix[i][j]=N;
        }
    }
    return ;
}
void floyd_deal(){
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(i==k||j==k){
                    continue;
                }
                else{
                    matrix[i][j]=min(matrix[i][j],matrix[i][k]+matrix[k][j]);
                }
            }
        }
    }
}
int main(){
    cin>>n>>m>>k;
    init();
    int b,e,val;
    for(int i=0;i<m;i++){
        scanf("%d %d %d",&b,&e,&val);
        matrix[b][e]=min(matrix[b][e],val);
    }
    floyd_deal();
    for(int i=0;i<k;i++){
        scanf("%d %d",&qb,&qe);
        if(matrix[qb][qe]<200000) printf("%d\n",matrix[qb][qe]);
        else printf("impossible\n");
    }   
return 0;
}

解题思路：

1. 初始化：在init()函数中，我们首先将所有的路径长度设为一个非常大的数（在这里是N），然后将每个节点到自身的路径长度设为0。这是因为在开始时，我们假设所有的节点之间都没有直接的路径（或者说路径非常长），只有节点自身到自身的路径长度是0。
2. 输入数据：在main()函数中，我们首先输入节点的数量n，边的数量m，以及查询的数量k。然后，我们输入每条边的信息，包括起点b，终点e，以及这条边的长度val。我们将matrix[b][e]设为val，表示节点b到节点e的路径长度为val。
3. Floyd-Warshall算法：在floyd_deal()函数中，我们使用Floyd-Warshall算法来找出所有节点之间的最短路径。这个算法的基本思想是，对于每一个节点k，我们尝试通过k来更新所有其他节点对之间的路径长度。具体来说，对于任意的两个节点i和j，如果通过k的路径比当前的路径更短，那么我们就更新matrix[i][j]为matrix[i][k]+matrix[k][j]。
4. 查询：最后，在main()函数中，我们进行k次查询。每次查询输入两个节点qb和qe，然后输出matrix[qb][qe]，即节点qb到节点qe的最短路径长度。如果这个长度小于200000，那么我们就输出这个长度；否则，我们输出"impossible"，表示节点qb到节点qe之间没有路径。

最后详细的讲一讲floyd算法：

什么是floyd算法：

首先，有一件事值得我们肯定，至少它不是那个著名心理学家西格蒙德·弗洛伊德所提出的算法，哈哈，事实上，该算法（Floyd’s algorithm）是一种用于寻找图中所有节点之间最短路径的算法。它通过动态规划的方式来计算所有节点之间的最短路径，具体步骤如下：

1. 初始化一个二维数组来存储节点之间的距离，如果两个节点之间有直接连接，则存储它们之间的距离，否则用无穷大表示。
2. 对于每一对节点i和j，遍历所有节点k，如果从节点i到节点j经过节点k的路径比直接从i到j的路径更短，则更新节点i到节点j的距离为经过节点k的路径长度。
3. 重复以上步骤直到所有节点之间的最短路径都被计算出来。

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->3==1->2+2->3，所以我们前面说我们将当前值与(x,i)+(i,y)比较，并取最小值，这里取最小值53，即成功的记录了一次更短路。

而对于最后的询问的阶段，我们可以用o(1)的时间复杂度直接输出答案。

以上就是本周的分享，感谢您的阅读。