微软面试100题(88,54):字符\'*\'移到串的前部分/移动奇数到数组前部分并保持顺序

88题目：函数将字符串中的字符'*'移到串的前部分，前面的非'*'字符后移，但不能改变非'*'字符的先后顺序，函数返回串中字符'*'的数量。如原始串为：ab**cd**e*12，处理后为*****abcde12，函数并返回值为5。（要求使用尽量少的时间和辅助空间）

54题目：输入一个整数数组，调整数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。要求时间复杂度为O(n)。

54扩展：要求移动之后，奇数部分和偶数部分每个数的相对位置不变。比如1,2,3,4移动完之后必须是1,3,2,4

这3个题目有类似，所以放在一起。

88.

a.用一个指针p逆序读取串，读到*时，记录位置w (例子中是倒数第三个字符）

b.然后继续往前读,读到最近的一个字符，记录位置c（例子中是最后一个e)

c.交换w,c的内容。

d.这时，显然w以及w之后的部分已经完成了，指针移到w-1处，跳转到a步骤。

54.

这个题目没有什么难度，类似快排，从头开始读，读到一个偶数的时候记录，从尾开始读，读到奇数记录，然后交换两个内容，继续向中间读，直到结束。

54扩展

这个比54难了一些，虽然不是很复杂，但是还是需要思考一下的。

采用了类似冒泡的算法。

a.取一个指针odd,指向数组头部,同时头部记录为head。odd往后读，如果是奇数,停下。

b.这时，需要把这个奇数单步往前挪，挪到head位置。

c.完成后，head处的值就是奇数了,也就是head和head之前的部分，完成了排序。

d.odd指向head后一位，同时，把head也后移一位。跳转到a步骤。

f.当a步骤读不到奇数时，循环结束。

三个题目代码如下

54题代码

#include <stdlib.h>

#include <stdio.h>

/*
 * ===  FUNCTION  ======================================================================
 *         Name:  main
 *  Description:
 * =====================================================================================
 */
    int
main ( int argc, char *argv[] )
{
    int input[] = {1,2,3,4,6,9,10};
    int *head = input;
    int *tail = input + sizeof(input)/sizeof(int);
    while(1){
        while(*head % 2 == 1) head++;
        while(*tail % 2 == 0) tail--;
        if(head>tail) break;
        *head ^= *tail;
        *tail ^= *head;
        *head ^= *tail;
    }
    int i = 0;
    for(;i<sizeof(input)/sizeof(int);i++){
        printf ( "%d ", input[i] );
    }

    return EXIT_SUCCESS;
}                /* ----------  end of function main  ---------- */

88和54扩展代码

/*
 * =====================================================================================
 *
 * Filename: movewildchar.c
 *
 * Description:
 *
 * Version: 1.0
 * Created: 10/09/2012 05:21:06 PM
 * Revision: none
 * Compiler: gcc
 *
 * Author: YOUR NAME (),
 * Organization:
 *
 * =====================================================================================
 */
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <unistd.h>

int movewildchar(char* input){
    char* wild, *letter, *ptr;
    ptr = input + strlen(input)-1;
    int count = 0;
    do{
        while(*ptr != '*' &&ptr!=input){
            ptr--;
        }
        wild = ptr;
        while(*ptr =='*'&&ptr!=input){
            ptr--;
        }
        letter = ptr;
        if(*wild != *input){
            *wild ^= *letter;
            *letter ^= *wild;
            *wild ^= *letter;
            count++;
            ptr = wild;
        }
    }while( * '*');
    return count;
}

void sortoddorder(int *nums, int size){
    int *odd = nums;
    int *head = nums;
    while(1){
        while((*odd & 1) == 0 && odd<nums+size){
            odd++;
        }
        if(odd-nums+1 > size) return;
        printf ( "now tracking %d\n", *odd );
        while( head){
            int *t = odd-1;
            *odd^=*t;
            *t^=*odd;
            *odd^=*t;
            odd--;
        }
        odd++;
        head = odd;
    }
}

/*
 * === FUNCTION ======================================================================
 * Name: main
 * Description:
 * =====================================================================================
 (n)。
 */
    int
main ( int argc, char *argv[] )
{
    char input[] = {"ab**cd**12"};
    int count = movewildchar(input);
    printf ( "count = %d %s\n", count, input );
    int nums[] = {1,2,3,4,5,5,5};
    sortodd(nums, sizeof(nums)/4);
    int i = 0;
    for(;i<sizeof(nums)/4;i++){
        printf ( "%d \n", nums[i] );
    }
    return EXIT_SUCCESS;
}                /* ---------- end of function main ---------- */