Posts tagged as “easy”

花花酱 LeetCode 806. Number of Lines To Write String

By zxi on March 24, 2018

Problem

题目大意：给你每个字母的宽度，以及一个字符串。问一共需要多少行和多少列才能把这个字符串打印出来。将设每行的宽度是100。

We are to write the letters of a given string S, from left to right into lines. Each line has maximum width 100 units, and if writing a letter would cause the width of the line to exceed 100 units, it is written on the next line. We are given an array widths, an array where widths[0] is the width of ‘a’, widths[1] is the width of ‘b’, …, and widths[25] is the width of ‘z’.

Now answer two questions: how many lines have at least one character from S, and what is the width used by the last such line? Return your answer as an integer list of length 2.

Example :
Input: 
widths = [10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]
S = "abcdefghijklmnopqrstuvwxyz"
Output: [3, 60]
Explanation: 
All letters have the same length of 10. To write all 26 letters,
we need two full lines and one line with 60 units.

Example :
Input: 
widths = [4,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]
S = "bbbcccdddaaa"
Output: [2, 4]
Explanation: 
All letters except 'a' have the same length of 10, and 
"bbbcccdddaa" will cover 9 * 10 + 2 * 4 = 98 units.
For the last 'a', it is written on the second line because
there is only 2 units left in the first line.
So the answer is 2 lines, plus 4 units in the second line.

Note:

The length of S will be in the range [1, 1000].
S will only contain lowercase letters.
widths is an array of length 26.
widths[i] will be in the range of [2, 10].

Solution: Simulation

Time Complexity: O(n)

Space Complexity: O(1)

// Author: Huahua

class Solution {

public:

vector<int> numberOfLines(vector<int>& widths, string S) {

int lines = 1;

int units = 0;

for (char c : S) {

if (units + widths[c - 'a'] > 100) {

++lines;

units = 0;

}

units += widths[c - 'a'];

}

return {lines, units};

}

};

花花酱 LeetCode 804. Unique Morse Code Words

By zxi on March 24, 2018

Problem

题目大意：给你一些单词，问这些单词的莫斯密码共有几种形式。

International Morse Code defines a standard encoding where each letter is mapped to a series of dots and dashes, as follows: "a" maps to ".-", "b" maps to "-...", "c" maps to "-.-.", and so on.

For convenience, the full table for the 26 letters of the English alphabet is given below:

[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]

Now, given a list of words, each word can be written as a concatenation of the Morse code of each letter. For example, “cab” can be written as “-.-.-….-“, (which is the concatenation “-.-.” + “-…” + “.-“). We’ll call such a concatenation, the transformation of a word.

Return the number of different transformations among all words we have.

Example:
Input: words = ["gin", "zen", "gig", "msg"]
Output: 2
Explanation: 
The transformation of each word is:
"gin" -> "--...-."
"zen" -> "--...-."
"gig" -> "--...--."
"msg" -> "--...--."

There are 2 different transformations, "--...-." and "--...--.".

Note:

The length of words will be at most 100.
Each words[i] will have length in range [1, 12].
words[i] will only consist of lowercase letters.

Solution: HashTable

Time Complexity: O(n)

Space Complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int uniqueMorseRepresentations(vector<string>& words) {

vector<string> m{".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};

unordered_set<string> s;

for (const string& word : words) {

string code;

for (char c : word)

code += m[c - 'a'];

s.insert(code);

}

return s.size();

}

};

花花酱 LeetCode 447. Number of Boomerangs

By zxi on March 24, 2018

Problem

Given n points in the plane that are all pairwise distinct, a “boomerang” is a tuple of points (i, j, k) such that the distance between i and j equals the distance between i and k (the order of the tuple matters).

Find the number of boomerangs. You may assume that n will be at most 500 and coordinates of points are all in the range [-10000, 10000] (inclusive).

Example:

Input:
[[0,0],[1,0],[2,0]]

Output:
2

Explanation:
The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]]

Solution: HashTable

For each point, compute the distance to the rest of the points and count.

