Skip to content

Commit 85a501f

Browse files
author
Botao Xiao
committed
[Function add]: 1. Add leetcode solutions with amazon tag.
1 parent b9d51c7 commit 85a501f

6 files changed

+314
-1
lines changed

‎leetcode/169. Majority Element.md

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -120,3 +120,25 @@ class Solution {
120120
}
121121
}
122122
```
123+
124+
### Fourth time
125+
* Method 1: Moore's Algorithm
126+
```Java
127+
class Solution {
128+
public int majorityElement(int[] nums) {
129+
int res = nums[0];
130+
int count = 1;
131+
for(int i = 1; i < nums.length; i++){
132+
if(nums[i] == res) count++;
133+
else{
134+
count--;
135+
if(count == 0){
136+
res = nums[i];
137+
count = 1;
138+
}
139+
}
140+
}
141+
return res;
142+
}
143+
}
144+
```

‎leetcode/380. Insert Delete GetRandom O(1).md

Lines changed: 87 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,87 @@
1+
## 380. Insert Delete GetRandom O(1)
2+
3+
### Question
4+
Design a data structure that supports all following operations in average O(1) time.
5+
6+
insert(val): Inserts an item val to the set if not already present.
7+
remove(val): Removes an item val from the set if present.
8+
getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.
9+
10+
```
11+
Example:
12+
13+
// Init an empty set.
14+
RandomizedSet randomSet = new RandomizedSet();
15+
16+
// Inserts 1 to the set. Returns true as 1 was inserted successfully.
17+
randomSet.insert(1);
18+
19+
// Returns false as 2 does not exist in the set.
20+
randomSet.remove(2);
21+
22+
// Inserts 2 to the set, returns true. Set now contains [1,2].
23+
randomSet.insert(2);
24+
25+
// getRandom should return either 1 or 2 randomly.
26+
randomSet.getRandom();
27+
28+
// Removes 1 from the set, returns true. Set now contains [2].
29+
randomSet.remove(1);
30+
31+
// 2 was already in the set, so return false.
32+
randomSet.insert(2);
33+
34+
// Since 2 is the only number in the set, getRandom always return 2.
35+
randomSet.getRandom();
36+
```
37+
38+
### Solution
39+
* Method 1: HashMap + ArrayList
40+
```Java
41+
class RandomizedSet {
42+
private Map<Integer, Integer> map;
43+
private List<Integer> nums;
44+
private Random random;
45+
/** Initialize your data structure here. */
46+
public RandomizedSet() {
47+
this.map = new HashMap<>();
48+
this.nums = new ArrayList<>();
49+
this.random = new Random();
50+
}
51+
52+
/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
53+
public boolean insert(int val) {
54+
if(map.containsKey(val)) return false;
55+
nums.add(val);
56+
map.put(val, nums.size() - 1);
57+
return true;
58+
}
59+
60+
/** Removes a value from the set. Returns true if the set contained the specified element. */
61+
public boolean remove(int val) {
62+
if(!map.containsKey(val)) return false;
63+
int index = map.get(val);
64+
if(index != nums.size() - 1){
65+
int last = nums.get(nums.size() - 1);
66+
nums.set(index, last);
67+
map.put(last, index);
68+
}
69+
nums.remove(nums.size() - 1);
70+
map.remove(val);
71+
return true;
72+
}
73+
74+
/** Get a random element from the set. */
75+
public int getRandom() {
76+
return this.nums.get(random.nextInt(nums.size()));
77+
}
78+
}
79+
80+
/**
81+
* Your RandomizedSet object will be instantiated and called as such:
82+
* RandomizedSet obj = new RandomizedSet();
83+
* boolean param_1 = obj.insert(val);
84+
* boolean param_2 = obj.remove(val);
85+
* int param_3 = obj.getRandom();
86+
*/
87+
```

‎leetcode/394. Decode String.md

Lines changed: 51 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,7 @@ The encoding rule is: k[encoded_string], where the encoded_string inside the squ
77

88
You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.
99

10-
Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won't be input like 3a or 2[4].
10+
Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won't be input like 3a or 2[4].
1111
```
1212
Example 1:
1313
@@ -93,3 +93,53 @@ class Solution {
9393
}
9494
}
9595
```
96+
97+
### Second Time
98+
* Method 1: Recursion
99+
```Java
100+
class Solution {
101+
private char[] arr;
102+
private int index;
103+
private String s;
104+
public String decodeString(String s) {
105+
this.arr = s.toCharArray();
106+
this.s = s;
107+
return decode(arr);
108+
}
109+
private String decode(char[] arr){
110+
String res = getValue();
111+
if(index < arr.length){
112+
if(arr[index] == ']'){
113+
index++;
114+
return res;
115+
}else{
116+
int mul = getCount();
117+
index++; // remove [
118+
String sub = decode(arr);
119+
for(int i = 0; i < mul; i++){
120+
res += sub;
121+
}
122+
}
123+
}
124+
if(index < arr.length){
125+
res += decode(arr);
126+
}
127+
return res;
128+
}
129+
private int getCount(){
130+
int count = 0;
131+
while(index < arr.length && arr[index] >= '0' && arr[index] <= '9'){
132+
count = count * 10 + arr[index] - '0';
133+
index++;
134+
}
135+
return count == 0 ? 1: count;
136+
}
137+
private String getValue(){
138+
int start = index;
139+
while(index < arr.length && Character.isLetter(arr[index])){
140+
index++;
141+
}
142+
return s.substring(start, index);
143+
}
144+
}
145+
```

‎leetcode/535. Encode and Decode TinyURL.md

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
## 535. Encode and Decode TinyURL
2+
3+
### Question
4+
Note: This is a companion problem to the System Design problem: Design TinyURL.
5+
TinyURL is a URL shortening service where you enter a URL such as https://leetcode.com/problems/design-tinyurl and it returns a short URL such as http://tinyurl.com/4e9iAk.
6+
7+
Design the encode and decode methods for the TinyURL service. There is no restriction on how your encode/decode algorithm should work. You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL.
8+
9+
### Solution
10+
* Method 1: HashMap + hashCode
11+
```Java
12+
public class Codec {
13+
private Map<Integer, String> map = new HashMap<>();
14+
private int index;
15+
// Encodes a URL to a shortened URL.
16+
public String encode(String longUrl) {
17+
int key = longUrl.hashCode();
18+
this.map.put(key, longUrl);
19+
return "http://tinyurl.com/" + longUrl.hashCode();
20+
}
21+
22+
// Decodes a shortened URL to its original URL.
23+
public String decode(String shortUrl) {
24+
return map.get(Integer.parseInt(shortUrl.replace("http://tinyurl.com/", "")));
25+
}
26+
}
27+
28+
// Your Codec object will be instantiated and called as such:
29+
// Codec codec = new Codec();
30+
// codec.decode(codec.encode(url));
31+
```
32+
33+
* Method 2: HashMap + count
34+
```Java
35+
public class Codec {
36+
private Map<Integer, String> map = new HashMap<>();
37+
private int index;
38+
// Encodes a URL to a shortened URL.
39+
public String encode(String longUrl) {
40+
this.map.put(index, longUrl);
41+
return "http://tinyurl.com/" + index++;
42+
}
43+
44+
// Decodes a shortened URL to its original URL.
45+
public String decode(String shortUrl) {
46+
return map.get(Integer.parseInt(shortUrl.replace("http://tinyurl.com/", "")));
47+
}
48+
}
49+
50+
// Your Codec object will be instantiated and called as such:
51+
// Codec codec = new Codec();
52+
// codec.decode(codec.encode(url));
53+
```

‎leetcode/771. Jewels and Stones.md

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
## 771. Jewels and Stones
2+
3+
### Question
4+
You're given strings J representing the types of stones that are jewels, and S representing the stones you have. Each character in S is a type of stone you have. You want to know how many of the stones you have are also jewels.
5+
6+
The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so "a" is considered a different type of stone from "A".
7+
8+
```
9+
Example 1:
10+
11+
Input: J = "aA", S = "aAAbbbb"
12+
Output: 3
13+
Example 2:
14+
15+
Input: J = "z", S = "ZZ"
16+
Output: 0
17+
```
18+
19+
Note:
20+
* S and J will consist of letters and have length at most 50.
21+
* The characters in J are distinct.
22+
23+
### Solution
24+
* Method 1: HashSet
25+
```Java
26+
class Solution {
27+
public int numJewelsInStones(String J, String S) {
28+
Set<Character> set = new HashSet<>();
29+
for(char c : J.toCharArray()){
30+
set.add(c);
31+
}
32+
int res = 0;
33+
for(char c : S.toCharArray()){
34+
if(set.contains(c)) res++;
35+
}
36+
return res;
37+
}
38+
}
39+
```

‎leetcode/856. Score of Parentheses.md

Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
## 856. Score of Parentheses
2+
3+
### Question
4+
Given a balanced parentheses string S, compute the score of the string based on the following rule:
5+
() has score 1
6+
AB has score A + B, where A and B are balanced parentheses strings.
7+
(A) has score 2 * A, where A is a balanced parentheses string.
8+
9+
```
10+
Example 1:
11+
12+
Input: "()"
13+
Output: 1
14+
Example 2:
15+
16+
Input: "(())"
17+
Output: 2
18+
Example 3:
19+
20+
Input: "()()"
21+
Output: 2
22+
Example 4:
23+
24+
Input: "(()(()))"
25+
Output: 6
26+
```
27+
28+
Note:
29+
* S is a balanced parentheses string, containing only ( and ).
30+
* 2 <= S.length <= 50
31+
32+
### Solution
33+
* Method 1: Recursion
34+
```Java
35+
class Solution {
36+
private char[] arr;
37+
private int index;
38+
public int scoreOfParentheses(String S) {
39+
this.arr = S.toCharArray();
40+
if(arr.length == 0) return 0;
41+
return scoreOfParentheses(arr);
42+
}
43+
private int scoreOfParentheses(char[] arr){
44+
int score = 0;
45+
while(index < arr.length && arr[index] == '(' && arr[index + 1] == ')'){
46+
score += 1;
47+
index += 2;
48+
}
49+
if(index < arr.length){
50+
if(arr[index] == ')'){
51+
index++;
52+
return score;
53+
}else{
54+
index++; //remove left bracket
55+
score += 2 * scoreOfParentheses(arr);
56+
}
57+
}
58+
if(index < arr.length) score += scoreOfParentheses(arr);
59+
return score;
60+
}
61+
}
62+
```

0 commit comments

Comments
 (0)