从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的类,然后创建二维数组,然后遍历二维数组的第一层,然后初始化第二层数组的大小,然后遍历第二层数组,然后将两侧的数组元素赋为1,然后其它数值通过公式计算,最后可以输…...

人工智能_机器学习071_SVM支持向量机_人脸识别算法_LFW人脸数据加载_与理解---人工智能工作笔记0111
然后我们继续来看 这里有个lfw_home可以看到这个数据是,包含了人脸数据 然后我们继续看,在我们的顶你用户目录下,如果安装了,sklearn就会有这样一个目录, scikit_learn_data目录,这个里面可以看到 可以看到这个文件夹中有个 lfw_home文件夹是对.zip文件夹的解压,这个下载以后…...
Java 8中流Stream API详解
先给个示例,展示Java 8流API的优势 假设我们有以下任务: 给定一个字符串列表,我们需要执行以下操作: 筛选出所有以"A"开头的字符串。 将这些字符串转换为大写。 对这些字符串按照长度进行排序。 最后,将…...
通过 xlsx 解析上传excel的数据
一、前言 在前端开发中,特别是在后台管理系统中,导入数据(上传excel)到后端是是否常见的功能;而一般的实现方式都是通过接口将excel上传到后端,再有后端进行数据解析并做后续操作。 今天,来记录…...
Flink系列之:JDBC SQL 连接器
Flink系列之:JDBC SQL 连接器 一、JDBC SQL 连接器二、依赖三、创建 JDBC 表四、连接器参数五、键处理六、分区扫描七、Lookup Cache八、幂等写入九、JDBC Catalog十、JDBC Catalog 的使用十一、JDBC Catalog for PostgreSQL十二、JDBC Catalog for MySQL十三、数据…...

OpenCV与YOLO学习与研究指南
引言 OpenCV是一个开源的计算机视觉和机器学习软件库,而YOLO(You Only Look Once)是一个流行的实时对象检测系统。对于大学生和初学者而言,掌握这两项技术将大大提升他们在图像处理和机器视觉领域的能力。 基础知识储备 在深入…...
hive中map相关函数总结
目录 hive官方函数解释示例实战 hive官方函数解释 hive官网函数大全地址: 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.…...

最大通关数
洛洛和晶晶计划一起挑战峡谷深渊,峡谷左右有不同数量的关卡,每个关卡需要不同的紫水晶通关,用给定的紫水晶依次通过最多的关卡。 (笔记模板由python脚本于2023年12月23日 12:16:50创建,本篇笔记适合熟悉贪心算法的coder翻阅) 【学…...
MySQL中EXPLAIN关键字解释
什么是MySQL的索引 索引是帮助MySQL高效获取数据的数据结构 MySQL再存储数据之外,数据库系统中还维护者满足特定查找算法的数据结构,这些数据结构以某种引用表中的数据,这样我们就可以通过数据结构上实现的高级查找算法来快速…...
初始JavaScript详解【精选】
Hi i,m JinXiang ⭐ 前言 ⭐ 本篇文章主要介绍初始JavaScript以及部分理论知识 🍉欢迎点赞 👍 收藏 ⭐留言评论 📝私信必回哟😁 🍉博主收将持续更新学习记录获,友友们有任何问题可以在评论区留言 目录 ⭐…...

计数排序,基数排序及排序总结
稳定性:当要排序的数组有相同数据时,排序后相同数据的相对位置不变,则称该排序算法稳定,否则即为不稳定. 在这里我在说说计数排序吧,计数排序就是将给定数组中的数进行计数,在从小到大依次输出即可。简单过…...
【LeetCode】459. 重复的子字符串(KMP2.0)
今日学习的文章链接和视频链接 leetcode题目地址:459. 重复的子字符串 代码随想录题解地址:代码随想录 题目简介 给定一个非空的字符串 s ,检查是否可以通过由它的一个子串重复多次构成。 看到题目的第一想法(可以贴代码) 1.…...

CSS(五) -- 动效实现(立体盒子旋转-四方体+正六边)
一. 四面立体旋转 正方形旋转 小程序中 wxss中 <!-- 背景 --><view class"dragon"><!--旋转物体位置--><view class"dragon-position"><!--旋转 加透视 有立体的感觉--><view class"d-parent"><view …...
Win10使用OpenSSL生成证书的详细步骤(NodeJS Https服务器源码)
远程开启硬件权限,会用到SSL证书。 以下是Win10系统下用OpenSSL生成测试用证书的步骤。 Step 1. 下载OpenSSL,一般选择64位的MSI Win32/Win64 OpenSSL Installer for Windows - Shining Light Productions 一路点下来,如果后续请你捐款ÿ…...

sql_lab之sqli中的堆叠型注入(less-38)
堆叠注入(less-38) 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】:什么是局部变量? 答:定义在局部位置的变量就是局部变量。 【问题2】:什么是局部位置? 答:方法的形参位置、方法体的内部。 【位置关系图】: class Xxx { //成员位…...

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

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

接口测试中缓存处理策略
在接口测试中,缓存处理策略是一个关键环节,直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性,避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明: 一、缓存处理的核…...
利用ngx_stream_return_module构建简易 TCP/UDP 响应网关
一、模块概述 ngx_stream_return_module 提供了一个极简的指令: return <value>;在收到客户端连接后,立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量(如 $time_iso8601、$remote_addr 等)&a…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例
文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...
大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计
随着大语言模型(LLM)参数规模的增长,推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长,而KV缓存的内存消耗可能高达数十GB(例如Llama2-7B处理100K token时需50GB内存&a…...

如何在网页里填写 PDF 表格?
有时候,你可能希望用户能在你的网站上填写 PDF 表单。然而,这件事并不简单,因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件,但原生并不支持编辑或填写它们。更糟的是,如果你想收集表单数据ÿ…...

无人机侦测与反制技术的进展与应用
国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机(无人驾驶飞行器,UAV)技术的快速发展,其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统,无人机的“黑飞”&…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化
缓存架构 代码结构 代码详情 功能点: 多级缓存,先查本地缓存,再查Redis,最后才查数据库热点数据重建逻辑使用分布式锁,二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...
Linux系统部署KES
1、安装准备 1.版本说明V008R006C009B0014 V008:是version产品的大版本。 R006:是release产品特性版本。 C009:是通用版 B0014:是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存:1GB 以上 硬盘…...

02.运算符
目录 什么是运算符 算术运算符 1.基本四则运算符 2.增量运算符 3.自增/自减运算符 关系运算符 逻辑运算符 &&:逻辑与 ||:逻辑或 !:逻辑非 短路求值 位运算符 按位与&: 按位或 | 按位取反~ …...

对象回调初步研究
_OBJECT_TYPE结构分析 在介绍什么是对象回调前,首先要熟悉下结构 以我们上篇线程回调介绍过的导出的PsProcessType 结构为例,用_OBJECT_TYPE这个结构来解析它,0x80处就是今天要介绍的回调链表,但是先不着急,先把目光…...