C/C++教程

leetcode二分算法学习笔记2021/10/10

本文主要是介绍leetcode二分算法学习笔记2021/10/10,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

因为vector是一个类模板,所以添加元素的时候要用到成员函数push_back

vector<int> arr;
int tmp = 0;
while(cin>>tmp){
   arr.push_back(tmp);
}

二分查找的关键是数组有序,这里题目中已经说了有序了,就不用自己排序了

自己在vscode里写全部代码的时候,怎么才能让arr数组和target分开呢?

因为cin输入只要满足条件,则cin会返回true,所以要让while循环停止就要用到cin的成员函数get,让cin检测到回车,也就是换行符'\n'就停止循环

int tmp = 0;
    while(cin>>tmp){
        arr.push_back(tmp);
        if(cin.get() == '\n') break;
    }

关于get函数的用法:

// This program demonstrates three ways to use cin.get()
// to pause a program.
#include <iostream>
using namespace std;
int main()
{
    char ch;
    cout << "This program has paused. Press Enter to continue.";
    cin.get(ch);//要读入字符到缓冲区,然后复制给ch
    cout << "It has paused a second time. Please press Enter again."; ch = cin.get();//要从缓冲区读入字符,然后复制给ch,本质上和第一种用法是一样的,这里也可以看出get是有一个返回值的,所以上面while里写的也是一种不错的方法
    cout << "It has paused a third time. Please press Enter again.";
    cin.get();//仅仅从缓冲区读入一个字符,然后什么都不做,所以此语句经常被用作暂停程序
    cout << "Thank you! \n";
    return 0;
}

而混合使用cin和cin.get会出现问题

char ch;    //定义一个字符变量
int number; //定义一个整型变量
cout << "Enter a number: ”;
cin >> number;   // 读取整数
//假设输入1然后按enter键,缓冲区中存储的是1'\n',cin读到换行符就停止了,就只把1读入了,缓冲区里还留着一个'\n'换行符,下面想通过cin.get读入一个数据的时候,因为get只读一个字符,就把缓冲区中的换行符给读了,没读到我们想输入的字符,这样的解决方法是使用两个get或者使用ignore,ignore还不知道是干什么用的,下次遇到再学习吧
cout << "Enter a character: ";
ch = cin.get() ;   // 读取字符
cout << "Thank You!\n";

最终代码

#include <iostream>
#include <vector>
using namespace std;
class Solution{
public:
    int search(vector<int>& nums, int target) {
       int low, mid, high;
       low = 0; high = nums.size();
       while(low <= high){
           mid = (low + high)/2;
           if(nums[mid] == target){
               return mid;
           }
           else if(target < nums[mid]){
               high = mid - 1;
           }
           else if(target > nums[mid]){
               low = mid + 1;
           }
       }
       return -1;
    }
    void cintarget(int &target){
        cin>>target;
    }
};//类的结尾需要分号
vector<int> arr;
int main(){
    int tmp = 0;
    while(cin>>tmp){
        arr.push_back(tmp);
        if(cin.get() == '\n') break;
    }
    int target = 0;
    Solution solution;
    solution.cintarget(target);
    cout<<solution.search(arr,target)<<endl;
}

这篇关于leetcode二分算法学习笔记2021/10/10的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!