【面试HOT200】回溯篇

系列综述:
💞目的:本系列是个人整理为了秋招面试的,整理期间苛求每个知识点,平衡理解简易度与深入程度。
🥰来源:材料主要源于【CodeTopHot300】进行的,每个知识点的修正和深入主要参考各平台大佬的文章,其中也可能含有少量的个人实验自证,所有代码均优先参考最佳性能。
🤭结语:如果有帮到你的地方,就点个赞关注一下呗,谢谢🎈🎄🌷!!!
🌈【C++】秋招&实习面经汇总篇


文章目录

    • 基础知识
    • 回溯基础算法模板
      • 组合问题
        • 无重复元素的组合
        • 有重复元素的组合
      • 排列问题
        • 无重复元素的全排列
        • 有重复元素的全排列
    • HOT200回溯相关题目
        • 39. 组合总和
        • 40. 组合总和 II
        • 93. 复原 IP 地址
        • 131. 分割回文串
        • 1005. K 次取反后最大化的数组和
    • 参考博客


😊点此到文末惊喜↩︎

基础知识

  1. 回溯算法 = 穷举 + 剪枝
    • 穷举:从一个选择开始,一步步尝试每一个可能的选择,如果某次选择导致问题无法解决,则回溯并选择另一种可能,直到找到一个可行的解或者穷举所有可能的解。
    • 剪枝:在搜索过程中,根据问题的限制条件,减少搜索空间,提高算法效率
  2. 作用
    • 在多个选择中搜索出满足条件所有可能解
    • 一般地,组合问题和排列问题是在树形结构的叶子节点上收集结果,而子集问题就是取树上所有节点的结果。
  3. 回溯算法解决的问题一般为npc问题,难以使用常规算法进行解决
    • 组合问题:N个数里面按一定规则找出k个数的集合
      • 切割问题:一个字符串按一定规则有几种切割方式
      • 子集问题:一个N个数的集合里有多少符合条件的子集
    • 排列问题:N个数按一定规则选出M个,有几种排列方式
    • 棋盘问题:N皇后,解数独等等
  4. 所有的回溯法解决的问题都可以抽象为树形结构
    • 根节点是总数据集合,树枝节点是可选数据集合
    • 叶子节点为根节点到叶子节点的路径的选择集合
      在这里插入图片描述
// 结果集和路径集
vector<vector<type> res;
vector<type> path;
void backtracking(vecotr<type> candidates, int startIndex) {
	// 针对当前选择的合法性判断
	auto is_ok = [](const type &data)->bool{
		// type中数据项的合法性判断
	};
	// 递归出口:结点剪枝,生成慢
    if (is_ok(val)) {
        res.push_back(path);
        return;
    }
	// 延申和回撤路径时,可能涉及多个状态标记变量的改动
    for (int i = startIndex; i < candidates.size(); ++i) {
    	分叉剪枝判断(性能高);
    	// 状态延申改动
        path.push_back(candidates[i]);// 向下延申
        backtracking(剩余可选列表); // 回溯
        // 状态回撤改动
        path.pop_back();// 回撤延申
    }
}
// 主函数
vector<vector<int>> combine(vector<type>& candidates) {
       res.clear(); // 可以不写
       path.clear();// 可以不写
       backtracking(candidates, 0);
       return result;
   }

回溯基础算法模板

模板使用的初衷:将问题的输入转换成对应模板的输入格式,然后调用模板的函数(已经背诵的)进行快速的求解

组合问题

  1. 组合问题的复杂度
    • 时间复杂度: O ( C n k × k ) O(C_n^k × k) O(Cnk×k),总共有 C n k C_n^k Cnk种组合,每种组合需要 O ( k ) O(k) O(k) 的时间复杂度
    • 空间复杂度: O ( n ) O(n) O(n),递归深度为n,所以系统栈所用空间为 O ( n ) O(n) O(n)
