/*
* 解法一：
* 构造一棵满二叉树，0为根节点，奇数节点表示某节点的左孩子，偶数节点为某节点的右孩子。
* 从数量最多的字符开始先填充右孩子，再填充左孩子，将字符使用完即可。
*
*/
typedef struct node_t {
int index;
int val;
}Node;
int cmp(const Node *a, const Node *b){
return a->val - b->val;
}
int get_len(char *s){
int i=0;
while(*s++ != '\0') i++;
return i;
}
void heap_right(char *s, int len, int index, Node *arr, int *arr_index){
if(index<0 || index>=len) return;
if(2*index+2 < len)
heap_right(s, len, 2*index+2, arr, arr_index);
if(index % 2 == 0){
while(!arr[(*arr_index)].val)
(*arr_index)--;
if(arr[(*arr_index)].val){
s[index] = arr[(*arr_index)].index;
arr[(*arr_index)].val--;
}
}
if(2*index+1 < len){
heap_right(s, len, 2*index+1, arr, arr_index);
}
}
void heap_left(char *s, int len, int index, Node *arr, int *arr_index){
if(index<0 || index>=len) return;
if(2*index+2 < len)
heap_left(s, len, 2*index+2, arr, arr_index);
if(index % 2 != 0){
while(!arr[(*arr_index)].val)
(*arr_index)--;
if(arr[(*arr_index)].val){
s[index] = arr[(*arr_index)].index;
arr[(*arr_index)].val--;
}
}
if(2*index+1 < len){
heap_left(s, len, 2*index+1, arr, arr_index);
}
}
char * reorganizeString(char * S){
Node arr[256];
int i, j;
int len = get_len(S);
int max = 0, max_index = 0;
printf("len = %d \n", get_len(S));
memset(arr, 0, sizeof(arr));
for(i=0; i<256; i++){
arr[i].index = i;
}
for(i=0; S[i]!= '\0'; i++){
arr[S[i]].val++;
}
qsort(arr, 256, sizeof(Node), cmp);
memset(S, 0, sizeof(char) * len);
int arr_index = 256-1;
/* 首先填充偶数节点，对应满二叉树的右节点 */
heap_right(S, len, 0, arr, &arr_index);
/* 再填充奇数数节点，对应满二叉树的右节点 */
heap_left(S, len, 0, arr, &arr_index);
S[len] = 0;
printf("%s\n", S);
/* check result */
for(i=0; i<len-1; i++){
if(S[i]==S[i+1]){
S[0] = 0;
return S;
}
}
//printf("len = %d \n", get_len(S));
return S;
}
/*
* 解法二：
* 从数量最多的字符开始先填充偶数位置，偶数位置填充完毕后，奇数位置用剩下的字符填充。
*
*/
typedef struct node_t {
int index;
int val;
}Node;
int cmp(const Node *a, const Node *b){
return a->val - b->val;
}
int get_len(char *s){
int i=0;
while(*s++ != '\0') i++;
return i;
}
char * reorganizeString(char * S){
Node arr[256];
int i, j;
int len = get_len(S);
int max = 0, max_index = 0;
printf("len = %d \n", get_len(S));
char *tmp = (char *)malloc(sizeof(char) * get_len(S));
memcpy(tmp, S, sizeof(char) * get_len(S));
memset(arr, 0, sizeof(arr));
for(i=0; i<256; i++){
arr[i].index = i;
}
for(i=0; S[i]!= '\0'; i++){
arr[S[i]].val++;
}
for(i=0; i<256; i++){
if(arr[i].val > max){
max = arr[i].val;
max_index = i;
break;
}
}
int cnt = 0;
for(i=0; i<256; i++){
if(i!=max_index){
cnt += arr[i].val;
}
}
int index = 0;
qsort(arr, 256, sizeof(Node), cmp);
memset(S, 0, sizeof(char) * len);
i=256-1;
j = 0;
for(;i>=0; i--){
if(!arr[i].val) continue;
while(arr[i].val){
S[j] = arr[i].index;
printf("ret[%d] = %c\n", j, arr[i].index);
arr[i].val--;
j += 2;
if(j>=len) break;
}
if(j>=len) break;
}
i=256-1 ;
j = 0;
for(;i>=0; i--){
if(!arr[i].val) continue;
while(arr[i].val){
if(S[j]){
j++;
continue;
}
printf("ret[%d] = %c\n", j, arr[i].index);
S[j] = arr[i].index;
arr[i].val--;
j += 1;
if(j>=len) break;
}
}
S[len] = '\0';
/* check result */
for(i=0; i<len-1; i++){
if(S[i]==S[i+1]){
S[0] = 0;
return S;
}
}
printf("len = %d \n", get_len(S));
return S;
}
