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

从0开始刷剑指Offer

剑指Offer题解

剑指 Offer 11. 旋转数组的最小数字

思路: 二分O(logn)

class Solution {public int stockManagement(int[] stock) {int l = 0;int r = stock.length - 1;while(l < r && stock[0] == stock[r]) r --;if(stock[r] >= stock[l]) return stock[0];while(l < r) {int mid = l + r >> 1;if(stock[mid] < stock[0]) r = mid;else l = mid + 1;}return stock[l];}
}

剑指 Offer 12. 矩阵中的路径

思路: 回溯O(n23k)

class Solution {int[] dx = new int[] {-1, 0, 1, 0};int[] dy = new int[] {0, 1, 0, -1};public boolean wordPuzzle(char[][] grid, String target) {char[] words = target.toCharArray();for(int i = 0; i < grid.length; i ++) {for(int j = 0; j < grid[i].length; j ++) {if(dfs(grid, words, i, j, 0)) return true;}}return false;}boolean dfs(char[][] grid, char[] target, int i, int j, int k) {if(i >= grid.length || i < 0 || j >= grid[0].length || j < 0 || grid[i][j] != target[k]) {return false;}if(k == target.length - 1) return true;grid[i][j] = '.';for(int num = 0; num < 4; num ++) {int a = i + dx[num];int b = j + dy[num]; if(dfs(grid, target, a, b, k + 1)) return true;}grid[i][j] = target[k];return false;}
}

剑指 Offer 13. 机器人的运动范围

思路一: 宽搜O(nm)

class Solution {int[] dx = new int[]{-1, 0, 1, 0};int[] dy = new int[]{0, 1, 0, -1};public int wardrobeFinishing(int m, int n, int k) {if(m == 0 || n == 0) return 0;Queue<int[]> q = new LinkedList<>();boolean[][] visited = new boolean[m][n];q.add(new int[]{0, 0});int cnt = 0;while(!q.isEmpty()) {int[] t = q.poll();int x = t[0];int y = t[1];if(visited[x][y] || getSum(x, y) > k) continue;cnt ++;visited[x][y] = true;for(int i = 0; i < 4; i ++) {int a = x + dx[i];int b = y + dy[i];if(a >= 0 && a < m && b >= 0 && b < n) {q.add(new int[]{a, b});}}}return cnt;}int getSum(int x, int y) {int s = 0;while(x != 0) {s += x % 10;x = x / 10;}while(y != 0) {s += y % 10;y = y / 10;}return s;}
}

思路二: 深搜O(nm)

class Solution {int m, n, cnt;boolean[][] visited;public int wardrobeFinishing(int m, int n, int cnt) {this.m = m;this.n = n;this.cnt = cnt;this.visited = new boolean[m][n];return dfs(0, 0, 0, 0);}public int dfs(int i, int j, int si, int sj) {if(i >= m || j >= n || cnt < si + sj || visited[i][j]) return 0;visited[i][j] =true;return 1 + dfs(i + 1, j, (i + 1) % 10 != 0 ? si + 1 : si - 8, sj) + dfs(i, j + 1, si, (j + 1) % 10 != 0 ? sj + 1 : sj - 8);}
}

剑指 Offer 14- I. 剪绳子

思路: 贪心O(n)

class Solution {public int cuttingBamboo(int n) {if(n <= 3) return n - 1;int res = 1;if(n % 3 == 1) {res = 4;n -= 4;}else if(n % 3 == 2) {res = 2;n -= 2;}while(n > 0) {res = (res * 3) % 1000000007;n -= 3;}return res;}
}

剑指 Offer 14- II. 剪绳子 II

思路: 贪心O(n) 同上

