阳江网页设计_哪家网站建设最好_上海网上推广_百度推广视频

这篇文章是看了“左程云”老师在b站上的讲解之后写的, 自己感觉已经能理解了, 所以就将整个过程写下来了。

这个是“左程云”老师个人空间的b站的链接, 数据结构与算法讲的很好很好, 希望大家可以多多支持左程云老师, 真心推荐.
https://space.bilibili.com/8888480?spm_id_from=333.999.0.0

在这里插入图片描述

1. 哈希表

注意：我们这一节课只是讲述用法, 不是讲述底层的实现原理, 请大家不要误会.

可以将哈希表想象成一个集合.

1.1 `Hashset` 类

例子：这个类就是一个集合, 将所有你自己想要加入的数字放进去, 比如：3, 5, 6, 7, 这些都是 key, 然后这些数字都会放到这个集合中, 实现增, 删, 改, 查, 等操作的时间复杂度是：O(1), 常数时间. 但是需要注意的是：这个常数时间是一个大常数时间.

在这里插入图片描述

1.2 `HashMap` 类

和 HashSet 基本上是一样的, 只是多了一个 value, 例子：比如将字符 A 存储到集合中, 那 A 对应的 Key 是 3(假设), 将字符 B 存储到集合中, 那 B 对应的 Key 是 3722(假设). 就是这样的一个对应的关系. 和 HashSet 区别只是多了一个伴随数据. 而且 HashSet 是将 Key 和 value 同时存储在集合中的. 时间复杂度也是一样：O(1).

在这里插入图片描述

1.3 代码实例

代码中对应的解释我都写到了注释当中.

public static void main(String[] args) {  // Integer、Long、Double、Float  // Byte、Short、Character、Boolean  // String等都有这个特征  String str1 = new String("Hello");  String str2 = new String("Hello");  // false，因为不同的内存地址  System.out.println(str1 == str2);  // 上面所说的类中, 都是比较的内存地址.// true，因为它们的值是相同的  System.out.println(str1.equals(str2));  // 需要使用.equals().这个都是在开始学习Java的时候就注意的坑了.HashSet<String> set = new HashSet<>(); // 创建了hashSet  set.add(str1);                         // 将“Hello”加入了进去, 对于hashSet来说, 只关心集合中有没有这个值,  System.out.println(set.contains("Hello"));  System.out.println(set.contains(str2));  // 这个返回的结果是：true, 因为在集合中, 已经有了Hello了(只关心值).  set.add(str2);             // 因为str1 和 str2 是一样的, 所以这个str2相当于在集合中已经存在了, 所以相当于没有将str2加入到集合中  System.out.println(set.size());  // 这里打印出来的值还是“1”.  set.remove(str1);          // 移除“str1”的Key  set.clear();               // 将集合中所有的Key都清空  System.out.println(set.isEmpty());  // 判断集合中是否为“空”.  System.out.println("===========");  HashMap<String, String> map1 = new HashMap<>();  map1.put(str1, "World");                // 放进去一个Key：str1, 一个value：World.  System.out.println(map1.containsKey("Hello")); // 判断其中有没有一个“Hello” 的key. 返回true  System.out.println(map1.containsKey(str2));    // 还是返回true, 和HashSet一样是只根据字面值判断.  System.out.println(map1.get(str2));       // 通过Key的值, 找到“World”并进行打印.  System.out.println(map1.get("你好") == null); // 想要在集合中拿到一个不存在的值会返回null.  map1.remove("Hello");  System.out.println(map1.size());  map1.clear();  System.out.println(map1.isEmpty());  //当存储的类型是上述八种类型的时候, 是根据字面值来进行判断的.System.out.println("===========");  // 一般在笔试中，未必需要申请哈希表  HashMap<Integer, Integer> map2 = new HashMap<>();  map2.put(56, 7285);  map2.put(34, 3671263);  map2.put(17, 716311);  map2.put(24, 1263161);  // 上面的map2行为，可以被如下数组的行为替代  int[] arr = new int[100];  arr[56] = 7285;  arr[34] = 3671263;  arr[17] = 716311;  arr[24] = 1263161;  // 哈希表的增、删、改、查，都可以被数组替代，前提是key的范围是固定的、可控的  System.out.println("在笔试场合中哈希表往往会被数组替代");  System.out.println("===========");  Student s1 = new Student(17, "张三");  Student s2 = new Student(17, "张三");  HashMap<Student, String> map3 = new HashMap<>();  map3.put(s1, "这是张三");  System.out.println(map3.containsKey(s1));  System.out.println(map3.containsKey(s2));  map3.put(s2, "这是另一个张三");  System.out.println(map3.size());  System.out.println(map3.get(s1));  System.out.println(map3.get(s2));  
}  public static class Student {  public int age;  public String name;  public Student(int a, String b) {  age = a;  name = b;  }  
}