无重复元素的组合
  1. 基本概述
    • 问题:从无重复元素的集合中选出K个元素组成组合,每个元素只能被选取一次,且选出的元素之间没有顺序之分。
    • 举例:从元素集合{1,2,3}中选择2个元素的组合为{(1,2),(1,3),(2,3)}。
      在这里插入图片描述
  2. 代码
    • 解决的问题:给定一个线性表,求该线性表中满足条件组合
    • 示例:求线性表中所有个数为target的结果。
    • 剪枝:列表中剩余元素(vec.size() - i) >= 所需需要的元素个数(target - path.size())
// 从候选集candidate中选出任意k个数组成的集合
vector<vector<int>> Backtracking(vector<int> &candidate, int k) {
	const int len = candidate.size();
    // 递归函数
    vector<int> path;			// 符合条件的路径
    vector<vector<int>> res;	// 符合条件的路径集合
    auto self = [&](auto &&self, int pos){
        // 递归出口:满足条件的路径加入结果集中
        if (path.size() == k) {
            res.push_back(path);
            return;
        }
        // i = start表示从之后剩余中选择
        for (int i = pos; i < len ; ++i) {
            if (i > len - (k-path.size())) 
                 continue;
            path.push_back(candidate[i]);	// 做出选择
           	self(self, i+1);// key: 是i+1	// 递归
            path.pop_back();				// 撤销选择
        }
    };
    self(self, 0);
    return res;
}

有重复元素的组合
  1. 基本概述
    • 问题:从有重复元素的组合中选出若干元素组成组合,每个元素只能被选取一次,且选出的元素之间没有顺序之分。
    • 举例:从集合{1, 2, 2, 3}中选择2个元素的组合为{1, 2}、{1, 3}、{2, 2}、{2, 3}。
  2. 代码
    • 解决问题:给定一个线性表,求该线性表中满足条件组合,因为有重复元素,所以选择重复元素时只能使用一次,否则会出现集合中的重复
vector<vector<int>> Backtracking(vector<int> &candidate, int k) {
    // 排序
    sort(candidate.begin(), candidate.end());
    // 递归匿名函数
    vector<int> path;
    vector<vector<int>> res;
    auto self = [&](auto &&self, int pos){
        if (path.size() == k) {
            res.push_back(path);
            return;
        }

        for (int i = pos; i < candidate.size(); ++i) {
            // key: i > pos。第一次选取到重复的数,不会影响后面
            if (i > pos && candidate[i] == candidate[i-1])
                continue;
            path.push_back(candidate[i]);
            self(self, i+1);
            path.pop_back();
        }
    };
    // 递归调用
    self(self, 0);
    return res;
}

排列问题

  1. 组合问题的复杂度
    • 时间复杂度: O ( n × n ! ) O(n×n!) O(n×n!),一共 n ! n! n! 种组合,每种排列构造时间需要 O ( n ) O(n) O(n) 的时间复杂度
    • 空间复杂度: O ( n ) O(n) O(n),递归深度为n,所以系统栈所用空间为 O ( n ) O(n) O(n)
无重复元素的全排列
  1. 基本概述
    • 问题:无重复元素的排列是指在给定一组不同的元素中,按照一定的顺序排列出所有可能的组合,每个元素只出现一次
    • 举例:从集合{1, 2, 3},则可以产生以下6种无重复元素的排列:{1, 2, 3}、{1, 3, 2}、{2, 1, 3}、{2, 3, 1}、{3, 1, 2}、{3, 2, 1}。
      在这里插入图片描述
  2. 代码
    • 不需要使用pos,每一个i对应一位
    vector<vector<int>> permute(vector<int>& candidate) {
        const int len = candidate.size();
        vector<int> path;				// 回溯路径
        vector<vector<int>> res;		// 回溯结果集
        vector<bool> used(len, false);	// 使用标记
        auto self = [&](auto &&self){	// 回溯算法
            if (path.size() == len) {
                res.push_back(path);
                return ;
            }
            for (int i = 0; i < len; ++i) {
            	// path里已经收录的元素,直接跳过
                if (used[i] == true) continue;
                // 增加选择
                used[i] = true;
                path.push_back(candidate[i]);
                // 进行回溯
                self(self);
                // 撤回选择
                used[i] = false;
                path.pop_back();
            }
        };
        // 调用
        self(self);
        return res;
    }
    