class Solution {public int cuttingBamboo(int n) {if(n < 4) return n - 1;long res = 1;if(n % 3 == 1) {res = 4;n -= 4;}else if(n % 3 == 2) {res = 2;n -= 2;}while(n > 0) {res = (res * 3) % 1000000007; //循环求余n -= 3;}return (int)res;}
}

剑指 Offer 15. 二进制中1的个数

思路一: 逐位判断O(logn)

public class Solution {// you need to treat n as an unsigned valuepublic int hammingWeight(int n) {int res = 0;while(n != 0) {res += n & 1;n >>>= 1; //无符号右移}return res;}
}

思路二: 末位置0法O(logn)

public class Solution {public int hammingWeight(int n) {int res = 0;while(n != 0) {res++;n &= n - 1;}return res;}
}

思路三: 末位移除法O(logn)

public class Solution {// you need to treat n as an unsigned valuepublic int hammingWeight(int n) {int res = 0;while(n != 0) {n -= n & -n;res ++;}return res;}
}

剑指 Offer 16. 数值的整数次方

思路一:暴力O(n) 超出时间限制

class Solution {public double myPow(double x, int n) {if(n == 0) return 1.0;long N = n;return N >= 0 ? Mul(x, N) * 1.0 : 1.0 / Mul(x, -N);}public double Mul(double x, long b) {double temp = x;while(b -- > 1) {x *= temp;}return x;}
}

思路二:快速幂O(logn)

class Solution {public double myPow(double x, int n) {long N = n;return N >= 0 ? quickMul(x, N) * 1.0 : 1.0 / quickMul(x, -N);}public double quickMul(double x, long b) {double res = 1;while (b > 0) {if((b & 1) > 0) {res *= x;} b >>= 1;x *= x;}return res;}
}

剑指 Offer 17. 打印从1到最大的n位数

思路一:模拟O(n)

class Solution {public int[] countNumbers(int cnt) {int end = (int)Math.pow(10, cnt) - 1;int[] res = new int[end];for(int i = 0; i < end; i ++) {res[i] = i + 1;}return res;}
}

思路二:递归全排列O(10cnt)

class Solution {int[] res;int nine = 0; int count = 0; int start; int cnt;char[] num, loop = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};public int[] countNumbers(int cnt) {this.cnt = cnt;res = new int[(int)Math.pow(10, cnt) - 1];num = new char[cnt];start = cnt - 1;dfs(0);return res;}void dfs(int x) {// if (x == cnt) { //x是指的是num数组的位数String s = String.valueOf(num).substring(start);if(!s.equals("0")) res[count ++] = Integer.parseInt(s);if(cnt - start == nine) start --;//刚开始,cnt - start = 1, 当个位等于9时,nine = 1, start --;return;//因为这一步返回了,所以dfs继续下去,nine --;}for(char i : loop) {if(i == '9') nine ++;num[x] = i;dfs(x + 1);}nine --;}
}

剑指 Offer 18. 删除链表的节点

思路: (链表, 遍历) O(n)

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) { val = x; }* }*/
class Solution {public ListNode deleteNode(ListNode head, int val) {ListNode dummy = head;if(dummy.val == val) dummy = dummy.next;while (head != null && head.next != null) {if(head.next.val == val) {head.next = head.next.next;}head = head.next;} return dummy;}
}

剑指 Offer 19. 正则表达式匹配

思路: 动态规划O(nm)

