目录

牛客.C-消减整数

力扣.最长上升子序列(dp)

牛客.最长上升子序列(二) (贪心+二分)

牛客.爱吃素

---

牛客.C-消减整数

开始的时候我还以为是什么，结果数学才是根本

import java.util.*;
public class Main{public static void main(String[]args){Scanner in=new Scanner(System.in);int n=in.nextInt();int[]a=new int[n];for(int i=0;i<n;i++){a[i]=in.nextInt();int count=0;int p=1;while(a[i]!=0){a[i]-=p;count++;if(a[i]%(2*p)==0){p=p*2;}}System.out.println(count);}}
}

力扣.最长上升子序列(dp)

经验+题目要求:

以i位置元素为结尾的所有子序列中，最长的递增子序列的长度

可以分成哪些类呢?

单独自己玩，长度为1.

情况二:    长度大于1 ，设j为i前面的数字, 0<=j<=i-1

...i-1 i   不管你前面什么样子，我的i跟着你的i-1后面

...i-2 ,i i跟着前面i-2的后面,...

0,i

注意这里面的j并非一定要化成二维数组，而是可以用来单纯的遍历数组中比i中点更小的数

nums[j]<nums[i] ->前提

class Solution {public int lengthOfLIS(int[] nums) {int n=nums.length;int []dp=new int[n];Arrays.fill(dp,1);//dp[i][j]:以i位置为结尾的子序列中，最长递增子序列的长度int max=0;for(int i=0;i<n;i++){for(int j=0;j<i;j++){if(nums[j]<nums[i]){dp[i]=Math.max(dp[j]+1,dp[i]);}}max=Math.max(max,dp[i]);}return max;}
}

牛客.最长上升子序列(二) (贪心+二分)

LIS最长上升子序列的

1.动态规划

2.贪心+二分(n*1ogn)

在保存序列的时候，只需要存最后一个元素就行了。

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** 给定数组的最长严格上升子序列的长度。* @param arr int整型一维数组 给定的数组* @return int整型*/public int LIS (int[] a) {int n=a.length;int[]dp=new int[n+1];int pos=0; //相当于指向存到哪个位置了,pos的含义是来说，这个位置是在第几个位次中//每一个数字都相当于插入到这个数组中，来看看在什么位置for(int x:a){if(pos==0||x>dp[pos]){//这句话的意思，假如第一次来，那么我们需要先++pos意思就是存到第一个位置了，然后把x放进去。此时还有一种情况，假如x特别大，大于最后一个的时候，直接新开一个dp[++pos]=x;}else{//二分快速查找插入位置 ，比如说新来了一个数字7，会把这个7放到一个较小的数字，和较大的数字中间，进而会把大的覆盖掉，这个序列是一个单调递增的序列。既然是单调递增就是有序的序列，我们要二分出插入的位置，我们要找大于等于阶段点,假如[1,3,7,5} 3(又来一个三，他会覆盖掉原先有的3)]int l=1,r=pos;while(l<r){int mid=(r+l)/2;if(dp[mid]>=x){r=mid;}else{l=mid+1;}}
//将获取到的那个位置，也就是恰好大于等于上一个多最小的覆盖原先的那个位置dp[l]=x;}}return pos;}}

牛客.爱吃素

这里可以看到，我这只通过了70，剩下的我感觉是数字太大，但是我又不知道该如何处理，所以我去看题解，发现这里还有数学的功劳

如果a>1,b>1的情况下，一个数有两个因子，他一定不是素数

假如一个数是素数，他的因子只有1和本身

所以a==1或者b==1

import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static boolean issu(long x){if(x==1){return false;}else if(x==2){return true;}else{for(int i=2;i<=Math.sqrt(x);i++){if(x%i==0){return false;}}}return true;}public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别int T=in.nextInt();long [][]ab =new long[T][2] ;for(int i=0;i<T;i++){ab[i][0]=in.nextLong();ab[i][1]=in.nextLong();if(ab[i][0]==1&&issu(ab[i][1])==true||ab[i][1]==1&&issu(ab[i][0])==true){System.out.println("YES") ;}else{System.out.println("NO");}}}
}