Amazon OA2 - Coding 20+题 C++

简书原创，转载请联系作者

// Right Rotation
bool rightRotation(string a, string b) {
    if (a.empty() || b.empty() || a.size() != b.size())
        return false;
    string x = a + a;
    return (x.find(b) != string::npos);
}

// Gray Code
// Two consecutive values differ in only one bit
bool grayCode(int a, int b) {
    int x = a ^ b;
    int count = 0;
    while (x) {
        x = x & (x - 1);
        count++;
    }
    return count == 1;
}
int grayCode(int a, int b) {
    const int W = sizeof(int) * 8;
    int x = a ^ b;
    int count = 0;
    for (int i = 0; i < W; i++)
        if ((x >> i) & 1)
            count++;
    return count == 1;
}

// Longest Palindromic Substring (LeetCode)
string longestPalindrome(string s) {
    const int n = s.size();
    bool f[n][n];
    for (int k = 0; k < n; k++) {
        for (int i = 0; i + k < n; i++) {
            int j = i + k;
            f[i][j] = (s[i] == s[j]) && (k <= 1 || f[i + 1][j - 1]);
        }
    }
    
    for (int k = n - 1; k >= 0; k--) {
        for (int i = 0; i + k < n; i++) {
            int j = i + k;
            if (f[i][j])
                return s.substr(i, j - i + 1);
        }
    }
    return "";
}

// Valid Parentheses (LeetCode)
bool isValid(string s) {
    stack<char> brackets;
    unordered_map<char, char> cache;
    cache[')'] = '(';
    cache['}'] = '{';
    cache[']'] = '[';
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{')
            brackets.push(c);
        else if (c == ')' || c == ']' || c == '}') {
            if (brackets.empty() || brackets.top() != cache[c])
                return false;
            else
                brackets.pop();
        }
    }
    return brackets.empty();
}

// Topological Sorting
// Course Schedule (LeetCode)
// Detect Cycle in a Directed Graph <=> Topological Sorting for Directed Acyclic Graph (DAG)
// Topological Sorting for a graph is not possible if the graph is not a DAG.
// 1. 从有向图中选取一个没有前驱的顶点
// 2. 从有向图中删去此顶点以及所有以它为起始节点的边
// 3. 重复上述两步：图空——拓扑排序成功；图不空,但找不到无前驱的顶点——有环
// 需要设一个数组inDegree[w]，记录顶点的入度数
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
    vector<vector<int>> adjacency(numCourses);
    vector<int> indegree(numCourses);
    for (auto pre: prerequisites) {
        adjacency[pre.second].push_back(pre.first);
        indegree[pre.first]++;
    }

    queue<int> s; // 或者stack<int> s;
    for (int i = 0; i < numCourses; i++)
        if (indegree[i] == 0)
            s.push(i);
    int count = 0;
    while (!s.empty()) {
        int v = s.front(); // int v = s.top(); 对应stack
        s.pop();
        count++;
        for (int u : adjacency[v]) {
            indegree[u]--;
            if (indegree[u] == 0)
                s.push(u);
        }
    }
    return (count == numCourses);
}

// Merge Two Sorted Lists (LeetCode)
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode dummy(-1);
    ListNode *p = l1, *q = l2, *r = &dummy;
    while (p && q) {
        if (p->val < q->val) {
            r->next = p;
            r = p;
            p = p->next;                
        } else {
            r->next = q;
            r = q;
            q = q->next;
        }
    }
    r->next = (p ? p : q);
    return dummy.next;
}

// Copy List with Random Pointer (LeetCode)
RandomListNode *copyRandomList(RandomListNode *head) {
    if (head == NULL)
        return NULL;
    unordered_map<RandomListNode*, RandomListNode*> cache;
    RandomListNode dummy(-1);
    RandomListNode *p = head, *q = &dummy;
    while (p) {
        q->next = new RandomListNode(p->label);
        q = q->next;
        cache[p] = q;
        p = p->next;
    }
    p = head;
    while (p) {
        if (p->random)
            cache[p]->random = cache[p->random];
        p = p->next;
    }
    return dummy.next;
}