class Solution {public boolean articleMatch(String s, String p) {int m = s.length() + 1, n = p.length() + 1;boolean[][] dp = new boolean[m][n];dp[0][0] = true;for(int j = 2; j < n; j += 2)dp[0][j] = dp[0][j - 2] && p.charAt(j - 1) == '*';//第一行初始化为0,因为s初始化是0for(int i = 1; i < m; i++) {for(int j = 1; j < n; j++) {dp[i][j] = p.charAt(j - 1) == '*' ?dp[i][j - 2] || dp[i - 1][j] && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.') :dp[i - 1][j - 1] && (p.charAt(j - 1) == '.' || s.charAt(i - 1) == p.charAt(j - 1));}}return dp[m - 1][n - 1];}
}

剑指 Offer 20. 表示数值的字符串

**思路: (模拟,字符串处理)O(n) **

class Solution {public boolean validNumber(String s) {if(s.length() <= 0 || s == null ) {return false;}char[] res = s.trim().toCharArray();int len = res.length;boolean isNumber = false;boolean isE = false;boolean isDot = false;for(int i = 0; i < len; i ++ ){if(res[i] >= '0' && res[i] <= '9') {isNumber = true;}else  if(res[i] == '.') {if(isDot == true || isE == true) {return false;}isDot = true;}else if(res[i] == 'e' || res[i] == 'E') {if(isE == true || !isNumber ) {return false;}isE = true;isNumber = false;}else  if(res[i] == '-' || res[i] == '+') {if(i!=0 && res[i-1] != 'e' && res[i-1] != 'E'){return false;}}else  return false;}return isNumber;}
}

相关文章:

从0开始刷剑指Offer

剑指Offer题解 剑指 Offer 11. 旋转数组的最小数字 思路: 二分O(logn) class Solution {public int stockManagement(int[] stock) {int l 0;int r stock.length - 1;while(l < r && stock[0] stock[r]) r --;if(stock[r] > stock[l]) return stock[0];whi…...

使用Java语言中的算法输出杨辉三角形

一、算法思想 创建一个名为YanghuiTest的类,然后创建二维数组&#xff0c;然后遍历二维数组的第一层&#xff0c;然后初始化第二层数组的大小&#xff0c;然后遍历第二层数组&#xff0c;然后将两侧的数组元素赋为1&#xff0c;然后其它数值通过公式计算&#xff0c;最后可以输…...

人工智能_机器学习071_SVM支持向量机_人脸识别算法_LFW人脸数据加载_与理解---人工智能工作笔记0111

然后我们继续来看 这里有个lfw_home可以看到这个数据是,包含了人脸数据 然后我们继续看,在我们的顶你用户目录下,如果安装了,sklearn就会有这样一个目录, scikit_learn_data目录,这个里面可以看到 可以看到这个文件夹中有个 lfw_home文件夹是对.zip文件夹的解压,这个下载以后…...

Java 8中流Stream API详解

先给个示例&#xff0c;展示Java 8流API的优势 假设我们有以下任务&#xff1a; 给定一个字符串列表&#xff0c;我们需要执行以下操作&#xff1a; 筛选出所有以"A"开头的字符串。 将这些字符串转换为大写。 对这些字符串按照长度进行排序。 最后&#xff0c;将…...

通过 xlsx 解析上传excel的数据

一、前言 在前端开发中&#xff0c;特别是在后台管理系统中&#xff0c;导入数据&#xff08;上传excel&#xff09;到后端是是否常见的功能&#xff1b;而一般的实现方式都是通过接口将excel上传到后端&#xff0c;再有后端进行数据解析并做后续操作。 今天&#xff0c;来记录…...

Flink系列之:JDBC SQL 连接器

Flink系列之&#xff1a;JDBC SQL 连接器 一、JDBC SQL 连接器二、依赖三、创建 JDBC 表四、连接器参数五、键处理六、分区扫描七、Lookup Cache八、幂等写入九、JDBC Catalog十、JDBC Catalog 的使用十一、JDBC Catalog for PostgreSQL十二、JDBC Catalog for MySQL十三、数据…...

OpenCV与YOLO学习与研究指南

引言 OpenCV是一个开源的计算机视觉和机器学习软件库&#xff0c;而YOLO&#xff08;You Only Look Once&#xff09;是一个流行的实时对象检测系统。对于大学生和初学者而言&#xff0c;掌握这两项技术将大大提升他们在图像处理和机器视觉领域的能力。 基础知识储备 在深入…...

hive中map相关函数总结

目录 hive官方函数解释示例实战 hive官方函数解释 hive官网函数大全地址&#xff1a; hive官网函数大全地址 Return TypeNameDescriptionmapmap(key1, value1, key2, value2, …)Creates a map with the given key/value pairs.arraymap_values(Map<K.V>)Returns an un…...

HttpServletRequestWrapper、HttpServletResponseWrapper结合 过滤器 实现接口的加解密、国际化

目录 一、HttpServletRequestWrapper代码 二、HttpServletRequestWrapper代码 三、加解密过滤器代码 四、国际化过滤器代码 一、HttpServletRequestWrapper代码 package com.vteam.uap.security.httpWrapper;import jakarta.servlet.ReadListener; import jakarta.servlet.…...

最大通关数

洛洛和晶晶计划一起挑战峡谷深渊&#xff0c;峡谷左右有不同数量的关卡&#xff0c;每个关卡需要不同的紫水晶通关&#xff0c;用给定的紫水晶依次通过最多的关卡。 (笔记模板由python脚本于2023年12月23日 12:16:50创建&#xff0c;本篇笔记适合熟悉贪心算法的coder翻阅) 【学…...

MySQL中EXPLAIN关键字解释

什么是MySQL的索引 索引是帮助MySQL高效获取数据的数据结构 MySQL再存储数据之外&#xff0c;数据库系统中还维护者满足特定查找算法的数据结构&#xff0c;这些数据结构以某种引用表中的数据&#xff0c;这样我们就可以通过数据结构上实现的高级查找算法来快速…...

初始JavaScript详解【精选】

Hi i,m JinXiang ⭐ 前言 ⭐ 本篇文章主要介绍初始JavaScript以及部分理论知识 &#x1f349;欢迎点赞 &#x1f44d; 收藏 ⭐留言评论 &#x1f4dd;私信必回哟&#x1f601; &#x1f349;博主收将持续更新学习记录获&#xff0c;友友们有任何问题可以在评论区留言 目录 ⭐…...

计数排序,基数排序及排序总结

稳定性&#xff1a;当要排序的数组有相同数据时&#xff0c;排序后相同数据的相对位置不变&#xff0c;则称该排序算法稳定&#xff0c;否则即为不稳定. 在这里我在说说计数排序吧&#xff0c;计数排序就是将给定数组中的数进行计数&#xff0c;在从小到大依次输出即可。简单过…...

【LeetCode】459. 重复的子字符串(KMP2.0)

今日学习的文章链接和视频链接 leetcode题目地址&#xff1a;459. 重复的子字符串 代码随想录题解地址&#xff1a;代码随想录 题目简介 给定一个非空的字符串 s &#xff0c;检查是否可以通过由它的一个子串重复多次构成。 看到题目的第一想法(可以贴代码&#xff09; 1.…...

CSS(五) -- 动效实现(立体盒子旋转-四方体+正六边)

一. 四面立体旋转 正方形旋转 小程序中 wxss中 <!-- 背景 --><view class"dragon"><!--旋转物体位置--><view class"dragon-position"><!--旋转 加透视 有立体的感觉--><view class"d-parent"><view …...

Win10使用OpenSSL生成证书的详细步骤(NodeJS Https服务器源码)

远程开启硬件权限&#xff0c;会用到SSL证书。 以下是Win10系统下用OpenSSL生成测试用证书的步骤。 Step 1. 下载OpenSSL,一般选择64位的MSI Win32/Win64 OpenSSL Installer for Windows - Shining Light Productions 一路点下来&#xff0c;如果后续请你捐款&#xff…...

sql_lab之sqli中的堆叠型注入(less-38)

堆叠注入&#xff08;less-38&#xff09; 1.判断注入类型 http://127.0.0.3/less-38/?id1 and 12 -- s 没有回显 http://127.0.0.3/less-38/?id1 and 11 -- s 有回显 则说明是单字节’注入 2.查询字段数 http://127.0.0.3/less-38/?id1 order by 4 -- s 报错 http:/…...

第5章-第3节-Java中对象的封装性以及局部变量、this、static

1、局部变量 【问题1】&#xff1a;什么是局部变量&#xff1f; 答&#xff1a;定义在局部位置的变量就是局部变量。 【问题2】&#xff1a;什么是局部位置&#xff1f; 答&#xff1a;方法的形参位置、方法体的内部。 【位置关系图】&#xff1a; class Xxx { //成员位…...

IP应用场景的规划

IP地址作为互联网通信的基石&#xff0c;在现代社会中扮演着至关重要的角色。本文将深入探讨IP地址在不同应用场景中的规划与拓展&#xff0c;探讨其在网络通信、安全、商业、医疗和智能城市等领域的关键作用与未来发展趋势。 IP地址的基本原理 IP地址是分配给网络上设备的数…...

27 redis 的 sentinel 集群

前言 redis 的哨兵的相关业务功能的实现 哨兵的主要作用是 检测 redis 主从集群中的 master 是否挂掉, 单个哨兵节点识别 master 下线为主管下线, 超过 quorum 个 哨兵节点 认为 master 挂掉, 识别为 客观下线 然后做 failover 的相关处理, 重新选举 master 节点 我们这里…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲

文章目录 前言第一部分&#xff1a;体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分&#xff1a;体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...

CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝

目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为&#xff1a;一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...

宇树科技,改名了!

提到国内具身智能和机器人领域的代表企业&#xff0c;那宇树科技&#xff08;Unitree&#xff09;必须名列其榜。 最近&#xff0c;宇树科技的一项新变动消息在业界引发了不少关注和讨论&#xff0c;即&#xff1a; 宇树向其合作伙伴发布了一封公司名称变更函称&#xff0c;因…...