koenjazh-CNfresde
짬뽕얼큰하게의 맨땅에 헤딩 :: '2025/02/05 글 목록

Check if One String Swap Can Make Strings Equal

알고리즘 2025. 2. 5. 21:35

Leetcode Problem:

Summary

  • Given two strings of equal length, determine if it is possible to make both strings equal by performing at most one string swap on exactly one of the strings.

Approach

  • This solution works by first finding all the indices where the two strings differ
  • If there are no differences, the strings are already equal, so the function returns true
  • If there are exactly two differences, the function checks if swapping the characters at these indices would result in equal strings
  • If so, the function returns true; otherwise, it returns false.

Complexity

  • O(n), where n is the length of the input strings, because the solution makes a single pass through the strings to find the differences.

Explain

  • The solution uses a vector to store the indices where the two strings differ
  • It then checks if there are exactly two differences
  • If so, it checks if swapping the characters at these indices would result in equal strings by comparing the characters at the two indices in both strings
  • If the characters are the same, the function returns true; otherwise, it returns false.

Solution Code:


class Solution {
public:
    vector diffIdx;
    bool areAlmostEqual(string s1, string s2) {
        for(int i = 0 ; i < s1.size(); i++){
            if(s1[i] != s2[i]){
                diffIdx.push_back(i);
            }
        }
        if(diffIdx.size() == 0) return true;
        if(diffIdx.size() != 2) return false;
        if(s1[diffIdx[0]] != s2[diffIdx[1]]){
            return false;
        }
        if(s1[diffIdx[1]] != s2[diffIdx[0]]){
            return false;
        }
        return true;
    }
};

'알고리즘' 카테고리의 다른 글

Find the Number of Distinct Colors Among the Balls  (0) 2025.02.07
Tuple with Same Product  (0) 2025.02.07
Magic Squares In Grid  (1) 2025.02.05
Spiral Matrix III  (0) 2025.02.05
Integer to English Words  (0) 2025.02.05
블로그 이미지

짬뽕얼큰하게

,

Magic Squares In Grid

알고리즘 2025. 2. 5. 08:50

Leetcode Problem:

Summary

  • Count the number of 3x3 magic square subgrids in a given grid.

Approach

  • The approach used is to iterate over the grid and for each possible 3x3 subgrid, check if it is a magic square by verifying the sums of rows, columns, and diagonals
  • If all conditions are met, increment the counter.

Complexity

  • O(R*C*(R*C)) where R is the number of rows and C is the number of columns in the grid.

Explain

  • The solution iterates over the grid and checks each 3x3 subgrid
  • For each subgrid, it checks if all numbers are distinct and within the range 1-9
  • Then, it calculates the sums of rows, columns, and diagonals and checks if they are all equal
  • If all conditions are met, it increments the counter
  • The time complexity is O(R*C*(R*C)) due to the nested loops and calculations.

Solution Code:


class Solution {
public:
    int numMagicSquaresInside(vector>& grid) {
        int ans = 0;
        if (grid.size() < 3 || grid[0].size() < 3) return 0;
        for(int i = 0 ; i < grid.size() - 2; i++){
            for(int j = 0 ; j < grid[i].size() - 2; j++){
                int cnt = 0;
                int sum = 0;
                bool visited[10] = {false};
                for(int r =i; r < i + 3; r++){
                    for(int c = j; c < j + 3; c++){
                        if(grid[r][c] < 1 || grid[r][c] >= 10 || visited[grid[r][c]]) break;
                        cnt++;
                        visited[grid[r][c]] = true;
                    }
                }
                int sumArr[8] = {0};
                if (cnt == 9){
                    for(int k = 0 ; k < 3; k++){
                        sumArr[0] += grid[i][j+k];
                        sumArr[1] += grid[i+1][j+k];
                        sumArr[2] += grid[i+2][j+k];
                        sumArr[3] += grid[i+k][j];
                        sumArr[4] += grid[i+k][j+1];
                        sumArr[5] += grid[i+k][j+2];
                        sumArr[6] += grid[i+k][j+k];
                        sumArr[7] += grid[i+k][j+2-k];
                    }
                    bool isMagicGrid = true;
                    for(int k = 1 ; k < 8; k++){
                        if (sumArr[k] != sumArr[0]){
                            isMagicGrid = false;
                            break;
                        }
                    }
                    if (isMagicGrid){
                        ans++;
                    }
                }
            }
        }
        return ans;
    }
};

'알고리즘' 카테고리의 다른 글

Tuple with Same Product  (0) 2025.02.07
Check if One String Swap Can Make Strings Equal  (0) 2025.02.05
Spiral Matrix III  (0) 2025.02.05
Integer to English Words  (0) 2025.02.05
Minimum Number of Pushes to Type Word II  (0) 2025.02.05
블로그 이미지

