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

Commit3aa011a

Browse files
author
zhenyu zhang
committed
update Solution 266、416、1492、1539、1640
1 parente59b665 commit3aa011a

File tree

5 files changed

+263
-0
lines changed

5 files changed

+263
-0
lines changed

‎src/com/hadley/_1492.java

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
packagecom.hadley;
2+
3+
/*
4+
2020.12.5
5+
The kth Factor of n
6+
7+
Given two positive integers n and k.
8+
A factor of an integer n is defined as an integer i where n % i == 0.
9+
Consider a list of all factors of n sorted in ascending order, return the kth factor in this list or return -1 if n has less than k factors.
10+
11+
Example 1:
12+
Input: n = 12, k = 3
13+
Output: 3
14+
Explanation: Factors list is [1, 2, 3, 4, 6, 12], the 3rd factor is 3.
15+
16+
Example 2:
17+
Input: n = 7, k = 2
18+
Output: 7
19+
Explanation: Factors list is [1, 7], the 2nd factor is 7.
20+
21+
Example 3:
22+
Input: n = 4, k = 4
23+
Output: -1
24+
Explanation: Factors list is [1, 2, 4], there is only 3 factors. We should return -1.
25+
26+
Example 4:
27+
Input: n = 1, k = 1
28+
Output: 1
29+
Explanation: Factors list is [1], the 1st factor is 1.
30+
31+
Example 5:
32+
Input: n = 1000, k = 3
33+
Output: 4
34+
Explanation: Factors list is [1, 2, 4, 5, 8, 10, 20, 25, 40, 50, 100, 125, 200, 250, 500, 1000].
35+
*/
36+
37+
publicclass_1492 {
38+
39+
publicintkthFactor(intn,intk) {
40+
for (inti =1;i <=n /2;i++) {
41+
if (n %i ==0) {
42+
k--;
43+
if (k ==0) {
44+
returni;
45+
}
46+
}
47+
}
48+
returnk ==1 ?n : -1;
49+
}
50+
}

‎src/com/hadley/_1539.java

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
packagecom.hadley;
2+
3+
/*
4+
2020.01.06
5+
Kth Missing Positive Number
6+
7+
Given an array arr of positive integers sorted in a strictly increasing order, and an integer k.
8+
9+
Find the kth positive integer that is missing from this array.
10+
11+
Example 1:
12+
Input: arr = [2,3,4,7,11], k = 5
13+
Output: 9
14+
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9.
15+
16+
Example 2:
17+
Input: arr = [1,2,3,4], k = 2
18+
Output: 6
19+
Explanation: The missing positive integers are [5,6,7,...]. The 2nd missing positive integer is 6.
20+
*/
21+
22+
publicclass_1539 {
23+
24+
//Memory Limit Exceeded
25+
publicintfindKthPositive(int[]arr,intk) {
26+
int[]allList =newint[Integer.MAX_VALUE];
27+
//index from 0 to Integer.MAX_VALUE-1
28+
for(inti =0;i <arr.length;i++){
29+
allList[arr[i] -1] =1;
30+
}
31+
32+
intresult =0;
33+
for(inti =0;i <allList.length;i++){
34+
if(k <=0){
35+
break;
36+
}
37+
38+
if(allList[i] ==1){
39+
k--;
40+
result++;
41+
}
42+
}
43+
returnresult;
44+
}
45+
46+
47+
publicintfindKthPositive1(int[]arr,intk) {
48+
//ideally, arr[i].value = i + 1
49+
for(inti =0;i <arr.length;i++){
50+
if(arr[i] -i -1 >=k){
51+
returnk +i;
52+
}
53+
}
54+
returnk +arr.length;
55+
}
56+
57+
}

