当前位置：网站首页>力扣记录：剑指offer（2）——JZ13-22
力扣记录：剑指offer（2）——JZ13-22
2022-07-26 00:26:00 【Kiwi_fruit】
本次题目
JZ13 机器人的运动范围
- 动态规划DP
- 时间复杂度O(mn)，空间复杂度O(mn)
class Solution {
public int movingCount(int m, int n, int k) {
//判断特殊情况
if(k == 0) return 1;
//定义dp数组dp[i][j]表示i，j位置是否可达
//可达为1，不可达为0
int[][] dp = new int[m][n];
//初始化
dp[0][0] = 1;
//计算结果
int result = 1;
//开始遍历
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
//0，0已经计算过
if(i == 0 && j == 0) continue;
//不符合条件跳过
if(digitSum(i) + digitSum(j) > k) continue;
//上边或左边有一个可达则本位置可达
if((i - 1 >= 0 && dp[i - 1][j] == 1) || (j - 1 >= 0 && dp[i][j - 1] == 1)) dp[i][j] = 1;
//计算结果
result += dp[i][j];
}
}
//返回结果
return result;
}
//计算位数和
private int digitSum(int num){
int res = 0;
while(num != 0){
res += (num % 10);
num /= 10;
}
return res;
}
}
JZ14-I 剪绳子
- 动态规划
- 时间复杂度O(n^2)，空间复杂度O(n)
class Solution {
public int cuttingRope(int n) {
//定义dp数组dp[i]表示长度为i的绳子剪完最大值为dp[i]
int[] dp = new int[n + 1];
//初始化
dp[2] = 1;
//遍历
for(int i = 3; i <= n; i++){
for(int j = 1; j <= i / 2; j++){
//剪两段（一段为1），剪多段，剪两段（一段为j）求最大
dp[i] = Math.max(dp[i], Math.max(dp[i - j] * j, (i - j) * j));
}
}
//返回结果
return dp[n];
}
}
- 数学推导 + 贪心：把绳子尽可能分为长度为3的小段，然后是2，最后是1（1+3替换为2+2）
- 时间复杂度O(n)，空间复杂度O(1)
class Solution {
public int cuttingRope(int n) {
//判断特殊情况
if(n == 2) return 1;
if(n == 3) return 2;
//计算分成3的个数和余数
int num = n / 3;
int rem = n % 3;
//优先3
if(rem == 0) return (int)Math.pow(3, num);
//2不动
if(rem == 2) return (int)Math.pow(3, num) * 2;
//将1 + 3替换为2 + 2
return (int)Math.pow(3, num - 1) * 4;
}
}
JZ14-II 剪绳子II
- 需要取模，不能使用动态规划，直接数学推导 + 贪心，循环取余
- 时间复杂度O(n)，空间复杂度O(1)
- 定义结果为long类型
class Solution {
public int cuttingRope(int n) {
//判断特殊情况
if(n == 2) return 1;
if(n == 3) return 2;
//取模
int m = 1000000007;
//定义结果为long类型
long res = 1L;
//循环取余
while(n > 4){
res *= 3;
res = Math.floorMod(res, m);
n -= 3;
}
//n最后可能为2，3，4
return Math.floorMod(res * n, m);
}
}
JZ15 二进制中1的个数
- 暴力法，遍历二进制的每一位
- 时间复杂度O(logn)，空间复杂度O(1)
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int res = 0;
for(int i = 0; i < 32; i++){
//判断当前位是否为1
if((n & 1) == 1) res++;
n = n >>> 1;
}
return res;
}
}
- n & (n - 1)：二进制数字 n 最右边的 1 变成 0 ，其余不变（还可以判断n是否为2的幂）*
- 时间复杂度O(M)，空间复杂度O(1)，M为二进制中1的个数
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int res = 0;
while(n != 0){
res++;
//找到n最右边的1并将其改为0
n &= (n - 1);
}
return res;
}
}
JZ16 数值的整数次方
- 快速幂，迭代实现
- 时间复杂度O(logn)，空间复杂度O(1)
class Solution {
public double myPow(double x, int n) {
//判断特殊情况
if(x == 0.0) return 0.0;
if(x == 1.0) return 1.0;
//将负数幂转为正数幂计算
long N = n;
if(N < 0){
x = 1 / x;
N = -N;
}
//定义结果
double res = 1.0;
//定义每轮乘数
double mul = x;
//奇数幂多乘一个，第一N=奇数和最后一次N=1
//偶数幂只有最后一次N=1
while(N > 0){
//求余实现
// if(N % 2 == 1) res *= mul;
// mul *= mul;
// N /= 2;
//二进制实现
if((N & 1) == 1) res *= mul;
mul *= mul;
N >>= 1;
}
return res;
}
}
JZ17 打印从1到最大的n位数
- 暴力法，先求出上限，然后定义数组遍历赋值
- 时间复杂度O(10^n)，空间复杂度O(1)
class Solution {
public int[] printNumbers(int n) {
//定义结果
int res = (int)Math.pow(10, n) - 1;
//打印结果
int[] result = new int[res];
for(int i = 0; i < res; i++){
result[i] = i + 1;
}
return result;
}
}
- 大数情况，使用字符串保存数组，全排列
- 时间复杂度O(10^n)，空间复杂度O(n)
class Solution {
//定义结果
private int[] result;
//计数
private int count = 0;
public int[] printNumbers(int n) {
//初始化
result = new int[(int) Math.pow(10, n) - 1];
//i位的数
for(int i = 1; i <= n; i++){
//固定第一位，防止第一位为0
for(char first = '1'; first <= '9'; first++){
char[] num = new char[i];
//第一位存在数组下标0
num[0] = first;
//递归其他位
traverseNum(num, i, 2);
}
}
return result;
}
//递归函数，输入总共有几位，当前第几位
private void traverseNum(char[] num, int i, int n){
// //直接打印
// if(i < n){
// System.out.println(String.valueOf(num));
// return;
// }
//当前位等于总共位时字符串转int存储到结果中
if(i < n){
result[count++] = Integer.parseInt(String.valueOf(num));
return;
}
//递归下一位，第n位存在下标n-1
for(char now = '0'; now <= '9'; now++){
num[n - 1] = now;
//递归
traverseNum(num, i, n + 1);
}
}
}
JZ18 删除链表的节点
- 虚拟头节点，遍历删除
- 时间复杂度O(n)，空间复杂度O(1)
/** * 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) {
//判断特殊情况
if(head == null) return null;
//虚拟头结点
ListNode virtualHead = new ListNode(0);
virtualHead.next = head;
//当前节点和上一个节点
ListNode front = virtualHead;
ListNode now = head;
//遍历
while(now != null){
if(now.val == val){
//找到要删除的节点
front.next = now.next;
break;
}
//下一轮
front = now;
now = now.next;
}
//返回头结点
return virtualHead.next;
}
}
JZ19 正则表达式匹配
- 动态规划DP
- 时间复杂度O(mn)，空间复杂度O(mn)
class Solution {
public boolean isMatch(String s, String p) {
int m = s.length();
int n = p.length();
//定义dp数组dp[i][j]表示下标i-1（包括i-1）前的s子串和下标j-1（包括j-1）前的p子串是否匹配
boolean[][] f = new boolean[m + 1][n + 1];
//初始化
//dp[i][0] = false但是dp[0][j]可能为true
f[0][0] = true;
//遍历顺序正序
for (int i = 0; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
//j从1开始
if (p.charAt(j - 1) == '*') {
//如果j-1为*
f[i][j] = f[i][j - 2]; //s[i]和p[j - 1]不匹配
if (matches(s, p, i, j - 1)) {
//s[i]和p[j - 1]匹配
f[i][j] = f[i][j] || f[i - 1][j];
}
} else {
//如果j-1不为*
if (matches(s, p, i, j)) {
//s[i]和p[j]匹配
f[i][j] = f[i - 1][j - 1];
}
}
}
}
return f[m][n]; //返回结果
}
//匹配函数，输入两个字符串及其对应下标
public boolean matches(String s, String p, int i, int j) {
if (i == 0) {
return false;
}
if (p.charAt(j - 1) == '.') {
return true;
}
return s.charAt(i - 1) == p.charAt(j - 1);
}
}
JZ20 表示数值的字符串
- 遍历所有的情况
- 时间复杂度O(n)，空间复杂度O(1)
class Solution {
public boolean isNumber(String s) {
//遍历所有情况
//去掉字符串前后的空格
s = s.trim();
//判断是否出现e或E
boolean eNum = false;
//判断是否出现.
boolean pNum = false;
//判断是否出现整数
boolean nNum = false;
//遍历字符串
for(int i = 0; i < s.length(); i++){
if(s.charAt(i) >= '0' && s.charAt(i) <= '9'){
//该位为数字
nNum = true;
}else if(s.charAt(i) == 'e' || s.charAt(i) == 'E'){
//该位为e或E
//e只能出现一次
if(eNum) return false;
//e前要有数
if(!nNum) return false;
eNum = true;
//e后要有整数
nNum = false;
}else if(s.charAt(i) == '.'){
//该位为点
//e后不能有点
if(eNum) return false;
//最多只能有一个点
if(pNum) return false;
pNum = true;
}else if(s.charAt(i) == '+' || s.charAt(i) == '-'){
//该位为符号字符
//只能出现在开头或e后
if(i != 0 && s.charAt(i - 1) != 'e' && s.charAt(i - 1) != 'E') return false;
}else{
//其他都为非法
return false;
}
}
//判断最后是否整数
return nNum;
}
}
- 有限状态自动机*
- 时间复杂度O(n)，空间复杂度O(1)
//小数表示可省去0，-0.4 = -.4，0.4 = .4；2.、3. = 2、3，小数点前有数，后面可以不跟数代表原数
//注意e8即10的8次幂（8次方），也可以是e-7，但题目要求必须跟整数
//题目规定是数值前后可有空格，中间不能有，这个情况要考虑清楚。s：符号、d：数字
class Solution {
public boolean isNumber(String s) {
Map[] states = {
//0：规定0是初值，字符串表示数值，有4种起始状态，开头空格、符号、数字、前面没有数的小数点
//其中 开头空格 还是指向states[0]，上一位是 开头空格，下一位可以是 空格、符号、数字、前面没有数的小数点
new HashMap<>() {
{
put(' ', 0); put('s', 1); put('d', 2); put('.', 4); }},
//1：上一位是符号，符号位后面可以是 数字、前面没有数的小数点
new HashMap<>() {
{
put('d', 2); put('.', 4); }},
//2：上一位是数字，数字的下一位可以是 数字、前面有数的小数点、e、结尾空格
new HashMap<>() {
{
put('d', 2); put('.', 3); put('e', 5); put(' ', 8); }},
//3：上一位是前面有数的小数点，下一位可以是 数字、e（8.e2 = 8e2，和2的情况一样）、结尾空格
new HashMap<>() {
{
put('d', 3); put('e', 5); put(' ', 8); }},
//4：上一位是前面没有数的小数点，下一位只能是 数字（符号肯定不行，e得前面有数才行）
new HashMap<>() {
{
put('d', 3); }},
//5：上一位是e，下一位可以是 符号、数字
new HashMap<>() {
{
put('s', 6); put('d', 7); }},
//6：：上一位是e后面的符号，下一位只能是 数字
new HashMap<>() {
{
put('d', 7); }},
//7：上一位是e后面的数字，下一位可以是 数字、结尾空格
new HashMap<>() {
{
put('d', 7); put(' ', 8); }},
//8：上一位是结尾空格，下一位只能是 结尾空格
new HashMap<>() {
{
put(' ', 8); }}
};
int p = 0;
char t;
//遍历字符串，每个字符匹配对应属性并用t标记，非法字符标记？
for(char c : s.toCharArray()) {
if(c >= '0' && c <= '9') t = 'd';
else if(c == '+' || c == '-') t = 's';
else if(c == 'e' || c == 'E') t = 'e';
else if(c == '.' || c == ' ') t = c;
else t = '?';
//当前字符标记和任何一种当前规定格式都不匹配，直接返回false
if(!states[p].containsKey(t)) return false;
//更新当前字符的规定格式，进入下一个规定的Map数组
p = (int)states[p].get(t);
}
//2（正、负整数）、3（正、负小数）、7（科学计数法）、8（前三种形式的结尾加上空格）
//只有这四种才是正确的结尾
return p == 2 || p == 3 || p == 7 || p == 8;
}
}
JZ21 调整数组顺序使奇数位于偶数前面
- 双指针，左指针找偶数，右指针找奇数，然后交换
- 时间复杂度O(n)，空间复杂度O(1)
class Solution {
public int[] exchange(int[] nums) {
//双指针
int leng = nums.length;
if(leng <= 1) return nums;
//左指针找偶数
int left = 0;
//右指针找奇数
int right = leng - 1;
//临时变量用于交换
int temp = 0;
//指针相遇结束
while(left < right){
while(left < right && nums[left] % 2 == 1) left++;
while(left < right && nums[right] % 2 == 0) right--;
//交换
temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
//返回结果
return nums;
}
}
JZ22 链表中倒数第k个节点
- 双指针，左指针指向倒数第k个节点，右指针指向null（相差k+1），然后返回左指针指向节点
- 时间复杂度O(n)，空间复杂度O(1)
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
//双指针
ListNode left = new ListNode(0);
ListNode right = new ListNode(0);
left.next = head;
right.next = head;
//相差k+1
while(k >= 0){
right = right.next;
k--;
}
//右指针指到最后一个节点时
//左指针指向倒数第k个节点
while(right != null){
right = right.next;
left = left.next;
}
//返回左指针指向节点
return left.next;
}
}
边栏推荐
- 对“DOF: A Demand-oriented Framework for ImageDenoising“的理解
- 【Redis】① Redis 的介绍、Redis 的安装
- Research on the integrated data quality management system and technical framework under the scenario of data circulation and transaction
- Use localdate class to complete calendar design
- [directory] nodejs, NPM, yarn, bug
- IP核：PLL
- 对比7种分布式事务方案，还是偏爱阿里开源的Seata(原理+实战)
- 基于SEIR模型的网络医疗众筹传播建模与仿真分析
- Revision of Journal of Computational Physics
- SQL time splicing problem, splicing recovery automatically truncated by the system
猜你喜欢
Super super super realistic digital people! Keep you on the air 24 hours a day
【Redis】② Redis通用命令；Redis 为什么这么快？；Redis 的数据类型
Research on the integrated data quality management system and technical framework under the scenario of data circulation and transaction
PC website realizes wechat code scanning login function (II)
【无标题】如何实现可插拔配置？
Redis killed twelve questions. How many questions can you carry?
Research on text classification of e-commerce comments based on mffmb
![[redis] ③ data elimination strategy, pipeline command, publish and subscribe](/img/80/7caeb24380ea026aa8153f2169dfdd.png)
[redis] ③ data elimination strategy, pipeline command, publish and subscribe
二进制表示--2的幂
Mwec: a new Chinese word discovery method based on multi semantic word vector
随机推荐
Leetcode 笔记 20. 有效的括号
攻防世界web题-favorit_number
The way of understanding JS: write a perfect combination inheritance (Es5)
SQL time splicing problem, splicing recovery automatically truncated by the system
Pikachu靶机通关和源码分析
Research on text classification of e-commerce comments based on mffmb
Sliding window_
牛血清白蛋白修饰牛红细胞超氧化物歧化酶SOD/叶酸偶联2-ME白蛋白纳米粒的制备
一个List到底能存多大的数据呢？
Super super super realistic digital people! Keep you on the air 24 hours a day
对比7种分布式事务方案，还是偏爱阿里开源的Seata(原理+实战)
P4047 [JSOI2010]部落划分
@The difference between requestparam and @pathvariable annotations
解决背景图设置100%铺满时，缩放浏览器出现水平滚动条时，滚动条超出的部分背景图没有铺满的问题
你还在掐表算时间复杂度?
[redis] ③ data elimination strategy, pipeline command, publish and subscribe
[redis] ① introduction and installation of redis
【目录】mqtt、nodejs项目
寻找命令find和locate
Nodejs learning resources