Skip to content

Commit f04889f

Browse files
GeekUniversityGeekUniversity
authored
Merge pull request algorithm001#608 from shironghui0593/master
065-第三周作业提交
2 parents 55af3dd + e87afba commit f04889f

3 files changed

Lines changed: 172 additions & 0 deletions

File tree

‎Week_01/id_65/LeetCode_441_065.java‎

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
package com.imooc.activiti.helloworld;
2+
3+
import java.io.BufferedReader;
4+
import java.io.IOException;
5+
import java.io.InputStreamReader;
6+
7+
/**
8+
* @author shironghui on 2019/4/18.
9+
*/
10+
11+
12+
class Solution14 {
13+
/**
14+
* 让我们按一定规律排列，第一行放1个，第二行放2个，以此类推，
15+
* 问我们有多少行能放满。通过分析题目中的例子可以得知最后一行只有两种情况，放满和没放满。
16+
* 由于是按等差数列排放的，我们可以快速计算出前i行的硬币总数。
17+
* 我们先来看一种O(n)的方法，非常简单粗暴，就是从第一行开始，一行一行的从n中减去，
18+
* 如果此时剩余的硬币没法满足下一行需要的硬币数了，我们之间返回当前行数即可
19+
* @param n
20+
* @return
21+
*/
22+
public int arrangeCoins(int n) {
23+
for(int i=1;i<Integer.MAX_VALUE;i++){
24+
if(n>=0){
25+
n=n-i;
26+
}
27+
else {
28+
return i-2;
29+
}
30+
}
31+
return -1;
32+
}
33+
}
34+
35+
public class TestArrangeCoins {
36+
public static void main(String[] args) throws IOException {
37+
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
38+
String line;
39+
while ((line = in.readLine()) != null) {
40+
int n = Integer.parseInt(line);
41+
42+
int ret = new Solution14().arrangeCoins(n);
43+
44+
String out = String.valueOf(ret);
45+
46+
System.out.print(out);
47+
}
48+
}
49+
}

‎Week_03/id_65/LeetCode_703_065.java‎

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
package com.imooc.activiti.helloworld;
2+
3+
import com.eclipsesource.json.JsonArray;
4+
5+
import java.io.BufferedReader;
6+
import java.io.IOException;
7+
import java.io.InputStreamReader;
8+
import java.util.PriorityQueue;
9+
10+
/**
11+
* @author shironghui on 2019/4/18.
12+
*/
13+
class KthLargest {
14+
int size;
15+
PriorityQueue<Integer> minheap;
16+
public KthLargest(int k, int[] nums) {
17+
minheap = new PriorityQueue<>(k+1);
18+
size = k;
19+
for(int num: nums) {
20+
minheap.offer(num);
21+
if(minheap.size() > k) minheap.poll();
22+
}
23+
}
24+
25+
public int add(int val) {
26+
if(minheap.isEmpty() || minheap.size() < size) minheap.offer(val);
27+
else if(val >= minheap.peek()) {
28+
minheap.offer(val);
29+
}
30+
if(minheap.size() > size) minheap.poll();
31+
return minheap.peek();
32+
}
33+
}
34+
35+
public class TestHeap{
36+
public static void main(String[] args) {
37+
int[] arr={4,5,8,2};
38+
KthLargest kthLargest=new KthLargest(3,arr);
39+
int add1 = kthLargest.add(3);
40+
int add2 = kthLargest.add(5);
41+
System.out.println(add1);
42+
System.out.println(add2);
43+
}
44+
}

‎Week_03/id_65/LeetCode_997_065.java‎

Lines changed: 79 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,79 @@
1+
package com.imooc.activiti.helloworld;
2+
3+
import com.eclipsesource.json.JsonArray;
4+
5+
import java.io.BufferedReader;
6+
import java.io.IOException;
7+
import java.io.InputStreamReader;
8+
9+
/**
10+
* @author shironghui on 2019/4/18.
11+
*/
12+
class SolutionGraph {
13+
public int findJudge(int N, int[][] trust) {
14+
//记录每个人被人相信的次数
15+
int[] outgoing = new int[N+1];
16+
//记录每个人相信别人的次数
17+
int[] incoming = new int[N+1];
18+
for(int i=0; i<trust.length; i++) {
19+
int o = trust[i][0];
20+
int in = trust[i][1];
21+
outgoing[o] += 1;
22+
incoming[in] += 1;
23+
}
24+
for(int i=1; i<N+1; i++) {
25+
//相信i的人N-1个且i相信的人为0
26+
if(incoming[i] == N-1 && outgoing[i] == 0)
27+
return i;
28+
}
29+
return -1;
30+
}
31+
}
32+
33+
public class TestGraph {
34+
public static int[] stringToIntegerArray(String input) {
35+
input = input.trim();
36+
input = input.substring(1, input.length() - 1);
37+
if (input.length() == 0) {
38+
return new int[0];
39+
}
40+
41+
String[] parts = input.split(",");
42+
int[] output = new int[parts.length];
43+
for(int index = 0; index < parts.length; index++) {
44+
String part = parts[index].trim();
45+
output[index] = Integer.parseInt(part);
46+
}
47+
return output;
48+
}
49+
50+
public static int[][] stringToInt2dArray(String input) {
51+
JsonArray jsonArray = JsonArray.readFrom(input);
52+
if (jsonArray.size() == 0) {
53+
return new int[0][0];
54+
}
55+
56+
int[][] arr = new int[jsonArray.size()][];
57+
for (int i = 0; i < arr.length; i++) {
58+
JsonArray cols = jsonArray.get(i).asArray();
59+
arr[i] = stringToIntegerArray(cols.toString());
60+
}
61+
return arr;
62+
}
63+
64+
public static void main(String[] args) throws IOException {
65+
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
66+
String line;
67+
while ((line = in.readLine()) != null) {
68+
int N = Integer.parseInt(line);
69+
line = in.readLine();
70+
int[][] trust = stringToInt2dArray(line);
71+
72+
int ret = new SolutionGraph().findJudge(N, trust);
73+
74+
String out = String.valueOf(ret);
75+
76+
System.out.print(out);
77+
}
78+
}
79+
}

0 commit comments

Comments
 (0)