力扣

841.钥匙和房间

题目描述

有 N 个房间，开始时你位于 0 号房间。每个房间有不同的号码：0，1，2，...，N-1，并且房间里可能有一些钥匙能使你进入下一个房间。

在形式上，对于每个房间 i 都有一个钥匙列表 rooms[i]，每个钥匙 rooms[i][j] 由 [0,1，...，N-1] 中的一个整数表示，其中 N = rooms.length。钥匙 rooms[i][j] = v 可以打开编号为 v 的房间。

最初，除 0 号房间外的其余所有房间都被锁住。

你可以自由地在房间之间来回走动。

如果能进入每个房间返回 true，否则返回 false。

示例 1：

输入: [[1],[2],[3],[]]
输出: true
解释:
我们从 0 号房间开始，拿到钥匙 1。
之后我们去 1 号房间，拿到钥匙 2。
然后我们去 2 号房间，拿到钥匙 3。
最后我们去了 3 号房间。
由于我们能够进入每个房间，我们返回 true。
示例 2：

输入：[[1,3],[3,0,1],[2],[0]]
输出：false
解释：我们不能进入 2 号房间。
提示：

1 <= rooms.length <= 1000
0 <= rooms[i].length <= 1000
所有房间中的钥匙数量总计不超过 3000。

分析

根据题解学习，该题目为孤岛问题，若有孤岛，则返回false，若无孤岛，则返回true。而遍历过程，使用bfs与dfs均可。

bfs解法

首先，bfs是广度优先遍历，使用深度优先遍历到每个节点，并用vis来记录是否遍历过。思路是：

首先找到 0 号房间，把所有 0 号房间的钥匙都开一遍。
进入刚刚开过的房间，再把它们房间里的钥匙再开一遍。
重复以往，层层递进，直到找不到符合要求的节点。

根据大佬的解答，队列和bfs是经常一起出现的。

class Solution {
//广度优先搜索
bool bfs(const vector<vector<int>>& rooms){
    vector<int> visited(rooms.size(), 0); // 标记房间是否被访问过
    visited[0] = 1; //  0 号房间开始,遍历过，设为1
    queue<int> que; //队列作用为如果没有遍历过，则压入队列，下一次循环遍历
    que.push(0); //  0 号房间开始
     // 广度优先搜索的过程
    while (!que.empty()) {
        int key = que.front(); que.pop();
         vector<int> keys = rooms[key];
         for (int key : keys) {
             if (!visited[key]) {
                 que.push(key);
                 visited[key] = 1;
             }
         }
    }
    // 检查房间是不是都遍历过了
    for (int i : visited) {
        if (i == 0) return false;
    }
    return true;
}

public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        return bfs(rooms);
    }
};

dfs解法

dfs是深度优先搜索，同样使用vis来存储是否访问过，思路为：

先找第0个房间的第一个钥匙
进入那个房间，再找它的第一个钥匙
重复以往，直到没钥匙了，那么退回刚刚的房间
找刚刚房间的第二把钥匙

重复搜索，直到所有房间遍历完成

class Solution {
private:
  void dfs(int key, const vector<vector<int>>& rooms, vector<int>& visited) {
      if (visited[key]) {
          return;
      }//若访问过了，则返回上一层
      visited[key] = 1;//若没有访问过，则将该房间的vis变为1
      vector<int> keys = rooms[key];//该房间里的钥匙能打开哪些锁
      for (int key : keys) {
          // 深度优先搜索遍历
          dfs(key, rooms, visited);//递归方式将可访问到的房间位置变为1
      }
  }
public:
  bool canVisitAllRooms(vector<vector<int>>& rooms) {
      vector<int> visited(rooms.size(), 0);
      dfs(0, rooms, visited);
      //检查是否都访问到了
      for (int i : visited) {
          if (i == 0) return false;//如果有0，则为孤岛
      }
      return true;//遍历后没有0，则都可以进入
  }
};

4、寻找两个有序数组的中位数

题目描述

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。

请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0
示例 2:

nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

分析

因为规定了时间复杂度，所以合并后取值不可用（时间复杂度为O(M+N)），所以使用二分查找，是奇数则取中间值，是偶数则取中间两个数和的二分之一。
题解中的图：图片说明

二分查找法

