算法学习day30

ops/2024/12/21 22:08:24/

一、最短无序连续子数组(贪心)

给你一个整数数组 nums ,你需要找出一个 连续子数组 ,如果对这个子数组进行升序排序,那么整个数组都会变为升序排序。请你找出符合题意的 最短 子数组,并输出它的长度。

输入:nums = [2,6,4,8,10,9,15]
输出:5
解释:你只需要对 [6, 4, 8, 10, 9] 进行升序排序,那么整个表都会变为升序排序。
思路:

我们如何去找到无序子数组的左右边界?从而计算出它的长度。

1.右边界需要满足的条件是:右边界往右的数都大于无序子数组中的最大值,如果小于的话,就要更新endIndex;如果大于的话就更新max;

2.左边界需要满足的条件是:  左边界往左的数都小于无序子数组中的最小值,如果大于的话,就要更新startIndex;如果小于的话就更新min;

3.那我们使用两次for循环分别去寻找endIndex,和startIndex;

int max=nums[0];
for(int i=1;i<nums.length;i++){if(nums[i]<max)endIndex=i;max=Math.max(max,nums[i]);
}
int min=nums[nums.length-1];
for(int j=nums.length-2;j>=0;j--){if(nums[j]>min)startIndex=j;min=Math.min(min,nums[j]);
}
return endIndex-startIndex==nums.length-1?0:endIndex-startIndex+1;
代码:
class Solution {public int findUnsortedSubarray(int[] nums) {if (nums == null || nums.length < 2) {return 0;}int startIndex = nums.length-1;int endIndex = 0;int max = nums[0];int min = nums[startIndex];// max是这段范围中的最大值,要是在max的右边并且还比max小的 就要到数组里面进行排序for (int i = 1; i < nums.length; i++) {if (max > nums[i])endIndex = i;max = Math.max(max, nums[i]);}// min是这段范围中的最小值,要是在min的左边并且还比min大的 就要到min里面排序for (int i = nums.length-2; i >= 0; i--) {if (min < nums[i])startIndex = i;min = Math.min(min, nums[i]);}System.out.println("endIndex:" + endIndex + "startIndex:" + startIndex);return startIndex - endIndex == nums.length - 1 ? 0 : endIndex - startIndex + 1;}
}

二、乘积最大子数组(贪心/dp)

给你一个整数数组 nums ,请你找出数组中乘积最大的非空连续

子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。

解法一:贪心

数组中可能存在负数,一旦出现负数,之前最大值就变成最小值了;如果负数出现偶数次,那么最小的值就变成最大值了。因此我们要记录一下最小值。

变量imax,imin,res;对数组进行遍历。

1.如果nums[i]>0,更新imax和imin;

imax=Math.max(imax,nums[i]*imax);

imin=Math.min(imim,nums[i]*imin);

2.如果nums[i]<0,此时要交换imax和imin的值,如果是第一次交换imax就=1了,imin=之前的imax*nums[i]了

class Solution {public int maxProduct(int[] nums) {//当前节点的最大值 当前节点的最小值(如果出现负数的话) 最小值*负数=最大值int res=Integer.MIN_VALUE,imin=1,imax=1;for(int i=0;i<nums.length;i++){if(nums[i]<0){//将imin和imax的数值交换 本来imax=imin*nums[i];现在imax=imax*nums[i];int temp=imin;imin=imax;imax=temp;}imax=Math.max(nums[i],imax*nums[i]);imin=Math.min(nums[i],imin*nums[i]);res=Math.max(res,imax);}return res;}
}
解法二:动态规划

1.初始化:dp[i][j]:i:以下标i为结尾的数组的乘积的最大值和最小值。dp[i][0]:最小值;dp[i][1]:最大值

2.递推公式:

if(nums[i]>0)

dp[i][0]=Math.min(nums[i],dp[i-1][0]*nums[i]);//dp[i-1][0]可能是负数 前面经历过nums[i]<0

dp[i][1]=Math.max(nums[i],dp[i-1][1]*nums[i]);

nums[i]<0

dp[i][0]=Math.min(nums[i],dp[i-1][1]*nums[i]);//要求最小值,dp[i-1][1](下标到i-1的最大值)*nums[i]

dp[i][1]=Math.max(nums[i],dp[i-1][0]*nums[i]);//要求最大值,dp[i-1][0]*nums[i]

3.初始化;dp[0][0]=nums[0];dp[0][1]=nums[1];

4.从1开始遍历;
 

class Solution {public int maxProduct(int[] nums) {//当前节点的最大值 当前节点的最小值(如果出现负数的话) 最小值*负数=最大值int[][] dp=new int[nums.length][2];dp[0][0]=nums[0];//初始化dp数组 以0结尾的最小值dp[0][1]=nums[0];for(int i=1;i<nums.length;i++){if(nums[i]>0){dp[i][0]=Math.min(nums[i],dp[i-1][0]*nums[i]);dp[i][1]=Math.max(nums[i],dp[i-1][1]*nums[i]);}else{dp[i][0]=Math.min(nums[i],dp[i-1][1]*nums[i]);dp[i][1]=Math.max(nums[i],dp[i-1][0]*nums[i]);}}int max=Integer.MIN_VALUE;for(int[] arr:dp){max=Math.max(max,arr[1]);}return max;}
}

三、递增的三元子序列

给你一个整数数组 nums ,判断这个数组中是否存在长度为 3 的递增子序列。

如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ,使得 nums[i] < nums[j] < nums[k] ,返回 true ;否则,返回 false 。

输入:nums = [2,1,5,0,4,6]
输出:true
解释:三元组 (3, 4, 5) 满足题意,因为 nums[3] == 0 < nums[4] == 4 < nums[5] == 6
题意:如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ,使得 nums[i] < nums[j] < nums[k] ,返回 true ;否则,返回 false 。
思路:

在数组中寻找是否出现了a<b<c;

如果找到比a小的就更新a;

找到比a大比b小的就更新b;

如果遇到第三种情况就说明遇到了a<b<c;

eg:2 1 5 0 4 6 

a:2 a:1 b:5 a:0 b:4 c:6

有人会问: 如果a\b遇到更小的值,更新之后顺序不就变了吗?其实是否存在这样的递增三元子序列是看b。a变小之后,b就有变更小的可能。这样出现三元组的概率更大。

代码:
class Solution {public boolean increasingTriplet(int[] nums) {int a = Integer.MAX_VALUE;int b = Integer.MAX_VALUE;for(int num:nums){if(num<=a)a=num;else if(num<=b)b=num;else return true;}return false;}
}

四、整数拆分(二刷 dp/数学)

给定一个正整数 n ,将其拆分为 k 个 正整数 的和( k >= 2 ),并使这些整数的乘积最大化。

输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
解法一:数学

推论一: 若拆分的数量 a 确定, 则 各拆分数字相等时 ,乘积最大。

推论二: 将数字 n 尽可能以因子 3 等分时,乘积最大。

当数字n<=3时,返回n-1;此时分成1,n-1; 1*(n-1)=n-1;

当数字>3

1.余数为0时,返回pow(3,n/3);

2.余数为1时,将一个3拆成2,1  返回pow(3,n/3-1)*2*2

3.余数为2时,返回pow(3,n/3)*2;

class Solution {public int integerBreak(int n) {if(n<=3)return n-1;int a=n/3,b=n%3;if(b==0)return (int)Math.pow(3,a);else if(b==1)return (int)Math.pow(3,a-1)*4;else return (int)Math.pow(3,a)*2;}
}
解法二:dp动态规划

遇到一个数字,可以把它拆分为两个数字或者多个数字。

5:可以分成2,3/也可以分成  2 1 2; 

就要在这些可能的拆分情况中取最大值;

五部曲:

1.dp[i]:表示将i拆分成n数之和的最大乘积

2.递推公式:dp[i]=Math.max(dp[i],Math.max(i*j,i*dp[j]));

3.初始化:dp[0]=0;dp[1]=0;

4.遍历:int i=2;i<=n;i++{

              int j=1;j<=i;j++{

                          }

}

class Solution {public int integerBreak(int n) {//dp[i]:拆分i的乘积的最大化//dp[i]=Math.max(i*j,dp[i]*dp[j]);int[] dp=new int[n+1];dp[0]=dp[1]=1;for(int i=2;i<=n;i++){for(int j=1;j<i;j++){dp[i]=Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));}}return dp[n];}
}

五、132模式(还有123模式)

给你一个整数数组 nums ,数组中共有 n 个整数。132 模式的子序列 由三个整数 nums[i]nums[j] 和 nums[k] 组成,并同时满足:i < j < k 和 nums[i] < nums[k] < nums[j] 。

如果 nums 中存在 132 模式的子序列 ,返回 true ;否则,返回 false 。

输入:nums = [3,1,4,2]
输出:true
解释:序列中有 1 个 132 模式的子序列: [1, 4, 2] 
思路:可以倒序看,2要找一个比它大然后再找一个比它小的数字

1.比它大可以使用单调栈,单调递增栈(从栈顶到栈底是从小到大的),如果nums[i]>stack.peek();就找到了比它大的

2.比它小可以使用现行遍历,如果nums[i]<k,那么就找到了。

class Solution {public boolean find132pattern(int[] nums) {if(nums==null||nums.length<=2)return false;Stack<Integer> stack=new Stack<>();int mid=Integer.MIN_VALUE;for(int i=nums.length-1;i>=0;i--){if(nums[i]<mid)return true;while(!stack.isEmpty()&&nums[i]>stack.peek()){mid=stack.pop();}stack.push(nums[i]);}return false;        }
}
代码:


http://www.ppmy.cn/ops/91998.html

相关文章

鸿蒙应用服务开发【自定义通知角标】

自定义通知角标 介绍 本示例主要展示了设定应用的桌面图标角标的功能&#xff0c;使用ohos.notificationManager接口&#xff0c;进行桌面角标的设置&#xff0c;通知的发送&#xff0c;获取等。 效果预览 使用说明 在主界面&#xff0c;可以看到当前应用的所有消息通知&am…

基于Qt实现图片查看器

一、简介 基于Qt实现的图片查看器。支持如下功能&#xff1a; 图像放大、缩小、拖动矩形标注框显示&#xff0c;在放大缩小时&#xff0c;标注框的线宽始终保持固定宽度。 二、源码 ImgViewWidget.hpp // ImgViewWidget.hpp #pragma once #include <QImage> #includ…

Java设计模式(适配器模式)

定义 将一个类的接口转换成客户希望的另一个接口。适配器模式让那些接口不兼容的类可以一起工作。 角色 目标抽象类&#xff08;Target&#xff09;&#xff1a;目标抽象类定义客户所需的接口&#xff08;在类适配器中&#xff0c;目标抽象类只能是接口&#xff09;。 适配器类…

Shell脚本-DNS域名解析格式化

Shell脚本-DNS域名解析格式化 大家好&#xff0c;我是秋意零。 今天&#xff0c;分享一个Shell脚本。大家不一定用的上&#xff0c;但可以参考&#xff1b;再一个是可以通过下列需求进行练手&#xff0c;初学者可以试试&#xff01; 脚本还有优化的地方&#xff08;懒得改了…

【Android】ContentProvider基本概念

ContentProvider Android权限机制详解 <manifest xmlns:android"http://schemas.android.com/apk/res/android"package"com.example.broadcasttest"> <uses-permission android:name"android.permission.RECEIVE_BOOT_COMPLETED" />…

计算机网络408考研 2014

1 计算机网络408考研2014年真题解析_哔哩哔哩_bilibili 1 111 1 11

Python | Leetcode Python题解之第326题3的幂

题目&#xff1a; 题解&#xff1a; class Solution:def isPowerOfThree(self, n: int) -> bool:return n > 0 and 1162261467 % n 0

SpringMVC学习笔记---带你快速入门和复习

一、初识SpringMVC 1.1、什么是SpringMVC 1.1.1、什么是MVC MVC是一种软件架构模式&#xff08;是一种软件架构设计思想&#xff0c;不止Java开发中用到&#xff0c;其它语言也需要用到&#xff09;&#xff0c;它将应用分为三块&#xff1a; M&#xff1a;Model&#xff0…