Unique Word Abbreviation
An abbreviation of a word follows the form <first letter><number><last letter>. Below are some examples of word abbreviations:
a) it --> it (no abbreviation)
1
b) d|o|g --> d1g
1 1 1
1---5----0----5--8
c) i|nternationalizatio|n --> i18n
1
1---5----0
d) l|ocalizatio|n --> l10n
Assume you have a dictionary and given a word, find whether its abbreviation is unique in the dictionary. A word's abbreviation is unique if no other word from the dictionary has the same abbreviation.
Example:
Given dictionary = [ "deer", "door", "cake", "card" ]
isUnique("dear") -> false
isUnique("cart") -> true
isUnique("cane") -> false
isUnique("make") -> true
-----------------------------------------------------------------
COME_BACK
看清题意
class ValidWordAbbr {
public:
string getAbre(string s) {
int len = s.length();
if (len > 1) {
s = s[0] + to_string(len - 2) + s[len - 1];
}
return s;
}
ValidWordAbbr(vector<string> &dictionary) {
for (int i = 0; i < dictionary.size(); i++) {
string abre = getAbre(dictionary[i]);
if (dic.find(abre) == dic.end()) {
vector<string> second;
second.push_back(dictionary[i]);
dic[abre] = second;
}else {
dic[abre].push_back(dictionary[i]);
}
}
}
bool isUnique(string word) {
string abre = getAbre(word);
if (dic.find(abre) == dic.end()) return true;
return dic[abre][0] == word && dic[abre].size() == 1;
}
private:
unordered_map<string,vector<string>> dic;
};
// Your ValidWordAbbr object will be instantiated and called as such:
// ValidWordAbbr vwa(dictionary);
// vwa.isUnique("hello");
// vwa.isUnique("anotherWord");
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?
---------------------------------------------------------------------
额外空间
class Solution {
public:
vector<int> row;
vector<int> col;
bool isLive(int i, int j, int m, int n, vector<vector<int>>& board) {
if (i < 0 || j < 0 || i == m || j == n) return false;
return board[i][j];
}
void gameOfLife(vector<vector<int>>& board) {
int m = board.size();
int n = board[0].size();
vector<vector<int>> rt(m, vector<int>(n));
row = {-1,-1,-1,0,0,1,1,1};
col = {-1,0,1,-1,1,-1,0,1};
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int numOfLives = 0;
for (int k = 0; k < 8; k++) {
if (isLive(row[k] + i,col[k] + j, m, n, board)) {
numOfLives++;
}
}
if (numOfLives < 2 || numOfLives > 3) rt[i][j] = 0;
else if (board[i][j] && numOfLives <= 3) rt[i][j] = 1;
else if (numOfLives == 3) rt[i][j] = 1;
}
}
board = rt;
}
};
constant space
用-1来表示之前为0，现在为1. -2来表示之前为1，现在为0
0 -> -1 -> 1
1 -> -2 -> 0
class Solution {
public:
vector<int> row;
vector<int> col;
bool isLive(int i, int j, int m, int n, vector<vector<int>>& board) {
if (i < 0 || j < 0 || i == m || j == n) return false;
if (board[i][j] == 0 || board[i][j] == -1) return false;
return true;
}
void gameOfLife(vector<vector<int>>& board) {
int m = board.size();
int n = board[0].size();
row = {-1,-1,-1,0,0,1,1,1};
col = {-1,0,1,-1,1,-1,0,1};
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int numOfLives = 0;
for (int k = 0; k < 8; k++) {
if (isLive(row[k] + i,col[k] + j, m, n, board)) {
numOfLives++;
}
}
if (board[i][j] && numOfLives < 2) board[i][j] = -2;
else if (board[i][j] && (numOfLives == 3 || numOfLives == 2)) continue;
else if (board[i][j] && numOfLives > 3) board[i][j] = -2;
else if (numOfLives == 3) board[i][j] = -1;
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == -1) board[i][j] = 1;
if (board[i][j] == -2) board[i][j] = 0;
}
}
}
};
Flip Game
You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -, you and your friend take turns to flip twoconsecutive "++" into "--". The game ends when a person can no longer make a move and therefore the other person will be the winner.
Write a function to compute all possible states of the string after one valid move.
For example, given s = "++++", after one move, it may become one of the following states:
[
"--++",
"+--+",
"++--"
]
If there is no valid move, return an empty list [].
---------------------------------------------
class Solution {
public:
vector<string> generatePossibleNextMoves(string s) {
vector<string> rt;
for (int i = 1; i < s.length(); i++) {
if (s[i] == '+' && s[i - 1] == '+') {
s[i] = '-';
s[i - 1] = '-';
rt.push_back(s);
s[i] = '+';
s[i - 1] = '+';
}
}
return rt;
}
};
Flip Game II
You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -, you and your friend take turns to flip twoconsecutive "++" into "--". The game ends when a person can no longer make a move and therefore the other person will be the winner.
Write a function to determine if the starting player can guarantee a win.
For example, given s = "++++", return true. The starting player can guarantee a win by flipping the middle "++" to become "+--+".
Follow up:
Derive your algorithm's runtime complexity.
--------------------------------------------------------------
递归
T(n) = n * T(n - 1)
= n * (n - 1) * T(n - 2)
= n * (n - 1) * (n - 2) * T(n - 3)
...
= n!
class Solution {
public:
bool canWin(string s) {
for (int i = 1; i < s.length(); i++) {
if (s[i] == '+' && s[i - 1] == '+') {
s[i] = '-';
s[i - 1] = '-';
if (!canWin(s)) return true;
s[i] = '+';
s[i - 1] = '+';
}
}
return false;
}
};
COME_BACK
game theory的方法可以达到O(n^2)
Find Median from Data Stream
Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.
Examples:
[2,3,4] , the median is 3
[2,3], the median is (2 + 3) / 2 = 2.5
Design a data structure that supports the following two operations:
- void addNum(int num) - Add a integer number from the data stream to the data structure.
- double findMedian() - Return the median of all elements so far.
For example:
add(1)
add(2)
findMedian() -> 1.5
add(3)
findMedian() -> 2
---------------------------------------------------------------------------
2个queue，还有其他方法吗
一个TreeSet加2个指针，跟2个heap原理是一样的
class MedianFinder {
public:
struct cmp {
bool operator() (int i1, int i2) {
return i1 > i2;
}
};
// Adds a number into the data structure.
void addNum(int num) {
small.push(num);
int temp = small.top();
small.pop();
large.push(temp);
temp = large.top();
large.pop();
if (small.size() > large.size()) {
large.push(temp);
}else {
small.push(temp);
}
}
// Returns the median of current data stream
double findMedian() {
if ((small.size() + large.size()) % 2 == 0) {
return (small.top() + large.top()) / 2.0;
}else {
return small.top();
}
}
private:
priority_queue<int> small;
priority_queue<int,vector<int>,cmp> large;
};
// Your MedianFinder object will be instantiated and called as such:
// MedianFinder mf;
// mf.addNum(1);
// mf.findMedian();
Binary Tree Longest Consecutive Sequence
Given a binary tree, find the length of the longest consecutive sequence path.
The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path need to be from parent to child (cannot be the reverse).
For example,
1
\
3
/ \
2 4
\
5
Longest consecutive sequence path is 3-4-5, so return 3.
2
\
3
/
2
/
1
Longest consecutive sequence path is 2-3,not3-2-1, so return 2.
-------------------------------------------------------
/**
* 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:
void dfs(TreeNode* root, int cur, int &maxL, int target) {
if (root == NULL) return;
if (root->val == target) {
cur++;
}else {
cur = 1;
}
maxL = max(maxL,cur);
dfs(root->left, cur, maxL, root->val + 1);
dfs(root->right, cur, maxL, root->val + 1);
}
int longestConsecutive(TreeNode* root) {
int maxL = 0;
if (root == NULL) return 0;
dfs(root,0,maxL,root->val);
return maxL;
}
};