有重复元素的全排列
  1. 基本概述

    • 问题:无重复元素的排列是指在给定一组不同的元素中,按照一定的顺序排列出所有的不重复组合
    • 举例:从集合[1,1,2],则可以产生无重复的全排列: [1,1,2], [1,2,1], [2,1,1]
  2. 代码

    • 产生重复解的原因:例如[1,1,2], 无法区分[1(0), 1(1), 2] 和[1(1), 1(0), 2] 这两种情况的解
      在这里插入图片描述
    vector<vector<int>> permuteUnique(vector<int>& candidate) {
        const int len = candidate.size();
        sort(candidate.begin(), candidate.end());
    	// 递归
        vector<int> path;
        vector<vector<int>> res;
        vector<bool> used(len, false);  // key:注意初始化
        auto self = [&](auto &&self){
            if (path.size() == len) {
                res.emplace_back(path);
                return ;
            }
            for (int i = 0; i < len; ++i) {
                // 有效的重复元素 && 前一个元素未被使用
                // 保证相同元素同层中只有第一个被使用
                if (i > 0 && candidate[i] == candidate[i-1] && used[i-1] == false) 
                    continue;
               if (used[i] == false) {
                    used[i] = true;
                    path.emplace_back(candidate[i]);
                    self(self);
                    used[i] = false;
                    path.pop_back();
               }
            }
        };
    
        self(self);
        return res;
    }
    
    // 哈希表处理重复解
    vector<vector<int>> permuteUnique(vector<int>& candidate) {
        const int len = candidate.size();
        // 去重
        unordered_map<int, int> umap;
        for (auto &i : candidate) ++umap[i];
        // 回溯算法
        vector<vector<int> > res;
        vector<int> path;
        auto self = [&](auto &&self, int pos){
            // 递归出口
            if (pos == len) {
                res.push_back(path);
                return ;
            }
            for (auto &i : umap) {
                if (i.second == 0) continue;
                path.push_back(i.first);
                --i.second;
                self(self, pos+1);
                path.pop_back();
                ++i.second;
            }
        };
        self(self, 0);
        return res;
    }
    

HOT200回溯相关题目

39. 组合总和
  1. 题目
    • 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回
    • candidates 中的 同一个 数字可以 无限制重复被选取
    • 输入:candidates = [2,3,5], target = 4
    • 输出:[[2,2]]
      在这里插入图片描述
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
	vector<vector<int>> res;
	vector<int> path;
	auto self =  [&](auto &&self, int pos, int sum){
	    // 结束条件
	    if (sum > target) return ;
	    if (sum == target) {
	        res.push_back(path);
	        return ;
	    }
	    // 路径回溯
	    for (int i = pos; i < candidates.size(); ++i) {
	        sum += candidates[i];
	        path.push_back(candidates[i]);
	        self(self, i, sum);	// key: 不用i+1表示可重复读取当前值
	        sum -= candidates[i];
	        path.pop_back();
	    }
	};
	self(self, 0, 0);
	return res;
}
40. 组合总和 II
  1. 题目
    • 给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
    • 输入: candidates = [2,5,2,1,2], target = 5,
    • 输出:[ [1,2,2], [5] ]
  2. 代码
    在这里插入图片描述
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    const int len = candidates.size();
    sort(candidates.begin(), candidates.end());
    // 回溯部分
    vector<int> path;
    vector<vector<int>> res;
    vector<bool> used(len, false);
    int sum = 0;
    auto self = [&](auto &&self, int pos){
        // 结点剪枝
        if (sum == target) {
            res.emplace_back(path);
            return ;
        }

        for (int i = pos; i < len; ++i) {
            // 分叉剪枝: 性能高一些
            if (sum + candidates[i] > target) continue;
            if (i > 0 && candidates[i] == candidates[i-1] && used[i-1] == false) 
                continue;
            if (used[i] == true) continue;
            used[i] = true;
            path.emplace_back(candidates[i]);
            sum += candidates[i];
            self(self, i+1);    // i+1表示每个元素不重复使用
            sum -= candidates[i];
            path.pop_back();
            used[i] = false;
        
        }
    };
    
    self(self, 0);
    return res;
}
93. 复原 IP 地址
  1. 题目
    • 给定一个只包含数字的字符串 s ,用以表示一个 IP 地址,返回所有可能的有效 IP 地址,这些地址可以通过在 s 中插入 ‘.’ 来形成
    • 输入:s = “25525511135”
    • 输出:[“255.255.11.135”,“255.255.111.35”]

