Leetcode 14: Longest Common Prefix
Write a function to find the longest common prefix string amongst an array of strings.
题目大意: M 个 string 组成的array, 求这些string的最长公共前缀
分析： 一般求最大，最小，有几种算法： 1. 直接求， 暴力解法。 2. DP 3. Best first search
这题需要一一比较每个字符串中的每一个字符，找到一个不相等就return， 否则，每个string的index 都往后移动一位。这样的计算过程，让我联想到merge K sorted array/list这种用Best first search 来求解的题目，initial state 放进priority_queue，然后进行expand_rule来对priority_queue进行操作，控制每个index移动。 但是这题不需要priority_queue,因为不需要比大小，只要各位的char相等，就必须都向后移，不需要控制index的移动，根据这样的特点，其实只要一个变量控制index 位置的移动，需要用一个for loop来检测每个string在index的位置是否相等。
一开始想看看有没有更加优化的方法，但是觉得这个题目最优解就只有o(N*M)的时间复杂度
//O(N * M)
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
string rst = "";
//sanity check
if (strs.size() == 0) return rst;
if (strs.size() == 1) return strs[0];
for (int j = 0;; j++)
for (int i = 0; i < strs.size()-1; i++) {
if (j < strs[i].size() && j < strs[i+1].size() && (strs[i][j] == strs[i+1][j])) {
continue;
} else {
return strs[i].substr(0, j);
}
}
return rst;
}
};
updated:
对于一眼上看去不知道题目属于哪个类型，用什么算法解的题目，首先提供给面试官暴力的解法， 然后想下时间空间复杂度， 比不会做好
暴力解法： O（n*m）
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
//sanity checkn
if (strs.size() == 0) return "";
for (int i = 0; i < strs[0].size(); i++) {
char tmp = strs[0][i];
for (int j = 1; j < strs.size(); j++) {
if (tmp != strs[j][i]) {
return strs[0].substr(0, i);
}
}
}
return strs[0];
}
};
Tuesday, June 23, 2015
Friday, June 19, 2015
Leetcode 32: Longest valid parentheses
Leetcode 32: Longest valid parentheses
Given a string containing just the characters
For
Another example is
找出最长的有效（）对， 一开始对这个题目没有思路，最先想到的是找最长的（）对，用dp来做，但是dp的做法想到的是对输入的字符串一点点分，判断有没有（）对，有多长。 其实这个题目很巧妙，不需要用dp来做，对于valid parentheses的判断，用stack来做就好，回头看前面的元素是否匹配，怎么记录消掉的长度，这题很巧妙的地方在于存在stack里面的是char的index，而不是char，一开始想的是存char，如果正好匹配就消除并且记录长度，但是这样记录长度很麻烦，存index就很方便了，每次消掉一对消掉的长度可以用current index - index in the top of the stack来记录，每次消掉就update max的值，当然要注意stack为empty时的一些判断。
class Solution {
public:
int longestValidParentheses(string s) {
//sanity check
if (s.size() == 0) return 0;
stack<int> st; //stack stores the index of the chars
//when (), update the length, the current index - top element in stack
int max_len = 0;
for (int i = 0; i < s.size(); i++) {
if (st.empty()) st.push(i);
else if (s[st.top()] == '(' && s[i] == ')') { //match, update max_len
st.pop();
if (!st.empty()) max_len = max(max_len, i - st.top());
else max_len = max(max_len, i+1);
}else {
st.push(i);
}
}
return max_len;
}
};
Given a string containing just the characters
'(' and ')', find the length of the longest valid (well-formed) parentheses substring.
For
"(()", the longest valid parentheses substring is "()", which has length = 2.
Another example is
")()())", where the longest valid parentheses substring is "()()", which has length = 4.找出最长的有效（）对， 一开始对这个题目没有思路，最先想到的是找最长的（）对，用dp来做，但是dp的做法想到的是对输入的字符串一点点分，判断有没有（）对，有多长。 其实这个题目很巧妙，不需要用dp来做，对于valid parentheses的判断，用stack来做就好，回头看前面的元素是否匹配，怎么记录消掉的长度，这题很巧妙的地方在于存在stack里面的是char的index，而不是char，一开始想的是存char，如果正好匹配就消除并且记录长度，但是这样记录长度很麻烦，存index就很方便了，每次消掉一对消掉的长度可以用current index - index in the top of the stack来记录，每次消掉就update max的值，当然要注意stack为empty时的一些判断。
class Solution {
public:
int longestValidParentheses(string s) {
//sanity check
if (s.size() == 0) return 0;
stack<int> st; //stack stores the index of the chars
//when (), update the length, the current index - top element in stack
int max_len = 0;
for (int i = 0; i < s.size(); i++) {
if (st.empty()) st.push(i);
else if (s[st.top()] == '(' && s[i] == ')') { //match, update max_len
st.pop();
if (!st.empty()) max_len = max(max_len, i - st.top());
else max_len = max(max_len, i+1);
}else {
st.push(i);
}
}
return max_len;
}
};
Leetcode 125: Valid Palindrome
Leetcode 125: valid Palindrome
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For example,
永远会记得这题，这题是面qualtrics时的原题，我记得我当时还没有做到这一题，或者很早之前做的完全没有印象，当时拿到这个题目的时候，首先想到的方法是先对 输入的数据进行预处理，使其变成只有a-z的string，我记得当时面试官说你这样就对原来的input进行了修改，我当时没有明白过来是什么意思，不对input修改怎么做，后来面试过后再想了想发现原来是可以直接在递归的时候单独对每个char进行处理，这样整个字符串就只用scan一遍就可以了，如果预处理的话，需要scan 两遍啊！！！！！我太笨了！
这个题目，对于不需要考虑的特殊字符可以直接跳过，那么怎么判断一个字符合不合法呢？ 如果这个字符是0-9、a-z/A-Z之间就是合法的，然后对于合法的字符需要统一到小写或者大写字符上面去。 可以用一个isValid函数来进行判断。
在leetcode上面，用recursion对palindrome进行判断，能通过小集合不能通过大集合， 出现runtime error。 一开始对出现这个问题不能理解，因为不能发现时间复杂度有什么区别，也不能进一步优化了，后来才知道原来一般的recursion对空间复杂度都是有要求的，如果输入的数据太大，会很消耗stack上面的空间，这样也能导致程序出现问题，但是如果用iteration代替recursion，就能消除对空间复杂度上的依赖。
所以，对于recursion 和iteration都能解决的题目，如果recursion 和iteration 写起来其实难度相当，那么优先选用iteration来做。 这样能节省空间。
class Solution {
private:
bool isValid(string &s, int i) {
if (isdigit(s[i]) || isalpha(s[i])) {
if (s[i] <= 'Z' && s[i] >= 'A')s[i] = tolower(s[i]);
return true;
}else {
return false;
}
}
public:
bool isPalindrome(string s) {
//sanity check
if (s.size() == 0) return true;
int start = 0;
int end = s.size()-1;
while (start < end) {
if (!isValid(s, start)) {
start++;
}else if (!isValid(s, end)) {
end--;
}else if (s[start] == s[end]) {
start++;
end--;
}else return false;
}
return true;
}
};
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For example,
"A man, a plan, a canal: Panama" is a palindrome."race a car" is not a palindrome.永远会记得这题，这题是面qualtrics时的原题，我记得我当时还没有做到这一题，或者很早之前做的完全没有印象，当时拿到这个题目的时候，首先想到的方法是先对 输入的数据进行预处理，使其变成只有a-z的string，我记得当时面试官说你这样就对原来的input进行了修改，我当时没有明白过来是什么意思，不对input修改怎么做，后来面试过后再想了想发现原来是可以直接在递归的时候单独对每个char进行处理，这样整个字符串就只用scan一遍就可以了，如果预处理的话，需要scan 两遍啊！！！！！我太笨了！
这个题目，对于不需要考虑的特殊字符可以直接跳过，那么怎么判断一个字符合不合法呢？ 如果这个字符是0-9、a-z/A-Z之间就是合法的，然后对于合法的字符需要统一到小写或者大写字符上面去。 可以用一个isValid函数来进行判断。
在leetcode上面，用recursion对palindrome进行判断，能通过小集合不能通过大集合， 出现runtime error。 一开始对出现这个问题不能理解，因为不能发现时间复杂度有什么区别，也不能进一步优化了，后来才知道原来一般的recursion对空间复杂度都是有要求的，如果输入的数据太大，会很消耗stack上面的空间，这样也能导致程序出现问题，但是如果用iteration代替recursion，就能消除对空间复杂度上的依赖。
所以，对于recursion 和iteration都能解决的题目，如果recursion 和iteration 写起来其实难度相当，那么优先选用iteration来做。 这样能节省空间。
class Solution {
private:
bool isValid(string &s, int i) {
if (isdigit(s[i]) || isalpha(s[i])) {
if (s[i] <= 'Z' && s[i] >= 'A')s[i] = tolower(s[i]);
return true;
}else {
return false;
}
}
public:
bool isPalindrome(string s) {
//sanity check
if (s.size() == 0) return true;
int start = 0;
int end = s.size()-1;
while (start < end) {
if (!isValid(s, start)) {
start++;
}else if (!isValid(s, end)) {
end--;
}else if (s[start] == s[end]) {
start++;
end--;
}else return false;
}
return true;
}
};
Wednesday, June 17, 2015
DFS game solver: leetcode35: valid sudoku / Leetcode 36: sudoku solver / Leetcode 51: eight Queen
Leetcode 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
本题求一个sudoku是否是valid，一个valid的sudoku必须满足， 每一行每一列的数字都是1-9，并且没有重复的数字，每一个3*3的小九宫格也不能有重复的数字，这个题目中，只考虑数字重复的情况，而不去考虑数字是不是在1-9之间。
要判断数字在1-9之间是否重复，由于是连续的数字，可以直接用一个一维数组size为10,(1-9+'.')，思想和bitvector相同， index为当前数字，value为标记，如果当前数字在数组里面标记为1，那么说明该数字之前出现过，此时出现重复情况。 对于每一行每一列可以用一个二重循环来进行check，对于每一个九宫格，其实也可以用二重循环check,只是当前的坐标需要进行一下转换，即第i个九宫格里面的9个坐标怎么用i,j表示呢？
board[3 * (i/3)+(j/3)][3*(i%3)+j%3]
class Solution {
private:
bool check(int* arr, int val) {
if (val < 0) return true;
if (arr[val] == 1) return false;
arr[val] = 1;
return true;
}
public:
bool isValidSudoku(vector<vector<char>>& board) {
//sanity chck
if (board.size() == 0 || board[0].size() == 0) return false;
//use 3 int array to do the check
int col[10] = {0};
int row[10] = {0};
int small[10] = {0};
for (int i = 0; i < 9; i++) { //ith row
memset(col, 0, sizeof(col));
memset(row, 0, sizeof(row));
memset(small, 0, sizeof(small));
for (int j = 0; j < 9; j++) { //jth col
if (!check(col, board[j][i]-'0') || !check(row, board[i][j]-'0') ||!check(small, board[3 * (i/3)+(j/3)][3*(i%3)+j%3]-'0'))
return false;
}
}
return true;
}
};
Leetcode 37: sudoku solver
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.
题目大意： 填 sudoku 9*9的格子， 每一行、列不能有重复的数字，并且3*3的格子也不能有重复的数字。
解题思路： 对于这种有一定规律地填格子的游戏，完全可以用DFS的思想来做， 因为每一个格子的填法都相同，每填完一个格子就对相应的行和列以及相应的3*3的格子进行检查，如果是valid，那么就对下一个格子进行填写。
M1： worst one！！！
先填列，再填行，如果一个格子不需要填， 跳过这个格子再填下一个。
这样填法，对于一些case，可能会出现超时，比如说，一个9*9的格子里面已经有很多已经填好的数字了，只有仅仅的几列都空格，这种情况跟worst case的时间复杂度是相同的。
M2： 如何避免这种case呢？？？
可以做一个preprocessing，把需要填的empty格子都记录下来，不用一个一个地去遍历original的每一个格子，只要直接对事先记录的empty的格子进行填写，如何判断填完了呢？ 可以利用一个计数器 cur, 表示目前已经填好的empty的格子。 每填完一个cur+1dfs到下一层，base case 是当cur == empty.size()的时候就可以return了，代表已经填好了。 这样做对于大多数的case可以节省很多时间。
class Solution {
private:
//check if the sudoku is valid
bool isValid(vector<vector<char>> &board, int i, int j) {
for (int k = 0; k < 9; k++) {
//check if there is a same num in ith row
if (k != j && board[i][k] == board[i][j]) {
return false;
}
//check if there is a same num in jth column
if (k != i && board[k][j] == board[i][j]) {
return false;
}
}
//check if there are dup nums in a 3*3 CELL
for (int m = i/3 * 3; m < i/3 * 3 + 3; m++) {
for (int n = j/3 *3; n < j/3 * 3 + 3; n++) {
if ((i != m || j != n) && (board[m][n] == board[i][j])) {
return false;
}
}
}
return true;
}
//fill the sudoku, fill column first then fill row
bool helper(vector<vector<char>> &board, vector<int> empty, int cur) {
//base case
if (cur == empty.size()) return true;
int index = empty[cur];
int row = index/9;
int col = index%9;
for (int k = 1; k <= 9; k++) {
board[row][col] = k + '0';
if (isValid(board, row, col)) {
if (helper(board,empty, cur+1)) {
return true;
}
}
board[row][col] = '.';
}
return false;
}
public:
void solveSudoku(vector<vector<char>>& board) {
//sanity check
if (board.size() == 0 || board.size() != 9 || board[0].size() != 9) return;
vector<int> empty;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == '.') {
empty.push_back(i * 9 + j);
}
}
}
helper(board, empty, 0);
}
};
class Solution {
private:
//check if the sudoku is valid
bool isValid(vector<vector<char>> &board, int i, int j) {
for (int k = 0; k < 9; k++) {
//check if there is a same num in ith row
if (k != j && board[i][k] == board[i][j]) {
return false;
}
//check if there is a same num in jth column
if (k != i && board[k][j] == board[i][j]) {
return false;
}
}
//check if there are dup nums in a 3*3 CELL
for (int m = i/3 * 3; m < i/3 * 3 + 3; m++) {
for (int n = j/3 *3; n < j/3 * 3 + 3; n++) {
if ((i != m || j != n) && (board[m][n] == board[i][j])) {
return false;
}
}
}
return true;
}
//fill the sudoku, fill column first then fill row
bool helper(vector<vector<char>> &board, vector<int> empty, int cur) {
//base case
if (cur == empty.size()) return true;
int index = empty[cur];
int row = index/9;
int col = index%9;
for (int k = 1; k <= 9; k++) {
board[row][col] = k + '0';
if (isValid(board, row, col)) {
if (helper(board,empty, cur+1)) {
return true;
}
}
board[row][col] = '.';
}
return false;
}
public:
void solveSudoku(vector<vector<char>>& board) {
//sanity check
if (board.size() == 0 || board.size() != 9 || board[0].size() != 9) return;
vector<int> empty;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == '.') {
empty.push_back(i * 9 + j);
}
}
}
helper(board, empty, 0);
}
};
Leetcode 51: N-Queen
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
题目大意： N皇后问题，使每行每列还有对角线上放置的皇后不会相互攻击。
解题思路： DFS， 对于DFS树，总共有N层，代表有这么多行，每一层一共是N种Q的放置方法，放置在该行的不同列上，但是这个是可以剪枝的DFS，因为并不是每种放置都是Valid的。 所以在每放一个Q时应该去检查这样是否valid,如果valid就DFS往下一层放置。
对于Valid函数，最直观的写法是，检测该列上是否有Q，检测左对角线是否有Q，检测右对角线是否有Q，但是这个函数的时间复杂度是O（n）。有没有能一次性判断是否valid的方法，使得时间复杂度是O（1）呢？？有！ 可以利用一个vector记录每一行上Q所在的列，然后遍历所有的层，如果vector上记录的该层Q所在列和此列正好相同就说明冲突，或者对角线x轴差距和y轴差距相同，则对角线冲突。 if(state[i] == col || abs(row - i) == abs(col - state[i]))。因为DFS里面判断valid的次数很多，优化VALID函数可以很大程度上优化运行效率。
class Solution {
private:
bool isValid(vector<int> state, int col, int row) {
for(int i = 0; i < row; i++)//只需要判断row前面的行，因为后面的行还没有放置
if(state[i] == col || abs(row - i) == abs(col - state[i]))
return false;
return true;
// return true;
}
void helper(int n, vector<string> solu, vector<vector<string>> &rst, int row, vector<int> state) {
//base case
if (row == n) {
rst.push_back(solu);
return;
}
for (int i = 0; i < n; i++) {
solu[row][i] = 'Q';
state[row] = i;
if (isValid(state, i, row))
helper(n, solu, rst, row+1,state);
solu[row][i] = '.';
state[row] = -1;
}
}
public:
//use dfs to solve
vector<vector<string> > solveNQueens(int n) {
string s = "";
vector<string> solu;
vector<vector<string>> rst;
vector<int> state(n, -1); //state to keep track of the position of Queen in each row
//sanity check
if(n == 0) return rst;
for (int i = 0; i < n; i++) {
s = "";
for (int j = 0; j < n; j++) {
s += '.';
}
solu.push_back(s);
}
// rst.push_back(solu);
helper(n, solu, rst,0, state);
return rst;
}
};
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
'.'.本题求一个sudoku是否是valid，一个valid的sudoku必须满足， 每一行每一列的数字都是1-9，并且没有重复的数字，每一个3*3的小九宫格也不能有重复的数字，这个题目中，只考虑数字重复的情况，而不去考虑数字是不是在1-9之间。
要判断数字在1-9之间是否重复，由于是连续的数字，可以直接用一个一维数组size为10,(1-9+'.')，思想和bitvector相同， index为当前数字，value为标记，如果当前数字在数组里面标记为1，那么说明该数字之前出现过，此时出现重复情况。 对于每一行每一列可以用一个二重循环来进行check，对于每一个九宫格，其实也可以用二重循环check,只是当前的坐标需要进行一下转换，即第i个九宫格里面的9个坐标怎么用i,j表示呢？
board[3 * (i/3)+(j/3)][3*(i%3)+j%3]
class Solution {
private:
bool check(int* arr, int val) {
if (val < 0) return true;
if (arr[val] == 1) return false;
arr[val] = 1;
return true;
}
public:
bool isValidSudoku(vector<vector<char>>& board) {
//sanity chck
if (board.size() == 0 || board[0].size() == 0) return false;
//use 3 int array to do the check
int col[10] = {0};
int row[10] = {0};
int small[10] = {0};
for (int i = 0; i < 9; i++) { //ith row
memset(col, 0, sizeof(col));
memset(row, 0, sizeof(row));
memset(small, 0, sizeof(small));
for (int j = 0; j < 9; j++) { //jth col
if (!check(col, board[j][i]-'0') || !check(row, board[i][j]-'0') ||!check(small, board[3 * (i/3)+(j/3)][3*(i%3)+j%3]-'0'))
return false;
}
}
return true;
}
};
Leetcode 37: sudoku solver
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.
题目大意： 填 sudoku 9*9的格子， 每一行、列不能有重复的数字，并且3*3的格子也不能有重复的数字。
解题思路： 对于这种有一定规律地填格子的游戏，完全可以用DFS的思想来做， 因为每一个格子的填法都相同，每填完一个格子就对相应的行和列以及相应的3*3的格子进行检查，如果是valid，那么就对下一个格子进行填写。
M1： worst one！！！
先填列，再填行，如果一个格子不需要填， 跳过这个格子再填下一个。
这样填法，对于一些case，可能会出现超时，比如说，一个9*9的格子里面已经有很多已经填好的数字了，只有仅仅的几列都空格，这种情况跟worst case的时间复杂度是相同的。
M2： 如何避免这种case呢？？？
可以做一个preprocessing，把需要填的empty格子都记录下来，不用一个一个地去遍历original的每一个格子，只要直接对事先记录的empty的格子进行填写，如何判断填完了呢？ 可以利用一个计数器 cur, 表示目前已经填好的empty的格子。 每填完一个cur+1dfs到下一层，base case 是当cur == empty.size()的时候就可以return了，代表已经填好了。 这样做对于大多数的case可以节省很多时间。
class Solution {
private:
//check if the sudoku is valid
bool isValid(vector<vector<char>> &board, int i, int j) {
for (int k = 0; k < 9; k++) {
//check if there is a same num in ith row
if (k != j && board[i][k] == board[i][j]) {
return false;
}
//check if there is a same num in jth column
if (k != i && board[k][j] == board[i][j]) {
return false;
}
}
//check if there are dup nums in a 3*3 CELL
for (int m = i/3 * 3; m < i/3 * 3 + 3; m++) {
for (int n = j/3 *3; n < j/3 * 3 + 3; n++) {
if ((i != m || j != n) && (board[m][n] == board[i][j])) {
return false;
}
}
}
return true;
}
//fill the sudoku, fill column first then fill row
bool helper(vector<vector<char>> &board, vector<int> empty, int cur) {
//base case
if (cur == empty.size()) return true;
int index = empty[cur];
int row = index/9;
int col = index%9;
for (int k = 1; k <= 9; k++) {
board[row][col] = k + '0';
if (isValid(board, row, col)) {
if (helper(board,empty, cur+1)) {
return true;
}
}
board[row][col] = '.';
}
return false;
}
public:
void solveSudoku(vector<vector<char>>& board) {
//sanity check
if (board.size() == 0 || board.size() != 9 || board[0].size() != 9) return;
vector<int> empty;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == '.') {
empty.push_back(i * 9 + j);
}
}
}
helper(board, empty, 0);
}
};
class Solution {
private:
//check if the sudoku is valid
bool isValid(vector<vector<char>> &board, int i, int j) {
for (int k = 0; k < 9; k++) {
//check if there is a same num in ith row
if (k != j && board[i][k] == board[i][j]) {
return false;
}
//check if there is a same num in jth column
if (k != i && board[k][j] == board[i][j]) {
return false;
}
}
//check if there are dup nums in a 3*3 CELL
for (int m = i/3 * 3; m < i/3 * 3 + 3; m++) {
for (int n = j/3 *3; n < j/3 * 3 + 3; n++) {
if ((i != m || j != n) && (board[m][n] == board[i][j])) {
return false;
}
}
}
return true;
}
//fill the sudoku, fill column first then fill row
bool helper(vector<vector<char>> &board, vector<int> empty, int cur) {
//base case
if (cur == empty.size()) return true;
int index = empty[cur];
int row = index/9;
int col = index%9;
for (int k = 1; k <= 9; k++) {
board[row][col] = k + '0';
if (isValid(board, row, col)) {
if (helper(board,empty, cur+1)) {
return true;
}
}
board[row][col] = '.';
}
return false;
}
public:
void solveSudoku(vector<vector<char>>& board) {
//sanity check
if (board.size() == 0 || board.size() != 9 || board[0].size() != 9) return;
vector<int> empty;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == '.') {
empty.push_back(i * 9 + j);
}
}
}
helper(board, empty, 0);
}
};
Leetcode 51: N-Queen
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
题目大意： N皇后问题，使每行每列还有对角线上放置的皇后不会相互攻击。
解题思路： DFS， 对于DFS树，总共有N层，代表有这么多行，每一层一共是N种Q的放置方法，放置在该行的不同列上，但是这个是可以剪枝的DFS，因为并不是每种放置都是Valid的。 所以在每放一个Q时应该去检查这样是否valid,如果valid就DFS往下一层放置。
对于Valid函数，最直观的写法是，检测该列上是否有Q，检测左对角线是否有Q，检测右对角线是否有Q，但是这个函数的时间复杂度是O（n）。有没有能一次性判断是否valid的方法，使得时间复杂度是O（1）呢？？有！ 可以利用一个vector记录每一行上Q所在的列，然后遍历所有的层，如果vector上记录的该层Q所在列和此列正好相同就说明冲突，或者对角线x轴差距和y轴差距相同，则对角线冲突。 if(state[i] == col || abs(row - i) == abs(col - state[i]))。因为DFS里面判断valid的次数很多，优化VALID函数可以很大程度上优化运行效率。
class Solution {
private:
bool isValid(vector<int> state, int col, int row) {
for(int i = 0; i < row; i++)//只需要判断row前面的行，因为后面的行还没有放置
if(state[i] == col || abs(row - i) == abs(col - state[i]))
return false;
return true;
// return true;
}
void helper(int n, vector<string> solu, vector<vector<string>> &rst, int row, vector<int> state) {
//base case
if (row == n) {
rst.push_back(solu);
return;
}
for (int i = 0; i < n; i++) {
solu[row][i] = 'Q';
state[row] = i;
if (isValid(state, i, row))
helper(n, solu, rst, row+1,state);
solu[row][i] = '.';
state[row] = -1;
}
}
public:
//use dfs to solve
vector<vector<string> > solveNQueens(int n) {
string s = "";
vector<string> solu;
vector<vector<string>> rst;
vector<int> state(n, -1); //state to keep track of the position of Queen in each row
//sanity check
if(n == 0) return rst;
for (int i = 0; i < n; i++) {
s = "";
for (int j = 0; j < n; j++) {
s += '.';
}
solu.push_back(s);
}
// rst.push_back(solu);
helper(n, solu, rst,0, state);
return rst;
}
};
挡板直方图问题 ：Leetcode 11 : Container With Most Water / Leetcode 42: Trapping Rain Water / Leetcode 84:Largest Rectangle in Histogram
1. Leetcode 11： Container With Most Water
Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
这一题大意是说： x 轴有很多垂直的线，代表高度，在这些线中选择两条线，使这两条线与x轴组成的容器的容积最大。
M1： 以每一个板子为一条边，遍历其他板子并记录容积，最后找到以当前板子为边的容器的容积最大值。最后会得到最大容积的两条边。 时间复杂度： O（n^2）
M2: 在M1的基础上考虑，其实在计算两个板子形成容器的容积时，如果其中某个板子为短板，那么以这个板子为一条边的容器的最大容积已经定了，那就是以这个为一条边，另一条边是离它最远的那个板子。如果用两个指针，left 和right，分别从0，size - 1处移动，每次只移动短板，在每次移动过程中，就能把以短板为一条边的容器的最大容积计算出来，最后当两个指针相遇时代表以所有板子为边的容器最大容积都求出来，并且可以得到最大容积。
挡板直方图容积问题， 有一个原理，短板原理，如果一个板子是短板，那么这个以这个板子为边的容器容积肯定不是最大，要找到最大的短板，需要移动指向短板的那个index，继续往后探索。
class Solution {
public:
//keep left_max and right_max
//compute the water in each index
//sum these water up
int maxArea(vector<int>& height) {
//sanity check
if (height.size() == 0) return 0;
int max1 = 0;
int left = 0;
int right = height.size()-1;
while (left <= right) {
max1 = max(max1, min(height[left],height[right]) * (right - left));
if (height[left] < height[right]) {
left = left + 1;
}else {
right = right - 1;
}
}
return max1;
}
};
time complexity: O(n)
space complexity: O(1)
2. Leetcode Trapping Rain Water
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
题目大意： 跟第一个挡板直方图问题类似，模型类似，但是这题是求所有这些挡板与X轴一起能积蓄多少水。
此题应用的挡板原理与第一题相同，短板原理，在这题中， 较短那块板子是不能够积水的，每次两个指针在移动的时候，只移动短板对应的指针，每次移动短板之前需要记录该短板能蓄水的容量。而对于较短的那块板子能蓄水的容量是该板子的左侧或者右侧的最大值 - 该板子的高度。
class Solution {
public:
int trap(vector<int>& height) {
//sanity check
if (height.size() == 0) return 0;
int left_max = 0;
int right_max = 0;
int left = 0;
int right = height.size() - 1;
int rst = 0;
while (left <= right) {
left_max = max(left_max, height[left]);
right_max = max(right_max, height[right]);
if (height[left] < height[right]) {
rst += left_max - height[left];
left = left + 1;
} else {
rst += right_max - height[right];
right = right - 1;
}
}
return rst;
}
};
Time complexity: O(n)
Space complexity: O(1)
Leetcode 84: Largest Rectangle in Histogram
Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
这一题大意是说： x 轴有很多垂直的线，代表高度，在这些线中选择两条线，使这两条线与x轴组成的容器的容积最大。
M1： 以每一个板子为一条边，遍历其他板子并记录容积，最后找到以当前板子为边的容器的容积最大值。最后会得到最大容积的两条边。 时间复杂度： O（n^2）
M2: 在M1的基础上考虑，其实在计算两个板子形成容器的容积时，如果其中某个板子为短板，那么以这个板子为一条边的容器的最大容积已经定了，那就是以这个为一条边，另一条边是离它最远的那个板子。如果用两个指针，left 和right，分别从0，size - 1处移动，每次只移动短板，在每次移动过程中，就能把以短板为一条边的容器的最大容积计算出来，最后当两个指针相遇时代表以所有板子为边的容器最大容积都求出来，并且可以得到最大容积。
挡板直方图容积问题， 有一个原理，短板原理，如果一个板子是短板，那么这个以这个板子为边的容器容积肯定不是最大，要找到最大的短板，需要移动指向短板的那个index，继续往后探索。
class Solution {
public:
//keep left_max and right_max
//compute the water in each index
//sum these water up
int maxArea(vector<int>& height) {
//sanity check
if (height.size() == 0) return 0;
int max1 = 0;
int left = 0;
int right = height.size()-1;
while (left <= right) {
max1 = max(max1, min(height[left],height[right]) * (right - left));
if (height[left] < height[right]) {
left = left + 1;
}else {
right = right - 1;
}
}
return max1;
}
};
time complexity: O(n)
space complexity: O(1)
2. Leetcode Trapping Rain Water
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
题目大意： 跟第一个挡板直方图问题类似，模型类似，但是这题是求所有这些挡板与X轴一起能积蓄多少水。
此题应用的挡板原理与第一题相同，短板原理，在这题中， 较短那块板子是不能够积水的，每次两个指针在移动的时候，只移动短板对应的指针，每次移动短板之前需要记录该短板能蓄水的容量。而对于较短的那块板子能蓄水的容量是该板子的左侧或者右侧的最大值 - 该板子的高度。
class Solution {
public:
int trap(vector<int>& height) {
//sanity check
if (height.size() == 0) return 0;
int left_max = 0;
int right_max = 0;
int left = 0;
int right = height.size() - 1;
int rst = 0;
while (left <= right) {
left_max = max(left_max, height[left]);
right_max = max(right_max, height[right]);
if (height[left] < height[right]) {
rst += left_max - height[left];
left = left + 1;
} else {
rst += right_max - height[right];
right = right - 1;
}
}
return rst;
}
};
Time complexity: O(n)
Space complexity: O(1)
Leetcode 84: Largest Rectangle in Histogram
Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
Leetcode 7: Palindrome Number
Leetcode 7: Palindrome Number
Determine whether an integer is a palindrome. Do this without extra space.
跟前几题类似， 这种string -> int 或者 int -> string的题目，凡是input or output 涉及int的题目，都要注意在计算过程中可能会出现output 的int overflow， 或者在计算过程中的某个变量overflow的情况。 如果是int -> string， 那么输入的数是一定不会overflow, 超过INT_MAX这个值的，要注意的是在计算过程中自定义的某个变量会不会overflow，为了避免这种情况发生，一般将过程中变量定义成long 型！ 如果是 string -> int ， 那么要注意输入的string convert to int的时候，会不会超过INT_MAX， 因为string 是不会overflow的， 为了避免这种情况发生，一般在计算过程中，要提前对overflow的情况进行check。
这一题属于第一种，input 是int，要对int 进行判断， 要注意过程中自定义的变量会不会overflow。这一题判断palindrome方法想到的是和string的判断方法相似，利用递归/迭代来一一比较首尾字符。
class Solution {
private:
bool helper(int x, int num) {
//base case
if (num <= 1) return true;
//recursive rule
//compare first and last num
int first = x / num;
int last = x % 10;
if (first == last) {
//get the mid nums
x = (x % num) / 10;
return helper(x, num/100);
}else
return false;
}
public:
//step1: preprocessing int
//step2: get the first and end num
//step3: recursion compare
bool isPalindrome(int x) {
//positive num
if (x < 0) return false;
long long num = 1; //num might be overflow, must be long long type
int n = x;
while (n) {
n = n / 10;
num = num * 10;
}
num = num / 10;
return helper(x, num);
}
};
time complexity: O(n)
space complexity: O(1)
Determine whether an integer is a palindrome. Do this without extra space.
跟前几题类似， 这种string -> int 或者 int -> string的题目，凡是input or output 涉及int的题目，都要注意在计算过程中可能会出现output 的int overflow， 或者在计算过程中的某个变量overflow的情况。 如果是int -> string， 那么输入的数是一定不会overflow, 超过INT_MAX这个值的，要注意的是在计算过程中自定义的某个变量会不会overflow，为了避免这种情况发生，一般将过程中变量定义成long 型！ 如果是 string -> int ， 那么要注意输入的string convert to int的时候，会不会超过INT_MAX， 因为string 是不会overflow的， 为了避免这种情况发生，一般在计算过程中，要提前对overflow的情况进行check。
这一题属于第一种，input 是int，要对int 进行判断， 要注意过程中自定义的变量会不会overflow。这一题判断palindrome方法想到的是和string的判断方法相似，利用递归/迭代来一一比较首尾字符。
class Solution {
private:
bool helper(int x, int num) {
//base case
if (num <= 1) return true;
//recursive rule
//compare first and last num
int first = x / num;
int last = x % 10;
if (first == last) {
//get the mid nums
x = (x % num) / 10;
return helper(x, num/100);
}else
return false;
}
public:
//step1: preprocessing int
//step2: get the first and end num
//step3: recursion compare
bool isPalindrome(int x) {
//positive num
if (x < 0) return false;
long long num = 1; //num might be overflow, must be long long type
int n = x;
while (n) {
n = n / 10;
num = num * 10;
}
num = num / 10;
return helper(x, num);
}
};
time complexity: O(n)
space complexity: O(1)
Monday, June 15, 2015
leetcode 5: longest palindrome subarray
leetcode 5: longest palindrome subarray
class Solution {
//use dp to find palindromes
//update the max length of the palindorome
public:
string longestPalindrome(string s) {
//sanity check
if (s.size() == 0) return s;
//M[i][j] represent if substring from i to i+j is palindrome or not
bool M[s.size()][s.size()];
//base case
for (int i = 0; i < s.size(); i++) {
M[i][i] = true;
}
int max_len = 0;
int start = 0;
int end = 0;
for (int j = 1; j < s.size(); j++) {
for (int i = 0; i+j < s.size(); i++) {
if (s[i] == s[i+j] && (j == 1 || M[i+1][i+j-1])) { //if the start and end char is the same
M[i][j+i] = true;
if (max_len < j) {
max_len = j;
start = i;
end = i+j;
}
}else M[i][j+i] = false;
}
}
return s.substr(start, end-start+1);
}
};
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
思路： 找到最长回文子串， 首先想到的是需要把所有可能的回文都找出来，update长度最长的一个，问题转化到如何把一个字符串里面所有的回文子串都找出来，对于panlindrome的求法，有3种，1.利用递归，两头的char是否相等，然后看去掉两头的字符串是不是回文 2. 利用DP， 二维矩阵，M[i][j]代表string from index i to index j is palindrome or not. M[i][j]依赖于M[i+1][j-1]。 3. 利用两个指针从中间往两边进行scan， 到不相等时，即此时的string 不是palindrome。 方法三是最好的，时间复杂度o(n^2), 空间复杂度o(1).
class Solution {
//use dp to find palindromes
//update the max length of the palindorome
public:
string longestPalindrome(string s) {
//sanity check
if (s.size() == 0) return s;
//M[i][j] represent if substring from i to i+j is palindrome or not
bool M[s.size()][s.size()];
//base case
for (int i = 0; i < s.size(); i++) {
M[i][i] = true;
}
int max_len = 0;
int start = 0;
int end = 0;
for (int j = 1; j < s.size(); j++) {
for (int i = 0; i+j < s.size(); i++) {
if (s[i] == s[i+j] && (j == 1 || M[i+1][i+j-1])) { //if the start and end char is the same
M[i][j+i] = true;
if (max_len < j) {
max_len = j;
start = i;
end = i+j;
}
}else M[i][j+i] = false;
}
}
return s.substr(start, end-start+1);
}
};
Thursday, June 11, 2015
Leetcode 4 : Median of Two Sorted Arrays
Leetcode 4 : Median of Two Sorted Arrays
There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
analysis:
M1: find the median of two sorted arrays: as for sorted arrays, we can use mergesort to linear finding the median element, time complexity is O(n)
M2: as the requested complexity is O(log n), we can use binary search to solve this problem
we can first solve find the kth smallest element in two sorted array, then apply k to (array1.size() + array2.size()) / 2;
How to find the kth smallest element in two sorted array?
step1: compare the k/2th element in two array,
if array1[k/2] is smaller than array2[k/2], then the kth smallest element is not
in the first k/2 elements in array1; otherwise, the kth smallest element is not
in the first k/2 elements in array2. In this way, we can remove half k elements
in one of the array.
step2: In the rest of arrays, we have to find k-k/2 th element, because we have
remove the smallest k/2 elements in the two array;
step3: do a recursion of step1 and step2, when the base case fits, we can find the
kth smallest element.
int findkth(vector<int> nums1, int left1, int left2,vector<int> nums2, int k) {
//base case
if (left1 >= nums1.size()) return nums2[left2 + k -1];
if (left2 >= nums2.size()) return nums1[left1 + k -1];
if (k == 1) { //find the first smallest element
return min(nums1[left1], nums2[left2]);
}
int half_1 = left1 + k/2 -1 < nums1.size()? nums1[left1 + k/2-1] : INT_MAX;
int half_2 = left2 + k/2 -1 < nums2.size()? nums2[left2 + k/2-1] : INT_MAX;
if (half_1 < half_2) {
return findkth(nums1, left1 + k/2, left2, nums2, k - k/2);
}else {
return findkth(nums1, left1, left2 + k/2, nums2, k - k/2);
}
}
After finding the kth smallest element in two sorted array, we can give k = array1.size() + array2.size(), if k is odd, then we can find the middle one with k/2-1, if k is even , we have to find the k/2th smallest element also, then compute the average number of k/2-1 th and k/2 th element.
Time complexity : O(log(m+n))
There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
analysis:
M1: find the median of two sorted arrays: as for sorted arrays, we can use mergesort to linear finding the median element, time complexity is O(n)
M2: as the requested complexity is O(log n), we can use binary search to solve this problem
we can first solve find the kth smallest element in two sorted array, then apply k to (array1.size() + array2.size()) / 2;
How to find the kth smallest element in two sorted array?
step1: compare the k/2th element in two array,
if array1[k/2] is smaller than array2[k/2], then the kth smallest element is not
in the first k/2 elements in array1; otherwise, the kth smallest element is not
in the first k/2 elements in array2. In this way, we can remove half k elements
in one of the array.
step2: In the rest of arrays, we have to find k-k/2 th element, because we have
remove the smallest k/2 elements in the two array;
step3: do a recursion of step1 and step2, when the base case fits, we can find the
kth smallest element.
int findkth(vector<int> nums1, int left1, int left2,vector<int> nums2, int k) {
//base case
if (left1 >= nums1.size()) return nums2[left2 + k -1];
if (left2 >= nums2.size()) return nums1[left1 + k -1];
if (k == 1) { //find the first smallest element
return min(nums1[left1], nums2[left2]);
}
int half_1 = left1 + k/2 -1 < nums1.size()? nums1[left1 + k/2-1] : INT_MAX;
int half_2 = left2 + k/2 -1 < nums2.size()? nums2[left2 + k/2-1] : INT_MAX;
if (half_1 < half_2) {
return findkth(nums1, left1 + k/2, left2, nums2, k - k/2);
}else {
return findkth(nums1, left1, left2 + k/2, nums2, k - k/2);
}
}
After finding the kth smallest element in two sorted array, we can give k = array1.size() + array2.size(), if k is odd, then we can find the middle one with k/2-1, if k is even , we have to find the k/2th smallest element also, then compute the average number of k/2-1 th and k/2 th element.
Time complexity : O(log(m+n))
Leetcode3: Longest Substring Without Repeating Characters
Leetcode 3: Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.
大意： 找到一个字符串里面最长无重复字母的子字符串
分析： 有两种做法，一种是用map, 一种是用set
M1: use map
key: char value: index of that char
需要一个start指针，表示当前最长子串的起始位置。
如果char 不在map 中， 将该char 放进map, 并且同时更新最长子串
如果char 在map 中， 我们需要删除从 start 到该char 的所有字符，使得这个字符在map中没有重复。首先获取该char 之前在map 中的index, 将所有的value = 0； 并且将新char的位置更新，然后update start 的位置。
worst case : time complexity is O(n), 最多扫描两遍string
M2: use set
keep a start pointer and an end pointer
if end char is not in the set, insert the end char into set and do end++ to explore the next char, update the max_length of the substring; if end char is in the set, erase the start char and do start++ until the end char is erased;
time complexity is O(nlogn), as the time complexity of insert and erase operation in set is both log(n), but the code is shorter and the space complexity is less than using map.
class Solution {
public:
int lengthOfLongestSubstring(string s) {
//sanity check
if (s.size() == 0) return 0;
//use a set to store unduplicate chars
set<int> se;
int max_len = 0;
int left = 0;
int right = 0;
for (;right < s.size(); right++) {
if (se.find(s[right]) == se.end()) { //case 1: char not in set
se.insert(s[right]);
//update max_len
max_len = max(max_len, right-left+1);
}else { //case2: char in set
se.erase(s[left++]);
right--;
}
}
return max_len;
}
};
updated:
不需要用map/set，对于以char为key 的 map， 可以直接用一个size 为256的一维数组来存储，数组的index是key， value是该字符在string里的位置。 这样就节省了空间。
用下面的方法，对sliding window进行了特殊的处理方式，只需要扫描一遍string，节省了时间。
判断存在duplicate的条件，不再是看map或者set里面有没有这个元素，而是看当前元素的value是不是比窗口左边大，如果大，说明当前元素已经在array中，找到了一个duplicate；如果小，说明当前元素是在窗口左边之外，是已经无用的元素，需要更新其index值。
class Solution {
public:
//sliding window
int lengthOfLongestSubstring(string s) {
//sanity check
if (s.size() == 0) return 0;
int left = 0;
int right = 1;
int carray[256];
for (int i = 0; i < 256; i++) {
carray[i] = -1;
}
int maxl = 1;
carray[s[0]] = 0;
for (; right < s.size(); right++) {
if (carray[s[right]] >= left) {
left = carray[s[right]] + 1;
}
maxl = max(maxl, right- left + 1);
carray[s[right]] = right;
}
return maxl;
}
};
updated:
最精简的写法了！
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if (s.size() == 0) return 0;
//unordered_set<char> iset;
int iset[256] = {0};
int left = 0;
int right = 0;
int gmax = 0;
while (right < s.size()) {
if (iset[s[right]] > 0) {
iset[s[left]]--;
left++;
} else {
iset[s[right]]++;
right++;
}
gmax = max(gmax, right-left);
}
return gmax;
}
};
Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.
大意： 找到一个字符串里面最长无重复字母的子字符串
分析： 有两种做法，一种是用map, 一种是用set
M1: use map
key: char value: index of that char
需要一个start指针，表示当前最长子串的起始位置。
如果char 不在map 中， 将该char 放进map, 并且同时更新最长子串
如果char 在map 中， 我们需要删除从 start 到该char 的所有字符，使得这个字符在map中没有重复。首先获取该char 之前在map 中的index, 将所有的value = 0； 并且将新char的位置更新，然后update start 的位置。
worst case : time complexity is O(n), 最多扫描两遍string
M2: use set
keep a start pointer and an end pointer
if end char is not in the set, insert the end char into set and do end++ to explore the next char, update the max_length of the substring; if end char is in the set, erase the start char and do start++ until the end char is erased;
time complexity is O(nlogn), as the time complexity of insert and erase operation in set is both log(n), but the code is shorter and the space complexity is less than using map.
class Solution {
public:
int lengthOfLongestSubstring(string s) {
//sanity check
if (s.size() == 0) return 0;
//use a set to store unduplicate chars
set<int> se;
int max_len = 0;
int left = 0;
int right = 0;
for (;right < s.size(); right++) {
if (se.find(s[right]) == se.end()) { //case 1: char not in set
se.insert(s[right]);
//update max_len
max_len = max(max_len, right-left+1);
}else { //case2: char in set
se.erase(s[left++]);
right--;
}
}
return max_len;
}
};
updated:
不需要用map/set，对于以char为key 的 map， 可以直接用一个size 为256的一维数组来存储，数组的index是key， value是该字符在string里的位置。 这样就节省了空间。
用下面的方法，对sliding window进行了特殊的处理方式，只需要扫描一遍string，节省了时间。
判断存在duplicate的条件，不再是看map或者set里面有没有这个元素，而是看当前元素的value是不是比窗口左边大，如果大，说明当前元素已经在array中，找到了一个duplicate；如果小，说明当前元素是在窗口左边之外，是已经无用的元素，需要更新其index值。
class Solution {
public:
//sliding window
int lengthOfLongestSubstring(string s) {
//sanity check
if (s.size() == 0) return 0;
int left = 0;
int right = 1;
int carray[256];
for (int i = 0; i < 256; i++) {
carray[i] = -1;
}
int maxl = 1;
carray[s[0]] = 0;
for (; right < s.size(); right++) {
if (carray[s[right]] >= left) {
left = carray[s[right]] + 1;
}
maxl = max(maxl, right- left + 1);
carray[s[right]] = right;
}
return maxl;
}
};
updated:
最精简的写法了！
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if (s.size() == 0) return 0;
//unordered_set<char> iset;
int iset[256] = {0};
int left = 0;
int right = 0;
int gmax = 0;
while (right < s.size()) {
if (iset[s[right]] > 0) {
iset[s[left]]--;
left++;
} else {
iset[s[right]]++;
right++;
}
gmax = max(gmax, right-left);
}
return gmax;
}
};
Subscribe to:
Posts (Atom)