当前位置: 首页 > news >正文

剑指offer12 矩阵中的路径 13 机器人的运动范围 34.二叉树中和为某一值得路径

在这里插入图片描述

class Solution {
public:bool exist(vector<vector<char>>& board, string word) {int row=board.size(),col=board[0].size();int index=0,i=0,j=0;if(word.size()>row*col) return 0;//vector<vector<int>> visit[row][col];//标记当前位置有没有被访问过vector<vector<int>> visit(row,vector<int>(col));bool flag=1;while(i<row&j<col){cout<<"board[i][j]: "<<board[i][j]<<endl;if(board[i][j]==word[index]){flag=1;if(index==word.size()-1) return 1;cout<<word[index]<<endl;index++;visit[i][j]=1;if(i-1>=0&&board[i-1][j]==word[index]&&visit[i-1][j]!=1){cout<<"上"<<endl;i=i-1;j=j;}else if(i+1<row&&board[i+1][j]==word[index]&&visit[i+1][j]!=1){cout<<"下"<<endl;i=i+1;j=j;}else if(j-1>=0&&board[i][j-1]==word[index]&&visit[i][j-1]!=1){cout<<"左"<<endl;i=i;j=j-1;}else if(j+1<col&&board[i][j+1]==word[index]&&visit[i][j+1]!=1){cout<<"右"<<endl;i=i;j=j+1;}}else {if(j==col-1&&i<row)//如果到了一行的最后面就调转到下一行 大前提是找不到word[index]相等{cout<<"最末尾的 "<<board[i][j]<<endl;i++;j=0;}else j++;}}  return 0;}
};

//写的有点问题,暂时想不到怎么改,先放着,通过用例71/83 卡住的是abcd 但是改了又有问题
无语 看了 答案 都写不对 在类成员里面定义了row和col 就不要重复定义了 不然不知道为什么就开始发疯

class Solution {
public:bool exist(vector<vector<char>>& board, string word) {rows=board.size();cols=board[0].size();for(int i=0;i<rows;i++){for(int j=0;j<cols;j++){if (dfs(board,word,i,j,0)) return true;}}return false;}
private:int rows,cols;bool dfs(vector<vector<char>>& board,string word,int i,int j,int k){if(i>=rows||i<0||j>=cols||j<0||board[i][j]!=word[k]) return false;if(k==word.size()-1) return true;board[i][j]='\0';bool res=dfs(board,word,i+1,j,k+1)||dfs(board,word,i-1,j,k+1)||dfs(board,word,i,j+1,k+1)||dfs(board,word,i,j-1,k+1);board[i][j]=word[k];return res;}
};

在这里插入图片描述
先贴出蠢货写出来的东西 审题也审不明白 机器人只能上下左右走 不能一行一行遍历 菜鸟总是这样 自己把自己搞破防
通过用列46/51

class Solution {
public:int movingCount(int m, int n, int k) {int index=0;for(int i=0;i<m;i++){if(add(i)>k) break;for(int j=0;j<n;j++){if(add(j)>k) break;int sum=add(i)+add(j);if(sum<=k) {index++;cout<<sum<<endl;}}}return index;}
private:int add(int x){int sum=0,num=0;while(x){num=x%10;x=x/10;sum+=num;}return sum;}
};

问题出在哪里呢!!!! 就是比如【10,0】虽然数位之和等于1,但是无法通过【9,0】或者其他走过去,假设k=1的话,也就是他妈的他有障碍物啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊
aaaa继续做就是要判断边界条件啊啊啊啊啊啊啊啊啊啊啊啊就是判断他是否能进入4个相邻的格子
首先0,0必定可以嗷,check[0,0]置为1。0,0能走到0,1和1,0,那对于0,1和1,0两个点来说,就是判断他们的上面i-1和左边j-1是否可以走,如果可以那就可以从左边和上面分别走过来,能走到当前这个点就置为1,然后左边和上面能走的点都走了之后,还有两个方向没有判断 ,再来判断能不能从右边(i+1)走到左边,下面(i+1)走到上面,如果能走到当前点,就置为1,最后有多少个1,就有多少个机器人能走的格子。

class Solution {
public:int movingCount(int m, int n, int k) {int index=0;int check[m][n];//不能直接写check[m][n]也不能check[m][n]={0},第一次无法保证元素全为0 ,第二个会报错memset(check,0,sizeof(check));//memset进行内存清零,可以将一块内存设置为指定的值check[0][0]=1;for(int i=0;i<m;i++){for(int j=0;j<n;j++){int sum=add(i)+add(j);if(sum<=k) {if(i-1>=0&&check[i-1][j]==1||j-1>=0&&check[i][j-1]==1) check[i][j]=1;}}}for(int i=0;i<m;i++){for(int j=0;j<n;j++){int sum=add(i)+add(j);if(sum<=k) {if(i+1<m&&check[i+1][j]==1||j+1<n&&check[i][j+1]==1) check[i][j]=1;}}}for(int i=0;i<m;i++){for(int j=0;j<n;j++){int sum=add(i)+add(j);if(check[i][j]) {index++;}}}return index;}
private:int add(int x){int sum=0,num=0;while(x){num=x%10;x=x/10;sum+=num;}return sum;}
};

在这里插入图片描述

和上题目类似,属于典型的搜索&回溯算法
先了解一下BFS模板
不需要当前遍历到哪一层,BFS模板

while queue 不空cur=queue.front();queue.pop();for 结点 in cur的所有相邻节点if 该节点有效且没被访问过:queue.push(该结点)

需要确定遍历到哪一层,比如之前写过一题打印二叉链表

level=0
while queue不空:size=queue.size()while(size--){cur=queue.pop();for 结点 in cur的所有相邻结点:if 该节点有效且未被访问过:queue.push(该节点)}level++;

直接使用模板

算了dfs

class Solution {
public:int sum(int x){//计算数位和int count = 0;while(x){count += x%10;x /= 10;}return count;}int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};//左上右下int res = 0;int m , n , k;vector<vector<bool>>st;int movingCount(int _m, int _n, int _k) {
//m行n列
//不能进入行坐标和列坐标的"数位"之和大于k的格子
//          i  +  j             > km = _m, n = _n, k = _k;vector<vector<bool>>_st(m,vector<bool>(n));//初始化st = _st;return dfs(0,0);}int dfs(int x, int y){st[x][y]=true;res++;for(int i = 0 ;i < 4 ; i++){int a = x+dx[i] , b = y + dy[i];if(a >= 0 && a < m && b >= 0 && b < n && !st[a][b] && sum(a)+sum(b)<=k){dfs(a,b);//那么我们就渲染一下}}return res;}};

DFS解法

class Solution {
public:int movingCount(int m, int n, int k) {vector<vector<int>> check(m,vector<int>(n,0));//球球你了祖宗啊记住这个定义方式吧dfs(check,m,n,k,0,0);return result;}private:int result=0;int add(int x){int sum=0,num=0;while(x){num=x%10;x=x/10;sum+=num;}return sum;}void dfs(vector<vector<int>> &check,int m, int n, int k,int x,int y){int sum=add(x)+add(y);if(x<0||x>=m||y<0||y>=n||check[x][y]==1||sum>k) return ;result++;check[x][y]=1;dfs(check,m,n,k,x+1,y);dfs(check,m,n,k,x,y+1);}
};

BFS解法就见鬼去吧 不想写队列啊啊啊啊
在这里插入图片描述

class Solution {
public:vector<vector<int>> pathSum(TreeNode* root, int target) {if(!root) return result;dfs(root,target);return result;}
private:vector<vector<int>> result;vector<int> subresult;void dfs(TreeNode* root,int target){if(!root) return ;subresult.push_back(root->val);target-=root->val;if(root->left==nullptr&&root->right==nullptr&&target==0){result.push_back(subresult);}dfs(root->left,target);dfs(root->right,target);subresult.pop_back();//回溯}
};

相关文章:

剑指offer12 矩阵中的路径 13 机器人的运动范围 34.二叉树中和为某一值得路径

class Solution { public:bool exist(vector<vector<char>>& board, string word) {int rowboard.size(),colboard[0].size();int index0,i0,j0;if(word.size()>row*col) return 0;//vector<vector<int>> visit[row][col];//标记当前位置有没有…...

Pushgateway+Prometheus监控Flink

思路方案 FlinkMtrics->pushgateway->prometheus->grafnana->altermanager 方案 : Flink任务先将数据推到pushgateway。然后pushgateway将值推送到prometheus,最后grafana展示prometheus中的值, 去这个 https://prometheus.io/download/ 下载最新的 Prometheu…...

OpenCV图像处理-视频分割静态背景-MOG/MOG2/GMG

视频分割背景 1.概念介绍2. 函数介绍MOG算法MOG2算法GMG算法 原视频获取链接 1.概念介绍 视频背景扣除原理&#xff1a;视频是一组连续的帧&#xff08;一幅幅图组成&#xff09;&#xff0c;帧与帧之间关系密切(GOP/group of picture)&#xff0c;在GOP中&#xff0c;背景几乎…...

nginx 反向代理浅谈

前言 通常情况下&#xff0c;客户端向Web服务器发送请求&#xff0c;Web服务器响应请求并返回数据。而在反向代理中&#xff0c;客户端的请求不直接发送到Web服务器&#xff0c;而是发送到反向代理服务器。反向代理服务器会将请求转发给真实的Web服务器&#xff0c;Web服务器响…...

【概率预测】对风力发电进行短期概率预测的分析研究(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

原型设计模式go实现尝试

文章目录 前言代码结果总结 前言 本文章尝试使用go实现“原型”。 代码 package mainimport ("fmt" )// 不同原型标志枚举 type Type intconst (PROTOTYPE_1 Type iotaPROTOTYPE_2 )// 原型接口 type IPrototype interface {Clone() IPrototypeMethod(value int)P…...

链表是否有环、环长度、环起点

问题引入 如何检测一个链表是否有环&#xff0c;如果有&#xff0c;那么如何确定环的长度及起点。 引自博客&#xff1a;上述问题是一个经典问题&#xff0c;经常会在面试中被问到。我之前在杭州一家网络公司的电话面试中就很不巧的问到&#xff0c;当时是第一次遇到那个问题&…...

有效文档管理离不开这几个特点

在我们日常生活中经常会遇到各式各样的文档类型&#xff0c;想要把它们都统一管理起来也不是一件容易的事情。后来looklook就去研究怎么样可以把这一堆文档整理起来呢&#xff1f;接下来&#xff0c;looklook就从有效的文档管理展开&#xff0c;和大家分享一下&#xff01; 有效…...

爬虫-requests-cookie登录古诗文网

一、前言 1、requests简介 requests是一个很实用的Python HTTP客户端库&#xff0c;爬虫和测试服务器响应数据时经常会用到&#xff0c;它是python语言的第三方的库&#xff0c;专门用于发送HTTP请求&#xff0c;使用起来比urllib更简洁也更强大。 2、requests的安装 pip i…...

Spring Boot实践三 --数据库

一&#xff0c;使用JdbcTemplate访问MySQL数据库 1&#xff0c;确认本地已正确安装mysql 按【winr】快捷键打开运行&#xff1b;输入services.msc&#xff0c;点击【确定】&#xff1b;在打开的服务列表中查找mysql服务&#xff0c;如果没有mysql服务&#xff0c;说明本机没有…...

分布式锁漫谈

简单解释一下个人理解的分布式锁以及主要的实现手段。 文章目录 什么是分布式锁常用分布式锁实现 什么是分布式锁 以java应用举例&#xff0c;如果是单应用的情况下&#xff0c;我们通常使用synchronized或者lock进行线程锁&#xff0c;主要为了解决多线程或者高并发场景下的共…...

mac 安装 php 与 hyperf 框架依赖的扩展并启动 gptlink 项目

m系列 mac 安装 php 与 hyperf 框架依赖的扩展并启动 gptlink 项目 gptlink 项目是一个前后端一体化的 chatgpt 开源项目 gptlink 项目地址&#xff1a;https://github.com/gptlink/gptlink 安装 php 8.0 版本&#xff1a; brew install php8.0安装完成后提示如下&#xff…...

ansible中run_once的详细介绍和使用说明

在Ansible中&#xff0c;run_once是一个用于控制任务在主机组中只执行一次的关键字参数。当我们在编写Ansible任务时&#xff0c;有时候我们希望某个任务只在主机组中的某个主机上执行一次&#xff0c;而不是在每个主机上都执行。 以下是run_once参数的详细说明和用法&#xf…...

短视频矩阵系统源码开发流程​

一、视频矩阵系统源码开发流程分为以下几个步骤&#xff1a; 四、技术开发说明&#xff1a; 产品原型PRD需求文档产品交互流程图部署方式说明完整源代码源码编译方式说明三方框架和SDK使用情况说明和代码位置平台操作文档程序架构文档 一、抖音SEO矩阵系统源码开发流程分为以…...

vite+vue3 css scss PC移动布局自适应

1. 安装 postcss-pxtorem 和 autoprefixer npm install postcss-pxtorem autoprefixer --save2. vite.config.js引入并配置 import postCssPxToRem from postcss-pxtorem import autoprefixer from autoprefixerexport default defineConfig({base: ./,resolve: {alias},plug…...

BLE配对和绑定

参考&#xff1a;一篇文章带你解读蓝牙配对绑定 参考&#xff1a;BLE安全之SM剖析(1) 参考&#xff1a;BLE安全之SM剖析&#xff08;2&#xff09; 参考&#xff1a;BLE安全之SM剖析(3) 目录 前言基本概念解读Paring(配对)Bonding(绑定&#xff09;STK短期秘钥、LTK长期秘钥等 …...

无涯教程-jQuery - html( val )方法函数

html(val)方法设置每个匹配元素的html内容。此属性在XML文档上不可用。 html( val ) - 语法 selector.html( val ) 这是此方法使用的所有参数的描述- val - 这是要设置的html内容。 html( val ) - 示例 以下是一个简单的示例&#xff0c;简单说明了此方法的用法- <…...

【单链表OJ题:删除链表中等于给定值 val 的所有节点】

1.删除链表中等于给定值 val 的所有节点 题目来源 给你一个链表的头节点 head 和一个整数 val &#xff0c;请你删除链表中所有满足 Node.val val 的节点&#xff0c;并返回 新的头节点 。 /*** Definition for singly-linked list.* struct ListNode {* int val;* s…...

vue element ui web端引入百度地图,并获取经纬度

最近接到一个新需要&#xff0c;要求如下&#xff1a; 当我点击选择地址时&#xff0c;弹出百度地图&#xff0c; 效果如下图&#xff1a; 实现方法&#xff1a; 1、首先要在百度地图开放平台去申请一个账号和key 2、申请好之后&#xff0c;在项目的index.html中引入 3、…...

25.10 matlab里面的10中优化方法介绍—— 函数fmincon(matlab程序)

1.简述 关于非线性规划 非线性规划问题是指目标函数或者约束条件中包含非线性函数的规划问题。 前面我们学到的线性规划更多的是理想状况或者说只有在习题中&#xff0c;为了便于我们理解&#xff0c;引导我们进入规划模型的一种情况。相比之下&#xff0c;非线性规划会更加贴近…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)

本期内容并不是很难&#xff0c;相信大家会学的很愉快&#xff0c;当然对于有后端基础的朋友来说&#xff0c;本期内容更加容易了解&#xff0c;当然没有基础的也别担心&#xff0c;本期内容会详细解释有关内容 本期用到的软件&#xff1a;yakit&#xff08;因为经过之前好多期…...

【C++进阶篇】智能指针

C内存管理终极指南&#xff1a;智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...

【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制

目录 节点的功能承载层&#xff08;GATT/Adv&#xff09;局限性&#xff1a; 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能&#xff0c;如 Configuration …...

【Veristand】Veristand环境安装教程-Linux RT / Windows

首先声明&#xff0c;此教程是针对Simulink编译模型并导入Veristand中编写的&#xff0c;同时需要注意的是老用户编译可能用的是Veristand Model Framework&#xff0c;那个是历史版本&#xff0c;且NI不会再维护&#xff0c;新版本编译支持为VeriStand Model Generation Suppo…...

0x-3-Oracle 23 ai-sqlcl 25.1 集成安装-配置和优化

是不是受够了安装了oracle database之后sqlplus的简陋&#xff0c;无法删除无法上下翻页的苦恼。 可以安装readline和rlwrap插件的话&#xff0c;配置.bahs_profile后也能解决上下翻页这些&#xff0c;但是很多生产环境无法安装rpm包。 oracle提供了sqlcl免费许可&#xff0c…...

沙箱虚拟化技术虚拟机容器之间的关系详解

问题 沙箱、虚拟化、容器三者分开一一介绍的话我知道他们各自都是什么东西&#xff0c;但是如果把三者放在一起&#xff0c;它们之间到底什么关系&#xff1f;又有什么联系呢&#xff1f;我不是很明白&#xff01;&#xff01;&#xff01; 就比如说&#xff1a; 沙箱&#…...

ui框架-文件列表展示

ui框架-文件列表展示 介绍 UI框架的文件列表展示组件&#xff0c;可以展示文件夹&#xff0c;支持列表展示和图标展示模式。组件提供了丰富的功能和可配置选项&#xff0c;适用于文件管理、文件上传等场景。 功能特性 支持列表模式和网格模式的切换展示支持文件和文件夹的层…...

鸿蒙HarmonyOS 5军旗小游戏实现指南

1. 项目概述 本军旗小游戏基于鸿蒙HarmonyOS 5开发&#xff0c;采用DevEco Studio实现&#xff0c;包含完整的游戏逻辑和UI界面。 2. 项目结构 /src/main/java/com/example/militarychess/├── MainAbilitySlice.java // 主界面├── GameView.java // 游戏核…...