1.Java 程序的基本结构
2.原始数据类型与表达式
，+、-、 *、/ 都是被重载过的——根据上下文，同样的运算符对不 同类型会执行不同的操作
3.语句
4.简便记法
5.数组
声明、创建并初始化一个数组：
// 完整模式：double[] a;a = new double[N];for (int i = 0; i < N; i++)a[i] = 0.0// 简化写法double[] a = new double[N];// 声明初始化int[] a = {1, 1, 2, 3, 5, 8};
使用数组
// 数组中最大元素double max = a[0];for (int i = 1; i < a.length; i++) {if (a[i] > max) {max = a[i];}}// 数组平均值int N = a.length;double sum = 0.0;for(int i = 0; i < N; i++) {sum += a[i];}double average = sum / N;// 复制数组int N = a.length;double[] b = new double[N];for (int i = 0; i < N; i++) {b[i] = a[i];}// 反转数组int N = a.length;for (int i = 0; i < N/2; i++) {double temp = a[i];a[i] = a[N-1-i];a[N-i-1] = temp;}// 矩阵相乘 a[][] * b[][] = c[][]int N = a.length;double[][] c = new double[N][N];for (int i = 0; i < N; i++) {for (int j = 0; j < N; j ++) {// 计算 i行 和 j列 的点乘for (int k = 0; k < N; k++) {c[i][j] += a[i][k] * b[k][j];}}}
6.静态方法
典型静态方法的实现
// 计算整数绝对值public static int abs(int x) {if (x < 0) return -x;else return x;}// 计算浮点数绝对值public static double abs(double x) {if (x < 0.0) return -x;else return x;}// 判断一个数是否是素数public static boolean isPrime(int N) {if (N < 2) return false;for (int i = 2; i * i <= N; i++) {if (N % i == 0)return false;return true;}}// 计算平方根(牛顿迭代法） NaN是Float,Double的一个成员常量，用来指示一个Float或Double不是合法的public static double sqrt(double c) {if (c < 0) return Double.NaN;double err = 1e-15;double t = c;while (Math.abs(t - c/t) > err * t)t = (c/t + t) / 2.0;return t;}// 已知直角三角形 垂直边 a, b 求斜边public static double hypotenuse(double a, double b) {return Math.sqrt(a*a + b*b);}// 计算调和级数public static double H(int N) {double sum = 0.0;for (int i = 1; i <= N; i++) {sum += 1.0 / i;}return sum;}
递归三条
- 递归总有一个最简单的情况—第一段语句就 return
- 递归调用总是常识解决 规模更小 的子问题。
- 递归调用的父问题和尝试解决的子问题之间没有交集。
举例：二分查找的递归实现
public static int rank(int key, int[] a) {
return rank(key, a, 0, a.length - 1);
}
public static int rank(int key, int[] a, int lo, int hi) {
// 如果 key 存在于 a[] 中，它的索引不会小于 lo 且不会大于 hi
if (lo > hi) return -1;
int mid = lo + (hi - lo) / 2;
if (key < a[mid]) return rank(key, a, lo, mid - 1);
else if (key > a[mid]) return rank(key, a, mid + 1, hi);
else return mid;
}
练习
1.1.1
// (0 + 15) / 2
double result = (0.0 + 15) / 2;
// 2.0e-6 * 10000000.1
double result = 2.0e-6 * 10000000.1;
// true && false || true && true
boolean result = true && false || true && true;
1.1.2
// (1 + 2.2360) / 2
double result = (1 + 2.2360) / 2; // 1.618
// 1 + 2 + 3 + 4.0
double result = 1 + 2 + 3 + 4.0; // 10.0
// 4.1 >= 4
boolean result = 4.1 >= 4; // true
// 1 + 2 + "3"
String result = 1 + 2 + "3"; // 33
1.1.3
int a = StdIn.readInt();
int b = StdIn.readInt();
int c = StdIn.readInt();
boolean result = a == b && b == c;
System.out.println(result);
1.1.4
a java 没有 then 关键字
b 条件语句要加括号
c
d else 语句不能与 if 一行
1.1.5
public static void isInOne(double a, double b) {
if (a > 0 && a < 1 && b > 0 && b < 1)
System.out.println(true);
else
System.out.println(false);
}
1.1.6
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610
1.1.7
a 3.00009
b 499500
c 10000
1.1.8
a b // println(char x)
b 197 // 进行加法运算时 char 会被转为 int
c e // int 强转 char
1.1.9
public static String toBinaryString(int N) {
StringBuilder s = new StringBuilder();
for (int n = N; n > 0; n /=2) {
s.insert(0, (n % 2));
}
return s.toString();
}
1.1.10
先 new 分配内存
int[] a = new int[10];
for (int i = 0; i < 10; i++) {
a[i] = i*i;
}
System.out.println(Arrays.toString(a));
1.1.11
public static void main(String[] args) {
boolean[][] b = new boolean[][]{{true, false, false}, {true, true, true}};
printBooleanMatrix(b);
}
public static void printBooleanMatrix(boolean[][] b) {
for (boolean[] booleans : b) {
for (boolean aBoolean : booleans) {
System.out.print(aBoolean ? "* " : " ");
}
System.out.println();
}
}
1.1.12
1.1.13
public static int[][] transposeMatrix(int[][] matrix) {
int rows = matrix.length;
int cols = matrix[0].length;
int[][] result = new int[cols][rows];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
result[j][i] = matrix[i][j];
}
}
return result;
}
1.1.14
public static int lg(int n) {
int sum = 2;
int result = 0;
while (sum <= n) {
result += 1;
sum *= 2;
}
return result;
}
1.1.15
public static int[] histogram(int[] a, int m){
int[] result = new int[m];
for (int i = 0; i < m; i++) {
int count = 0;
for (int item : a) {
if (item == i)
count++;
}
result[i] = count;
}
return result;
}
1.1.16
1.1.17
代码中的基础情况不会被调用返回，直至 StackOverflowError
1.1.18
50 33
65795 6574
1.1.19
斐波那契数列（Fibonacci sequence），又称黄金分割数列
结果是前两个数的和，所以保留前两个数结果就可以
public static void fibonacci(int n) {
BigInteger[] container = new BigInteger[2];
for (int i = 0; i < n; i++) {
int index = i % 2;
if (i < 2) {
container[index] = BigInteger.valueOf(i);
} else {
container[index] = container[0].add(container[1]);
}
System.out.println(container[index]);
}
}
1.1.20
public static double ln(int n) {
if (n == 1) {
return 0;
}
return Math.log(n) + ln(n-1);
}
1.1.21
public static void write() {
int n = StdIn.readInt();
String[] nameArray = new String[n];
int[] intArray1 = new int[n];
int[] intArray2 = new int[n];
for (int i = 0; i < n; i ++){
nameArray[i] = StdIn.readString();
intArray1[i] = StdIn.readInt();
intArray2[i] = StdIn.readInt();
}
System.out.println("| 姓名 | 语文 | 数学 |");
for (int i = 0; i < n; i ++){
System.out.println("| " + nameArray[i] + " | " + intArray1[i] + " | " + intArray2[i] + " |");
}
}
1.1.22
public static int rank(int key, int[] a) {
return rank(key, a, 0, a.length - 1, 0);
}
public static int rank(int key, int[] a, int lo, int hi, int deep) {
// 如果 key 存在于 a[] 中，它的索引不会小于 lo 且不会大于 hi
System.out.println("lo: " + lo + ", hi: " + hi + ", deep: " + deep);
if (lo > hi) return -1;
int mid = lo + (hi - lo) / 2;
if (key < a[mid]) return rank(key, a, lo, mid - 1, ++deep);
else if (key > a[mid]) return rank(key, a, mid + 1, hi, ++deep);
else return mid;
}
1.1.23
public static void main(String[] args) {
int[] arr = {0, 1, 2, 3, 5, 6, 7, 8, 9, 10, 44};
int[] whiteList = {6, 7, 9, 10};
String func = StdIn.readLine();
for (int item : arr) {
if (func.equals("+") && rank(item, whiteList) < 0) {
StdOut.println(item);
} else if (func.equals("-") && rank(item, whiteList) >= 0) {
StdOut.println(item);
}
}
}
1.1.24
public static void main(String[] args) {
StdOut.printf("gcd(105,24)=%d",gcd(105,24));
}
public static int gcd(int p,int q) {
StdOut.printf("p=%d,q=%d\n",p,q);
if (q==0) return p;
int r=p % q;
return gcd(q,r);
}
public class Euclid {
public static void main(String[] args) {
int p=Integer.parseInt(args[0]);
int q=Integer.parseInt(args[1]);
StdOut.printf("gcd("+Integer.toString(p)+","+Integer.toString(q)+")=%d",gcd(p,q));
}
public static int gcd(int p,int q) {
StdOut.printf("p=%d,q=%d\n",p,q);
if (q==0) return p;
int r=p % q;
return gcd(q,r);
}
}
1.1.25
1) 基础步骤:求证gcd(p,q)=gcd(q,r)
证：令p=a*q+r,其中p、a、q、r均为非负整数。
设整数d|p、d|q,则d|(p-a*q),得p与q的公约数和q与r的公约数相同。
设整数d|q、d|r,则d|(a*q+r),得q与r的公约数和p与r的公约数相同。基于上述两点得gcd(p,q)=gcd(q,r)。
2) 归纳步骤：设有gcd(p,q)=gcd(q,r)，求证gcd(q,r)=gcd(r, q%r)
证：由gcd(p,q)=gcd(q,r)可得d|p、d|q、d|r、p=a*q+r。
由于有q=⌊q/r⌋*r+q%r、d|q、d|r，所以有d|q%r所以有gcd(q,r)=gcd(r,q%r)。
提高题
1.1.26
前两句保证 a 位置最小
第三句保证 c 位置最大
1.1.27
二项分布
命中概率为 p，求 N 次，命中 k 次的概率
1.1.28
/**
* 获取有序数组去重后的数组长度，截取后即为去重数组
* @param a 有序数组
* @return 去重后的数组长度
*/
public static int removeDuplicates(int[] a) {
if (a.length == 0) return 0;
int j = 0;
for (int i = 0; i < a.length; i++) {
if (a[j] != a[i]) {
a[++j] = a[i];
}
}
return j + 1;
}
1.1.29
public static int rank(int key, int[] a) {
int lower = 0;
for (int item : a) {
if (key > item) {
lower++;
}
}
return lower;
}
public static int count(int key, int[] a) {
int equal = 0;
for (int item : a) {
if (key == item) {
equal++;
}
}
return equal;
}
若有收获，就点个赞吧
0 人点赞
