倬倬吃三碗
0%

数据结构笔记

发表于 更新于 分类于

序

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

常见的数据结构有如下：

总体

数组

数组是讲相同类型的元素存储于连续内存空间的数据结构，长度不可变。

初始化时需要给定长度并对每个索引元素赋值：

1
2
3
4
5
6
7
8
9
// 初始化一个长度为 5 的数组 array
int[] array = new int[5];
// 元素赋值
array[0] = 2;
array[1] = 3;
array[2] = 1;
array[3] = 0;
array[4] = 2;

或者可以使用直接复制的初始化方式：

1
int[] array = {2,3,1,0,2}

Picture2.png

“可变数组”是经常使用的数据结构，其基于数组和扩容机制实现，相比普通数组更加灵活.常用的操作有:访问元素、添加元素、删除元素：

1
2
3
4
5
6
7
8
//初始化可变数组
List<Integer> array = new ArrayList<>():
//向尾部添加元素
array.add(2);
array.add(3);
array.add(1);
array.add(0);
array.add(2);

LC485.最大连续1的个数

给定一个二进制数组 nums ， 计算其中最大连续 1 的个数。

示例 1：

输入：nums = [1,1,0,1,1,1]
输出：3
解释：开头的两位和最后的三位都是连续 1 ，所以最大连续 1 的个数是 3.
示例 2:

输入：nums = [1,0,1,1,0,1]
输出：2

提示：

1 <= nums.length <= 105
nums[i] 不是 0 就是 1.

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/max-consecutive-ones
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

count记录当前连续1个数，遇到0时在当前count与result中取最大值赋给result，并重置当前count重新计数。

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
class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        //边界判断
        if(nums == null || nums.length == 0){
            return 0;
        }

        //初始化count和result
        int count = 0;
        int result = 0;
        //遍历数组，如果当前元素是1则count+1
        //如果不是1则代表连续段已完，max比较count与result大小，更新result，之后count重置为0
        for(int i = 0; i < nums.length; i++){
            if(nums[i] == 1){
                count++;
            }else{
                result = Math.max(result, count);
                count = 0;
            }
        }
        //返回遍历更新完的最终result，因为元素不等于1时才进行result的更新，如果数组结尾是连续1时则不会进行更新操作。所以此处需要再次max来比较一下
        return Math.max(result, count);
    }
}

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        #边界判断
        if nums is None or len(nums) == 0:
            return 0
        #初始化count和result
        count = 0
        result = 0
        #遍历数组，如果当前元素是1则count+1
        #如果不是则1则代表连续段已完，max比较count与result的大小，更新result，之后count重置为0
        for num in nums:
            if num == 1:
                count = count + 1
            else:
                result = max(result, count)
                count = 0
        #返回遍历更新完的最终result，因为元素不等于1时才进行result的更新，如果数组结尾是连续1时则不会进行更新操作。所以此处需要再次max来比较一下
        return max(result,count)

LC283.移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:

输入: nums = [0]
输出: [0]

提示:

1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1

进阶：你能尽量减少完成的操作次数吗？

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/move-zeroes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

遍历数组，当前不为0则赋给索引为0的位置并index+1，

非0元素都移动到前面去后，

从i=index出发，对剩下的都赋0

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public void moveZeroes(int[] nums) {
        //初始化index为0
        int index = 0;
        //遍历数组，如果当前元素不为0则将该元素赋给nums[index],index加1
        for(int i = 0; i < nums.length; i++){
            if(nums[i] != 0){
                nums[index] = nums[i];
                index++;
            }
        }
        //遍历完后，此时从下标0到下标index都不为0
        //从下标index遍历到数组末尾，全部赋为0
        for(int i = index; i < nums.length; i++){
            nums[i] = 0;
        }
    }
}

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        #初始化index为0
        index = 0
        #遍历数组，如果当前元素不为0则将该元素赋给nums[index]，index加1
        for num in nums:
            if num != 0:
                nums[index] = num
                index += 1
        #遍历完后，此时从下标0到下标index都不为0
        #从下标index遍历到数组末尾，全部赋为0
        for i in range(index, len(nums)):
            nums[i] = 0

LC27.移动元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

提示：

0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/remove-element
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

双指针，i找到val时停下，j找不到val时停下

i，j值交换

i >= j时，循环停止。前半部分是有效部分，存储不等于val的元素，后半部分是无效部分，存储等于val的元素，需要返回前半部分

