跳至主要内容

16 篇文章 含有標籤「codility」

檢視所有標籤

Position of robot after given movements

· 閱讀時間約 1 分鐘

Assume that:

  • the length of string moves is within the range [1...100];
  • string moves is made only of the following characters: <, ^, >, v;
  • the robot never visits the same point twice, except for the starting point, which may be visited at the start and end of the robots path.

In your solution, focus on correctness. The performance of your solution will not be the focus of the assessment.

bool solution(string& moves)
{
    int up = 0, down = 0;
    int left = 0, right = 0;

    for (auto m : moves)
    {
        if (m == '<')
        {
         ++left;
        }
        else if (m == '^')
        {
            ++up;
        }
        else if (m == '>')
        {
            ++right;
        }
        else if (m == 'v')
        {
            ++down;
        }
    }
    return up == down && left == right;
};

int main()
{
    vector<string> moves = {"<", "<>^v", "<>^v", ">>>>>>>>>>>>>>>>>>>><<"};
    for (auto m : moves)
    {
        printf("%d\n", solution(m));
    }
}
  • T: $O(n)$
  • S: $O(1)$

gameWinner

· 閱讀時間約 1 分鐘

Wendy 和 Bob 輪流拿掉 w 和 b，只能拿掉被同樣字母包圍的，回傳誰贏。

給予一個陣列 colors = "wwwbbbbwww"

  1. Wendy 拿掉 index = 1 的 w，這時候 colors = "wwbbbbwww"
  2. Bob 拿掉 index = 3 的 b，這時候 colors = "wwbbbwww"
  3. Wendy 拿掉 index = 6 的 w，這時候 colors = "wwbbbww"
  4. Bob 拿掉 index = 3 的 b，這時候 colors = "wwbbww"
  5. Wendy 沒辦法拿了，所以 Bob 贏
#include <bits/stdc++.h>

using namespace std;

/*
 * Complete the 'gameWinner' function below.
 *
 * The function is expected to return a STRING.
 * The function accepts STRING colors as parameter.
 */

string gameWinner(string colors)
{
    int n = colors.size();

    int wendy = 0, bob = 0;

    for (int i = 1; i < n - 1; ++i)
    {
        // 如果字母被包圍的話
        if (colors[i - 1] == colors[i] && colors[i] == colors[i + 1])
        {
            // 如果字母是 w 的話，wendy 拿
            if (colors[i] == 'w')
            {
                ++wendy;
            }
            // 反之，bob 拿
            else
            {
                ++bob;
            }
        }
    }
    // 最後計算誰贏
    return (wendy > bob) ? "wendy" : "bob";
}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    string colors;
    getline(cin, colors);

    string result = gameWinner(colors);

    fout << result << "\n";

    fout.close();

    return 0;
}

  • T: $O()$
  • S: $O()$

Minimum Swaps to Sort

· 閱讀時間約 2 分鐘

https://www.geeksforgeeks.org/problems/minimum-swaps/1

Given an array of n distinct elements. Find the minimum number of swaps required to sort the array in strictly increasing order.

Example 1:

Input:
nums = {2, 8, 5, 4}

Output:
1

Explanation:
swap 8 with 4.

Example 2:

Input:
nums = {10, 19, 6, 3, 5}

Output:
2

Explanation:
swap 10 with 3 and swap 19 with 5.
#include <iostream>
#include <string>
#include <vector>
#include <utility>

using namespace std;

int minSwapsAscending(vector<int>& nums)
{
    int n = nums.size();

    vector<pair<int, int>> arr(n);
    for (int i = 0; i < n; i++)
    {
        arr[i] = {nums[i], i};
    }

    sort(arr.begin(), arr.end());

    vector<bool> seen(n);

    int swaps = 0;

    for (int i = 0; i < n; i++)
    {
        // If the element is already in the correct position or already visited
        if (seen[i] || arr[i].second == i)
            continue;

        int cycleSize = 0;
        int j = i;

        while (!seen[j])
        {
            seen[j] = true;
            j = arr[j].second;
            cycleSize++;
        }

        if (cycleSize > 0)
        {
            swaps += (cycleSize - 1);
        }
    }
    return swaps;
}

