c++ LeetCode (網易面試題和鏈表以及樹篇) 五道演算法例題程式碼詳解（三）

• 2019 年 10 月 6 日
• 筆記

一.1道網易c++的面試題

 我當時第一時間的解答方案

#include <iostream>  #include <vector>    using namespace std;    int main()  {  	const int Wi = 3840;  	const int Hi = 2160;  	int N,M;  	int temp;  	int x,y,w,h;  	int x1,y1;  	int b;  	vector<vector<int> > Windows(0, vector<int> (4));  	vector<int> Window;  	vector<vector<int> > pos(0, vector<int> (2));  	vector<int> po;  	vector<int> nums;      vector<int> SX;  	cin >> N >> M;  	if(N<=0 || M >= 1000) return 0;  	for(int i = 0;i < N;i++){          SX.emplace_back(N-i);  		cin>>x>>y>>w>>h;  		Window.emplace_back(x);  		Window.emplace_back(y);  		Window.emplace_back(w);  		Window.emplace_back(h);  		Windows.emplace_back(Window);  		Window.clear();  	}    	for(int j = 0; j < M; j++){  		cin>>x1>>y1;  		po.emplace_back(x1);  		po.emplace_back(y1);  		pos.emplace_back(po);  		po.clear();  	}  	for(int k = 0; k < M; k++){  		int flag = -1;  		for(int i = 0; i < N; i++){  			if(flag = -1)  			if(Windows[SX[i] - 1][0] <= pos[k][0] && (Windows[SX[i] -1][0]+Windows[SX[i] -1][2])>=pos[k][0] && Windows[SX[i]-1][1] <= pos[k][1] && (Windows[SX[i]-1][1]+Windows[SX[i]-1][3])>=pos[k][1]){  				flag = SX[i];  				int size = SX.size();  				for(int j = i - 1; j >= 0 ;j--){  					SX[j + 1] = SX[j];  				}  				SX[0] = flag;  				break;  			}    		}  		nums.emplace_back(flag);  		flag = -1;  	}  	for(auto num:nums){  		cout<<num<<endl;  	}  }

二.環形鏈表

給定一個鏈表，判斷鏈表中是否有環。

為了表示給定鏈表中的環，我們使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該鏈表中沒有環。

示例 1：

輸入：head = [3,2,0,-4], pos = 1  輸出：true  解釋：鏈表中有一個環，其尾部連接到第二個節點。

示例 2：

輸入：head = [1,2], pos = 0  輸出：true  解釋：鏈表中有一個環，其尾部連接到第一個節點。

示例 3：

輸入：head = [1], pos = -1  輸出：false  解釋：鏈表中沒有環。

進階：

你能用 O(1)（即，常量）記憶體解決此問題嗎？

我的程式碼：20ms

/**   * Definition for singly-linked list.   * struct ListNode {   *     int val;   *     ListNode *next;   *     ListNode(int x) : val(x), next(NULL) {}   * };   */  class Solution {  public:      bool hasCycle(ListNode *head) {          if(head == NULL) return false;          unordered_map<ListNode*,int> umap;          ListNode *node = head;          while(node->next != NULL){              umap[node]++;              if(umap[node] > 1) return true;              node = node->next;            }          return false;      }  };

我的思路就是把每個鏈表遍歷存儲在map容器中，出現已經存放的地址時申請再次存放時，這時候就是環形鏈表。

大佬們的程式碼5ms左右：

class Solution {  public:      bool hasCycle(ListNode *head) {          if(head == NULL)              return false;          ListNode *slow,*fast;          slow = head;          fast = head;          while(slow && fast)          {              slow = slow->next;              fast = fast->next;              if(fast)                  fast = fast->next;              else                  return false;              if(slow == fast)                  return true;          }          return false;      }  };

這個程式碼思路就是快慢指針，如果鏈表出現環形，那麼我的快慢指針一定會相遇。

3.二叉樹的最大深度：

給定一個二叉樹，找出其最大深度。

二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數。

說明: 葉子節點是指沒有子節點的節點。

示例： 給定二叉樹 [3,9,20,null,null,15,7]，

    3     /     9  20      /       15   7

返回它的最大深度 3

我的程式碼：16ms

/**   * Definition for a binary tree node.   * struct TreeNode {   *     int val;   *     TreeNode *left;   *     TreeNode *right;   *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}   * };   */  class Solution {  public:      int count = 0;      int max = 0;      int maxDepth(TreeNode* root) {          if(root == NULL) return 0;          count++;          if(count > max) max = count;          maxDepth(root->left);          maxDepth(root->right);          count--;          return max;      }  };

 我的思路就是全部遍歷一遍，記錄最大深度。

大佬的程式碼：4ms

/**   * Definition for a binary tree node.   * struct TreeNode {   *     int val;   *     TreeNode *left;   *     TreeNode *right;   *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}   * };   */  class Solution {  public:        int detectDepth(TreeNode* node) {          if (!node) return 0;          int leftDepth = 1 + detectDepth(node -> left);          int rightDepth = 1 +  detectDepth(node -> right);          return std::max(leftDepth, rightDepth);      }        int maxDepth(TreeNode* root) {          return detectDepth(root);      }  };

