任意一串字符串 字符串裡包含數字部分和一般的字符
例如 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的專欄”