Biweekly Contest 10

Posted on | In , | |
Words count in article: 593 | Reading time ≈ 3

1213. Intersection of Three Sorted Arrays

Given three integer arrays arr1, arr2 and arr3 sorted in strictly increasing order, return a sorted array of only the integers that appeared in all three arrays.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<int> arraysIntersection(vector<int>& arr1, vector<int>& arr2, vector<int>& arr3) {
        vector<int> ret;
        for(int i=0; i<arr1.size(); i++)
        {
            int cur = arr1[i];
            if(find(arr2.begin(), arr2.end(), cur) != arr2.end() && find(arr3.begin(), arr3.end(), cur) != arr3.end())
                ret.push_back(arr1[i]);
        }
        return ret;
    }
};

1214. Two Sum BSTs

Given two binary search trees, return True if and only if there is a node in the first tree and a node in the second tree whose values sum up to a given integer target.

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
29
30
31
32
33
34
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    set<int> s;
    void dfs(TreeNode* root)
    {
        if(!root) return;
        dfs(root->left);
        dfs(root->right);
        s.insert(root->val);
    }
    
    bool helper(TreeNode* root, int target)
    {
        if(!root) return false;
        if(find(s.begin(), s.end(), target-root->val) != s.end())
            return true;
        return helper(root->left, target) || helper(root->right, target);
    }
    
    bool twoSumBSTs(TreeNode* root1, TreeNode* root2, int target) {
        s.clear();
        dfs(root1);
        return helper(root2, target);
    }
};

1215. Stepping Numbers

A Stepping Number is an integer such that all of its adjacent digits have an absolute difference of exactly 1. For example, 321 is a Stepping Number while 421 is not.

Given two integers low and high, find and return a sorted list of all the Stepping Numbers in the range [low, high] inclusive.

Constraints:

0 <= low <= high <= 2 * 10^9

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> countSteppingNumbers(int low, int high) {
        vector<int> ans;
        queue<int> q;
        int i, j;
        for(i=1; i<10 && i<=high; i++)
            q.push(i);
        if(!low) ans.push_back(0);
        while(!q.empty())
        {
            i = q.front();
            q.pop();
            if(i >= low) ans.push_back(i);
            j = i % 10;
            if(j && i*10LL+j-1 <= high) q.push(i*10+j-1);
            if(j<9 && i*10LL+j+1 <= high) q.push(i*10+j+1);
        }
        sort(ans.begin(), ans.end());
        return ans;
    }
};

1216. Valid Palindrome III

Given a string s and an integer k, find out if the given string is a K-Palindrome or not.

A string is K-Palindrome if it can be transformed into a palindrome by removing at most k characters from it.

Constraints:

1 <= s.length <= 1000

s has only lowercase English letters.

1 <= k <= s.length

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool isValidPalindrome(string s, int k) {
        int n = s.size();
        vector<vector<int>> dp(n+2, vector<int>(n+2));
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                if(s[i-1] == s[n-j+1-1])
                    dp[i][j] = dp[i-1][j-1]+1;
                else
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
        int ret = n-dp[n][n];
        return ret <= k;
    }
};
Donate? comment?