LeetCode - Weekly Contest 311

풀이

Smallest Even Multiple

https://leetcode.com/problems/smallest-even-multiple/

정수 n이 주어지면 n이나 2n의 배수인 가장 작은 양의 정수를 반환한다.

n이 짝수인 경우에는 n을 반환하면 되는데, n이 짝수가 아니면 홀수라는 이야기이고 홀수일 때는 n에 2를 곱한 결과가 답이된다.

소스 코드

class Solution {
public:
    int smallestEvenMultiple(int n) {
        return (n & 1) == 0 ? n : n << 1;
    }
};

문제 풀이와는 크게 중요하지 않은 설명

• 정수 타입에서 홀수 짝수를 비교하기 대부분 모듈러 연산이 익숙할 것이지만 비트 연산을 사용할 수도 있다.
• 수를 이진법으로 생각했을 때 어떤 경우에 홀수인지 고려해본다면 홀수인 경우에는 항상 최하위 비트(LSB)가 1이다.
• 그리고 이것은 1과 n을 &(AND 연산)을 했을 때 그 결과가 0이라면 짝수라는 이야기이다.
  • 즉 XXXX XXX1 이면 항상 홀수이고, XXXX XXX0 이면 항상 짝수이다.

Length of the Longest Alphabetical Continuous Substring

https://leetcode.com/problems/length-of-the-longest-alphabetical-continuous-substring/

알파벳 소문자로 이루어진 문자열 s가 주어진다.

s에서 길이가 가장 알파벳 연속 문자열의 길이를 찾는 문제이다.

알파벳 연속 문자열이란 알파벳 순서를 지키면서 연속적으로 구성된 문자열을 의미한다.

• "abc"는 알파벳 연속 문자열이다.
• "abc", "za"는 알파벳 연속 문자열이 아니다.
• "abd"도 알파벳 연속 문자열이 아니다.

X 다음으로 올 수 있는 수는 X 보다 정확히 1 커야된다.는 조건을 지켜야하므로

문자열 i의 다음 글자가 i글자보다 정확히 1 큰 지를 확인하여 최대 길이를 갱신하고 반환하였다.

소스 코드

class Solution {
public:
    int longestContinuousSubstring(string s) {
        int ans = 1;
        
        char last = s[0];
        int len = 1;
        for (int i = 1; i < s.length(); ++i) {
            if (last + 1 == s[i]) {
                ++len;
                ans = max(ans, len);
            }
            else {
                len = 1;
            }
            last = s[i];
        }
        return ans;
    }
};

Reverse Odd Levels of Binary Tree

https://leetcode.com/problems/reverse-odd-levels-of-binary-tree/

포화 이진 트리가 주어질 때 트리 레벨 L이 홀수인 경우에 한해서,

트리의 좌측 서브 트리 노드 중 레벨 L에 위치한 노드와 우측 서브 트리 노드 중 레벨 L에 위치한 노드를 서로 맞바꾸는 문제이다. (좌우 대칭)

• 포화 이진 트리 : 트리의 모든 레벨에 대해 노드가 가득 차있는 트리
• 이 문제에서 트리의 레벨은 0부터 시작한다. (루트 노드의 트리 레벨 : 0)

우선 트리를 레벨 순회(level order traversal)하여 루트 부터 단말 노드까지 차례대로 벡터에 추가하였다.

• 1번째 인덱스를 루트 노드로 사상할 것이기 때문에 벡터의 초기 크기를 1로 설정했다.
• 즉, i가 부모 노드일 때 아래의 성질을 갖는다.
  • i의 좌측 노드는 2 * i
  • i의 우측 노드는 2 * i + 1

이 과정에서 홀수 레벨인 경우에는 추가한 노드를 맞바꾸어야 한다.

L번 레벨까지의 모든 노드를 누적한 개수를 nodeCount라고 할 때, 포화 이진 트리의 특성상

• nodeCount번째 노드가 속한 레벨 L에서 가장 왼쪽 노드의 인덱스는 (nodeCount >> 1) + 1이다.
• nodeCount번째 노드가 속한 레벨 L에서 가장 오른쪽 노드의 인덱스는 nodeCount이다.

따라서 아래처럼 swap하면 된다.

int start = (nodeCount >> 1) + 1;
int end = nodeCount;
while (start < end) {
    swap(v[start], v[end]);
    ++start, --end;
}

이렇게 벡터가 만들어지고 나면, 레벨 순회를 하는 방식과 똑같이 루트 노드부터 시작하여 순서대로 TreeNode를 만들면 되고 이때 만들어진 TreeNode가 정답이 된다.

문제가 요구하는 바는 어렵지 않으므로 어떻게 구현하느냐가 관건일 것 같다.

소스 코드

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

#define pb push_back

class Solution {
public:
    TreeNode* reverseOddLevels(TreeNode* root) {
        // root is perfect binary tree
        if (root->left == nullptr) return root;
        
        vector<int> v(1);
        
        // level order
        int nodeCount = 0;
        int level = 0;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int qsize = q.size();
            for (int s = 0; s < qsize; ++s) {
                auto now = q.front();
                q.pop();
                if (now->left != nullptr) q.push(now->left);
                if (now->right != nullptr) q.push(now->right);
                v.pb(now->val);
                ++nodeCount;
            }
            if (level & 1) {
                int start = (nodeCount >> 1) + 1;
                int end = nodeCount;
                // cout << start << ' ' << end << '\n';
                while (start < end) {
                    swap(v[start], v[end]);
                    ++start;
                    --end;
                }
            }
            ++level;
        }
        
        int idx = 1;
        TreeNode* ret = new TreeNode(v[idx]);
        q.push(ret);
        while (!q.empty()) {
            int qsize = q.size();
            for (int s = 0; s < qsize; ++s) {
                auto now = q.front();
                q.pop();
                
                int left = idx << 1;
                int right = left + 1;
                if (left >= v.size()) break;
                
                // cout << left << ' ' << right << '\n';
                now->left = new TreeNode(v[left]);
                now->right = new TreeNode(v[right]);
                q.push(now->left);
                q.push(now->right);
                ++idx;
            }
        }
        return ret;
    }
};