首页 > 编程语言 >LeetCode回溯算法

LeetCode回溯算法

时间：2022-10-07 11:46:34浏览次数：95  
标签：return helper nums int res 算法 vector 回溯 LeetCode

Letter Combinations of a Phone Number

LeetCode/力扣

vector<string> letterCombinations(string digits) {
    if(digits.length() == 0) return {};
    map<char,string> num_to_char{
        {'2',"abc"},
        {'3',"def"},
        {'4',"ghi"},
        {'5',"jkl"},
        {'6',"mno"},
        {'7',"pqrs"},
        {'8',"tuv"},
        {'9',"wxyz"}
    };
    vector<string> res;
    string combination(digits.length(),' ');
    letterCombinations(digits,combination,0,num_to_char,res);
    return res;
}
void letterCombinations(string digits, string& combination, int idx, map<char,string>& num_to_char, vector<string>& res){
    if(idx == digits.length()){
        res.push_back(combination);
        return;
    }
    
    for(char c:num_to_char[digits[idx]]){
        combination[idx] = c;
        letterCombinations(digits,combination,idx+1,num_to_char,res);
    }
}

Generate Parentheses

LeetCode/力扣

vector<string> generateParenthesis(int n) {
    vector<string> result;
    if (n <= 0) return result;
    string tmpString = "(";
    addItem(result, tmpString, n-1, 1);
    return result;
}
    
void addItem(vector<string> &result,string &tmpString, int pre, int end) {
    if (pre == 0 && end == 0) {
        result.push_back(tmpString);
        return;
    }
    if (pre > 0) {
        tmpString.push_back('(');
        addItem(result, tmpString, pre-1, end+1);
        tmpString.pop_back();
    }
    if (end > 0) {
        tmpString.push_back(')');
        addItem(result, tmpString, pre, end-1);
        tmpString.pop_back();
    }
   return;
}

Sudoku Solver

LeetCode/力扣

void solveSudoku(vector<vector<char>>& board) {
    helper(board,0,0);
}
bool helper(vector<vector<char>>& board, int i, int j ) {
    if(i == 9) return true;
    if(j == 9) return helper(board, i + 1,0);
    if(board[i][j] != '.') return helper(board, i, j + 1);
    for(int k = 1; k <= 9; k++) {
        if(safe(board, i, j, k )){
            board[i][j] = k + '0';
            bool check = helper(board, i, j + 1);
            if(check) return true;
        } 
    }
    board[i][j] = '.';
    return false;
}
bool safe(vector<vector<char>>& board, int i,int j, int target) {
    for(int k = 0; k < 9; k++) {
        if(board[i][k] == target + '0' || board[k][j] == target + '0') return false;
    }
    int m = i / 3, n = j / 3;
    for(int k1 = m * 3; k1 < 3 * m + 3; k1++) {
        for(int k2 = n * 3; k2 < 3 * n + 3; k2++) {
            if(board[k1][k2] == target + '0') return false;
        }
    }
    return true;
}

Combination Sum

LeetCode/力扣

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<int> temp;
    vector<vector<int>> res;
    helper(candidates, target,0, 0, temp, res);
    return res;
}

void helper(vector<int>& can, int target,int index, int sum, vector<int>& temp, vector<vector<int>>& res) {
    if(sum == target){
        res.push_back(temp);
        return;
    }
    if(sum > target) return;
    
    for(int i = index; i < can.size(); i++) {
        temp.push_back(can[i]);
        helper(can, target,i, sum + can[i], temp, res);
        temp.pop_back();
    }
}

Combination Sum II

LeetCode/力扣

vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    vector<int> temp;
    vector<vector<int>> res;
    sort(candidates.begin(),candidates.end());
    helper(candidates, target, temp, res, 0, 0);
    return res;
}
void helper(vector<int>& can, int target, vector<int>& temp, vector<vector<int>>& res,int sum, int index) {
    if(sum == target){
        res.push_back(temp);
        return;
    }
    if(sum > target) return;
    
    for(int i = index; i<can.size();i++) {
        if(i > index && can[i] == can[i-1]) continue;
        temp.push_back(can[i]);
        helper(can,target, temp, res, sum + can[i], i + 1);
        temp.pop_back();
    }
}

Permutations

LeetCode/力扣

vector<vector<int>> permute(vector<int>& nums) {
    vector<int> temp;
    vector<vector<int>> res;
    vector<bool> visited(nums.size(), false);
    helper(nums, nums.size(), temp, res, visited);
    return res;
}
void helper(vector<int>& nums, int len, vector<int>& temp, vector<vector<int>>& res,vector<bool> visited) {
    if(len <= 0) {
        res.push_back(temp);
        return;
    }
    for(int i = 0; i < nums.size(); i++) {
        if(!visited[i]) {
            temp.push_back(nums[i]);
            visited[i] = true;
            helper(nums,len - 1, temp, res, visited);
            visited[i] = false;
            temp.pop_back();
        }
    }
}

