杨辉三角
- 第n行有n个数字.
- 每一行的开始和结尾数字都为1.
- 第n+1行的第i个数字等于第n行的i-1个数字加上第n行的i个数字。
image.png
- A部分与B部分的区别在于：A部分的横坐标大于等于纵坐标。用数组中的话就是i<=j;知道要赋值的范围
image.png
image.png
public class YangHui {
public static void main(String[] args) {
int[][] arr = new int[10][10];
//定义了一个长度为10，高度为10的二维数组，数组中的值都为0；
for (int i = 0; i < arr.length; i++) {
//由于只是给杨辉三角内的位置赋值，所以是j<=i
for (int j = 0; j <= i; j++) {
if (j == 0 || j == i) {
arr[i][j] = 1;
} else {
arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j];
}
/*由于只是输出杨辉三角范围内的值，所以在内层循环就输出，这种方法不能全部赋值完之后再输出
"\t"的原因是10和小于10的数组的宽度不同，所以使用\t制表符能使数与数之间距离相等
*/
System.out.print(arr[i][j]+"\t");
}
System.out.println("\n");
}
}
}
1到100有多少个素数
- 关键：outer和Math.sqrt
public class PrimeNumber {
//1到100有多少个素数
public static void main(String[] args) {
//1不是素数
outer:for(int i = 2;i<=100;i++){
//每个数从2到它的根号
for(int j = 2; j<=Math.sqrt(i);j++){
if(i%j==0){
continue outer;
}
}
System.out.println(i);
}
}
}
最大公约数和最小公倍数
public class GcdTest {
public static void main(String[] args) {
int a = 48;
int b = 72;
int gcd = gcdCount(a, b);
System.out.println("最大公约数是：" + gcd);
//两数相乘除以最大公约数
System.out.println("最小公倍数是："+(a*b)/gcd);
}
private static int gcdCount(int a ,int b) {
//记录最大公约数
int gcd = 1;
//求出两个数字之间的小值
int min = a < b ? a : b;
for (int i = min;i >= 1;i --) {
if (a % i == 0 && b % i == 0) {
gcd = i;
break;
}
}
return gcd;
}
}
最长山峰
题目：
我们把数组 A 中符合下列属性的任意连续子数组 B 称为 “山脉”：
B.length >= 3
存在 0 < i < B.length - 1 使得 B[0] < B[1] < … B[i-1] <B[i] > B[i+1] > … > B[B.length - 1] （注意：B 可以是 A 的任意子数组，包括整个数组 A。）
给出一个整数数组 A，返回最长 “山脉” 的长度。
如果不含有 “山脉” 则返回 0。
public class LongestMountain {
public int longest(int[] A) {
if (A.length <= 2) {
return 0;
}
//记录没次循环的最长山峰长度
int count = 0;
//
for (int i = 1; i < A.length - 1; i++) {
if (A[i] > A[i - 1] && A[i] > A[i + 1]) {
int left = i - 1;
int right = i + 1;
while (left > 0 && A[left] > A[left - 1]) {
left--;
}
while (right < A.length - 1 && A[right] > A[right + 1]) {
right++;
}
//每一次都比较找出最大的长度
count = Math.max(right - left + 1, count);
}
}
return count;
}
}
水仙花数
- 打印出所有的”水仙花数”，所谓”水仙花数”是指一个三位数，其各位数字立方和等于该数本身。例如：153是一个”水仙花数”，因为153=1的三次方＋5的三次方＋3的三次方。
- 看怎么获取一个数的每一位
public class daffodilTest {
public static void main(String[] args) {
daffodil();
}
private static void daffodil() {
int sum = 0;
for(int i = 100; i<1000; i++){
int one = i%10;
int ten = i/10%10;
int hundred = i/100;
if((one*one*one)+(ten*ten*ten)+(hundred*hundred*hundred) == i){
sum++;
System.out.println("水仙花数："+i);
}
}
System.out.println("100-999之间共有"+sum+"个水仙花数。");
}
}
分解质因数
public class PrimeFactor {
public static void main(String[] args) {
prime(988);
}
private static void prime(int input) {
System.out.print(input+"=");
for(int i = 2 ; i<input+1 ; i++){
//input是会影响上面的外层的。所以如果他可以输出6的话，之前肯定会被2除，所以不会出现6
while(input%i==0&&input!=i) {
input=input/i;
System.out.print(i+"*");
}
if(input==i){//上面的都不能整除，，input没有发生改变，说明这是一个质数
System.out.print(i);
break;
}
}
}
}
统计各种个数
- 输入一行字符，分别统计出其英文字母、空格、数字和其它字符的个数。
这里的需要的知识点:
1、获取一行字符串，nextLine（）
2、把字符串的每一个字符赋值到一个数值中
3、对比每一个数值在ASK码的范围，就可以确定它符号的类别
4、char字符ASK码的范围
（1）数字0到9： 48~57
（2）字母A到Z：65到90 a到z：97到122
（3）空格是32
Integer.valueOf(char)可以获取ask，但是这个似乎可以直接和int比较
public static void main(String[] args) {
int num=0;//数字的个数
int letter=0;//字母的个数
int space=0;//空格的个数
int others=0;//其他的个数
System.out.println("请输入一串字符：");
Scanner scanner=new Scanner(System.in);
String string=scanner.nextLine();//获取一行字符串
//把字符串里面的值赋值给一个字符型数组
char[]arr=string.toCharArray();
//遍历字符串里面的所有值
for (inti = 0; i < arr.length; i++) {
if (arr[i]>=48&&arr[i]<=57) {//字符是数字
num++;
} else if((arr[i]>=65&&arr[i]<=90)||(arr[i]>=97&&arr[i]<=122)) {
letter++;
}else if (arr[i]==32) {
space++;
}else {
others++;
}
}
System.out.println("数字："+num+"个，字母："+letter+"个，空格："+space+"个，其他："+others+"个");
scanner.close();
求s=a+aa+aaa+aaaa+aa…a的值，其中a是一个数字。例如2+22+222+2222+22222(此时共有5个数相加)，几个数相加有键盘控制。输出结果的形式如：2+22+222=246；
- 放一个数组里。当前数等于位数整+前一个数字
public static void main(String[] args) {
int n=0,a=0;
Scanner scanner=new Scanner(System.in);
System.out.println("请输入a的值:");
a=scanner.nextInt();
System.out.println("请输入n的值：");
n=scanner.nextInt();
int[] arr=new int[n];//创建数组长度为输入的项数
int i=1;//while循环初始化的值
arr[0]=a;//数组的第一个值为3
//把每一项的值赋值给数组里面的数
while (i<n) {
a*=10;
arr[i]=a+arr[i-1];
i++;
}
//求和
int sum=0;
for(ints:arr){
sum+=s;//累加求和
if (s==arr[n-1]) {
System.out.print(s);
break;//最后一次只输出结果
}
System.out.print(s+"+");//前面的值输出结果，后面还要加一个加号
}
System.out.println("="+sum);//完美结束
}
给出一个非空的字符串，判断这个字符串是否是由它的一个子串进行多次首尾拼接构成的。例如，"abcabcabc"满足条件，因为它是由"abc"首尾拼接而成的，而"abcab"则不满足条件
- 思想如下：从最长的二等分开始查找，用等分后的子字符串拼接成新的字符串B，与原字符串A进行比较，如果相等，返回这个字符串，如果不相等进行三等分以此类推，如果直至n等分（n=字符串A长度）都不能满足，输出false
public class StringRepeat {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
System.out.println(binSearch(str));
}
public static String binSearch(String str) {
int len = 2;
while (str.length()/len>0){
//除不尽的不可能拼接成功
if(str.length()%len!=0){
len++;
continue;
}else {
StringBuilder sb =new StringBuilder();
//如果是相同的，用第一个截取到的去拼接就行了
for(int i=0;i<len;i++){
sb.append(str.substring(0,str.length()/len));
}
if(sb.toString().equals(str)){
return str.substring(0,str.length()/len);
}
len++;
}
}
return "false";
}
}
从非负整数序列 0, 1, 2, ..., n中给出包含其中n个数的子序列，请找出未出现在该子序列中的那个数。
- 输入为n+1个非负整数，用空格分开。其中：首个数字为非负整数序列的最大值n，后面n个数字为子序列中包含的数字。 3 3 0 1
- 输出为1个数字，即未出现在子序列中的那个数。1
public class IsContain {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String string = in.nextLine();
String[] list = string.split(" ");//只是用到list的长度，即输入数字的个数
for (int i = list.length-1; i > -1 ; i--)
if (/*字符串i在不在大字符串中*/! string.contains(""+i)) {
System.out.println(i);
break;
}
}
}
给定一个正整数数组，它的第 i 个元素是比特币第 i 天的价格。如果你最多只允许完成一笔交易（即买入和卖出一次），设计一个算法来计算你所能获取的最大利润。注意你不能在买入比特币前卖出。
- 输入描述: 正整数数组，为以空格分隔的n个正整数。
7 1 5 3 6 4 - 输出描述:最大利润
5 - 分析：是理解动态规划法非常经典的一道题。从左往右遍历，每遍历到一个元素时，用当前元素减去它左边的最小值（上一轮选出来的）。用得到的结果和已经求得的最小值比较即可。
public class BitCoin {
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
String[] sArray = s.split(" ");
int preMin = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for(int i = 0; i < sArray.length ; i++) {
int cur = Integer.valueOf(sArray[i]);
//下面两句话不能调换顺序。如果新轮询到的arr[i]是新的最小值，不能马上拿来用
//因为购出的日期一定是在购入之后或者同一天
max = Math.max(max, cur - preMin);
preMin = Math.min(preMin, cur);
}
System.out.println(Math.max(max, 0));
}
}
