Java_011_数据结构初探

参考资料

哈希表 (Hash Table)

  • 哈希表是一种将键映射到值的数据结构。它用哈希方程来将键映射到小范围的指数（一般为[0..哈希表大小-1]）
  • 可视化解析哈希表

栈 (Stack)

  • 栈是计算机科学中一种特殊的串列形式的抽象数据类型，其特殊之处在于只能允许在链表或数组的一端（称为栈顶端指针，英语：top）进行加入数据（英语：push）和输出数据（英语：pop）的运算。
  • 由于栈数据结构只允许在一端进行操作，因而按照后进先出（LIFO, Last In First Out）的原理运作.

数组实现栈
链表实现栈

队列 (Queue)

  • 是先进先出（FIFO, First-In-First-Out）的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端（称为rear）进行插入操作，在前端（称为front）进行删除操作。

数组实现队列
链表实现队列

参考资料

时间空间复杂度

表示法

  • 表示法O(n^n), O(n!), O(n²), O(n), O(1), O(nlogn)
  • 这些是规模的量级! 和N (数据量的大小)成比例的

目的

  • 评估算法的效率, 也就是需要耗费的时间(计算量)和空间(存储占用).
  • 主要关注点是相对于输入数据的规模
    • 快速排序 1000000
    • 冒泡排序 100
  • 简单来说, 时间复杂度就是基本语句的运算次数.

学习目标

时间复杂度的计算和证明是可以比较困难的. 但是常见的数据结构和算法的时间复杂度是很容易大致计算的!

主要目标是理解不同时间复杂度相对于输入数据量的增长速度是不一样的!

常用复杂度对比

  1. 数多少个循环嵌套: 平方, 立方, 还是4次方
  2. 如果遇到有”二分”这样的结构, 一般会是包含logn
  3. 数搜索空间

如何锻炼算法能力

  • 多做题!多训练!

哈希表

  1. 提供一个存储结构, 其中存储的是Key-Value对, Key和Value可以是任意的类型

    • 类似于数组(伪数组): 可以使用数组的下标索引(数字!!!!)去访问存储的数据!
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      Key可以是任何类型的! arr[名字] = 人的身份对象

      // 用js了
      var arr = [1,2,3];
      arr[0] // 1
      arr[1] // 2
      arr[2] // 3
      arr.length // 3

      var obj ={
          "0":1,
          "1":2,
          "2":3,
          "length":3
      }
      obj["0"] //1
      obj["1"] //2
      obj["2"] //3
      obj["length"] //3
  • 类似于f(x) = y这样的函数, 我们可以设置任意的f(x1) = y1, 或者f(x2) = y2.
  • 或者访问: a = f(x1)

它支持四种操作: 增删改查!

增加, 查询,修改和删除操作的时间复杂度都近似于 O(1) , 也不依赖于插入的顺序. 也就是随机访问(想访问哪个数据就马上访问哪个数据!)

不可以对 哈希表进行排序

  • 存储在哈希表里的数据没有顺序!!! 不可以对哈希表进行排序

数组和哈希表不一样的点

  • 数组的key只支持数字的, 但是哈希表支持更多的数据类型!
  • 数组在中间插入数据操作, 时间复杂度一般不是O(1)

栈

一个数据结构, 用于存储数据. 支持两种操作:

  • 插入数据 (push);
  • 取出数据 (pop); 获得数据, 同时把数据从栈中删除
  • 所有操作的时间复杂度度为O(1)

最重要的是, 哈希表可以随机访问. 但是栈对数据的访问顺序有规定. 遵循一个规则: 先进后出, 后进先出. 也就是只能访问当最近放进到栈里面的那个数据!

队列

一个类似于栈的数据结构, 用于存储数据, 同样支持两种操作:

  • 插入数据 (push);
  • 取出数据 (pop); 获得数据, 同时从队列中删除
  • 所有操作的时间复杂度为O(1)

队列遵循一个规则: 先进先出, 后进后出. 也就是从队列中取出数据的顺序和放进去的顺序是一样的!

遇到这种描述方式的时候, 尝试使用接口! 抽象数据类型