// Reverse Linked List (LeetCode)
ListNode* reverseList(ListNode* head) {
    if (head == NULL || head->next == NULL)
        return head;
    ListNode *pre = head, *cur = head->next, *next;
    pre->next = NULL;
    while(cur) {
        next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}

// Reverse Second Half of Linked List
ListNode* reverseList(ListNode* head) {
    if (head == NULL || head->next == NULL)
        return head;
    ListNode *slow = head, *fast = head;
    while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    ListNode *pre = slow->next, *cur = slow->next->next, *next;
    pre->next = NULL;
    while(cur) {
        next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }
    slow->next = pre;
    return head;
}

// Subtree of Another Tree (LeetCode)
bool isSubtree(TreeNode* s, TreeNode* t) {
    if (t == NULL)
        return true;
    if (s == NULL)
        return false;
    if (s->val == t->val && isSametree(s, t))
        return true;
    return isSubtree(s->left, t) || isSubtree(s->right, t);
}
bool isSametree(TreeNode* s, TreeNode* t) {
    if (s == NULL || t == NULL)
        return s == t;
    return (s->val == t->val) && isSametree(s->left, t->left) && isSametree(s->right, t->right);
}

// Two Sum (LeetCode)
vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> value_index_map;
    for (int i = 0; i < nums.size(); i++) {
        int desired = target - nums[i];
        if (value_index_map.find(desired) != value_index_map.end()) {
            vector<int> result = {value_index_map[desired], i};
            return result;
        }
        value_index_map[nums[i]] = i;
    }
}

// K-Nearest Points
// 时间复杂度：O(NlogK)
// 空间复杂度： O(K) 
struct Point {
    double x;
    double y;
    Point(double _x, double _y): x(_x), y(_y) {}
};

double squaredDistance(Point a, Point b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
typedef bool (*cmp)(Point, Point);
Point global_origin = Point(0, 0);
bool compare(Point a, Point b) {
    return squaredDistance(a, global_origin) < squaredDistance(b, global_origin);
}

vector<Point> kNearestPoint(vector<Point> points, Point origin, int k) {
    global_origin = origin;
    priority_queue<Point, vector<Point>, cmp> pq(compare);
    for (int i = 0; i < points.size(); i++) {
        pq.push(points[i]);
        if (i >= k)
            pq.pop();
    }
    vector<Point> res;
    for (int i = 0; i < k; i++) {
        res.push_back(pq.top());
        pq.pop();
    }
    return res;
}

// Overlap Rectangle
bool overlapRectangle(Point l1, Point r1, Point l2, Point r2)
{
    // If one rectangle is on left side of other
    if (l1.x > r2.x || l2.x > r1.x)
        return false;
    // If one rectangle is above other
    if (l1.y < r2.y || l2.y < r1.y)
        return false;
    return true;
}

// Search a 2D Matrix II (LeetCode)
// Integers in each row are sorted in ascending from left to right.
// Integers in each column are sorted in ascending from top to bottom.
bool searchMatrix(vector<vector<int>>& matrix, int target) {
    if (matrix.empty() || matrix[0].empty())
        return false;
    const int n = matrix.size(), m = matrix[0].size();
    int i = n - 1, j = 0;
    while (i >= 0 && j < m) {
        if (matrix[i][j] == target)
            return true;
        else if (matrix[i][j] > target)
            i--;
        else
            j++;
    }
    return false;
}

// 3Sum Closest (LeetCode)
// 左右夹逼
int threeSumClosest(vector<int>& nums, int target) {
    int diff = INT_MAX, result;
    sort(nums.begin(), nums.end());
    for (int i = 0; i < nums.size() - 2; ++i) {
        int j = i + 1, k = nums.size() - 1;
        int cur_target = target - nums[i];
        while (j < k) {
            if (abs(nums[j] + nums[k] - cur_target) < diff) {
                diff = abs(nums[j] + nums[k] - cur_target);
                result = nums[i] + nums[j] + nums[k];
            }
            if (nums[j] + nums[k] < cur_target)
                j++;
            else if (nums[j] + nums[k] > cur_target)
                k--;
            else
                break;                   
        }
        if (diff == 0)
            break;
        while (nums[i + 1] == nums[i] && i < nums.size() - 2)
            i++;
    }
    return result;
}

// 2Sum Closest
int twoSumClosest(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());
    int diff = INT_MAX, res;
    int i = 0, j = nums.size() - 1;
    while (i < j) {
        int sum = nums[i] + nums[j];
        if (abs(sum - target) < diff) {
            res = sum;
            diff = abs(sum - target);
        }
        if (sum < target)
            i++;
        else if (sum > target)
            j--;
        else
            break;
    }
    return res;
}