int minSwapsDescending(vector<int>& nums)
{
    int n = nums.size();

    vector<pair<int, int>> arrPos(n);
    for (int i = 0; i < n; i++)
    {
        arrPos[i] = {nums[i], i};
    }

    sort(arrPos.rbegin(), arrPos.rend());

    vector<bool> seen(n);

    int swaps = 0;

    for (int i = 0; i < n; i++)
    {
        if (seen[i] || arrPos[i].second == i)
        {
            continue;
        }

        int numOfCycles = 0;
        int j = i;

        while (!seen[j])
        {
            seen[j] = true;
            j = arrPos[j].second;
            numOfCycles++;
        }

        if (numOfCycles > 0)
        {
            swaps += (numOfCycles - 1);
        }
    }
    return swaps;
}

int main()
{
    vector<int> nums = {2, 8, 5, 4};
    int r1 = minSwapsAscending(nums); // swap 8 and 4
    int r2 = minSwapsDescending(nums); // swap 8 and 2, swap 2 and 5, swap 2 amd 4
    printf("Ascending: %d, Descending: %d\n", r1, r2);
}
  • T: $O(n \cdot \log n)$
  • S: $O(n)$

MissingInteger

· 閱讀時間約 1 分鐘

https://app.codility.com/programmers/lessons/4-counting_elements/missing_integer/

  • 找第一個出現的正整數
#include <bits/stdc++.h>

using namespace std;

int solution(vector<int> &A) {
    int n = A.size();

    // 建立一個 n + 1 長度的 vector
    // 如果數字出現過就 mark true
    vector<bool> seen(n + 1);

    for (int a : A)
    {
        // 因為題目只要求正整數，所以只求這個範圍內的
        if (1 <= a && a <= n + 1)
        {
            // 因為 N 最小的長度是 1
            // 所以要 - 1 從 0 開始算
            seen[a - 1] = true;
        }
    }

    // 從最前面開始找
    for (int i = 0; i < n + 1; ++i)
    {
        // 找沒出現過的數字，return i + 1
        if (!seen[i])
        {
            return i + 1;
        }
    }
    return -1;
}
  • T: $O(n)$
  • S: $O(n)$

Palindrome Minimization

· 閱讀時間約 2 分鐘

You are given a string S consisting of N letters. In a single move, you can remove a letter from either the left or the right end of S.

A palindrome is a word that reads the same both forwards and backwards. An empty string is not considered to be a palindrome. For example:

  • "aba", "c" and "xyzzyx are palindromes;
  • "fg", *abbac" and an empty string (*) are not palindromes.

Your task is to find the minimum number of moves required so that the resulting string is not a palindrome.

Write a function:

int solution(string &S);

that, given a string S consisting of N characters, returns the minimum number of moves needed.

Examples:

  1. Given S = "xyzx", the function should return 0 because S is already not a palindrome.
  2. Given S = "kayak", the function should retum 1. By deleting one letter from the left, you obtain the string "ayak", which is not a palindrome.
  3. Given S = "xxxx", the function should return 4. The only option is to delete all the letters one by one from S to obtain an empty string, which is not a palindrome.
  4. Given S = "abba", the function should return 1.

Write an efficient algorithm for the following assumptions:

  • string S is made only of lowercase letters (a-z);
  • N is an integer within the range [1...100,000].
#include<vector>
#include<string>

using namespace std;

int solution(string &S)
{
    int n = S.size();

    int left = 0, right = n - 1;

    bool isPalindrome = true;

    while (left < right)
    {
        if (S[left] != S[right])
        {
            isPalindrome = false;
        }
        ++left; --right;
    }

    if (!isPalindrome) return 0;

    bool isSame = true;

    for (int i = 1; i < n; ++i)
    {
        if (S[i] != S[0])
        {
            isSame = false; break;
        }
    }
    if (isSame) return n;
    return 1;
}

int main()
{
    vector<string> moves = {"xyzx", "kayak", "xxxx", "abba"};
    vector<int> ans = {0, 1, 4, 1};
    for (int i = 0; i < moves.size(); ++i)
    {
        printf("%d\n", solution(moves[i]) == ans[i]);
    }
}
  • T: $O()$
  • S: $O()$