Cao Lin's Blog.

二维vector的遍历方法与DFC遍历邻接矩阵

C++ 剑指offer
Word count: 487Reading time: 2 min
2020/04/13 Share

二维数组的遍历方法

使用auto

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<vector>

using namespace std;

int main()
{
	vector<vector<int>> vec;
	vector<int> a{ 1, 2, 3 };
	vector<int> b{ 2, 4, 5, 6 };

	vec.push_back(a);
	vec.push_back(b);
    for(auto it : vec){
		for (auto i : it){
            cout << i << endl;
		}
	}
    return 0;
}

使用iterator

1
2
3
4
5
6
7
8
9
10
vector<int>::iterator        it;
vector<vector<int>>::iterator iter;

for(iter = vec.begin(); iter != vec.end(); iter++)
    {
        for(it = (*iter).begin(); it != (*iter).end(); it++)
        {
            cout << *it << endl;
        }
    }

使用下标

1
2
3
4
5
6
7
for (i = 0; i < vec.size(); i++)
    {
        for(j = 0; j < vec[0].size(); j++)
            {
                cout << vec[i][j] << endl;
            }
    }

DFC 遍历二维邻接矩阵

题目

image-20200413141100358

解决方案

https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/solution/mian-shi-ti-12-ju-zhen-zhong-de-lu-jing-shen-du-yo/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {

        for (i = 0; i < board.size(); i++)
        {
            for (j = 0; j < board[0].size(); j++)
            {

                if (DFC(i, j, board, word)) { return true;}
            }
        }
        return false;
    }

private:
    bool DFC(int i, int j, vector<vector<char>>& board, string words)
    {
        // 查找结束条件
        if (words.length() == 0) { return true;}
        if (i >= board.size() || i < 0 || j >= board[0].size() || j < 0 || board[i][j] != word[0]) {return false;}

        // 继续查找
        char temp = board[i][j];
        board[i][j] = ' ';
        //去掉已经查询过的str
        string tempW = words.substr(1);
        //四个方向（邻接）进行查找
        bool res = DFC(i+1, j, board, tempW) || DFC(i-1, j, board, tempW)
                        || DFC(i, j+1, board, tempW) || DFC(i, j-1, board, tempW);
        board[i][j] = temp;

        return res;
    }
private:
    int i;
    int j;
};

/*
执行用时 :112 ms, 在所有 C++ 提交中击败了49.15%的用户
内存消耗 :20.7 MB, 在所有 C++ 提交中击败了100.00%的用户
*/

时间还是很长，使用substr(1)使得传入的word只是未查询的，可以省略掉一个索引记录值k，然后内存消耗少了很多很多很多，时间是原来的一半：

image-20200413141555356

Author：Cao Lin

原文链接：http://www.cao-lin.top/2020/04/13/DFC%E9%81%8D%E5%8E%86%E9%82%BB%E6%8E%A5%E7%9F%A9%E9%98%B5%E4%B8%8E%E4%BA%8C%E7%BB%B4vector%E7%9A%84%E9%81%8D%E5%8E%86%E6%96%B9%E6%B3%95/

发表日期：April 13th 2020, 2:17:22 pm

更新日期：September 20th 2020, 11:19:52 am

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 二维数组的遍历方法
    1. 1.1. 使用auto
    2. 1.2. 使用iterator
    3. 1.3. 使用下标
  2. 2. DFC 遍历二维邻接矩阵
    1. 2.1. 题目
    2. 2.2. 解决方案
Total : 11
Invalid date
2020
Invalid date
Invalid date
2020
Invalid date
2020
C++ 剑指offer python 视觉SLAM