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

Commit6c31644

Browse files
committed
[Function add]
1. Add leetcode solutions.
1 parentc38bef6 commit6c31644

File tree

3 files changed

+168
-0
lines changed

3 files changed

+168
-0
lines changed
Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
##340. Longest Substring with At Most K Distinct Characters
2+
3+
###Question
4+
Given a string, find the length of the longest substring T that contains at most k distinct characters.
5+
6+
```
7+
Example 1:
8+
9+
Input: s = "eceba", k = 2
10+
Output: 3
11+
Explanation: T is "ece" which its length is 3.
12+
13+
Example 2:
14+
15+
Input: s = "aa", k = 1
16+
Output: 2
17+
Explanation: T is "aa" which its length is 2.
18+
```
19+
20+
###Solutions
21+
* Method 1: Sliding window + HashMap
22+
```Java
23+
classSolution {
24+
publicintlengthOfLongestSubstringKDistinct(Strings,intk) {
25+
if(s.length()<= k)return s.length();
26+
int start=0, end=0;
27+
Map<Character,Integer> map=newHashMap<>();
28+
char[] arr= s.toCharArray();
29+
int max=0;
30+
while(end< s.length()){
31+
if(map.containsKey(arr[end])|| map.size()< k){
32+
map.put(arr[end], map.getOrDefault(arr[end],0)+1);
33+
max=Math.max(max, end- start+1);
34+
}else{// current we need to remove
35+
map.put(arr[end],1);
36+
while(map.size()> k){
37+
char c= arr[start++];
38+
int count= map.get(c);
39+
if(count==1){
40+
map.remove(c);
41+
}else{
42+
map.put(c, count-1);
43+
}
44+
}
45+
}
46+
end++;
47+
}
48+
return max;
49+
}
50+
}
51+
```

‎leetcode/509. Fibonacci Number.md

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
##509. Fibonacci Number
2+
3+
###Question
4+
The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,
5+
6+
F(0) = 0, F(1) = 1
7+
F(N) = F(N - 1) + F(N - 2), for N > 1.
8+
9+
Given N, calculate F(N).
10+
11+
```
12+
Example 1:
13+
14+
Input: 2
15+
Output: 1
16+
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.
17+
18+
Example 2:
19+
20+
Input: 3
21+
Output: 2
22+
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.
23+
24+
Example 3:
25+
26+
Input: 4
27+
Output: 3
28+
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.
29+
```
30+
31+
Note:
32+
* 0 ≤ N ≤ 30.
33+
34+
35+
###Solutions
36+
* Method 1: DP
37+
```Java
38+
classSolution {
39+
publicintfib(intN) {
40+
if(N<2)returnN;
41+
int[] dp=newint[N+1];
42+
dp[0]=0; dp[1]=1;
43+
for(int i=2; i<=N; i++){
44+
dp[i]= dp[i-1]+ dp[i-2];
45+
}
46+
return dp[N];
47+
}
48+
}
49+
```
Lines changed: 68 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,68 @@
1+
##636. Exclusive Time of Functions
2+
3+
###Question
4+
On a single threaded CPU, we execute some functions. Each function has a unique id between 0 and N-1.
5+
6+
We store logs in timestamp order that describe when a function is entered or exited.
7+
8+
Each log is a string with this format: "{function_id}:{"start" | "end"}:{timestamp}". For example, "0:start:3" means the function with id 0 started at the beginning of timestamp 3. "1:end:2" means the function with id 1 ended at the end of timestamp 2.
9+
10+
A function's exclusive time is the number of units of time spent in this function. Note that this does not include any recursive calls to child functions.
11+
12+
Return the exclusive time of each function, sorted by their function id.
13+
14+
```
15+
Example 1:
16+
17+
Input:
18+
n = 2
19+
logs = ["0:start:0","1:start:2","1:end:5","0:end:6"]
20+
Output: [3, 4]
21+
Explanation:
22+
Function 0 starts at the beginning of time 0, then it executes 2 units of time and reaches the end of time 1.
23+
Now function 1 starts at the beginning of time 2, executes 4 units of time and ends at time 5.
24+
Function 0 is running again at the beginning of time 6, and also ends at the end of time 6, thus executing for 1 unit of time.
25+
So function 0 spends 2 + 1 = 3 units of total time executing, and function 1 spends 4 units of total time executing.
26+
```
27+
28+
Note:
29+
1. 1 <= n <= 100
30+
2. Two functions won't start or end at the same time.
31+
3. Functions will always log when they exit.
32+
33+
34+
###Solutions
35+
* Method 1: Simulation
36+
```Java
37+
classSolution {
38+
publicint[]exclusiveTime(intn,List<String>logs) {
39+
int[] result=newint[n];
40+
int startTime=-1;
41+
int curId=-1;
42+
Stack<Integer> stack=newStack<>();
43+
for(String log: logs){
44+
String[] tokens= log.split(":");
45+
int id=Integer.parseInt(tokens[0]);
46+
int time=Integer.parseInt(tokens[2]);
47+
if(tokens[1].equals("start")){
48+
if(curId!=-1){
49+
result[curId]+= time- startTime;
50+
stack.push(curId);
51+
}
52+
curId= id;
53+
startTime= time;
54+
}else{// current log is for ending.
55+
result[curId]+= time- startTime+1;
56+
if(!stack.isEmpty()){
57+
curId= stack.pop();
58+
startTime= time+1;
59+
}else{
60+
curId=-1;
61+
startTime=-1;
62+
}
63+
}
64+
}
65+
return result;
66+
}
67+
}
68+
```

0 commit comments

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