花花酱 LeetCode 192. Word Frequency

By zxi on March 28, 2018

Write a bash script to calculate the frequency of each word in a text file words.txt.

For simplicity sake, you may assume:

words.txt contains only lowercase characters and space ' ' characters.
Each word must consist of lowercase characters only.
Words are separated by one or more whitespace characters.

For example, assume that words.txt has the following content:

the day is sunny the the
the sunny is is

Your script should output the following, sorted by descending frequency:

the 4
is 3
sunny 2
day 1

Note:
Don’t worry about handling ties, it is guaranteed that each word’s frequency count is unique.

Solution

bash

# Author: Huahua

# Running time: 8 ms (beats 99.80%)

cat words.txt | tr -s " " "\n" | sort | uniq -c | sort -r | awk '{print $2, $1}'

花花酱 LeetCode 56. Merge Intervals

By zxi on October 14, 2017

Problem:

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

Idea:

Sweep line

Solution:

C++

// Author: Huahua

// Runtime: 12 ms

class Solution {

public:

vector<Interval> merge(vector<Interval>& intervals) {

if (intervals.empty()) return {};

std::sort(intervals.begin(), intervals.end(),

[](const Interval& a, const Interval& b){

return a.start < b.start;

});

vector<Interval> ans;

for (const auto& interval : intervals) {

if (ans.empty() || interval.start > ans.back().end) {

ans.push_back(interval);

} else {

ans.back().end = max(ans.back().end, interval.end);

}

return ans;

}

};

Python

"""

Author: Huahua

Runtime: 69 ms

"""

class Solution(object):

def merge(self, intervals):

ans = []

for interval in sorted(intervals, key=lambda x: x.start):

if not ans or interval.start > ans[-1].end:

ans.append(interval)

else:

ans[-1].end = max(ans[-1].end, interval.end)

return ans

Related Problems:

花花酱 LeetCode 451. Sort Characters By Frequency

By zxi on March 18, 2017

Given a string, sort it in decreasing order based on the frequency of characters.

Example 1:

Input:

"tree"

Output:

"eert"

Explanation:

'e' appears twice while 'r' and 't' both appear once.

So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

Example 2:

Input:

"cccaaa"

Output:

"cccaaa"

Explanation:

Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer.

Note that "cacaca" is incorrect, as the same characters must be together.

Example 3:

Input:

"Aabb"

Output:

"bbAa"

Explanation:

"bbaA" is also a valid answer, but "Aabb" is incorrect.

Note that 'A' and 'a' are treated as two different characters.

Solution:

class Solution {

public:

string frequencySort(string s) {

map<char, int> f;

for(char c:s) ++f[c];

vector<pair<int,char>> v;

for(auto& kv : f)

v.push_back({kv.second, kv.first});

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

stringstream ans;

for(auto& kv : v)

ans << string(kv.first, kv.second);

return ans.str();

}

};

Posts tagged as “sort”

花花酱 LeetCode 192. Word Frequency

Solution

bash

花花酱 LeetCode 56. Merge Intervals

花花酱 LeetCode 451. Sort Characters By Frequency