Permutations II

LeetCode/力扣

vector<vector<int>> permuteUnique(vector<int>& nums) {
    vector<int> temp;
    unordered_map<int, int> m;
    for(int i = 0; i < nums.size(); i++) {
        m[nums[i]]++;
    }
    vector<vector<int>> res;
    helper(nums, nums.size(), temp, res, m);
    return res;
}
void helper(vector<int>& nums, int len, vector<int>& temp, vector<vector<int>>& res, unordered_map<int,int>& m) {
    if(len <= 0) {
        res.push_back(temp);
        return;
    }
    
    for(auto& it : m) {
        if(it.second <= 0) continue;
        it.second--;
        temp.push_back(it.first);
        helper(nums, len - 1, temp, res, m);
        it.second++;
        temp.pop_back();
    }
}

N-Queens

LeetCode/力扣

vector<vector<int>> placements;
vector<int> placement, br, bd1, bd2;
void dfs(int col, int n) {
    if (col == n) {
        placements.push_back(placement);
        return;
    }
    for (int row = 0; row < n; ++row) {
        if (br[row] || bd1[row + col]) continue;
        int id = row - col < 0 ? 2 * n + row - col : row - col;
        if (bd2[id]) continue;
        placement.push_back(row);
        br[row] = bd1[row + col] = bd2[id] = 1;
        dfs(col + 1, n);
        br[row] = bd1[row + col] = bd2[id] = 0;
        placement.pop_back();
    }
}
vector<vector<string>> solveNQueens(int n) {
    br.resize(n);
    bd1.resize(2 * n + 1);
    bd2.resize(2 * n + 1);
    dfs(0, n);
    vector<vector<string>> boards(placements.size(), vector<string>(n, string(n, '.')));
    for (int i = 0; i < placements.size(); ++i) {
        for (int j = 0; j < n; ++j) {
            boards[i][placements[i][j]][j] = 'Q';
        }
    }
    return boards;
}

Combinations

LeetCode/力扣

vector<vector<int>> combine(int n, int k) {
    vector<int> t;
    vector<vector<int>> r;
    vector<int> v(n+1,0);
    helper(t,r,1,n,k,v);
    return r;
}

void helper(vector<int>& t, vector<vector<int>>& r,int idx, int n, int k,vector<int>& v) {
    if(t.size() == k) {
        r.push_back(t);
        return;
    }
    for(int i = idx; i <= n; i++) {
        if(v[i] == 1) continue;
        t.push_back(i);
        v[i] = 1;
        helper(t, r,i, n, k,v);
        t.pop_back();
        v[i] = 0;
    }
}

Subsets

LeetCode/力扣

vector<vector<int>> subsets(vector<int>& nums) {
    vector<int> t;
    vector<vector<int>> r;
    helper(t,r,nums,0);
    return r;
}

void helper(vector<int>& t, vector<vector<int>>& r, vector<int>& nums, int idx) {
    if(t.size() <= nums.size()) {
        r.push_back(t);
    }
    if(t.size() > nums.size() || idx > nums.size()) {
        return;
    }
    
    for(int i = idx; i < nums.size(); i++) {
        t.push_back(nums[i]);
        helper(t,r,nums,i + 1);
        t.pop_back();
    }
}

Subsets II

LeetCode/力扣

vector<vector<int>> subsetsWithDup(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<int> t;
    vector<vector<int>> r;
    helper(t,r,nums,0);
    return r;
}

void helper(vector<int>& t, vector<vector<int>>& r, vector<int>& nums, int idx) {
    if(t.size() <= nums.size()) {
        r.push_back(t);
    }
    if(t.size() > nums.size() || idx > nums.size()) return;
    
    for(int i = idx; i < nums.size(); i++) {
        if(i > idx && nums[i] == nums[i - 1]) continue;
        t.push_back(nums[i]);
        helper(t,r,nums,i+1);
        t.pop_back();
    }
}

Palindrome Partitioning

LeetCode/力扣

void _solve(int ind, string &s, vector<vector<bool>> &dp, vector<string> &ans, vector<vector<string>> &res){
    if(ind == s.length()){
        res.push_back(ans);
        return;
    }
    for(int i = ind; i < s.length(); i++)
        if(dp[ind][i]){
            ans.push_back(s.substr(ind, i - ind + 1));
            _solve(i + 1, s, dp, ans, res);
            ans.pop_back();
        }
}
    
vector<vector<string>> partition(string s) {
    vector<vector<string>> res;
    vector<string> ans;
    int n = s.length();
    vector<vector<bool>> dp(n, vector<bool>(n));
    
    for(int i = 0; i < n; i++)
        dp[i][i] = true;
    for(int l = 2; l <= n; l++){
        for(int i = 0; i < n - l + 1; i++){
            int j = i + l - 1;
            if(l == 2)
                dp[i][j] = s[i] == s[j] ? true : false;
            else
                dp[i][j] = s[i] == s[j] && dp[i + 1][j - 1] ? true : false;
         }
    }
    _solve(0, s, dp, ans, res);
    return res;
}

