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 an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

• 0 <= a, b, c, d < n
• a, b, c, and d are distinct.
• nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

Example 1:

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

Example 2:

Input: nums = [2,2,2,2,2], target = 8 Output: [[2,2,2,2]]

Constraints:

• 1 <= nums.length <= 200
• -109 <= nums[i] <= 109
• -109 <= target <= 109

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, long target) {
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        long left, right, sum;
        if (nums.size() >= 4)
        {
            for (int i = 0; i < nums.size() - 3; i++)
            {
                if (i > 0 && nums[i] == nums[i - 1]) continue;

                for (int j = i + 1; j < nums.size() - 2; j++)
                {
                    if (j > i + 1 && nums[j] == nums[j - 1]) continue;

                    left = j + 1;
                    right = nums.size() - 1;

                    while (left < right)
                    {
                        sum = (long)nums[i] + (long)nums[j] + (long)nums[left] + (long)nums[right];

                        if (sum < target) left++;
                        else if (sum > target) right--;
                        else
                        {
                            ans.push_back({ nums[i], nums[j], nums[left], nums[right] });

                            while (left < right && nums[left] == ans[ans.size() - 1][2]) left++;
                            while (left < right && nums[right] == ans[ans.size() - 1][3]) right--;
                        }
                    }
                }
            }
        }
        return ans;
    }
};

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;
    }
};