5830. 三除数

题目描述

给你一个整数n。如果n恰好有三个正除数,返回true ;否则,返回false
如果存在整数k,满足n = k*m,那么整数m就是n的一个 除数
提示:

  • 1<=n<=10^4

解题思路

这题就遍历就行

class Solution {
   
    public boolean isThree(int n) {
   
    	if(n<=2)
    		return false;
    	int i=2;
    	int flag = 0;
    	while(i<n) {
   
    		if(n%i==0) {
   
    			if(n/i!=i)
    				return false;
    			else {
   
    				flag++;
    			}
    		}
    		i++;
    	}
    	return flag==1?true:false;
    }
}

5831. 你可以工作的最大周数

题目描述

给你n个项目,编号从0n-1。同时给你一个整数数组milestones,其中每个milestones[i]表示第i个项目中的阶段任务数量。

你可以按下面两个规则参与项目中的工作:

  • 每周,你将会完成某一个项目中的恰好一个阶段任务。你每周都必须工作。
  • 连续的两周中,你不能参与并完成同一个项目中的两个阶段任务。

一旦所有项目中的全部阶段任务都完成,或者仅剩余一个阶段任务都会导致你违反上面的规则,那么你将停止工作。注意,由于这些条件的限制,你可能无法完成所有阶段任务。

返回在不违反上面规则的情况下你最多能工作多少周。
提示:

  • n==milestones.length
  • 1 <= n <= 10^5
  • 1 <= milestones[i] <= 10^9

解题思路

本来想用优先队列模拟来做,然后超时了。
之后想着最坏情况就是一个特别大,大于其他数之和。
因此只需要判断是否存在最大值Max大于其他数之和,存在则返回2*Sum+1,否则返回Sum+Max。

class Solution {
   
       public long numberOfWeeks(int[] milestones) {
   
    	int Max = 0;
    	long Sum = 0;
    	for(int n:milestones) {
   
    		Max = Math.max(Max, n);
    		Sum+=n;
    	}
    	Sum-=Max;
    	if(Max>Sum)
    		return 2*Sum+1;
    	else
    		return Sum+Max;
    }
}

5187. 收集足够苹果的最小花园周长

题目描述

给你一个用无限二维网格表示的花园,每一个整数坐标处都有一棵苹果树。整数坐标(i, j)处的苹果树有|i|+|j|个苹果。
你将会买下正中心坐标是(0, 0)的一块正方形土地,且每条边都与两条坐标轴之一平行。
给你一个整数neededApples,请你返回土地的最小周长,使得 至少 有neededApples个苹果在土地里面或者边缘上

|x|的值定义为:

  • 如果x>=0,那么值为x
  • 如果x<0,那么值为-x

解题思路

找规律题,每次增加一次,会使得每个边长增加 2 i + 1 + 4 ( i + 1 ) 2i+1+4(i+1) 2i+1+4(i+1),总个数增加 4 ∗ ( 4*( 4(上一次边长上水果和+边长长度*1 ) + 4 ∗ 2 ∗ ( )+4*2*( )+42(边长长度 + 1 ) +1) +1)

class Solution {
   
    public long minimumPerimeter(long neededApples) {
   
// int Max = 100000000;
// long[] dp = new long[Max];
// dp[1] = 5;
// 
    	long dp1 = 5;
    	long dp2 = 5;
    	int i=1;
    	long Sum = 12;
    	while(Sum<neededApples) {
   
    		dp2 = dp1+2*i+1+4*(i+1);
    		Sum = Sum+4*(dp1+2*i+1)+8*(i+1);
    		dp1 = dp2;
    		i++;
    	}
    	return 8*(i);
    }
}

5833. 统计特殊子序列的数目

题目描述

特殊序列是由正整数0,紧接着正整数1,最后正整数2组成的序列。

比方说,[0,1,2][0,0,1,1,1,2]是特殊序列。
相反,[2,1,0][1][0,1,2,0]就不是特殊序列。
给你一个数组nums包含整数012),请你返回不同特殊子序列的数目。由于答案可能很大,请你将它对10^9+7取余后返回。

一个数组的子序列是从原数组中删除零个或者若干个元素后,剩下元素不改变顺序得到的序列。如果两个子序列的下标集合不同,那么这两个子序列是不同的

解题思路

当时竞赛的时候没时间了,也没来得及多想,最后看的别人的解题思路,只觉得自己是个菜鸡。
动态规划的题目,和黄叶收集者那题很像,哎,又败在dp。
d p [ 0 ] dp[0] dp[0]记录0的子序列数目。
d p [ 1 ] dp[1] dp[1]记录01的子序列数目。
d p [ 2 ] dp[2] dp[2]记录012的子序列数目。
针对 n u m [ i ] num[i] num[i]的情况不同,进行处理

  • n u m [ i ] = 0 num[i]=0 num[i]=0时,0的子序列数目增加dp[0]+1个,因为最后一个0可以和之前所以的排列组合成子序列,单个也能组成子序列。
  • n u m [ i ] = 1 num[i]=1 num[i]=1时,01的子序列增加dp[0]+dp[1]个,因为当前1能和之前的01子序列组成01子序列,也能和0子序列组成01子序列。
  • n u m [ i ] = 2 num[i]=2 num[i]=2时,012的子序列增加dp[1]+dp[2]个,因为当前2能和之前的01子序列组成012子序列,也能和012子序列组成012子序列。
class Solution {
   
    public int countSpecialSubsequences(int[] nums) {
   
    	long[] dp = new long[3];
    	int Mod = 1000000000+7;
    	for(int i:nums) {
   
    		if(i==0) {
   
    			dp[0]+=dp[0]+1;
    		}else if(i==1){
   
    			dp[1]+=dp[0]+dp[1];
    		}else {
   
    			dp[2]+=dp[1]+dp[2];
    		}
			dp[i]%=Mod;
    	}
    	return (int) dp[2];
    }
}