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

Commit231521b

Browse files
committed
[Function add]
1. Add leetcode solutions.
1 parent2d86af3 commit231521b

5 files changed

+436
-0
lines changed

‎leetcode/149. Max Points on a Line.md

Lines changed: 113 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,113 @@
1+
##149. Max Points on a Line
2+
3+
###Question
4+
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
5+
6+
```
7+
Example 1:
8+
9+
Input: [[1,1],[2,2],[3,3]]
10+
Output: 3
11+
Explanation:
12+
^
13+
|
14+
| o
15+
| o
16+
| o
17+
+------------->
18+
0 1 2 3 4
19+
20+
Example 2:
21+
22+
Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
23+
Output: 4
24+
Explanation:
25+
^
26+
|
27+
| o
28+
| o o
29+
| o
30+
| o o
31+
+------------------->
32+
0 1 2 3 4 5 6
33+
```
34+
35+
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.
36+
37+
38+
###Solutions:
39+
* Method 1: I first used the double to calculate the slope but cause precision error. O(n^3) cannot AC.
40+
```Java
41+
classSolution {
42+
publicintmaxPoints(int[][]points) {
43+
int len= points.length;
44+
if(len<=2)return len;
45+
int res=0;
46+
for(int i=0; i< len; i++){
47+
for(int j= i+1; j< len; j++){
48+
int temp=2;
49+
double x1= (double)points[i][0];
50+
double x2= (double)points[j][0];
51+
if(x1!= x2){
52+
double y1= (double)points[i][1];
53+
double y2= (double)points[j][1];
54+
double s= (y2- y1)/ (x2- x1);
55+
double b= y1- s* x1;
56+
for(int k=0; k< len; k++){
57+
if(k== i|| k== j)continue;
58+
double x= (double)points[k][0];
59+
double y= (double)points[k][1];
60+
if(y== x* s+ b) temp++;
61+
}
62+
}else{
63+
for(int k=0; k< len; k++){
64+
if(k== i|| k== j)continue;
65+
double x= (double)points[k][0];
66+
if(x== x1) temp++;
67+
}
68+
}
69+
res=Math.max(res, temp);
70+
}
71+
}
72+
return res;
73+
}
74+
}
75+
```
76+
77+
*Method2:HashMap to save the slope(use string)AC
78+
```Java
79+
classSolution {
80+
publicintmaxPoints(int[][]points) {
81+
int len= points.length;
82+
if(len<=2)return len;
83+
int res=0;
84+
for(int i=0; i< len; i++){
85+
for(int j= i+1; j< len; j++){
86+
int temp=2;
87+
double x1= (double)points[i][0];
88+
double x2= (double)points[j][0];
89+
if(x1!= x2){
90+
double y1= (double)points[i][1];
91+
double y2= (double)points[j][1];
92+
double s= (y2- y1)/ (x2- x1);
93+
double b= y1- s* x1;
94+
for(int k=0; k< len; k++){
95+
if(k== i|| k== j)continue;
96+
double x= (double)points[k][0];
97+
double y= (double)points[k][1];
98+
if(y== x* s+ b) temp++;
99+
}
100+
}else{
101+
for(int k=0; k< len; k++){
102+
if(k== i|| k== j)continue;
103+
double x= (double)points[k][0];
104+
if(x== x1) temp++;
105+
}
106+
}
107+
res=Math.max(res, temp);
108+
}
109+
}
110+
return res;
111+
}
112+
}
113+
```

‎leetcode/443. String Compression.md

