以下题目均来自leetcode、poj
二分查找
首先，假设表中元素是按升序排列（也可是降序），将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
//二分查找递归
bool binary_search(std::vector<int> &sort_array,
int begin,int end,int target){
if(begin > end){
return false;
}
int mid = (begin+end)/2;
if(target == sort_arry[mid]){
return true;
}else if(target < sort_arry[mid]){
return binary_search(sort_array,begin,mid-1,target);
}else if(target > sort_arry[mid])){
return binary_search(sort_array,mid+1,end,target);
}
}
//二分查找循环
bool binary_search(std::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_arry[mid]){
return true;
}else if(target < sort_arry[mid]){
end = mid -1;
}else if(target > sort_arry[mid])){
begin = mid + 1;
}
}
return false;
}
搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
输入: [1,3,5,6], 5 输出: 2 示例 2:
输入: [1,3,5,6], 2 输出: 1 示例 3:
输入: [1,3,5,6], 7 输出: 4 示例 4:
输入: [1,3,5,6], 0 输出: 0
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int index = -1;//未找到
int begin = 0;
int end = num.size()-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 == num.size() - 1 || target < nums[mid+1]){
index = mid + 1;
}
begin = mid+1;
}
}
return index;
}
};
在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8 输出: [3,4] 示例 2:
输入: nums = [5,7,7,8,8,10], target = 6 输出: [-1,-1]
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
std:vector<int> result;
result.push_back(leftBound(nums,target));
result.push_back(rightBound(nums,target));
return result;
}
private:
int leftBound(vector<int>& nums, int target) {
int begin = 0;
int end = num.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 rightBound(vector<int>& nums, int target) {
int begin = 0;
int end = num.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;
}
};
搜索旋转排序数组
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。
示例 1:
输入: nums = [4,5,6,7,0,1,2], target = 0 输出: 4 示例 2:
输入: nums = [4,5,6,7,0,1,2], target = 3 输出: -1
//部分有序，部分无序
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(mums[mid] < mums[end] ){//如果中间的数小于最右边的数，则右半段是有序的
//保留有序部分去找
if(nums[mid] < target && target <= nums[end]){
begin = mid + 1;
}else{
end = mid - 1;
}
}else if(mums[mid] > mums[end]){//若中间数大于最右边数，则左半段是有序的
if(nums[begin] <= target && target < nums[mid]){
end = mid - 1;
}else{
begin = mid + 1;
}
}
}
return -1;
}
};
二叉排序树
二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有节点的值均小于它的根节点的值；
（2）若右子树不空，则右子树上所有节点的值均大于它的根节点的值；
（3）左、右子树也分别为二叉排序树；
（4）没有键值相等的节点。
二叉查找树的中序遍历是从小到大的。
void BST_insert(TreeNode* node,TreeNode* insertNode){
if(indertNode->val < node->val){
if(node->left){
BST_insert(node->left,insertNode);
}else{
node->left = indertNode->val;
}
}else{
if(node->right){
BST_insert(node->right,insertNode);
}else{
node->right = insertNode->val;
}
}
}
void BST_search(TreeNode* node,int value){
if(value == node->val){
return true;
}
if(value < node->val){
if(node->left){
return BST_insert(node->left,value);
}else{
return false;
}
}else{
if(node->right){
return BST_insert(node->right,value);
}else{
return false;
}
}
}
Serialize and Deserialize BST
Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.
Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary search tree can be serialized to a string and this string can be deserialized to the original tree structure.
The encoded string should be as compact as possible.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
//前序
class Codec {
public:
void change_int_to_string(int val,std::string &str_val){
std::string temp;
while(val){
temp +=val%10+'0';
val = val/10;
}
for(int i = temp.length() - 1;i >= 0;i--){
str_val+=temp[i];
}
str_val += "#";
}
void BST_preorder(TreeNode *node,std::string &data){
if(!node){
return;
}
std::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) {
std::string data;
BST_preorder(root,data);
return data;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
if(data.length() == 0){
return NULL;
}
std:vector<TreeNode*> node_vec;
int val = 0;
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];
}
};
// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));
计算右侧小于当前元素的个数
给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
示例:
输入: [5,2,6,1] 输出: [2,1,1,0] 解释: 5 的右侧有 2 个更小的元素 (2 和 1). 2 的右侧仅有 1 个更小的元素 (1). 6 的右侧有 1 个更小的元素 (1). 1 的右侧有 0 个更小的元素.
//反序后，求前面有多少个比target小
struct TreeNode {
int val;
int count;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL),count(0) {}
};
class Solution {
public:
void BST_insert(TreeNode* node,TreeNode* insertNode,int &countSmall){
if(indertNode->val < node->val){
node->count++;
if(node->left){
BST_insert(node->left,insertNode,countSmall);
}else{
node->left = indertNode->val;
}
}else{
countSmall+=node->count+1;
if(node->right){
BST_insert(node->right,insertNode,countSmall);
}else{
node->right = insertNode->val;
}
}
vector<int> countSmaller(vector<int>& nums) {
std::vector<int> result;
std::vector<TreeNode*> node_vec;
std::vector<int> count;
for(int i = nums.size() -1;i >= 0;i--){
node_vec.push_back(new TreeNode(nums[i]));
}
count.push_back(0);
for(int i = 1;i < node_vec.size();i++){
int count_small = 0;
BST_insert(node_vec[0],node_vec[1],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;
}
};
