休息了几天，继续最后20道！
1道easy+12道medium+1道hard。
(medium)50. Pow(x, n)
二进制快速幂，原理其实就是譬如：x^10=x^2*x^8，二进制为1的位置就把当前的tmp乘进sum，每次tmp都要平方。懒得写成递归。代码如下：
class Solution {
public:
double get(double x, unsigned int n)
{
double tmp = x;
double sum = 1;
while(n)
{
if(n & 1)
sum = sum * tmp;
n = n >> 1;
tmp = tmp * tmp;
}
return sum;
}
double myPow(double x, int n) {
if(x == 1)
return 1;
if(n < 0)
{
long long tmp = n;
return 1.0/get(x , -tmp);
}
else
{
return get(x , n);
}
}
};(medium)215. 数组中的第K个最大元素
堆或者手写快排，太久没手写快排了所以尝试写一下。代码如下：
class Solution {
public:
void q_sort(vector<int>& nums, int l, int r)
{
if (l >= r)
return;
//随机当前位置
int pos = l + (rand() % (r - l + 1));
int tmp = nums[pos];
swap(nums[l] , nums[pos]);
int tmp_l = l;
int tmp_r = r;
// 排完之后确保tmp_l左边的都是小于tmp，右边都是大于tmp，至于左右是否有序，在当下不确定
while (tmp_l < tmp_r)
{
// 找到右边第一个小于tmp的就放到左链中
while (tmp_l < tmp_r && nums[tmp_r] >= tmp)
tmp_r--;
nums[tmp_l] = nums[tmp_r];
// 找到左边第一个大于tmp的就放到右链中
while (tmp_l < tmp_r && nums[tmp_l] <= tmp)
tmp_l++;
nums[tmp_r] = nums[tmp_l];
}
nums[tmp_l] = tmp;
//处理很多重复的情况
while(tmp_l && nums[tmp_l] == nums[tmp_l - 1])
tmp_l--;
while(tmp_r < r && nums[tmp_r] == nums[tmp_r + 1])
tmp_r++;
q_sort(nums, l, tmp_l - 1);
q_sort(nums, tmp_r + 1, r);
}
int findKthLargest(vector<int>& nums, int k) {
n = nums.size();
q_sort(nums , 0 , n - 1);
return nums[n - k];
}
private:
int n;
};(hard)149. 直线上最多的点数
本质就是y=kx+b，只不过需要浮点数的差值比较以及x1=x2的特判罢了。代码如下：
#define eps 1e-9
class Solution {
public:
int maxPoints(vector<vector<int>>& points) {
memset(vis , 0 , sizeof(vis));
int n = points.size();
int maxn = min(1 , n);
for(int i = 0 ; i < n ; i++)
{
memset(vis , 0 , sizeof(vis));
for(int j = i + 1 ; j < n ; j++)
{
if(vis[j])
continue;
double tmp_k;
int cnt = 1;
if(points[j][0] != points[i][0])
{
tmp_k = (double)(points[j][1] - points[i][1]) / (double)((points[j][0] - points[i][0]));
double tmp_b = (double)points[i][1] - tmp_k * (double)points[i][0];
for(int t = j ; t < n ; t++)
{
if(vis[t])
continue;
if(abs(tmp_k * points[t][0] + tmp_b - (double)points[t][1]) < eps)
{
vis[t] = 1;
cnt++;
}
}
}
else
{
int tmp_x = points[i][0];
for(int t = j ; t < n ; t++)
{
if(vis[t])
continue;
if(points[t][0] == tmp_x)
{
vis[t] = 1;
cnt++;
}
}
}
maxn = max(maxn , cnt);
}
}
return maxn;
}
private:
bool vis[301];
};(easy)70. 爬楼梯
记忆化搜/动规。dp[n] = dp[n - 1] + dp[n - 2]。代码如下：
搜索：
class Solution {
public:
int climbStairs(int n) {
if(n < 0)
return 0;
if(n == 1 || n == 0)
return 1;
if(dp[n])
return dp[n];
dp[n] = climbStairs(n - 1) + climbStairs(n - 2);
return dp[n];
}
private:
int dp[46];
};动规：
class Solution {
public:
int climbStairs(int n) {
dp[0] = 1;
dp[1] = 1;
for(int i = 0 ; i <= n ; i++)
{
if(i >= 2)
{
dp[i] = dp[i - 1] + dp[i - 2];
}
}
return dp[n];
}
private:
int dp[46];
};(medium)198. 打家劫舍
动规版题，思路见代码。代码如下：
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
dp1.resize(n , 0);
dp2.resize(n , 0);
dp1[0] = nums[0];
for(int i = 1 ; i < n ; i++)
{
//如果盗窃i,那i-1肯定不能盗,盗窃i的最大收益为不盗窃i-1的收益+nums[i]
dp1[i] = dp2[i - 1] + nums[i];
//如果不盗窃i,那么i-1盗不盗都行,最大收益为i-1盗或不盗的最大值
dp2[i] = max(dp1[i - 1] , dp2[i - 1]);
}
return max(dp1[n - 1] , dp2[n - 1]);
}
private:
//dp1[i]表示盗窃i所能得到最多，dp2[i]表示不盗窃i所能拿到的最多。
vector<int> dp1;
vector<int> dp2;
};(medium)139. 单词拆分
不知道这算啥动规，分治解决了。每次都看s能不能从头拆出字典中的单词，能就看拆完之后的s能不能继续拆。vis[a]表示a字符串是否被判断过以及状态：为0则表示没判断过；为1则表示判断过，无法拆；为2则表示判断过，可拆；代码如下：
class Solution {
public:
bool check(string s, vector<string>& wordDict) {
int l = 0;
int n = s.size();
if(vis[s])
return vis[s] - 1;
/*for(int i = minl ; i < n ; i++)
{
if(check(s.substr(0 , i), wordDict) && check(s.substr(i), wordDict))
{
vis[s] = 2;
return 1;
}
}*/
for(int i = 0 ; i < m ; i++)
{
int tmp = wordDict[i].size();
if(tmp > n)
continue;
if(s.substr(0 , tmp) == wordDict[i])
{
if(check(s.substr(tmp) , wordDict))
{
vis[s] = 2;
return 1;
}
}
}
vis[s] = 1;
return 0;
}
bool wordBreak(string s, vector<string>& wordDict) {
m = wordDict.size();
for(int i = 0 ; i < m ; i++)
{
vis[wordDict[i]] = 2;
}
return check(s , wordDict);
}
private:
int m;
unordered_map<string , int> vis;
};(medium)322. 零钱兑换
思路同上，只不过vis[num]记录的是值为num的最少硬币数，若vis[num]=-1则表示没法构成num。代码如下：
class Solution {
public:
int check(vector<int>& coins, int amount)
{
if(vis[amount])
return vis[amount];
vis[amount] = INT_MAX;
for(int i = 0 ; i < n ; i++)
{
if(coins[i] <= amount)
{
int tmp = check(coins , amount - coins[i]);
if(tmp != -1)
{
vis[amount] = min(vis[amount] , 1 + tmp);
}
}
}
if(vis[amount] == INT_MAX)
vis[amount] = -1;
return vis[amount];
}
int coinChange(vector<int>& coins, int amount) {
n = coins.size();
if(amount == 0)
return 0;
for(int i = 0 ; i < n ; i++)
{
if(coins[i] <= amount)
vis[coins[i]] = 1;
}
return check(coins , amount);
}
private:
int n;
int vis[10001];
};(medium)300. 最长递增子序列
dp[i]表示以nums[i]结尾的最长严格递增子序列长度，而每次针对i，我们都枚举小于i的j，如果nums[i]>nums[j]，则dp[i] = max(dp[i] , dp[j] + 1)。代码如下：
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
if(!n)
return 0;
int maxn = 0;
for(int i = 0 ; i < n ; i++)
{
dp[i] = 1;
for(int j = 0 ; j < i ; j++)
{
if(nums[i] > nums[j])
{
dp[i] = max(dp[i] , dp[j] + 1);
}
}
maxn = max(maxn , dp[i]);
}
return maxn;
}
private:
int dp[2501];
};(medium)120. 三角形最小路径和
dp[i][j] = triangle[i][j] + min(dp[i + 1][j] , dp[i + 1][j + 1])，就这个公式。不过需要注意，dp[i][j]可能为0，所以不能用dp[i][j]来判断i,j是否访问过，还要开一个数组才行。代码如下：
class Solution {
public:
int dfs(vector<vector<int>>& triangle , int x , int y)
{
if(x >= n)
return 0;
if(y >= n)
return 0;
if(vis[x][y])
return dp[x][y];
dp[x][y] = triangle[x][y] + min(dfs(triangle , x + 1 , y) , dfs(triangle , x + 1 , y + 1));
vis[x][y] = 1;
return dp[x][y];
}
int minimumTotal(vector<vector<int>>& triangle) {
n = triangle.size();
return dfs(triangle , 0 , 0);
}
private:
int n;
bool vis[201][201];
int dp[201][201];
};(medium)64. 最小路径和
递归，dp[i][j]表示从左上角到i,j的最小路径，搜索起点是m - 1 , n - 1。dp[i][j] = grid[i][j] + min(dp[i - 1][j] , dp[i][j - 1])。本来最开始是如果超界就返回INT_MAX，但因为编译器检测到有存在a+INT_MAX超界限的可能，所以超界就返回-1。代码如下：
class Solution {
public:
int dfs(vector<vector<int>>& grid , int x , int y)
{
if(x < 0 || y < 0)
return -1;
if(vis[x][y])
return dp[x][y];
vis[x][y] = 1;
int tmp1 = dfs(grid , x - 1 , y);
int tmp2 = dfs(grid , x , y - 1);
dp[x][y] = grid[x][y];
if(tmp1 == -1)
{
if(tmp2 != -1)
dp[x][y] += tmp2;
}
else if(tmp2 == -1)
{
dp[x][y] += tmp1;
}
else
{
dp[x][y] += min(tmp1 , tmp2);
}
return dp[x][y];
}
int minPathSum(vector<vector<int>>& grid) {
m = grid.size();
n = grid[0].size();
return dfs(grid , m - 1 , n - 1);
}
private:
int dp[201][201];
bool vis[201][201];
int m , n;
};(medium)63. 不同路径 II
思路同上，只不过dp[0][0]初始值为1(但如果obstacleGrid[0][0]=1那就直接返回0)。以及需要先跑完左边和上边的再判断当前位置是否为障碍物。代码如下：
class Solution {
public:
int dfs(vector<vector<int>>& obstacleGrid , int x , int y)
{
if(x < 0 || y < 0)
return 0;
if(vis[x][y])
return ans[x][y];
vis[x][y] = 1;
int tmp1 = dfs(obstacleGrid , x - 1 , y);
int tmp2 = dfs(obstacleGrid , x , y - 1);
if(obstacleGrid[x][y] == 1)
return 0;
ans[x][y] += tmp1 + tmp2;
return ans[x][y];
}
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
m = obstacleGrid.size();
n = obstacleGrid[0].size();
if(obstacleGrid[0][0] == 1)
return 0;
ans[0][0] = 1;
return dfs(obstacleGrid , m - 1 , n - 1);
}
private:
int m , n;
bool vis[101][101];
int ans[101][101];
};(medium)5. 最长回文子串
直接判断字符串是否是回文即可，唯一需要注意的就是别把s传参，会炸内存。dp是可做的，判断i~j是否为回文串，只需要判断i+1~j-1是否为回文子串同时i和j点的值是否相等即可，边界为长度为1的时候。但这道题我感觉不如直接暴力枚举。代码如下：
class Solution {
public:
bool check(int l , int r)
{
int df = r - l + 1;
int mid;
mid = l + (df >> 1);
if(df & 1)//abcba
{
for(int i = 0 ; i <= (df >> 1) ; i++)
{
if(tmp[mid - i] != tmp[mid + i])
return 0;
}
}
else//abccba
{
for(int i = 0 ; i < (df >> 1) ; i++)
{
if(tmp[mid - 1 - i] != tmp[mid + i])
return 0;
}
}
return 1;
}
string longestPalindrome(string s) {
cnt = 0;
n = s.length();
tmp = s;
for(int i = 0 ; i < n ; i++)
{
for(int j = max(i , i + cnt - 1) ; j < n ; j++)
{
if(j - i + 1 < cnt)
continue;
if(check(i , j))
{
cnt = j - i + 1;
ans_l = i;
ans_r = j;
}
}
}
return s.substr(ans_l , cnt);
}
private:
int n;
//长度
int cnt;
//左边界
int ans_l;
//右边界
int ans_r;
//临时存储
string tmp;
};dp的代码也写了一份，但效率不高，究其原因还是其把n*n的都跑出来了，而我的方法是只跑i到max(i,i+cnt-1)~n-1的字符串。代码如下：
class Solution {
public:
void dfs(int l , int r)
{
if(l >= r)
return ;
if(vis[l][r])
{
return ;
}
vis[l][r] = 1;
if(r - l == 1)
{
if(tmp[l] == tmp[r])
{
vis[l][r] = 2;
if(r - l + 1 > cnt)
{
cnt = r - l + 1;
ans_l = l;
ans_r = r;
}
}
}
else
{
dfs(l + 1 , r);
dfs(l , r - 1);
//l+1~r-1是回文
if(vis[l + 1][r - 1] == 2)
{
if((tmp[l] == tmp[r]))
{
vis[l][r] = 2;
if(r - l + 1 > cnt)
{
cnt = r - l + 1;
ans_l = l;
ans_r = r;
}
}
}
}
return ;
}
string longestPalindrome(string s) {
int n = s.length();
if(n == 0)
return "";
tmp = s;
for(int i = 0 ; i < n ; i++)
vis[i][i] = 2;
cnt = 1;
ans_l = 0;
ans_r = 0;
dfs(0 , n - 1);
return s.substr(ans_l , cnt);
}
private:
string tmp;
int ans_l;
int ans_r;
int cnt;
int vis[1001][1001];
};(medium)97. 交错字符串
vis[i][j][k]表示i之前的s1被使用，j之前的s2被使用，k之前的s3被使用后能否交错，为2表示能，为1表示不能，为0表示未访问。三维dp代码如下：
class Solution {
public:
//l1表示在l1之前的s1字符串都被用，l2表示在l2之前的s2字符串都被用了，l3是l3之前的s3字符串都已匹配了。l1 l2 l3均未被使用
void check(int l1 , int l2 , int l3)
{
if(l3 > n3)
{
return ;
}
if(vis[l1][l2][l3])
return ;
if(l3 == n3)
{
vis[l1][l2][l3] = 2;
return ;
}
vis[l1][l2][l3] = 1;
if(tmp1[l1] == tmp3[l3])
{
check(l1 + 1 , l2 , l3 + 1);
if(vis[l1 + 1][l2][l3 + 1] == 2)
{
vis[l1][l2][l3] = 2;
return ;
}
}
if(tmp2[l2] == tmp3[l3])
{
check(l1 , l2 + 1 , l3 + 1);
if(vis[l1][l2 + 1][l3 + 1] == 2)
{
vis[l1][l2][l3] = 2;
return ;
}
}
return ;
}
bool isInterleave(string s1, string s2, string s3) {
tmp1 = s1;
tmp2 = s2;
tmp3 = s3;
n1 = s1.length();
n2 = s2.length();
n3 = s3.length();
if(n1 + n2 != n3)
return 0;
check(0 , 0 , 0);
return vis[0][0][0] - 1;
}
private:
string tmp1;
string tmp2;
string tmp3;
int n1 , n2 , n3;
int vis[101][101][201];
};二维dp也写了个，dp[i][k]时的j=k-i，所以很简单就能降维，，代码如下：
class Solution {
public:
//l1表示在l1之前的s1字符串都被用，l2表示在l2之前的s2字符串都被用了，l3是l3之前的s3字符串都已匹配了。l1 l2 l3均未被使用
void check(int l1 , int l2 , int l3)
{
if(l3 > n3)
{
return ;
}
if(vis[l1][l3])
return ;
if(l3 == n3)
{
vis[l1][l3] = 2;
return ;
}
vis[l1][l3] = 1;
if(tmp1[l1] == tmp3[l3])
{
check(l1 + 1 , l2 , l3 + 1);
if(vis[l1 + 1][l3 + 1] == 2)
{
vis[l1][l3] = 2;
return ;
}
}
if(tmp2[l2] == tmp3[l3])
{
check(l1 , l2 + 1 , l3 + 1);
if(vis[l1][l3 + 1] == 2)
{
vis[l1][l3] = 2;
return ;
}
}
return ;
}
bool isInterleave(string s1, string s2, string s3) {
tmp1 = s1;
tmp2 = s2;
tmp3 = s3;
n1 = s1.length();
n2 = s2.length();
n3 = s3.length();
if(n1 + n2 != n3)
return 0;
check(0 , 0 , 0);
return vis[0][0] - 1;
}
private:
string tmp1;
string tmp2;
string tmp3;
int n1 , n2 , n3;
//vis[i][k]表示i之前的s1都被使用，k之前的s3都被比较，那么当前的j=k-i
int vis[101][201];
};(medium)221. 最大正方形
dp方程就是这个:num[x][y] = min(min(num[x - 1][y] , num[x][y - 1]) , num[x - 1][y - 1]) + 1。代码如下：
class Solution {
public:
void dfs(vector<vector<char>>& matrix , int x , int y)
{
if(x < 0 || y < 0 || vis[x][y])
{
return ;
}
vis[x][y] = 1;
dfs(matrix , x - 1 , y);
dfs(matrix , x , y - 1);
if(matrix[x][y] == '1')
{
num[x][y] = 1;
if(x >= 1 && y >= 1 && num[x - 1][y - 1])
num[x][y] = min(min(num[x - 1][y] , num[x][y - 1]) , num[x - 1][y - 1]) + 1;
ans = max(ans , num[x][y]);
}
return ;
}
int maximalSquare(vector<vector<char>>& matrix) {
m = matrix.size();
n = matrix[0].size();
ans = 0;
dfs(matrix , m - 1 , n - 1);
return ans*ans;
}
private:
int n , m;
int ans;
//num[x][y]表示以x,y为底的正方形最大边长,vis[x][y]表示x,y是否访问过
bool vis[301][301];
int num[301][301];
};