這個程式碼就是跟我的思路差不多，不過用遞歸的方法優化，比我好多了。

4.驗證二叉搜索樹

給定一個二叉樹，判斷其是否是一個有效的二叉搜索樹。

假設一個二叉搜索樹具有如下特徵：

• 節點的左子樹只包含小於當前節點的數。
• 節點的右子樹只包含大於當前節點的數。
• 所有左子樹和右子樹自身必須也是二叉搜索樹。

示例 1:

輸入:      2     /     1   3  輸出: true

示例 2:

輸入:      5     /     1   4       /       3   6  輸出: false  解釋: 輸入為: [5,1,4,null,null,3,6]。       根節點的值為 5 ，但是其右子節點值為 4 。    我的程式碼24ms

/**   * Definition for a binary tree node.   * struct TreeNode {   *     int val;   *     TreeNode *left;   *     TreeNode *right;   *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}   * };   */  class Solution {  public:      bool flag = 1;      int ergodic(TreeNode* root,long min,long max){          if(root == NULL) return 0;          if(root->left != NULL){              if(root->left->val >= root->val || root->left->val <= min){                  flag = 0;                  return 0;              }              ergodic(root->left,min,root->val);          }          if(root->right != NULL){              if(root->right->val <= root->val || root->right->val >= max){                  flag = 0;                  return 0;              }              ergodic(root->right,root->val,max);          }          return 0;      }      bool isValidBST(TreeNode* root) {          if(root == NULL) return 1;          if(root->left != NULL){              if(root->left->val >= root->val){                  flag = 0;                  return 0;              }              ergodic(root->left,LONG_MIN,root->val);          }          if(root->right != NULL){              if(root->right->val <= root->val){                  flag = 0;                  return 0;              }              ergodic(root->right,root->val,LONG_MAX);          }            return flag;      }  };

 我的方法就是遞歸遍歷加上數值判斷

大佬的程式碼：8ms

/**   * Definition for a binary tree node.   * struct TreeNode {   *     int val;   *     TreeNode *left;   *     TreeNode *right;   *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}   * };   */  class Solution {  public:      bool isValidBST(TreeNode* root, long long min = LONG_LONG_MIN, long long max = LONG_LONG_MAX) {          if(root == NULL)  return true;          if(root->val <= min || root->val >= max)      return false;            return isValidBST(root->left, min, root->val) && isValidBST(root->right, root->val, max);      }  };

這個程式碼其實思路是跟我差不多的，但是程式碼的簡潔和調用庫函數來判斷，比我那亂七八糟的好太多了。

5.對稱二叉樹

給定一個二叉樹，檢查它是否是鏡像對稱的。

例如，二叉樹 [1,2,2,3,4,4,3] 是對稱的。

    1     /     2   2   /  /   3  4 4  3

但是下面這個 [1,2,2,null,3,null,3] 則不是鏡像對稱的:

    1     /     2   2             3    3

說明:

如果你可以運用遞歸和迭代兩種方法解決這個問題，會很加分。

我的程式碼：8ms

/**   * Definition for a binary tree node.   * struct TreeNode {   *     int val;   *     TreeNode *left;   *     TreeNode *right;   *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}   * };   */  class Solution {  public:      int flag = 1;      int left = 0;      int right = 0;      vector<int> leftTree,rightTree;      void leftRecursiveComparison(TreeNode* root){          if(root){              left++;              leftRecursiveComparison(root->left);              leftTree.emplace_back(root->val);              leftRecursiveComparison(root->right);          }          else leftTree.emplace_back(left);      }      void rightRecursiveComparison(TreeNode* root){          if(root){              right++;              rightRecursiveComparison(root->right);              rightTree.emplace_back(root->val);              rightRecursiveComparison(root->left);          }          else rightTree.emplace_back(right);      }      bool isSymmetric(TreeNode* root) {          if(root == NULL) return true;          leftRecursiveComparison(root->left);          rightRecursiveComparison(root->right);          int lenLeft = leftTree.size();          int lenRight = rightTree.size();          if(lenLeft != lenRight) return false;          for(int i = 0; i < lenLeft; i++){              cout<<rightTree[i];              if(leftTree[i] != rightTree[i])                  return false;          }            return true;      }  };

 我的思路已經不想講了 ，直接看大佬的吧。

大佬們的程式碼：1ms左右

class Solution {  public:      bool isSymmetric(TreeNode* root) {          if(root==nullptr) return true;          return helper(root->left,root->right);      }      bool helper(TreeNode* left,TreeNode* right){          if(left==nullptr&&right==nullptr) return true;          if(left==nullptr||right==nullptr) return false;          return (left->val==right->val)&&helper(left->left,right->right)              &&helper(left->right,right->left);      }  };

大佬這個就是同時對兩邊的子樹進行遞歸遍歷，然後需要對稱的值進行判斷。

哎，看看自己跟大佬們的程式碼就知道差距了QAQ…………….