1，每个小孩的糖果数量是多少
有p个小孩，c个糖果，刚开始第1个小孩发一个糖果，第2个小孩发两个糖果，第p个小孩发p个糖果，如果糖果没有发完，就接着【注意】第1个小孩发p+1个糖果.....第p个小孩发2*p个糖果，如果糖果还没有发完，就继续下一轮，第1个小孩发2*p+1个糖果，...
方法一，遍历【这种方法太low了就折叠一下】
package com.cnblogs.mufasa.Main1;
import java.util.Scanner;
public class Main {
public static int[] getCandies(int c,int p){
int[] pGet=new int[p];
int preNum=1;
while (c!=0){
for(int i=0;i<p;i++){
if(preNum<c){
pGet[i]+=preNum;
c-=preNum;
preNum++;
}else {
pGet[i]+=c;
return pGet;
}
}
}
return null;
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int c=Integer.valueOf(sc.next());
int p=Integer.valueOf(sc.next());
int[] pGet=getCandies(c,p);
System.out.print("[");
for(int i=0;i<p-1;i++){
System.out.print(pGet[i]+",");
}
System.out.println(pGet[p-1]+"]");
}
}
/*
7
4
*/
View Code
方法二，数学推导【算法复杂度急速降低】除了，推理的时候复杂一些，其他都还好
package com.cnblogs.mufasa.Main1;
import java.util.Scanner;
public class Main1 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// int c = Integer.valueOf(sc.next());
// int p = Integer.valueOf(sc.next());
//0,测试
int c=45,p=4;
int lineSum=(1+p)*p/2;//1+2+3+...+p的总数
int leve=0,preCan=c;
//1,1先判断出是在第几层中断【正确】
while (true){
if(preCan<leve*p*p+lineSum){
break;
}
preCan-=(leve*p*p+lineSum);
leve++;
}
int[] pGet=new int[p];
//1,2直接算出各个小朋友持有的糖果数【还是要区分第0层与其他层的区别】
if(leve!=0){//1,2,2 非第0层中断
int temp=p*(leve-1)*leve/2;
for(int i=1;i<=p;i++){
pGet[i-1]=temp+i*leve;
}
}
int preSta=p*leve;
for(int i=1;i<=p;i++){
if(preCan<preSta+i){
pGet[i-1]+=preCan;
break;
}else {
pGet[i-1]+=(preSta+i);
}
preCan-=(preSta+i);
}
//3数据输出
System.out.print("[");
for(int i=0;i<p-1;i++){
System.out.print(pGet[i]+",");
}
System.out.println(pGet[p-1]+"]");
}
}
2，找两个数组公有的数
方法一：使用HashSet和TreeSet解决问题，但是只AC60%！！！可能是耗时太多【时间复杂度大】理解简单易懂
package com.cnblogs.mufasa.Main2;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;
import java.util.TreeSet;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
String str0=sc.next();
String str1=sc.next();
String[] strs0=str0.substring(1,str0.length()-1).split(",");
String[] strs1=str1.substring(1,str1.length()-1).split(",");
if(str0.length()<str1.length()){
String[] temp=strs0;
strs0=strs1;
strs1=temp;
}
HashSet<Integer> hs=new HashSet<>();
TreeSet<Integer> tsOut=new TreeSet<>();
for(int i=0;i<strs0.length;i++){
hs.add(Integer.valueOf(strs0[i]));
}
for(int i=0;i<strs1.length;i++){
int temp=Integer.valueOf(strs1[i]);
if(hs.contains(temp)){
tsOut.add(temp);
}
}
System.out.print("[");
for(int i=0;i<tsOut.size()-1;i++){
System.out.print(tsOut.pollFirst()+",");
}
System.out.print(tsOut.pollFirst());
System.out.println("]");
}
}
/*
[1,2,2,1,3]
[2,2,3]
[2,3]
*/
View Code
方法二：直接使用遍历进行，省略了计算hash值以及进行查找的费时操作【算法复杂度降低并且拥有两个光标进行判断】
package com.cnblogs.mufasa.Main2_1;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
// String str0=sc.next();
// String str1=sc.next();
//测试
String str0="[1,2,2,1,3]";
String str1="[2,2,3]";
String[] strs0=str0.substring(1,str0.length()-1).split(",");
String[] strs1=str1.substring(1,str1.length()-1).split(",");
if(str0.length()<str1.length()){
String[] temp=strs0;
strs0=strs1;
strs1=temp;
}
int[] arr0=new int[strs0.length];
int[] arr1=new int[strs1.length];
for(int i=0;i<arr0.length;i++){
arr0[i]=Integer.valueOf(strs0[i]);
}
for(int i=0;i<arr1.length;i++){
arr1[i]=Integer.valueOf(strs1[i]);
}
Arrays.sort(arr0);//排序
Arrays.sort(arr1);
ArrayList<Integer> tsOut=new ArrayList<>();
int index0=0,index1=0;
while (index0<arr0.length&&index1<arr1.length){
if(arr0[index0]==arr1[index1]){
if(!tsOut.contains(arr0[index0])){
tsOut.add(arr0[index0]);
}
index0++;
}else if(arr0[index0]<arr1[index1]){
index0++;
}else {
index1++;
}
}
System.out.print("[");
for(int i=0;i<tsOut.size()-1;i++){
System.out.print(tsOut.get(i)+",");
}
System.out.print(tsOut.get(tsOut.size()-1));
System.out.println("]");
}
}
/*
[1,2,2,1,3]
[2,2,3]
[2,3]
*/
3，最少几个硬币找零
例如：有1,2,5