剑指offer第七、八天

1.矩阵中的路径

class Solution {int n, m;int dx[4]{ 1,-1,0,0 };int dy[4]{ 0,0,1,-1 };bool dfs(int i, int j, vector<vector<char> >mat,vector<vector<bool> >vis, int u, const char* str){if (u == strlen(str)-1){//刚开始这里我用的是strlen(str)，但是可能会有一种情况，需要矩阵中所有的元素去匹配，这样的话，我的方法就是错误的了，所以改成这样return mat[i][j] == str[u];}if (mat[i][j] != str[u])return false;for (int k = 0; k < 4; ++k){int x = i + dx[k], y = j + dy[k];if (x >= 0 && x < n && y >= 0 && y < m && !vis[x][y]){vis[x][y] = true;if (dfs(x, y, mat,vis, u + 1, str))return true;vis[x][y] = false;}}return false;}
public:bool hasPath(const char* matrix, int rows, int cols, const char* str){n = rows, m = cols;int idx = 0;vector<vector<char> >mat(n, vector<char>(m));vector<vector<bool> >vis(n, vector<bool>(m));;for (int i = 0; i < n; ++i){for (int j = 0; j < m; ++j){mat[i][j] = matrix[idx++];}}for (int i = 0; i < n; ++i){for (int j = 0; j < m; ++j){vis[i][j] = true;if (dfs(i, j, mat,vis, 0, str))return true;vis[i][j] = false;}}return false;}
};

2.机器人的运动路径

class Solution {
public://记录遍历的四个方向int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};//记录答案int res = 0;//计算一个数字的每个数之和int cal(int n){int sum = 0;//连除法算出每一位while(n){sum += (n % 10);n /= 10;}return sum;}//深度优先搜索dfsvoid dfs(int i, int j, int rows, int cols, int threshold, vector<vector<bool> >& vis){//越界或者已经访问过if(i < 0 || i >= rows || j < 0 || j >= cols || !vis[i][j])return;//行列和数字相加大于threshold，不可取if(cal(i) + cal(j) > threshold)return;res += 1;//标记经过的位置vis[i][j] = false;//上下左右四个方向搜索for(int k = 0; k < 4; k++)dfs(i + dir[k][0], j + dir[k][1], rows, cols, threshold, vis);}int movingCount(int threshold, int rows, int cols) {//判断特殊情况if(threshold <= 0)return 1;//标记某个格子没有被访问过vector<vector<bool> > vis(rows, vector<bool>(cols, true));dfs(0, 0, rows, cols, threshold, vis);return res;}
};

3.数组中重复的数字

class Solution {int cnt[10010]{};
public:int duplicate(vector<int>& numbers) {// write code herefor(int&x:numbers)if(cnt[x])return x;else cnt[x]++;return -1;}
};

4.数组中的逆序对

class Solution {//使用归并排序的方法 来求解int n,temp[100010];const int mod = 1000000007;int merge_sort(vector<int>&nums,int l,int r){if(l>=r)return 0;int mid = l+r>>1;int ans = (merge_sort(nums,l,mid) + merge_sort(nums,mid+1,r))%mod;int i = l,j = mid+1,idx = 0;while(i<=mid&&j<=r){if(nums[i]<=nums[j]){temp[idx++] = nums[i++];}else{ans = (ans + mid-i+1)%mod;temp[idx++] = nums[j++];}}while(i<=mid)temp[idx++] = nums[i++];while(j<=r)temp[idx++] = nums[j++];for(i =l,j = 0;i<=r;++i,++j)nums[i] = temp[j];return ans%mod;}
public:int InversePairs(vector<int>& nums) {// write code heren = nums.size();return merge_sort(nums,0,n-1);}
};

5.最小的k个数

class Solution {
public:vector<int> GetLeastNumbers_Solution(vector<int>& input, int k) {// write code herepriority_queue<int,vector<int>,greater<int> >pq;for(int&x:input)pq.push(x);vector<int>ans;while(k--){ans.push_back(pq.top());pq.pop();}return ans;}
};

6.数据流中的中位数

直接模拟

class Solution {
public:void Insert(int num) {result.push_back(num);n++;}double GetMedian() { sort(result.begin(),result.end());if(n%2){return 1.0 * result[n/2];}else{int l = n/2;return (result[l]+result[l-1])/2.0;}}
private:vector<int>result;int n;
};

7.不用加减乘除作加法

class Solution {public:int Add(int num1, int num2) {return num2 ? Add(num1 ^ num2, (num1 & num2) << 1) : num1;}
};

8.二进制中1的个数

#include <bits/stdc++.h>using namespace std;int main()
{int x;cin>>x;int cnt = 0;while(x){cnt++;x = x&(x-1);}cout<<cnt<<'\n';return 0;
}

9数值的整数次方

class Solution {//快速幂double quickpow(double a,int n){double ans = 1.0;for(;n;n>>=1){if(n&1){ans *= a;}a = a * a; }return ans;}
public:double Power(double base, int exponent) {int p = abs(exponent);if(exponent<0){return 1.0/quickpow(base,p);}else{return quickpow(base,p);}}
};