剑指offer题解

剑指 Offer 03. 数组中重复的数字 - 力扣（LeetCode） (leetcode-cn.com)

 1 class Solution {
 2 public:
 3     int findRepeatNumber(vector<int>& nums) {
 4         int a[100000] = {0};
 5         for(int i=0;i){
 6             if(a[nums[i]] == 1)
 7                 return nums[i];
 8             a[nums[i]] = 1;
 9         }
10         return 0;
11     }
12 };

 剑指 Offer 04. 二维数组中的查找 - 力扣（LeetCode） (leetcode-cn.com)

 1 class Solution {
 2 public:
 3     bool ans = false;
 4     void f(vectorint>>& matrix,vectorint>>& vis,int target,int x,int y){
 5         if(x>=matrix.size()||y>=matrix[0].size())
 6             return ;
 7         if(vis[x][y])
 8             return ;
 9         vis[x][y] = 1;
10         if(target == matrix[x][y]){
11             ans = true;
12             return ;
13         }
14         if(x+1 < matrix.size()&&target >= matrix[x+1][y]&&vis[x+1][y] == 0)
15             f(matrix,vis,target,x+1,y);
16         if(y+1 < matrix[0].size()&&target >= matrix[x][y+1]&& vis[x][y+1] == 0)
17             f(matrix,vis,target,x,y+1);
18     }
19     bool findNumberIn2DArray(vectorint>>& matrix, int target) {
20         if(matrix.size() == 0)
21             return ans;
22         vectorint>> vis(matrix.size(),vector<int>(matrix[0].size(),0));
23         f(matrix,vis,target,0,0);
24         return ans;
25     }
26 };

 剑指 Offer 05. 替换空格 - 力扣（LeetCode） (leetcode-cn.com)

 1 class Solution {
 2 public:
 3     string replaceSpace(string s) {
 4         string ans = "";
 5         for(int i=0;i){
 6             if(s[i]!=' ')
 7                 ans+=s[i];
 8             else
 9                 ans+="%20";
10         }
11         return ans;
12     }
13 };

 剑指 Offer 06. 从尾到头打印链表 - 力扣（LeetCode） (leetcode-cn.com)

 1 class Solution {
 2 public:
 3     vector<int> reversePrint(ListNode* head) {
 4         ListNode* pre = nullptr,*cur = head;
 5         while(cur){
 6             ListNode *t = cur->next;
 7             cur->next = pre;
 8             pre = cur;
 9             cur = t;
10         }
11         vector<int> ans;
12         while(pre){
13             ans.push_back(pre->val);
14             pre = pre->next;
15         }
16         return ans;
17     }
18 };

剑指 Offer 07. 重建二叉树 - 力扣（LeetCode） (leetcode-cn.com)

 1 class Solution {
 2 public:
 3     TreeNode* f(vector<int>& preorder, vector<int>& inorder,int leftp,int rightp,int lefti,int righti){
 4         if(leftp>rightp||lefti>righti)
 5             return nullptr;
 6         TreeNode* root = new TreeNode(preorder[leftp]);
 7         int mid;
 8         for(int i=lefti;i<=righti;i++){
 9             if(inorder[i] == preorder[leftp]){
10                 mid = i;
11                 break;
12             }
13         }
14         int leftlen = mid-lefti+1;
15         root->left = f(preorder,inorder,leftp+1,leftp+leftlen-1,lefti,mid-1);
16         root->right = f(preorder,inorder,leftp+leftlen,rightp,mid+1,righti);
17         return root;
18     }
19     TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
20         return f(preorder,inorder,0,preorder.size()-1,0,inorder.size()-1);
21 
22     }
23 };

 剑指 Offer 09. 用两个栈实现队列 - 力扣（LeetCode） (leetcode-cn.com)

 1 class CQueue {
 2 public:
 3     CQueue() {
 4 
 5     }
 6     stack<int> s1,s2;
 7     void appendTail(int value) {
 8         s1.push(value);
 9     }
10     
11     int deleteHead() {
12         if(s2.empty()){
13             while(!s1.empty()){
14                 s2.push(s1.top());
15                 s1.pop();
16             }
17             
18         }
19         if(s2.empty())
20             return -1;
21         int head = s2.top();
22         s2.pop();
23         return head;
24     }
25 };

 剑指 Offer 10- I. 斐波那契数列 - 力扣（LeetCode） (leetcode-cn.com)

 1 class Solution {
 2 public:
 3     int fib(int n) {
 4         long a = 0,b = 1;
 5         if(n==0)
 6             return a;
 7         while(n>=2){
 8             long c = a+b%1000000007;
 9             a = b;
10             b = c;
11             n--;
12         }
13         return b%1000000007;
14     }
15 };

 剑指 Offer 10- II. 青蛙跳台阶问题 - 力扣（LeetCode） (leetcode-cn.com)

 1 class Solution {
 2 public:
 3     int numWays(int n) {
 4         long a = 1,b = 2;
 5         if(n==0||n==1)
 6             return a;
 7         while(n>2){
 8             long c = a+b%1000000007;
 9             a = b;
10             b = c;
11             n--;
12         }
13         return b%1000000007;
14     }
15 };

剑指 Offer 11. 旋转数组的最小数字 - 力扣（LeetCode） (leetcode-cn.com)

 1 class Solution {
 2 public:
 3     int minArray(vector<int>& numbers) {
 4         int l = 0,r = numbers.size()-1;
 5         while(l<r){
 6             int mid  =(l+r)/2;
 7             if(numbers[mid]>numbers[r]){
 8                 l = mid+1;
 9             }else if(numbers[mid]<numbers[r]){
10                 r = mid;//细节边界
11             }else{
12                 r--;
13             }
14         }
15         return numbers[l];
16     }
17 };

 剑指 Offer 12. 矩阵中的路径 - 力扣（LeetCode） (leetcode-cn.com)

这道题真离谱，多一点点代码都过不了

 1 class Solution {
 2 public:
 3     bool exist(vectorchar>>& board, string word) {
 4         rows = board.size();
 5         cols = board[0].size();
 6         for(int i = 0; i < rows; i++) {
 7             for(int j = 0; j < cols; j++) {
 8                 if(dfs(board, word, i, j, 0)) return true;
 9             }
10         }
11         return false;
12     }
13 private:
14     int rows, cols;
15     bool dfs(vectorchar>>& board, string word, int i, int j, int k) {
16         if(i >= rows || i < 0 || j >= cols || j < 0 || board[i][j] != word[k]) return false;
17         if(k == word.size() - 1) return true;
18         board[i][j] = '\0';
19         bool res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) || 
20                       dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i , j - 1, k + 1);
21         board[i][j] = word[k];
22         return res;
23     }
24 };