Skip to content

Commit 124c693

Browse files
dohyeon2dohyeon2
authored
Merge pull request DaleStudy#2458 from dohyeon2/week3
2 parents 7ca3900 + e9acb59 commit 124c693

5 files changed

Lines changed: 175 additions & 0 deletions

File tree

‎combination-sum/dohyeon2.java‎

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
import java.util.ArrayList;
2+
import java.util.List;
3+
4+
class Solution {
5+
// TC : O(n!) => TC : O(2^T)
6+
// SC : O(n^2) => SC : O(T)
7+
ArrayList<List<Integer>> result = new ArrayList<>();
8+
9+
public List<List<Integer>> combinationSum(int[] candidates, int target) {
10+
backtrack(0, target, candidates, new ArrayList<>());
11+
return result;
12+
}
13+
14+
private void backtrack(int start, int diff, int[] candidates, ArrayList<Integer> path) {
15+
if (diff == 0) {
16+
result.add(new ArrayList<>(path)); // 깊은 복사
17+
return;
18+
}
19+
20+
if (diff < 0) {
21+
return;
22+
}
23+
24+
for (int i = start; i < candidates.length; i++) {
25+
path.add(candidates[i]);
26+
backtrack(i, diff - candidates[i], candidates, path);
27+
path.remove(path.size() - 1);
28+
}
29+
}
30+
}

‎decode-ways/dohyeon2.java‎

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
class Solution {
2+
// TC : O(n)
3+
// SC : O(1)
4+
public int numDecodings(String s) {
5+
// If it starts with 0, the value can't be decoded.
6+
if (s.charAt(0) == '0') {
7+
return 0;
8+
}
9+
10+
int n = s.length();
11+
12+
int prev2 = 1;
13+
int prev1 = 1;
14+
15+
// dp[i] = dp[i-1] + dp[i-2]
16+
for (int i = 1; i < n; i++) {
17+
int current = 0;
18+
19+
if (s.charAt(i) != '0') {
20+
current += prev1;
21+
}
22+
23+
int twoDigit = Integer.valueOf(s.substring(i - 1, i + 1));
24+
25+
if (twoDigit >= 10 && twoDigit <= 26) {
26+
current += prev2;
27+
}
28+
29+
prev2 = prev1;
30+
prev1 = current;
31+
}
32+
33+
return prev1;
34+
}
35+
}

‎maximum-subarray/dohyeon2.java‎

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
class Solution {
2+
// TC : O(n)
3+
// SC : O(1)
4+
public int maxSubArray(int[] nums) {
5+
int max = nums[0];
6+
int sum = 0;
7+
8+
for (int i = 0; i < nums.length; i++) {
9+
// 부분합보다 현재 숫자가 더 크면 갱신한다.
10+
// 현재 숫자 단독이 더 큰 경우 이전 합이 의미가 없기 때문에 그리디하게 처리 가능
11+
sum = Math.max(nums[i], nums[i] + sum);
12+
max = Math.max(sum, max);
13+
}
14+
15+
return max;
16+
}
17+
}

‎number-of-1-bits/dohyeon2.java‎

Lines changed: 75 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,75 @@
1+
import java.util.HashMap;
2+
3+
class Solution {
4+
// n & (n-1) -> 마지막 set bit 제거
5+
// n & -n -> 마지막 set bit 추출
6+
// i >> 1 -> 절반
7+
// i & 1 -> 마지막 bit
8+
// i & (i - 1) == 0 -> i는 2의 거듭제곱
9+
10+
// Follow up: If this function is called many times, how would you optimize it?
11+
// I'll cache the results in a HashMap.
12+
// (Or I can use lookup table or DP)
13+
private HashMap<Integer, Integer> cache = new HashMap<>();
14+
15+
public int hammingWeight(int n) {
16+
// simple in Java
17+
// return Integer.bitCount(n);
18+
19+
if (cache.containsKey(n)) {
20+
return cache.get(n);
21+
}
22+
23+
int buffer = n;
24+
int answer = 0;
25+
26+
// 1. self thought solution
27+
// TC : O(log n)
28+
// SC : O(1)
29+
while (buffer > 0) {
30+
answer += buffer % 2;
31+
buffer = buffer / 2;
32+
}
33+
34+
// 2. fancy solution from leetcode using bit computing
35+
// TC : O(log n)
36+
// SC : O(1)
37+
// while(buffer > 0){
38+
// if((buffer & 1) == 1){
39+
// answer++;
40+
// }
41+
// buffer = buffer >> 1;
42+
// }
43+
44+
// 3. another fancy solution from ChatGPT
45+
// Brian Kernighan algorithm
46+
// TC : O(number of set bits)
47+
// SC : O(1)
48+
// while (buffer != 0) {
49+
// // 11 & 10 => 1 & 0 => 0
50+
// buffer = buffer & (buffer - 1); // AND with buffer and buffer -1 => remove
51+
// last set bit.
52+
// System.out.println(buffer);
53+
// answer++;
54+
// }
55+
56+
// 4. using lookup table
57+
// int[] table = new int[256];
58+
// for (int i = 0; i < 256; i++) {
59+
// table[i] = (i & 1) + table[i >> 1];
60+
// }
61+
// answer = table[buffer & 0xff] +
62+
// table[(buffer >> 8) & 0xff] +
63+
// table[(buffer >> 16) & 0xff] +
64+
// table[(buffer >> 24) & 0xff];
65+
66+
// 5. DP
67+
// int[] bits = new int[n + 1];
68+
// for (int i = 1; i <= n; i++) {
69+
// bits[i] = bits[i >> 1] + (i & 1);
70+
// }
71+
72+
cache.put(n, answer);
73+
return answer;
74+
}
75+
}

‎valid-palindrome/dohyeon2.java‎

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
class Solution {
2+
// TC : O(n)
3+
// SC : O(1)
4+
public boolean isPalindrome(String s) {
5+
// Condition 1 : after converting all uppercase letters into lowercase letters
6+
// and removing all non-alphanumeric characters
7+
String onlyAlphaNumeric = s.toLowerCase().replaceAll("[^a-z0-9]", "");
8+
int length = onlyAlphaNumeric.length();
9+
for (int i = 0; i < length / 2; i++) {
10+
int right = length - 1 - i;
11+
int left = i;
12+
// Condition 2 : it reads the same forward and backward
13+
if (onlyAlphaNumeric.charAt(left) != onlyAlphaNumeric.charAt(right))
14+
return false;
15+
}
16+
return true;
17+
}
18+
}

0 commit comments

Comments
 (0)