数据结构学习方法

  • 理解数据结构的操作！时间复杂度
  • 理解数据结构的属性
  • 理解数据结构的内部构造!!!
    • 这部分不用马上搞清楚，先把它用起来
    • 当你感兴趣，当你有时间，当你抑制不住你的好奇和求知欲就会自然而然去探索它的内部构造！！！
  • 应用—-> 训练！大量的训练！大量大量的训练！ 力扣300题是起点(一年时间做完)
    • 在美国 没有力扣300题 基本投简历就挂了
    • 但是如果你这些过了，你可以不会安卓，不会java 不会web不会mysql都无所谓
    • 抓住核心本质， 教你redis 一步步部署有用吗！
    • 想要职业生涯更广阔这是一个非常值得投入的地方

一定要给自己鼓励！不会就拿时间去磨，很多东西你想去做，就不会考虑困难

  • 追一个女孩子，被拒就不追了吗？
  • 这个问题解决了对我们利益足部足够大？
  • 目标不是学会，而是学了这个扩展视野获得经济

question

1简述哈希表的操作及其相应满足的特性

  • 增删查快
  • 修改慢
  • 时间负责度O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
import java.util.*;

public class T001_Hash {
    public static void main(String[] args) {

        Map<String,String> hashMap = new HashMap<>();

        // 增删改查

        // 增
        hashMap.put("张三","29");
        hashMap.put("李四","22");
        hashMap.put("王五","18");

        // 改
        // 如果key相同， 后面的覆盖前面的
        hashMap.put("王五","99");

        // 查
        // 根据key获取值
        System.out.println(hashMap.get("王五")); // 99

        // 判断key是否存在
        System.out.println(hashMap.containsKey("王五"));
        System.out.println(hashMap.containsKey("赵六"));

        // 删除
        /*
        * 删除成功则 返回删除的值，删除失败返回 null
        * */
        System.out.println(hashMap.remove("王五")); // 99
        System.out.println(hashMap.remove("赵六")); // null

        // 获取所有key
        Set<String> key_set = hashMap.keySet();

        // 循环 map
        for (String key:key_set) {
            String value = hashMap.get(key);
            System.out.println("key:" + key + ",value:" + value);
        }

        // 获取所有value   hashMap.values() 返回的是Collection 向下转型报错
        // 没法 这样 List<String> valuesList = (List<String>) map.values();
        // 在ArrayList中，有一个构造函数 可以接受一个集合类型的参数，然后返回一个list
        List<String> valuesList = new ArrayList<String>(hashMap.values());
        for(String str:valuesList){
            System.out.println(str);
        }

        // k-v对 的数量
        System.out.println(hashMap.size()); // 2

        // 清空 所有数据
        hashMap.clear();
        System.out.println(hashMap.size()); // 0

    }
}

2 简述栈的操作及其满足的特性或限制和时间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
package com.oop.demo.data;

import java.util.Stack;

public class Test2 {
    public static void main(String[] args) {

        // 栈
        Stack<Integer> stack = new Stack<Integer>();

        // 压栈
        stack.push(3);
        stack.push(5);

        // 出栈
        System.out.println(stack.pop()); // 5
        System.out.println(stack.pop()); // 3


        stack.push(66);
        // 只看顶部数据，但是不删除
        System.out.println(stack.peek()); // 66

        // 看栈是否为空
        System.out.println(stack.empty());

        // 深度优先搜索
        // 汉诺塔
        // 匹配 [({})] 是否配对
    }
}

3 简述队列的操作及其满足的特性或限制和时间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
package com.oop.demo.data;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Test2 {
    public static void main(String[] args) {
        // 队列  先进先出
        // Queue 是个接口 无法实例化
        // Queue<Integer> queue = new Queue<Integer>();

        Queue<Integer> queue = new LinkedList<Integer>();


        queue.add(3);
        queue.add(5);

        System.out.println(queue.poll()); // 3
        System.out.println(queue.poll()); // 5

        Integer firstVal = queue.peek();

        //  queue.isEmpty() 和 上面的 Stack 不一致 stack.empty()
        // 这就是因为 接口不稳定导致，以至于现在就无法改了，因为已经批量使用了
        System.out.println( queue.isEmpty());

        // 消息队列
        // 买票
        // 广度优先搜索
    }
}

