Leetcode

June 6, 2023

Daily

2021-08-20: Valid Sudoku

都是通过把各行、各列、各个小方块，分别各个放在一个set中，如果有重复的，那么就return false就好了，还有一种思考，是分别构建三个二维数组：char\[9\]\[9\]来存放boolean value。In this case, each 2d array stores the placement situation for row, column and cube(the 3*3 matrix)。row: char[0][0] denotes position 0 at the first row, if this is true, that means there is already a one on that position.

It’s difficult to partition the original index to the correct cube position. That is to say, we have nature index to denote which row/column the number belongs to, but we need to manipulate the indexes a little bit to understand how the row, col mapped to the correct cube. So we can calculate the cube index like this: cubeIndex = (row/3)*3 + col/3. The first row/3 that:

we need to put the nine box here: _ _ _

_ _ _

_ _ _，row/3 tells you which ‘column’(splited by “

”), however, it only gives an idea of which column to go to if the index of _ _ _

_ _ _

_ _ _ really always starts with 0, 1, 2。So we need to multiply 3 to get the starting position. And then, we add up the column number, in this case, it denotes the offset from the original start position.

Another way is to use [bigRow, bigColumn] to denote the box

This way we use two index to locate the box
To flip a box, just iterate through all the box(little) and set row, col = col, row

initialize

Object name = new Object();
initialize multiple variables
```
Boolean a, b, c;
a = b = c = false;
```

for

for (Object a: Object[]){
  //
}
   
for(int i = 0; i<3; i++){
}

boolean operator

//&& and || only evaluate left side(Logical and, logical or)
//& and | evaluate both sides(bitwise and, or)
//^ -> XOR,is only true when both operands are of the same value

char comparison

char a = 'a';
char b = 'b';
char c = '1';
char d = '2';
//just use == to compare, this is a primitive type
int caseC = (int)c;
//That would give you caseC=49 because when cast char to int, the int value equals to the ascii code value for the char.
   
//char a + char b = ascii value of a + ascii value of b, and then search for the character that has the sum of ascii value
   
//char a(with number) + int b: 会直接把a囊括的数字'1'变成1，然后和b的数字相加 

java main

public static void main(String args[]){}

java 1/3

double a, b;
// a/b produce真实的除法，带有小数点精度的除法，返还一个double
int c, d;n
// c/d 返还int，他只会返还c除以d的整数部分，不返还余数，python中的//则是floor division
// java的/和python的//是不一样的,当结果是正数的时候表现是一样的

comments in java
```
//single line
/* Multiple
Line*/
```

2021-08-21: Number of ways to arrive at destination

Dijkstra’s shortest path algorithm：

visted = []
unvisted = []
# shortest_path_from_src: {k:v}, k denotes that the shortest path from src to k, v denotes how long this path is
shortest_path_from_src = dict()
# previous_visted: {k:v}, k denotes that the shortest path from src to k, v denotest that this shortest path previously(before visting k) visted v
previous_visted = dict()
# Set up
visted.append(src)
unvisted.remove(src)
shortest_path_from_src[src] = 0
previous_visted[src] = src
for node in all_node:
  shortest_path_from_src[node] = inf
  
while unvisted.is_not_empty():
  smallest_unvisted = find out the unvisted vertex with smallest shortest_path_from_src value
  for the smallest_unvisted:
  	examin the neighbors(unvisted) of the smallest_unvisted
  	add up the distance shortest_path_from_src[smallest_unvisted_neighbours]
  	which is shortest_path_from_src[smallest_unvisted_neighbours] = shortest_path_from_src[smallest_unvisted] + dist(smallest_un, neighbours)
  	see if any update to make(if shortest_path_from_src[smallest_unvisted_neighbours] is less than its previous value)
  	add the current smallest_unvisted to the visted_vertex

minheap

class Solution:
    def countPaths(self, n: int, roads: List[List[int]]) -> int:
        graph = defaultdict(list)
        for u, v, time in roads:
            graph[u].append([v, time])
            graph[v].append([u, time])
  
        def dijkstra(src):
            dist = [math.inf] * n
            ways = [0] * n
            minHeap = [(0, src)]  # dist, src
            dist[src] = 0
            ways[src] = 1
            while minHeap:
                d, u = heappop(minHeap)
                if dist[u] < d: continue  # Skip if `d` is not updated to latest version!
                for v, time in graph[u]:
                    if dist[v] > dist[u] + time:
                        dist[v] = dist[u] + time
                        ways[v] = ways[u]
                        heappush(minHeap, (dist[v], v))
                    elif dist[v] == dist[u] + time:
                        ways[v] = (ways[v] + ways[u]) % 1_000_000_007
            return ways[n - 1]
  
        return dijkstra(0)

[A]--1-[C]
 |  \     \	
 1   4	   -2--[E]
 |    \         1
[B]-1--[D]------|
  
set_visted = {A, B, D, C}
  
set_not_visted = {E}	
  
dist: A:0, B:1, C:1, D:2, E:3
  
dp: A:1, B:1, C:1, D:1, E:2
  
A:
  
for each of {B, C, D} as x:
	curr_shortest = dist[B]
	if dist[A] + long(A, x) < curr_shortest:
		dist[x] = dist[A] + long(A, x)
		dp[x] = dp[A]
	else:
		pass
  
B:
  
for each of {D}:
	curr_shortest = dist[D]
	pass_by_B = dist[B] + long(B, D) = 2
	# better
	dist[D] = 2
	dp[D] = dp[B]
  
C:
for each of {E}:
	curr_shortest = dist[E]
	pass_by_C = dist[C] + long(C, E) = 3
	# better
	dist[E] = 3
	dp[E] = dp[C]
  
D:
for each of {E}:
	curr_shortest = dist[D]
	pass_by_D = dist[D] + long(D, E) = 3
	# same good
	dist[E] = 3
	dp[E] = dp[D] + dp[E] = 2
E:
	all visted	
  
一个简单的迪杰斯特拉的一个walkthrough，在这里，最关键的是要知道我们遍历结束的条件不是访问到最终的node就完了，而是要把set_not_visted的node全部vist完才算是搞定
而迪杰斯特拉搞定了，那我们如何知道从起点到终点总共有多少条最短的路径呢？访问到一个node的时候，会examine他的neighbor，如果说起点经过我到neighbor的用时比起点不知道怎么的到
neighbor的用时要短，那么显然，经过我是最短的，而到neighbor的最短路径的数量，和到我的最短路径的数量一样。那么如果是说起点经过我到neighbor的用时比起点不知道怎么的到
neighbor的用时是一样的话，那么说明总共有（到我的最短路径+不知道怎地去到neighbor的最短路径）那么多的最短路径到neighbor

why have to if dist[u] < d: continue
还用到了dynamic programming
- dp用在了在记录到某点的最短路径的数量上，他的逻辑存在于迪杰斯特拉算法的判断“从某点来是否比原来的更短”的这个，以下这个逻辑里
```
if dist[v] > dist[u] + time:
  dist[v] = dist[u] + time
  ways[v] = ways[u]
  heappush(minHeap, (dist[v], v))
elif dist[v] == dist[u] + time:
	ways[v] = (ways[v] + ways[u]) % 1_000_000_007
```
  他的逻辑是如果经过u来的v的时间比经过别的地方来到v的时间更短，那么到v点的最短路径的数量必然也等于到u点的最短路径数量。同样，如果经过u来v的时间和经过别的点来v的时间一样短，那么到v点的最短路径数量应该等于原最短路径数量加上经过u到v的最短路径数量
java stack，stack is empty
- isEmpty return true if stack is empty(每个collection都有)
- empty return true iff the stack is empty(只在stack实现)
- 本质上没有区别
initialize collection, specifying item’s type：Stack a = new Stack<>();</code>
Initialize double with number: double a = 0d;
priority queue:
- PriorityQueue pq = new PriorityQueue<>(); </code>
- head存的是最小的东西，而“大小”的概念可以在initialize的时候pass一个comparator到这个priority queue的对象里
- add/offer都是增加，当没有capacity的时候
  - add会抛出异常
  - offer会返还false
- poll就像pop，把头变回来
Array .fill：Arrays.fill(array, val)
为什么要mod？
- modulo 10**9 + 7
- 因为有些数字相乘的操作之后，会溢出存储的格式，那么使用modulo可以保证这个数字一直在存储范围内
坑点：不能用int去存距离

2021-08-23: LRU Cache

LRU
- Didn’t understand lru cache quite well. lru cache is short for “least recently used cache”. Basically, I thought every “accesse” and “change of value” of certain key-value pair weights differently. However, for lru, each “access” and “change of value” can be regarded as a “visit” to that specific kv pair hence the kv pair should be immediately moved to the tail of the priority queue.
Hashtable
- Hashtable\<Object, Object\> hashtable = new Hashtable\<\>();
- containsKey; get; put; isEmpty; size
LinkedList
- LinkedList\<Object\> linkedList = new LinkedList<>();
- 增加：
  - add: 没有除元素外参数的add，直接加在linkedlist的最后面
  - offer：没有除元素外参数的offer，直接加在linkedlist的最后面
  - push：没有除元素外参数的push，直接把元素加在linkedlist的最前面
- 减少：
  - remove：直接得到并去除linkedlist的最前面的，没有的话会throw exception
  - pop；直接得到并除去linkedlist最前面，没有的话会throw exception
  - poll：直接得到去除最前面的元素，没有的话会返还null

priority queue with comparator

comprator：

class NodeComparator implements Comparator<Node>{
  //只用实现compare
  public int compare(Node n1, Node n2){
    //return -1 if n2 is larger
    //return 1 if n1 is larger
    //return 0 if equals
  }
}

.equals

@Override
public boolean equals(Object object){
  if (object instanceOf Node){
    Node nodeObj = (Node)object;
  }
  return false;
}

linkedHashMap

design specifically for lru cache…
maintain the insertion order or the access order of kv pair, use access order for lru cache
only need to override one method: removeEldestEntry，this method tells the object when to remove the eldest entry, in our case, we need to remove the eldest entry when our cache is full: this.size() > capacity
use getOrDefault to specify the return value when mis hit, else it will return null using get

import java.util.LinkedHashMap;
import java.util.Map;
  