判断如果nums[l] == val，代表l的值等于当前数组的长度,直接返回

否则返回l + 1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int removeElement(int[] nums, int val) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        int l = 0;
        int r = nums.length - 1;
        while(l<r){
            while(l < r && nums[l] != val){
                l++;
            }
            while(l <r && nums[r] == val){
                r--;
            }
            int temp = nums[l];
            nums[l] = nums[r];
            nums[r] = temp; 
        }
        return nums[l] == val? l: l+1;
    }
}

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        if nums is None or len(nums) == 0:
            return 0
        l,r = 0,len(nums) - 1
        while(l < r):
            while(l < r and nums[l] != val):
                l +=1
            while(l < r and nums[r] == val):
                r -= 1
            nums[l],nums[r] = nums[r],nums[l]
        if nums[l] == val:
            return l
        else:
            l+1

链表

链表以节点为单位，每个元素都是一个独立对象，在内存空间的存储是非连续的。链表的节点对象具有两个成员变量：「值 val」，「后继节点引用 next」 。

1
2
3
4
5
class ListNode {
    int val;       // 节点值
    ListNode next; // 后继节点引用
    ListNode(int x) { val = x; }
}

建立链表需要实例化每个节点，并构建各节点的引用指向。

1
2
3
4
5
6
7
8
//实例化节点
ListNode n1 = new ListNode(4); //头节点 head
ListNode n2 = new ListNode(5);
ListNode n3 = new ListNode(1);

//构建引用指向
n1.next = n2;
n2.next = n3;

Picture3.png

LC203.移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
示例 2：

输入：head = [], val = 1
输出：[]
示例 3：

输入：head = [7,7,7,7], val = 7
输出：[]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/remove-linked-list-elements
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

image-20220725162838134

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        while(head != null){
            if(head.val == val){
                prev.next = head.next;
            }else{
                prev = head;
            }
            head = head.next;
        }
        return dummy.next;
            
    }
}

Python3

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        dummy = ListNode(0)
        dummy.next = head
        prev = dummy
        while head is not None:
            if head.val == val:
                prev.next = head.next
            else:
                prev = prev.next
            head = head.next
        return dummy.next

队列

队列是一种具有 「先入先出」 特点的抽象数据结构，可使用链表实现。

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

如下图所示，通过常用操作「入队 push()」,「出队 pop()」，展示了队列的先入先出特性。

1
2
3
4
queue.offer(1);	//元素1入队
queue.offer(2); //元素2入队
queue.poll();	//出队 -> 元素1
queue.poll();	//出队 -> 元素2

Picture5.png

image-20220725165651220

LC933.最近的请求次数

写一个 RecentCounter 类来计算特定时间范围内最近的请求。

请你实现 RecentCounter 类：

RecentCounter() 初始化计数器，请求数为 0 。
int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。确切地说，返回在 [t-3000, t] 内发生的请求数。
保证 每次对 ping 的调用都使用比之前更大的 t 值。

示例 1：

输入：
[“RecentCounter”, “ping”, “ping”, “ping”, “ping”]
[[], [1], [100], [3001], [3002]]
输出：
[null, 1, 2, 3, 3]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/number-of-recent-calls
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

image-20220725165931229

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.LinkedList;
import java.util.Queue;

class RecentCounter {
    Queue<Integer> queue;
    public RecentCounter() {
            queue = new LinkedList<>();
    }
    
    public int ping(int t) {
        queue.add(t);
        while(!queue.isEmpty() && t - queue.peek() > 3000){
            queue.poll();
        }
        return queue.size();
    }
}

Python3

1
2
3
4
5
6
7
8
9
10
class RecentCounter:

    def __init__(self):
        self.q = deque()

    def ping(self, t: int) -> int:
        self.q.append(t)
        while len(self.q) > 0 and t - self.q[0] > 3000:
            self.q.popleft()
        return len(self.q)

栈

栈是一种具有 「先入后出」 特点的抽象数据结构，可使用数组或链表实现。

1
Stack<Integer> stack = new Stack<>();

如下图所示，通过常用操作「入栈 push()」,「出栈 pop()」，展示了栈的先入后出特性。

1
2
3
4
stack.push(1); //元素1入栈
stack.push(2); //元素2入栈
stack.pop();   // 出栈 -> 元素 2
stack.pop();   // 出栈 -> 元素 1

Picture4.png

