438. Find All Anagrams in a String
문제
s로 주어지는 문자열 안에서 p로 주어지는 문자열의 Anagram을 찾고 시작부분의 인덱스를 리턴하라.
Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".해결 O(n) / O(1)
해시테이블과 sliding window기법을 사용하는 좋은 문제였다.
p크기 만큼의 윈도우를 s내에서 하나씩 오른쪽으로 이동하면서 체크하면 됨.
Runtime: 12 ms, faster than 92.59% of C++
class Solution {
bool is_table_same(int *st, int *pt) {
for (int i = 0; i < 26; i++) {
if (st[i] != pt[i])
return false;
}
return true;
}
public:
vector<int> findAnagrams(string s, string p) {
vector<int> ret;
int ssize = s.size();
int psize = p.size();
if (ssize < psize)
return ret;
int stable[26] = {0};
int ptable[26] = {0};
for (int i = 0; i < psize; i++) {
ptable[p[i] - 'a']++;
stable[s[i] - 'a']++;
}
if (is_table_same(stable, ptable))
ret.push_back(0);
for (int i = 1; i <= ssize - psize; i++) {
stable[s[i - 1] - 'a']--;
stable[s[i + psize - 1] - 'a']++;
if (is_table_same(stable, ptable))
ret.push_back(i);
}
return ret;
}
};424. Longest Repeating Character Replacement
문제
대문자로 구성된 문자열이 주어지고, 그 중 하나를 선택해서 아무 대문자로 바꿀수 있는 횟수 k가 주어질때, 동일한 문자로 구성된 substring의 최대 갯수는?
Input: s = "ABAB", k = 2
Output: 4
Input: s = "AABABBA", k = 1
Output: 4해결 O(n)
생각하기 어려웠던 문제였다. discussion을 좀 참고했음. right와 left를 O(n)동안 하나씩만 이동해도 결과를 얻을수 있는게 직관적으로 와닿지 않음. right를 for문에서 하나씩 증가. 각 루프에서 해당 right까지 내에서 최대 길이 보장됨을 의미. 문자열길이에서 해당 문자열중에 가장 freq가 많은 문자 갯수 를 뺀갯수가 k개를 초과하면 left를 증가시킨다.
속도는 100% 나옴.
#define max(a,b) (((a) > (b)) ? (a) : (b))
int characterReplacement(char * s, int k){
int freq[26] = {0};
int maxfreq = 0;
int ssize = strlen(s);
int left = 0, right = 0;
int maxlen = 0;
for (; right < ssize; right++) {
/* update s[right] freq */
freq[s[right] - 'A']++;
maxfreq = max(maxfreq, freq[s[right] - 'A']);
/* if target charactors to change is larger than k */
/* len = right - left + 1 */
if (right - left + 1 - maxfreq > k) {
freq[s[left] - 'A']--;
left++;
} else {
maxlen = max(right - left + 1, maxlen);
}
}
return maxlen;
}1652. Defuse the Bomb
문제
주어진 배열값과 k값으로 폭탄을 해체하는 코드를 생성해라. 코드를 생성하는 방법은, 각 자리수를 k개만큼 이전/이후 까지를 더한값으로 계산하면 된다. 아래 예시를 확인!
주의할 사항은 순환배열이라는 사실.
Input: code = [5,7,1,4], k = 3
Output: [12,10,16,13]
Explanation: Each number is replaced by the sum of the next 3 numbers.
The decrypted code is [7+1+4, 1+4+5, 4+5+7, 5+7+1].
Notice that the numbers wrap around.
Input: code = [2,4,9,3], k = -2
Output: [12,5,6,13]
Explanation: The decrypted code is [3+9, 2+3, 4+2, 9+4].
Notice that the numbers wrap around again.
If k is negative, the sum is of the previous numbers.https://leetcode.com/problems/defuse-the-bomb/
해결 O(n)
sliding window 구간합 문제, 매번 모든 구간을 더할필요없고 이전 sum에서 필요한 부분만 더하고 빼면 O(1) 에 합을 계산할 수 있다. 배열인덱싱은 항상 햇갈린다. 이번 문제는 인덱싱이 복잡해서 더 햇갈렸음.
배운것들.
- 순환(circular)하는 배열 -> 이런 단어가 나오면 항상
%으로 배열인덱싱을 한다. - 시계방향 순환 인덱싱:
[i % asize]/ 반 시계방향 순환 인덱싱:?. (asize 배열크기) - 이 문제의 경우 k가 음수/양수이건간에 시계방향 순환 인덱싱이기 때문에
[positino % asize]으로 적절한 포지션을 계산한 뒤% 크기연산을 하면 된다.
k < 0인경우 position 구하는 계산이 매우 햇갈렸다. 근데 생각해보면 시계방향으로 커지는것이기 때문에 그냥 적절한 position만 계산한다는 생각을 하면 될것같다.[((codeSize + k - 1) + i) % codeSize]
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* decrypt(int* code, int codeSize, int k, int* returnSize){
int sum = 0;
*returnSize = codeSize;
int *ret = (int *)calloc(codeSize, sizeof(int));
if (k == 0) {
return ret;
} else if (k > 0) {
for (int i = 1; i < k + 1; i++)
sum += code[i]; // no need to [i % codeSize]
ret[0] = sum;
for (int i = 1; i < codeSize; i++) {
sum = sum - code[i] + code[(i + k) % codeSize];
ret[i] = sum;
}
} else if (k < 0) {
for (int i = codeSize - 1; i >= codeSize + k; i--)
sum += code[i]; // no need to [i % codeSize]
ret[0] = sum;
for (int i = 1; i < codeSize; i++) {
sum = sum - code[((codeSize + k - 1) + i) % codeSize] + code[(i-1) % codeSize];
ret[i] = sum;
}
}
return ret;
}159. Longest Substring with At Most Two Distinct Characters
문제
문자열이 주어질때, 최대 2개로만 구성된 가장 긴 substring 길이를 리턴하라.
Input: s = "eceba"
Output: 3
Explanation: The substring is "ece" which its length is 3.아이디어
- two pointer & sliding window (with hashtable)
- hashtable빈도수가 2개 이하일때 -> right 증가
- hashtable빈도수가 2개 초과일때 -> left증가
two pointer 문제는 어떤 조건에서 right를 증가 시킬지, 그리고 어떤 조건에서 left를 증가시킬지를 먼서 생각해보는 전략을 사용하기.
해결 O(n)
O(n) 이지만 빈도수를 체크할때 매번 hashtable 전체를 순회해야해서 비효율적인 방법. (Runtime: 426 ms)
#define TABLE_SIZE 128
#define max(a,b) (((a) > (b)) ? (a) : (b))
int check_nr_char(int *table)
{
int cnt = 0;
for (int i = 0; i < TABLE_SIZE; i++) {
if (table[i] != 0)
cnt++;
}
return cnt;
}
int lengthOfLongestSubstringTwoDistinct(char * s){
int table[TABLE_SIZE] = {0,};
int maxlen = 0;
int ssize = strlen(s);
int left = 0, right = 0;
table[s[right]]++;
while (right < ssize) {
if (check_nr_char(table) <= 2) {
maxlen = max(maxlen, right - left + 1);
right++;
table[s[right]]++;
} else {
table[s[left++]]--;
}
}
return maxlen;
}해결 O(n)
빈도수를 체크할때 hashtable 크기만큼 순회하지 않고, 문자종류 갯수 cur_freq 변수값 하나를 조정해서 수행. 훨씬 효율적이고 빠르다. (Runtime: 22 ms, faster than 80.95%)
hashtable빈도수를 저장할때 0이었다면 총 문자종류개수를 +1 하고, 빈도수를 감소시킬때 0이 된다면 총 문자종류수를 -1 한다.
#define TABLE_SIZE 128
#define max(a,b) (((a) > (b)) ? (a) : (b))
int lengthOfLongestSubstringTwoDistinct(char * s){
int table[TABLE_SIZE] = {0,};
int maxlen = 0;
int ssize = strlen(s);
int left = 0, right = 0;
int cur_freq = 1;
table[s[right]]++;
while (right < ssize) {
if (cur_freq <= 2) {
maxlen = max(maxlen, right - left + 1);
right++;
if (table[s[right]] == 0)
cur_freq++;
table[s[right]]++;
} else {
if (table[s[left]] == 1)
cur_freq--;
table[s[left++]]--;
}
}
return maxlen;
}해결 O(n)
위와 동일한 로직인데 아래 코드가 더 논리적으로 이해하기 쉽고 간결. 속도도 더 빠르게 나왔음.
(Runtime: 12 ms, faster than 100.00%)
#define TABLE_SIZE 128
#define max(a,b) (((a) > (b)) ? (a) : (b))
int lengthOfLongestSubstringTwoDistinct(char * s){
int table[TABLE_SIZE] = {0,};
int maxlen = 0;
int ssize = strlen(s);
int left = 0, right = 0;
int cur_freq = 0;
while (right < ssize) {
table[s[right]]++;
if (table[s[right]] == 1)
cur_freq++;
if (cur_freq <= 2) {
maxlen = max(maxlen, right - left + 1);
} else {
table[s[left]]--;
if (table[s[left]] == 0)
cur_freq--;
left++;
}
right++;
}
return maxlen;
}3. Longest Substring Without Repeating Characters
문제
문자열이 주어질때, 반복된 문자가 없는 가장 긴 substring의 길이를 구하라.
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.해결 O(N)
sliding window 로 해결. (discussion참고)
- left/right 두개의 포인터를 이동하면서 window의 사이즈를 변경하여 체크.
- 해시테이블에 빈도수를 저장.
- table[s[right]] 이 2 이상 이라면, 1이하로 줄때까지 left를 증가
- right가 증가하면서 중복된 값을 만났다는뜻.
- update max lenth
1. constraint
- 0 <= s.length <= 50000
- s can be all kind of letter
2. Ideas
- greedy way O(N) -> X
- using hashtable to check repeated letter exist
- brute force with Window size -> O(N^2)
- sliding window with two pointer (l, r)
- increase l, while (table[s[r]] > 1)
3. TC#define TABLE_SIZE 128
int lengthOfLongestSubstring(char * s) {
int table[TABLE_SIZE] = {0,};
int ssize = strlen(s);
int max_len = 0;
int left = 0, right = 0;
while (right < ssize) {
table[s[right]]++;
while (table[s[right]] > 1) {
table[s[left]]--;
left++;
}
if ((right - left + 1) > max_len)
max_len = right - left + 1;
right++;
}
return max_len;
}추가로 배열에서 두개의 인덱스값 a, b 가 주어졌을때 (a<b)라면 a에서 b의 길이는 b - a + 1이다. 당연한거긴 하지만 매번 만날때마다 계산을 하게되서 뇌를 쓰게된다. 그냥 이 패턴을 외우는게 좋겠다. 코딩시 STM을 최소로 사용. 인지적 부하를 최대한 줄이기.
비슷한 내용을 사용한풀이 :
https://velog.io/@soopsaram/Leetcode-5.-Longest-Palindromic-Substring
5. Longest Palindromic Substring
문자열이 주어질때 substring중 가장 긴 길이의 palindrome 문자열(좌/우에서 읽어도 동일한 문자열)을 구하라.
Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.https://leetcode.com/problems/longest-palindromic-substring/
해결 O(N^2)
문자열을 처음부터 끝까지 순회하면서 각각의 자리에서 expand를 하여 체크,
- 각각의 자리에서 가장 큰 길이의 palindrome 을 찾고 업데이트
expand_around_center()함수로 길이가 짝수인경우 홀수인경우 두가지 모두 체크- 가장긴 길이를 찾았을때 업데이트하는 start, end공식은 짝/홀일때 모두 적용되는 공식...(!)
TODO 복사해올것
219. Contains Duplicate II
문제
배열이 주어지고 서로다른 두 인덱스 i, j가 있을때 다음의 조건을 만족하는 i,j가 있다면 true 리턴
nums[i] == nums[j] abs(i - j) <= k.
Input: nums = [1,2,3,1,2,3], k = 2
Output: false문제를 다시 해석하면 i, j의 간격크기가 k 이하인 요소 중, 배열값이 서로 같은 요소가 있는지 확인하는것과 같음.
해결 O(N)
sliding window와 hashtable을 활용한 풀이. 먼저 초기 윈도우사이즈 k만큼 해시테이블에 빈도수를 기록하고, 그뒤 윈도우를 이동하면서 바뀐부분(이전 윈도우의 첫번째, 다음윈도우의 마지막)만 체크하면 해결된다. 빈도수가 2가되면 true다.
마지막으로 처음으로 C로 hashtable을 구현하지 않고 cpp의 unordered_map을 사용했는데, 그렇게 간편할수가 없다. leetcode에서 처음으로 stl을 사용해서 풀었는데, c++로 전환준비중인 요즘이라 더 기쁘다.
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
std::unordered_map<int, int> table;
int nsize = nums.size();
for (int i = 0; i <= k && i < nsize; i++) {
if (i < nsize && table[nums[i]] > 0)
return true;
table[nums[i]]++;
}
for (int i = 0; i+k+1 < nsize; i++) {
table[nums[i]]--;
if (table[nums[i+k+1]] > 0)
return true;
table[nums[i+k+1]]++;
}
return false;
}
};해결 O(N^2)
무지성방식, TLE 발생
/* brute force : Time Limit Exceeded */
bool containsNearbyDuplicate(int* nums, int numsSize, int k){
for (int i = 0; i < numsSize; i++) {
for (int j = i+1; j < numsSize && j < i+k+1; j++) {
if (nums[i] == nums[j] && abs(i-j) <= k)
return true;
}
}
return false;
}2269. Find the K-Beauty of a Number
문제
숫자num이 주어지고 k길이가 주어질때, 숫자를 k만큼 쪼갠 수가 주어진 num의 몫이 될수 있는가? 있다면 몇개 존재하나?
Input: num = 430043, k = 2
Output: 2
Explanation: The following are the substrings of num of length k:
- "43" from "430043": 43 is a divisor of 430043.
- "30" from "430043": 30 is not a divisor of 430043.
- "00" from "430043": 0 is not a divisor of 430043.
- "04" from "430043": 4 is not a divisor of 430043.
- "43" from "430043": 43 is a divisor of 430043.
Therefore, the k-beauty is 2.해결 O(k N)
int divisorSubstrings(int num, int k){
int retcnt = 0;
char snum[11];
sprintf(snum, "%d", num);
int nsize = strlen(snum);
char *substr = (char *)calloc(k + 1, sizeof(char));
int sub = 0;
for (int i = 0; i <= nsize - k; i++) {
strncpy(substr, snum + i, k);
sscanf(substr, "%d", &sub);
if (sub == 0)
continue;
if (num % sub == 0) // always check devide by zero
retcnt++;
}
return retcnt;
}