剑指offer第七、八天

1.矩阵中的路径

1. class Solution {
2.     int n, m;
3.     int dx[4]{ 1,-1,0,0 };
4.     int dy[4]{ 0,0,1,-1 };
6.     bool dfs(int i, int j, vector<vector<char> >mat,vector<vector<bool> >vis, int u, const char* str)
7.     {
8.         if (u == strlen(str)-1)
9.         {
10.             //刚开始这里我用的是strlen(str)，但是可能会有一种情况，需要矩阵中所有的元素去匹配，这样的话，我的方法就是错误的了，所以改成这样
11.             return mat[i][j] == str[u];
12.         }
13.         if (mat[i][j] != str[u])return false;
14.         for (int k = 0; k < 4; ++k)
15.         {
16.             int x = i + dx[k], y = j + dy[k];
17.             if (x >= 0 && x < n && y >= 0 && y < m && !vis[x][y])
18.             {
19.                 vis[x][y] = true;
20.                 if (dfs(x, y, mat,vis, u + 1, str))return true;
21.                 vis[x][y] = false;
23.             }
24.         }
25.         return false;
26.     }
27. public:
28.     bool hasPath(const char* matrix, int rows, int cols, const char* str)
29.     {
30.         n = rows, m = cols;
31.         int idx = 0;
32.         vector<vector<char> >mat(n, vector<char>(m));
33.         vector<vector<bool> >vis(n, vector<bool>(m));;
34.         for (int i = 0; i < n; ++i)
35.         {
36.             for (int j = 0; j < m; ++j)
37.             {
38.                 mat[i][j] = matrix[idx++];
39.             }
40.         }
41.         for (int i = 0; i < n; ++i)
42.         {
43.             for (int j = 0; j < m; ++j)
44.             {
45.                 vis[i][j] = true;
46.                 if (dfs(i, j, mat,vis, 0, str))
47.                     return true;
48.                 vis[i][j] = false;
49.             }
50.         }
51.         return false;
52.     }
53. };

复制代码

2.呆板人的活动路径

1. class Solution {
2. public:
3.     //记录遍历的四个方向
4.     int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
5.     //记录答案
6.     int res = 0;
7.     //计算一个数字的每个数之和
8.     int cal(int n){
9.         int sum = 0;
10.         //连除法算出每一位
11.         while(n){
12.             sum += (n % 10);
13.             n /= 10;
14.         }
15.         return sum;
16.     }
17.     //深度优先搜索dfs
18.     void dfs(int i, int j, int rows, int cols, int threshold, vector<vector<bool> >& vis){
19.         //越界或者已经访问过
20.         if(i < 0 || i >= rows || j < 0 || j >= cols || !vis[i][j])
21.             return;
22.         //行列和数字相加大于threshold，不可取
23.         if(cal(i) + cal(j) > threshold)
24.             return;
25.         res += 1;
26.         //标记经过的位置
27.         vis[i][j] = false;
28.         //上下左右四个方向搜索
29.         for(int k = 0; k < 4; k++)
30.             dfs(i + dir[k][0], j + dir[k][1], rows, cols, threshold, vis);
31.     }
32.    
33.     int movingCount(int threshold, int rows, int cols) {
34.         //判断特殊情况
35.         if(threshold <= 0)
36.             return 1;
37.         //标记某个格子没有被访问过
38.         vector<vector<bool> > vis(rows, vector<bool>(cols, true));
39.         dfs(0, 0, rows, cols, threshold, vis);
40.         return res;
41.     }
42. };

复制代码

3.数组中重复的数字

1. class Solution {
2.     int cnt[10010]{};
3. public:
4.     int duplicate(vector<int>& numbers) {
5.         // write code here
6.         for(int&x:numbers)
7.             if(cnt[x])return x;
8.             else cnt[x]++;
9.         return -1;
10.     }
11. };

复制代码

4.数组中的逆序对

1. class Solution {
2.     //使用归并排序的方法 来求解
3.     int n,temp[100010];
4.     const int mod = 1000000007;
5.     int merge_sort(vector<int>&nums,int l,int r)
6.     {
7.         if(l>=r)return 0;
8.         int mid = l+r>>1;
9.         int ans = (merge_sort(nums,l,mid) + merge_sort(nums,mid+1,r))%mod;
10.         int i = l,j = mid+1,idx = 0;
11.         while(i<=mid&&j<=r)
12.         {
13.             if(nums[i]<=nums[j])
14.             {
15.                 temp[idx++] = nums[i++];
16.             }
17.             else{
18.                 ans = (ans + mid-i+1)%mod;
19.                 temp[idx++] = nums[j++];
20.             }
21.         }
22.         while(i<=mid)temp[idx++] = nums[i++];
23.         while(j<=r)temp[idx++] = nums[j++];
24.         for(i =l,j = 0;i<=r;++i,++j)
25.             nums[i] = temp[j];
26.         return ans%mod;
27.     }
28. public:
29.     int InversePairs(vector<int>& nums) {
30.         // write code here
31.         n = nums.size();
32.         return merge_sort(nums,0,n-1);
33.     }
34. };

复制代码

5.最小的k个数

1. class Solution {
2. public:
4.     vector<int> GetLeastNumbers_Solution(vector<int>& input, int k) {
5.         // write code here
6.         priority_queue<int,vector<int>,greater<int> >pq;
7.         for(int&x:input)pq.push(x);
8.         vector<int>ans;
9.         while(k--)
10.         {
11.             ans.push_back(pq.top());
12.             pq.pop();
13.         }
14.         return ans;
15.     }
16. };

复制代码

6.数据流中的中位数

直接模仿

1. class Solution {
2. public:
3.     void Insert(int num) {
4.         result.push_back(num);
5.         n++;
6.     }
7.     double GetMedian() {
8.         sort(result.begin(),result.end());
9.         if(n%2)
10.         {
11.             return 1.0 * result[n/2];
12.         }
13.         else{
14.             int l = n/2;
15.             return (result[l]+result[l-1])/2.0;
16.         }
17.     }
18. private:
19.     vector<int>result;
20.     int n;
21. };

复制代码

7.不消加减乘除作加法

1. class Solution {
2.   public:
3.     int Add(int num1, int num2) {
4.         return num2 ? Add(num1 ^ num2, (num1 & num2) << 1) : num1;
6.     }
7. };

复制代码

8.二进制中1的个数

1. #include <bits/stdc++.h>
3. using namespace std;
5. int main()
6. {
7.         int x;
8.         cin>>x;
9.         int cnt = 0;
10.         while(x)
11.         {
12.                 cnt++;
13.                 x = x&(x-1);
14.         }
15.         cout<<cnt<<'\n';
16.         return 0;
17. }

复制代码

9数值的整数次方

1. class Solution {
2.     //快速幂
3.     double quickpow(double a,int n)
4.     {
5.         double ans = 1.0;
6.         for(;n;n>>=1)
7.         {
8.             if(n&1)
9.             {
10.                 ans *= a;
11.             }
12.             a = a * a;
13.         }
14.         return ans;
15.     }
16. public:
17.     double Power(double base, int exponent) {
18.         int p = abs(exponent);
19.         if(exponent<0)
20.         {
21.             return 1.0/quickpow(base,p);
22.         }
23.         else{
24.             return quickpow(base,p);
25.         }
26.     }
27. };

复制代码