/**
 * Created by fhqplzj on 16-7-11 at 下午5:41.
 */
public class LRUCache extends LinkedHashMap<Integer, Integer> {
    private int capacity;
  
    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }
  
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;
    }
  
    public int get(int key) {
        return getOrDefault(key, -1);
    }
  
    public void set(int key, int value) {
        put(key, value);
    }
}

2021-08-25 1936: Add Minimum Number of Rungs

贪心
向上取整
向下取整
- 就是2.3-> 2，3.3->3
- The reason we should use floor division to approach this question is because we want to know how many stairs we need to insert in between. If the division returns 2.3，that means we need to take 2.3 steps to get there, however, in the last 0.7 steps, we can just step to the new stair immediately, we don’t need to insert new stairs. For example, the current step size is 2, and we need to go to stair at height 10, we are now at stair at height 5. In this case, (10 - 5)/2 gives us 2.5, but we only need 2 stairs to get to 10. So we take a floor division on (target - current)/dist. The reason for (target - current - 1)//dist is because we want to prevent situation when (target - current) is divisible by dist, in case, floor division will return something not optimal(target: 13, current: 5, dist: 2, we get 4 if we dont minus one), so we minus one.
concat 2 arrays

2021-09-30: Add two numbers

思考过程：一开始想尝试的方法是，先把两个由linked list代表的数字转换成普通的int存成primitive type，然后用primitive type相加，再把结果直接转换成linked list代表的数字
- 问题1:integer overflow，这里能够允许最多100个nodes，并且每个node最多可以代表数字9，所以最多能存$\approx 9*10^{100}$ ,但是java的int最多也只能存4 bytes，也就是$2^{32}$，所以把linked list链接的数字强行cast到int是有很巨大的风险的
- 问题2:在已知integer的情况下，很难只通过这个integer就把这个数字的十位数，百位数给分离开来 -> 可以用什么string split，但现在发现用到这种的基本都是裂开的

答案：把linked list每一步相加的过程都当作在计算整数加法，列竖式的感觉。自己先在纸上演示一遍，然后发现carry是怎样确定的

public class Solution{
  public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummyHead = new ListNode(0);
    //必须要整清楚ptr和本来的头，如果不小心没有记录本来的头的话，linked list就丢了
    ListNode ptr1 = l1, ptr2 = l2, curr = dummyHead;
    int sum = 0, carry = 0, l1Val = 0, l2Val = 0;
    while (ptr1 != null || ptr2 != null){
      l1Val = (ptr1 != null)?ptr1.val:0;
      l2Val = (ptr2 != null)?ptr2.val:0;
      if(ptr1 != null){ptr1 = ptr1.next;}
      if(ptr2 != null){ptr2 = ptr2.next;}
      sum = l1Val + l2Val + carry;
      carry = sum/10;
      LinkedNode currNext = new ListNode(sum%10);
      curr.next = currNext;
      curr = curr.next;
    }
    if (carry > 0){curr.next = new ListNode(carry);}
    return dummyHead.next;
  }
}

比较要注意的点是要分清真正的ptr和head在哪

Sorting

2021-10-14: 49. Group Anagrams

description:

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

一开始的思路：维护一个set -> list的数据结构，其中，set代表的是字母的出现，而他对应的list则是由这个字母的出现组成的单词在strs中的index。比如set(e, a, t):[0, 1, 2]就代表着，由e，a，t组成的单词(eat, eta, tea, tae)。但这东西在一开始就没想清楚，因为set会把重复的elem给prune掉，这样子的话，eat和eaat也会被判定为是符合要求的anagram，但其实是错误的。

修改了的思路：只要是anagrams，那么他们的sort好的string一定是一样的，所以：利用string -> list，string就是sort好的string，其他的东西都和原来的想法保持一致

用Arrays这个package里的sort->Arrays.sort()可以在O(nlogn)中sort array的值
str.toCharArray() -> string -> char array

2021-10-14: 56. Merge Intervals

description:

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

一开始的思路：目前的2d array中存着的是interval，先根据各个interval的起点从小到大sort这个interval array，然后扫过一遍interval，有两个ptr，一个ptr指向目前达不到的interval（和之前overlap的东西完全断开），一个ptr指向“可能可以达到的interval”。在每一步，我们看现在的和之前overlap的interval完全断开的interval能不能和ptr指向的interval overlap，如果可以，就合并，然后把这合并了之后的作为第一个ptr指向的东西，然后持续increment另一个ptr。对于[a, b], [c, d]，判断能否合并的规则基于b和c的关系，如果b大于等于c，那么是可以合并的，合并之后的interval[a, x]，x要定位的是b和d中更大的那个: 代码

更好的思路：

2021-10-15: 1818. Minimum Absolute Sum Difference

You are given two positive integer arrays nums1 and nums2, both of length n.

The absolute sum difference of arrays nums1 and nums2 is defined as the sum of |nums1[i] - nums2[i]| for each 0 <= i < n (0-indexed).

You can replace at most one element of nums1 with any other element in nums1 to minimize the absolute sum difference.

Return the minimum absolute sum difference after replacing at most one element in the array nums1. Since the answer may be large, return it modulo 109 + 7.

|x| is defined as:

x if x >= 0, or
-x if x < 0.

一开始的思路：暴力。把nums1每个位置的都替换成nums1别的值，然后把abs sum diff都分别计算，然后最后来个排序。对于长度为n的总共需要$n\times(n-1)$.代码

2021-10-15: 2007. Find Original Array From Doubled Array

An integer array original is transformed into a doubled array changed by appending twice the value of every element in original, and then randomly shuffling the resulting array.

Given an array changed, return original if changed is a doubled array. If changed is not a doubled array, return an empty array. The elements in original may be returned in any order.

一开始的思路：无

2021-10-16: 1235. Maximum Profit in Job Scheduling

We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i].

You’re given the startTime, endTime and profit arrays, return the maximum profit you can take such that there are no two jobs in the subset with overlapping time range.

If you choose a job that ends at time X you will be able to start another job that starts at time X.

一开始的思路：无

改进的思路：对于每个工作来说，都只有两种可能：1. 这个工作在整个maximum的path里 2. 这个工作不在整个maximum的path里。那么也就是说，现在可以利用这两个想法去完成算法：从abstract view来看，我们先按照工作开始时间给这一堆工作排序，紧接着，我们从最早开始时间开始遍历这些工作：当遍历到工作1，我们比较工作1的两个可能：当工作1属于maximum path和当他不在的时候，也就是像递归一样：compare(currentValue + findMax(nextIndex), findMax(nextPosition))，nextPosition找的直接是比目前examine的job更晚开始的job，但是nextIndex指的是，如果选了这个工作，我们接下来该这么选，这个用的是binary search去定位

2021-10-16: 253. Meeting Rooms II

Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.

一开始的思路：无

改进的思路：模拟一下寻找空的房间的过程：对于一个meeting，尽可能的找到结束时间最早的房间。可以直接维护一个priority queue，其中每个node都是一个房间，然后queue的值就是这个房间的会议的结束时间，所以queue的头表示的就是目前最快能够结束会议的房间，然后遍历工作，如果queue的头（目前最快能够结束会议的房间）的时间要小于工作的时间，那么我们就更新queue头变成目前工作的工作时间，如果大于，那么就在queue里多加一个房间代码

2021-10-17: 75. Sort Colors

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library’s sort function.

一开始的思路：很简单，就是个简单的sort，要注意的是我们要修改的是array本身的东西，pass by reference，但是好像是incorrect？？？代码

更好的思路：

2021-10-17: 147. Insertion Sort List

Given the head of a singly linked list, sort the list using insertion sort, and return the sorted list’s head.

The steps of the insertion sort algorithm:

Insertion sort iterates, consuming one input element each repetition and growing a sorted output list.
At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list and inserts it there.
It repeats until no input elements remain.

The following is a graphical example of the insertion sort algorithm. The partially sorted list (black) initially contains only the first element in the list. One element (red) is removed from the input data and inserted in-place into the sorted list with each iteration.

一开始的思路：

改进的思路：代码

2021-10-18: 215. Kth Largest Element in an Array

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

一开始的思路：很简单，写个排序就好了代码

更好的思路：

2021-10-18: 973. K Closest Points to Origin

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).

The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x1 - x2)2 + (y1 - y2)2).

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).

一开始的思路：先遍历一遍，把所有坐标的距离都找出来，写个归并排序排序，很简单代码

2021-10-19: 1. Two Sum

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

0 <= a, b, c, d < n
a, b, c, and d are distinct.
nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

一开始的思路：先把原来的nums给sort好，一定要把原来的index给记录下来。然后利用两个pointer，分别指向sort好的array的头尾两侧（假设此时arr是按照小到大的顺序给sort好的）代码

更好（不一样）的思路

2021-10-19: 15. 3sum

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

一开始的思路：一样和2sum一样使用双指针，并且尝试把问题规约到2sum的问题。首先要把nums给sort好，然后逐个遍历nums的元素，当遍历到元素nums[i]，我们可以把剩下的arr丢进2sum的算法里面去，希望从剩下的arr寻找target=-nums[i]的结果。但是实际上的操作要比这里讲的要复杂很多：

为了提高运行的效率，在sort好了arr之后，不考虑所有nums[i] > 0的情况，因为如果num[i] > 0，算法会进可能的从nums[i+1:]中找到加起来等于负数的解，但明显不可能
为了确保答案的唯一性，我们在遍历nums的时候要确保不要重复运行相同target的2sum，比如如果判断nums[i] == nums[i-1]的话，直接跳过这个遍历
虽然要保证一个结果：[1,2,3]的唯一性，但是对于相同的nums[i]，并没有假设只有唯一的2sum结果（但是在2sum这一题则这样明确了），所以在找到了一个2sum结果的时候，需要缩小范围了之后继续搜索
虽然但是，紧接上条，如果出现了对称的list：[0,0,2,2]，2，这样的话即使左右都缩小了一个范围，我们还是会得到duplicate的结果，所以还要判断任意一边：while(left < right && nums[left] == nums[left - 1]){left++;}，这里用right来判断也可以
最后的感想：简单快排真他妈垃圾，连测试都过不了，换成merge之后快了很多代码

