Welcome To Sora Park

A DNA sequence can be represented as a string consisting of the letters A, C, G and T, which correspond to the types of successive nucleotides in the sequence. Each nucleotide has an impact factor, which is an integer. Nucleotides of types A, C, G and T have impact factors of 1, 2, 3 and 4, respectively. You are going to answer several queries of the form: What is the minimal impact factor of nucleotides contained in a particular part of the given DNA sequence?

The DNA sequence is given as a non-empty string S = S[0]S[1]...S[N-1] consisting of N characters. There are M queries, which are given in non-empty arrays P and Q, each consisting of M integers. The K-th query (0 ≤ K < M) requires you to find the minimal impact factor of nucleotides contained in the DNA sequence between positions P[K] and Q[K] (inclusive).

For example, consider string S = CAGCCTA and arrays P, Q such that:

P[0] = 2 Q[0] = 4 P[1] = 5 Q[1] = 5 P[2] = 0 Q[2] = 6

The answers to these M = 3 queries are as follows:

• The part of the DNA between positions 2 and 4 contains nucleotides G and C (twice), whose impact factors are 3 and 2 respectively, so the answer is 2.
• The part between positions 5 and 5 contains a single nucleotide T, whose impact factor is 4, so the answer is 4.
• The part between positions 0 and 6 (the whole string) contains all nucleotides, in particular nucleotide A whose impact factor is 1, so the answer is 1.

Write a function:

vector<int> solution(string &S, vector<int> &P, vector<int> &Q);

that, given a non-empty string S consisting of N characters and two non-empty arrays P and Q consisting of M integers, returns an array consisting of M integers specifying the consecutive answers to all queries.

Result array should be returned as a vector of integers.

For example, given the string S = CAGCCTA and arrays P, Q such that:

P[0] = 2 Q[0] = 4 P[1] = 5 Q[1] = 5 P[2] = 0 Q[2] = 6

the function should return the values [2, 4, 1], as explained above.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [1..100,000];
• M is an integer within the range [1..50,000];
• each element of arrays P, Q is an integer within the range [0..N − 1];
• P[K] ≤ Q[K], where 0 ≤ K < M;
• string S consists only of upper-case English letters A, C, G, T.

vector<int> solution(string &S, vector<int> &P, vector<int> &Q) {
    vector<int> ans;
    int A[S.length()+1];
    int C[S.length()+1];
    int G[S.length()+1];
    int T[S.length()+1];
    A[0] = 0;
    C[0] = 0;
    G[0] = 0;
    T[0] = 0;
    for (int i = 0; i < S.length(); i++)
    {
        A[i+1] = A[i];
        C[i+1] = C[i];
        G[i+1] = G[i];
        T[i+1] = T[i];
        switch (S[i])
        {
            case 'A':
                A[i+1] = A[i] + 1;
                break;
            case 'C':
                C[i+1] = C[i] + 1;
                break;
            case 'G':
                G[i+1] = G[i] + 1;
                break;
            case 'T':
                T[i+1] = T[i] + 1;
                break;
        }
    }
    for (int i = 0; i < P.size(); i++)
    {
        if (A[P[i]] < A[Q[i]+1])
        {
            ans.push_back(1);
            continue;
        }
        if (C[P[i]] < C[Q[i]+1])
        {
            ans.push_back(2);
            continue;
        }
        if (G[P[i]] < G[Q[i]+1])
        {
            ans.push_back(3);
            continue;
        }
        if (T[P[i]] < T[Q[i]+1])
        {
            ans.push_back(4);
            continue;
        }
    }
    return ans;
}

Detected time complexity: O(N + M)

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Example 1:

Input: head = [1,2,3,4,5], n = 2 Output: [1,2,3,5]

Example 2:

Input: head = [1], n = 1 Output: []

Example 3:

Input: head = [1,2], n = 1 Output: [1]

Constraints:

• The number of nodes in the list is sz.
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if (!head->next) return NULL;
        ListNode *ans = head, *cur = head;
        for (int i = 0; i < n; i++) cur = cur->next;
        if (!cur) return head->next;
        while (cur->next)
        {
            cur = cur->next;
            ans = ans->next;
        }
        ans->next = ans->next->next;
        return head;
    }
};

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example 1:

Input: digits = "23" Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:

Input: digits = "" Output: []

Example 3:

Input: digits = "2" Output: ["a","b","c"]

Constraints:

• 0 <= digits.length <= 4
• digits[i] is a digit in the range ['2', '9'].

class Solution {
public:
    map<char, vector<char>> al;
    string addDigits(vector<string>& ans, string s, string digits, int num)
    {
        string str = "";
        if (num < digits.length())
        {
            for (int i = 0; i < al[digits[num]].size(); i++)
            {
                str = s + al[digits[num]][i];
                addDigits(ans, str, digits, num + 1);
                if (num == digits.length() - 1)
                {
                    ans.push_back(str);
                }
            }
        }
        else if (num == 1)
        {
            ans.push_back(s);
        }
        return str;
    }
    vector<string> letterCombinations(string digits) {
        vector<string> ans;
        int start = 97;
        for (int i = 0; i < 8; i++)
        {
            if (i + 2 == 7)
            {
                al['7'].push_back('p');
                start++;
            }
            if (i + 2 == 9)
            {
                al['9'].push_back('w');
                start++;
            }
            for (int j = 0; j < 3; j++)
            {
                al[to_string(i + 2)[0]].push_back((char)(start+(3*i)+j));
            }
        }
        for (int i = 0; i < al[digits[0]].size(); i++)
        {
            string s(1, al[digits[0]][i]);
            addDigits(ans, s, digits, 1);
        }
        return ans;
    }
};

Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.

Return the sum of the three integers.

You may assume that each input would have exactly one solution.

Example 1:

Input: nums = [-1,2,1,-4], target = 1 Output: 2 Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Example 2:

Input: nums = [0,0,0], target = 1 Output: 0

Constraints:

• 3 <= nums.length <= 1000
• -1000 <= nums[i] <= 1000
• -104 <= target <= 104

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int ans = nums[0] + nums[1] + nums[2];
        int left, right, sum;
        for (int i = 0; i < nums.size() - 2; i++)
        {
            left = i + 1;
            right = nums.size() - 1;
            while (left < right)
            {
                sum = nums[i] + nums[left] + nums[right];
                if (abs(sum - target) < abs(ans - target)) ans = sum;
                
                if (sum > target) right--;
                else if (sum < target) left++;
                else break;
            }
        }
        return ans;
    }
};