Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit2d86af3

Browse files
author
Botao Xiao
committed
[Function add]: 1. Add leetcode solutions.
1 parent90df0ed commit2d86af3

4 files changed

+293
-0
lines changed

‎leetcode/393. UTF-8 Validation.md

Lines changed: 102 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,102 @@
1+
##393. UTF-8 Validation
2+
3+
###Question
4+
A character in UTF8 can be from 1 to 4 bytes long, subjected to the following rules:
5+
6+
For 1-byte character, the first bit is a 0, followed by its unicode code.
7+
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.
8+
This is how the UTF-8 encoding would work:
9+
10+
```
11+
Char. number range | UTF-8 octet sequence
12+
(hexadecimal) | (binary)
13+
--------------------+---------------------------------------------
14+
0000 0000-0000 007F | 0xxxxxxx
15+
0000 0080-0000 07FF | 110xxxxx 10xxxxxx
16+
0000 0800-0000 FFFF | 1110xxxx 10xxxxxx 10xxxxxx
17+
0001 0000-0010 FFFF | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
18+
```
19+
20+
Given an array of integers representing the data, return whether it is a valid utf-8 encoding.
21+
22+
Note:
23+
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.
24+
25+
```
26+
Example 1:
27+
28+
data = [197, 130, 1], which represents the octet sequence: 11000101 10000010 00000001.
29+
30+
Return true.
31+
It is a valid utf-8 encoding for a 2-bytes character followed by a 1-byte character.
32+
Example 2:
33+
34+
data = [235, 140, 4], which represented the octet sequence: 11101011 10001100 00000100.
35+
36+
Return false.
37+
The first 3 bits are all one's and the 4th bit is 0 means it is a 3-bytes character.
38+
The next byte is a continuation byte which starts with 10 and that's correct.
39+
But the second continuation byte does not start with 10, so it is invalid.
40+
```
41+
42+
###Solutions:
43+
* Method 1: String + Recursion
44+
```Java
45+
classSolution {
46+
privateint[] data;
47+
publicbooleanvalidUtf8(int[]data) {
48+
this.data= data;
49+
return valid(0);
50+
}
51+
publicbooleanvalid(intindex){
52+
if(index== data.length)returntrue;
53+
String cur=Integer.toBinaryString(data[index]);
54+
if(cur.length()<8|| cur.startsWith("0")){
55+
return valid(index+1);
56+
}elseif(cur.startsWith("10")){
57+
returnfalse;
58+
}else{
59+
int ind= cur.indexOf("0");
60+
if(ind>4|| ind==-1|| ind+ index> data.length)returnfalse;
61+
index++;
62+
for(int i= index; i< index+ ind-1; i++){
63+
String s=Integer.toBinaryString(data[i]);
64+
if(s.length()<8||!s.startsWith("10"))returnfalse;
65+
}
66+
return valid(index+ ind-1);
67+
}
68+
}
69+
}
70+
```
71+
72+
* Method 2: Bit operation + recursion
73+
```Java
74+
classSolution {
75+
privateint[] data;
76+
publicbooleanvalidUtf8(int[]data) {
77+
this.data= data;
78+
return valid(0);
79+
}
80+
privatebooleanvalid(intindex){
81+
if(index== data.length)returntrue;
82+
int cur= data[index];
83+
if((cur& (1<<7))==0){
84+
return valid(index+1);
85+
}elseif((cur& (3<<6))==0b10000000){
86+
returnfalse;
87+
}else{
88+
int count=0;
89+
int mask=0b10000000;
90+
while((cur& mask)>0){
91+
count++;
92+
mask>>=1;
93+
}
94+
if(count>4|| index+ count> data.length)returnfalse;
95+
for(int i= index+1; i< index+ count; i++){
96+
if((data[i]& (3<<6))!=0b10000000)returnfalse;
97+
}
98+
return valid(index+ count);
99+
}
100+
}
101+
}
102+
```