‎src/com/hadley/_1640.java

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
packagecom.hadley;
2+
3+
/*
4+
2021.1.2
5+
Check Array Formation Through Concatenation
6+
7+
You are given an array of distinct integers arr and an array of integer arrays pieces, where the integers in pieces are distinct. Your goal is to form arr by concatenating the arrays in pieces in any order. However, you are not allowed to reorder the integers in each array pieces[i].
8+
9+
Return true if it is possible to form the array arr from pieces. Otherwise, return false.
10+
11+
Example 1:
12+
Input: arr = [85], pieces = [[85]]
13+
Output: true
14+
15+
Example 2:
16+
Input: arr = [15,88], pieces = [[88],[15]]
17+
Output: true
18+
Explanation: Concatenate [15] then [88]
19+
20+
Example 3:
21+
Input: arr = [49,18,16], pieces = [[16,18,49]]
22+
Output: false
23+
Explanation: Even though the numbers match, we cannot reorder pieces[0].
24+
25+
Example 4:
26+
Input: arr = [91,4,64,78], pieces = [[78],[4,64],[91]]
27+
Output: true
28+
Explanation: Concatenate [91] then [4,64] then [78]
29+
30+
Example 5:
31+
Input: arr = [1,3,5,7], pieces = [[2,4,6,8]]
32+
Output: false
33+
34+
*/
35+
36+
importjava.util.Arrays;
37+
importjava.util.HashMap;
38+
importjava.util.Map;
39+
40+
publicclass_1640 {
41+
42+
publicbooleancanFormArray(int[]arr,int[][]pieces) {
43+
Map<Integer,int[]>map =newHashMap<>();
44+
45+
for(int[]piece:pieces){
46+
map.put(piece[0],piece);
47+
}
48+
49+
//sum(piece[i].length) = arr.length
50+
int[]result =newint[arr.length];
51+
inti =0;
52+
53+
for(inta :arr){
54+
if(map.containsKey(a)){
55+
for(intp :map.get(a)){
56+
result[i++] =p;
57+
}
58+
}
59+
}
60+
61+
returnArrays.equals(arr,result);
62+
}
63+
}

‎src/com/hadley/_266.java

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
packagecom.hadley;
2+
3+
/*
4+
2021.01.02
5+
Palindrome Permutation
6+
Given a string, determine if a permutation of the string could form a palindrome.
7+
8+
Example 1:
9+
Input: "code"
10+
Output: false
11+
12+
Example 2:
13+
Input: "aab"
14+
Output: true
15+
16+
Example 3:
17+
Input: "carerac"
18+
Output: true
19+
*/
20+
21+
importjava.util.HashSet;
22+
23+
publicclass_266 {
24+
publicbooleancanPermutePalindrome(Strings) {
25+
HashSet<Character>set =newHashSet<>();
26+
for(inti =0;i <s.length();i++){
27+
if(set.contains(s.charAt(i))){
28+
set.remove(s.charAt(i));
29+
}else{
30+
set.add(s.charAt(i));
31+
}
32+
}
33+
34+
if(set.size() ==0 ||set.size() ==1){
35+
returntrue;
36+
}
37+
38+
returnfalse;
39+
}
40+
}

‎src/com/hadley/_416.java

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
packagecom.hadley;
2+
3+
/*
4+
2020.11.27
5+
Partition Equal Subset Sum
6+
Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.
7+
8+
Example 1:
9+
Input: nums = [1,5,11,5]
10+
Output: true
11+
Explanation: The array can be partitioned as [1, 5, 5] and [11].
12+
13+
Example 2:
14+
Input: nums = [1,2,3,5]
15+
Output: false
16+
Explanation: The array cannot be partitioned into equal sum subsets.
17+
18+
guidance: https://wangxin1248.github.io/algorithm/2020/06/leetcode-416.html
19+
*/
20+
21+
publicclass_416 {
22+
publicbooleancanPartition(int[]nums) {
23+
intn =nums.length;
24+
if(n <1){
25+
returntrue;
26+
}
27+
intsum =0;
28+
for(inti :nums){
29+
sum +=i;
30+
}
31+
32+
if(sum %2 !=0){
33+
returnfalse;
34+
}
35+
36+
intc =sum/2;
37+
boolean[]memo =newboolean[c+1];
38+
for(inti =0;i <=c;i++){
39+
memo[i] = (nums[0] ==i);
40+
}
41+
42+
for(inti =1;i <n;i++){
43+
for(intj =c;j >=nums[i];j--){
44+
memo[j] =memo[j] ||memo[j-nums[i]];
45+
}
46+
}
47+
48+
49+
50+
returnmemo[c];
51+
}
52+
53+
}

0 commit comments

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