文章目錄

• • • 1.預備知識
    • • 1.1 題目目錄
      • 1.2 二分查找
      • 1.3 遞歸二分查找
      • 1.4 循環二分查找
      • 1.5 二叉查找（排序）樹
      • 1.6 二叉搜索樹的代碼實現
    • 2.搜索插入位置
    • • 2.1 題目描述
      • 2.2 C++代碼實現
    • 3.區間查找
    • • 3.1 題目描述
      • 3.2 算法思路
      • 3.3 C++代碼實現
    • 4.旋轉數組查找
    • • 4.1 題目描述
      • 4.2 解題思路
      • 4.3 C++代碼實現
    • 5.序列化和反序列化二叉搜索樹
    • • 5.1 題目描述
      • 5.2 算法思路
      • 5.3 C++代碼實現
    • 6.計算右側小于當前元素的個數
    • • 6.1 題目描述
      • 6.2 算法思路
      • 6.3 C++代碼實現

1.預備知識

1.1 題目目錄

1.2 二分查找

1.3 遞歸二分查找

bool binary_search(vector<int>& sort_array, int begin, int end, int target) {if (begin>end) {return false;}int mid = (begin + end) / 2;if (target == sort_array[mid]) {return true;}else if (target < sort_array[mid]) {binary_search(sort_array, begin, mid - 1, target);}else if (target > sort_array[mid]) {binary_search(sort_array, mid + 1, end, target);} }

1.4 循環二分查找

bool binary_search(vector<int>& sort_array, int target) {int begin = 0;int end = sort_array.size() - 1;while (begin<=end) {int mid = (begin + end) / 2;if (target == sort_array[mid]) {return true;}else if(target < sort_array[mid]) {end = mid - 1;}else if (target > sort_array[mid]) {begin = mid + 1;}}return false; }

1.5 二叉查找（排序）樹

1.6 二叉搜索樹的代碼實現

1.二叉搜索樹的插入

void solution::BST_insert(TreeNode* node, TreeNode* insert_node) {if (insert_node->val < node->val) {if (node->left) {BST_insert(node->left, insert_node);}else {node->left = insert_node;}}else {if (node->right) {BST_insert(node->right, insert_node);}else {node->right = insert_node;}} }

2.二叉搜索樹的搜索

bool solution::BST_search(TreeNode* node, int value) {if (value == node->val) {return true;}else if (value < node->val) {if (node->left) {BST_search(node->left, value);}else {return false;}}else if (value > node->val) {if (node->right) {BST_search(node->right, value);}else {return false;}} }

2.搜索插入位置

2.1 題目描述

給定一個排序數組和一個目標值，在數組中找到目標值，并返回其索引。如果目標值不存在于數組中，返回它將會被按順序插入的位置。

你可以假設數組中無重復元素。

2.2 C++代碼實現

class Solution { public:int searchInsert(vector<int>& nums, int target) {int begin=0;int end=nums.size()-1;int index=-1;while(index==-1){int mid=(begin+end)/2;if(target==nums[mid]){index=mid;}else if(target<nums[mid]){if(mid==0||target>nums[mid-1]){index=mid;}end=mid-1;}else if(target>nums[mid]){if(mid==nums.size()-1||target<nums[mid+1]){index= mid+1;}begin=mid+1;}}return index;} };

3.區間查找

3.1 題目描述

給定一個按照升序排列的整數數組 nums，和一個目標值 target。找出給定目標值在數組中的開始位置和結束位置。

如果數組中不存在目標值 target，返回 [-1, -1]。

3.2 算法思路

3.3 C++代碼實現

class Solution { public:int left_bound(vector<int>& nums,int target){int begin=0;int end=nums.size()-1;while(begin<=end){int mid=(begin+end)/2;if(target==nums[mid]){if(mid==0||target>nums[mid-1]){return mid;}end=mid-1;}else if(target<nums[mid]){end=mid-1;}else if(target>nums[mid]){begin=mid+1;}}return -1;}int right_bound(vector<int>& nums,int target){int begin=0;int end=nums.size()-1;while(begin<=end){int mid=(begin+end)/2;if(target==nums[mid]){if(mid==nums.size()-1||target<nums[mid+1]){return mid;}begin=mid+1;}else if(target<nums[mid]){end=mid-1;}else if(target>nums[mid]){begin=mid+1;}}return -1;}vector<int> searchRange(vector<int>& nums, int target) {int left=left_bound(nums,target);int right=right_bound(nums,target);vector<int> result;result.push_back(left);result.push_back(right);return result;} };

4.旋轉數組查找

4.1 題目描述

整數數組 nums 按升序排列，數組中的值 互不相同 。

在傳遞給函數之前，nums 在預先未知的某個下標 k（0 <= k < nums.length）上進行了 旋轉，使數組變為 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下標 從 0 開始 計數）。例如， [0,1,2,4,5,6,7] 在下標 3 處經旋轉后可能變為 [4,5,6,7,0,1,2] 。

