数据结构与算法
大约 4 分钟
数据结构与算法
算法
质数
枚举
o(nolan)
//判断某数是否为质数
public boolean IsPrime(int n) {
for (int i = 2; i <= Math.sqrt(n); i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
//计数
public int testIsPrime(int n){
int count = 0;
if (n==2){
return count=1;
}
for (int i = 2; i < n; i++) {
count += IsPrime(i)? 1:0;
}
return count;
}
埃式筛
标记质数的倍数，存在重复标记,o(nloglogn)
public int testPrimeNumber(int n) {
boolean[] isPrime = new boolean[n+1];
Arrays.fill(isPrime, true);
int count = 0;
for (int i = 2; i < isPrime.length; i++) {
//计数，并把质数的倍数标记为false
if (isPrime[i]) {
count++;
//从 （i * i） 开始，[i * (i-1)]已经被上一轮i标记过，
//如i=2时标记4,6,,10..., i=3时应标记6,9,12...,但6已经标记过了无须再标记
for (int j = i * i; j < isPrime.length; j += i) {
isPrime[j] = false;
}
}
}
return count;
}
线性筛
解决重复标记，o(n)
private int testIsPrime3(int n) {
boolean[] isPrime = new boolean[n + 1];
Arrays.fill(isPrime, true);
ArrayList<Integer> primes = new ArrayList<>();
for (int i = 2; i < n + 1; i++) {
//计数，并把质数的倍数标记为false
if (isPrime[i]) {
primes.add(i);
}
//i=2,标记4
//i=3,标记6，9
//i=4,标记8
//i=5,标记10，15，25
//标记：所有整数 与 当前质数集合的每个质数 的乘积
for (int j = 0; j < primes.size() && i * primes.get(j) < n + 1; j++) {
isPrime[i * primes.get(j)] = false;
//避免重复标记
//合数 = 若干质数的乘积
//6被2整除，6定是合数，2是最小的质数，6*3=2*3*3=2*(3*3)=9*2,...
//9被3整除，9定是合数，3是最小的质数，9*5=3*3*5=3*(3*5)=15*3,...
//35被5整除，35定是合数，5是最小的质数，35*7=5*7*7=5*(7*7)=49*5,...
if (i % primes.get(j) == 0) {
break;
}
}
}
return primes.size();
}
高效计算2*8
2 << 3
// 8 << 1
杨辉三角
public void testYangHui() {
int[][] array= new int[10][];
for (int i = 0; i < array.length; i++) {
array[i] = new int[i+1];
for (int j = 0; j <= i; j++) {
array[i][0] = array[i][i] = 1;
if (i > 0 && j > 0 && j < i){
array[i][j] = array[i-1][j-1] + array[i-1][j];
}
System.out.print(array[i][j] + "t");
}
System.out.println();
}
}
回形数
public static void testHuiXingShu() {
Scanner scanner = new Scanner(System.in);
System.out.println("请输入边长： ");
int n = scanner.nextInt();
int[][] ints = new int[n][n];
int count = 1;
for (int i = 0; i < n / 2 + 1; i++) { //圈数
for (int j = i; j < n - i - 1; j++) {
ints[i][j] = count++; //上
}
for (int j = i; j < n - i - 1; j++) {
ints[j][n - i - 1] = count++; //右
}
for (int j = i; j < n - i - 1; j++) {
ints[n - i - 1][n - j - 1] = count++; //下
}
for (int j = i; j < n - i - 1; j++) {
ints[n - j - 1][i] = count++; //左
}
}
//奇数时，最后一次循环的内循环进不去
if (n % 2 != 0) {
ints[n / 2][n / 2] = n * n;
}
//遍历
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.print(ints[i][j] + "t");
}
System.out.println();
}
}
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("输入一个数字");
int num = scanner.nextInt();
int[][] huiXingShu = new int[num][num];
int count = 0; // 要显示的数据
int maxX = num - 1; // x横轴的最大下标
int maxY = num - 1; // Y纵轴的最大下标
int minX = 0; // x横轴的最小下标
int minY = 0; // Y纵轴的最小下标
while (minX <= maxX) { //直到X横轴线最小下标比最大下标还大时就退出循环 说明已经把值赋到最后一个了
for (int x = minX; x <= maxX; x++) { //向右 从最小到最大下标递增
huiXingShu[minY][x] = ++count; //必须++count 不然count++第一次会赋值为0
}
minY++; //说明Y纵轴的最小下标+1 向右已经赋值完一行了
for (int y = minY; y <= maxY; y++) { //向下 从最小到最大下标递增
huiXingShu[y][maxX] = ++count;
}
maxX--; //以上同理不再赘述
for (int x = maxX; x >= minX; x--) { //向左 从最小到最大下标递减
huiXingShu[maxY][x] = ++count;
}
maxY--;
for (int y = maxY; y >= minY; y--) { //向上 从最小到最大下标递减
huiXingShu[y][minX] = ++count;
}
minX++;
}
// 遍历
for (int[] anhuiXingShu : huiXingShu) {
for (int anAnhuiXingShu : anhuiXingShu) {
System.out.print(anAnhuiXingShu + "t");
}
System.out.println();
}
}
}
查找
线性查找
public void testLinearSearch(){
int[] ints = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14};
int a = 13;
boolean isFlag = true;
for (int i = 0; i < ints.length; i++) {
if (ints[i] == a) {
System.out.println(a + "的索引为" + i);
isFlag = false;
break;
}
}
if (isFlag) {
System.out.println(a + "未找到");
}
}
二分法查找
public void testDichotomySearch(){
int[] ints = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14};
int a = 23;
int head = 0; //头指针
int end = ints.length - 1; //尾指针
boolean isFlag = true;
while (head <= end) {
int middle = (head + end)/2;
if (ints[middle] == a) {
System.out.println(a + "的索引为" + (middle));
isFlag = false;
break;
}else if (a > ints[middle]){
head = middle + 1;
}else {
end = middle - 1;
}
}
if (isFlag) {
System.out.println("未找到");
}
}
排序
冒泡排序
public void testBubbleSort(){
int[] ints = new int[]{-10,14,4,24,-9,-1,15,19,4};
System.out.println("开始排序");
int temp = ints[0];
for (int i = 0; i < ints.length - 1; i++){ //轮数
boolean isFlag = true; //isFlag为true，即未交换过，就不在进行大轮循环
for (int j = 0; j < ints.length - i - 1; j++) { //交换次数
if (ints[j] > ints[j + 1]) {
temp = ints[j];
ints[j] = ints[j + 1];
ints[j + 1] = temp;
isFlag = false;
}
}
if (isFlag) break;
}
System.out.println(Arrays.toString(ints));
}