Lines changed: 90 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,90 @@
1+
##443. String Compression
2+
3+
###Question
4+
Given an array of characters, compress it in-place.
5+
6+
The length after compression must always be smaller than or equal to the original array.
7+
8+
Every element of the array should be a character (not int) of length 1.
9+
10+
After you are done modifying the input array in-place, return the new length of the array.
11+
12+
13+
Follow up:
14+
Could you solve it using only O(1) extra space?
15+
16+
```
17+
Example 1:
18+
19+
Input:
20+
["a","a","b","b","c","c","c"]
21+
22+
Output:
23+
Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]
24+
25+
Explanation:
26+
"aa" is replaced by "a2". "bb" is replaced by "b2". "ccc" is replaced by "c3".
27+
28+
29+
30+
Example 2:
31+
32+
Input:
33+
["a"]
34+
35+
Output:
36+
Return 1, and the first 1 characters of the input array should be: ["a"]
37+
38+
Explanation:
39+
Nothing is replaced.
40+
41+
42+
43+
Example 3:
44+
45+
Input:
46+
["a","b","b","b","b","b","b","b","b","b","b","b","b"]
47+
48+
Output:
49+
Return 4, and the first 4 characters of the input array should be: ["a","b","1","2"].
50+
51+
Explanation:
52+
Since the character "a" does not repeat, it is not compressed. "bbbbbbbbbbbb" is replaced by "b12".
53+
Notice each digit has it's own entry in the array.
54+
```
55+
56+
Note:
57+
1. All characters have an ASCII value in[35, 126].
58+
2. 1 <= len(chars) <= 1000.
59+
60+
61+
62+
63+
64+
###Solutions:
65+
* Method 1: 9m46s two pointers
66+
```Java
67+
classSolution {
68+
publicintcompress(char[]chars) {
69+
int count=0;
70+
int read=0;
71+
while(read< chars.length){
72+
char c= chars[read];
73+
int check= read;
74+
while(check< chars.length&& chars[check]== c){
75+
check++;
76+
}
77+
// c appears check - read times.
78+
chars[count++]= c;
79+
if(check- read>1){
80+
String num=""+ (check- read);
81+
for(int i=0; i< num.length(); i++){
82+
chars[count++]= num.charAt(i);
83+
}
84+
}
85+
read= check;
86+
}
87+
return count;
88+
}
89+
}
90+
```
Lines changed: 94 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,94 @@
1+
##528. Random Pick with Weight
2+
3+
###Question
4+
Given an array w of positive integers, where w[i] describes the weight of index i, write a function pickIndex which randomly picks an index in proportion to its weight.
5+
6+
Note:
7+
* 1 <= w.length <= 10000
8+
* 1 <= w[i] <= 10^5
9+
* pickIndex will be called at most 10000 times.
10+
11+
```
12+
Example 1:
13+
14+
Input:
15+
["Solution","pickIndex"]
16+
[[[1]],[]]
17+
Output: [null,0]
18+
19+
Example 2:
20+
21+
Input:
22+
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
23+
[[[1,3]],[],[],[],[],[]]
24+
Output: [null,0,1,1,1,0]
25+
```
26+
27+
Explanation of Input Syntax:
28+
29+
The input is two lists: the subroutines called and their arguments. Solution's constructor has one argument, the array w. pickIndex has no arguments. Arguments are always wrapped with a list, even if there aren't any.
30+
31+
32+
###Solutions:
33+
* Method 1: O(n) for each pick
34+
```
35+
class Solution {
36+
private static Random random = new Random();
37+
private int[] w;
38+
private int sum;
39+
public Solution(int[] w) {
40+
this.w = w;
41+
for(int num : w) this.sum += num;
42+
}
43+
44+
public int pickIndex() {
45+
int rand = random.nextInt(sum) + 1;
46+
int temp = 0;
47+
for(int i = 0; i < w.length; i++){
48+
if(temp + w[i] >= rand) return i;
49+
temp += w[i];
50+
}
51+
return w.length - 1;
52+
}
53+
}
54+
55+
/**
56+
* Your Solution object will be instantiated and called as such:
57+
* Solution obj = new Solution(w);
58+
* int param_1 = obj.pickIndex();
59+
*/
60+
```
61+
62+
* Method 2: Binary search O(lgN)
63+
* we take the sum up to all indexes.
64+
* we use binary search to find the first number bigger(or equal to) the random value.
65+
```Java
66+
class Solution {
67+
private static Random random = new Random();
68+
private int[] w;
69+
public Solution(int[] w) {
70+
this.w = w;
71+
for(int i = 1; i < w.length; i++){
72+
w[i] += w[i - 1];
73+
}
74+
}
75+
76+
public int pickIndex() {
77+
int rand = random.nextInt(w[w.length - 1]) + 1;
78+
int left = 0, right = w.length - 1;
79+
while(left < right){
80+
int mid = left + (right - left) / 2;
81+
if(w[mid] == rand) return mid;
82+
else if(w[mid] < rand) left = mid + 1;
83+
else right = mid;
84+
}
85+
return left;
86+
}
87+
}
88+
89+
/**
90+
* Your Solution object will be instantiated and called as such:
91+
* Solution obj = new Solution(w);
92+
* int param_1 = obj.pickIndex();
93+
*/
94+
```

‎leetcode/57. Insert Interval.md

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -107,3 +107,38 @@ class Solution {
107107
}
108108
}
109109
```
110+
111+
###Third Time
112+
* Method 1: Array + Sort
113+
```Java
114+
class Solution {
115+
public int[][] insert(int[][] intervals, int[] newInterval) {
116+
int len = intervals.length;
117+
int[] starts = new int[len + 1];
118+
int[] ends = new int[len + 1];
119+
// Currently the starts and ends are sorted and non-overlap
120+
for(int i = 0; i < len; i++){
121+
starts[i] = intervals[i][0];
122+
ends[i] = intervals[i][1];
123+
}
124+
starts[len] = newInterval[0];
125+
ends[len] = newInterval[1];
126+
Arrays.sort(starts);
127+
Arrays.sort(ends);
128+
List<int[]> temp = new ArrayList<>();
129+
int start = starts[0];
130+
for(int i = 1; i <= len; i++){
131+
if(starts[i] > ends[i - 1]){
132+
temp.add(new int[]{start, ends[i - 1]});
133+
start = starts[i];
134+
}
135+
}
136+
temp.add(new int[]{start, ends[len]});
137+
int[][] res = new int[temp.size()][2];
138+
for(int i = 0; i < temp.size(); i++){
139+
res[i] = temp.get(i);
140+
}
141+
return res;
142+
}
143+
}
144+
```

0 commit comments

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