給你 旋轉后 的數組 nums 和一個整數 target ，如果 nums 中存在這個目標值 target ，則返回它的下標，否則返回 -1 。

4.2 解題思路

4.3 C++代碼實現

class Solution { public:int search(vector<int>& nums, int target) {int begin=0;int end=nums.size()-1;while(begin<=end){int mid=(begin+end)/2;if(target==nums[mid]){return mid;}else if(target<nums[mid]){if(nums[begin]<nums[mid]){if(target>=nums[begin]){end=mid-1;}else{begin=mid+1;}}else if(nums[begin]>nums[mid]){end=mid-1;}else if(nums[begin]==nums[mid]){begin=mid+1;}}else if(target>nums[mid]){if(nums[begin]<nums[mid]){begin=mid+1;}else if(nums[begin]>nums[mid]){if(target>=nums[begin]){end=mid-1;}else{begin=mid+1;}}else if(nums[begin]==nums[mid]){begin=mid+1;}}}return -1;} };

5.序列化和反序列化二叉搜索樹

5.1 題目描述

序列化是將數據結構或對象轉換為一系列位的過程，以便它可以存儲在文件或內存緩沖區中，或通過網絡連接鏈路傳輸，以便稍后在同一個或另一個計算機環境中重建。

設計一個算法來序列化和反序列化 二叉搜索樹 。 對序列化/反序列化算法的工作方式沒有限制。 您只需確保二叉搜索樹可以序列化為字符串，并且可以將該字符串反序列化為最初的二叉搜索樹。

編碼的字符串應盡可能緊湊。

5.2 算法思路

5.3 C++代碼實現

class Codec { public:void BST_insert(TreeNode* node, TreeNode* insert_node) {if (insert_node->val < node->val) {if (node->left) {BST_insert(node->left, insert_node);}else {node->left = insert_node;}}else {if (node->right) {BST_insert(node->right, insert_node);}else {node->right = insert_node;}}}void change_int_to_string(int val, string& str_val) {string tmp;while (val) {tmp += val % 10 + '0';val = val / 10;}for (int i = tmp.length()- 1; i >= 0; i--) {str_val += tmp[i];}str_val += '#';}/*9.2 將二叉查找樹按照前序遍歷的方式，轉化為字符串，數字之間使用#隔開*/void BST_preorder(TreeNode* node, string& data) {if (!node) {return;}string str_val;change_int_to_string(node->val, str_val);data += str_val;BST_preorder(node->left, data);BST_preorder(node->right, data);}// Encodes a tree to a single string.string serialize(TreeNode* root) {string data;BST_preorder(root,data);return data; }// Decodes your encoded data to tree.TreeNode* deserialize(string data) {int val=0;vector<TreeNode*> node_vec;if(data.length()==0){return NULL;} for(int i=0;i<data.length();i++){if(data[i]=='#'){node_vec.push_back(new TreeNode(val));val=0;}else{val=val*10+(data[i]-'0');}}for(int i=1;i<node_vec.size();i++){BST_insert(node_vec[0],node_vec[i]);}return node_vec[0];} };

6.計算右側小于當前元素的個數

6.1 題目描述

給定一個整數數組 nums，按要求返回一個新數組 counts。數組 counts 有該性質： counts[i] 的值是 nums[i] 右側小于 nums[i] 的元素的數量。

示例：
輸入：nums = [5,2,6,1]
輸出：[2,1,1,0]
解釋：
5 的右側有 2 個更小的元素 (2 和 1)
2 的右側僅有 1 個更小的元素 (1)
6 的右側有 1 個更小的元素 (1)
1 的右側有 0 個更小的元素

6.2 算法思路

6.3 C++代碼實現

struct BSTNode{int val;int count;BSTNode* left;BSTNode* right;BSTNode(int x):val(x),count(0),left(NULL),right(NULL){} };class Solution { public:void BSTInsert(BSTNode* node,BSTNode* insert_node,int& count_small){if(insert_node->val<=node->val){node->count++;if(node->left){BSTInsert(node->left,insert_node,count_small);}else{node->left=insert_node;}}else{count_small+=node->count+1;if(node->right){BSTInsert(node->right,insert_node,count_small);}else{node->right=insert_node;}}}vector<int> countSmaller(vector<int>& nums) {vector<int> result;vector<int> count;vector<BSTNode*> node_vec;for(int i=nums.size()-1;i>=0;i--){node_vec.push_back(new BSTNode(nums[i]));}count.push_back(0);for(int i=1;i<node_vec.size();i++){int count_small=0;BSTInsert(node_vec[0],node_vec[i],count_small);count.push_back(count_small);}for(int i=node_vec.size()-1;i>=0;i--){delete node_vec[i];result.push_back(count[i]);}return result;} };

總結

以上是生活随笔為你收集整理的数据结构与算法——二分查找与二叉排序树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。