跳至主要内容

closestNumbers

· 閱讀時間約 1 分鐘

給予一個陣列 numbers,輸出出兩者之差最小的組合。

例如 numbers = [6, 2, 4, 10],輸出:

2 4
4 6
#include <bits/stdc++.h>

using namespace std;

string ltrim(const string &);
string rtrim(const string &);


/*
* Complete the 'closestNumbers' function below.
*
* The function accepts INTEGER_ARRAY numbers as parameter.
*/

void closestNumbers(vector<int> numbers)
{
int n = numbers.size();

if (n <= 1) return;

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

int minDiff = numbers[1] - numbers[0];

for (int i = 2; i < n; ++i)
{
minDiff = min(minDiff, numbers[i] - numbers[i - 1]);
}

unordered_map<int, int> m;

for (int i = 1; i < n; ++i)
{
if (numbers[i] - numbers[i - 1] == minDiff)
{
printf("%d %d\n", numbers[i - 1], numbers[i]);
}
}
}
int main()
{
string numbers_count_temp;
getline(cin, numbers_count_temp);

int numbers_count = stoi(ltrim(rtrim(numbers_count_temp)));

vector<int> numbers(numbers_count);

for (int i = 0; i < numbers_count; i++) {
string numbers_item_temp;
getline(cin, numbers_item_temp);

int numbers_item = stoi(ltrim(rtrim(numbers_item_temp)));

numbers[i] = numbers_item;
}

closestNumbers(numbers);

return 0;
}

string ltrim(const string &str) {
string s(str);

s.erase(
s.begin(),
find_if(s.begin(), s.end(), not1(ptr_fun<int, int>(isspace)))
);

return s;
}

string rtrim(const string &str) {
string s(str);

s.erase(
find_if(s.rbegin(), s.rend(), not1(ptr_fun<int, int>(isspace))).base(),
s.end()
);

return s;
}

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

Count number of squares in a rectangle

· 閱讀時間約 1 分鐘

Given a m x n rectangle, how many squares are there in it?

class Solution {
public:
int countSquares(int m, int n) {
int count = 0;
for (int i = 1; i <= min(m, n); ++i) {
count += (m - i + 1) * (n - i + 1);
}
return count;
}
};
  • T: $O(N)$
  • S: $O(1)$

FrogJmp

· 閱讀時間約 1 分鐘
#include <bits/stdc++.h>

using namespace std;

int solution(int X, int Y, int D)
{
return ceil((Y - X) * 1.0 / D);
}
  • T: $O(1)$
  • S: $O(1)$

BinaryGap

· 閱讀時間約 1 分鐘

https://app.codility.com/programmers/lessons/1-iterations/binary_gap/

#include <bits/stdc++.h>

using namespace std;

int solution(int N)
{
int maxGap = 0, curGap = 0;

// 這個 loop 移除 N 前面的所有 0,直到遇到第一個 1 為止。這是因為 leading zero 不會形成有效的間隙。
while (N > 0 && N % 2 == 0)
{
N /= 2;
}

// 走訪剩餘的二進位數字
while (N > 0)
{
int digits = N % 2;

// digits 等於 0 代表是在 gap 中
if (digits == 0)
{
++curGap;
}
else
{
// digits 不等於 0 代表 gap 結束
if (curGap)
{
// 這時候計算 maxGap 最大是多少,並且 reset curGap
maxGap = max(curGap, maxGap);
curGap = 0;
}

}
N /= 2;
}
return maxGap;
}
  • T: $O()$
  • S: $O()$

TapeEquilibrium

· 閱讀時間約 1 分鐘

https://app.codility.com/programmers/lessons/3-time_complexity/tape_equilibrium/

  • 初始化 head = A[0]tail = accumulate(A.begin() + 1, A.end(), 0)
  • 再用一個迴圈加一個元素、減一個元素,比 minDiff 的大小
#include <bits/stdc++.h>
using namespace std;

int solution(vector<int> &A)
{
int n = A.size();
int head = A[0];
int tail = accumulate(A.begin() + 1, A.end(), 0);

int minDiff = abs(head - tail);

for (int i = 1; i < n - 1; ++i)
{
head += A[i];
tail -= A[i];
int cur = abs(head - tail);
minDiff = min(minDiff, cur);
}
return minDiff;
}
  • T: $O(n)$
  • S: $O(1)$

Filter Installation Strategy

· 閱讀時間約 3 分鐘

There are N houses along the street. Carbon filters are already installed in some of them. We would like to install filters in the remaining houses (those that do not possess them yet). Two types of filter, named 'a' and 'b' are being used. The filters work best if no three adjacent houses have the same type of filter. The houses are represented as a string of characters a, b' and ? (a' and 'b' denote a house with a filter of a given type installed; "? represents a house with no filter yet. Your task Is to make a plan of the filter types to be installed in the houses that do not yet have them.

Write a function

string solution(string& S)

Given a string S of length N, returns a string that is the result of replacing each '?' in string S with an 'a' or a'b' character and does not contain three identical consecutive letters (in other words, neither "aaa" nor bbb* may occur in the processed string). Examples:

  1. Given S = "a?bb", your function should return "aabb".
  2. Given S = "??abb*, your function should return "ababb", "bbabb" or "baabb"
  3. Given S = 'a?b?aa", your function should return "aabbaa".
  4. Given S = "aa??aa", your function should return "aabbaa"

Write an efficient algorithm for the following assumptions:

  1. string S is made only of the following characters: 'a', 'b' and/or '?
  2. N is an integer within the range [1...500,000);
  3. it is always possible to create a plan so that there are no three identical consecutive filters.
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

string solution(string &S)
{
vector<int> seen;

// 這邊先建立一個 seen 數列,方便操作
// 例如以 a?bb 來說,就會 return [0, 0, 1, 0, -1, -1, 0, 0]
for (char c : s)
{
if (c == 'a')
{
seen.push_back(1);
}
else if (c == 'b')
{
seen.push_back(-1);
}
else
{
seen.push_back(0);
}
}

seen.insert(seen.begin(), {0, 0});
seen.insert(seen.end(), {0, 0});

int n = seen.size();

auto helper = [&seen](int i)
{
// 如果遇到問號的話
if (seen[i] == 0)
{
vector<int> sums = {seen[i - 2] + seen[i - 1], seen[i - 1] + seen[i + 1], seen[i + 1] + seen[i + 2]};
if (find(sums.begin(), sums.end(), 2) != sums.end())
{
// 如果相鄰的兩個 'a',則填入 'b'
seen[i] = -1;
} else if (find(sums.begin(), sums.end(), -2) != sums.end())
{
// 如果相鄰的兩個 'b',則填入 'a'
seen[i] = 1;
}
}
};

// 由左到右走訪
for (int i = 2; i < n - 2; ++i)
{
helper(i);
}

// 由右到左走訪
for (int i = n - 3; i > 1; --i)
{
helper(i);
}


// 由左到右走訪,如果遇到 0
for (int i = 2; i < n - 2; ++i) {
if (seen[i] == 0)
{
// 檢查前一個元素是 1 還是 -1
seen[i] = (seen[i - 1] > 0) ? -1 : 1;
}
}

// 將數列填入 res
string res;
for (int i = 2; i < n - 2; ++i)
{
if (seen[i] == 1)
{
res += 'a';
} else if (seen[i] == -1) {
res += 'b';
}
}

return res;
}

int main()
{
vector<string> s = {"a?bb", "??abb", "a?b?aa", "aa??aa"};
for (auto c : s)
{
cout << solution(s) << endl;
}
}
  • T: $O()$
  • S: $O()$