更好（不一样）的思路：

2021-10-19: 18. 4sum

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

0 <= a, b, c, d < n
a, b, c, and d are distinct.
nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

一开始的思路：$n^3$?直接4sum调3sum，3sum调2sum。但是这里在4sum和3sum的调用会有些许的不一样：

在3sum中：我们“为了提高运行的效率，在sort好了arr之后，不考虑所有nums[i] > 0的情况，因为如果num[i] > 0，算法会进可能的从nums[i+1:]中找到加起来等于负数的解，但明显不可能”，更generalize一点，就是“为了提高运行的效率，在sort好了arr之后，不考虑所有nums[i] > target的情况，因为如果num[i] > 0，算法会进可能的从nums[i+1:]中找到加起来等于负数的解，但明显不可能”，这样的筛检手段只针对target>=0适用，因为只要当nums[i] > target，那么target - nums[i]就必定是个负数，而因为nums[i] > target >= 0，且这个数组已经排列好的了，那么我们不可能可以从剩下的arr找到一组加起来小于0的解。但是当target<0的时候，在这里并不适用，因为现在我们要找到的是target，当target < 0 的时候，虽然nums[i] > target，但这没有明确nums[i]和0的关系，他还可以是负的，我们根本无法排除掉这个值之后的arr，例如target是-11，nums[i]是-5，虽然nums[i]确实大于target，但target减去nums[i]得到的是-6，-5后面跟一个-4和-2解就存在了

别的基本一样：Code

更好的思路：

2021-10-19: 767. Reorganize String

Given a string s, rearrange the characters of s so that any two adjacent characters are not the same.

Return any possible rearrangement of s or return "" if not possible.

一开始的思路：无

更好的思路：利用了hashmap和priority queue。首先，利用hashmap把各个char的出现的次数记录下来：’a’:20说明a总共出现了20次，然后，把每个键值对按照出现次数都存在pq里。然后开始构建我们需要的string：我们每次从pq里取出一个char（目前在pq里排名最高的那个），然后先比对他和目前string的最后一位是不是一样的char，如果是的话，说明违背了题目的规则，我们接下来从pq中再取出一个东西出来（此时的排位第二的char），把它放进去，如果我们发现此时已经没有东西取了，那么直接返还一个空的str。伪代码如下：

构建priority queue，其中存的是char:occurrences这样的键值对，pq中用occur从大到小来排列
构建res（我们要返还的string）
while (res.length() < 原来的str的长度)
- 如果这是第一个：
  - 从pq中取出目前最大的char1
  - 如果char1 == res[-1]
    - 如果pq此时已经没有额外的键值对，那么说明已经没有char可以解决这个问题了
      - return空str
    - 如果有：
      - 从pq中取出目前最大的char2
      - 把char2加入res中，decrease char2的value
      - 把char1和char2加回pq
  - 如果char1 != res[-1]
    - 把char1加入res中，decrease char1的value
    - 把char1加回pq（如果还有的话）
返还res

code

2021-10-22: 1152. Analyze User Website Visit Pattern

You are given two string arrays username and website and an integer array timestamp. All the given arrays are of the same length and the tuple [username[i], website[i], timestamp[i]] indicates that the user username[i] visited the website website[i] at time timestamp[i].

A pattern is a list of three websites (not necessarily distinct).

For example, ["home", "away", "love"], ["leetcode", "love", "leetcode"], and ["luffy", "luffy", "luffy"] are all patterns.

The score of a pattern is the number of users that visited all the websites in the pattern in the same order they appeared in the pattern.

For example, if the pattern is ["home", "away", "love"], the score is the number of users x such that x visited "home" then visited "away" and visited "love" after that.
Similarly, if the pattern is ["leetcode", "love", "leetcode"], the score is the number of users x such that x visited "leetcode" then visited "love" and visited "leetcode" one more time after that.
Also, if the pattern is ["luffy", "luffy", "luffy"], the score is the number of users x such that x visited "luffy" three different times at different timestamps.

Return the pattern with the largest score. If there is more than one pattern with the same largest score, return the lexicographically smallest such pattern.

一开始的想法：暴力，目的是把所有的pattern出现的次数都统计出来。这里很容易看出我们对于pattern是按照user来统计的，所以先用user找出所有的pattern：根据user，找出user访问过的所有网站，按照timestamp来罗列（这题真的非常恶心，他的timestamp都没有sort好，并且他给出来的例子让你以为他都是sort好的），然后把每个user的所有pattern都找出来，最后再统计次数。虽然想法不算很绕，但是细节比较多，如果要用pq写的话需要自己整comparator：code

2021-10-25 621. Task Scheduler

Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any order. Each task is done in one unit of time. For each unit of time, the CPU could complete either one task or just be idle.

However, there is a non-negative integer n that represents the cooldown period between two same tasks (the same letter in the array), that is that there must be at least n units of time between any two same tasks.

Return the least number of units of times that the CPU will take to finish all the given tasks.

一开始的想法：暴力贪心，先用priority queue按照需要schedule的次数存放所有的task，每一次都先找到最需要处理的task（pq第一个），尝试在时间里加入这个，遍历之前n个元素，如果n个元素内没有相同的task，就可以加入，一直遍历到没有task为止，大致的算法是，超出时间限制: code

改进的想法：用二元数组遍历记录任务i的信息：（下一次可供调度的时间，还剩下需要调动的次数）。然后遍历二元数组，找到目前时间t下：可供调动，且需要调动次数最多的任务。这其中最巧妙的地方是，我们先找到最早的可供调度的任务之后，直接把时间t加到那个最早的时间（如果t<最早的可供调度的任务的话）。这样做的目的是可以直接把需要idle时的遍历给抹掉！！非常关键！！code

2021-10-26: 692. Top K Frequent Words

Given an array of strings words and an integer k, return the k most frequent strings.

Return the answer sorted by the frequency from highest to lowest. Sort the words with the same frequency by their lexicographical order.

一开始的想法：map：string：occurrences -> pq，在pq中实现comparator（包含lexi order），逐个抽取 code

更好的想法：

2021-10-27: 347. Top K Frequent Elements

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

一开始的想法：map：Integer：occurrences -> pq，在pq中实现comparator（改写一下，令pq一开始存的是最大的），逐个抽取code

更好的想法：

2021-10-27: 1647. Minimum Deletions to Make Character Frequencies Unique

A string s is called good if there are no two different characters in s that have the same frequency.

Given a string s, return the minimum number of characters you need to delete to make s good.

The frequency of a character in a string is the number of times it appears in the string. For example, in the string "aab", the frequency of 'a' is 2, while the frequency of 'b' is 1.

一开始的想法：先把String变成char array，然后扫过这个char array。扫的时候把每个字母的frequencies都统计下来，然后加入一个freq set中，当扫到一个字母的freq已经存在freq set中的时候，#deletion++，代表我们需要删掉这个字母的一个，这样遍历下去。需要注意的是对一些edge case的处理 code

改进的想法：

2021-11-08: 912. Sort an Array

Given an array of integers nums, sort the array in ascending order.

一开始的想法：code

改进的想法：

Dynamic Programming

2021-11-09 5. Longest Palindromic Substring

Given a string s, return the longest palindromic substring in s.

一开始的思路：回文的特点是：正着读和反着读是一模一样的，所以根据这个特性，给定一个string s，把他reverse一下变成s’，然后找s和s’的longest common substring就好了，但因为这样子的话会忽略一个case：$abcxicba$,这样子的话，reverse了之后，s’有和原string的abc match了，但这明显不是valid的回文，因为match的原因是因为原string含有abc的reversed version，所以必须要先确定位置，但这题在实现上有一点问题 code

改进的思路

九章算法

2021-11-24 Lintcode: 56. 两数之和

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are zero-based.

本来的思路：老生常谈的two sum问题还是磕磕碰碰的。还是一样的思想：双指针，然后一个指向左一个指向右，根据目前两个指针指向的index加起来的值和target值做对比从而得出该移动左指针还是右指针。现在的问题是，双指针的思路是记住了，但是忽视了双指针只作用于sort好的array上，这是第一，第二点就是在sort完之后，index改了，需要用到一个数据结构去记录这个index 代码

改进的思路：

2021-11-24 Lintcode: 104. 合并k个排序链表

Merge k sorted linked lists and return it as one sorted list.

Analyze and describe its complexity.

样例

Example 1:

Input:

lists = [2->4->null,null,-1->null]

Output:

-1->2->4->null

Explanation:

Merge 2->4->null, nulll and -1->null into an ascending list.

一开始的思路: 实现一个可以合并两个链表的方程，然后一个一个的合并list中的链表，问题就是时间复杂度会很高，但被accept了。反思是在写代码的时候，对于是新建一个全新的object还是在原有的结构上改变很模糊，要复习并且学习java的关于这方面的知识code

改进的思路

2021.11.24 Lintcode: 102 · 带环链表

描述

Given a linked list, determine if it has a cycle in it.

The length of the linked list does not exceed 10000.

样例

Example 1:

Input:

linked list = 21->10->4->5，then tail connects to node index 1(value 10).

Output:

true

Explanation:

The linked list has rings.

一开始的思路：无思路

更好的思路：两个指针，一个快指针，一个慢指针，快指针一次跳两格，慢指针一次跳一格，如果存在cycle的话，快慢指针必定相遇 code

2021-11-25 Lintcode: 94 · Binary Tree Maximum Path Sum

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node’s values in the path.

Given the root of a binary tree, return the maximum path sum of any non-empty path.

一开始的思路：使用recursion，在每一步，尝试对比：root+左，root+右和root+左+右。但这样子会有问题，因为在这样的算法下，他不能避免不是path的情况，path的定义是：A node can only appear in the sequence at most once，如下图

Snipaste_2021-11-25_12-40-06

在这一题里，-10的root node的右树的最大的path是：15 20 7，并且这个最大的path是会被记录下来的，这样子-10会理所当然认为结果就是一个存在-10 15 20 7这些node的path，但很明显这不构成path。实际上错误的点在于，我要找一个path，我只能一次探索一个方向，切不可两个方向都探索，root+左+右这样是完全不存在的。

