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

Commitb9154ce

Browse files
committed
[Function add]
1. Add leetcode solutions.
1 parent2467e78 commitb9154ce

4 files changed

+288
-0
lines changed
Lines changed: 78 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,78 @@
1+
#316. Remove Duplicate Letters
2+
3+
###Question
4+
Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.
5+
6+
```
7+
Example 1:
8+
9+
Input: "bcabc"
10+
Output: "abc"
11+
12+
Example 2:
13+
14+
Input: "cbacdcbc"
15+
Output: "acdb"
16+
```
17+
18+
19+
###Solutions
20+
* Method 1: Greedy
21+
* what we are greedy for: we are greedy for a smaller lexicographical order.
22+
```Java
23+
classSolution {
24+
publicStringremoveDuplicateLetters(Strings) {
25+
if(s.length()==0)return"";
26+
char[] arr= s.toCharArray();
27+
int[] count=newint[26];
28+
for(char c: arr){
29+
count[c-'a']++;
30+
}
31+
int pos=0;
32+
// Greedy for the smallest lexicographical order until we meet a letter exist the last time.
33+
// We assume it is c.
34+
for(int i=0; i< arr.length; i++){
35+
if(arr[i]< arr[pos]) pos= i;// always greedy for the smallest lexicographical order for current letter.
36+
if(--count[arr[i]-'a']==0)break;// once we meet a letter exists the last time, we need to break.
37+
}
38+
// remove all c in current string and make it as the beginning of the result.
39+
String next= s.substring(pos+1).replace(arr[pos]+"","");
40+
return arr[pos]+ removeDuplicateLetters(next);
41+
}
42+
}
43+
```
44+
45+
*Method2:Deque
46+
*The idea of deque is very same as previous one.
47+
```Java
48+
classSolution {
49+
publicStringremoveDuplicateLetters(Strings) {
50+
int[] count=newint[26];
51+
char[] arr= s.toCharArray();
52+
for(char c: arr) count[c-'a']++;
53+
boolean[] visited=newboolean[26];
54+
// Deque increasing.
55+
Deque<Character> dq=newLinkedList<>();
56+
for(char c: arr){
57+
count[c-'a']--;// remove the frequency of current letter.
58+
if(visited[c-'a'])continue;// means current character has already in the dq.
59+
// !dq.isEmpty(): Means current dq is not empty
60+
// dq.peekLast() > c: the end character in the dq has larger lexicographical order than c.
61+
// count[dq.peekLast() - 'a'] > 0: if end letter is at the last time appearence, it means we cannot remove it.
62+
while(!dq.isEmpty()&& dq.peekLast()> c&& count[dq.peekLast()-'a']>0){
63+
visited[dq.pollLast()-'a']=false;
64+
}
65+
visited[c-'a']=true;
66+
dq.offer(c);
67+
}
68+
StringBuilder sb=newStringBuilder();
69+
while(!dq.isEmpty()){
70+
sb.append(dq.poll());
71+
}
72+
return sb.toString();
73+
}
74+
}
75+
```
76+
77+
###Reference
78+
1.[Java solution usingStack with comments](https://leetcode.com/problems/remove-duplicate-letters/discuss/76769/Java-solution-using-Stack-with-comments)
Lines changed: 103 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,103 @@
1+
##382. Linked List Random Node
2+
3+
###Question
4+
Given a singly linked list, return a random node's value from the linked list. Each node must have the same probability of being chosen.
5+
6+
Follow up:
7+
What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space?
8+
9+
```
10+
Example:
11+
12+
// Init a singly linked list [1,2,3].
13+
ListNode head = new ListNode(1);
14+
head.next = new ListNode(2);
15+
head.next.next = new ListNode(3);
16+
Solution solution = new Solution(head);
17+
18+
// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
19+
solution.getRandom();
20+
```
21+
22+
###Solution
23+
* Method 1: Use axtra space to get O(1).
24+
```Java
25+
/**
26+
* Definition for singly-linked list.
27+
* public class ListNode {
28+
* int val;
29+
* ListNode next;
30+
* ListNode(int x) { val = x; }
31+
* }
32+
*/
33+
classSolution {
34+
privateRandom random;
35+
privateHashMap<Integer,Integer> map;
36+
/** @param head The linked list's head.
37+
Note that the head is guaranteed to be not null, so it contains at least one node.*/
38+
publicSolution(ListNodehead) {
39+
this.map=newHashMap<>();
40+
this.random=newRandom();
41+
ListNode cur= head;
42+
int count=0;
43+
while(cur!=null){
44+
map.put(count++, cur.val);
45+
cur= cur.next;
46+
}
47+
}
48+
49+
/** Returns a random node's value.*/
50+
publicintgetRandom() {
51+
int rand= random.nextInt(map.size());
52+
return map.get(rand);
53+
}
54+
}
55+
56+
/**
57+
* Your Solution object will be instantiated and called as such:
58+
* Solution obj = new Solution(head);
59+
* int param_1 = obj.getRandom();
60+
*/
61+
```
62+
63+
*Method2:ReservoirSampling
64+
```Java
65+
/**
66+
* Definition for singly-linked list.
67+
* public class ListNode {
68+
* int val;
69+
* ListNode next;
70+
* ListNode(int x) { val = x; }
71+
* }
72+
*/
73+
classSolution {
74+
privateListNode head;
75+
privateRandom random;
76+
/** @param head The linked list's head.
77+
Note that the head is guaranteed to be not null, so it contains at least one node.*/
78+
publicSolution(ListNodehead) {
79+
this.head= head;
80+
this.random=newRandom();
81+
}
82+
83+
/** Returns a random node's value.*/
84+
publicintgetRandom() {
85+
ListNode cur= head.next;
86+
int count=1;
87+
ListNode hold= head;
88+
while(cur!=null){
89+
count++;
90+
int rand= random.nextInt(count)+1;
91+
if(rand== count) hold= cur;
92+
cur= cur.next;
93+
}
94+
return hold.val;
95+
}
96+
}
97+
98+
/**
99+
* Your Solution object will be instantiated and called as such:
100+
* Solution obj = new Solution(head);
101+
* int param_1 = obj.getRandom();
102+
*/
103+
```

‎leetcode/458. Poor Pigs.md

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
##458. Poor Pigs
2+
3+
###Question
4+
There are 1000 buckets, one and only one of them is poisonous, while the rest are filled with water. They all look identical. If a pig drinks the poison it will die within 15 minutes. What is the minimum amount of pigs you need to figure out which bucket is poisonous within one hour?
5+
6+
Answer this question, and write an algorithm for the general case.
7+
8+
General case:
9+
10+
If there are n buckets and a pig drinking poison will die within m minutes, how many pigs (x) you need to figure out the poisonous bucket within p minutes? There is exactly one bucket with poison.
11+
12+
Note:
13+
1. A pig can be allowed to drink simultaneously on as many buckets as one would like, and the feeding takes no time.
14+
2. After a pig has instantly finished drinking buckets, there has to be a cool down time of m minutes. During this time, only observation is allowed and no feedings at all.
15+
3. Any given bucket can be sampled an infinite number of times (by an unlimited number of pigs).
16+
17+
18+
###Solutions
19+
* Method 1: Information Theory
20+
* For a single pig(bit), we can figure out how many states can be representated.
21+
* Example: minutesToTest 60 mins, minutesToDie 15mins
22+
* states to resent die:[15, 30, 45, 60] + live = 5
23+
* The question changed to: how many bits required to resent the value of buckets.
24+
```Java
25+
classSolution {
26+
publicintpoorPigs(intbuckets,intminutesToDie,intminutesToTest) {
27+
//how many states can be represented by a pig within the test.
28+
int statesToPresent= minutesToTest/ minutesToDie+1;
29+
return (int)Math.ceil(Math.log(buckets)/Math.log(statesToPresent));
30+
}
31+
}
32+
```
33+
34+
###Reference
35+
1. [leetcode458.PoorPigs 可怜的猪+ 猪试毒需要最少的数量+ 发现规律](https://blog.csdn.net/JackZhang_123/article/details/78775716)
Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
#635. Design Log Storage System
2+
3+
###Question
4+
You are given several logs that each log contains a unique id and timestamp. Timestamp is a string that has the following format: Year:Month:Day:Hour:Minute:Second, for example, 2017:01:01:23:59:59. All domains are zero-padded decimal numbers.
5+
6+
Design a log storage system to implement the following functions:
7+
8+
void Put(int id, string timestamp): Given a log's unique id and timestamp, store the log in your storage system.
9+
10+
int[] Retrieve(String start, String end, String granularity): Return the id of logs whose timestamps are within the range from start to end. Start and end all have the same format as timestamp. However, granularity means the time level for consideration. For example, start = "2017:01:01:23:59:59", end = "2017:01:02:23:59:59", granularity = "Day", it means that we need to find the logs within the range from Jan. 1st 2017 to Jan. 2nd 2017.
11+
12+
```
13+
Example 1:
14+
15+
put(1, "2017:01:01:23:59:59");
16+
put(2, "2017:01:01:22:59:59");
17+
put(3, "2016:01:01:00:00:00");
18+
retrieve("2016:01:01:01:01:01","2017:01:01:23:00:00","Year"); // return [1,2,3], because you need to return all logs within 2016 and 2017.
19+
retrieve("2016:01:01:01:01:01","2017:01:01:23:00:00","Hour"); // return [1,2], because you need to return all logs start from 2016:01:01:01 to 2017:01:01:23, where log 3 is left outside the range.
20+
```
21+
22+
Note:
23+
1. There will be at most 300 operations of Put or Retrieve.
24+
2. Year ranges from[2000,2017]. Hour ranges from[00,23].
25+
3. Output for Retrieve has no order required.
26+
27+
28+
###Solutions
29+
* Method 1: Map
30+
```Java
31+
classLogSystem {
32+
privateMap<String,Integer> map;
33+
privatestaticfinalMap<String,Integer> g;
34+
privatestaticfinalString token="00";
35+
static{
36+
g=newHashMap<>();
37+
g.put("Year",4);
38+
g.put("Month",7);
39+
g.put("Day",10);
40+
g.put("Hour",13);
41+
g.put("Minute",16);
42+
g.put("Second",19);
43+
}
44+
publicLogSystem() {
45+
this.map=newHashMap<>();
46+
}
47+
48+
publicvoidput(intid,Stringtimestamp) {
49+
map.put(timestamp, id);
50+
}
51+
52+
publicList<Integer>retrieve(Strings,Stringe,Stringgra) {
53+
int index= g.get(gra);
54+
String ssub= s.substring(0, index);
55+
String esub= e.substring(0, index);
56+
List<Integer> result=newArrayList<>();
57+
for(String k: map.keySet()){
58+
String ksub= k.substring(0, index);
59+
if(ksub.compareTo(ssub)>=0&& ksub.compareTo(esub)<=0)
60+
result.add(map.get(k));
61+
}
62+
return result;
63+
}
64+
}
65+
66+
/**
67+
* Your LogSystem object will be instantiated and called as such:
68+
* LogSystem obj = new LogSystem();
69+
* obj.put(id,timestamp);
70+
* List<Integer> param_2 = obj.retrieve(s,e,gra);
71+
*/
72+
```

0 commit comments

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