欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++回溯算法深度優(yōu)先搜索舉例分析

 更新時(shí)間:2022年03月24日 16:38:15   作者:ymz123_  
回溯在迷宮搜索中使用很常見(jiàn),就是這條路走不通,然后返回前一個(gè)路口,繼續(xù)下一條路?;厮菟惴ㄕf(shuō)白了就是窮舉法,下面讓我們一起來(lái)看看回溯算法深度優(yōu)先搜索吧

撲克牌全排列

假如有編號(hào)為1~ 3的3張撲克牌和編號(hào)為1~3的3個(gè)盒子,現(xiàn)在需要將3張牌分別放到3個(gè)盒子中去,且每個(gè)盒子只能放一張牌,一共有多少種不同的放法。

解題思路:假定按照牌面值從小到大依次嘗試,即將1號(hào)牌放入第一個(gè)盒子中。按此順序繼續(xù)向后走,放完第三個(gè)盒子時(shí),手中的牌也已經(jīng)用完,再繼續(xù)往后則到了盒子的盡頭。此時(shí)一種放法已經(jīng)完成了,即這條路走到了盡頭,需要折返,重新回到上一個(gè)盒子。這里回到第三個(gè)盒子,把第三個(gè)盒子中的牌回收,再去嘗試能否放其它的牌。但這時(shí)手里只有一張3號(hào)牌,所以需要繼續(xù)向后回退,到2號(hào)盒子。按照上述步驟依次會(huì)產(chǎn)生所有結(jié)果。 用一個(gè)數(shù)組book標(biāo)記手里是否有這張牌。

Dfs(當(dāng)前這一步的處理邏輯)
{
1. 判斷邊界,是否已經(jīng)一條道走到黑了:向上回退
2. 嘗試當(dāng)下的每一種可能
3. 確定一種可能之后,繼續(xù)下一步 Dfs(下一步)
}

代碼實(shí)現(xiàn):

void DFS(vector<int>& boxs, vector<int>& books, int n, int index)
{
	if (index >= n + 1)
	{
		for (int i = 1; i <= n; i++)
			cout << boxs[i] << " "; //打印每一種結(jié)果
		cout << endl;
		return;
	}
	for (int i = 1; i <= n; i++)
	{
		if (books[i] == 0) //如果i號(hào)牌仍在手上
		{
			boxs[index] = i;
			books[i] = 1;
			DFS(boxs, books, n, index + 1);
			books[i] = 0;
		}
	}
}

員工的重要性

問(wèn)題描述:

給定一個(gè)保存員工信息的數(shù)據(jù)結(jié)構(gòu),它包含了員工 唯一的 id ,重要度 和 直系下屬的 id 。 比如,員工 1 是員工 2 的領(lǐng)導(dǎo),員工 2 是員工 3 的領(lǐng)導(dǎo)。他們相應(yīng)的重要度為 15 , 10 , 5 。那么員工 1 的數(shù)據(jù)結(jié)構(gòu)是 [1, 15, [2]] ,員工 2的 數(shù)據(jù)結(jié)構(gòu)是 [2, 10, [3]] ,員工 3 的數(shù)據(jù)結(jié)構(gòu)是 [3, 5, []] 。注意雖然員工 3 也是員工 1 的一個(gè)下屬,但是由于 并不是直系 下屬,因此沒(méi)有體現(xiàn)在員工 1 的數(shù)據(jù)結(jié)構(gòu)中。

現(xiàn)在輸入一個(gè)公司的所有員工信息,以及單個(gè)員工 id ,返回這個(gè)員工和他所有下屬的重要度之和。

解題思路:

邊界:下屬為空

每次先加第一個(gè)下屬的重要性

按照相同的操作再去加下屬的第一個(gè)下屬的重要性。

代碼實(shí)現(xiàn):

/*
// Definition for Employee.
class Employee {
public:
    int id;
    int importance;
    vector<int> subordinates;
};
*/

class Solution {
public:
    int DFS(unordered_map<int, Employee*>& info, int id)
    {
        int curImpo = info[id]->importance;
        for(const auto& sid : info[id]->subordinates)
        {
            curImpo += DFS(info, sid);
        }

        return curImpo;
    }