注意：通常情况下，不推荐使用 Java 的 Vector 以及其子类 Stack ，而一般将 LinkedList 作为栈来使用。

1
2
3
4
5
6
LinkedList<Integer>stack = new LinkedList<>()

stack.addLast(1);   // 元素 1 入栈
stack.addLast(2);   // 元素 2 入栈
stack.removeLast(); // 出栈 -> 元素 2
stack.removeLast(); // 出栈 -> 元素 1

image-20220725164321959

LC20.有效的括号

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例 1：

输入：s = “()”
输出：true
示例 2：

输入：s = “()[]{}”
输出：true
示例 3：

输入：s = “(]”
输出：false
示例 4：

输入：s = “([)]”
输出：false
示例 5：

输入：s = “{[]}”
输出：true

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

image-20220725164901141

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
class Solution {
    public boolean isValid(String s) {
        if(s.length() == 0){
            return true;
        }

        Stack<Character> stack = new Stack<>();
        for (char ch: s.toCharArray()){
            if(ch =='(' || ch == '{' || ch =='['){
                stack.push(ch);
            }else{
                if(stack.isEmpty()){
                    return false;
                }else{
                    char temp = stack.pop();
                    if(ch ==')'){
                        if(temp != '('){
                            return false;
                        }
                    }else if(ch == ']'){
                        if(temp != '['){
                            return false;
                        }                      
                    }else if(ch == '}'){
                        if(temp != '{'){
                            return false;
                        }
                    }
                }
            }
        }

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) == 0:
            return True
        stack = []
        for c in s:
            if c == '(' or c == '[' or c == '{':
                stack.append(c)
            else:
                if len(stack) == 0:
                    return False
                else:
                    temp = stack.pop()
                    if c == ')':
                        if temp != '(':
                            return False
                    elif c ==']':
                        if temp != '[':
                            return False
                    elif c == '}':
                        if temp != '{':
                            return False
        return True if len(stack) == 0 else False

LC496.下一个更大元素

nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。

给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。

对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。

返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。

示例 1：

输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
输出：[-1,3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：

  • 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
  • 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
  • 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
    示例 2：

输入：nums1 = [2,4], nums2 = [1,2,3,4].
输出：[3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：

  • 2 ，用加粗斜体标识，nums2 = [1,2,3,4]。下一个更大元素是 3 。
  • 4 ，用加粗斜体标识，nums2 = [1,2,3,4]。不存在下一个更大元素，所以答案是 -1 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/next-greater-element-i
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

image-20220725165527805

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
import java.util.Stack;
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] res = new int[nums1.length];
        Stack<Integer> stack = new Stack<>();
        for(int num:nums2){
            stack.push(num);
        }
        for(int i = 0; i < nums1.length; i++){
            Stack<Integer> temp = new Stack<>();
            boolean isFound = false;
            int cur = nums1[i];
            int max = -1;
            while(!stack.isEmpty() && !isFound){
                int top = stack.pop();
                if(top > cur){
                    max = top;
                }else if (top == cur){
                    isFound = true;
                }
                temp.push(top);
            }
            res[i] = max;
            while(!temp.isEmpty()){
                stack.push(temp.pop());
            }
        }
        return res;
    }
}

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        res = []
        stack = []
        mapping = {}
        for num in nums2:
            while len(stack) != 0 and num > stack[-1]:
                temp = stack.pop()
                mapping[temp] = num
            stack.append(num)

        while len(stack) != 0:
            mapping[stack.pop()] = -1

        for num in nums1:
            res.append(mapping[num])

        return res

散列表

散列表是一种非线性数据结构，通过利用 Hash 函数将指定的「键 key」映射至对应的「值 value」，以实现高效的元素查找。

设想一个简单场景：小力、小特、小扣的学号分别为 10001, 10002, 10003 。
现需求从「姓名」查找「学号」。

则可通过建立姓名为 key ，学号为 value 的散列表实现此需求，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
// 初始化散列表
Map<String, Integer> dic = new HashMap<>();

// 添加 key -> value 键值对
dic.put("小力", 10001);
dic.put("小特", 10002);
dic.put("小扣", 10003);

// 从姓名查找学号
dic.get("小力"); // -> 10001
dic.get("小特"); // -> 10002
dic.get("小扣"); // -> 10003

Hash函数设计Demo

假设需求：从「学号」查找「姓名」。

将三人的姓名存储至以下数组中，则各姓名在数组中的索引分别为 0, 1, 2 。

