C++在做递归回溯算法相关题目时,递归函数形参传值和传引用运行速度有很大的差异。
给定一个二维网格和一个单词,找出该单词是否存在于网格中。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
class Solution { public: bool exist(vector<vector<char>>& board, string word) { if(board.empty()||word.empty()) return false; for(int i=0; i<board.size(); ++i) { for(int j=0; j<board[0].size(); ++j) { // 使用回溯法解题 if(dfs(board, word, i, j, 0)) return true; } } return false; } bool dfs(vector<vector<char>>& board, string& word, int i, int j, int w) { // 如果索引越界,或者值不匹配,返回false if(i<0 || i>=board.size() || j<0 || j>=board[0].size() || board[i][j]!=word[w]) return false; if(w == word.length() - 1) return true; char temp = board[i][j]; board[i][j] = '0'; // 将当前元素标记为'\0',即一个不可能出现在word里的元素,表明当前元素不可再参与比较 if(dfs(board,word,i-1,j,w+1) ||dfs(board,word,i+1,j,w+1) ||dfs(board,word,i,j-1,w+1) ||dfs(board,word,i,j+1,w+1)) { // 当前元素的上下左右,如果有匹配到的,返回true return true; } board[i][j] = temp; // 将当前元素恢复回其本身值 return false; } };
感觉最近状态不是很好,到了这回真的熬不太住了,脑子昏昏沉沉的,明天得准备点咖啡之类的。
效率太低了。增强自觉性!!!
昨天面了深信服,主要问了问项目,tcpip握手分手,为什么分手多一次,冒泡排序,冒泡排序优化
C++11特性、象棋中固定起点和重点,让马去跳,最少几步能到达终点。大概记得这些,之后就直接感谢您参与这次面试,祝您生活越快。太真实了,也挺好,要挂直接挂,不跟你多墨迹。