45-60
45: Jump GameII
55: Jump GameI
这两个题目最基本的是用DP， Linear 往回看，这样做时间复杂度O(n^2).
Jump GameI 其实这个题目进一步思考，可以利用 greedy 的算法来解，每次跳到一个位置i， 从这个位置出发能到达的最远距离是 i + A[i], 每次我们只要看在这中间是否有某一个位置能跳到最后，有就直接return true就好了，在每一个位置的，如果发现在这个位置能跳的更远，就需要更新最远距离。
class Solution {
public:
bool canJump(vector<int>& nums) {
if (nums.size() == 0) return false;
int canReach = nums[0];
int start = 0;
for (; start <= canReach; start++) {
if (start+ nums[start] +1 >= nums.size()) return true;
else canReach = max(canReach,nums[start] + start);
}
return false;
}
};
greedy 解法时间复杂度： O(n)
Jump GameII
感觉这个题目做起来还是有点理解费劲啊！
46：permutation I
47: permutation II
这两个题目感觉没什么好说的，
48. rotate image 🐴🐴🐴
这个又是属于一个数学问题， 旋转矩阵，就是矩阵里的行和列怎么怎么去变换， 唉，真是不想记这些算法步骤,
后来发现其实这个题目很好做的，分为两个步骤：
1. 行列交换，之前觉得行列交换的操作很麻烦，今天突然发现其实很简单啊，行列交换其实就是沿对角线把元素对称交换嘛！🐴🐴🐴
2. 沿列中心线交换就是交换一半就可以了嘛！🐴🐴🐴
所以最后以前觉得很复杂的的程序，两个简短简单通俗易懂的循环就解决~\(≧▽≦)/~啦啦啦， 天啊，我突然发现一个题目越多想想越多做做，会发现很奇妙的简单啊！
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
if (matrix.size() == 0 || matrix[0].size() == 0) return;
//沿对角线进行交换
for (int i = 0; i < matrix.size(); i++) {
for (int j = i+1; j < matrix.size(); j++) {
int tmp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = tmp;
}
}
//沿列中心线进行交换
for (int j = 0; j < matrix.size()/2; j++) {
for (int i = 0; i < matrix.size(); i++) {
int tmp = matrix[i][j];
matrix[i][j] = matrix[i][matrix.size()-1-j];
matrix[i][matrix.size()-1-j] = tmp;
}
}
}
};
follow up: 对角线交换元素
follow up: 行中心线交换元素
这种对称问题，找到一半的元素，然后找到需要交换的两个元素之间的坐标对应关系，然后扫描一般的元素，同时进行交换。
49. group anagram
这个题目是要将一堆string 按照anagram的性质分组，判断两个string是不是anagram， 其实有两种判断方法，一种是对string 进行sort，如果两个string 是 anagram的话，那么sort完肯定是相等的， 一种是利用bit vector对两个string里面的char进行统计，一样的字符出现频率，就是anagram的。 这个题目要判断一堆string，肯定是第一种方便啦~第二种需要每次都对所有的string进行check，这样太麻烦，而且效率太低啦
时间复杂度： O(n * k * logk) ： k-->string长度。
50. pow(x, n)
这个题目虽然是很简单的recursion的题目，但是面试中感觉出现频率还是很高的。
这个题目做的时候还是要注意下的， 那个n ， 可以是正数，也可能是负数， 也可能是0！
所以应该区分来做， 每次做这个题目总是忘记先考虑下n的可能取值。
class Solution {
private:
double helper(double x, int n) {
if (n == 0) return 1;
if (n == 1) return x;
double half = myPow(x, n/2);
if (n % 2) {
return half*half*x;
}
return half*half;
}
public:
double myPow(double x, int n) {
if (n >= 0) return helper(x,n);
if (n < 0) {
double tmp = helper(x, abs(n));
return 1.0/tmp;
}
}
};
51： N-QueensI
52: N-QueensII
感觉难点变成了怎么判断对角线是否valid！唉，对自己的数学也是很难过。
这个题目最容易最简单判断valid的方法： 利用一个state数组来存储每一行上存放queen的信息，放到了哪行，只需要对这行之前的行进行判断，因为后面的行还没有放置任何queen，如果想要判断行上的列冲突，只需要判断， state[row] == col? 就是说前面的那几行放置queen的col有没有跟当前行的col相同，如果相同，就返回false，如果想要判断对角线上的冲突，只要判断 行的差的绝对值和列的差的绝对值是否相同， abs(i-row) == abs(state[i] - col), 这种方法比较简单易懂。
N-Queen I和sudoku solver的做法是相似的，利用dfs， 但是不同的是， N-queueI是不需要返回bool值，而sudoku 是需要返回bool 值，这是因为N-queen在每次check完就能立刻保证整个布局是有效的； 而sudoku只能判断当前该元素放好后对当前行列小九格有没有影响，可能之后放值的对之前的有影响，所以需要返回一个bool值来判断整体放值是否y
84. Largest Rectangle in histogram
这个题目属于一维数组里面难度很大的题目了， 这个题目的思想是： 对每一个bar, 以它为高度求出它能组成的最大的面积，其实这个题目的思想在之前的几个题目里也应用过，利用deque 或者stack， 里面存单调递增或者单调递减的元素的信息，比如：data stream里面 k-size 的window 里面的max value， 就是用一个k-size的deque来模拟窗口，而deque里面存的数是单调递减的； 又比如： Q4 Given an array A[N] of integers, for each index i, find the nearest j from index i, such that A[j] < A[i] and j < i, print out A[j] ( 0 <= i < N ).
Example:
Input: arr[] = {1, 6, 4, 10, 2, 5}
Output: {_, 1, 1, 4, 1, 2}就是利用一个stack，里面存的数是单调递增的; 这类问题啊，恩，找通性的话，还是只能说这些问题在对某一个元素进行考虑的时候需要lineat 往回看之前的记录或者之前的值，这个时候能想到的就是利用stack, 此外，如果是k-size window相关的话，需要用到deque。 从这个方面看的话， 这个题目我们需要求每个Bar能到达的最大面积，我们也是需要往回看的，如果之前的bar比它高，我们是需要累加之前的面积的， 这个时候我们也可以想到用stack来处理往回看的问题， 而这个问题中，stack里面存储的单调递增的序列，因为一旦遇到一个小于top元素的值，那么说明那些高的bar的最大面积可以开始计算了。这就是这个题目的思想，在stack中，我记录了两个信息，一个是该bar构成面积的左边界，以及该bar自身的Indx, 右边界是很好处理的，当遇到一个较小的元素时，这个较小元素其实就是这个bar的右边界。
class Solution {
public:
int largestRectangleArea(vector<int>& height) {
if (height.size() == 0) return 0;
int gmax = 0;
//add a 0 at the end of height
height.push_back(0);
stack<pair<int,int>> buf; // pair: left , index
for (int i = 0; i < height.size(); i++) {
while (!buf.empty() && height[i] <= height[buf.top().second]) {
pair<int, int> tmp = buf.top();
buf.pop();
gmax = max(gmax, (i - tmp.first) * height[tmp.second]);
}
if (!buf.empty()) buf.push(make_pair(buf.top().second+1,i));
else buf.push(make_pair(0, i));
}
return gmax;
}
};
85: largest rectangle in 0, 1 matrix
这个题目是按照上个题目的思想来解的，先对这个0,1 matrix对每一列，从上往下做最长1的子序列dp， 然后按照上面题目的做法对每一行进行求最大的面积，其中的最大值就是最后的值。time complexity: O(N^2)
class Solution {
private:
int largestArea(vector<char> input) {
if (input.size() == 0) return 0;
stack<pair<int,int>> buf;
input.push_back('0');
int gmax = 0;
for (int i = 0; i < input.size(); i++) {
while (!buf.empty() && input[i] <= input[buf.top().second]) {
pair<int, int> tmp = buf.top();
buf.pop();
gmax = max(gmax, (i-tmp.first)*(input[tmp.second]-'0'));
}
if (!buf.empty()) buf.push(make_pair(buf.top().second+1, i));
else buf.push(make_pair(0, i));
}
return gmax;
}
public:
int maximalRectangle(vector<vector<char>>& matrix) {
if (matrix.size() == 0 || matrix[0].size() == 0) return 0;
for (int i = 0; i < matrix[0].size(); i++) {
for (int j = 1; j < matrix.size(); j++) {
if (matrix[j][i] == '1') {
matrix[j][i] = matrix[j-1][i] + 1;
}
}
}
int gmax = 0;
for (int i = 0; i < matrix.size(); i++) {
vector<char> tmp = matrix[i];
gmax = max(gmax, largestArea(tmp));
}
return gmax;
}
};
注意这个题目和另外一道 二维dp 求0,1 matrix里面的最大square的解题思想是不同的！！！
也说明： 不要记题目，要记思想！
No comments:
Post a Comment