    int getImportance(vector<Employee*> employees, int id) {
        if(employees.empty())
            return 0;
        unordered_map<int, Employee*> info;
        for(const auto& e : employees)
        {
            info[e->id] = e;
        }

        return DFS(info, id);
    }
};

圖像渲染

問(wèn)題描述:

有一幅以二維整數(shù)數(shù)組表示的圖畫(huà),每一個(gè)整數(shù)表示該圖畫(huà)的像素值大小,數(shù)值在 0 到 65535 之間。 給你一個(gè)坐標(biāo) (sr, sc) 表示圖像渲染開(kāi)始的像素值(行 ,列)和一個(gè)新的顏色值 newColor,讓你重新上色這幅圖像。 為了完成上色工作,從初始坐標(biāo)開(kāi)始,記錄初始坐標(biāo)的上下左右四個(gè)方向上像素值與初始坐標(biāo)相同的相連像素點(diǎn),接著再記錄這四個(gè)方向上符合條件的像素點(diǎn)與他們對(duì)應(yīng)四個(gè)方向上像素值與初始坐標(biāo)相同的相連像素點(diǎn),……,重復(fù)該過(guò)程。將所有有記錄的像素點(diǎn)的顏色值改為新的顏色值。

最后返回經(jīng)過(guò)上色渲染后的圖像。

解題思路:

從所給坐標(biāo)開(kāi)始,向上下左右四個(gè)方向渲染,只要渲染點(diǎn)的顏色值和原坐標(biāo)相同,則繼續(xù)向外渲染。 邊界:位置是否越界。

這里需要用標(biāo)記避免重復(fù)修改,使時(shí)間復(fù)雜度不超過(guò)O(row*col)

代碼實(shí)現(xiàn):

int nextP[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

class Solution {
public:
    void DFS(vector<vector<int>>& image, vector<vector<int>>& book, int sr, int sc, int newColor, int oldColor, int row, int col)
    {
        image[sr][sc] = newColor;
        book[sr][sc] = 1;
        for(int i = 0; i < 4; i++)
        {
            int curX = sr + nextP[i][0];
            int curY = sc + nextP[i][1];

            //判斷是否越界
            if(curX < 0 || curX >= row || curY < 0 || curY >= col)
                continue;
            //顏色符合要求且之前沒(méi)被渲染過(guò)則繼續(xù)渲染
            if(image[curX][curY] == oldColor && book[curX][curY] == 0)
            {
                DFS(image, book, curX, curY, newColor, oldColor, row, col);
            }
        }
    }

    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        int row = image.size();
        int col = image[0].size();
        int oldColor = image[sr][sc];
        vector<vector<int>> book(row, vector<int>(col, 0));

        DFS(image, book, sr, sc, newColor, oldColor, row, col);

        return image;
    }
};

被圍繞的區(qū)域

問(wèn)題描述:

給你一個(gè) m x n 的矩陣 board ,由若干字符 ‘X' 和 ‘O' ,找到所有被 ‘X' 圍繞的區(qū)域,并將這些區(qū)域里所有的 ‘O' 用 ‘X' 填充。

解題思路: 從每個(gè)邊緣的O開(kāi)始,只要和邊緣的O連通,則它就沒(méi)有被包圍。

1.首先尋找邊上的每一個(gè)O,如果沒(méi)有,表示所有的O都被包圍。

2.對(duì)于邊上的每一個(gè)O進(jìn)行dfs擴(kuò)散,先把邊上的每一個(gè)O用特殊符號(hào)標(biāo)記(除了X和O以外)。把和它相鄰的O都替換為特殊符號(hào),每一個(gè)新的位置都做相同的dfs操作。

3.所有擴(kuò)散結(jié)束之后,把特殊符號(hào)的位置(和邊界連通)還原為O,原來(lái)為O的位置(和邊界不連通)替換為X即可。

代碼實(shí)現(xiàn):