1
String[] names = {"小力","小特","小扣"}:

此时，我们构造一个简单的 Hash 函数（ %% 为取余符号 ），公式和封装函数如下所示：

hash(key) = (key - 1) % 10000

1
2
3
4
int hash(int id) {
    int index = (id - 1) %1000;
    return index;
}

则我们构建了以学号为 key 、姓名对应的数组索引为 value 的散列表。利用此 Hash 函数，则可在 O(1)O(1) 时间复杂度下通过学号查找到对应姓名，即：

1
2
3
names[hash(10001)] // 小力
names[hash(10002)] // 小特
names[hash(10003)] // 小扣

以上设计只适用于此示例，实际的 Hash 函数需保证低碰撞率、 健壮性等，以适用于各类数据和场景。

image-20220727143717085

LC217.存在重复元素

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

示例 1：

输入：nums = [1,2,3,1]
输出：true
示例 2：

输入：nums = [1,2,3,4]
输出：false
示例 3：

输入：nums = [1,1,1,3,3,4,3,2,4,2]
输出：true

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/contains-duplicate
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

image-20220727144826899

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    public boolean containsDuplicate(int[] nums) {
        if(nums == null || nums.length == 0){
            return false;
        }
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int num : nums){
            if(map.containsKey(num)){
                map.put(num,map.get(num)+1);
            }else{
                map.put(num,1);
            }
        }

        for(int k: map.keySet()){
            if(map.get(k) > 1){
                return true;
            }
        }
        return false;
    }
}

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        if len(nums) == 0:
            return False
        mapping = {}
        for num in nums:
            if num not in mapping:
                mapping[num] = 1
            else:
                mapping[num] = mapping.get(num) + 1
        for v in mapping.values():
            if v > 1:
                return True
        return False

LC389.找不同

给定两个字符串 s 和 t ，它们只包含小写字母。

字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。

请找出在 t 中被添加的字母。

示例 1：

输入：s = “abcd”, t = “abcde”
输出：”e”
解释：’e’ 是那个被添加的字母。
示例 2：

输入：s = “”, t = “y”
输出：”y”

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-the-difference
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

image-20220727145658582

S里就+1，T里就-1，+1-1抵消

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public char findTheDifference(String s, String t) {
        int sizeS = s.length();
        int sizeT = t.length();
        if(sizeS == 0){
            return t.charAt(0);
        }
        int[] table = new int[26];
        for(int i = 0; i < sizeT; i++){
            if(i < sizeS){
                table[s.charAt(i)-'a']++;
            }
            table[t.charAt(i)-'a']--;
        }
        for(int i = 0; i < 26; i++){
            if(table[i] != 0){
                return(char)('a'+i);
            }
        }
        return 'a';
    }
}

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        if len(s) == 0:
            return t
        table = [0]*26
        for i in range(len(t)):
            if i < len(s):
                table[ord(s[i])-ord('a')] -= 1
            table[ord(t[i])-ord('a')] += 1
        for i in range(26):
            if table[i] != 0:
                return chr(i+97)
        return 'a'

集合

image-20220727153141004

LC217.存在重复元素

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

示例 1：

输入：nums = [1,2,3,1]
输出：true
示例 2：

输入：nums = [1,2,3,4]
输出：false
示例 3：

输入：nums = [1,1,1,3,3,4,3,2,4,2]
输出：true

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/contains-duplicate
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

image-20220727153844464

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import java.util.Arrays;
import java.util.HashSet;

class Solution {
    public boolean containsDuplicate(int[] nums) {
        if(nums == null || nums.length == 0){
            return false;
        }
        HashSet<Integer> set = new HashSet<>();
        for(int num : nums){
            set.add(num);
        }
        return set.size() == nums.length? false : true;
    }
}

Python3

1
2
3
4
5
6
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        if len(nums) == 0:
            return False
        hashset = set(nums)
        return False if len(nums) == len(hashset) else True

LC705.设计哈希集合

不使用任何内建的哈希表库设计一个哈希集合（HashSet）。

实现 MyHashSet 类：

void add(key) 向哈希集合中插入值 key 。
bool contains(key) 返回哈希集合中是否存在这个值 key 。
void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。

示例：

输入：
[“MyHashSet”, “add”, “add”, “contains”, “contains”, “add”, “contains”, “remove”, “contains”]
[[], [1], [2], [1], [3], [2], [2], [2], [2]]
输出：
[null, null, null, true, false, null, true, null, false]