在这里插入图片描述

vector<string> restoreIpAddresses(string s) {
  const int len = s.size();
  // 判断字符串s在左闭又闭区间[start, end]所组成的数字是否合法
  auto is_valid = [](const string& s, int start, int end) {
      cout << start <<' ' <<  end << endl;
       
      if (start > end) {
          return false;
      }
      if (s[start] == '0' && start != end) // 0开头的数字不合法
          return false;
      
      int num = 0;
      for (int i = start; i <= end; i++) {
          if (s[i] > '9' || s[i] < '0') { // 遇到非数字字符不合法
              return false;
          }
          num = num * 10 + (s[i] - '0');
          if (num > 255) { // 如果大于255了不合法
              return false;
          }
      }
   return true;
};
131. 分割回文串
  1. 131. 分割回文串
    • 获取[startIndex,i]在s中的子串s.substr(startIndex, i - startIndex + 1)
    // 判断是否为回文字符串
    bool isPalindrome(const string& s, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            if (s[i] != s[j]) {
                return false;
            }
        }
        return true;
    }
    // 基本的回溯
    vector<vector<string>> result;
    vector<string> path; // 放已经回文的子串
    void backtracking (const string& s, int startIndex) {
        // 如果起始位置已经大于s的大小,说明已经找到了一组分割方案了
        if (startIndex >= s.size()) {
            result.push_back(path);
            return;
        }
        for (int i = startIndex; i < s.size(); i++) {
        	// 剪枝与枝的延长
            if (isPalindrome(s, startIndex, i)) {   // 是回文子串
                // 获取[startIndex,i]在s中的子串
                string str = s.substr(startIndex, i - startIndex + 1);
                path.push_back(str);
            } else {  // 不是回文,跳过
                continue;
            }
            backtracking(s, i + 1); // 寻找i+1为起始位置的子串
            path.pop_back(); // 回溯过程,弹出本次已经填在的子串
        }
    }
    
    
    vector<vector<string>> partition(string s) {
        result.clear();
        path.clear();
        backtracking(s, 0);
        return result;
    }
    

1005. K 次取反后最大化的数组和
  1. 1005. K 次取反后最大化的数组和
    • sort的使用:第三个参数为自定义的排序队则,在头文件#include
    • accumulate的使用:第三个参数为累加的初值,在头文件include
    static bool cmp(int a, int b) {
        return abs(a) > abs(b);// 绝对值的从大到小进行排序
    }
    int largestSumAfterKNegations(vector<int>& A, int K) {
    	// 将容器内的元素按照绝对值从大到小进行排序
        sort(A.begin(), A.end(), cmp); 
        // 在K>0的情况下,将负值按照绝对值从大到小依次取反
        for (int i = 0; i < A.size(); i++) { 
            if (A[i] < 0 && K > 0) {
                A[i] *= -1;
                K--;
            }
        }
        // 如果K为奇数,将最小的正数取反
        if (K % 2 == 1) 
        	A[A.size() - 1] *= -1; 
       	// 求和
        return accumulate(A.begin(),A.end(),0);
        // 第三个参数为累加的初值,在头文件include<numeric>
    }
    