// Rotate Image (LeetCode)
// 首先沿对角线翻转一次，然后沿水平中线翻转一次
void rotate(vector<vector<int>>& matrix) {
    int n = matrix.size();
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < n - i - 1; j++)
            swap(matrix[i][j], matrix[n - 1 - j][n - 1 - i]);
    for(int i = 0; i < n / 2; i++)
        for (int j = 0; j < n; j++)
            swap(matrix[i][j], matrix[n - 1 - i][j]);
}

// Sliding Window Maximum (LeetCode)
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    if (nums.empty())
        return vector<int>();
    vector<int> result(nums.size() - k + 1);
    priority_queue<pair<int, int>> maxpq;
    for (int i = 0; i < k - 1; i++)
        maxpq.push(make_pair(nums[i], i));
    for (int i = 0; i < result.size(); i++) {
        maxpq.push(make_pair(nums[i + k - 1], i + k - 1));
        while (maxpq.top().second < i) {
            maxpq.pop();
        }
        result[i] = maxpq.top().first;
    }
    return result;
}

// Linked List Cycle II
ListNode *detectCycle(ListNode *head) {
    ListNode *p = head, *q = head;
    while (q && q->next) {
        p = p->next;
        q = q->next->next;
        if (p == q) {
            q = head;
            while (p != q) {
                p = p->next;
                q = q->next;
            }
            return p;
        }
    }
    return NULL;
}

// Round Robin - Average Waiting Time
double roundRobin(vector<int> arriveTime, vector<int> executionTime, int q) {
    queue<pair<int, int> > requests;
    int i = 0, curTime;
    double totalWaitingTime = 0;
    while (i < arriveTime.size() || !requests.empty()) {
        if (!requests.empty()) {
            int arrTime = requests.front().first;
            int exeTime = requests.front().second;
            requests.pop();
            totalWaitingTime += (curTime - arrTime);
            curTime += min(exeTime, q);
            while (i < arriveTime.size() && arriveTime[i] < curTime) {
                requests.push(make_pair(arriveTime[i], executionTime[i]));
                i++;
            }
            if (exeTime > q)
                requests.push(make_pair(curTime, exeTime - q));
        } else {
            requests.push(make_pair(arriveTime[i], executionTime[i]));
            curTime = arriveTime[i];
            i++;
        }
    }
    return totalWaitingTime / arriveTime.size();
}

// Shortest Job First - Average Waiting Time
struct Task {
    int arrTime;
    int exeTime;
    Task(int a, int e) : arrTime(a), exeTime(e) {}
    bool operator<(const Task &other) const {
        if (exeTime == other.exeTime)
            return arrTime > other.arrTime;
        return exeTime > other.exeTime;
    }
};
double shortestJobFirst(vector<int> arriveTime, vector<int> executionTime) {
    priority_queue<Task> pq;
    for (int i = 0; i < arriveTime.size(); i++)
        pq.push(Task(arriveTime[i], executionTime[i]));
    double totalWaitingTime = 0;
    int curTime = pq.top().arrTime;
    while (!pq.empty()) {
        int arrTime = pq.top().arrTime;
        int exeTime = pq.top().exeTime;
        pq.pop();
        if (curTime < arrTime)
            curTime = arrTime;
        else
            totalWaitingTime += (curTime - arrTime);
        curTime += exeTime;
    }

    return totalWaitingTime / arriveTime.size();
}

// Arithmetic Sequence
// Count of AP (Arithmetic Progression) Subsequences in an array
// 求长度至少为3的等差数列的个数

// Minimum Spanning Tree
// Kruskal's algorithm
// implemented with disjoint-set data structure
// KRUSKAL(G):
// 1 A = ∅
// 2 foreach v ∈ G.V:
// 3    MAKE-SET(v)
// 4 foreach (u, v) in G.E ordered by weight(u, v), increasing:
// 5    if FIND-SET(u) ≠ FIND-SET(v):
// 6       A = A ∪ {(u, v)}
// 7       UNION(u, v)
// 8 return A
vector<int> parent(n, -1);
int find(vector<int>& parent, int i) {
    if (parent[i] == -1)
        return i;
    return find(parent, parent[i]);
}
void Union(vector<int>& parent, int i, int j, int& circles) {
    // can't use the function name union(), union is a c++ keyword
    int x = find(parent, i);
    int y = find(parent, j);
    if (x != y) {
        parent[x] = y;
    }
}