花花酱 LeetCode 758. Bold Words in String

By zxi on January 8, 2018

题目大意：给你一个字符串和一些要加粗的单词，返回加粗后的HTML代码。

Problem:

Given a set of keywords words and a string S, make all appearances of all keywords in S bold. Any letters between  and  tags become bold.

The returned string should use the least number of tags possible, and of course the tags should form a valid combination.

For example, given that words = ["ab", "bc"] and S = "aabcd", we should return "aabcd". Note that returning "aabcd" would use more tags, so it is incorrect.

Note:

words has length in range [0, 50].
words[i] has length in range [1, 10].
S has length in range [0, 500].
All characters in words[i] and S are lowercase letters.

Solution:

C++

Time complexity: O(nL^2)

Space complexity: O(n + d)

d: size of dictionary

L: max length of the word which is 10.

// Author: Huahua

// Running time: 13 ms

class Solution {

public:

string boldWords(vector<string>& words, string S) {

const int kMaxWordLen = 10;

unordered_set<string> dict(words.begin(), words.end());

int n = S.length();

vector<int> bolded(n, 0);

for (int i = 0; i < n; ++i)

for (int l = 1; l <= min(n - i, kMaxWordLen); ++l)

if (dict.count(S.substr(i, l)))

std::fill(bolded.begin() + i, bolded.begin() + i + l, 1);

string ans;

for (int i = 0; i < n; ++i) {

if (bolded[i] && (i == 0 || !bolded[i - 1])) ans += "";

ans += S[i];

if (bolded[i] && (i == n - 1 || !bolded[i + 1])) ans += "";

}

return ans;

}

};

花花酱 LeetCode 760. Find Anagram Mappings

By zxi on January 8, 2018

题目大意：输出数组A中每个元素在数组B中的索引。

Given two lists Aand B, and B is an anagram of A. B is an anagram of A means B is made by randomizing the order of the elements in A.

We want to find an index mapping P, from A to B. A mapping P[i] = j means the ith element in A appears in B at index j.

These lists A and B may contain duplicates. If there are multiple answers, output any of them.

For example, given

1 2	A = [12, 28, 46, 32, 50] B = [50, 12, 32, 46, 28]

We should return

1	[1, 4, 3, 2, 0]

as P[0] = 1 because the 0th element of A appears at B[1], and P[1] = 4 because the 1st element of Aappears at B[4], and so on.

Solution:

C++

Time complexity: O(nlogn)

Space complexity: O(n)

// Author: Huahua

// Running time: 6 ms

class Solution {

public:

vector<int> anagramMappings(vector<int>& A, vector<int>& B) {

map<int, int> indices;

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

indices[B[i]] = i;

vector<int> ans;

for (const int a : A)

ans.push_back(indices[a]);

return ans;

}

};

C++ / No duplication

// Author: Huahua

// Running time: 6 ms

class Solution {

public:

vector<int> anagramMappings(vector<int>& A, vector<int>& B) {

map<int, vector<int>> indices;

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

indices[B[i]].push_back(i);

vector<int> ans;

for (const int a : A) {

ans.push_back(indices[a].back());

indices[a].pop_back();

}

return ans;

}

};

花花酱 LeetCode 264. Ugly Number II

By zxi on January 7, 2018

题目大意：让你找到第n个丑数。

Problem:

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note that 1 is typically treated as an ugly number, and n does not exceed 1690.

Solution:

C++ / O(n)

// Author: huahua

// Running time: 6 ms

class Solution {

public:

int nthUglyNumber(int n) {

static vector<int> nums{1};

static int i2 = 0;

static int i3 = 0;

static int i5 = 0;

while (nums.size() < n) {

const int next2 = nums[i2] * 2;

const int next3 = nums[i3] * 3;

const int next5 = nums[i5] * 5;

const int next = min(next2, min(next3, next5));

if (next == next2) ++i2;

if (next == next3) ++i3;

if (next == next5) ++i5;

nums.push_back(next);

}

return nums[n - 1];

}

};

C++ /query * O(NlogN)

// Author: Huahua

// Running time: 89 ms

class Solution {

public:

int nthUglyNumber(int n) {

vector<int> nums;

for (long a = 1; a <= INT_MAX; a *= 2)

for (long b = a; b <= INT_MAX; b *= 3)

for (long c = b; c <= INT_MAX; c *= 5)

nums.push_back(c);

std::sort(nums.begin(), nums.end());

return nums[n - 1];

}

};

C++ / static variables O(NlogN) + query*O(1)

// Author: Huahua

// Running time: 7 ms

class Solution {

public:

int nthUglyNumber(int n) {

static vector<int> nums;

if (nums.empty()) {

for (long a = 1; a <= INT_MAX; a *= 2)

for (long b = a; b <= INT_MAX; b *= 3)

for (long c = b; c <= INT_MAX; c *= 5)

nums.push_back(c);

std::sort(nums.begin(), nums.end());

}

return nums[n - 1];

}

};

C++ / table O(1)
leetcode_264_table.cc

花花酱 LeetCode 758. Bold Words in String

花花酱 LeetCode 760. Find Anagram Mappings

花花酱 LeetCode 264. Ugly Number II

Related Problems:

花花酱 LeetCode 263. Ugly Number

花花酱 LeetCode 167. Two Sum II – Input array is sorted

Huahua's Tech Road

花花酱 LeetCode 758. Bold Words in String

花花酱 LeetCode 760. Find Anagram Mappings

花花酱 LeetCode 264. Ugly Number II

Related Problems:

花花酱 LeetCode 263. Ugly Number

花花酱 LeetCode 167. Two Sum II – Input array is sorted