4 栈的练习题

5 队列练习题

6 两数之和

js版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var twoSum = function(nums, target) {
    let res = [];
    
    // 第一次的思路 两层循环 
    /* 
        第一层循环锁定 i=0 的值 1
        第二层循环从   j = i+1 之后开始循环 比对（因为循环时不该包括已经选定的值）
            只要 nums[i] + nums[j] === target 就返回结果
    */ 
    for(let i = 0;i<nums.length-1;i++){
      for(let j = i + 1;j<nums.length;j++){
          if(nums[i] + nums[j] === target){
              res.push(i,j);
              break;
          }
      }
    }  
    return res;
};

java版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public class Solution {

    public static int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        // 第一次的思路 两层循环
    /*
        第一层循环锁定 i=0 的值 1
        第二层循环从   j = i+1 之后开始循环 比对（因为循环时不该包括已经选定的值）
            只要 nums[i] + nums[j] === target 就返回结果
    */
        for(int i = 0;i<nums.length-1;i++){
            for(int j = i + 1;j<nums.length;j++){
                if(nums[i] + nums[j] == target){
                    res[0] = i;
                    res[1] = j;
                    break;
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[][] arr = {
                {2,7,11,15},
                {2,6,11,15},
                {0,7,1,3},
                {5,7,110,12},
                {10,90,101,1},
        };
        int[] target = {
                9,
                13,
                4,
                19,
                111
        };

        for (int i = 0; i < arr.length; i++) {
            int[] res = twoSum(arr[i],target[i]);
            System.out.println("["+res[0]+","+res[1]+"]");
        }
    }
}

7字母统计

给一个字符串 (只包含26个字母)，统计每个字母出现的次数(返回类型为HashMap)

样例

  • 给出 numbers = “alexyang”, 返回一个HashMap counts,里面包含所有26个字母出现的次数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

public class WordCounter {
    public static HashMap count(String input) {
        HashMap<String,Integer> map = new HashMap<String,Integer>();
        // 写具体实现
        for (int i = 0; i <input.length() ; i++) {
            String key = input.charAt(i) + "";
            if(map.containsKey(key)){
                int value = map.get(key);
                map.put(key,value+1);
            }else{
                map.put(key,1);
            }
        }
        return map;
    }


    public static void main(String[] args) {
        String[] a =  {"alexyang","huangjx","zhangsan","bbbbdddd","abbccc"};
        for (int i = 0; i < a.length ; i++) {
            HashMap<String,Integer> map = count(a[i]);
            System.out.println(map);
        }
    }
}
  • 请实现count方法.
  • 然后在main()方法中至少写5组测试用例, 测试你的实现.

8 括号匹配序列

  • 给定一个字符串所表示的括号序列，包含以下字符： ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’， 判定是否是有效的括号序列。
  • 例子 
    1
    括号必须依照 "()" 顺序表示， "()[]{}" 是有效的括号，但 "([)]"则是无效的括号。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class T003Solution {
    public static void main(String[] args) {
        String[] arr = {"{}{}()()[][]","{[()()()[]]}","{(([])([])())}","[]]","[[[["};
        for (int i = 0; i < arr.length; i++) {
            boolean res = isValidParentheses(arr[i]);
            System.out.println(res);
        }
    }

    public static boolean isValidParentheses(String s) {
        Map<String,String> map = new HashMap<String,String>();
        map.put("{","}");
        map.put("(",")");
        map.put("[","]");
        map.put("}","{");
        map.put(")","(");
        map.put("]","[");
        Stack<String> stack = new Stack<String>();
        for (int i = 0; i < s.length() ; i++) {
            String currentVal = s.charAt(i) + "";
            if(stack.empty()){
                stack.push(currentVal);
            }else{
                String convertVal = map.get(currentVal);
                String topValue = stack.peek();
                if(topValue.equals(convertVal)){
                    stack.pop();
                }
            }
        }
        return stack.empty();
    }
}