分治法 Divide and Conquer

1.分治法

分治法(Divide and Conquer)是一种常见的算法设计思想,它将一个大问题分解成若干个子问题,递归地解决每个子问题,最后将子问题的解合并起来得到整个问题的解。分治法通常包含三个步骤:

  • 1. Divide:将问题分解成若干个子问题。
  • 2. Conquer:递归地解决每个子问题。
  • 3. Combine:将子问题的解合并起来得到整个问题的解。

分治法的主要思想是将问题分解成若干个相互独立的子问题,通过递归地解决每个子问题,最后将子问题的解合并起来得到整个问题的解。这种思想可以应用于许多问题的解法中,如排序、搜索、图论、数学计算等等。

一些常见的使用分治法的算法包括:归并排序、快速排序、二分搜索、线性时间选择、Karatsuba 算法等等。

2.练习题

1)

力扣https://leetcode.cn/problems/different-ways-to-add-parentheses/解题思路:

依次遍历字符串的每个字符,如果是运算符,就递归计算左边和右边的值。

class Solution {
public:
    vector<int> diffWaysToCompute(string expression) {
        int n = expression.size();
       
        vector<int> res;
        
        for(int i=0;i<n;i++){
            char c = expression[i];
            if(c=='+'||c=='-'||c=='*'){
                vector<int> left = diffWaysToCompute(expression.substr(0,i));
                vector<int> right = diffWaysToCompute(expression.substr(i+1));
                for(auto l:left){
                    for(auto r:right){
                        switch(c){
                            case '+':   res.push_back(l+r);
                                        break;
                            case '-':   res.push_back(l-r);
                                        break;
                            case '*':   res.push_back(l*r);
                                        break;

                        }
                    }
                }
            }
        }

        if(res.empty()) res.push_back(stoi(expression));
        return res;
        
    }

    
};

2)

力扣icon-default.png?t=N6B9https://leetcode.cn/problems/beautiful-array/description/

解题思路:

首先确定一点,怎么满足这个条件:

  • 对于每个 0 <= i < j < n ,均不存在下标 ki < k < j)使得 2 * nums[k] == nums[i] + nums[j] 。

最简单的方法就是让右边的nums[i] + nums[j] 这个表达式的值为奇数,因为2 * nums[k]肯定是偶数。这样我们可以假设i<j,且nums[i]为奇数,nums[j]为偶数。也就是让数组左边为奇数,右边为偶数。

又因为如果A是漂亮数组,那么a*A+b还是漂亮数组。

所有我们可以用分治法,将问题从大到小拆解,先满足每个长度为1、2、3......的数组都是漂亮数组,这样最后长度为n的数组也是漂亮数组。

代码:

class Solution {
public:
    vector<int> beautifulArray(int n) {
        vector<int> res(n,1);
        part(0,n-1,res);
        return res;
    }

    void part(int left, int right, vector<int>& res){
        if(left>=right) return;
        int mid = left + (right-left)/2;
        part(left, mid, res);
        part(mid+1, right, res);
        for(int i=left;i<=mid;i++){
            res[i] = 2*res[i]-1;
        }
        for(int i=mid+1;i<=right;i++){
            res[i] = 2*res[i];
        }
        


    }
};

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

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

相关文章

2023年7月第4周大模型荟萃

2023年7月第4周大模型荟萃 2023.7.31版权声明&#xff1a;本文为博主chszs的原创文章&#xff0c;未经博主允许不得转载。 1、Cerebras推出全球最强AI超算 AI芯片初创公司Cerebras Systems和总部位于阿联酋的技术控股集团G42于7月20日宣布&#xff0c;携手打造一个由互联的超…

Docker 阿里云容器镜像服务

阿里云-容器镜像服务ACR 将本地/服务器docker image&#xff08;镜像&#xff09;推送到 阿里云容器镜像服务仓库 1. 在容器镜像服务ACR中创建个人实例 2. 进入个人实例 > 命名空间 创建命名空间 3. 进入个人实例 > 镜像仓库 创建镜像仓库 4. 进入镜像仓库 > 基本信…

CHI中的error处理

Error Handling Error types 包含两种sub-packet级别的error, 和两种packe级别的error; Packet level error Data Error, DERR □ 访问的地址是正确的&#xff0c;但是访问的数据有错误&#xff1b;通常是在数据崩溃的时候使用&#xff0c;例如ECC&#xf…

汽车销售企业消费税,增值税高怎么合理解决?

《税筹顾问》专注于园区招商、企业税务筹划&#xff0c;合理合规助力企业节税&#xff01; 汽车行业一直处于炙手可热的阶段&#xff0c;这是因为个人或者家庭用车的需求在不断攀升&#xff0c;同时随着新能源的技术进一步应用到汽车领域&#xff0c;一度实现了汽车销量的翻倍。…

Java读取及生成pb文件并转换jsonString

Java读取及生成pb文件并转换jsonString 1. 效果图2. 原理2.1 Protocol Buffers是什么2.2 支持的语言2.3 根据.proto生成.java2.4 初始化及构建pb&#xff0c;读取&#xff0c;转jsonString 3. 源码3.1 address.proto3.2 PbParseUtil.java 参考 读取pb及生成pb文件pb文件转换jso…

【Unity细节】关于NotImplementedException: The method or operation is not implemented

&#x1f468;‍&#x1f4bb;个人主页&#xff1a;元宇宙-秩沅 hallo 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! 本文由 秩沅 原创 收录于专栏&#xff1a;unity细节和bug ⭐关于NotImplementedException: The method or operation is not implemented.⭐…

