幾道算法題

任意一串字符串 字符串裡包含數字部分和一般的字符

例如 ad2ef35adx1wewe76
注意這個字符串 裡面有4個數字 分別是 1 2 35 76 不考慮大數

將數字按照從小到大排序 組成一個新的字符串

要求制作一個函數來進行處理

假設是 fun(char*src,char*des)
  {
  }

src 輸入字符串 ad2ef35adx1wewe76

des 輸出字符串 1-2-35-76

view plaincopy to clipboardprint?void Convert(const char *str) 
{ 
    int res = 0; 
    vector<int> vec; 
    while (*str != '\0') 
    { 
        if (isdigit(*str)) 
        { 
            while (isdigit(*str)) 
            { 
                res = res * 10 + (*str - '0'); 
                str++; 
            } 
 
            vec.push_back(res); 
        } 
        else 
        { 
            res = 0; 
            str++; 
        } 
    } 
 
    sort(vec.begin(), vec.end()); 
 
    copy(vec.begin(), vec.end(), ostream_iterator<int>(cout, "-")); 
    cout<<endl; 
} 
void Convert(const char *str)
{
 int res = 0;
 vector<int> vec;
 while (*str != '\0')
 {
  if (isdigit(*str))
  {
   while (isdigit(*str))
   {
    res = res * 10 + (*str - '0');
    str++;
   }

   vec.push_back(res);
  }
  else
  {
   res = 0;
   str++;
  }
 }

 sort(vec.begin(), vec.end());

 copy(vec.begin(), vec.end(), ostream_iterator<int>(cout, "-"));
 cout<<endl;
}

一個整數數組，數組中元素按照大小先增後減，設計算法，給定元素求其在數組中的位置索引。

view plaincopy to clipboardprint?#include "stdafx.h"  
#include <iostream>  
#include <vector>  
#include <iterator>  
#include <algorithm>  
using namespace std; 
 
//利用二分查找的思想，來獲得最大元素的索引  
int FindMax(int arr[], int n) 
{ 
    int low = 0;  
    int high = n - 1; 
    int mid = 0; 
    while (low + 2 <= high) 
    { 
        mid = (low + high) / 2; 
 
        if (arr[mid] > arr[mid-1] && (arr[mid] > arr[mid+1])) //the max element  
            return mid; 
        else if (arr[mid] > arr[mid-1] && (arr[mid+1] > arr[mid])) //遞增部分  
            low = mid; 
        else 
            high = mid; 
    } 
} 
 
//遞增部分的二分查找  
int BinSearchLeft(int arr[], int begin, int end, int target) 
{ 
    int low = begin; 
    int high = end - 1; 
    int mid = 0; 
 
    while (low <= high) 
    { 
        mid = (low + high) / 2; 
 
        if (arr[mid] == target) 
            return mid; 
        else if (arr[mid] < target) 
            low = mid + 1; 
        else 
            high = mid - 1; 
    } 
    return -1; 
} 
//遞減部分的二分查找  
int BinSearchRight(int arr[], int begin, int end, int target) 
{ 
    int low = begin; 
    int high = end - 1; 
    int mid = 0; 
 
    while (low <= high) 
    { 
        mid = (low + high) / 2; 
 
        if (arr[mid] == target) 
            return mid; 
        else if (arr[mid] > target) 
            low = mid + 1; 
        else 
            high = mid - 1; 
    } 
    return -1; 
} 
//算法思想：先找到最大元素的索引，然後對左右兩個部分進行二分查找  
int FindTargetIndex(int arr[], int n, int target) 
{ 
    int maxIndex = FindMax(arr, n); 
     
    if (arr[maxIndex] == target) 
        return maxIndex; 
 
    int res = 0; 
    if ((res = BinSearchLeft(arr, 0, maxIndex, target)) != -1) 
        return res; 
 
    if ((res = BinSearchRight(arr, maxIndex + 1, n, target)) != -1) 
        return res; 
 
    return -1; 
} 
int main() 
{ 
    int arr[] = {2, 3, 4, 5, 10, 7, 6, 1}; 
    int size = sizeof(arr) / sizeof(int); 
 
    int maxIndex = FindMax(arr, size); 
    if (-1 != maxIndex) 
        cout<<"the max element's index is "<<maxIndex<<", the max elemet is "<<arr[maxIndex]<<endl; 
 
    int res = FindTargetIndex(arr, size, 3); 
    if (-1 != res) 
        cout<<"the target's position is "<<res<<endl; 
    else 
        cout<<"can not find this target!"<<endl; 
 
    return 0; 
} 
#include "stdafx.h"
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
using namespace std;

//利用二分查找的思想，來獲得最大元素的索引
int FindMax(int arr[], int n)
{
 int low = 0;
 int high = n - 1;
 int mid = 0;
 while (low + 2 <= high)
 {
  mid = (low + high) / 2;

  if (arr[mid] > arr[mid-1] && (arr[mid] > arr[mid+1])) //the max element
   return mid;
  else if (arr[mid] > arr[mid-1] && (arr[mid+1] > arr[mid])) //遞增部分
   low = mid;
  else
   high = mid;
 }
}

//遞增部分的二分查找
int BinSearchLeft(int arr[], int begin, int end, int target)
{
 int low = begin;
 int high = end - 1;
 int mid = 0;

 while (low <= high)
 {
  mid = (low + high) / 2;

  if (arr[mid] == target)
   return mid;
  else if (arr[mid] < target)
   low = mid + 1;
  else
   high = mid - 1;
 }
 return -1;
}
//遞減部分的二分查找
int BinSearchRight(int arr[], int begin, int end, int target)
{
 int low = begin;
 int high = end - 1;
 int mid = 0;

 while (low <= high)
 {
  mid = (low + high) / 2;

  if (arr[mid] == target)
   return mid;
  else if (arr[mid] > target)
   low = mid + 1;
  else
   high = mid - 1;
 }
 return -1;
}
//算法思想：先找到最大元素的索引，然後對左右兩個部分進行二分查找
int FindTargetIndex(int arr[], int n, int target)
{
 int maxIndex = FindMax(arr, n);
 
 if (arr[maxIndex] == target)
  return maxIndex;

 int res = 0;
 if ((res = BinSearchLeft(arr, 0, maxIndex, target)) != -1)
  return res;

 if ((res = BinSearchRight(arr, maxIndex + 1, n, target)) != -1)
  return res;

 return -1;
}
int main()
{
 int arr[] = {2, 3, 4, 5, 10, 7, 6, 1};
 int size = sizeof(arr) / sizeof(int);

 int maxIndex = FindMax(arr, size);
 if (-1 != maxIndex)
  cout<<"the max element's index is "<<maxIndex<<", the max elemet is "<<arr[maxIndex]<<endl;

 int res = FindTargetIndex(arr, size, 3);
 if (-1 != res)
  cout<<"the target's position is "<<res<<endl;
 else
  cout<<"can not find this target!"<<endl;

 return 0;
}

 作者“wangyangkobe的專欄”