A character in UTF8 can be from 1 to 4 bytes long, subjected to the following rules:

For 1-byte character, the first bit is a 0, followed by its unicode code.

For n-bytes character, the first n-bits are all one's, the n+1 bit is 0, followed by n-1 bytes with most significant 2 bits being 10.

This is how the UTF-8 encoding would work:

Given an array of integers representing the data, return whether it is a valid utf-8 encoding.

Note:

The input is an array of integers. Only the least significant 8 bits of each integer is used to store the data. This means each integer represents only 1 byte of data.

* Method 1: String + Recursion

```Java

class Solution {

private int[] data;

public boolean validUtf8(int[] data) {

this.data = data;

return valid(0);

}

public boolean valid(int index){

if(index == data.length) return true;

String cur = Integer.toBinaryString(data[index]);

if(cur.length() < 8 || cur.startsWith("0")){

return valid(index + 1);

}else if(cur.startsWith("10")){

return false;

}else{

int ind = cur.indexOf("0");

if(ind > 4 || ind == -1 || ind + index > data.length) return false;

index++;

for(int i = index; i < index + ind - 1; i++){

String s = Integer.toBinaryString(data[i]);

if(s.length() < 8 || !s.startsWith("10")) return false;

}

return valid(index + ind - 1);

}

}

}

```

* Method 2: Bit operation + recursion

```Java

class Solution {

private int[] data;

public boolean validUtf8(int[] data) {

this.data = data;

return valid(0);

}

private boolean valid(int index){

if(index == data.length) return true;

int cur = data[index];

if((cur & (1 << 7)) == 0){

return valid(index + 1);

}else if((cur & (3 << 6)) == 0b10000000){

return false;

}else{

int count = 0;

int mask = 0b10000000;

while((cur & mask) > 0){

count++;

mask >>= 1;

}

if(count > 4 || index + count > data.length) return false;

for(int i = index + 1; i < index + count; i++){

if((data[i] & (3 << 6)) != 0b10000000) return false;

}

return valid(index + count);

}

}

}

```

Given a non-empty list of words, return the k most frequent elements.

Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the word with the lower alphabetical order comes first.

Note:

1. You may assume k is always valid, 1 ≤ k ≤ number of unique elements.

2. Input words contain only lowercase letters.

Follow up:

1. Try to solve it in O(n log k) time and O(n) extra space.

* Method 1: TreeMap + PriorityQueue

```Java

class Solution {

private static class Pair{

String s;

int count;

public Pair(String s, int count){

this.s = s;

this.count = count;

}

}

public List<String> topKFrequent(String[] words, int k) {

TreeMap<String, Integer> treeMap = new TreeMap<>(new Comparator<String>(){ //time complexity: O(nlogN)

@Override

public int compare(String a, String b){

return a.compareTo(b);

}

});

for(String word : words){

treeMap.put(word, treeMap.getOrDefault(word, 0) + 1);

}

PriorityQueue<Pair> pq = new PriorityQueue<>(new Comparator<Pair>(){ //time complexity: O(nlogN)

@Override

public int compare(Pair p1, Pair p2){

return p2.count == p1.count ? p1.s.compareTo(p2.s) : p2.count - p1.count;

}

});

for(Map.Entry<String, Integer> entry : treeMap.entrySet()){

pq.offer(new Pair(entry.getKey(), entry.getValue()));

}

List<String> result = new ArrayList<>();

for(int i = 0; i < k; i++){

result.add(pq.poll().s);

}

return result;

}

}

```

Given a positive integer N, how many ways can we write it as a sum of consecutive positive integers?

* Method 1: Math

* We assume the first term is x and totally m terms.

* 2xm + m(m - 1) = 2N => we try all possible m and find if there is a valid x.

```Java

class Solution {

public int consecutiveNumbersSum(int N) {

int res = 0;

for(int m = 1;;m++){

int mx = 2 * N - m *(m - 1);

if(mx <= 0) break;

else if(mx % (2 * m) == 0) res++;

}

return res;

}

}

```

On a 2D plane, we place stones at some integer coordinate points. Each coordinate point may have at most one stone.

Now, a move consists of removing a stone that shares a column or row with another stone on the grid.

What is the largest possible number of moves we can make?

Note:

1. 1 <= stones.length <= 1000

2. 0 <= stones[i][j] < 10000

* Method 1: Union find

* Union the row and col, it means if we have a stone, we union the row number and col number.

```Java

class Solution {

private int[] uf;

public int removeStones(int[][] stones) {

this.uf = new int[20000];

for(int i = 0; i < uf.length; i++) uf[i] = i;

for(int[] stone : stones){

union(stone[0], stone[1] + 10000); // union the row with col

}

Set<Integer> seen = new HashSet<>();

for(int[] stone : stones){

seen.add(find(stone[0]));

}

return stones.length - seen.size();

}

private int find(int i){

if(uf[i] != i){

uf[i] = find(uf[i]);

}

return uf[i];

}

private void union(int i, int j){

int p = find(i);

int q = find(j);

uf[p] = q;

}

}

```

* Method 2: dfs

* Check all stones and if row number or col number is same, we can do the dfs.

```Java

class Solution {

public int removeStones(int[][] stones) {

Set<int[]> visited = new HashSet<>();

int count = 0;

for(int[] stone : stones){

if(visited.contains(stone)) continue;

dfs(stone, visited, stones);

count++;

}

return stones.length - count;

}

private void dfs(int[] stone, Set<int[]> visited, int[][] stones){

visited.add(stone);

for(int[] s : stones){

if(visited.contains(s)) continue;

if(stone[0] == s[0] || stone[1] == s[1])

dfs(s, visited, stones);

}

}

}

```