改进的思路：应该调整思路，我们探索整张图的只走左或者只走右的路径，如果要探索root+左+右的话，我们只能假设目前recur到的位置就是开启一个新的path的root，而不能把这个当作一个探索的思路去返还给上一层。所以我们的主函数依然是只探索一个方向的path的最大，但是在探索的过程中，我们时刻记录着以各个node为root的最大，最后对比并且返还 code

2021-11-25 Lintcode: 94 · Binary Tree Maximum Path Sum

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

一开始的思路：接受事实，dp就是$n^2$的玩意儿。用dp的思想去做，从前往后扫过所有的元素，每一步，检查之前存下来的信息的array，dpRes就是信息的array，dpRes[i]->{val, max}代表了：第i个元素，有着val值，并且拥有以他为最后一个的最长升序的序列长度，那么我每扫过一个element，我都在这个dpRes[0, i]里面找：val小于目前的元素，且max最大的。但似乎不算很正常的dp？？code

改进的思路：

2021-11-25 Lintcode: 45 · Maximum Subarray Difference Code

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: An integer indicate the value of maximum difference between two substrings
     */
    public int maxDiffSubArrays(int[] nums) {
        // write your code here
        int length = nums.length;
        
        if(length < 2) {
            return -1;
        }
        
        int[] leftMax = new int[length];
        int[] leftMin = new int[length];
        int[] rightMax = new int[length];
        int[] rightMin = new int[length];
        
        
        int minSum = 0;
        int maxSum = 0;
        int sum = 0;
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < length; i++) {
            sum += nums[i];
            
            max = Math.max(sum - minSum, max);
            minSum = Math.min(sum, minSum);
            leftMax[i] = max;
            
            min = Math.min(sum - maxSum, min);
            maxSum = Math.max(sum, maxSum);
            leftMin[i] = min;
        }
        
        minSum = 0;
        maxSum = 0;
        sum = 0;
        max = Integer.MIN_VALUE;
        min = Integer.MAX_VALUE;
        
        for(int j = length - 1; j >= 0; j--) {
            sum += nums[j];
            
            max = Math.max(sum - minSum, max);
            minSum = Math.min(sum, minSum);
            rightMax[j] = max;
            
            min = Math.min(sum - maxSum, min);
            maxSum = Math.max(sum, maxSum);
            rightMin[j] = min;
        }
        
        max = Integer.MIN_VALUE;
        
        for(int k = 0; k < length - 1; k++) {
            int candidate1 = Math.abs(leftMin[k] - rightMax[k + 1]);
            int candidate2 = Math.abs(leftMax[k] - rightMin[k + 1]);
            max = Math.max(max, Math.max(candidate1 , candidate2));
        }
        
        return max;
    }
}

Thought End Pointer

Code End Pointer

回到目录

Code

2021-10-14: 56. Merge Intervals Code

import java.util.*;
class Solution {
    public int[][] merge(int[][] intervals) {
        List<List<Integer>> mergeResult = new ArrayList<List<Integer>>();
        int[][] sortedIntervals = getSortedIntervals(intervals);
        for (int i = 0; i < sortedIntervals.length; i++){
            int ptr = i + 1;
            int[] currentNode = sortedIntervals[i];
            while (ptr < sortedIntervals.length){
                //mergeable, update current node -> [a, b], [c, d] -> a<c, a<b, c<d -> b>c, a<c, a<b, c<d -> the 
                //infomation between b and d is not given and we always care about the smallest and largest valu of
                //the range
                if (currentNode[1] >= sortedIntervals[ptr][0]) {
                    //make sure the current node is being updated to most representitive range
                    currentNode[1] = currentNode[1] >= sortedIntervals[ptr][1]?currentNode[1]:sortedIntervals[ptr][1];
                    ptr++;
                }else{
                    //if the current range can't reach the next one, break
                    break;
                }
            }
            List currentNodeList = toList(currentNode);
            mergeResult.add(currentNodeList);
            //There are two ways to get out from the while:(1) next one is non-reachable, then we need to start examine
            //the next node (2) the ptr has already reached the end of the array, and we don't have more nodes to examine
            i = ptr-1;
        }
        return get2dArray(mergeResult);
    }
    
    public List<Integer> toList(int[] currentNode){
        List<Integer> resultList = new ArrayList<Integer>();
        for (int i = 0; i < currentNode.length; i++){
            resultList.add(currentNode[i]);
        }
        return resultList;
    }
    
    public int[][] get2dArray(List<List<Integer>> result){
        int[][] resultArray = new int[result.size()][result.get(0).size()];
        for (int i = 0; i < result.size(); i++){
            int[] interval = new int[result.get(i).size()];
            for (int j = 0; j < result.get(i).size(); j++){
                interval[j] = (int)result.get(i).get(j);
            }
            resultArray[i] = interval;
        }
        return resultArray;
        
    }
    
    
    public int[][] getSortedIntervals(int[][] intervals){
        //base case
        if (intervals.length <= 1){
            return intervals;
        }
        //split
        int leftLength = intervals.length/2, rightLength = intervals.length - leftLength, leftEndsOn = leftLength - 1, rightPtr = 0;
        int[][] left = new int[leftLength][2], right = new int[rightLength][2], sortedFinal = new int[intervals.length][2];
        for (int i = 0; i < intervals.length; i++){
            if (i <= leftEndsOn) {
                left[i] = intervals[i];
            }else{
                right[rightPtr] = intervals[i];
                rightPtr++;
            }
        }
        //sort each
        int[][] leftSorted = getSortedIntervals(left), rightSorted = getSortedIntervals(right);
        //merge
        int leftPtr = 0;
        rightPtr = 0;
        for (int i = 0; i < sortedFinal.length; i++){
            if (leftPtr >= leftSorted.length){
                sortedFinal[i] = rightSorted[rightPtr];
                rightPtr++;
            }else if (rightPtr >= rightSorted.length) {
                sortedFinal[i] = leftSorted[leftPtr];
                leftPtr++;
            }
            else if (leftSorted[leftPtr][0] <= rightSorted[rightPtr][0]){
                sortedFinal[i] = leftSorted[leftPtr];
                leftPtr++;
            }else if (leftSorted[leftPtr][0] > rightSorted[rightPtr][0]){
                sortedFinal[i] = rightSorted[rightPtr];
                rightPtr++;
            }else{
                //
            }
        }
        return sortedFinal;
    }
}

2021-10-14: 1818. Minimum Absolute Sum Difference Code

import java.util.*;
class Solution {
    public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
        List<Integer> resultList = new ArrayList<Integer>();
        int leftPtr = 0, rightPtr = nums1.length - 1;
        resultList.add(diff(nums1, nums2));
        for (int i = 0; i < nums1.length; i++){
            while (leftPtr < i){
                int[] newNums1 = replace(nums1, i, nums1[leftPtr]);
                resultList.add(diff(newNums1, nums2));
                leftPtr++;
            }
            while (rightPtr > i){
                int[] newNums1 = replace(nums1, i, nums1[rightPtr]);
                resultList.add(diff(newNums1, nums2));
                rightPtr--;
            }
            leftPtr = 0;
            rightPtr = nums1.length - 1;
        }
        Collections.sort(resultList);
        return resultList.get(0) % 1000000007;
    }
    
    public int diff(int[] nums1, int[] nums2){
        int result = 0;
        for (int i = 0; i < nums1.length; i++){
            int local = nums1[i]>=nums2[i]?(nums1[i] - nums2[i]):(-nums1[i] + nums2[i]);
            result = result + local;
        }
        return result;
    }
    
    public int[] replace(int[] nums, int toBeReplacedIndex, int value){
        int[] newInstance = nums.clone();
        newInstance[toBeReplacedIndex] = value;
        return newInstance;
    }
}

2021-10-15: 2007. Find Original Array From Doubled Array

class Solution {
    public int[] findOriginalArray(int[] changed) {
        if ((changed.length & 1) == 1){
            return new int[0];
        }
        // 2*(100000+1) because we want to store all possible value from
        // 0-10**5 and the double of the value
        int[] countingTable = new int[2*(100000+1)], resultArr = new int[changed.length/2];
        int ptr = 0;
        for (int changedIndex : changed){
            //basically, we now record the occurrences for each value
            countingTable[changedIndex]++;
        }
        
        for (int i = 0; i < countingTable.length; i++){
            if (countingTable[i] < 0){
                return new int[0];
            }
            if (countingTable[i] > 0){
                if (countingTable[i*2] == 0){
                    return new int[0];
                }
                countingTable[2*i] -= countingTable[i];
                while (countingTable[i] > 0){
                    resultArr[ptr] = i;
                    countingTable[i]--;
                    ptr++;
                }
            }
        }
        return resultArr;
    }
}

2021-10-16: 253. Meeting Rooms II Code

import java.util.*;
class Solution {
    public int minMeetingRooms(int[][] intervals) {
        //base case
        if (intervals.length == 1){
            return 1;
        }
        Queue<Integer> earliestEndingRoom = new PriorityQueue<>();
        int[][] intervalsCloneSorted = sortIntervals(intervals.clone());
        for (int[] meeting : intervalsCloneSorted){
            if (earliestEndingRoom.isEmpty()){
                boolean result = earliestEndingRoom.offer(meeting[1]);
            }else{
                int earliestEndingMeetingTime = earliestEndingRoom.peek();
                if (earliestEndingMeetingTime <= meeting[0]){
                    //the earliest room will be prepared, we will use that
                    int toBeReplaceTime = earliestEndingRoom.poll();
                    boolean added = earliestEndingRoom.offer(meeting[1]);
                }else{
                    //the room is not empty and we can't use that, need to allocate a new room
                    boolean added = earliestEndingRoom.offer(meeting[1]);
                }
            }
        }
        return earliestEndingRoom.size();
    }
    