짬뽕얼큰하게

,

Spiral Matrix III

알고리즘 2025. 2. 5. 08:47

Leetcode Problem:

Summary

  • Find the positions of a 2D grid in a clockwise spiral shape.

Approach

  • The solution uses a while loop to traverse the grid in a clockwise spiral shape
  • It starts at the given start position and moves in a direction (right, down, left, up) for a specified number of steps
  • The direction is updated after each step, and the position is added to the result list if it is within the grid boundaries.

Complexity

  • O(rows * cols)

Explain

  • The solution uses four arrays `dy` and `dx` to represent the possible directions (up, down, left, right) in the grid
  • The `ans_cnt` variable keeps track of the number of positions visited, and the `cnt` variable keeps track of the number of steps in the current direction
  • The `dir` variable keeps track of the current direction
  • The solution uses a while loop to traverse the grid, and it adds the current position to the result list if it is within the grid boundaries.

Solution Code:


class Solution {
public:
    vector> spiralMatrixIII(int rows, int cols, int rStart, int cStart) {
        vector> ans;
        int dy[] = {0, 1, 0, -1};
        int dx[] = {1, 0, -1, 0};
        int ans_cnt = 0;
        int cnt = 1;
        int dir = 0;
        ans.push_back({rStart, cStart});
        ans_cnt++;
        while(ans_cnt < rows * cols){
            for(int i = 0 ; i < 2; i++){
                for(int j = 0 ; j < cnt; j++){
                    rStart += dy[dir];
                    cStart += dx[dir];
                    if (rStart < 0 || rStart >= rows || cStart < 0 || cStart >= cols){
                        continue;
                    }
                    ans.push_back({rStart, cStart});
                    ans_cnt++;
                }
                dir = (dir + 1) % 4;
            }
            cnt++;
        }
        return ans;
    }
};

'알고리즘' 카테고리의 다른 글

Check if One String Swap Can Make Strings Equal  (0) 2025.02.05
Magic Squares In Grid  (1) 2025.02.05
Integer to English Words  (0) 2025.02.05
Minimum Number of Pushes to Type Word II  (0) 2025.02.05
Kth Distinct String in an Array  (0) 2025.02.05
블로그 이미지

짬뽕얼큰하게

,

Integer to English Words

알고리즘 2025. 2. 5. 08:43

Leetcode Problem:

Summary

  • Convert a non-negative integer to its English words representation.

Approach

  • The approach used is to recursively break down the number into smaller parts (thousands, millions, billions) and then convert each part to words using a combination of arrays and helper functions.

Complexity

  • O(log n) where n is the number of digits in the input number

Explain

  • The solution code uses three arrays to store the words for thousands, millions, and billions
  • It also uses a helper function `getUnderHndred` to convert numbers less than 100 to words
  • The `numberToWords` function recursively breaks down the input number into smaller parts and then combines the words for each part to form the final result.

Solution Code:


class Solution {
public:
    string digitOf1000[5] = {
        "",
        " Thousand",
        " Million",
        " Billion"

    };
    string digitOf10[11] = {
        "",
        " Ten",
        " Twenty",
        " Thirty",
        " Forty",
        " Fifty",
        " Sixty",
        " Seventy",
        " Eighty",
        " Ninety"
    };
    string underTwenty[21] = {
        "",
        " One",
        " Two",
        " Three",
        " Four",
        " Five",
        " Six",
        " Seven",
        " Eight",
        " Nine",
        " Ten",
        " Eleven",
        " Twelve",
        " Thirteen",
        " Fourteen",
        " Fifteen",
        " Sixteen",
        " Seventeen",
        " Eighteen",
        " Nineteen"
    };
    string getUnderHndred(int num){
        if (num < 20){
            return underTwenty[num];
        }
        string s = "";
        if (num / 10 > 0){
            s += digitOf10[num/10];
        }
        if (num %10 > 0){
            s += underTwenty[num % 10];
        }
        return s;
    }

    string numberToWords(int num) {
        string res = "";
        int cnt = 0;
        if (num == 0) return "Zero";
        while(num){
            string s = "";
            int num2 = (num % 1000);
            if ( num2 / 100){
                s += underTwenty[num2/100] + " Hundred";
            }
            s += getUnderHndred(num2 % 100);
            if (s.compare("") != 0)
                res = s + digitOf1000[cnt] + res;
            num /= 1000;
            cnt++;
        }
        return res.substr(1);
    }
};

'알고리즘' 카테고리의 다른 글

Magic Squares In Grid  (1) 2025.02.05
Spiral Matrix III  (0) 2025.02.05
Minimum Number of Pushes to Type Word II  (0) 2025.02.05
Kth Distinct String in an Array  (0) 2025.02.05
Maximum Ascending Subarray Sum  (0) 2025.02.04
블로그 이미지

