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

Commit435e662

Browse files
committed
find frequency
1 parentf710a07 commit435e662

File tree

3 files changed

+146
-3
lines changed

3 files changed

+146
-3
lines changed

‎algorithm/dp/MinAdjustmentCost_Class.java

Lines changed: 8 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -10,7 +10,7 @@ public static void main(String[] strs) {
1010
A.add(2);
1111
A.add(3);
1212

13-
System.out.println(MinAdjustmentCost(A,1));
13+
System.out.println(MinAdjustmentCost1(A,1));
1414
}
1515

1616
/**
@@ -23,7 +23,12 @@ public static int MinAdjustmentCost1(ArrayList<Integer> A, int target) {
2323
return0;
2424
}
2525

26-
returnrec(A,newArrayList<Integer>(A),target,0);
26+
ArrayList<Integer>B =newArrayList<Integer>();
27+
for (inti =0;i <A.size();i++) {
28+
B.add(0);
29+
}
30+
31+
returnrec(A,B,target,0);
2732
}
2833

2934
/*
@@ -53,7 +58,7 @@ public static int rec(ArrayList<Integer> A, ArrayList<Integer> B, int target, in
5358
min =Math.min(min,dif);
5459

5560
// 回溯
56-
B.set(index,A.get(index));
61+
//B.set(index, A.get(index));
5762
}
5863

5964
returnmin;
Lines changed: 107 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,107 @@
1+
packageAlgorithms.algorithm.interviews.pocketGem;
2+
3+
importjava.util.ArrayList;
4+
importjava.util.Collections;
5+
importjava.util.Comparator;
6+
importjava.util.HashMap;
7+
importjava.util.HashSet;
8+
importjava.util.LinkedList;
9+
importjava.util.List;
10+
importjava.util.Map.Entry;
11+
importjava.util.PriorityQueue;
12+
importjava.util.Set;
13+
14+
/*
15+
* Input: int[] A = {1, 1, 2, 3, 4, 5, 2}; k = 3
16+
* return the highest frequency numbers.
17+
* return: [1, 2, 3] or [1, 2, 4] or [1, 2, 5]
18+
* */
19+
20+
publicclassFindKthFrequency {
21+
publicstaticvoidmain(String[]strs) {
22+
int[]A = {1,1,2,3,3,3,4,4,4,4,4,5,7,2};
23+
System.out.println(findKthFrenquency(A,3).toString());
24+
}
25+
26+
/*
27+
* Solution 1:
28+
* 对HashMap Sort.
29+
* Complexity: O(NLogN)
30+
* */
31+
publicstaticSet<Integer>findKthFrenquency1(int[]input,intk) {
32+
HashSet<Integer>set =newHashSet<Integer>();
33+
HashMap<Integer,Integer>map =newHashMap<Integer,Integer>();
34+
for (intnum:input) {
35+
if (map.containsKey(num)) {
36+
map.put(num,map.get(num) +1);
37+
}else {
38+
map.put(num,1);
39+
}
40+
}
41+
42+
ArrayList<Entry<Integer,Integer>>list =newArrayList<Entry<Integer,Integer>>(map.entrySet());
43+
44+
Collections.sort(list,newComparator<Entry<Integer,Integer>>() {
45+
publicintcompare(Entry<Integer,Integer>o1,Entry<Integer,Integer>o2) {
46+
returno2.getValue() -o1.getValue();
47+
}
48+
});
49+
50+
for (inti =0;i <k;i++) {
51+
set.add(list.get(i).getKey());
52+
}
53+
54+
returnset;
55+
}
56+
57+
/*
58+
* Solution 2:
59+
* Use TreeMap.
60+
* */
61+
publicstaticSet<Integer>findKthFrenquency2(int[]input,intk) {
62+
HashSet<Integer>set =newHashSet<Integer>();
63+
64+
returnset;
65+
}
66+
67+
/*
68+
* Solution 3:
69+
* Use The priority queue.
70+
* */
71+
publicstaticList<Integer>findKthFrenquency(int[]input,intk) {
72+
LinkedList<Integer>list =newLinkedList<Integer>();
73+
74+
HashMap<Integer,Integer>map =newHashMap<Integer,Integer>();
75+
for (intnum:input) {
76+
if (map.containsKey(num)) {
77+
map.put(num,map.get(num) +1);
78+
}else {
79+
map.put(num,1);
80+
}
81+
}
82+
83+
PriorityQueue<Entry<Integer,Integer>>q =newPriorityQueue<Entry<Integer,Integer>>(k +1,newComparator<Entry<Integer,Integer>>(){
84+
publicintcompare(Entry<Integer,Integer>o1,Entry<Integer,Integer>o2) {
85+
returno1.getValue() -o2.getValue();
86+
}
87+
});
88+
89+
for (Entry<Integer,Integer>entry:map.entrySet()) {
90+
if (q.size() ==k +1) {
91+
// Delete the smallest element from the queue.
92+
q.poll();
93+
}
94+
q.offer(entry);
95+
}
96+
97+
// delete one small element
98+
q.poll();
99+
100+
while (!q.isEmpty()) {
101+
Entry<Integer,Integer>entry =q.poll();
102+
list.addFirst(entry.getKey());
103+
}
104+
105+
returnlist;
106+
}
107+
}

‎string/StrStr.java

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,10 @@
11
packageAlgorithms.string;
22

33
publicclassStrStr {
4+
publicstaticvoidmain(String[]strs) {
5+
System.out.println(findPattern("ppa","pp"));
6+
}
7+
48
publicStringstrStr(Stringhaystack,Stringneedle) {
59
if (haystack ==null ||needle ==null) {
610
returnnull;
@@ -30,4 +34,31 @@ public String strStr(String haystack, String needle) {
3034
// didn't find the needle.
3135
returnnull;
3236
}
37+
38+
publicstaticintfindPattern(Stringbase,Stringpattern) {
39+
if (base ==null ||pattern ==null) {
40+
return -1;
41+
}
42+
43+
intlen1 =base.length();
44+
intlen2 =pattern.length();
45+
46+
for (inti =0;i <=len1 -len2;i++) {
47+
intj =0;
48+
for (;j <len2;j++) {
49+
if (base.charAt(i +j) !=pattern.charAt(j)) {
50+
break;
51+
}
52+
53+
54+
if (j ==len2 -1) {
55+
returni;
56+
}
57+
}
58+
59+
}
60+
61+
// did not find pattern.
62+
return -1;
63+
}
3364
}

0 commit comments

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