    public int[][] sortIntervals(int[][] intervals){
        //base case
        if (intervals.length == 1){
            return intervals;
        }
        //split
        int rightPtr = 0;
        int[][] left = new int[intervals.length/2][2], right = new int[intervals.length - left.length][2]; 
        for (int i = 0; i < intervals.length; i++){
            if (i < left.length){
                left[i] = intervals[i];
            }else{
                right[rightPtr++] = intervals[i];
            }
        }
        //sort
        int[][] leftSorted = sortIntervals(left), rightSorted = sortIntervals(right), result = new int[intervals.length][2];
        int leftCount = 0, rightCount = 0;
        //merge
        for (int i = 0; i < result.length; i++){
            if (leftCount >= leftSorted.length){
                //when all the value from left has been used, we continue to increment right
                result[i] = rightSorted[rightCount++];
            }else if (rightCount >= rightSorted.length){
                //when all the value from right has been used, we continue to increment left
                result[i] = leftSorted[leftCount++];
            }else if (leftSorted[leftCount][0] <= rightSorted[rightCount][0]){
                result[i] = leftSorted[leftCount++];
            }else if (leftSorted[leftCount][0] > rightSorted[rightCount][0]){
                result[i] = rightSorted[rightCount++];
            }else{
                //
            }
        }
        return result;
    }
}

2021-10-17: 75. Sort Colors Code

class Solution {
    public void sortColors(int[] nums) {
        nums = mergeSort(nums);
    }
    
    public int[] mergeSort(int[] nums){
        //base
        if (nums.length <= 1){
            return nums;
        }
        //split
        int leftLength = nums.length/2, rightLength = nums.length - leftLength, rightCount = 0;
        int[] left = new int[leftLength], right = new int[rightLength], result = new int[nums.length];
        for (int i = 0; i < nums.length; i++){
            if (i < leftLength){
                left[i] = nums[i];
            }else{
                right[rightCount++] = nums[i];
            }
        }
        //sort
        int[] leftSorted = mergeSort(left), rightSorted = mergeSort(right);
        //merge
        int leftPtr = 0, rightPtr = 0;
        for (int i = 0; i < result.length; i++){
            if (leftPtr >= leftSorted.length){
                nums[i] = rightSorted[rightPtr++];
            }else if (rightPtr >= rightSorted.length){
                nums[i] = leftSorted[leftPtr++];
            }else if (leftSorted[leftPtr] <= rightSorted[rightPtr]){
                nums[i] = leftSorted[leftPtr++];
            }else if (leftSorted[leftPtr] > rightSorted[rightPtr]){
                nums[i] = rightSorted[rightPtr++];
            }else{
                //
            }
        }
        return nums;
    }
}

2021-10-17: 147. Insertion Sort List Code

2021-10-18: 215. Kth Largest Element in an Array Code

import java.util.*;
class Solution {
    public int findKthLargest(int[] nums, int k) {
        // sort the arr in desc order
        nums = mergeSort(nums);
        return nums[k-1];
    }
    
    public int[] mergeSort(int[] nums){
        //base case
        if (nums.length <= 1){
            return nums;
        }
        //split
        int leftLength = nums.length/2, rightLength = nums.length - leftLength, rightCount = 0;
        int[] left = new int[leftLength], right = new int[rightLength], result = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            if (i < leftLength){
                left[i] = nums[i];
            }else{
                right[rightCount++] = nums[i];
            }
        }
        //sort
        int[] leftSorted = mergeSort(left), rightSorted = mergeSort(right);
        int leftPtr = 0, rightPtr = 0;
        //merge
        for (int i = 0; i < result.length; i++){
            if (leftPtr >= leftSorted.length){
                result[i] = rightSorted[rightPtr++];
            }else if (rightPtr >= rightSorted.length){
                result[i] = leftSorted[leftPtr++];
            }else if (leftSorted[leftPtr] >= rightSorted[rightPtr]){
                result[i] = leftSorted[leftPtr++];
            }else if (leftSorted[leftPtr] < rightSorted[rightPtr]){
                result[i] = rightSorted[rightPtr++];
            }else{
                //
            }
        }
        return result;
    }
}

2021-10-18: 973. K Closest Points to Origin Code

import java.lang.*;
class Solution {
    public int[][] kClosest(int[][] points, int k) {
        double[][] pointsWithDist = getDistForPoints(points);
        double[][] pointsWithDistSorted = mergeSortPoints(pointsWithDist);
        int[][] result = copyToArray(pointsWithDistSorted, k);
        return result;
    }
    
    public double getDist(int x, int y){
        double term1 = Math.pow(x, 2), term2 = Math.pow(y, 2);
        return Math.pow((term1+term2), 1.0/2.0);
        
    }
    
    public double[][] getDistForPoints(int[][] points){
        //return [xi, yi, disti] for each points
        double[][] pointsWithDist = new double[points.length][3];
        for (int i = 0; i < points.length; i++){
            pointsWithDist[i][0] = points[i][0];
            pointsWithDist[i][1] = points[i][1];
            pointsWithDist[i][2] = getDist(points[i][0], points[i][1]);
        }
        return pointsWithDist;
    }
    
    public double[][] mergeSortPoints(double[][] points){
        //base
        if (points.length <= 1){
            return points;
        }
        //split
        int leftLength = points.length/2, rightLength = points.length - leftLength, rightCount = 0;
        double[][] left = new double[leftLength][3], right = new double[rightLength][3], result = new double[points.length][3];
        for (int i = 0; i < points.length; i++){
            if (i < leftLength){
                left[i] = points[i];
            }else{
                right[rightCount++] = points[i];
            }
        }
        //sort
        double[][] leftSorted = mergeSortPoints(left), rightSorted = mergeSortPoints(right);
        //merge
        int leftPtr = 0, rightPtr = 0;
        for (int i = 0; i < result.length; i++){
            if (leftPtr >= leftSorted.length){
                result[i] = rightSorted[rightPtr++];
            }else if (rightPtr >= rightSorted.length){
                result[i] = leftSorted[leftPtr++];
            }else if (rightSorted[rightPtr][2] <= leftSorted[leftPtr][2]){
                result[i] = rightSorted[rightPtr++];
            }else if (rightSorted[rightPtr][2] > leftSorted[leftPtr][2]){
                result[i] = leftSorted[leftPtr++];
            }else{
                //
            }
        }
        
        return result;
    }
    
    public int[][] copyToArray(double[][] points, int k){
        int[][] result = new int[k][2];
        for (int i = 0; i < k; i++){
            result[i][0] = (int)points[i][0];
            result[i][1] = (int)points[i][1];
        }
        return result;
    }
}

2021-10-19: 1. Two Sum Code

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[][] valPos = getValPos(nums);
        int[][] sortedNums = mergeSort(valPos);
        int left = 0, right = sortedNums.length - 1;
        int[] result = new int[2];
        while (left < right){
            int sum = sortedNums[left][0] + sortedNums[right][0];
            if (sum == target){
                result[0] = sortedNums[left][1];
                result[1] = sortedNums[right][1];
                break;
            }else if (sum > target){
                right--;
            }else{
                left++;
            }
        }
        return result;
    }
    
    public int[][] getValPos(int[] nums){
        int[][] result = new int[nums.length][2];
        for (int i = 0; i < nums.length; i++){
            result[i][0] = nums[i];
            result[i][1] = i;
        }
        return result;
    }
    
    public int[][] mergeSort(int[][] nums){
        //base
        if (nums.length <= 1){
            return nums;
        }
        //split 
        int leftLength = nums.length/2, rightLength = nums.length - leftLength, rightCount = 0;
        int[][] left = new int[leftLength][2], right = new int[rightLength][2] , result = new int[nums.length][2];
        for (int i = 0; i < nums.length; i++){
            if (i < leftLength){
                left[i] = nums[i];
            }else{
                right[rightCount++] = nums[i];
            }
        }
        //sort
        int[][] leftSorted = mergeSort(left), rightSorted = mergeSort(right);
        //merge
        int leftPtr = 0, rightPtr = 0;
        for (int i = 0; i < result.length; i++){
            if (leftPtr >= leftSorted.length){
                result[i] = rightSorted[rightPtr++];
            }else if (rightPtr >= rightSorted.length){
                result[i] = leftSorted[leftPtr++];
            }else if (leftSorted[leftPtr][0] <= rightSorted[rightPtr][0]){
                result[i] = leftSorted[leftPtr++];
            }else if (leftSorted[leftPtr][0] > rightSorted[rightPtr][0]){
                result[i] = rightSorted[rightPtr++];
            }else{
                //
            }
        }
        return result;
    }
}

2021-10-19: 15. 3sum Code

import java.util.*;
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        //quickSort(nums, 0, nums.length-1);
        //Arrays.sort(nums);
        nums = mergeSort(nums);
        int rightPtr = nums.length - 1;
        for (int i = 0; i < nums.length && nums[i] <= 0; i++){
            if (i == 0 || nums[i] != nums[i-1]){
                getTwoSumResult(0-nums[i], i+1, rightPtr, nums, result);
                //if there are no according two sum result
            }
        }
        return result;
    }
    
    public void getTwoSumResult(int target, int startIndex, int endIndex, int[] nums, List<List<Integer>> result){
        int leftPtr = startIndex, rightPtr = endIndex;
        //int[] result = new int[2];
        boolean isExistResult = false;
        while (leftPtr < rightPtr){
            int sum = nums[leftPtr] + nums[rightPtr];
            if (sum == target){
                List<Integer> localList = new ArrayList<>();
                localList.add(nums[leftPtr++]);
                localList.add(nums[rightPtr--]);
                localList.add(-target);
                result.add(localList);
                isExistResult = true;
                while (leftPtr < rightPtr && nums[leftPtr] == nums[leftPtr - 1]){
                    ++leftPtr;
                }
            }else if (sum > target){
                --rightPtr;
            }else{
                ++leftPtr;
            }
        }
    }
    
    public int[] mergeSort(int[] nums){
        //base
        if (nums.length <= 1){
            return nums;
        }
        //split
        int[] left = new int[nums.length/2], right = new int[nums.length - left.length];
        int rightCount = 0;
        for (int i = 0; i < nums.length; i++){
            if (i < left.length){
                left[i] = nums[i];
            }else{
                right[rightCount++] = nums[i];
            }
        }
        //sort
        int[] leftSorted = mergeSort(left), rightSorted = mergeSort(right), res = new int[nums.length];
        //merge
        int leftPtr = 0, rightPtr = 0;
        for (int i = 0; i < res.length; i++){
            if (leftPtr >= leftSorted.length){
                res[i] = rightSorted[rightPtr++];
            }else if (rightPtr >= rightSorted.length){
                res[i] = leftSorted[leftPtr++];
            }else if (rightSorted[rightPtr] <= leftSorted[leftPtr]){
                res[i] = rightSorted[rightPtr++];
            }else if (rightSorted[rightPtr] > leftSorted[leftPtr]){
                res[i] = leftSorted[leftPtr++];
            }
        }
        return res;
    }
    
    public void quickSort(int[] nums, int left, int right){
        if (left < right){
            int i = left, j = left;
            int pivot = nums[right];
            
            for (j = i; j < right; j++){
                if (nums[j] < pivot){
                    int tmp = nums[j];
                    nums[j] = nums[i];
                    nums[i] = tmp;
                    i++;
                }
            }
            int tmp = nums[j];
            nums[j] = nums[i];
            nums[i] = tmp;
            
            quickSort(nums, 0, i-1);
            quickSort(nums, i+1, right);
        }
    }
}