中药配方煎药-亿发智能中药汤剂煎煮系统,智慧中药房的数字化升级

随着中药的普及&#xff0c;在治病、养生等方面都发挥这积极作用&#xff0c;但中药煎煮过程繁琐&#xff0c;如果有所差错将会影响药品的药性。为了满足当今用户对中药的需求&#xff0c;增强生产效率和业务水平&#xff0c;亿发中药煎配智能管理系统应运而生&#xff0c;为用…

机器学习深度学习——多层感知机的从零开始实现

&#x1f468;‍&#x1f393;作者简介&#xff1a;一位即将上大四&#xff0c;正专攻机器学习的保研er &#x1f30c;上期文章&#xff1a;机器学习&&深度学习——多层感知机 &#x1f4da;订阅专栏&#xff1a;机器学习&&深度学习 希望文章对你们有所帮助 为…

Linux Day03

一、基础命令(在Linux Day02基础上补充) 1.10 find find 搜索路径 -name 文件名 按文件名字搜索 find 搜索路径 -cmin -n 搜索过去n分钟内修改的文件 find 搜索路径 -ctime -n搜索过去n分钟内修改的文件 1&#xff09;按文件名字 2&#xff09;按时间 1.11 grep 在文件中过…

【Ajax】笔记-同源策略

同源策略(Same-Origin Policy)&#xff0c;是浏览器的一种安全策略 同源&#xff08;即url相同&#xff09;&#xff1a;协议、域名、端口号 必须完全相同。&#xff08;请求是来自同一个服务&#xff09; 跨域&#xff1a;违背了同源策略&#xff0c;即跨域。 ajax请求是遵循…

软件测试面试题——接口自动化测试怎么做?

面试过程中&#xff0c;也问了该问题&#xff0c;以下是自己的回答&#xff1a; 接口自动化测试&#xff0c;之前做过&#xff0c;第一个版本是用jmeter 做的&#xff0c;1 主要是将P0级别的功能接口梳理出来&#xff0c;根据业务流抓包获取相关接口&#xff0c;并在jmeter中跑…

BUU CODE REVIEW 1

BUU CODE REVIEW 1 考点&#xff1a;PHP变量引用 源码直接给了 <?phphighlight_file(__FILE__);class BUU {public $correct "";public $input "";public function __destruct() {try {$this->correct base64_encode(uniqid());if($this->c…

回归预测 | MATLAB实现SO-CNN-BiLSTM蛇群算法优化卷积双向长短期记忆神经网络多输入单输出回归预测

回归预测 | MATLAB实现SO-CNN-BiLSTM蛇群算法优化卷积双向长短期记忆神经网络多输入单输出回归预测 目录 回归预测 | MATLAB实现SO-CNN-BiLSTM蛇群算法优化卷积双向长短期记忆神经网络多输入单输出回归预测预测效果基本介绍模型描述程序设计参考资料 预测效果 基本介绍 Matlab实…

git stash clear清空本地暂存代码

git stash clear清空本地暂存代码 git stash 或者 git stash list 查看本地暂存的代码。 清除本地暂存的代码修改&#xff1a; git stash clear git回退代码仓库版本_git回退到之前的版本会影响本地代码嘛_zhangphil的博客-CSDN博客git回退代码版本_git回退到之前的版本会影…

没有软件测试经验,怎样面试测试工作?

纸上得来终觉浅&#xff0c;所有的面试经验都是要自己去体验&#xff0c;他人说来的都是他人的经验。 同样&#xff0c;每个公司&#xff0c;面对的面试官都会有不同的问题&#xff0c;当然这些问题可能会大同小异&#xff0c;但是也需要自己总结得出&#xff0c;这样的经验不…

文件上传到远程服务器

文件上传 一、上传文件到本地 package com.ruoyi.system.knowledgebase;import com.ruoyi.common.annotation.Anonymous; import com.ruoyi.common.core.domain.AjaxResult; import com.ruoyi.system.domain.SzKnowledge; import com.ruoyi.system.service.ISzKnowledgeServi…

基于物联网、视频监控与AI视觉技术的智慧电厂项目智能化改造方案

一、项目背景 现阶段&#xff0c;电力行业很多企业都在部署摄像头对电力巡检现场状况进行远程监控&#xff0c;但是存在人工查看费时、疲劳、出现问题无法第一时间发现等管理弊端&#xff0c;而且安全事件主要依靠人工经验判断分析、管控&#xff0c;效率十分低下。 为解决上述…

vue生命周期的传统写法和setup语法糖写法

&#x1f642;博主&#xff1a;小猫娃来啦 &#x1f642;文章核心&#xff1a;vue生命周期的传统写法和setup语法糖写法 文章目录 setup语法糖设计目的Vue2 与Vue3的生命周期对比vue3钩子函数beforeCreated和created被封装传统写法和语法糖写法的对比 setup语法糖设计目的 <…

容器部署jenkins定时构建于本地时间不一致

1. Dockerfile FROM jenkins/jenkins:2.411-jdk11 USER root #以下生成密钥方式为旧格式&#xff0c;因为新格式暂不能被"Publish over SSH--->Jenkins SSH Key"功能识别 RUN ssh-keygen -q -m PEM -t rsa -b 2048 -N -f /root/.ssh/id_rsa ADD ./apache-maven…

【Boost搜索引擎项目】

文章目录 一、项目流程二、项目展示 一、项目流程 1.编写数据去标签模块–parser.cc 将去标签之后干净文档以title\3content\3url\ntitle\3content\3url\n格式放入同一文件中。 2.建立索引模块–index.hpp 读取处理好的行文本文件进行分词、权重计算等操作&#xff0c;在内存中…