Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.
Example 1:
Input: s = "aaabb", k = 3 Output: 3 The longest substring is "aaa", as 'a' is repeated 3 times.
Example 2:
Input: s = "ababbc", k = 2 Output: 5 The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.
class Solution {
public:
int longestSubstring(string s, int k) {
return divideAndConqur(s, 0, s.size(), k);
}
// It takes O(logn) iterations and each iteration takes O(n) so the time
// complexity is O(nlogn).
int divideAndConqur(const string &s, int b, int e, int k) {
if ((e - b) < k) {
return 0;
}
int cnt[26]{}; // Initialize all to 0.
for (int i = b; i < e; ++i) {
const int val = s[i] - 'a';
cnt[val] += 1;
}
for (int i = b; i < e; ++i) {
const int val = s[i] - 'a';
if (cnt[val] < k) {
// If we found one element whose total < k, then any sub string containing
// that element cannot be taken into consideration.
return max(divideAndConqur(s, b, i, k), divideAndConqur(s, i+1, e, k));
}
}
return e - b;
}
};
Thanks to wfxr for enlightening.
One O(n) time complexity solution is here, but it consumes O(n) extra memory as well.
314. FACEBOOK Binary Tree Vertical Order Traversal
Given a binary tree, return the vertical order traversal of its nodes' values. (ie, from top to bottom, column by column).
If two nodes are in the same row and column, the order should be from left to right.
Examples:
- Given binary tree
[3,9,20,null,null,15,7],
3 /\ / \ 9 20 /\ / \ 15 7return its vertical order traversal as:
[ [9], [3,15], [20], [7] ]
- Given binary tree
[3,9,8,4,0,1,7],
3 /\ / \ 9 8 /\ /\ / \/ \ 4 01 7return its vertical order traversal as:
[ [4], [9], [3,0,1], [8], [7] ]
- Given binary tree
[3,9,8,4,0,1,7,null,null,null,2,5](0's right child is 2 and 1's left child is 5),
3 /\ / \ 9 8 /\ /\ / \/ \ 4 01 7 /\ / \ 5 2return its vertical order traversal as:
[ [4], [9,5], [3,0,1], [8,2], [7] ]
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
struct NodeColumn {
TreeNode *node;
int col;
};
struct Size {
int left;
int right;
};
Size GetColumnSize(TreeNode *root) {
if (root == nullptr) {
return Size{0, 0};
}
const Size &left = GetColumnSize(root->left);
const Size &right = GetColumnSize(root->right);
return Size {
std::max(left.left + 1, right.left - 1),
std::max(left.right - 1, right.right + 1)
};
}
vector<vector<int>> verticalOrder(TreeNode* root) {
vector<vector<int>> ret;
if (root == nullptr) {
return ret;
}
const Size &size = GetColumnSize(root);
ret.resize(size.left + size.right - 1, {});
// Traverse using queue.
std::queue<NodeColumn> trav;
trav.push(NodeColumn{root, size.left - 1});
while (!trav.empty()) {
const NodeColumn ¤t = trav.front();
trav.pop();
ret[current.col].push_back(current.node->val);
if (current.node->left) {
trav.push(NodeColumn{current.node->left, current.col - 1});
}
if (current.node->right) {
trav.push(NodeColumn{current.node->right, current.col + 1});
}
}
return ret;
}
};
273. Integer to English Words
Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 - 1.
For example,
123 -> "One Hundred Twenty Three" 12345 -> "Twelve Thousand Three Hundred Forty Five" 1234567 -> "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"
class Solution {
public:
void trim(string *str) {
while (*str->rbegin() == ' ') {
str->pop_back();
}
}
string join(const vector<string> &input) {
string ret;
for (const string &t : input) {
if (!t.empty()) {
ret.append(t);
ret.append(" ");
}
}
trim(&ret);
return ret;
}
string numberToWords(int num) {
if (num == 0) {
return "Zero";
}
static const vector<string> split = {
"",
"Thousand",
"Million",
"Billion",
"Trillion"
};
vector<string> all_tokens;
int i = 0;
while (num > 0) {
const int under_thou = num - (num / 1000) * 1000;
num /= 1000;
const string &token = BelowThousand(under_thou);
if (!token.empty()) {
all_tokens.push_back(join({
token, split[i]
}));
}
++i;
}
std::reverse(all_tokens.begin(), all_tokens.end());
return join(all_tokens);
}
string TokenTranslate(int num) {
static const map<int, string> mapping = {
{0, ""},
{1, "One"},
{2, "Two"},
{3, "Three"},
{4, "Four"},
{5, "Five"},
{6, "Six"},
{7, "Seven"},
{8, "Eight"},
{9, "Nine"},
{10, "Ten"},
{11, "Eleven"},
{12, "Twelve"},
{13, "Thirteen"},
{14, "Fourteen"},
{15, "Fifteen"},
{16, "Sixteen"},
{17, "Seventeen"},
{18, "Eighteen"},
{19, "Nineteen"},
{20, "Twenty"},
{30, "Thirty"},
{40, "Forty"},
{50, "Fifty"},
{60, "Sixty"},
{70, "Seventy"},
{80, "Eighty"},
{90, "Ninety"}
};
return mapping.at(num);
}
string BelowHundred(int num) {
// num < 100.
if (num < 20) {
return TokenTranslate(num);
}
int tens = (num / 10) * 10;
return join({
TokenTranslate(tens), TokenTranslate(num - tens)
});
}
string BelowThousand(int num) {
// num < 1000.
if (num < 100) {
return BelowHundred(num);
}
return join({
BelowHundred(num / 100), "Hundred", BelowHundred(num - (num / 100) * 100)
});
}
};
410. Split Array Largest Sum BAIDU
Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.
Note:
Given m satisfies the following constraint: 1 ≤ m ≤ length(nums) ≤ 14,000.
Examples:
Input: nums = [7,2,5,10,8] m = 2 Output: 18 Explanation: There are four ways to split nums into two subarrays. The best way is to split it into [7,2,5] and [10,8], where the largest sum among the two subarrays is only 18.
class Solution {
public:
int splitArray(vector<int>& nums, int m) {
if (nums.empty()) {
return 0;
}
if (nums.size() < m) {
return 0;
}
long max = sum(nums);
long min = MaxVal(nums);
while (min < max) {
const long mid = (min + max) / 2;
if (IsValid(nums, m, mid)) {
// It is valid to find a partition of m sub arrays with the
// largest sum <= mid.
// In this case, we should try a smaller mid to see whether
// there are better solutions.
max = mid;
} else {
// We increase mid to see whether there is valid solution.
min = mid + 1;
}
}
return min;
}
// Returns true if there is one partition of m with the largest sum <= max.
// This function can be done in O(n).
bool IsValid(const vector<int> &n, int m, long max) {
long sum = 0;
int group = 1;
for (const int i : n) {
if (sum + i <= max) {
// Put as many element as possible into previous partition.
sum += i;
} else {
// The previous partition ends, start a new partition.
sum = i;
++group;
}
if (group > m || sum > max) {
return false;
}
}
return true;
}
// Sum of vectors, using long because int will over flow.
long sum(const vector<int> &n) {
long ret = 0;
for (const int i : n) {
ret += i;
}
return ret;
}
// The max value in the vector.
int MaxVal(const vector<int> &n) {
int ret = 0;
for (const int i : n) {
ret = std::max(ret, i);
}
return ret;
}
};
161. One Edit Distance SNAPCHAT
Given two strings S and T, determine if they are both one edit distance apart.
class Solution {
public:
bool isOneEditDistance(string s, string t) {
if (s.empty() || t.empty()) {
return s.size() + t.size() == 1;
}
if (s.size() == t.size()) {
// When the two has the same size, check whether only one char differs.
int diff = 0;
for (int i = 0; i < s.size() && diff <= 1; ++i) {
// Put diff <= 1 here to early terminate the loop.
if (s.at(i) != t.at(i)) {
++diff;
}
}
return diff == 1;
}
// Find the shorter string.
const string &small = s.size() < t.size() ? s : t;
const string &large = s.size() < t.size() ? t : s;
if (small.size() + 1 != large.size()) {
// If the two has distance not equal to one, false.
return false;
}
for (int i = 0; i < small.size(); i++) {
if (small.at(i) != large.at(i)) {
// Find the first character mismatch, than compare the following characters.
return small.substr(i) == large.substr(i + 1);
}
}
return true;
}
};
36. Valid Sudoku
Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.
The Sudoku board could be partially filled, where empty cells are filled with the character '.'.
A partially filled sudoku which is valid.
Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.
class Solution {
public:
using BOA = vector<vector<char>>;
bool ValidOrAdd(bitset<9> *n, const char val) {
if (val != '.') {
const int p = val - '1';
if (n->test(p)) {
return false;
} else {
n->set(p);
return true;
}
}
return true;
}
bool isValidSudoku(const BOA &b) {
for (int i = 0; i < 9; i++) {
bitset<9> n;
for (int j = 0; j < 9; j++) {
if (!ValidOrAdd(&n, b[i][j])) {
return false;
}
}
}
for (int j = 0; j < 9; j++) {
bitset<9> n;
for (int i = 0; i < 9; i++) {
if (!ValidOrAdd(&n, b[i][j])) {
return false;
}
}
}
for (int i = 0; i < 9; i+=3) {
for (int j = 0; j < 9; j+=3) {
bitset<9> n;
for (int k = i; k < i + 3; k++) {
for (int f = j; f < j + 3; f++) {
if (!ValidOrAdd(&n, b[k][f])) {
return false;
}
}
}
}
}
return true;
}
};
37. Sudoku Solver SNAPCHAT
Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character '.'.
You may assume that there will be only one unique solution.
A sudoku puzzle...
...and its solution numbers marked in red.
class Solution {
public:
void solveSudoku(vector<vector<char>>& board) {
solve(board);
}
private:
using BOA = vector<vector<char>>;
using BIT = bitset<9>;
struct POS {
int r;
int c;
int cell() const {
return (r/3) * 3 + (c/3);
}
};
BIT row[10];
BIT col[10];
BIT cell[10];
void change(BIT *val, int num, bool bitval) {
if (bitval) {
val->set(num);
} else {
val->reset(num);
}
}
bool valid(const BOA &b, const POS &p, char val) {
// Returns true if it is OK to put val in (r, c).
const int test = val - '1';
return !(row[p.r].test(test)) && !(col[p.c].test(test)) && !(cell[p.cell()].test(test));
}
void set(BOA &b, const POS &p, char val) {
const int test = val - '1';
b[p.r][p.c] = val;
change(&row[p.r], test, true);
change(&col[p.c], test, true);
change(&cell[p.cell()], test, true);
}
void clear(BOA &b, const POS &p) {
const int test = b[p.r][p.c] - '1';
b[p.r][p.c] = '.';
change(&row[p.r], test, false);
change(&col[p.c], test, false);
change(&cell[p.cell()], test, false);
}
bool helper(BOA &b, vector<POS> &candi) {
if (candi.empty()) {
return true;
}
const POS p = *candi.rbegin();
candi.pop_back();
for (char d = '1'; d <= '9'; d++) {
if (valid(b, p, d)) {
set(b, p, d);
if (helper(b, candi)) return true;
clear(b, p);
}
}
candi.push_back(p);
return false;
}
void sort(vector<POS> &candi) {
std::sort(candi.begin(), candi.end(), [this](const POS &a, const POS &b) {
int c_a = row[a.r].count() + col[a.c].count() + cell[a.cell()].count();
int c_b = row[b.r].count() + col[b.c].count() + cell[b.cell()].count();
return c_a < c_b;
});
}
bool solve(BOA &board) {
vector<POS> candi;
for (int r = 0; r < 9; r++) {
for (int c = 0; c < 9; c++) {
const POS p {r, c};
if (board[p.r][p.c] != '.') {
set(board, p, board[p.r][p.c]);
} else {
candi.push_back(p);
}
}
}
sort(candi);
return helper(board, candi);
}
};
127. Word Ladder
Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:
- Only one letter can be changed at a time
- Each intermediate word must exist in the word list
For example,
Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Note:
- Return 0 if there is no such transformation sequence.
- All words have the same length.
- All words contain only lowercase alphabetic characters.
class Solution {
public:
using SET = unordered_set<string>;
int ladderLength(string beg, string end, unordered_set<string>& w) {
if (beg == end) {
return 1;
}
SET left, right, *pleft, *pright;
int dist = 2;
left.insert(beg);
right.insert(end);
w.erase(beg);
w.erase(end);
while (!left.empty() && !right.empty()) {
if (left.size() <= right.size()) {
// We plan to process the one with smaller size first.
// As it can be more balanced in that way.
pleft = &left;
pright = &right;
} else {
pleft = &right;
pright = &left;
}
SET temp; // Store all neighbors of elements in pleft.
for (string v : *pleft) {
for (int i = 0; i < v.size(); ++i) {
const char ori = v[i];
for (char d = 'a'; d <= 'z'; ++d) {
v[i] = d;
if (pright->find(v) != pright->end()) {
return dist;
}
if (w.find(v) != w.end()) {
temp.insert(v);
w.erase(v);
}
}
v[i] = ori;
}
}
swap(*pleft, temp);
++dist;
}
return 0;
}
};
253. Meeting Rooms II
Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.
For example,
Given [[0, 30],[5, 10],[15, 20]],
return 2.
class Solution {
public:
int minMeetingRooms(vector<Interval>& intervals) {
if(intervals.size() == 0) {
return 0;
}
map<int, int> map;
// We have to use map here as the keys need to be sorted.
// Thus the time complexity is O(nlogn).
for(auto interval : intervals) {
map[interval.start]++;
map[interval.end]--;
}
int count = 0;
int result = 0;
for(auto it = map.begin() ; it != map.end() ; ++it) {
count = count + it -> second;
result = max(result, count);
}
return result;
}
};
# Definition for an interval.
# class Interval(object):
# def __init__(self, s=0, e=0):
# self.start = s
# self.end = e
class Solution(object):
def minMeetingRooms(self, intervals):
"""
:type intervals: List[Interval]
:rtype: int
"""
if not intervals:
return 0
intervals.sort(key=lambda x: x.start)
rooms = []
end_time_of_first_room = intervals[0].end
heapq.heappush(rooms, end_time_of_first_room)
for i in xrange(1, len(intervals), 1):
start, end = intervals[i].start, intervals[i].end
earliest_room_end_time = rooms[0]
if start < earliest_room_end_time:
heapq.heappush(rooms, end)
else:
heapq.heappushpop(rooms, end)
return len(rooms)
/**
* Definition for an interval.
* struct Interval {
* int start;
* int end;
* Interval() : start(0), end(0) {}
* Interval(int s, int e) : start(s), end(e) {}
* };
*/
class Solution {
public:
int minMeetingRooms(vector<Interval>& intervals) {
if (intervals.empty()) {
return 0;
}
// Sort according to start time.
sort(intervals.begin(), intervals.end(), [](const Interval &a, Interval &b) {
return a.start < b.start;
});
// Top is min value, heap for the end times.
priority_queue<int, vector<int>, greater<int>> end_times;
end_times.push(intervals[0].end);
for (int i = 1; i < intervals.size(); ++i) {
const int end_t = intervals[i].end;
const int start_t = intervals[i].start;
if (start_t < end_times.top()) {
// Need a new room, as the next start time is earlier than the earliest end time.
end_times.push(end_t);
} else {
// One room is available for the next start meeting, use that room instead.
end_times.pop();
end_times.push(end_t);
}
}
// The size of the queue is the largest room used.
return end_times.size();
}
};
206. Reverse Linked List
Reverse a singly linked list.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}
ListNode *next = head->next;
ListNode *new_head = reverseList(next);
next->next = head;
head->next = nullptr;
return new_head;
}
};
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}
ListNode *p = head;
ListNode *q = head->next;
ListNode *temp = nullptr;
while (q) {
temp = q->next;
q->next = p;
p = q;
q = temp;
}
head->next = nullptr;
return p;
}
};
96. Unique Binary Search Trees
Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
For example,
Given n = 3, there are a total of 5 unique BST's.
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
class Solution {
public:
int numTrees(int n) {
vector<int> dp(n + 1, 0);
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; ++i) {
for (int j = 1; j <= i; j++) {
// put j as the root.
dp[i] += dp[j-1] * dp[i-j];
}
}
return dp[n];
}
};
151. Reverse Words in a String
Given an input string, reverse the string word by word.
For example,
Given s = "the sky is blue",
return "blue is sky the".
Update (2015-02-12):
For C programmers: Try to solve it in-place in O(1) space.
Clarification:
- What constitutes a word?
A sequence of non-space characters constitutes a word. - Could the input string contain leading or trailing spaces?
Yes. However, your reversed string should not contain leading or trailing spaces. - How about multiple spaces between two words?
Reduce them to a single space in the reversed string.
class Solution {
public:
void reverseWords(string &s) {
stripSpace(s);
reverse(s.begin(), s.end());
int begin = 0, end = 0;
while (begin < s.size()) {
end = begin;
while (end < s.size() && s[end] != ' ') {
++end;
}
reverse(s.begin() + begin, s.begin() + end);
begin = end + 1;
}
}
void stripSpace(string &s) {
if (s.empty()) {
return;
}
int p = 0;
int w = 0;
while (w < s.size() && s[w] == ' ') {
++w;
}
while (w < s.size()) {
if (s[w] == ' ') {
if (w + 1 < s.size() && s[w + 1] != ' ') {
s[p++] = s[w++];
continue;
}
} else {
s[p++] = s[w++];
continue;
}
++w;
}
s.resize(p);
}
};
403. Frog Jump
A frog is crossing a river. The river is divided into x units and at each unit there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.
Given a list of stones' positions (in units) in sorted ascending order, determine if the frog is able to cross the river by landing on the last stone. Initially, the frog is on the first stone and assume the first jump must be 1 unit.
If the frog's last jump was k units, then its next jump must be either k - 1, k, or k + 1 units. Note that the frog can only jump in the forward direction.
Note:
- The number of stones is ≥ 2 and is < 1,100.
- Each stone's position will be a non-negative integer < 231.
- The first stone's position is always 0.
Example 1:
[0,1,3,5,6,8,12,17] There are a total of 8 stones. The first stone at the 0th unit, second stone at the 1st unit, third stone at the 3rd unit, and so on... The last stone at the 17th unit. Return true. The frog can jump to the last stone by jumping 1 unit to the 2nd stone, then 2 units to the 3rd stone, then 2 units to the 4th stone, then 3 units to the 6th stone, 4 units to the 7th stone, and 5 units to the 8th stone.
Example 2:
[0,1,2,3,4,8,9,11] Return false. There is no way to jump to the last stone as the gap between the 5th and 6th stone is too large.
class Solution {
public:
using SET = unordered_set<int>;
void updateJump(unordered_map<int, SET> &s, int unit, int k) {
if (k > 0) {
const int next_unit = unit + k;
auto it = s.find(next_unit);
if (it != s.end()) {
it->second.insert(k);
}
}
}
bool canCross(vector<int>& stones) {
if (stones.empty()) {
return true;
}
// Stores all possible last-jumps for stone unit at a specific position.
unordered_map<int, SET> stones_to_jump = {{0, {0}}};
for (const int unit : stones) {
if (unit > 0) {
// Pre insert all stone unit into the map, this can
// facilitate a little.
stones_to_jump[unit] = {};
}
}
// This points to all possible last-jumps for the last stone unit.
auto final_iter = stones_to_jump.find(stones.back());
for (const int unit : stones) {
auto it = stones_to_jump.find(unit);
if (it->second.empty()) {
// If empty, then means no possible jumps to stone at <unit>
continue;
}
for (const int jump : it->second) {
// Update all other jumps starting from <unit>.
updateJump(stones_to_jump, unit, jump - 1);
updateJump(stones_to_jump, unit, jump);
updateJump(stones_to_jump, unit, jump + 1);
}
if (!final_iter->second.empty()) {
// This means we already find one solution, directly return.
return true;
}
}
return !final_iter->second.empty();
}
};
270. Closest Binary Search Tree Value
Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.
Note:
- Given target value is a floating point.
- You are guaranteed to have only one unique value in the BST that is closest to the target.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int ret_;
int closestValue(TreeNode* root, double target) {
if (root == nullptr) {
return 0;
}
ret_ = root->val;
return helper(root, target, abs(target - root->val));
}
int helper(TreeNode *root, double target, double dis) {
if (root == nullptr) {
return ret_;
}
const double new_dis = abs(target - root->val);
if (new_dis < dis) {
ret_ = root->val;
}
dis = min(new_dis, dis);
if (target < root->val) {
return helper(root->left, target, dis);
} else {
return helper(root->right, target, dis);
}
}
};
402. Remove K Digits
Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.
Note:
- The length of num is less than 10002 and will be ≥ k.
- The given num does not contain any leading zero.
Example 1:
Input: num = "1432219", k = 3 Output: "1219" Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.
Example 2:
Input: num = "10200", k = 1 Output: "200" Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.
Example 3:
Input: num = "10", k = 2 Output: "0" Explanation: Remove all the digits from the number and it is left with nothing which is 0.
class Solution {
public:
string removeKdigits(string num, const int k) {
if (num.size() <= k) {
return "0";
}
if (num == "0") {
return num;
}
string res;
// We always choose to pop out the largest value in the stack.
int deleted = 0;
for (int i = 0; i < num.size(); ++i) {
if (res.empty() && num[i] == '0') {
// Lead value cannot be 0. So skip to the next value.
continue;
}
if (deleted == k || res.empty() || num[i] >= res.back()) {
// 3 conditions:
// 1, We have deleted enough value, so simply insert all remains.
// 2, No available value right now, in this case num[i] != '0'
// by default so insert it.
// 3, The next value is larger, so insert it as it should
// have a higher priority to delete the the current
// top one in stack.
res.push_back(num[i]);
continue;
}
// Pop all previous string out.
// We meet a value smaller than the current stack top,
// so delete the current stack top.
res.pop_back();
--i;
++deleted;
}
// res: first element is not 0, but its length maybe longer or shorter
// as deleted may not equal to k.
res = res.substr(0, num.size() - k);
return res.empty() ? "0" : res;
}
};
289. Game of Life
According to the Wikipedia's article: "The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970."
Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):
- Any live cell with fewer than two live neighbors dies, as if caused by under-population.
- Any live cell with two or three live neighbors lives on to the next generation.
- Any live cell with more than three live neighbors dies, as if by over-population..
- Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
Write a function to compute the next state (after one update) of the board given its current state.
Follow up:
- Could you solve it in-place? Remember that the board needs to be updated at the same time: You cannot update some cells first and then use their updated values to update other cells.
- In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches the border of the array. How would you address these problems?
Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.
class Solution {
public:
using BOA = vector<vector<int>>;
int numlive(const BOA &b, const int i, const int j) {
int res;
for (int k = max(0, i - 1); k <= i + 1 && k < b.size(); ++k) {
for (int f = max(0, j - 1); f <= j + 1 && f < b[0].size(); ++f) {
if (k != i || f != j) {
res += (b[k][f] & 1);
}
}
}
return res;
}
void gameOfLife(BOA& b) {
if (b.empty() || b[0].empty()) {
return;
}
const int m = b.size();
const int n = b[0].size();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
const int num_live = numlive(b, i, j);
const bool is_live = (b[i][j] & 1);
// cout << is_live << " " << num_live << " " << i << " " << j << endl;
if (is_live) {
if (num_live < 2 || num_live > 3) {
// Die
} else {
// Live
b[i][j] |= 2;
}
} else {
if (num_live == 3) {
b[i][j] |= 2;
}
}
}
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
b[i][j] = (b[i][j] >> 1) & 1;
}
}
}
};
439. Ternary Expression Parser
Given a string representing arbitrarily nested ternary expressions, calculate the result of the expression. You can always assume that the given expression is valid and only consists of digits 0-9, ?, :, T and F (T and F represent True and False respectively).
Note:
- The length of the given string is ≤ 10000.
- Each number will contain only one digit.
- The conditional expressions group right-to-left (as usual in most languages).
- The condition will always be either
TorF. That is, the condition will never be a digit. - The result of the expression will always evaluate to either a digit
0-9,TorF.
Example 1:
Input: "T?2:3" Output: "2" Explanation: If true, then result is 2; otherwise result is 3.
Example 2:
Input: "F?1:T?4:5"
Output: "4"
Explanation: The conditional expressions group right-to-left. Using parenthesis, it is read/evaluated as:
"(F ? 1 : (T ? 4 : 5))" "(F ? 1 : (T ? 4 : 5))"
-> "(F ? 1 : 4)" or -> "(T ? 4 : 5)"
-> "4" -> "4"
Example 3:
Input: "T?T?F:5:3"
Output: "F"
Explanation: The conditional expressions group right-to-left. Using parenthesis, it is read/evaluated as:
"(T ? (T ? F : 5) : 3)" "(T ? (T ? F : 5) : 3)"
-> "(T ? F : 3)" or -> "(T ? F : 5)"
-> "F" -> "F"
class Solution {
public:
string parseTernary(string e) {
if (e.empty()) {
return "";
}
if (e.size() == 1) {
return e;
}
if (e[1] == ':') {
return e.substr(0, 1);
}
if (e[0] == 'T') {
return parseTernary(e.substr(2));
} else if (e[0] == 'F') {
int mat = 1;
int i = 2;
for (; i < e.size(); ++i) {
if (e[i] == '?') {
++mat;
} else if (e[i] == ':') {
--mat;
}
if (mat == 0) break;
}
return parseTernary(e.substr(i + 1));
} else {
return e.substr(0, 1);
}
}
};