最后总结一下：

Integer、Long、Double、Float Byte、Short、Character、Boolean String 等都是使用字面值判断Key.
除此之外的类都是使用内存地址做 Key.

2. 有序表

在这里插入图片描述

有序表的增删改查操作的时间复杂度是：O(log(n)). 而且在传入对象的时候, 会自动进行排序.

2.1 代码实例

public static void main(String[] args) {  // 底层红黑树  TreeMap<Integer, String> treeMap = new TreeMap<>();  treeMap.put(5, "这是5");  treeMap.put(7, "这是7");  treeMap.put(1, "这是1");  treeMap.put(2, "这是2");  treeMap.put(3, "这是3");  treeMap.put(4, "这是4");  treeMap.put(8, "这是8");  System.out.println(treeMap.containsKey(1));    // 判断有序表中包不包含存在不存在key值为“1”  System.out.println(treeMap.containsKey(10));  System.out.println(treeMap.get(4));           // 打印Key值为“4”对应的值.  treeMap.put(4, "张三是4");                     // 进行修改更新  System.out.println(treeMap.get(4));           // 重新打印, 会更新为新的值  treeMap.remove(4);                        // 移除Key值为“4”的值.  System.out.println(treeMap.get(4) == null);     // 下面这四行功能就是哈希表做不到的事情.  System.out.println(treeMap.firstKey());  // 寻找key值最小的key.System.out.println(treeMap.lastKey());   // 寻找key值最大的key.// TreeMap中，所有的key，<= 4且最近的key是什么  System.out.println(treeMap.floorKey(4));  // TreeMap中，所有的key，>= 4且最近的key是什么  System.out.println(treeMap.ceilingKey(4));  System.out.println("========");TreeSet<Integer> set = new TreeSet<>();  set.add(3);  set.add(3);  set.add(4);  set.add(4);  System.out.println("有序表大小 : " + set.size());  while (!set.isEmpty()) {  System.out.println(set.pollFirst());  // System.out.println(set.pollLast());  }  // 堆，默认小根堆、如果要大根堆，定制比较器！  PriorityQueue<Integer> heap1 = new PriorityQueue<>();  heap1.add(3);  heap1.add(3);  heap1.add(4);  heap1.add(4);  System.out.println("堆大小 : " + heap1.size());  while (!heap1.isEmpty()) {  System.out.println(heap1.poll());  }  // 定制的大根堆，用比较器！  PriorityQueue<Integer> heap2 = new PriorityQueue<>((a, b) -> b - a);  heap2.add(3);  heap2.add(3);  heap2.add(4);  heap2.add(4);  System.out.println("堆大小 : " + heap2.size());  while (!heap2.isEmpty()) {  System.out.println(heap2.poll());  }  }

3. 比较器

3.1 代码实例

public static class Employee {  public int company;  public int age;  public Employee(int c, int a) {  company = c;  age = a;  }  
}  public static class EmployeeComparator implements Comparator<Employee> {  @Override  public int compare(Employee o1, Employee o2) {  
//       if(o1.age < o2.age) {
//           return -1;
//       } else if (o1.age > o2.age) {
//           return 1;                   // 这段代码可以实现谁年龄小, 谁优先级高.
//       } else {
//           return 0;
//       }// 上面这段代码可以简化为下面这句代码.// 这个比较的意义是：谁优先级高谁在前面.// 任何比较器都默认  // 如果返回负数认为o1的优先级更高  // 如果返回正数认为o2的优先级更高  // 任何比较器都是这样，所以利用这个设定，可以定制优先级怎么确定，也就是怎么比较  // 不再有大小的概念，就是优先级的概念  return o1.age - o2.age;  }  }  public static void main(String[] args) {  Employee s1 = new Employee(2, 27);  Employee s2 = new Employee(1, 60);  Employee s3 = new Employee(4, 19);  Employee s4 = new Employee(3, 23);  Employee s5 = new Employee(1, 35);  Employee s6 = new Employee(3, 55);  Employee[] arr = { s1, s2, s3, s4, s5, s6 };  Arrays.sort(arr, new EmployeeComparator());    // 按照上述比较器的方式进行排序.for (Employee e : arr) {  System.out.println(e.company + " , " + e.age);  }  System.out.println("=====");  Arrays.sort(arr, (a, b) -> b.age - a.age);    // 使用lambad表达式.可以进行简化, 这个遵循的还是谁大谁在前面.for (Employee e : arr) {  System.out.println(e.company + " , " + e.age);  }  System.out.println("=====");  // 所有员工，先按照谁的公司编号小，谁在前；如果公司编号一样，谁年龄小谁在前  Arrays.sort(arr, (a, b) -> a.company != b.company ? (a.company - b.company) : (a.age - b.age));  for (Employee e : arr) {  System.out.println(e.company + " , " + e.age);  }  // 一定要将比较方法放到这个里面. 因为我们实现的是自己实现的员工类型TreeSet<Employee> treeSet1 = new TreeSet<>(new EmployeeComparator());  for (Employee e : arr) {  treeSet1.add(e);  }  System.out.println(treeSet1.size());  // 会去重  treeSet1.add(new Employee(2, 27));  System.out.println(treeSet1.size());  System.out.println("===");  // 如果不想去重，就需要增加更多的比较  // 比如对象的内存地址、或者如果对象有数组下标之类的独特信息  TreeSet<Employee> treeSet2 = new TreeSet<>((a, b) -> a.company != b.company ? (a.company - b.company)  : a.age != b.age ? (a.age - b.age) : a.toString().compareTo(b.toString()));  for (Employee e : arr) {  treeSet2.add(e);  }  System.out.println(treeSet2.size());  // 不会去重  (堆是不进行去重的)treeSet2.add(new Employee(2, 27));  System.out.println(treeSet2.size());  System.out.println("===");  // PriorityQueue不会去重，不再展示了  
}

4. 字典序

先举两个例子：

两个字符串长度一样的时候： "ab"和"cd" 比较大小, 因为 c > a, 所以 "cd" > "ab". a, b, c, d 都可以认为是一个 26 进制的, 可以进行比较, 要是有什么 *, %, #, @ 也可以认为是一个 256 进制的. 都可以进行比较.
两个字符串长度不一样的时候："abcd"和"ck", 因为是和"字典"一样的, 所以肯定还是 "abcd" > "ck", 但是我们需要用数学的方式进行定义, 所以直接将短的那一个字符串补到和长的字符串一样长, 这个时候再进行比较, 并且要用 0(不是字符0, 是进制中最小的) 来补.

// 字典序  
String str1 = "abcde";  
String str2 = "ks";  
System.out.println(str1.compareTo(str2));  
// 可以认为str1是前, str2是后, 然后进行比较, 让前面的 - 后面的.  
System.out.println(str2.compareTo(str1));  
// 可以认为str2是前, str1是后, 然后进行比较, 让后面的 - 前面的.