头尾遍历思想（待续）

作者: AwesomeAshe | 来源:发表于2016-03-08 08:43 被阅读73次

头尾遍历思想（待续）
C++遍历算法
61.旋转链表（leetcode）
图
图的深度优先遍历和马踏棋盘算法
二叉树的遍历
SelectionSort
二叉树
C++第16天：第189-第214课字符串容器，栈，队列，d
2018-08-28

case1：字符串：判断一个字符串是不是对称的
case2: 数组：调整数组元素位置使奇数位于偶数前面
case3: 字符串：翻转字符串
我之前一直不知道而现在觉得很巧妙的一个方法就是，定义两个指针pHead,pEnd，从头和尾向中间移动遍历。

case1，判断字符串是否对称，goog就是对称的

bool isSymmetical(char* pbegin, char* pend)
{
    //first check valid
    if (pbegin == NULL || pend == NULL || pbegin>pend)
        return false;

    while (pbegin<pend)
    {
        if (*pbegin == *pend)
        {
            pbegin++;
            pend++;
        }
        else
            return false;
    }
    //if not return yet, return 1
    return true;
}

case2：使奇数元素位于偶数元素前面
一种想法是新建两个临时数组用于存放奇数和偶数，但是这样会浪费额外的空间并且计算量大，我们可以从两头向中间遍历，遇到偶数和奇数则交换其位置

bool isEven(int n)
{
    return (n & 1)==0;
}

void swap(int* beg, int* end)
{
    int tmp = *beg;
    *beg = *end;
    *end = tmp;
}
//odd-even
void reorderArray(int* arr,int len)
{
    if (!arr || len == 0)
        return;
    int* beg = arr;
    int* end = arr + len - 1;

    while (beg < end)
    {
        while (!isEven(*beg))
            beg++;
        while (isEven(*end))
            end--;
        swap(beg, end);
    }
}

case3：
给定一个字符串如abcde，要求将钱n个元素移动到后面，比如n=2时为cdeab
要求复杂度为O(n)，辅助内存为1
如果不考虑时间和空间复杂度的限制，最简单的方法莫过于把这道题看成是把字符串分成前后两部分，通过旋转操作把这两个部分交换位置。于是我们可以新开辟一块长度为n+1的辅助空间，把原字符串后半部分拷贝到新空间的前半部分，在把原字符串的前半部分拷贝到新空间的后半部分。不难看出，这种思路的时间复杂度是O(n)，需要的辅助空间也是O(n)
首先对 X和 Y 两段分别进行翻转操作，这样就能得到XTYT。接着再对 XTYT进行翻转操作，得到(XTYT)T=(YT)T(XT)T=YX。

char* LeftRotateString(char* pStr, unsigned int n)
{
  if(pStr != NULL)
{
int nLength = static_cast<int>(strlen(pStr));
if(nLength > 0 && n > 0 && n < nLength)
{
char* pFirstStart = pStr;
char* pFirstEnd = pStr + n - 1;
char* pSecondStart = pStr + n;
char* pSecondEnd = pStr + nLength - 1;
// reverse the first part of the string
ReverseString(pFirstStart, pFirstEnd);
// reverse the second part of the string
ReverseString(pSecondStart, pSecondEnd);// reverse the whole string
ReverseString(pFirstStart, pSecondEnd);}
}
return pStr;}
// Reverse the string between pStart and pEnd
void ReverseString(char* pStart, char* pEnd)
{
if(pStart != NULL && pEnd != NULL)
{
while(pStart <= pEnd)
{
char temp = *pStart;
*pStart = *pEnd;
*pEnd = temp;
pStart ++;
pEnd --;}
}
}