使用「前缀和」解决力扣 560 号问题:和为 K 的子数组
前缀和,是指一个数组的某下标 i 之前的所有数组元素的和(包不包括 i 都可)。比如,现有数组:[1, 2, 3, 4, 5],那么对应的前缀和数组就是 [0, 1, 3, 6, 10, 15]。使用前缀和可以通过预处理数组来降低每次求和的复杂度。
如果没有前缀和数组,我们想计算数组位置 [1, 3] 的和,是不是需要写一个 for(int i = 1; i <= 3; i++) sum += nums[i]; 循环。计算一次还好,如果是需要计算上千上万次呢?如果数组非常大呢?这样简单的用 for 循环是不是很费时间?
我们通过预处理计算出前缀和数组,就能很容易的在 O(1) 的时间复杂度内求得任意数组位置的和。
int[] nums = new int[]{1,2,3,4,5};int[] prefixSum = new int[nums.length + 1];prefixSum[0] = 0;for (int i = 0; i < nums.length; i++) { prefixSum[i + 1] = nums[i] + pr ...
牛客网ACM编程模式Java模版
数组输入import java.util.*;/* 对于每一组测试数据,第一行输入两个整数 n,k 代表这个序列的长度和要判断的元素 接下来输入 n 个整数,a[i] 表示序列中第 i 个元素 举例: 5 8 1 2 3 4 5 */public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { int n = sc.nextInt(); int k = sc.nextInt(); int[] nums = new int[n]; for (int i = 0; i < n; i++) { nums[i] = sc.nextInt(); } ...
LRU(最近最少使用)缓存
这道题是 LeetCode 中的第 146 号问题。LRU(Least Recently Used) 对计算机科班出身的同学应该不会陌生,那么今天就自己动手实现一个 LRU。
这是题目给出的模版:
class LRUCache { public LRUCache(int capacity) { } public int get(int key) { } public void put(int key, int value) { }}/** * Your LRUCache object will be instantiated and called as such: * LRUCache obj = new LRUCache(capacity); * int param_1 = obj.get(key); * obj.put(key,value); */ 特殊要求:get 和 put 方法都要是 O(1) 的时间复杂度
首先我们可以很容易想到,用 Hash ...
JVM垃圾收集器
Java 与 C++ 之间有一堵由内存动态分配和垃圾收集技术所围成的高墙,墙外的人想进来,墙里面的人想出去。
本文用的是 HotSpot 虚拟机,其垃圾收集器有 10 种,分别是:
Serial
ParNew
Parallel Scavenge
Serial Old
Parallel Old
CMS
G1(Garbage First)
低延迟收集器:
Shenandoah
ZGC
不清理垃圾的收集器:
Epsilon
Serial(最经典)Serial 是 HotSpot 中最经典的垃圾收集器。因为它是单线程收集器,因此其工作的时候一定要「Stop The World」。
其采取的收集策略是:新生代采用「标记-复制」算法,老年代采用「标记-整理」算法。
其优势是:简单而高效。因此 Serial 是 HotSpot 在客户端模式下的默认收集器。
ParNew(HotSpot 中第一款退出历史舞台的收集器)ParNew 可以理解为是 Serial 的多线程并行版本。
并行(Parallel):多条垃圾收集器之间的关系。
并发(Concurrent):垃圾收集器线程与用户线程 ...
递归回溯问题(排列和组合)
写在前面:本文的一些定义不一定是对的,我就是把我的思路写出来了。
递归一般是和树紧密相连的。回溯也可以认为是在树形结构中进行的。
回溯就是递归触底了然后向上返。同时在向上返的过程中要注意「恢复状态」。不能说返回到上一级了,状态还是当前层级的。
回溯问题一般和排列、组合问题关系比较密切。排列、组合需要枚举所有的可能性,枚举的过程就可以画出一棵树形图,然后在树里边选择符合题意的。因此解答回溯问题一般都是建议要先画出树形图。
画好树形图,就可以写代码了。
下面总结了几个技巧:
大概的框架:
这题是 39 号问题,这里只用来说明一般的代码框架。
public List<List<Integer>> combinationSum(int[] candidates, int target) { // 一般都会用到这两个变量,ans 存放最终答案,curAns 存放当前答案 // 存放当前答案的 curAns 也不一定是一个,也可能是多个。比如二进制手表问题 List<List<Integer>&g ...
我的2021年终总结
回头看看 2020 年立下的 flag,一共 3 个,有 1 个没完成。
实习,一直没去投简历。无论怎样 2022 年一定要去实习的了,必须要抓住秋招。
虽然没去实习但是也一直在准备当中。分门别类的刷了 100+ 力扣,坚持了两个月了。2022 年希望也不要落下。打算充个力扣会员,重点练一下各个大厂的算法题。还要在保持题目熟练度的同时,开始准备其他面试考点。
英语,其实当时是买了一本英文原著的,但是看了几页就发现有问题:查词太麻烦。有的词可以猜或者是跳过,但是遇到必须要查的词就要一个个的手动查,同样有的句子实在看不懂,就要一个句子手动查,有点打击积极性行。
后来就改变了学英语的策略。看 Youtube、听 TED、刷 Twitter、读文章、用英文 Google 等等,反正就是尽可能的多用英语,主要还是用起来。
2021 年的后半年,英语确实有一些提升。阅读更顺畅了,听力也不是光听见吧啦吧啦了,起码有的可以听懂原文大意。所以我觉得英语方面,其实可以算是完成的了。
如果说再往前看看 2019 年的 flag,那可以说是完全脱节了。视频剪辑、日语、公号写文章,可以说是都没了,对象也没了,只 ...
自底向上的归并排序(可用于链表排序)
从 1 个元素开始归并,逐渐向上归并到全部元素。
链表排序,就可以使用这种「自底向上的归并排序」思想。但是又因为链表不能通过下标来划分子序列,所以操作上和数组还是有些区别的,但是思路是一样的。详见 LeetCode 148 号问题:排序链表
public class MergeSortBU { // 和自顶向下的归并排序中的 merge 函数一样 private static void merge(Comparable[] arr, int l, int mid, int r) { Comparable[] aux = Arrays.copyOfRange(arr, l, r + 1); int i = l, j = mid + 1; for (int k = l; k <= r; k++) { if (i > mid) { arr[k] = aux[j - l]; j++; ...
插入排序
相信扑克牌大家都玩过,当随机发给你一捋扑克牌,你会先将牌理好,然后再想一下这手牌的好坏。那你会怎样将这捋扑克牌理好呢?
这时你可以借助「插入排序」的算法思想:从最后一张牌开始看,看这张牌之前的牌比它大还是小,如果前面的牌比它大(假设进行升序排序),那就继续往前看一张,直到看到第一张比它小的牌。此时你就可以将它插在比它小的牌后边。如果发现看到这捋牌的第一张,发现每张都比它大,那说明它是最小的,直接插在第一张的位置就好了。插好这张牌的位置后,继续从后往前看下一张牌,重复上述步骤,直到最后一张牌看完为止。
public class InsertionSort { private InsertionSort() { } // 对 arr 数组使用 InsertionSort 排序 public static void sort(Comparable[] arr) { int n = arr.length; for (int i = 0; i < n; i++) { ...
归并排序(优化)
归并排序的算法思想:递归的将待排序大数组一分为二,直至不可再分,即分割后的小数组只有一个待排序元素为止。此时使用合并算法思想,对已经有序的数组进行合并,合并为一个大数组。不断重复合并过程,直至所有小数组合并为一个数组为止。
归并排序的时间复杂度是:O($N \log_{}N$)。假如有待排序大数组有 8 个元素,那么只需要分割 $\log_{2}8=3$ 次,就可以达到不可再分的状态。然后每一步都需要 O(N) 的复杂度来合并。因此总的时间复杂度是 O($N \log_{}N$)。
public class MergeSort { // 将 arr[l...mid] 和 arr[mid+1...r] 两部分进行归并,注意前后都是闭区间 private static void merge(Comparable[] arr, int l, int mid, int r) { Comparable[] aux = Arrays.copyOfRange(arr, l, r + 1); // 初始化,i 指向左半部分的起始索引位置 l; ...
2021年我的桌面布局
我也是读了研才享受到宿舍这种「上床下桌」的待遇的。
专科的时候,住的是 7 人间,只有一个下铺是书桌。但是空间太小只能满足 3 连坐,所以一般都是用抢的。我在上铺,为了方便就买了一个直接放床上的多层书桌。不过没用多久,导员查宿舍就给我收走了。后来只好买的那种可折叠的小桌板。而且我的电脑是游戏本,特别沉。每天都要在衣橱里拿出来,用完了,再放回去。就这样过了三年。
升本以后,更惨。直接没有书桌。就只好继续用小桌板。不过好在买了一个 MacBook Air,比较游戏本整体上省事了不少。
后来考研的时候我就想,一定要考去一个有「上床下铺」的学校。这也算是我考研的一大动力。
终于,在研究生的时候,用上了「上床下铺」。
0.全景
很简单,没有贴壁纸,也没有花里胡哨的灯光秀。
我从左上开始逆时针,逐个介绍一下。
1. 左上
这个框里没啥,就是一些专业书。最上面那个是国誉的活页本。纸质非常好,用钢笔写起来唰唰的,很得劲。不过现在也基本上不记笔记了,因此就闲置了。
2. 左中
那个汤姆猫是吃麦当劳儿童套餐送的玩具。
中间那个是手冲壶,平时会做一些手冲咖啡。有时候泡早餐也会用到它。
右边是镜子。现在被我用 ...