짬뽕얼큰하게

,

Minimum Number of Pushes to Type Word II

알고리즘 2025. 2. 5. 08:40

Leetcode Problem:

Summary

  • Given a string of lowercase English letters, find the minimum number of times the keys will be pushed to type the string after remapping the keys on a telephone keypad.

Approach

  • The approach used is to first count the frequency of each letter in the string, then sort the letters based on their frequency and map them to the keys in a way that minimizes the number of pushes required.

Complexity

  • O(n log n) where n is the number of unique letters in the string

Explain

  • The code first counts the frequency of each letter in the string using an array `word_cnt`
  • Then it sorts the letters based on their frequency using a merge sort algorithm
  • After sorting, it maps the letters to the keys in a way that minimizes the number of pushes required
  • The `merge` function is used to merge two sorted subarrays into a single sorted subarray
  • The `merge_sort` function is used to recursively sort the letters
  • The `minimumPushes` function is the main function that calculates the minimum number of pushes required.

Solution Code:


class Solution {
public:
    int word_cnt[26];
    int sortedAlphabet[26];
    int tmp[26];
    void merge(int l, int mid, int r){
        int i = l;
        int j = mid + 1;
        int cur = i;
        while(i <= mid && j <= r){
            if(word_cnt[sortedAlphabet[i]] > word_cnt[sortedAlphabet[j]]){
                tmp[cur++] = sortedAlphabet[i++];
            } else {
                tmp[cur++] = sortedAlphabet[j++];
            }
        }
        while(i <= mid){
            tmp[cur++] = sortedAlphabet[i++];
        }
        for(i = l; i < cur; i++){
            sortedAlphabet[i] = tmp[i];
        }
    }
    void merge_sort(int l, int r){
        if(l >= r) return;
        int mid = (l + r) / 2;
        merge_sort(l ,mid);
        merge_sort(mid+1, r);
        merge(l, mid, r);
    }
    int minimumPushes(string word) {
        int min_cnt = 0;
        for(int i = 0 ; i < word.size(); i++){
            word_cnt[word[i] - 'a']++;
        }
        for(int i = 0 ; i < 26; i++){
            sortedAlphabet[i] = i;
        }
        merge_sort(0, 25);
        int buttonCnt = 0;
        int ans = 0;
        for(int i = 0 ; i < 26; i++){
            int c = sortedAlphabet[i];
            if (word_cnt[c] == 0) break;
            int click_cnt = buttonCnt / 8 + 1;
            ans += click_cnt*word_cnt[c];
            buttonCnt++;
        }
        return ans;
    }
};

'알고리즘' 카테고리의 다른 글

Spiral Matrix III  (0) 2025.02.05
Integer to English Words  (0) 2025.02.05
Kth Distinct String in an Array  (0) 2025.02.05
Maximum Ascending Subarray Sum  (0) 2025.02.04
Range Sum of Sorted Subarray Sums  (0) 2025.02.04
블로그 이미지

짬뽕얼큰하게

,

Kth Distinct String in an Array

알고리즘 2025. 2. 5. 08:37

Leetcode Problem:

Summary

  • Given an array of strings and an integer k, return the kth distinct string present in the array
  • If there are fewer than k distinct strings, return an empty string.

Approach

  • The approach used is to count the frequency of each string in the array using an unordered map
  • Then, iterate through the array again to find the kth distinct string
  • If k is greater than the number of distinct strings, return an empty string.

Complexity

  • O(n + m) where n is the size of the array and m is the number of distinct strings

Explain

  • First, we create an unordered map to store the frequency of each string in the array
  • We then initialize a counter K to keep track of the number of distinct strings
  • We iterate through the array again, and for each string, we check if its frequency is 1
  • If it is, we increment the counter K
  • If K equals k, we return the current string
  • If we finish iterating through the array and K is still less than k, we return an empty string.

Solution Code:


class Solution {
public:
    string kthDistinct(vector& arr, int k) {
        unordered_map m;
        for(int i = 0 ; i < arr.size(); i++){
            m[arr[i]]++;
        }
        int K = 0;
        for(int i = 0 ; i < arr.size(); i++){
            if(m[arr[i]] == 1){
                K++;
                if(k == K) return arr[i];
            }
        }
        return "";
    }
};

'알고리즘' 카테고리의 다른 글

Integer to English Words  (0) 2025.02.05
Minimum Number of Pushes to Type Word II  (0) 2025.02.05
Maximum Ascending Subarray Sum  (0) 2025.02.04
Range Sum of Sorted Subarray Sums  (0) 2025.02.04
Number of Senior Citizens  (0) 2025.02.04
블로그 이미지

짬뽕얼큰하게

,

공지사항

글 보관함

달력

«   2025/02   »
일 월 화 수 목 금 토
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28

티스토리툴바