‎leetcode/692. Top K Frequent Words.md

Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
1+
##692. Top K Frequent Words
2+
3+
###Question
4+
Given a non-empty list of words, return the k most frequent elements.
5+
6+
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.
7+
8+
```
9+
Example 1:
10+
Input: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
11+
Output: ["i", "love"]
12+
Explanation: "i" and "love" are the two most frequent words.
13+
Note that "i" comes before "love" due to a lower alphabetical order.
14+
Example 2:
15+
Input: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
16+
Output: ["the", "is", "sunny", "day"]
17+
Explanation: "the", "is", "sunny" and "day" are the four most frequent words,
18+
with the number of occurrence being 4, 3, 2 and 1 respectively.
19+
```
20+
21+
Note:
22+
1. You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
23+
2. Input words contain only lowercase letters.
24+
Follow up:
25+
1. Try to solve it in O(n log k) time and O(n) extra space.
26+
27+
###Solution
28+
* Method 1: TreeMap + PriorityQueue
29+
```Java
30+
classSolution {
31+
privatestaticclassPair{
32+
String s;
33+
int count;
34+
publicPair(Strings,intcount){
35+
this.s= s;
36+
this.count= count;
37+
}
38+
}
39+
publicList<String>topKFrequent(String[]words,intk) {
40+
TreeMap<String,Integer> treeMap=newTreeMap<>(newComparator<String>(){//time complexity: O(nlogN)
41+
@Override
42+
publicintcompare(Stringa,Stringb){
43+
return a.compareTo(b);
44+
}
45+
});
46+
for(String word: words){
47+
treeMap.put(word, treeMap.getOrDefault(word,0)+1);
48+
}
49+
50+
PriorityQueue<Pair> pq=newPriorityQueue<>(newComparator<Pair>(){//time complexity: O(nlogN)
51+
@Override
52+
publicintcompare(Pairp1,Pairp2){
53+
return p2.count== p1.count? p1.s.compareTo(p2.s): p2.count- p1.count;
54+
}
55+
});
56+
for(Map.Entry<String,Integer> entry: treeMap.entrySet()){
57+
pq.offer(newPair(entry.getKey(), entry.getValue()));
58+
}
59+
List<String> result=newArrayList<>();
60+
for(int i=0; i< k; i++){
61+
result.add(pq.poll().s);
62+
}
63+
return result;
64+
}
65+
}
66+
```
Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
##829. Consecutive Numbers Sum
2+
3+
###Question
4+
Given a positive integer N, how many ways can we write it as a sum of consecutive positive integers?
5+
6+
```
7+
Example 1:
8+
9+
Input: 5
10+
Output: 2
11+
Explanation: 5 = 5 = 2 + 3
12+
Example 2:
13+
14+
Input: 9
15+
Output: 3
16+
Explanation: 9 = 9 = 4 + 5 = 2 + 3 + 4
17+
Example 3:
18+
19+
Input: 15
20+
Output: 4
21+
Explanation: 15 = 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5
22+
Note: 1 <= N <= 10 ^ 9.
23+
```
24+
25+
###Solution:
26+
* Method 1: Math
27+
* We assume the first term is x and totally m terms.
28+
* 2xm + m(m - 1) = 2N => we try all possible m and find if there is a valid x.
29+
```Java
30+
classSolution {
31+
publicintconsecutiveNumbersSum(intN) {
32+
int res=0;
33+
for(int m=1;;m++){
34+
int mx=2*N- m*(m-1);
35+
if(mx<=0)break;
36+
elseif(mx% (2* m)==0) res++;
37+
}
38+
return res;
39+
}
40+
}
41+
```
Lines changed: 84 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,84 @@
1+
##947. Most Stones Removed with Same Row or Column
2+
3+
###Question
4+
On a 2D plane, we place stones at some integer coordinate points. Each coordinate point may have at most one stone.
5+
6+
Now, a move consists of removing a stone that shares a column or row with another stone on the grid.
7+
8+
What is the largest possible number of moves we can make?
9+
10+
```
11+
Example 1:
12+
13+
Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
14+
Output: 5
15+
Example 2:
16+
17+
Input: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
18+
Output: 3
19+
Example 3:
20+
21+
Input: stones = [[0,0]]
22+
Output: 0
23+
```
24+
25+
Note:
26+
1. 1 <= stones.length <= 1000
27+
2. 0 <= stones[i][j] < 10000
28+
29+
###Solutions:
30+
* Method 1: Union find
31+
* Union the row and col, it means if we have a stone, we union the row number and col number.
32+
```Java
33+
classSolution {
34+
privateint[] uf;
35+
publicintremoveStones(int[][]stones) {
36+
this.uf=newint[20000];
37+
for(int i=0; i< uf.length; i++) uf[i]= i;
38+
for(int[] stone: stones){
39+
union(stone[0], stone[1]+10000);// union the row with col
40+
}
41+
Set<Integer> seen=newHashSet<>();
42+
for(int[] stone: stones){
43+
seen.add(find(stone[0]));
44+
}
45+
return stones.length- seen.size();
46+
}
47+
privateintfind(inti){
48+
if(uf[i]!= i){
49+
uf[i]= find(uf[i]);
50+
}
51+
return uf[i];
52+
}
53+
privatevoidunion(inti,intj){
54+
int p= find(i);
55+
int q= find(j);
56+
uf[p]= q;
57+
}
58+
}
59+
```
60+
61+
* Method 2: dfs
62+
* Check all stones and if row number or col number is same, we can do the dfs.
63+
```Java
64+
classSolution {
65+
publicintremoveStones(int[][]stones) {
66+
Set<int[]> visited=newHashSet<>();
67+
int count=0;
68+
for(int[] stone: stones){
69+
if(visited.contains(stone))continue;
70+
dfs(stone, visited, stones);
71+
count++;
72+
}
73+
return stones.length- count;
74+
}
75+
privatevoiddfs(int[]stone,Set<int[]>visited,int[][]stones){
76+
visited.add(stone);
77+
for(int[] s: stones){
78+
if(visited.contains(s))continue;
79+
if(stone[0]== s[0]|| stone[1]== s[1])
80+
dfs(s, visited, stones);
81+
}
82+
}
83+
}
84+
```

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp