Java数据结构
- 数据与数据之间的逻辑关系：集合、一对一、一对多、多对多
- 数据的存储结构
线性表：顺序表（比如：集合）、链表、栈、队列
树形结构：二叉树
图形结构
算法
- 排序算法
- 搜索算法
数组中涉及的常见算法
- 数组元素的赋值（杨辉三角、回形数）
- 求数值型数组中元素的最大值、最小值、平均值、总和等
- 数组的复制、反转、查找（线性查找、二分法查找）
- 数组元素的排序算法
十大内部排序算法
-
选择排序
直接选择排序、堆排序 -
交换排序
冒泡排序、快速排序（速度最快） -
插入排序
直接插入排序、折半插入排序、Shell排序 -
归并排序
-
桶式排序
-
基数排序
Arrays工具类
Arrays.sort(arr); // 底层使用快排算法
简单：将九九乘法表打印到控制台。
for (int i = 1; i <10; i++) {
for (int j = 1; j <=i; j++) {
System.out.print(j+" * "+i+" = " + i*j+" ");
}
System.out.println();
}
求1000以内的水仙花数
中等：打印1000以内所有满足水仙花的数，“水仙花数”是指一个三位数其各位数字的立方和等于该数本身，例如153是“水仙花数”，因为：153 = 1^3 + 5^3 + 3^3
for (int i = 100; i <1000; i++) {
int a=i,sum=0;
while (a>0){
int b=a%10;
sum+=b*b*b;
a/=10;
}
if (sum==i) System.out.println(i);
}
青蛙跳台阶问题
困难：一共有n个台阶，一只青蛙每次只能跳一阶或是两阶，那么一共有多少种跳到顶端的方案？例如n=2，那么一共有两种方案，一次性跳两阶或是每次跳一阶。
// 青蛙跳台阶
int[] ints = new int[45];
ints[0]=1;
ints[1]=2;
for (int i = 2; i
ints[i]=ints[i-1]+ints[i-2];
System.out.println(ints[i]);
}
三大基本排序算法
- 冒泡排序
冒泡排序就是冒泡，其实就是不断使得我们无序数组中的最大数向前移动，经历n轮循环逐渐将每一个数推向最前。
public static void main(String[] args) {
// 冒泡排序
int query[] = {1, 5, 6, 2, 0, 14, 52, 32, 98};
test(query);
for (int j = 0; j
System.out.print(query[j]+" ");
}
}
public static void test(int query[]){
for (int i = 0; i < query.length - 1; i++) {
boolean lock=true;//优化锁
for (int j = 0; j
if (query[j]
lock=false;
int temp=query[j];
query[j]=query[j+1];
query[j+1]=temp;
}
}
if (lock) break;
}
}
- 插入排序
插入排序其实就跟我们打牌是一样的，我们在摸牌的时候，牌堆是乱序的，但是我们一张一张摸到手中进行排序，使得它变成了有序的！
public static void main(String[] args) {
// 插入排序
int query[] = {1, 5, 6, 2, 0, 14, 52, 32, 98};
test(query);
for (int i = 0; i < query.length; i++) {
System.out.print(query[i] + " ");
}
}
public static void test(int query[]) {
for (int i = 1; i < query.length; i++) {
int temp = query[i];
int j = i - 1;
while (j >= 0 && temp < query[j]) {
query[j + 1] = query[j];
j--;
}
query[j + 1] = temp;
}
}
- 选择排序
选择排序其实就是每次都选择当前数组中最大的数排到最前面！
public static void main(String[] args) {
// 选择排序
int query[] = {1, 5, 6, 2, 0, 14, 52, 32, 98};
test(query);
for (int i = 0; i < query.length; i++) {
System.out.print(query[i] + " ");
}
}
public static void test(int[] query) {
for (int i = 0; i < query.length-1; i++) {
int max = query[i],p = i;
for (int j = i+1; j < query.length; j++) {
if (query[j] > max){
max = query[j];
p=j;
}
}
int temp=query[p];
query[p]=query[i];
query[i]=temp;
}
}
面向对象编程实战
- 二分搜索（搜索算法）
现在有一个有序数组（从小到大，数组长度 0 < n < 1000000）如何快速寻找我们想要的数在哪个位置，如果存在请返回下标，不存在返回-1即可。
public static void main(String[] args) {
// 二分查找
int[] arr = new int[]{1, 2, 5, 9, 10, 23, 50, 88, 99, 101};
System.out.println(test(arr, 88));
}
public static int test(int[] arr, int find) {
int start = 0, end = arr.length - 1;
while (start <= end) {
int mid = (start + end + 1) / 2;
if (find == arr[mid]) return mid;
if (find < arr[mid]) end = mid - 1;
if (find > arr[mid]) start = mid + 1;
}
return -1;
}
- 快速排序（排序算法、递归分治）
（开始之前先介绍一下递归！）快速排序其实是一种排序执行效率很高的排序算法，它利用分治法来对待排序序列进行分治排序，它的思想主要是通过一趟排序将待排记录分隔成独立的两部分，其中的一部分比关键字小，后面一部分比关键字大，然后再对这前后的两部分分别采用这种方式进行排序，通过递归的运算最终达到整个序列有序。
快速排序就像它的名字一样，快速！
- 0/1背包问题（回溯法、剪枝/动态规划优化）给定 n件物品，每一个物品的重量为 w[n]，每个物品的价值为 v[n]。现挑选物品放入背包中，假定背包能承受的最大重量为 capacity，背包中最多只能存放number件物品，求装入物品的最大重量是多少?