少年,我观你骨骼清奇,颖悟绝伦,必成人中龙凤。
不如点赞·收藏·关注一波

🚩点此跳转到首行↩︎

参考博客

  1. 「代码随想录」47. 全排列 II:【彻底理解排列中的去重问题】详解
  2. codetop

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/206393.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

恒驰服务 | 华为云云上运维服务offering

恒驰运维服务主要针对运维要求高或自身运维能力有限的客户&#xff0c;通过服务增购的形式&#xff0c;提供运维服务以协助客户做好云上资源运维管理&#xff0c;规避业务风险&#xff0c;降低运维开销&#xff0c;提升客户业务稳定性。 适用场景&#xff1a; 如何保障业务稳定…

音乐播放器Swinsian mac功能介绍

Swinsian mac是一款音乐播放器&#xff0c;它的特点是轻量级、快速、易用。Swinsian支持多种音频格式&#xff0c;包括MP3、AAC、FLAC、WAV等。它还具有iTunes集成功能&#xff0c;可以自动导入iTunes音乐库中的音乐&#xff0c;并支持智能播放列表、标签编辑、自定义快捷键等功…

ssh连接docker容器处理备忘

1、查看容器ip&#xff0c;记下来之后要用 docker inspect elastic | grep IPAddress 2、使用root进入docker容器 docker exec -it -u root elastic /bin/bash 3、安装openssh #更新apt apt-get update#安装ssh client apt-get install openssh-client#安装ssh server apt-…

Ps:用好钢笔工具

使用钢笔工具时&#xff0c;应随时注意鼠标指针的形状。 ◆ ◆ ◆ 基本操作方法 1、绘制闭合路径 路径绘制结束时回到起点即可创建闭合路径。 2、绘制开放路径 想结束绘制时&#xff0c;按住 Ctrl 键点击画布空白处&#xff0c;或者&#xff0c;直接按 Esc 键&#xff0c;即可…

STM32的看门狗原理和示例代码

看门狗基础&#xff1a; STM32微控制器上的看门狗主要有两种类型&#xff1a;独立看门狗&#xff08;IWDG&#xff09;和窗口看门狗&#xff08;WWDG&#xff09;&#xff0c;这两者都是用于监控系统运行状态的机制&#xff0c;但它们在实现和应用上有一些区别&#xff1a; 独立…

docker buildx跨架构构建笔记(x86_64构建下构建aarch64镜像)

docker buildx跨架构构建(x86_64构建aarch64镜像) 文章目录 docker buildx跨架构构建(x86_64构建aarch64镜像)简介第一步 先交叉编译一个aarch64的HelloWorld程序。准备一个用于跨架构的Dockerfile文件使用docker buildx命令构建aarch64架构的镜像。查看镜像具体详细信息&#…

建堆的时间复杂度和堆排序

