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

Commita0f8a9d

Browse files
length of increasing subsequence using binary search
1 parente07e906 commita0f8a9d

File tree

2 files changed

+140
-100
lines changed

2 files changed

+140
-100
lines changed

‎Common/src/utils/CommonUtils.java

Lines changed: 107 additions & 99 deletions
Original file line numberDiff line numberDiff line change
@@ -8,53 +8,61 @@
88

99
publicclassCommonUtils {
1010

11-
privatestaticfinalintDEFAULT_TREE_SIZE =10;
12-
privatestaticfinalintDEFAULT_UPPER_BOUND =100;
13-
14-
publicstaticvoidprint(Stringmessage) {
15-
System.out.print(message);
16-
}
17-
18-
publicstaticvoidprint(intnum) {
19-
System.out.print(num);
20-
}
21-
22-
publicstaticvoidprintln(Stringmessage) {
23-
System.out.println(message);
24-
}
25-
26-
publicstaticvoidprintln(intnum) {
27-
System.out.println(num);
28-
}
29-
30-
publicstaticvoidprintln() {
31-
System.out.println();
32-
}
33-
34-
//overloaded method to take only one argument
35-
publicstaticList<Integer>randomIntArrayGenerator(intsize) {
36-
returnCommonUtils.randomIntArrayGenerator(size,DEFAULT_UPPER_BOUND);
37-
}
38-
39-
//overloaded method to take no argument
40-
publicstaticList<Integer>randomIntArrayGenerator() {
41-
returnCommonUtils.randomIntArrayGenerator(CommonUtils.DEFAULT_TREE_SIZE,DEFAULT_UPPER_BOUND);
42-
}
43-
44-
//this one has two other overloaded methods as above
45-
publicstaticList<Integer>randomIntArrayGenerator(intsize,intupperBound) {
46-
List<Integer>result =newArrayList<Integer>();
47-
Randomrandom =newRandom();
48-
for (inti =0;i <size;i++) {
49-
intrandomInt =random.nextInt(upperBound);
50-
result.add(randomInt);
51-
print(String.valueOf(randomInt) +" ");
52-
}
53-
println();
54-
returnresult;
55-
}
56-
57-
//this one has two other overloaded methods as above
11+
privatestaticfinalintDEFAULT_TREE_SIZE =10;
12+
privatestaticfinalintDEFAULT_UPPER_BOUND =100;
13+
14+
publicstaticvoidprintArray(int[]nums) {
15+
for(inti :nums){
16+
System.out.print(i +", ");
17+
}
18+
System.out.println();
19+
}
20+
21+
publicstaticvoidprint(Stringmessage) {
22+
System.out.print(message);
23+
}
24+
25+
publicstaticvoidprint(intnum) {
26+
System.out.print(num);
27+
}
28+
29+
publicstaticvoidprintln(Stringmessage) {
30+
System.out.println(message);
31+
}
32+
33+
publicstaticvoidprintln(intnum) {
34+
System.out.println(num);
35+
}
36+
37+
publicstaticvoidprintln() {
38+
System.out.println();
39+
}
40+
41+
// overloaded method to take only one argument
42+
publicstaticList<Integer>randomIntArrayGenerator(intsize) {
43+
returnCommonUtils.randomIntArrayGenerator(size,DEFAULT_UPPER_BOUND);
44+
}
45+
46+
// overloaded method to take no argument
47+
publicstaticList<Integer>randomIntArrayGenerator() {
48+
returnCommonUtils.randomIntArrayGenerator(CommonUtils.DEFAULT_TREE_SIZE,
49+
DEFAULT_UPPER_BOUND);
50+
}
51+
52+
// this one has two other overloaded methods as above
53+
publicstaticList<Integer>randomIntArrayGenerator(intsize,intupperBound) {
54+
List<Integer>result =newArrayList<Integer>();
55+
Randomrandom =newRandom();
56+
for (inti =0;i <size;i++) {
57+
intrandomInt =random.nextInt(upperBound);
58+
result.add(randomInt);
59+
print(String.valueOf(randomInt) +" ");
60+
}
61+
println();
62+
returnresult;
63+
}
64+
65+
// this one has two other overloaded methods as above
5866
publicstaticList<Integer>uniqueIntArrayGenerator(intsize) {
5967
List<Integer>result =newArrayList<Integer>();
6068
for (inti =0;i <size;i++) {
@@ -64,59 +72,59 @@ public static List<Integer> uniqueIntArrayGenerator(int size) {
6472
returnresult;
6573
}
6674

67-
//@Notes(context = "I'm assuing only classes in this PACKAGE will call the following two methods, so just leave the modifier as default, i.e. no public, private, or protected.")
68-
public
69-
staticvoidprintWhitespaces(intcount) {
70-
for (inti =0;i <count;i++)
71-
System.out.print(" ");
72-
}
73-
74-
publicstatic <T>booleanisAllElementsNull(List<T>list) {
75-
for (Objectobject :list) {
76-
if (object !=null)
77-
returnfalse;
78-
}
79-
80-
returntrue;
81-
}
82-
83-
/**
84-
* If you want to print the reversed list out, you need to return the
85-
* reversed list's head,which was the end node of the original node. using
86-
* the following function.
87-
*/
88-
publicstaticListNodereverseList(ListNodehead) {
89-
if (head ==null ||head.next ==null) {
90-
returnhead;
91-
}
92-
ListNodeprevious,current,next;
93-
previous=head;
94-
current=head.next;
95-
while (current !=null) {
96-
next =current.next;
97-
current.next =previous;
98-
previous =current;
99-
current =next;
100-
}
101-
head.next =null;
102-
returnprevious;
103-
}
104-
105-
publicstaticvoidprintList(finalListNodehead) {
106-
ListNodetemp =head;
107-
System.out.println("--------------------------------------------");
108-
while (temp !=null) {
109-
System.out.print(temp.val);
110-
temp=temp.next;
111-
if(temp !=null)System.out.print("->");
112-
}
113-
System.out.println();
114-
}
115-
116-
publicstaticvoidprintMatrix(int[][]matrix) {
75+
//@Notes(context =
76+
// "I'm assuing only classes in this PACKAGE will call the following two methods, so just leave the modifier as default, i.e. nopublic, private, or protected.")
77+
publicstaticvoidprintWhitespaces(intcount) {
78+
for (inti =0;i <count;i++)
79+
System.out.print(" ");
80+
}
81+
82+
publicstatic <T>booleanisAllElementsNull(List<T>list) {
83+
for (Objectobject :list) {
84+
if (object !=null)
85+
returnfalse;
86+
}
87+
88+
returntrue;
89+
}
90+
91+
/**
92+
* If you want to print the reversed list out, you need to return the reversed list's head,
93+
*which was the end node of the original node. using the following function.
94+
*/
95+
publicstaticListNodereverseList(ListNodehead) {
96+
if (head ==null ||head.next ==null) {
97+
returnhead;
98+
}
99+
ListNodeprevious,current,next;
100+
previous =head;
101+
current=head.next;
102+
while (current!=null) {
103+
next =current.next;
104+
current.next =previous;
105+
previous =current;
106+
current =next;
107+
}
108+
head.next =null;
109+
returnprevious;
110+
}
111+
112+
publicstaticvoidprintList(finalListNodehead) {
113+
ListNodetemp =head;
114+
System.out.println("--------------------------------------------");
115+
while (temp !=null) {
116+
System.out.print(temp.val);
117+
temp =temp.next;
118+
if (temp!=null)
119+
System.out.print("->");
120+
}
121+
System.out.println();
122+
}
123+
124+
publicstaticvoidprintMatrix(int[][]matrix) {
117125
System.out.println("Matrix is: ");
118-
for(inti =0;i <matrix.length;i++){
119-
for(intj =0;j <matrix[0].length;j++){
126+
for(inti =0;i <matrix.length;i++){
127+
for(intj =0;j <matrix[0].length;j++){
120128
System.out.print(matrix[i][j] +"\t");
121129
}
122130
System.out.println();

‎MEDIUM/src/medium/LengthIncreasingSubsequence.java

Lines changed: 33 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,7 @@
11
packagemedium;
22

3+
importjava.util.Arrays;
4+
35
importutils.CommonUtils;
46

57
/**300. Longest Increasing Subsequence QuestionEditorial Solution My Submissions
@@ -19,13 +21,43 @@ Your algorithm should run in O(n2) complexity.
1921
Credits:
2022
Special thanks to @pbrother for adding this problem and creating all test cases.*/
2123
publicclassLengthIncreasingSubsequence {
24+
25+
publicintlengthOfLIS_using_binary_search_from_discuss(int[]nums) {
26+
/**Java doc for this Arrays.binarySearch method:
27+
* int java.util.Arrays.binarySearch(int[] a, int fromIndex, int toIndex, int key)
28+
29+
Searches a range of the specified array of ints for the specified value using the binary search algorithm. The range must be sorted (as by the sort(int [], int, int) method) prior to making this call. If it is not sorted, the results are undefined. If the range contains multiple elements with the specified value, there is no guarantee which one will be found.
30+
31+
Parameters:
32+
a the array to be searched
33+
fromIndex the index of the first element (inclusive) to be searched
34+
toIndex the index of the last element (exclusive) to be searched
35+
key the value to be searched for
36+
37+
Returns:
38+
index of the search key, if it is contained in the array within the specified range; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the array: the index of the first element in the range greater than the key, or toIndex if all elements in the range are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.*/
39+
int[]dp =newint[nums.length];
40+
intlen =0;
41+
for(intx :nums){
42+
inti =Arrays.binarySearch(dp,0,len,x);
43+
System.out.println("i = " +i +"\tx = " +x);
44+
if(i <0)i = -(i+1);
45+
dp[i] =x;
46+
if(i ==len)len++;
47+
}
48+
CommonUtils.printArray(nums);
49+
CommonUtils.printArray(dp);
50+
returnlen;
51+
}
52+
2253
publicstaticvoidmain(String...strings){
2354
LengthIncreasingSubsequencetest =newLengthIncreasingSubsequence();
2455
int[]nums =newint[]{10,9,2,5,3,7,101,18};
2556
// int[] nums = new int[]{10,9,2,5,3,4};
2657
// int[] nums = new int[]{1,3,6,7,9,4,10,5,6};
2758
// int[] nums = new int[]{18,55,66,2,3,54};
28-
System.out.println(test.lengthOfLIS(nums));
59+
// System.out.println(test.lengthOfLIS(nums));
60+
System.out.println(test.lengthOfLIS_using_binary_search_from_discuss(nums));
2961
}
3062

3163
/**This is the closest I got, passed all normal cases, made it to 22/23 test cases, but got TLE, as I expected,

0 commit comments

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