Java算法入门-数组&链表&队列
2020-12-13 03:13
标签：integer 程序 priority inf 体验 eset hash target btree 算法就是解决问题的步骤，在一般的项目中可能用不上，但是一旦涉及到高并发，高性能时，就不得不考虑算法的优劣。 设计原则：正确性，可读性，健壮性，高效率和低存储 特性：有穷性，确定性，可行性，有输入，有输出。 如何判断是一个数是2的整数次幂？常规方法使用循环，但是在学习了二进制的基础知识后，发现可以使用模运算来实现。 控制台输出情况 评价算法的两个重要的指标为时间复杂度和空间复杂度。 时间复杂度：运行一个程序需要的时间，一般用O()表示，一般有如下几种，具体可以参考代码。 （1）常数型，能确定循环的次数，一般为O(1) （2）线性型，循环次数不确定，并且没有嵌套循环等，一般表示O(N) （3）对数型，参考代码，一般表示为log(N) （4）嵌套型，参考代码循环嵌套，一般表示为O(N^2) 注意使用时间复杂度表达式时会省略低指数位，省略常数。 空间复杂度：运行一个程序所需要的内存，一般用OOM表示。 数据结构是计算机存储和组织数据的方式，指相互之间存在一种或者多种特性关系的数据元素的集合。通常情况下，精心设计的数据结构可以带来更高的运行或者存储效率，如Btree用于MySql。数据结构跟高效的检索算法和索引技术有关，其中常见的数据结构有List，Set，Map和Queue，具体可以参考自己写的博客，持续添加中。 （1）List （2）Set （3）队列 博客地址： （1）https://www.cnblogs.com/youngchaolin/p/11032616.html 栈队列数组链表和红黑树 （2）https://www.cnblogs.com/youngchaolin/p/11028365.html Collection集合 （3）https://www.cnblogs.com/youngchaolin/p/10463887.html 二进制 Java算法入门-数组&链表&队列 标签：integer 程序 priority inf 体验 eset hash target btree 原文地址：https://www.cnblogs.com/youngchaolin/p/11026368.html设计原则和特性
算法题入门体验
1 import java.util.Scanner;
2
3 public class base {
4
5 public static void main(String[] args) {
6 /**
7 * 算法入门，如何判断一个数是否为2的整数次幂，即是否为2^n
8 * 如果不用算法就可以使用循环来实现
9 * 如果使用算法，就可以考虑二进制的与运算
10 */
11 Scanner scan = new Scanner(System.in);
12 System.out.println("请输入需要计算的数字：");
13 int num = scan.nextInt();
14 method2(num);
15
16 }
17
18 /**
19 * 使用循环来实现
20 *
21 * @param n
22 */
23 public static void methon1(int n) {
24 while(true){
25 n=n/2;
26 if(n==2||n==1){
27 break;
28 }
29 }
30 if(n==2){
31 System.out.println("这个数是2的整数次幂");
32 }else{
33 System.out.println("这个数不是2的整数次幂");
34 }
35 }
36
37 /**
38 * 使用二进制与运算来实现
39 * @param n
40 */
41 public static void method2(int n){
42 /**
43 * 2的二进制10 1的二进制01 高位补齐
44 * 4的二进制100 3的二进制011 高位补齐
45 * 8的二进制1000 7的二进制0111 高位补齐
46 * ...
47 */
48 int m=n&(n-1);
49
50 if(m==0){
51 System.out.println("这个数是2的整数次幂");
52 }else{
53 System.out.println("这个数不是2的整数次幂");
54 }
55
56 }
57 }
时间复杂度&空间复杂度
import java.util.ArrayList;
import java.util.List;
public class OCTest {
public static void main(String[] args) {
/**
* 时间复杂度计算方法
*/
//常数型
int n=0; //O(1)
int m=n+1; //O(1)
for (int i = 0; i ) {
//有确定循环数目的，时间复杂度也是O(1)
} //O(1)
//线性型
for (int i = 0; i ) {
//循环次数不确定，就是线性型
} //O(m)
//对数型
int c=1;
while(cn){
c=c*2;
//循环结束就是2^m=n，这样使用高中数学知识就知道，m=log2^n，循环次数就是对数形式，在算法中就是写成log(n)
} //O(log(n))
//对数型
for (int i = 0; i ) {
int d=1;
while(dn){
d=d*2;
}
} //参考上面的例子，时间复杂度就是O(n*log(n))
//下面嵌套的类型
for (int i = 0; i
数据结构
1 import java.util.ArrayList;
2 import java.util.LinkedList;
3 import java.util.List;
4 import java.util.Vector;
5
6 public class ListTest {
7
8 public static void main(String[] args) {
9 /**
10 * 数组和链表
11 */
12
13 //List
14 List
1 public class SetTest {
2
3 public static void main(String[] args) {
4 /**
5 * Set，主要用来去重的，Java有三种实现方式
6 * 1 HashSet：去重的，去重后元素的顺序和插入的不一样
7 * 2 TreeSet：排序的，底层数据结构为红黑树
8 * 3 LinkedHashSet：维护了一个链表，保持插入和输出后的顺序一致
9 */
10 }
11 }
1 public class QueueTest {
2
3 public static void main(String[] args) {
4 /**
5 * queue队列，用于等待队列，排队场景，如果一个系统流量高，需要做排队系统
6 * MQ，消息队列
7 *
8 *
9 * PriorityBlockingQueue：优先队列，如果实现一个排队场景，如有vip用户，可以让vip排在前面
10 * 其他比较常用的队列有：
11 * ArrayBlockingQueue 基于数组的阻塞队列，有界，不担心爆内存，take()一直会阻塞到有数据为止，可以用在高并发场景
12 * LinkedBlockingQueue 无界的队列，可能会爆内存
13 *
14 * DelayQueue 延迟队列
15 */
16
17 }
18 }
常见数据结构优缺点
