Posts tagged as “easy”

花花酱 LeetCode 933. Number of Recent Calls

By zxi on November 4, 2018

Problem

Write a class RecentCounter to count recent requests.

It has only one method: ping(int t), where t represents some time in milliseconds.

Return the number of pings that have been made from 3000 milliseconds ago until now.

Any ping with time in [t - 3000, t] will count, including the current ping.

It is guaranteed that every call to ping uses a strictly larger value of t than before.

Example 1:

Input: inputs = ["RecentCounter","ping","ping","ping","ping"], inputs = [[],[1],[100],[3001],[3002]]
Output: [null,1,2,3,3]

Note:

Each test case will have at most 10000 calls to ping.
Each test case will call ping with strictly increasing values of t.
Each call to ping will have 1 <= t <= 10^9.

Solution: Queue

Use a FIFO queue to track all the previous pings that are within 3000 ms to current.

Time complexity: Avg O(1), Total O(n)

Space complexity: O(n)

C++

class RecentCounter {

public:

RecentCounter() {}

int ping(int t) {

while (!q.empty() && t - q.front() > 3000) q.pop();

q.push(t);

return q.size();

}

private:

queue<int> q;

};

花花酱 LeetCode 929. Unique Email Addresses

By zxi on October 28, 2018

Every email consists of a local name and a domain name, separated by the @ sign.

For example, in alice@leetcode.com, alice is the local name, and leetcode.com is the domain name.

Besides lowercase letters, these emails may contain '.'s or '+'s.

If you add periods ('.') between some characters in the local name part of an email address, mail sent there will be forwarded to the same address without dots in the local name. For example, "alice.z@leetcode.com" and "alicez@leetcode.com" forward to the same email address. (Note that this rule does not apply for domain names.)

If you add a plus ('+') in the local name, everything after the first plus sign will be ignored. This allows certain emails to be filtered, for example m.y+name@email.com will be forwarded to my@email.com. (Again, this rule does not apply for domain names.)

It is possible to use both of these rules at the same time.

Given a list of emails, we send one email to each address in the list. How many different addresses actually receive mails?

Example 1:

Input: ["test.email+alex@leetcode.com","test.e.mail+bob.cathy@leetcode.com","testemail+david@lee.tcode.com"]
Output: 2
Explanation: "testemail@leetcode.com" and "testemail@lee.tcode.com" actually receive mails

Note:

1 <= emails[i].length <= 100
1 <= emails.length <= 100
Each emails[i] contains exactly one '@' character.

Solution:

Time complexity: O(n*l)
Space complexity: O(n*l)

C++

// Author: Huahua, 24 ms

class Solution {

public:

int numUniqueEmails(vector<string>& emails) {

unordered_set<string> s;

for (const string& email : emails) {

string e;

bool at = false;

bool plus = false;

for (char c : email) {

if (c == '.') {

if (!at) continue;

} else if (c == '@') {

at = true;

} else if (c == '+') {

if (!at) {

plus = true;

continue;

}

if (!at && plus) continue;

e += c;

}

s.insert(std::move(e));

}

return s.size();

}

};

花花酱 LeetCode 922. Sort Array By Parity II

By zxi on October 13, 2018

Problem

Given an array A of non-negative integers, half of the integers in A are odd, and half of the integers are even.

Sort the array so that whenever A[i] is odd, i is odd; and whenever A[i] is even, i is even.

You may return any answer array that satisfies this condition.

Example 1:

Input: [4,2,5,7]
Output: [4,5,2,7]
Explanation: [4,7,2,5], [2,5,4,7], [2,7,4,5] would also have been accepted.

Note:

2 <= A.length <= 20000
A.length % 2 == 0
0 <= A[i] <= 1000

Solution 1: Brute Force

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<int> sortArrayByParityII(vector<int>& A) {

vector<int> evens;

vector<int> odds;

for (int a : A)

if (a % 2 == 0)

evens.push_back(a);

else

odds.push_back(a);

auto it1 = begin(evens);

auto it2 = begin(odds);

for (int i = 0; i < A.size(); ++i) {

A[i] = *it1++;

swap(it1, it2);

}

return A;

}

};

花花酱 LeetCode 917. Reverse Only Letters

By zxi on October 6, 2018

Problem

Given a string S, return the “reversed” string where all characters that are not a letter stay in the same place, and all letters reverse their positions.

Example 1:

Input: "ab-cd"
Output: "dc-ba"

Example 2:

Input: "a-bC-dEf-ghIj"
Output: "j-Ih-gfE-dCba"

Example 3:

Input: "Test1ng-Leet=code-Q!"
Output: "Qedo1ct-eeLg=ntse-T!"

Note:

S.length <= 100
33 <= S[i].ASCIIcode <= 122
S doesn’t contain \ or "

Solution: Two Pointers

Time complexity: O(n)

Space complexity: O(1) – in place

C++/index

// Author: Huahua

class Solution {

public:

string reverseOnlyLetters(string S) {

int i = 0;

int j = S.length() - 1;

while (i < j) {

if (isalpha(S[i]) && isalpha(S[j])) {

swap(S[i++], S[j--]);

} else {

if (!isalpha(S[i])) ++i;

if (!isalpha(S[j])) --j;

}

return S;

}

};

C++/iter

// Author: Huahua

class Solution {

public:

string reverseOnlyLetters(string S) {

auto it1 = begin(S);

auto it2 = prev(end(S));

while (it1 < it2) {

if (isalpha(*it1) && isalpha(*it2)) {

swap(*it1++, *it2--);

} else {

if (!isalpha(*it1)) ++it1;

if (!isalpha(*it2)) --it2;

}

return S;

}

};

花花酱 LeetCode 28. Implement strStr()

By zxi on October 2, 2018

Problem

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = "hello", needle = "ll"
Output: 2

Example 2:

Input: haystack = "aaaaa", needle = "bba"
Output: -1

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C’s strstr() and Java’s indexOf().

Solution 1: Brute Force

Time complexity: O(mn)

Space complexity: O(1)

C++

// Author: Huahua, 4 ms

class Solution {

public:

int strStr(string haystack, string needle) {

const int l1 = haystack.length();

const int l2 = needle.length();

for (int i = 0; i <= l1 - l2; ++i) {

int j = 0;

while (j < l2 && haystack[i + j] == needle[j]) ++j;

if (j == l2) return i;

}

return -1;

}

};

Python3

# Author: Huahua

class Solution:

def strStr(self, haystack, needle):

l1 = len(haystack)

l2 = len(needle)

for i in range(l1 - l2 + 1):

if haystack[i:i+l2] == needle: return i

return -1