二分查找

題目

思路

這道題就是一道很簡單的二分查找，但也有我們很多要注意的地方，區間的劃分最為關鍵，
其實區間劃分的問題，一般我們有兩種區間劃分的方法，1，[left,right-1] 2,[left,right) ,這兩種劃分是等價的，其次你還要搞明白，[right,right]這個區間是有意思的，因為你可以取到right這個位置的值，而[right,right)這個區間是沒有意義的，因為你取不到right這個地方的值，當你明白了這幾個點了之后，區間的劃分就變的十分簡單了，

首先的先用之前在y總那記的二分模板來寫了下，

          /*  y總那學習的模板
          int r=nums.size()-1,l=0,mid=0;
          while(l<r)
          {
              mid=(l+r)>>1;
              if(nums[mid]>=target)  r=mid;
              else l=mid+1;
          }
          if(nums[r]==target) return r;
          else return -1;
          */

他的模板確實很簡單，這是不易理解， 很多人可能第一感覺應該是寫if(nums[mid]=target) return mid,其實是不行的，你只要去舉幾個例子就知道了，寫成nums[r]和nums[l]都是可以的，

代碼隨想錄那兒的兩種寫法
1，區間劃分成[left，right]

//取左閉右閉區間
          /*int left=0,right=nums.size()-1; //因為是右閉，所以這兒right取nums.size()-1
          int mid=0;
          while(left<=right)  //這兒要有等于號，因為當left==right時，【right，right】這個區間也是有意義的
          {
              mid=(left+right)>>1;
              if(nums[mid]>target)  right=mid-1;  // 此時說明答案在mid的左邊，而且mid這個位置
                                                  //一定大于target，且區間是右閉，所以區間更新
                                                  // 為【0，mid-1】
              else if(nums[mid]<target) left=mid+1; //理由和推理同上
              else  return mid;
          }
          return -1;*/

2,區間劃分成[left,nums.size() )

 //左閉右開的寫法
          int left=0,right=nums.size(); //因為右區間開的，所以區間[0,nums.size() )可以確保遍歷
                                        //完整個陣列 
          int mid=0;
          while(left<right)   //因為是左開右閉，所以當left==right時，[right,right)這個區間是沒有
                              //意義的
        {
            mid=(left+right)>>1;
            if(nums[mid]>target)  right=mid; //此時說明答案在左區間[left,mid-1],而這種情況的
                                             //為左開右閉，所以區間[left,mid)等價于[left,mid-1]
            else if(nums[mid]<target)  left=mid+1; // 此時說明答案在右區間[mid+1,nums.size-1]
                                                   // 而區間[mid+1,nums.size)等價于此區間
            else return mid;
        }
        return -1;

移除元素

題目

思路

首先要明白一點，要想從陣列中移除元素肯定是不可能的，因為陣列中的空間是連續的，所以我們只能采用元素覆寫的方法，想到這，一個思路也就來了：我們可以用一個for回圈遍歷陣列，找到等于val的位置，然后將其之后的元素往前移一位，達到覆寫它的目的，

    int size=nums.size();
    for(int i=0;i<size;i++)
    {
        if(nums[i]==val)
        {
            for(int j=i+1;j<size;j++)
            {
                    nums[j-1]=nums[j];
            }
            i--;
            size--;
        }
    }
    return size;

注意：要記得i–和size–，因為你將后面所有的元素往前移一位時，你i本身這個位置也要往前移一位，同時你覆寫了你個等于val的位置，所以要size–，

像這種兩層for回圈可以暴力求解的題目，往往可以用雙指標來優化，已達到用一個for回圈就可以做出來的目的，

        /*  雙指標法
        int fast=0,slow=0;
        for(fast=0;fast<nums.size();fast++)
        {
            if(nums[fast]!=val)
            {
                nums[slow++]=nums[fast];
            }
        }
        return slow;

帶分數

題目

剛拿到這題時我是迷茫的，根本沒有任何的思路，我一開始想找找看，是否具有什么規律，發現并不行，因為你無法確保它里面包含每一個數字，后來看了題解之后，才恍然大悟，既然我們不能正向推導，保證它里面包含所有的數字，那為什么我們不反過來想了，我們列舉出1到9的所有全排列，然后將這9個數分成3組，分別對應這a，b，c，這樣就確保了a，b，c這三個數中一定包含了1到9，而且不會有重復，之后我們判斷a，b，c這三個數是否滿足等于n的關系即可，

#include<iostream>
using namespace std;
const int N=10;
int backup[N]; //用來存放不同排列組合結果的陣列
bool st[N];
int n;
int res;

int cal(int l,int r)  //將陣列中的數分離出來的方法，
{
    int ans=0;
    for(int i=l;i<=r;i++)
    {
        ans=ans*10+backup[i];
    }
    return ans;
}


void dfs(int u)
{
    if(u>9)  //因為陣列是從1開始放的，所以最后結束的時候是10
    {
        for(int i=1;i<8;i++)   //因為存放的陣列是從1開始的
        {
            for(int j=i+1;j<9;j++)
            {
                    int a=cal(0,i);
                    int b=cal(i+1,j);
                    int c=cal(j+1,9);
                    if(a*c+b==n*c)
                    {
                        res++;
                    }
            }
        }
        return ;
    }
    
    for(int i=1;i<=9;i++)
    {
        if(!st[i])
        {
            st[i]=true;
            backup[u]=i;
            dfs(u+1);
            backup[u]=0;
            st[i]=false;
        }
    }
}

int main()
{
    cin>>n;
    dfs(1);  //按照我正常的習慣，做dfs時陣列從第一個位置開始放      
    cout<<res<<endl;
    return 0;
}