int nextP[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

class Solution {
public:
    void DFS(vector<vector<char>>& board, int curX, int curY, int row, int col)
    {
        board[curX][curY] = 'A';
        for(int i = 0; i < 4; i++)
        {
            int x = curX + nextP[i][0];
            int y = curY + nextP[i][1];

            if(x < 0 || x >= row
               ||y < 0 || y >= col)
                continue;

            if(board[x][y] != 'A' && board[x][y] != 'X')
                DFS(board, x, y, row, col);
        }
    }

    void solve(vector<vector<char>>& board) {
        if(board.empty())
            return;
        int row = board.size();
        int col = board[0].size();

        //第一行和最后一行
        for(int i = 0; i < col; i++)
        {
            if(board[0][i] == 'O')
                DFS(board, 0, i, row, col);
            if(board[row-1][i] == 'O')
                DFS(board, row-1, i, row, col);
        }
        //第一列和最后一列
        for(int i = 0; i < row; i++)
        {
            if(board[i][0] == 'O')
                DFS(board, i, 0, row, col);
            if(board[i][col-1] == 'O')
                DFS(board, i, col-1, row, col);
        }

        for(int i = 1; i < row-1; i++)
        {
            for(int j = 0; j < col; j++)
            {
                if(board[i][j] == 'A')
                    board[i][j] = 'O';
                else if(board[i][j] == 'O')
                    board[i][j] = 'X';
            }
        }
    }
};

島嶼數(shù)量

問(wèn)題描述:

給你一個(gè)由 ‘1'(陸地)和 ‘0'(水)組成的的二維網(wǎng)格,請(qǐng)你計(jì)算網(wǎng)格中島嶼的數(shù)量。 島嶼總是被水包圍,并且每座島嶼只能由水平方向和/或豎直方向上相鄰的陸地連接形成。 此外,你可以假設(shè)該網(wǎng)格的四條邊均被水包圍。

示例 1:

輸入:grid = [ [“1”,“1”,“1”,“1”,“0”], [“1”,“1”,“0”,“1”,“0”], [“1”,“1”,“0”,“0”,“0”], [“0”,“0”,“0”,“0”,“0”] ]

輸出:1

解題思路:

本題可以采用類(lèi)似渲染的做法,嘗試以每個(gè)點(diǎn)作為渲染的起點(diǎn),可以渲染的陸地都算作一個(gè)島嶼,最后看渲染了多少次,即深度優(yōu)先算法執(zhí)行了多少次,就是島嶼的數(shù)量。

代碼實(shí)現(xiàn):

int nextP[4][2] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };

class Solution {
public:
    void DFS(vector<vector<char>>& grid, vector<vector<int>>& book, int x, int y, int row, int col)
    {
        book[x][y] = 1;
        for(int i = 0; i < 4; i++)
        {
            int curX = x + nextP[i][0];
            int curY = y + nextP[i][1];

            if(curX < 0 || curX >= row || curY < 0 || curY >= col)
                continue;
            
            if(grid[curX][curY] == '1' && book[curX][curY] == 0)
                DFS(grid, book, curX, curY, row, col);
        }
    }

    int numIslands(vector<vector<char>>& grid) {
        if(grid.empty())
            return 0;
        int row = grid.size();
        int col = grid[0].size();
        int num = 0;
        vector<vector<int>> book(row, vector<int>(col, 0));
        for(int i = 0; i < row; i++)
        {
            for(int j = 0; j < col; j++)
            {
                if(grid[i][j] == '1' && book[i][j] == 0)
                {
                    ++num;
                    DFS(grid, book, i, j, row, col);
                }
            }
        }

        return num;
    }
};

電話號(hào)碼的字母組合

問(wèn)題描述:

給定一個(gè)僅包含數(shù)字 2-9 的字符串,返回所有它能表示的字母組合。答案可以按 任意順序 返回。 給出數(shù)字到字母的映射如下(與電話按鍵相同)。注意 1 不對(duì)應(yīng)任何字母。

解題思路:

首先使用數(shù)組(也可使用哈希表)存儲(chǔ)每個(gè)數(shù)字對(duì)應(yīng)的所有可能的字母,然后進(jìn)行回溯操作?;厮菟惴ㄓ糜趯ふ宜械目尚薪猓绻l(fā)現(xiàn)一個(gè)解不可行,則會(huì)舍棄不可行的解。在這道題中,由于每個(gè)數(shù)字對(duì)應(yīng)的每個(gè)字母都可能進(jìn)入字母組合,因此不存在不可行的解,直接窮舉所有的解即可。

代碼實(shí)現(xiàn):