文章目录 建堆的时间复杂度向下调整建堆向上调整建堆 堆排序实现 建堆的时间复杂度 下面都以建大堆演示 向下调整建堆 void Adjustdown(HPDataType* a, int size,int parent) {int child parent * 2 1;while (child < size){if (child1<size&&a[child 1] &…

【shell】正则表达式和AWK

一.正则表达式 通配符匹配文件&#xff08;而且是已存在的文件&#xff09; 基本正则表达式扩展正则表达式 可以使用 man 手册帮助 正则表达式&#xff1a;匹配的是文章中的字符 通配符&#xff1a;匹配的是文件名 任意单个字符 1.元字符&#xff08;字符匹配&…

【2023CANN训练营第二季】——Ascend C算子调用及实验演示

自定义算子调用方式 完成自定义算子的开发部署后&#xff0c;可以通过单算子调用的方式来验证单算子的功能。单算子调用有API执行和模型执行两种方式&#xff1a; 单算子API执行&#xff1a;基于C语言的API执行算子&#xff0c;无需提供单算子描述文件进行离线模型的转换&…

IDEA性能优化的相关配置

有时候会发现idea用起来特别卡&#xff0c;你会发现不是整个电脑卡&#xff0c;而是idea用起来卡。这时候就需要对idea做一下性能优化了。 首先我们把idea的内存调出来&#xff1a;可以右击idea底部然后点这个Memory Indicator&#xff0c;然后就能看到idea使用的内存了。 为什…

传统算法:使用 Pygame 实现选择排序

使用 Pygame 模块实现了选择排序的动画演示。首先,它生成一个包含随机整数的数组,并通过 Pygame 在屏幕上绘制这个数组的条形图。接着,通过选择排序算法对数组进行排序,动画效果可视化每一步的排序过程。在排序的过程中,程序找到未排序部分的最小元素,并将其与未排序部分…

wyler水平仪维修WYLER倾角仪维修CH-8405

瑞士WYLER电子水平仪维修&#xff1b;BIueCLINO倾斜度测量仪维修&#xff1b;wyler电子倾角仪维修。 水平仪常见故障及处理方法 1、 仪表通电不工作。 A、检查仪表220V电源端子接线是否正确 B、检查仪表电容是否熔断&#xff1b; C、拧下仪表后的固定螺钉&#xff0c;将表…

群晖NAS配置之搭建WordPress个人博客站点

群晖NAS配置之搭建WordPress个人博客站点 之前写了一些ngrok和frp给群晖nas做内网穿透&#xff0c;今天分享一下在群晖nas下安装wordpress的教程。 WordPress是一个开源的内容管理系统&#xff08;CMS&#xff09;&#xff0c;最初是用来搭建博客的&#xff0c;但后来发展成为…

transformer模型和Multi-Head Attention

参考英文文献&#xff1a; Understanding and Coding the Self-Attention Mechanism of Large Language Models From Scratch Transformer Block 弄懂Transformer Layer 和Transformer Block的关系后&#xff0c;豁然开朗_MengYa_DreamZ的博客-CSDN博客 https://www.tensorf…

RocketMQ-RocketMQ快速实战及集群原理

一、MQ简介 ​ MQ&#xff1a;MessageQueue&#xff0c;消息队列。是在互联网中使用非常广泛的一系列服务中间件。 这个词可以分两个部分来看&#xff0c;一是Message&#xff1a;消息。消息是在不同进程之间传递的数据。这些进程可以部署在同一台机器上&#xff0c;也可以分布…

seata集成springboot的一些错误小计

1 seata依赖没找到 dependencies.dependency.version for com.alibaba.cloud:spring-cloud-starter-alibaba-seata:jar is missing. line 126, column 21错误原因:未指定具体的seata版本 解决 <!-- https://mvnrepository.com/artifact/com.alibaba.cloud/spring-cloud-st…

Echarts 柱状图添加标记 最大值 最小值 平均值

标记 最大值 最小值 series: [//图表配置项 如大小&#xff0c;图表类型{name: 图例,type: bar,//图表类型data: [{value: 500,time: 2012-11-12},{value: 454,time: 2020-5-17},{value: 544,time: 2022-1-22},{value: 877,time: 2013-1-30}, {value: 877,time: 2012-11-12}] …

魔珐科技:3D虚拟人AIGC原生产品,助力全新商业机遇

11月28日-29日&#xff0c;WISE2023 商业之王大会在北京国际会议中心成功举办。此次大会以“太阳照常升起&#xff08;The Sun Always Rises&#xff09;”为主题&#xff0c;活动汇聚了全商业领域知名企业&#xff0c;围绕前沿趋势&#xff0c;共话商业创新之策。 在本次论坛…

基于Python Flask 的全流程全栈项目自己的实战心得

我基于Python Flask框架开发全流程全栈项目的实战经验和心得。我将介绍整个项目的架构设计、前后端交互、数据库管理以及部署等方面&#xff0c;并提供具体的代码示例。通过这个实例项目&#xff0c;你将学习到如何使用Flask构建一个完整的Web应用&#xff0c;并了解一些常见的…