数据结构和算法

发表于 更新于 分类于
1.汇总用 Java 写算法的一些小技巧；2.总结语雀上的所有算法笔记。方便每次笔试之前复习总结

算法

链表

快慢指针

链表倒数第n个数

分治法

排序

二分查找

【1】目标不存在于数组中，找第一个大于它的下标

【2】有多个目标存在于数组中，找第一个等于它的下标

【思路】基于二分查找，优化寻找 mid 指针和收敛 left right 指针的步骤，具体问题具体分析

  • mid=(left+right)>>2；if (nums[left]<nums[mid]) left=mid+1; else right=mid;【找左边】
  • mid=(left+right**+1**)>>2；if (nums[left]<=nums[mid]) left=mid; else right=mid-1;【找右边】

堆排序

数组实现大根堆的两个主要方法（注意动态扩容）

class Heap {
    int[] data;
    public void downHeapify(int i) {
        // 下标从0开始，子节点下标为2i+1和2i+2
        int l = i*2 + 1, r = i*2 + 2, largest = i;
        if (l < heapSize && data[l] > data[largest]) {
            largest = l;
        } 
        if (r < heapSize && data[r] > data[largest]) {
            largest = r;
        }
        if (largest != i) {
            swap(i, largest);
            maxHeapify(largest);
        }
    }
    public void upHeapify(int i) {
        // 父节点下标为(i-1)/2
        int parent = (i-1)/2, min = i;
        if (parent>=0 && data[parent] < data[i]) {
            min = parent;
        } 
        if (min != i) {
            swap(min, i);
            upHeapify(min);
        }
    }
}

动态规划

思路：动规的中心思想就是把一个复杂问题拆分成多个简单、可以逐步堆叠得到答案的子问题。

做题步骤

  1. 确定dp数组（dp table）以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组

0-1背包

每个物品只能用一次

下标含义：dp[物品 i ][容量 j ] 。如果 物品价值==物品种类，dp数组可以直接用 boolean[][]，不相等用 int[][]

状态转移方程：dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]]

初始化：物品 0 和容量 0 的情况

遍历顺序：二维数组先遍历物品和容量都可以，一维数组只能先遍历容量

树形 dp

题型：树的直径

思路：可以看作是再求树的深度，在求深度的同时“更新树的最长直径”。

代码模板

class LongestPath {
    List<Integer>[] g;
    int longestPath = 0;
    int dfs(int x) {
        // 两种思路：1.记录最大和次大长的路径；2.记录最大长 max，max+当前结果 和 result 比大小
        int max = 0;
        for (int child:g[x]) {
            int cur = dfs(child) + 1;
            longestPath = Math.max(longestPath, max + cur);
            max = Math.max(max, cur);
        }
        return max;
    }
    void solve() {
        int[] relate = {-1, 2, 4, 2, 3};  // 边的关系(题目给出)
        // 构建关系，List 存儿子节点，可以拓展到一般树的情况
        g = new ArrayList[relate.length];
        Arrays.setAll(g, e -> new ArrayList<>());
        for (int i = 1; i<relate.length; i++) {
            g[relate[i]].add(i);
        }
        dfs(0);
        System.out.println(longestPath);
    }
}

拓展：

  • 【124】求二叉树中最大的路径和。改左右子树的深度为节点值的和，若和为负数则返回 0
  • 【2245】一般树的最长路径。遍历所有邻居（过滤掉父节点），取最长、次长两条路径相加，结果为最长路径。此外，根据题意还要去除父子结点相同的情况。

题型：树上最大独立集（从图中选择尽量多的点，使得这些点互不相邻）

题型：树上最小支配集（从图中选择尽量少的点，使得这些点和其父子结点包括了整棵树）

二维 dp

题型：最长公共子序列

思路：定义 dp[i][j] 表示 text1[0:i-1] 和 text2[0:j-1] 的最长公共子序列

前缀和

应用题型：连续子数组

并查集

应用题型：检查树是否连通；构造最小生成树

扩展：带权并查集

数据结构模板

class Node {
    int[] father;
    Node (int size) {
        this.father = new int[size];
        for (int i = 0; i < size; ++i) father[i] = i;
    }
    // 找根节点
    int find(int i) {
        return i==father[i] ? i : (father[i] = find(father[i]));
    }
    // 加入 v->u 这条边
    void union(int x, int y) {
        tab[find(x)] = find(y);
    }
}