string mapString[] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

class Solution {
public:
    void DFS(string& digits, vector<string>& result, string curStr, int curDepth)
    {
        //邊界,找到一種組合,放入數(shù)組中,結(jié)束此路徑,向上回溯
        if(curDepth == digits.size())
        {
            if(!curStr.empty())
                result.push_back(curStr);
            return;
        }
        //找到當(dāng)前字符映射在mapString種的位置
        int curMapIndex = digits[curDepth] - '0';
        string curMap = mapString[curMapIndex];
        //遍歷每一種可能
        for(const auto& ch : curMap)
        {
            DFS(digits, result, curStr+ch, curDepth+1);
        }
    }

    vector<string> letterCombinations(string digits) {
        vector<string> result;
        DFS(digits, result, "", 0);
        return result;
    }
};

組合總數(shù)

問(wèn)題描述:

給你一個(gè) 無(wú)重復(fù)元素 的整數(shù)數(shù)組 candidates 和一個(gè)目標(biāo)整數(shù) target ,找出 candidates 中可以使數(shù)字和為目標(biāo)數(shù) target 的 所有不同組合 ,并以列表形式返回。你可以按 任意順序 返回這些組合。

candidates 中的 同一個(gè) 數(shù)字可以 無(wú)限制重復(fù)被選取 。如果至少一個(gè)數(shù)字的被選數(shù)量不同,則兩種組合是不同的。

對(duì)于給定的輸入,保證和為 target 的不同組合數(shù)少于 150 個(gè)。

輸入:candidates = [2,3,6,7], target = 7

輸出:[[2,2,3],[7]]

解題思路:

此題相加的元素可以重復(fù),所以去下一個(gè)元素的位置可以從當(dāng)前位置開(kāi)始,DFS+回溯。為了保證組合不重復(fù)(順序不同,元素相同,也算重復(fù)),不再?gòu)漠?dāng)前位置向前看。

1.從第一個(gè)元素開(kāi)始相加

2.讓局部和繼續(xù)累加候選的剩余值

3.局部和等于目標(biāo)值,保存組合,向上回退,尋找其它組合

代碼實(shí)現(xiàn):

class Solution {
public:
    void DFS(vector<int>& candidates, vector<vector<int>>& result, vector<int> curCand, int prePos, int curSum, int target)
    {
        if(curSum >= target)
        {
            if(curSum == target)
                result.push_back(curCand);
            return;
        }
        for(int i = prePos; i < candidates.size(); i++)
        {
            if(candidates[i] <= target)
            {
                curCand.push_back(candidates[i]);
                DFS(candidates, result, curCand, i, curSum+candidates[i], target);
                //回溯
                curCand.pop_back();
            }
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> result;
        vector<int> curCand;
        DFS(candidates, result, curCand, 0, 0, target);
        return result;
    }
};

活字印書(shū)

問(wèn)題描述:

你有一套活字字模 tiles,其中每個(gè)字模上都刻有一個(gè)字母 tiles[i]。返回你可以印出的非空字母序列的數(shù)目。

注意:本題中,每個(gè)活字字模只能使用一次。

示例 1:

輸入:“AAB”

輸出:8

解釋:可能的序列為 “A”, “B”, “AA”, “AB”, “BA”, “AAB”, “ABA”, “BAA”。

解題思路:

此題組合的長(zhǎng)度不唯一,最小組合長(zhǎng)度為1,最大組合長(zhǎng)度為tiles的長(zhǎng)度。按照題意tiles中每一個(gè)位置的字符在組合中只能出現(xiàn)一次,所以可以用一個(gè)標(biāo)記輔助。當(dāng)組合新的組合時(shí),可以與tiles種的每一個(gè)位置組合,但是如果當(dāng)前位置已經(jīng)在當(dāng)前組合中出現(xiàn)過(guò),則跳過(guò)。雖然此題種每一個(gè)位置的字符在組合中只能出現(xiàn)一次,但是tiles中可能有相同的字符,所以需要考慮重復(fù)的組合。而用unordered_set可以天然去重。

DFS+回溯:

1.當(dāng)前組合不為空,則插入set中

2.繼續(xù)給當(dāng)前組合拼接新的組合,嘗試拼接tiles每一個(gè)位置的字符

3.如果當(dāng)前位置已經(jīng)在組合中出現(xiàn)過(guò),返回到2,否則標(biāo)記當(dāng)前位置,繼續(xù)拼接更長(zhǎng)的組合

4.回溯,嘗試組合其它位置,返回2

當(dāng)所有位置都已經(jīng)使用過(guò)時(shí),當(dāng)前遞歸就結(jié)束了,繼續(xù)向上層DFS回退

最終返回set大小即為組合數(shù)目

代碼實(shí)現(xiàn):

class Solution {
public:
    void DFS(string& tiles, vector<int>& book, string curStr, unordered_set<string>& totolaString)
    {
        if(!curStr.empty())
        {
            totolaString.insert(curStr);
        }
        for(int i = 0; i < tiles.size(); i++)
        {
            //當(dāng)前字符已用過(guò),跳過(guò)
            if(book[i] == 1)
                continue;
            book[i] = 1;
            DFS(tiles, book, curStr+tiles[i], totolaString);
            book[i] = 0;
        }
    }