2021-10-19: 18. 4sum Code

import java.util.*;
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        //sort
        //nums = mergeSort(nums);
        Arrays.sort(nums);
        //traverse
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++){
            if (i != 0 && nums[i] == nums[i-1]){
                continue;
            }
            threeSum(target-nums[i], nums[i], i+1, nums, res);
        }
        return res;
    }
    
    public void threeSum(int target, int fourAdd, int startIndex, int[] nums, List<List<Integer>> res){
        //find all unique three sum tuple from nums
        for (int i = startIndex; i < nums.length; i++){
            if (i != startIndex && nums[i] == nums[i-1]){
                continue;
            }
            twoSum(target-nums[i], fourAdd, nums[i], i+1, nums, res);
        }
    }
    
    public void twoSum(int target, int fourAdd, int threeAdd, int startIndex, int[] nums, List<List<Integer>> res){
        int left = startIndex, right = nums.length - 1;
        while (left < right){
            int sum = nums[left] + nums[right];
            if (sum == target){
                List<Integer> localResult = new ArrayList<>();
                localResult.add(fourAdd);
                localResult.add(threeAdd);
                localResult.add(nums[left]);
                localResult.add(nums[right]);
                res.add(localResult);
                left++;
                right--;
                while (left < right && nums[right] == nums[right+1]){
                    right--;
                }
            }else if (sum < target){
                left++;
            }else{
                right--;
            }
        }
    }
}

2021-10-19: 767. Reorganize String Code

import java.lang.*;
import java.util.*;
class Solution {
    public String reorganizeString(String s) {
        Map<Character, Integer> occurMap = new HashMap<>();
        int targetLength = s.length();
        for (int i = 0; i < targetLength; i++){
            occurMap.put(s.charAt(i), occurMap.getOrDefault(s.charAt(i), 0)+1);
        }
        Queue<Map.Entry<Character, Integer>> pq = new PriorityQueue<>((e1, e2) -> e2.getValue() - e1.getValue());
        for (Map.Entry<Character, Integer> occurPair : occurMap.entrySet()){
            pq.offer(occurPair);
        }
        StringBuilder sBuild = new StringBuilder();
        
        while (sBuild.length() < targetLength){
            if (sBuild.length() == 0){
                //the first element
                Map.Entry<Character, Integer> currentLargest = pq.poll();
                sBuild.append(currentLargest.getKey());
                currentLargest.setValue(currentLargest.getValue()-1);
                if (currentLargest.getValue() > 0){
                    pq.offer(currentLargest);
                }
            }else{
                Map.Entry<Character, Integer> currentLargest = pq.poll();
                if (sBuild.charAt(sBuild.length() - 1) == currentLargest.getKey()){
                    if (pq.isEmpty()){
                        return "";
                    }else{
                        Map.Entry<Character, Integer> secondLargest = pq.poll();
                        sBuild.append(secondLargest.getKey());
                        secondLargest.setValue(secondLargest.getValue()-1);
                        if (secondLargest.getValue() > 0){
                            pq.offer(secondLargest);
                        }
                        pq.offer(currentLargest);
                    }
                }else{
                    sBuild.append(currentLargest.getKey());
                    currentLargest.setValue(currentLargest.getValue()-1);
                    if (currentLargest.getValue() > 0){
                        pq.offer(currentLargest);
                }   
                }
            }
        }
        
        return sBuild.toString();
    }
}

2021-10-22: 1152. Analyze User Website Visit Pattern Code

import java.util.*;
class Solution {
    public List<String> mostVisitedPattern(String[] username, int[] timestamp, String[] website) {
        List<Visit> visitList = new ArrayList<>();
        for (int i = 0; i < timestamp.length; i++){
            visitList.add(new Visit(username[i], timestamp[i], website[i]));
        }
        Collections.sort(visitList, (Visit v1, Visit v2) -> v1.time - v2.time);
        
        Map<String, List<String>> visitMap = new HashMap<>();
        for (int i = 0; i < visitList.size(); i++){
            List<String> valueArr = visitMap.getOrDefault(visitList.get(i).user, new ArrayList<String>());
            valueArr.add(visitList.get(i).web);
            visitMap.put(visitList.get(i).user, valueArr);
        }
        
        //construct the user -> patterns map
        Map<String, Set<String>> patternMap = new HashMap<>();
        for (String user : visitMap.keySet()){
            List<String> history = visitMap.get(user);
            Set<String> patterns = new HashSet<>();
            for (int i = 0; i < history.size() - 2; i++){
                for (int j = i+1; j < history.size() - 1; j++){
                    for (int k = j + 1; k < history.size(); k++){
                        List<String> splitPattern = Arrays.asList(new String[]{
                            history.get(i),
                            history.get(j),
                            history.get(k),
                        });
                        patterns.add(getPatternString(splitPattern));
                    }
                }
            }
            patternMap.put(user, patterns);
        }
        
        //constructing the pattern -> occurrences map and the priority queue
        Map<String, Integer> patternCompare = new HashMap<>();
        Queue<Map.Entry<String, Integer>> pq = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>(){
            @Override
            public int compare(Map.Entry<String, Integer> entry1, Map.Entry<String, Integer> entry2){
                if (entry1.getValue() == entry2.getValue()){
                    //if there are exactly the same occurrences
                  	//这里用entry1.compareTo(entry2)的原因是因为我们本来就desire的是更小的lexi order的string
                  	//而下面之所以要换成-(e1-e2) = e2 - e1的原因在于我们desire更大的score，pq存放的东西本来就是
                  	//小到大，用e2-e1本就属于要令pq存放大到小的无奈之举。compareTo的结果本就是我们desire的
                    return entry1.getKey().compareTo(entry2.getKey());
                }
                return entry2.getValue() - entry1.getValue();
            }
        });
        
        for (String user : patternMap.keySet()){
            Set<String> patterns = patternMap.get(user);
            for (String pattern : patterns){
                patternCompare.put(pattern, patternCompare.getOrDefault(pattern, 0)+1);
            }
        }
        
        for (Map.Entry<String, Integer> entry : patternCompare.entrySet()){
            pq.offer(entry);
        }
        
        return Arrays.asList(pq.poll().getKey().split(" "));
    }
    
   public String getPatternString(List<String> jointList){
       return String.join(" ", jointList);
   }
}

class Visit{
    String user;
    int time;
    String web;
    
    public Visit(String u, int t, String w){
        user = u;
        time = t;
        web = w;
    }
}

621. Task Scheduler code

import java.util.*;
import java.lang.*;
class Solution {
    public int leastInterval(char[] tasks, int n) {
        Map<Character, Integer> taskOccur = new HashMap<>();
        int sbMax = tasks.length + n*(tasks.length-1);
        Queue<Map.Entry<Character, Integer>> pq = new PriorityQueue<>((e1, e2) -> e2.getValue() - e1.getValue());
        
        for (int i = 0; i < tasks.length; i++){
            taskOccur.put(tasks[i], taskOccur.getOrDefault(tasks[i], 0)+1);
        }
        
        for (Map.Entry<Character, Integer> entry : taskOccur.entrySet()){
            pq.offer(entry);
        }
        
        List<Character> result = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        
        while (!pq.isEmpty()){
            Map.Entry<Character, Integer> candidate = pq.poll();
            if (sb.length() < 1){
                sb.append(candidate.getKey());
                taskOccur.put(candidate.getKey(), taskOccur.get(candidate.getKey())-1);
            }else{
                while (!(pq.isEmpty()||okToAdd(candidate.getKey(), sb, n))){
                    candidate = pq.poll();
                }
                if (okToAdd(candidate.getKey(), sb, n)){
                    //candidate is ready to use
                    sb.append(candidate.getKey());
                    taskOccur.put(candidate.getKey(), taskOccur.get(candidate.getKey())-1);
                }else{
                    //there is no right key, add idle
                    sb.append(Character.valueOf('i'));
                }
            }
            resumePQ(taskOccur, pq);
        }
        
        return sb.length();
    }
    
    public boolean okToAdd(Character candidate, StringBuilder sb, int n){
        for (int i = sb.length() - 1; i >= 0 && i >= sb.length() - n; i--){
            if (sb.charAt(i) == candidate.charValue()){
                return false;
            }
        }
        return true;
    }
    
    public void resumePQ(Map<Character, Integer> taskOccur, Queue<Map.Entry<Character, Integer>> pq){
        pq.clear();
        for (Map.Entry<Character, Integer> entry : taskOccur.entrySet()){
            if (entry.getValue() > 0){
                pq.offer(entry);
            }
        }
    }
}

621. Task Scheduler better code