解释：
MyHashSet myHashSet = new MyHashSet();
myHashSet.add(1); // set = [1]
myHashSet.add(2); // set = [1, 2]
myHashSet.contains(1); // 返回 True
myHashSet.contains(3); // 返回 False ，（未找到）
myHashSet.add(2); // set = [1, 2]
myHashSet.contains(2); // 返回 True
myHashSet.remove(2); // set = [1]
myHashSet.contains(2); // 返回 False ，（已移除）

提示：

  • 0 <= key <= 106
  • 最多调用 104 次 add、remove 和 contains

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/design-hashset
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

image-20220727160436191

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class MyHashSet {

    boolean[] hashSet = null;

    public MyHashSet() {
        hashSet = new boolean[1000001];
    }
    
    public void add(int key) {
        hashSet[key] = true;
    }
    
    public void remove(int key) {
        hashSet[key] = false;
    }
    
    public boolean contains(int key) {
        return hashSet[key];
    }
}

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
class MyHashSet:

    def __init__(self):
        self.hashset = [0]*1000001

    def add(self, key: int) -> None:
        self.hashset[key] = 1

    def remove(self, key: int) -> None:
        self.hashset[key] = 0

    def contains(self, key: int) -> bool:
        return bool(self.hashset[key])

树

树是一种非线性数据结构，根据子节点数量可分为 「二叉树」 和 「多叉树」，最顶层的节点称为「根节点 root」。以二叉树为例，每个节点包含三个成员变量：「值 val」、「左子节点 left」、「右子节点 right」

1
2
3
4
5
6
class TreeNode {
    int val;        // 节点值
    TreeNode left;  // 左子节点
    TreeNode right; // 右子节点
    TreeNode(int x) { val = x; }
}

如下图所示，建立此二叉树需要实例化每个节点，并构建各节点的引用指向。

1
2
3
4
5
6
7
8
9
10
11
12
// 初始化节点
TreeNode n1 = new TreeNode(3); // 根节点 root
TreeNode n2 = new TreeNode(4);
TreeNode n3 = new TreeNode(5);
TreeNode n4 = new TreeNode(1);
TreeNode n5 = new TreeNode(2);

// 构建引用指向
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;

image-20220727143537452

image-20220727143604216

堆

堆是一种基于「完全二叉树」的数据结构，可使用数组实现。以堆为原理的排序算法称为「堆排序」，基于堆实现的数据结构为「优先队列」。堆分为「大顶堆」和「小顶堆」，大（小）顶堆：任意节点的值不大于（小于）其父节点的值。

完全二叉树定义： 设二叉树深度为 k ，若二叉树除第 k 层外的其它各层（第 11 至 k-1 层）的节点达到最大个数，且处于第 k 层的节点都连续集中在最左边，则称此二叉树为完全二叉树。

如下图所示，为包含 1, 4, 2, 6, 8 元素的小顶堆。将堆（完全二叉树）中的结点按层编号，即可映射到右边的数组存储形式。

通过使用「优先队列」的「压入 push()」和「弹出 pop()」操作，即可完成堆排序，实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 初始化小顶堆
Queue<Integer> heap = new PriorityQueue<>();

// 元素入堆
heap.add(1);
heap.add(4);
heap.add(2);
heap.add(6);
heap.add(8);

// 元素出堆（从小到大）
heap.poll(); // -> 1
heap.poll(); // -> 2
heap.poll(); // -> 4
heap.poll(); // -> 6
heap.poll(); // -> 8

image-20220727164726636

LC215.数组中的第k个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4], k = 2
输出: 5
示例 2:

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/kth-largest-element-in-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

image-20220727165731247

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.Collections;
import java.util.PriorityQueue;

class Solution {
    public int findKthLargest(int[] nums, int k) {
        if(nums == null || nums.length < k || k == 0){
            return Integer.MIN_VALUE;
        }

        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for(int num:nums){
            pq.add(num);
        }

        while(k > 1){
            pq.poll();
            k--;
        }

        return pq.poll();
    }
}

Python3

1
2
3
4
5
6
7
8
9
10
11
import heapq
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = []
        heapq.heapify(heap)
        for num in nums:
            heapq.heappush(heap,num*-1)
        while k > 1:
            heapq.heappop(heap)
            k = k - 1
        return heapq.heappop(heap)*-1

*LC.692.前K个高频单词

给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。