Java 功能代码

强制类型转换

  • 向零截断，直接保留整数位 1/2 == -1/2 == 0

基本数据类型的默认值

  • int \ double：0
  • boolean：false

常量池

  • 包装类型常量池：Byte, Short, Integer [-128,127], Long, Character, Boolean
  • 字符串常量池

初始化

  • 成员变量（定义在类里方法外的变量）一定要进行初始化的，如果不显式的进行初始化，那么虚拟机会进行默认的初始化
    • 基本数据类型一般是给予默认值
    • 引用类型初始值为 null
  • 局部变量不会自动初始化，所以在声明局部变量时要注意，可以不在声明时初始化，但在使用之前一定要进行初始化，否则会报编译错误

数组、列表快速初始化

int[] array = {1,2,3};
int[] array = new int[]{1,2,3};
int[][] array = {{1,2},{2,3}};
List<> list = Arrays.asList(1,2,3);  // 返回的是Arrays的内部类【无法增删】
List<> list = new ArrayList<>(){{
    add(1);
    add(2);
    add(3);
}};

初始化小根堆

使用优先级队列 PriorityQueue 实现小根堆

PriorityQueue<int[]> queue = new PriorityQueue<>((pair1,pair2) -> pair1[1]-pair2[1]);  // 数组
PriorityQueue<ListNode> queue = new PriorityQueue<>((o1, o2) -> o1.val-o2.val);  // 节点

queue.offer(data)  // 节点入堆
data = queue.poll()  // 头节点出堆

List 转数组

// 基本数据类型需要手动拆箱
int[] array = list.stream().mapToInt(Integer::valueOf).toArray();
// 流式
String[] array = list.stream().toArray(String[]::new);
// 串行【规定好数组大小，转换速度更快】
String[] array = list.toArray(new String[list.size()]);
String[] array = list.toArray(new String[0]);

数组转 List

// 基本数据类型需要手动装箱
int[] arr = { 1, 2, 3, 4, 5 };
List<Integer> list = Arrays.stream(arr).boxed().collect(Collectors.toList());
Integer[] integers = new Integer[]{3,8,20,7,11,25};
List<Integer> list = Arrays.asList(integers); 
// ArrayList<Object> list = new ArrayList<>();
// Collections.addAll(list, a);

位运算值交换

ch[a] ^= ch[b];
ch[b] ^= ch[a];
ch[a] ^= ch[b];

泛型&占位符

泛型：T E K V

泛型的初衷就是为了能在编译器检查出类型安全问题，并通过编译错误提示程序员

  • 泛型必须是引用类型，不能是基本类型
  • 泛型通过类型擦除实现

占位符：?

TODO lambda stream 流式计算 详解

位运算判断奇偶

num & 1 == 0

十进制数转 char

char t = Character.forDigit(i, 10);

Collection 转 List

Collection<T> collection = map.values();
List<T> list = new ArrayList<T>(collection);

Map 遍历方法

for (Map.Entry<Key.class, Value.class> entry : map.entrySet()) {
    System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
}

在条件语句中赋值

不能直接在 if 语句的条件部分进行声明和赋值，需要在 if 语句之前声明变量，并在条件语句中只进行赋值或比较操作

int dis;  
if ((dis = i - dp[i - 1]) > 1 && s.charAt(dis - 2) == '(') {  
    // ... 使用 dis 进行操作 ...  
}

StringBuilder/StringBuffer 常用方法

s.append(char c) // 将 char 追加到此序列
s.charAt(int index) // 返回指定索引处的此序列中的 char 值
s.deleteCharAt(int index) // 按此顺序删除指定位置的 char
s.setCharAt(int index, char ch) // 指定索引处的字符设置为 ch

String 内的字符串排序

String sort(String s) {
    char[] c = s.toCharArray();
    Arrays.sort(c);
    return new String(c);
}

HashMap 遍历 key 和 value

for (K key:map.keySet()) ;
for (V value:map.values()) ;

重难题反思

[560] 和为 K 的子数组

  • 前缀和+哈希表，存储前缀和为 sum 的次数（因为 num 有正有负）