import java.util.*;
import java.lang.*;
class Solution {
    public int leastInterval(char[] tasks, int n) {
        Map<Character, Integer> freq = new HashMap<>();
        for (int i = 0; i < tasks.length; ++i){
            freq.put(tasks[i], freq.getOrDefault(tasks[i], 0) + 1);
        }
        int[] nextValid = new int[freq.entrySet().size()], rest = new int[freq.entrySet().size()];
        int ptr = 0; 
        for (Map.Entry<Character, Integer> entry : freq.entrySet()){
            //since every task can be place on the first position
            nextValid[ptr] = 1;
            rest[ptr] = entry.getValue();
            ptr++;
        }
        
        int time = 0;
        for (int i = 0; i < tasks.length; ++i){
            ++time;
            int minNextValid = Integer.MAX_VALUE;
            for (int j = 0; j < nextValid.length; ++j){
                if (rest[j] > 0){
                    minNextValid = Math.min(minNextValid, nextValid[j]);
                }
            }
            
            time = Math.max(time, minNextValid);
            int maxRest = Integer.MIN_VALUE;
            int nextAvailableIndex = -1;
            for (int j = 0; j < nextValid.length; ++j){
                if (nextValid[j] <= time && rest[j] > 0){
                    nextAvailableIndex = Math.max(maxRest, rest[j]) == maxRest?nextAvailableIndex:j;
                    maxRest = Math.max(maxRest, rest[j]);
                }
            }
            nextValid[nextAvailableIndex] = nextValid[nextAvailableIndex] + n + 1;
            rest[nextAvailableIndex]--;
        }
        
        
        return time;
    }
}

2021-10-26: 692. Top K Frequent Words code

import java.util.*;
class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        List<String> result = new ArrayList<>();
        Map<String, Integer> freq = new HashMap<>();
        for (int i = 0; i < words.length; ++i){
            freq.put(words[i], freq.getOrDefault(words[i], 0)+1);
        }
        
        Queue<Map.Entry<String, Integer>> pq = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>(){
            @Override
            public int compare(Map.Entry<String, Integer> e1, Map.Entry<String, Integer> e2){
                if (e1.getValue() == e2.getValue()){
                    //lexi
                    return e1.getKey().compareTo(e2.getKey());
                }
                return -(e1.getValue() - e2.getValue());
            }
        });
        
       for (Map.Entry<String, Integer> entry : freq.entrySet()){
           pq.offer(entry);
       }
        
       for (int i = 0; i < k; ++i){
           result.add(pq.poll().getKey());
       }
        
       return result;
    }
}

2021-10-27: 347. Top K Frequent Elements code

import java.util.*;
import java.lang.*;
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        int[] res = new int[k];
        for (int i = 0; i < nums.length; ++i){
            freq.put(nums[i], freq.getOrDefault(nums[i], 0) + 1);
        }
        
        Queue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>(new Comparator<Map.Entry<Integer, Integer>>(){
            @Override
            public int compare(Map.Entry<Integer, Integer> e1, Map.Entry<Integer, Integer> e2){
                return e2.getValue() - e1.getValue();
            }
        });
        
        for (Map.Entry<Integer, Integer> entry : freq.entrySet()){
            pq.offer(entry);
        }
        
        for (int i = 0; i < k; ++i){
            //poll from pq
            res[i] = pq.poll().getKey().intValue();
        }
        return res;
    }
}

2021-10-27: 1647. Minimum Deletions to Make Character Frequencies Unique code

import java.util.*;
class Solution {
    public int minDeletions(String s) {
        char[] charArray = s.toCharArray();
        Arrays.sort(charArray);
        Set<Integer> freqSet = new HashSet<>();
        int res = 0, freq = 1;
        Character ch = charArray[0];
        for (int i = 0; i < charArray.length; ++i){
            if (i < charArray.length - 1 && charArray[i+1] != ch){
                if (i == charArray.length - 2 && charArray[i+1] != ch){
                    int newFreq = freq;
                    while (freqSet.contains(freq)){
                        --freq;
                    }
                    res = freq > 0?res + (newFreq - freq):res + newFreq;
                    freqSet.add(freq);
                    freq = 1;
                    if (freqSet.contains(freq)){
                        res++;
                    }
                    break;
                }else{
                    int newFreq = freq;
                    while (freqSet.contains(freq)){
                        --freq;
                    }
                    res = freq > 0?res + (newFreq - freq):res + newFreq;
                    freqSet.add(freq);
                    freq = 1;
                    ch = charArray[i+1];
                }
            }else if (i < charArray.length - 1 && charArray[i+1] == ch){
                ++freq;
            }else if (i == charArray.length - 1){
                int newFreq = freq;
                while (freqSet.contains(freq)){
                    --freq;
                }
                res = freq > 0?res + (newFreq - freq):res + newFreq;
            }else{
                //
            }
        }
        return res;
    }
}

2021-11-08: 912. Sort an Array Code

class Solution {
    public int[] sortArray(int[] nums) {
        //base
        if (nums.length <= 1){
            return nums;
        }
        //div
        int leftLength = nums.length/2, rightLength = nums.length - leftLength, rightCount = 0;
        int[] left = new int[leftLength], right = new int[rightLength], res = new int[nums.length];
        for (int i = 0; i < nums.length; ++i){
            if (i < leftLength){
                left[i] = nums[i];
            }else{
                right[rightCount++] = nums[i];
            }
        }
        //sort
        int[] leftSorted = sortArray(left), rightSorted = sortArray(right);
        //merge
        int leftPtr = 0, rightPtr = 0;
        for (int i = 0; i < res.length; ++i){
            if (leftPtr == leftSorted.length){
                res[i] = rightSorted[rightPtr++];
            }else if (rightPtr == rightSorted.length){
                res[i] = leftSorted[leftPtr++];
            }else if (leftSorted[leftPtr] <= rightSorted[rightPtr]){
                res[i] = leftSorted[leftPtr++];
            }else if (leftSorted[leftPtr] > rightSorted[rightPtr]){
                res[i] = rightSorted[rightPtr++];
            }else{
                //
            }
        }
        return res;
    }
}

5. Longest Palindromic Substring Code

import java.lang.*;
import java.util.*;
class Solution {
    public String longestPalindrome(String s) {
        //Map<String, Integer> map = new HashMap<>();
        //Queue<Map.Entry<String, Integer>> pq = new PriorityQueue<>((e1, e2) -> e2.getValue() - e1.getValue());
        s = "abb";
        if (s.length() < 1){
            return s;
        }
        char[] old = s.toCharArray(), reverse = new char[old.length];
        //reverse
        int lastOldIndex = old.length - 1;
        for (int i = 0; i < reverse.length; ++i){
            reverse[i] = old[lastOldIndex - i];
        }
        //compare
        return findTheValidLongestSubsequence(old, reverse);
    }
    
    public String findTheValidLongestSubsequence(char[] old, char[] reverse){
        List<String> res = new ArrayList<>();
        int max = Integer.MIN_VALUE;
        String result = "";
        for (int i = 0; i < old.length; ++i){
            if (i == 0){
                if (old[i] == reverse[i]){
                    res.add(String.valueOf(old[i]));
                    result = String.valueOf(old[i]);
                    max = 1;
                }else{
                    res.add("");
                }
            }else{
                if (old[i] == reverse[i]){
                    res.add(res.get(i-1).concat(String.valueOf(old[i])));
                    if (res.get(res.size()-1).length() >= max){
                        result = res.get(res.size()-1);
                        max = result.length();
                    }
                }else{
                    res.add("");
                }
                
            }
        }
        return result != ""?result:String.valueOf(old[0]);
    }
}

2021-11-24 Lintcode: 104. 合并k个排序链表 Code

/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */ 
import java.util.*;
public class Solution {
    /**
     * @param lists: a list of ListNode
     * @return: The head of one sorted list.
     */
    public ListNode mergeKLists(List<ListNode> lists) {  
        // write your code here
        ListNode res = lists.get(0);
        for (int i = 1; i < lists.size(); ++i){
            res = merge(res, lists.get(i));
        }
        return res;
    }

    public ListNode merge(ListNode res, ListNode ln2){
        if (res == null || ln2 == null){
            return ln2 == null ? res : ln2;
        }
        ListNode ln1Ptr = res, ln2Ptr = ln2, temp = new ListNode(0), tempPtr = temp;
        while (ln1Ptr != null && ln2Ptr != null) {
            if (ln1Ptr.val <= ln2Ptr.val){
                ListNode tempListNode = new ListNode(ln1Ptr.val);
                tempPtr.next = tempListNode;
                tempPtr = tempPtr.next;
                ln1Ptr = ln1Ptr.next;
            }else{
                ListNode tempListNode = new ListNode(ln2Ptr.val);
                tempPtr.next = tempListNode;
                tempPtr = tempPtr.next;
                ln2Ptr = ln2Ptr.next;
            }
        }
        while (ln1Ptr != null) {
            ListNode tempListNode = new ListNode(ln1Ptr.val);
            tempPtr.next = tempListNode;
            tempPtr = tempPtr.next;
            ln1Ptr = ln1Ptr.next;
        }
        while (ln2Ptr != null) {
            ListNode tempListNode = new ListNode(ln2Ptr.val);
            tempPtr.next = tempListNode;
            tempPtr = tempPtr.next;
            ln2Ptr = ln2Ptr.next;
        }
        return temp.next;
    }
}

2021.11.24: 102 · 带环链表 Code

/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
import java.util.*;
public class Solution {
    /**
     * @param head: The first node of linked list.
     * @return: True if it has a cycle, or false
     */
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null){
            return false;
        }
        ListNode fast = head.next;
        ListNode slow = head;

        while (fast != null && fast.next != null){
            if (fast == slow) {
                return true;
            }
            fast = fast.next.next;
            slow = slow.next;
        }
        return false;
}

}

2021-11-25 Lintcode: 94 · Binary Tree Maximum Path Sum Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
import java.lang.*;
class Solution {
    int maxSum = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        int gain = maxGain(root);
        return Math.max(maxSum, gain);
    }
    
    public int maxGain(TreeNode root){
        if (root == null){
            return 0;
        }
        int leftGain = Math.max(maxGain(root.left), 0);
        int rightGain = Math.max(maxGain(root.right), 0);
        int priceNewPath = leftGain + rightGain + root.val;
        maxSum = priceNewPath >= maxSum ? priceNewPath : maxSum;
        return root.val + Math.max(leftGain, rightGain);
    }

}

Code End Pointer

2021-11-25 Lintcode: 94 · Binary Tree Maximum Path Sum Code

import java.lang.*;
class Solution {
    public int lengthOfLIS(int[] nums) {
        int[][] dpRes = new int[nums.length][2];
        generateDP(nums, dpRes);
        int maxVal = Integer.MIN_VALUE;
        for (int[] info : dpRes){
            maxVal = Math.max(maxVal, info[1]);
        }
        return maxVal;
    }
    