    int numTilePossibilities(string tiles) {
        vector<int> book(tiles.size(), 0);
        unordered_set<string> totolaString;
        DFS(tiles, book, "", totolaString);

        return totolaString.size();
    }
};

N皇后

問(wèn)題描述:

n 皇后問(wèn)題 研究的是如何將 n 個(gè)皇后放置在 n×n 的棋盤(pán)上,并且使皇后彼此之間不能相互攻擊。

給你一個(gè)整數(shù) n ,返回所有不同的 n 皇后問(wèn)題 的解決方案。

每一種解法包含一個(gè)不同的 n 皇后問(wèn)題 的棋子放置方案,該方案中 ‘Q' 和 ‘.' 分別代表了皇后和空位。

解題思路:

DFS+回溯

從第一行開(kāi)始放置皇后,每確定一個(gè)位置,判斷是否會(huì)沖突(是否在同一列、同一斜線,已經(jīng)不可能在同一行)

同一列:縱坐標(biāo)相同

同一斜線:坐標(biāo)差或坐標(biāo)和相同。

當(dāng)前行位置確定后,繼續(xù)確定下一行的位置。

回退,嘗試其他行的其它位置。

代碼實(shí)現(xiàn):

class Solution {
public:
    bool isValidPos(vector<pair<int, int>>& curRet, int row, int col)
    {
        for(pair<int, int> pos : curRet)
        {
            if(pos.second == col || pos.first + pos.second == row + col
               || pos.first - pos.second == row - col)
                return false;
        }

        return true;
    }

    void DFS(vector<vector<pair<int, int>>>& allRet, vector<pair<int, int>>& curRet, int curRow, int n)
    {
        //如果每一行都沒(méi)有沖突,則是一種可行的方案
        if(curRow == n)
        {
            allRet.push_back(curRet);
            return;
        }
        //確定當(dāng)前行的每一個(gè)位置是否和已確定的位置有沖突
        for(int i = 0; i < n; i++)
        {
            if(isValidPos(curRet, curRow, i))
            {
                curRet.push_back(make_pair(curRow,i));
                //處理下一行
                DFS(allRet, curRet, curRow+1, n);
                //回溯
                curRet.pop_back();
            }
        }
    }

    vector<vector<string>> transResult(vector<vector<pair<int, int>>>& allRet, int n)
    {
        vector<vector<string>> allMap;
        //所有方案
        for(vector<pair<int, int>> curRet : allRet)
        {
            vector<string> curMap(n, string(n, '.'));
            //一種方案中的所有皇后的位置
            for(pair<int, int> pos : curRet)
            {
                curMap[pos.first][pos.second] = 'Q';
            }
            allMap.push_back(curMap);
        }

        return allMap;
    }

    vector<vector<string>> solveNQueens(int n) {
        vector<vector<pair<int, int>>> allRet;
        vector<pair<int, int>> curRet;
        DFS(allRet, curRet, 0, n);

        return transResult(allRet, n);
    }
};

到此這篇關(guān)于C++回溯算法深度優(yōu)先搜索舉例分析的文章就介紹到這了,更多相關(guān)C++ 回溯算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

最新評(píng)論