花花酱 LeetCode 443. String Compression

By zxi on March 24, 2018

Problem

题目大意：对一个string进行in-place的run length encoding。

https://leetcode.com/problems/string-compression/description/

Given an array of characters, compress it in-place.

The length after compression must always be smaller than or equal to the original array.

Every element of the array should be a character (not int) of length 1.

After you are done modifying the input array in-place, return the new length of the array.

Follow up:
Could you solve it using only O(1) extra space?

Example 1:

Input:
["a","a","b","b","c","c","c"]

Output:
Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]

Explanation:
"aa" is replaced by "a2". "bb" is replaced by "b2". "ccc" is replaced by "c3".

Example 2:

Input:
["a"]

Output:
Return 1, and the first 1 characters of the input array should be: ["a"]

Explanation:
Nothing is replaced.

Example 3:

Input:
["a","b","b","b","b","b","b","b","b","b","b","b","b"]

Output:
Return 4, and the first 4 characters of the input array should be: ["a","b","1","2"].

Explanation:
Since the character "a" does not repeat, it is not compressed. "bbbbbbbbbbbb" is replaced by "b12".
Notice each digit has it's own entry in the array.

Note:

All characters have an ASCII value in [35, 126].
1 <= len(chars) <= 1000.

Solution

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 9 ms

class Solution {

public:

int compress(vector<char>& chars) {

const int n = chars.size();

int p = 0;

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

int count = 1;

while (i < n && chars[i] == chars[i - 1]) { ++i; ++count; }

chars[p++] = chars[i - 1];

if (count == 1) continue;

for (char c : to_string(count))

chars[p++] = c;

}

return p;

}

};

花花酱 LeetCode 433. Minimum Genetic Mutation

By zxi on March 24, 2018

Problem

题目大意：给你一个基因库，问一个基因最少需要变异多少次才能变为另外一个基因。每次变异只能修改一个字符，并且必须在基因库里。

https://leetcode.com/problems/minimum-genetic-mutation/description/

A gene string can be represented by an 8-character long string, with choices from "A", "C", "G", "T".

Suppose we need to investigate about a mutation (mutation from “start” to “end”), where ONE mutation is defined as ONE single character changed in the gene string.

For example, "AACCGGTT" -> "AACCGGTA" is 1 mutation.

Also, there is a given gene “bank”, which records all the valid gene mutations. A gene must be in the bank to make it a valid gene string.

Now, given 3 things – start, end, bank, your task is to determine what is the minimum number of mutations needed to mutate from “start” to “end”. If there is no such a mutation, return -1.

Note:

Starting point is assumed to be valid, so it might not be included in the bank.
If multiple mutations are needed, all mutations during in the sequence must be valid.
You may assume start and end string is not the same.

Example 1:

start: "AACCGGTT"
end:   "AACCGGTA"
bank: ["AACCGGTA"]

return: 1

Example 2:

start: "AACCGGTT"
end:   "AAACGGTA"
bank: ["AACCGGTA", "AACCGCTA", "AAACGGTA"]

return: 2

Example 3:

start: "AAAAACCC"
end:   "AACCCCCC"
bank: ["AAAACCCC", "AAACCCCC", "AACCCCCC"]

return: 3

Solution: BFS Shortest Path

Time complexity: O(n^2)

Space complexity: O(n)

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int minMutation(string start, string end, vector<string>& bank) {

queue<string> q;

q.push(start);

unordered_set<string> visited;

visited.insert(start);

int mutations = 0;

while (!q.empty()) {

size_t size = q.size();

while (size--) {

string curr = std::move(q.front()); q.pop();

if (curr == end) return mutations;

for (const string& gene : bank) {

if (visited.count(gene) || !validMutation(curr, gene)) continue;

visited.insert(gene);

q.push(gene);

}

++mutations;

}

return -1;

}

private:

bool validMutation(const string& s1, const string& s2) {

int count = 0;

for (int i = 0; i < s1.length(); ++i)

if (s1[i] != s2[i] && count++) return false;

return true;

}

};

花花酱 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 553. Optimal Division

By zxi on March 22, 2018

Problem

https://leetcode.com/problems/optimal-division/description/

题目大意：给你一个连除的表达式，让你加一些括号使得表达式的值最大。

Given a list of positive integers, the adjacent integers will perform the float division. For example, [2,3,4] -> 2 / 3 / 4.

However, you can add any number of parenthesis at any position to change the priority of operations. You should find out how to add parenthesis to get the maximum result, and return the corresponding expression in string format. Your expression should NOT contain redundant parenthesis.

Example:

Input: [1000,100,10,2]
Output: "1000/(100/10/2)"
Explanation:
1000/(100/10/2) = 1000/((100/10)/2) = 200
However, the bold parenthesis in "1000/((100/10)/2)" are redundant, 
since they don't influence the operation priority. So you should return "1000/(100/10/2)". 

Other cases:
1000/(100/10)/2 = 50
1000/(100/(10/2)) = 50
1000/100/10/2 = 0.5
1000/100/(10/2) = 2

Note:

The length of the input array is [1, 10].
Elements in the given array will be in range [2, 1000].
There is only one optimal division for each test case.

Solution: Math

For: X1/X2/X3/…/Xn, X1/(X2/X3/…/Xn) > X1/X2/(X3/…/Xn) > X1/X2/X3/(…/Xn)

X1/(X2/X3/…/Xn) is the max value.

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 5 ms

class Solution {

public:

string optimalDivision(vector<int>& nums) {

string ans = to_string(nums[0]);

if (nums.size() == 1) return ans;

else if (nums.size() == 2) return ans + "/" + to_string(nums[1]);

ans += "/(" + to_string(nums[1]);

for (int i = 2; i < nums.size(); ++i)

ans += "/" + to_string(nums[i]);

ans += ")";

return ans;

}

};

花花酱 LeetCode 541. Reverse String II

By zxi on March 21, 2018

Problem

题目大意：把字符串分成块，每块长度2k，单独反转每一块的前k的字符。

https://leetcode.com/problems/reverse-string-ii/description/

Given a string and an integer k, you need to reverse the first k characters for every 2k characters counting from the start of the string. If there are less than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and left the other as original.Example:

Input: s = "abcdefg", k = 2
Output: "bacdfeg"

Restrictions:

The string consists of lower English letters only.
Length of the given string and k will in the range [1, 10000]

Solution

C++

// Author: Huahua

// Running time: 9 ms

class Solution {

public:

string reverseStr(string s, int k) {

const int n = s.length();

for (int i = 0; i <= n / k; i += 2)

std::reverse(s.begin() + i * k, s.begin() + min(n, (i + 1) * k));

return s;

}

};

Posts published in “String”

花花酱 LeetCode 443. String Compression

Problem

Solution

花花酱 LeetCode 433. Minimum Genetic Mutation

Problem

Solution: BFS Shortest Path

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

Problem

Solution

花花酱 LeetCode 553. Optimal Division

Problem

Example:

Note:

Solution: Math

花花酱 LeetCode 541. Reverse String II

Problem

Solution

Related Problems