if there are k points that have the same distance to current point, then there are P(k,2) = k*k-1 Boomerangs.

for example, p1, p2, p3 have the same distance to p0, then there are P(3,2) = 3 * (3-1) = 6 Boomerangs

(p1, p0, p2), (p1, p0, p3)

(p2, p0, p1), (p2, p0, p3)

(p3, p0, p1), (p3, p0, p2)

C++

// Author: Huahua

// Running time: 210 ms (beats 83.33%)

class Solution {

public:

int numberOfBoomerangs(vector<pair<int, int>>& points) {

int ans = 0;

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

unordered_map<int, int> dist(points.size());

for (int j = 0; j < points.size(); ++j) {

const int dx = points[i].first - points[j].first;

const int dy = points[i].second - points[j].second;

++dist[dx * dx + dy * dy];

}

for (const auto& kv : dist)

ans += kv.second * (kv.second - 1);

}

return ans;

}

};

Solution 2: Sorting

dist = [1, 2, 1, 2, 1, 5]

sorted_dist = [1, 1, 1, 2, 2, 5], 1*3, 2*2, 5*1

ans = 3*(3-1) + 2 * (2 – 1) * 1 * (1 – 1) = 8

Time complexity: O(n*nlogn)

Space complexity: O(n)

// Author: Huahua

// Running time: 150 ms (beats 98.52%)

class Solution {

public:

int numberOfBoomerangs(vector<pair<int, int>>& points) {

const int n = points.size();

int ans = 0;

vector<int> dist(points.size());

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

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

const int dx = points[i].first - points[j].first;

const int dy = points[i].second - points[j].second;

dist[j] = dx * dx + dy * dy;

}

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

for (int j = 1; j < n; ++j) {

int k = 1;

while (j < n && dist[j] == dist[j - 1]) { ++j; ++k; }

ans += k * (k - 1);

}

return ans;

}

};

花花酱 LeetCode 434. Number of Segments in a String

By zxi on March 23, 2018

Problem

题目大意：返回字符串中的非空白字符连续的字串数量。

https://leetcode.com/problems/number-of-segments-in-a-string/description/

Count the number of segments in a string, where a segment is defined to be a contiguous sequence of non-space characters.

Please note that the string does not contain any non-printable characters.

Example:

Input: "Hello, my name is John"
Output: 5

Solution

Be aware of special cases: like ” “.

Time complexity: O(n)

Space complexity: O(1)

C++

class Solution {

public:

int countSegments(string s) {

if (s.empty()) return 0;

int ans = 0;

int i = 0;

while (i < s.length()) {

while (i < s.length() && s[i] == ' ') ++i;

if (i == s.length()) break;

while (i < s.length() && s[i] != ' ') ++i;

++ans;

++i;

}

return ans;

}

};

Python3

"""

Author: Huahua

Running time: 40 ms

"""

class Solution:

def countSegments(self, s):

return len(s.split())

花花酱 LeetCode 94. Binary Tree Inorder Traversal

By zxi on March 23, 2018

Problem

Given a binary tree, return the inorder traversal of its nodes’ values.

For example:
Given binary tree [1,null,2,3],

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

Solution: Recursion

Time complexity: O(n)

Space complexity: O(h)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

vector<int> inorderTraversal(TreeNode* root) {

vector<int> ans;

inorderTraversal(root, ans);

return ans;

}

private:

void inorderTraversal(TreeNode* root, vector<int>& ans) {

if (root == nullptr) return;

inorderTraversal(root->left, ans);

ans.push_back(root->val);

inorderTraversal(root->right, ans);

}

};

Solution 2: Iterative

// Author: Huahua

// Running time: 3 ms

lass Solution {

public:

vector<int> inorderTraversal(TreeNode* root) {

if (root == nullptr) return {};

vector<int> ans;

stack<TreeNode*> s;

TreeNode* curr = root;

while (curr != nullptr || !s.empty()) {

while (curr != nullptr) {

s.push(curr);

curr = curr->left;

}

curr = s.top(); s.pop();

ans.push_back(curr->val);

curr = curr->right;

}

return ans;

}

};