Ruoke Zhang

不那么功利地学习

0%

发表于： 分类于：

灵神题单

合法括号字符串

32 最长有效括号

“()(())”

用一个数组tmp记录匹配成功的index。遇到(时，把它的 index 加入栈。遇到）时，从栈里pop出一个(，它们两个匹配成功，于是把tmp中它们两个的index上都标记为1.

发表于： 分类于：

LC 188

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

方法一：切片操作；取数组里的后k个元素：nums[-k%n:]

方法二：先反转整体，再反转局部. 反转过程单独实现，不要用切片，因为可能会产生额外空间。

发表于： 分类于：

参考：JavaGuide

并发问题

CPU Cache

Alt text Cahce中某个变量的值可能与 Main memory中的值不一致，导致计算出错。

指令级重排

编译器优化重排

JVM, JIT做这件事。对于Java程序，在不改变它的语义的情况下，编译时进行指令重排序，类似g1, g2 optimization的重排。

发表于： 分类于：

merge sort

LC 148: sort a linked list

快慢指针分成两半，断开中间，分别递归排序，最后升序合并两个链表。边界条件：head==None or head.next==None

LC 23. Merge k Sorted Lists

注意边界情况

quick sort

以数组某个元素（一般选取首元素）为基准数，将所有小于基准数的元素移动至其左边，大于基准数的元素移动至其右边。 python模版

发表于： 分类于：

参考：JavaGuide

线程

线程的实现

一个Java程序作为一个进程，运行时实际上是多线程并发的, main函数就是主线程。每个调用过start()方法，并且还未结束的java.lang.Thread类的实例就是一个线程。Java线程是Java程序的并发执行单位。

发表于： 分类于：

intervals.sort(key=lambda p: p[0])

LC 189 [:]切片操作

dict 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

# 包含初始键值对的字典
filled_dict = {'key1': 'value1', 'key2': 'value2'}

# 使用 dict() 构造函数
constructed_dict = dict(key1='value1', key2='value2')

valueList=list(filled_dict.values())

my_dict = {'apple': 1, 'banana': 2, 'cherry': 3}
for key in my_dict.keys():
    print(f"Key: {key}")

LC 49

发表于： 分类于：

reference：灵茶山艾府

定长滑窗

入：下标为i的元素进入窗口，更新相关统计量。如果i<k−1则重复第一步。

更新：更新答案。一般是更新最大值/最小值。

发表于： 分类于：

前缀和题单

一维前缀和

LC 1749

任意子数组和的绝对值的最大值: 在前缀和数组里面找最小值和最大值，他们的差的绝对值就是答案。

1
2
3

def maxAbsoluteSum(self, nums: List[int]) -> int:
    s = list(accumulate(nums, initial=0))  # nums 的前缀和
    return max(s) - min(s)

2055. 蜡烛之间的盘子

  1. 找a或其右边第一个蜡烛
  2. 找b或其左边第一个蜡烛
  3. 用前缀和，算他们之间的盘子数量

步骤1，2可以用二分，但是会超时
最好是预处理，记录每个位置左边/右边的第一个蜡烛位置

发表于： 分类于：

参考： 深入理解Java虚拟机 ， 极致八股文之JVM垃圾回收器G1&ZGC详解

对象已死？

引用计数算法 

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

/**
* testGC()方法执行后，objA和objB会不会被GC呢？
* @author zzm
*/
public class ReferenceCountingGC {
    public Object instance = null;
    private static final int _1MB = 1024 * 1024;
    /**
    * 这个成员属性的唯一意义就是占点内存，以便能在GC日志中看清楚是否有回收过
    */
    private byte[] bigSize = new byte[2 * _1MB];
    public static void testGC() {
    ReferenceCountingGC objA = new ReferenceCountingGC();
    ReferenceCountingGC objB = new ReferenceCountingGC();
    objA.instance = objB;
    objB.instance = objA;
    objA = null;
    objB = null;
    // 假设在这行发生GC，objA和objB是否能被回收？
    System.gc();
    }
}

缺点：这两个对象互相引用，导致他们的 reference counting 始终不能为 0，无法被回收。

发表于： 分类于：

灵神题单

线性dp

lc 377: 与完全背包的不同点在于：[1,3],[3,1]被算作两个不同的答案。因此解法类似permutation型的回溯。 如果用cache修饰 dfs, 则不能使用全局变量res来计算个数，必须把res作为 dfs的返回值。