    public void generateDP(int[] nums, int[][] dpRes){
        dpRes[0] = new int[]{nums[0], 1};
        for (int i = 1; i < nums.length; ++i){
            int localMax = Integer.MIN_VALUE;
            for (int j = 0; j < i; ++j){
                if (nums[i] > dpRes[j][0]){
                    localMax = Math.max(localMax, dpRes[j][1] + 1);
                }
            }
            dpRes[i] = new int[]{nums[i], Math.max(localMax, 1)};
        }
    }
}

2021-11-25 Lintcode: 45 · Maximum Subarray Difference

Given an array with integers.

Find two non-overlapping subarrays A and B, which SUM(A) - SUM(B) ∣SUM(A)−SUM(B)∣ is the largest.

Return the largest difference.

一开始的思路：

改进的思路：code

Thought

回到目录

九章算法

2021-11-24

Others

急需解决

task scheduler的代码里，为何把time++放在28行和最后的结果完全不一样？

[Review]

binary search for all the search
just sort() it
- Java的array sort是按照ascending的格式来sort的
  - 怎么变成descending的格式？
简单的快排真的垃圾
如果可以的话，尽可能的在一个arr上进行改动，rather than不停的赋值新的arr
map.getOrDefault(Object key, V defaultValue): 尝试从一个map中access一个value，如果没有这个key的话，就返还一个自己设定的default
comparator: Comparator<Player> comparator = (p1, p2) -> p1.getRanking() - p2.getRanking();
- 快速新建comparator的方法，可以直接用在priority queue的initialization里
- 后面这个方法实际上就是实现了compare这个方法：
  - Compares its two arguments for order. Returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.
- 实例化pq的例子是：Queue<E> pq = new PriorityQueue<(e1, e2) -> e1.field - e2.field>//如果按照从小到大的顺序来排序的话
需要注意的是，priority queue的头是least element，所以如果想令他的头是most element的话，需要manipulate一下comparator：
- 之前要实现的是 int compare(e1, e2)，当返还-的时候，pq认为e1比e2小，然后把e1丢在了前面，但是我们希望把e2丢前面，那么就negate一下结果就好
- 理解如果design compare的时候，我们要和需要用到comparator的东西相结合。比如pq，compare返还负数的时候，compare会把e1给排在e2前面（因为e1 - e2 < 0），如果e1和e2各有一个value，我们想把更大的值放在前面的话，我们就需要用-(e1.val - e2.val)。
StringBuilder在lang中
那种带有很多个field，然后需要排序的东西，比较好的做法是把他们封装成一个类，然后调用collections.sort去sort code像这样，然后这样的类直接定义在solution class一个级别 class 什么什么就好了

[python]sort dictionary by value python:

  x = {1: 2, 3: 4, 4: 3, 2: 1, 0: 0}
  new_dict = {k: v for k, v in sorted(x.items(), key=lambda item: item[1])}
  {0: 0, 2: 1, 1: 2, 4: 3, 3: 4}
  
  or
  
  dict(sorted(x.items(), key=lambda item: item[1]))
  sorted(x.items(), key=lambda item: item[1])
  -> [(1:2), (2:3), (3:4)]
  {0: 0, 2: 1, 1: 2, 4: 3, 3: 4}

[python]Regular Expression

raw string is a string prefix with a r: not to handle back slash in any way(no escaping)

所以’\ttab’和r’\ttab’是不一样的，前者会处理backslash
case sensitive

.       - Any Character Except New Line
\d      - Digit (0-9)
\D      - Not a Digit (0-9)
\w      - Word Character (a-z, A-Z, 0-9, _)
\W      - Not a Word Character
\s      - Whitespace (space, tab, newline)
\S      - Not Whitespace (space, tab, newline)
    
\b      - Word Boundary
\B      - Not a Word Boundary
^       - Beginning of a String
$       - End of a String
    
[]      - Matches Characters in brackets
[^ ]    - Matches Characters NOT in brackets
|       - Either Or
( )     - Group
    
Quantifiers:
*       - 0 or More
+       - 1 or More
?       - 0 or One
{3}     - Exact Number
{3,4}   - Range of Numbers (Minimum, Maximum)
    
    
#### Sample Regexs ####
    
[a-zA-Z0-9_.+-]+@[a-zA-Z0-9-]+\.[a-zA-Z0-9-.]+

re.search
- scan through the whole string and look for the FIRST match, and return the match object. Return None if no position in the string matches the pattern.
  - match: https://docs.python.org/3/library/re.html#match-objects
  - 一般来说，只要用match.group(0)就可以得到具体的match
- Match with group: 在pattern里，用()括号括起来的就是一个group，在识别的时候，不仅把符合pattern的目标识别出来，还会把目标中具体的不同的group的信息识别出来，比如我的pattern是r"(\w\*)([2-3]\*)"，那么就知道前面的字母是一个组，而后面的数字是一个组，那么一个识别出来的target string: “abc222”，用group(1)可以得到abc，group(2)可以得到222

[Java] Regex

[latex]并列图片

[code]How to read java doc, python doc?

use java se documentation kit，很多东西都在base里
- use指的是usage of the (this) class

[Java] bitwise & and decide if the number is odd/even

The bitwise & operator 把两个operands的两边的bit表示拉取出来，一个bit一个bit的用&去比，会得出一个新的数字
decide if the number is odd/even:
1. 模2，看看结果是不是0
2. & 1，看看结果是不是1
  - 因为1的bit是r’0*1’，所以最后一位必定是1，前面都是0，所以前面的结果肯定都是0，因为0不管和谁&结果都是0，而最后一位，只有奇数的最后一位必定是1，所以奇数和1&必定是1

[Java] Arrays.copy(array)

[Java] k++

k++ increases the value of k, but returns the previous value. 他会在所有基于k的操作都结束的时候再增加k的值
- 即使是在for i 的运行中的时候，i++都是可以理解为是在loop中基于i的操作完成了之后再进行的
++i will increment the value of i, and then return the incremented value.

[Java] Map.Entry<k, v>

entry是一个类似键值对的接口，好像只能通过AbstractMap.SimpleEntry(K k, V v);去实例化，但这样子实例化似乎也没啥太大的意义。最大的意义在Map.entrySet()会返还一个entry的set，这样子可以使用foreach去access各个键值对，用

[Java] Priority Queue in reverse order

[Code] Sorting

Insertion Sort

public static void insertionSortImplement(int[] nums){
  //traverse整个array，把这当成没有sort好的那个array
  for (int i = 0; i < nums.length; i++){
    //tmp为目前要丢进sort好的arr中的那个元素
    int tmp = nums[i];

    int j;
    //接下来，我们遍历sort好的arr -> 现在的结构：[- - - - | ^ - - -]，左边是sort好的
    //所以j要--
    for (j = i; j > 0 && nums[j - 1] > tmp; j--){
      //当遇到比tmp大的值，就把他们向前移动一格
      nums[j] = nums[j - 1];
    }
    //把tmp插入到合适的位置
    nums[j] = tmp;
  }
}

可以理解为要维护一个sort好的array，这个array一开始是空的，然后从没有sort好的arr中不停的抽取东西插进sort好的list中。

[] [4 2 3 1]
[4] [2 3 1]
[2 4] [3 1]
[2 3 4] [1]
[1 2 3 4] []

原理就是这样，代码实现看代码

Merge Sort

算法：split，sort，merge
每次在写的时候不要犯下一些莫名其妙的小错误
优点是不管原始的数组多么的乱，排序的效率都是恒定的$O(nlogn)$；缺点就是需要重复的利用新的数组来存放排好序的数组，所以很浪费空间

Quick Sort

public static void quickSort(int[] nums, int left, int right){
    if (left < right){
        //选择数组的最后一个作为pivot
        int i = left, j = left;
        int pivot = nums[right];
      	//此时的i可以看作是一直指向最左边的比pivot大的元素
      	//j扫过整个arr，是一个希望找到比pivot小，能和i指向的位置替换的元素的指针
        for (j = left; j < right; j++){
            if (nums[j] < pivot){
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
                i++;
            }
        }

        nums[j] = nums[i];
        nums[i] = pivot;
        quickSort(nums, left, i-1);
        quickSort(nums, i+1, right);
    }
}

其实最主要的思想就是：在每一步，快排选择一个值作为pivot，然后把所有比他小的元素放到pivot的左边，把所有比他大的元素放到pivot的右边，然后再分别排序在pivot左边和右边的arr

回到目录

硬背

Java Primitive type and space

Data Type	Size	Description
byte	1 byte	Stores whole numbers from -128 to 127
short	2 bytes	Stores whole numbers from -32,768 to 32,767
int	4 bytes	Stores whole numbers from -2,147,483,648 to 2,147,483,647
long	8 bytes	Stores whole numbers from -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807
float	4 bytes	Stores fractional numbers. Sufficient for storing 6 to 7 decimal digits
double	8 bytes	Stores fractional numbers. Sufficient for storing 15 decimal digits
boolean	1 bit	Stores true or false values
char	2 bytes	Stores a single character/letter or ASCII values

模版：mergeSort

public void mergeSort(int[] A, int start, int end, int[] temp){
  if (start >= end){
    return;
  }
  //deal with lhs
  mergeSort(A, start, (start+end)/2, temp);
  //deal with rhs
  mergeSort(A, (start+end)/2+1, end, temp);
  //merge
  merge(A, start, end, temp);
}

public void merge(int[] A, int start, int end, int[] temp){
  int middle = (start + end)/2;
  int leftIndex = start;
  int rightIndex = middle + 1;
  int index = start;
  while (leftIndex <= middle && rightIndex <= end) {
    if (A[leftIndex] < A[rightIndex]) {
      temp[index++] = A[leftIndex++];
    }else{
      temp[index++] = A[rightIndex++];
    }
  }
  while (leftIndex <= middle){
    temp[index++] = A[leftIndex++];
  }
  while (rightIndex <= end){
    temp[index++] = A[rightIndex++];
  }
  for (int i = start; i <= end; ++i){
    A[i] = temp[i];
  }
}

待补充

$O(log_{f}N)$

Sorting

Java Regex

Java Pointer

回到目录