class Solution {
public:
int getKthElement(const vector<int>& nums1, const vector<int>& nums2, int k) {
        /* 主要思路：要找到第 k (k>1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较
         * 这里的 "/" 表示整除
         * nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个
         * nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个
         * 取 pivot = min(pivot1, pivot2)，两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个
         * 这样 pivot 本身最大也只能是第 k-1 小的元素
         * 如果 pivot = pivot1，那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums1 数组
         * 如果 pivot = pivot2，那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums2 数组
         * 由于我们 "删除" 了一些元素（这些元素都比第 k 小的元素要小），因此需要修改 k 的值，减去删除的数的个数
         */

        int m = nums1.size();
        int n = nums2.size();
        int index1 = 0, index2 = 0;

        while (true) {
            // 边界情况
            if (index1 == m) {
                return nums2[index2 + k - 1];
            }
            if (index2 == n) {
                return nums1[index1 + k - 1];
            }
            if (k == 1) {
                return min(nums1[index1], nums2[index2]);
            }

            // 正常情况
            int newIndex1 = min(index1 + k / 2 - 1, m - 1);
            int newIndex2 = min(index2 + k / 2 - 1, n - 1);
            int pivot1 = nums1[newIndex1];
            int pivot2 = nums2[newIndex2];
            if (pivot1 <= pivot2) {
                k -= newIndex1 - index1 + 1;
                index1 = newIndex1 + 1;
            }
            else {
                k -= newIndex2 - index2 + 1;
                index2 = newIndex2 + 1;
            }
        }
    }
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int totalLength = nums1.size() + nums2.size();
        if (totalLength % 2 == 1) {//如果是奇数
            return getKthElement(nums1, nums2, (totalLength + 1) / 2);
        }
        else {//如果是偶数
            return (getKthElement(nums1, nums2, totalLength / 2) + getKthElement(nums1, nums2, totalLength / 2 + 1)) / 2.0;
        }
    }
};

贪心算法（12、整数转罗马数字）

题目描述：

罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。

字符数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如，罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。

示例 1:

输入: 3
输出: "III"
示例 2:

输入: 4
输出: "IV"
示例 3:

输入: 9
输出: "IX"
示例 4:

输入: 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.
示例 5:

输入: 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.

贪心算法分析

贪心：每次先考虑最大的数，确定了最大的数，减去以后，再考虑后面的数字。例如58，先考虑50--L，再考虑5--V，最后是3---III，所以58为LVIII。

程序

//建立哈希表，对应数字来查找
class Solution {
public:
    string intToRoman(int num) {
        //建立哈希表
        int values[] = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
        string romas[] = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
        //遍历哈希表
        string roma;
        for(int i=0;i<13;i++){
            while(num>=values[i]){
                num -= values[i];
                roma += romas[i];
            }
        }
        return roma; 
    }
};

unordered_map的使用（13、罗马数字转整数）

题目描述

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

字符数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如，罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。

示例 1:

输入: "III"
输出: 3
示例 2:

输入: "IV"
输出: 4
示例 3:

输入: "IX"
输出: 9
示例 4:

输入: "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.

分析

使用map容器，可以将对应的键-值放入其中，再通过比较来取出即可。

程序

class Solution {
public:
    int romanToInt(string s) {
        //使用map容器比较,需要注意的是，在比较IV时，先比较了I，所以当时已经+1，故使IV对应3，即为3+1=4
        unordered_map<string,int> m = {{"I", 1}, {"IV", 3}, {"IX", 8}, {"V", 5}, {"X", 10}, {"XL", 30}, {"XC", 80}, {"L", 50}, {"C", 100}, {"CD", 300}, {"CM", 800}, {"D", 500}, {"M", 1000}};
        int ret = m[s.substr(0,1)];
        for(int i=1;i<s.size();++i){
            string two = s.substr(i-1,2);
            string one = s.substr(i,1);
            ret += (m[two]?m[two]:m[one]);
        }
        return ret;
    }
};

琐碎

链表的创建

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
ListNode * ret = new ListNode(-1); //返回的头结点

哈希表使用

在查找重复字符时，可以使用哈希表

class Solution {
public:
    int hashmap[130];//建立一张哈希表
    int lengthOfLongestSubstring(string s){
        int max=0;
        int n=s.size();
        for(int i=0,j=0;j<n;j++){
            //哈希表存储s[j]字符，哈希位置+1
            hashmap[s[j]]++;
            //当存储超过一个时，即发现重复的
            //左指针右移，移到不与s[j]位置重复的地方，并将沿途中的1变为0
            while(hashmap[s[j]]>1){
                hashmap[s[i++]]--;
            }
            //如果中间的长度>max，则将max重新赋值
            if(j-i+1>max){
                max=j-i+1;
            }
        }
        return max;
    }
};

二分查找

如果对时间复杂度有log的要求，一般都可以用二分查找

关于数字转换问题

判断是不是数字

isdigit()函数
字符c,(c>='0' && c<='9')

将字符变为数字

例如，char c = '4',若变为整数 int a = c-'0'即可
使用atoi或者stoi函数，不顾需要注意的是，atoi不会范围检查，超过上限就输出上限，超过下限就输出下限；stoi会做范围检查，超过就报错，而且使用时，格式为
```
string s = "123";
int a = atoi(s.c_str());
```

将数字变为字符串

使用itoa函数

int a = "123";
char str[25];
itoa(a,str,10);//转换

使用to_string函数
```
int a = 123;
string str = to_string(a);
```

int的范围
INT_MIN(−2^31=-2147483648)~INT_MAX(2^31=2147483647)

二、题目分析-力扣

力扣

841.钥匙和房间

题目描述

分析

bfs解法

dfs解法

4、寻找两个有序数组的中位数

题目描述

分析

二分查找法

贪心算法（12、整数转罗马数字）

题目描述：

贪心算法分析

程序

unordered_map的使用（13、罗马数字转整数）

题目描述

分析

程序

琐碎

链表的创建

哈希表使用

二分查找

关于数字转换问题