Combination Sum III

LeetCode/力扣

vector<vector<int>> combinationSum3(int k, int n) {
    vector<int> t;
    vector<vector<int>> r;
    vector<int> visited(9,0);
    helper(k,n, t, r, 0,1, 0,visited);
    return r;
}
void helper(int k, int n, vector<int>& t, vector<vector<int>>& r, int sum,int index, int idx,vector<int>& visited) {
    if(idx == k && sum == n) {
        r.push_back(t);
        return;
    }
    if(sum > n) return;
    
    for(int i = index; i <= 9; i++) {
        if(visited[i-1] == 1) continue;
        t.push_back(i);
        visited[i-1] = 1;
        helper(k, n, t, r, sum + i,i + 1, idx + 1,visited);
        t.pop_back();
        visited[i-1] = 0;
    }
}

Target Sum

LeetCode/力扣

int findTargetSumWays(vector<int>& nums, int target) {
    long sum=0,n=nums.size();
    for(auto x:nums) sum+=x;
    if((sum+target)&1 or target>sum) return 0;
    long newsum=(sum+target)/2;
    vector<vector<int>>dp(n+1,vector<int>(newsum+1,0));
    dp[0][0]=1;
    for(int i=1 ; i<=n ; i++)
        for(int j=0 ; j<=newsum ; j++)
        {
            if(nums[i-1]>j) dp[i][j]=dp[i-1][j];
            else dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i-1]];
        }
    return dp[n][newsum];
}

Letter Case Permutation

LeetCode/力扣

vector<string> letterCasePermutation(string S) {
    vector<string> r;
    helper(r,S,0);
    return r;
}

void helper(vector<string>& r, string s, int idx) {
    if(idx == s.size()) {
        r.push_back(s);
        return;
    }
    
    helper(r, s, idx + 1);
    
    if(isalpha(s[idx])){
        s[idx]=isupper(s[idx]) ? tolower(s[idx]) : toupper(s[idx]) ;
        helper(r,s,idx+1);
    }
}

标签：return,helper,nums,int,res,算法,vector,回溯,LeetCode
From： https://www.cnblogs.com/xnzone/p/16759358.html

相关文章

  • LeetCode双堆问题
    FindMedianfromDataStreamLeetCode/力扣数组保存数据，add的时候直接在末尾插入，查找的时候，先排序，然后再算其中的结果vector<int>data;/**initializeyourdatastr......
  • LeetCode二分搜索
    SearchinRotatedSortedArrayLeetCode/力扣先判断中间的和尾部的数字大小，再判断target和首尾中三个数字大小关系，如此便能进行二分搜索intsearch(vector<int>&nums,......
  • 目前最强性能的人脸检测算法（Wider Face Dataset）
           最强性能的人脸检测今天我们不说计算机视觉基础知识，接下来说说AAAI2019一篇比较新颖的Paper，其是中科院自动化所和京东AI研究院联合的结果，在WiderFace......
  • Python 冒泡排序，选择排序，归并排序， 希尔排序 算法 及测试
    使用代码实现冒泡排序，选择排序，归并排序，希尔排序4中算法完成下列任务。对1~100000序列打乱顺序，使用上述4种排序算法进行排序。每种算法排序重复100次排序过程中记录......
  • 【复习笔记】tarjan算法
    写点东西好复习，主要是tarjan这个东西学了容易忘，忘了也不难捡起来，但捡起来了又容易忘。tarjan的前置知识dfs树就暂且咕咕了，因为这东西没什么模板，变化挺多的，估计是写不完。......
  • 我整理了50道经典Java算法题，直接进了字节跳动！！
    写在前面最近，很多小伙伴都想进入字节跳动这个快速发展的公司，而字节跳动对于算法的要求比较高。于是乎，有些小伙伴问我能否整理一些基础的算法题，帮助他们提升下基础算法能......
  • Java 面试题 10 - 海量数据处理算法
    大数据处理中的分治思想哈希映射：如果数据太大，不能全部放入内存中，就可以利用映射函数将每条数据映射到一个小文件中，例如%1000可以将大文件映射成1000个小文件。相同的......
  • Kmeans聚类算法详解
    摘要：本文详细介绍Kmeans聚类算法的原理和程序实现。首先介绍利用该算法的原理及理解，详细介绍基于MATLAB设计一个自定义的Kmeans函数过程，然后利用该函数对UCI的数据集进行聚......
  • LeetCode20 有效的括号
    给定一个只包括'('，')'，'{'，'}'，'['，']' 的字符串s，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都......
  • LeetCode138 复制带随机指针的链表
     idea: 刚开始没有思路，被题目弄懵了，我能想到的方法就是先复制不带random指针的链表，之后由表头到表尾再将每个结点的random指针通过循环进行连接，时间复杂度肯定时很高......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99