示例 1：

输入: words = [“i”, “love”, “leetcode”, “i”, “love”, “coding”], k = 2
输出: [“i”, “love”]
解析: “i” 和 “love” 为出现次数最多的两个单词，均为2次。
注意，按字母顺序 “i” 在 “love” 之前。
示例 2：

输入: [“the”, “day”, “is”, “sunny”, “the”, “the”, “the”, “sunny”, “is”, “is”], k = 4
输出: [“the”, “is”, “sunny”, “day”]
解析: “the”, “is”, “sunny” 和 “day” 是出现次数最多的四个单词，
出现次数依次为 4, 3, 2 和 1 次。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/top-k-frequent-words
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

image-20220727170454102

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
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.PriorityQueue;

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        HashMap<String, Integer> mapping = new HashMap<>();

        for(String word:words){
            if(!mapping.containsKey(word)){
                mapping.put(word,0);
            }
            int count = mapping.get(word) + 1;
            mapping.put(word,count);
        }

        PriorityQueue<String> pq = new PriorityQueue<>(
            (w1,w2) -> mapping.get(w1).equals(mapping.get(w2)) ? w2.compareTo(w1) : mapping.get(w1) - mapping.get(w2)
        );
        
        for(String word : mapping.keySet()){
            pq.add(word);
            if(pq.size() > k){
                pq.poll();
            }
        }

        List<String> res = new ArrayList<>();
        while(!pq.isEmpty()){
            res.add(pq.poll());
        }

        Collections.reverse(res);
        return res;
    }
}

Python3

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
import heapq

class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        mapping = {}
        for word in words:
            if word not in mapping:
                mapping[word] = 0
            mapping[word] = mapping[word] + 1
        
        print(mapping)
        heap = []
        for key,value in mapping.items():
            heapq.heappush(heap,Node(key,value))
            if len(heap) > k:
                heapq.heappop(heap)

        res = []
        while len(heap) > 0:
            temp = heapq.heappop(heap)
            print(temp.key," ",temp.value)
            res.append(temp.key)

        res.reverse()

        return res

class Node:
    def __init__(self,key,value):
        self.key = key
        self.value = value

图

图是一种非线性数据结构，由「节点（顶点）vertex」和「边 edge」组成，每条边连接一对顶点。根据边的方向有无，图可分为「有向图」和「无向图」。本文 以无向图为例 开展介绍。

如下图所示，此无向图的 顶点 和 边 集合分别为：

  • 顶点集合： vertices = {1, 2, 3, 4, 5}

  • 边集合： edges = {(1, 2), (1, 3), (1, 4), (1, 5), (2, 4), (3, 5), (4, 5)}

  1. 邻接矩阵： 使用数组 verticesvertices 存储顶点，邻接矩阵 edgesedges 存储边； edges[i][j]edges[i][j] 代表节点 i + 1i+1 和 节点 j + 1j+1 之间是否有边。

    1
    2
    3
    4
    5
    6
    7
    vertices = [1, 2, 3, 4, 5]
    edges = [[0, 1, 1, 1, 1],
             [1, 0, 0, 1, 0],
             [1, 0, 0, 0, 1],
             [1, 1, 0, 0, 1],
             [1, 0, 1, 1, 0]]

  2. 邻接表： 使用数组 verticesvertices 存储顶点，邻接表 edgesedges 存储边。 edgesedges 为一个二维容器，第一维 ii 代表顶点索引，第二维 edges[i]edges[i] 存储此顶点对应的边集和；例如 edges[0] = [1, 2, 3, 4]edges[0]=[1,2,3,4] 代表 vertices[0]vertices[0] 的边集合为 [1, 2, 3, 4][1,2,3,4] 。

    1
    2
    3
    4
    5
    6
    vertices = [1, 2, 3, 4, 5]
    edges = [[1, 2, 3, 4],
             [0, 3],
             [0, 4],
             [0, 1, 4],
             [0, 2, 3]]

    邻接矩阵 VS 邻接表 ：

    邻接矩阵的大小只与节点数量有关，即 N^2,其中 N 为节点数量。因此，当边数量明显少于节点数量时，使用邻接矩阵存储图会造成较大的内存浪费。
    因此，邻接表 适合存储稀疏图（顶点较多、边较少）； 邻接矩阵 适合存储稠密图（顶点较少、边较多）。

image-20220727171214457

1
2
3
4
作者：Krahets
链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/50e446/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。