Riordina una stringa della metà del carattere

Question

Questa è una domanda di intervista.

Data una stringa come: 123456abcdef costituita da n/2 numeri interi seguiti da n/2 caratteri. Riordina la stringa da contenere come 1a2b3c4d5e6f. L'algoritmo dovrebbe essere sul posto.

La soluzione che ho dato era banale - O (n^2). Basta spostare i personaggi di n/2 posti a sinistra.

Ho provato a utilizzare la ricorsione come -
a. Swap dopo la metà del primo semestre con la metà precedente della 2a parte - es.
123 456 abc def
123 abc 456 def
b. Recurse su due metà.

Il pbm che ho bloccato è che lo scambio varia con il numero di elementi - per es.

Cosa fare dopo? 123 abc 12AB 3c

e cosa fare per: 12345 ABCDE 123abc 45ab

Questa è una domanda piuttosto vecchio e potrebbe essere un duplicato. Per favore fatemelo sapere .. :)

Un altro esempio: Ingresso: 38726zfgsa uscita: 3z8f7g2s6a

Answer 1

Ecco come vorrei affrontare il problema:

1) Divide the string into two partitions, number part and letter part 
2) Divide each of those partitions into two more (equal sized) 
3) Swap the second the third partition (inner number and inner letter) 
4) Recurse on the original two partitions (with their newly swapped bits) 
5) Stop when the partition has a size of 2 

Ad esempio:

123456abcdef -> 123456 abcdef -> 123 456 abc def -> 123 abc 456 def

123abc -> 123 abc -> 12 3 ab c -> 12 ab 3 c

12 ab -> 1 2 ab -> 1 a 2 b

... ecc

E lo stesso per l'altra metà della ricorsione ..

Tutto può essere fatto in posizione con l'unico trucchetto che scambia le partizioni che non hanno le stesse dimensioni (ma sarà fuori da una, quindi non è difficile da gestire).

Answer 2

In questi giorni, se ho chiesto a questa domanda, quello che sto cercando di scrivere sulla lavagna qualcuno prima è:

assertEquals("1a2b3c4d5e6f",funnySort("123456abcdef")); 
... 

e poi magari una domanda per ulteriori esempi.

(E poi, a seconda, se l'operazione è di interlacciare i numeri & lettere, penso che si possa fare con due puntatori, indexLetter e indexDigit, e farli avanzare attraverso lo swapping secondo necessità fino a raggiungere la fine.)

Answer 3

nella soluzione ricorsiva perché non basta fare un test se n/2% 2 == 0 (n% 4 == 0) e trattare il 2 situazioni in modo diverso

Come templatetypedef commentato la tua ricorsione non può essere sul posto.

Ma qui è una soluzione (non in posizione) utilizzando il modo in cui si voleva fare il vostro ricorsione:

def f(s): 
    n=len(s) 
    if n==2: #initialisation 
     return s 
    elif n%4 == 0 : #if n%4 == 0 it's easy 
     return f(s[:n/4]+s[n/2:3*n/4])+f(s[n/4:n/2]+s[3*n/4:]) 
    else: #otherwise, n-2 %4 == 0 
     return s[0]+s[n/2]+f(s[1:n/2]+s[n/2+1:]) 

Answer 4

Punteggio ogni cifra come valore numerico. Assegna un punteggio a ogni lettera come a = 1.5, b = 2.5 c = 3.5 ecc. Esegui un ordinamento di inserimento della stringa in base al punteggio di ciascun carattere.

[ETA] Il punteggio semplice non funziona, quindi utilizzare due puntatori e invertire il pezzo della stringa tra i due puntatori. Un puntatore inizia nella parte anteriore della stringa e avanza di un passo per ciclo. L'altro puntatore inizia nel mezzo della stringa e avanza ogni secondo ciclo.

123456abcdef 
^ ^

1a65432bcdef 
^^

1a23456bcdef 
^^

1a2b6543cdef 
    ^^ 

Answer 5

Eccoci. Ricorsivo, taglia a metà ogni volta e sul posto. Usa l'approccio delineato da @Chris Mennie. Ottenere la scissione giusta è stato complicato. Molto più lungo di Python, innit?

/* In-place, divide-and-conquer, recursive riffle-shuffle of strings; 
* even length only. No wide characters or Unicode; old school. */ 

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 

void testrif(const char *s); 
void riffle(char *s); 
void rif_recur(char *s, size_t len); 
void swap(char *s, size_t midpt, size_t len); 
void flip(char *s, size_t len); 
void if_odd_quit(const char *s); 

int main(void) 
{ 
    testrif(""); 
    testrif("a1"); 
    testrif("ab12"); 
    testrif("abc123"); 
    testrif("abcd1234"); 
    testrif("abcde12345"); 
    testrif("abcdef123456"); 

    return 0; 
} 

void testrif(const char *s) 
{ 
    char mutable[20]; 

    strcpy(mutable, s); 
    printf("'%s'\n", mutable); 
    riffle(mutable); 
    printf("'%s'\n\n", mutable); 
} 

void riffle(char *s) 
{ 
    if_odd_quit(s); 
    rif_recur(s, strlen(s)); 
} 

void rif_recur(char *s, size_t len) 
{ 
    /* Turn, e.g., "abcde12345" into "abc123de45", then recurse. */ 

    size_t pivot = len/2; 
    size_t half = (pivot + 1)/2; 
    size_t twice = half * 2; 

    if (len < 4) 
     return; 

    swap(s + half, pivot - half, pivot); 
    rif_recur(s, twice); 
    rif_recur(s + twice, len - twice); 
} 

void swap(char *s, size_t midpt, size_t len) 
{ 
    /* Swap s[0..midpt] with s[midpt..len], in place. Algorithm from 
    * Programming Pearls, Chapter 2. */ 

    flip(s, midpt); 
    flip(s + midpt, len - midpt); 
    flip(s, len); 
} 

void flip(char *s, size_t len) 
{ 
    /* Reverse order of characters in s, in place. */ 

    char *p, *q, tmp; 

    if (len < 2) 
     return; 

    for (p = s, q = s + len - 1; p < q; p++, q--) { 
     tmp = *p; 
     *p = *q; 
     *q = tmp; 
    } 
} 

void if_odd_quit(const char *s) 
{ 
    if (strlen(s) % 2) { 
     fputs("String length is odd; aborting.\n", stderr); 
     exit(1); 
    } 
} 

Answer 6

E 'facile da permutare una matrice in posizione da caccia di elementi circolari cicli se si dispone di un po-map per contrassegnare gli elementi che sono stati spostati. Non abbiamo una mappa dei bit separata, ma se i tuoi personaggi sono lettere (o almeno hanno il chiaro ordine alto), possiamo usare il bit più in alto di ciascun carattere per contrassegnarlo. Questo produce il seguente programma, che non è ricorsivo e quindi non usa lo stack space.

class XX 
{ 
    /** new position given old position */ 
    static int newFromOld(int x, int n) 
    { 
    if (x < n/2) 
    { 
     return x * 2; 
    } 
    return (x - n/2) * 2 + 1; 
    } 
    private static int HIGH_ORDER_BIT = 1 << 15; // 16-bit chars 
    public static void main(String[] s) 
    { 
    // input data - create an array so we can modify 
    // characters in place 
    char[] x = s[0].toCharArray(); 
    if ((x.length & 1) != 0) 
    { 
     System.err.println("Only works with even length strings"); 
     return; 
    } 
    // Character we have read but not yet written, if any 
    char holding = 0; 
    // where character in hand was read from 
    int holdingPos = 0; 
    // whether picked up a character in our hand 
    boolean isHolding = false; 
    int rpos = 0; 
    while (rpos < x.length) 
    { // Here => moved out everything up to rpos 
     // and put in place with top bit set to mark new occupant 
     if (!isHolding) 
     { // advance read pointer to read new character 
     char here = x[rpos]; 
     holdingPos = rpos++; 
     if ((here & HIGH_ORDER_BIT) != 0) 
     { 
     // already dealt with 
     continue; 
     } 
     int targetPos = newFromOld(holdingPos, x.length); 
     // pick up char at target position 
     holding = x[targetPos]; 
     // place new character, and mark as new 
     x[targetPos] = (char)(here | HIGH_ORDER_BIT); 
     // Now holding a character that needs to be put in its 
     // correct place 
     isHolding = true; 
     holdingPos = targetPos; 
     } 
     int targetPos = newFromOld(holdingPos, x.length); 
     char here = x[targetPos]; 
     if ((here & HIGH_ORDER_BIT) != 0) 
     { // back to where we picked up a character to hold 
     isHolding = false; 
     continue; 
     } 
     x[targetPos] = (char)(holding | HIGH_ORDER_BIT); 
     holding = here; 
     holdingPos = targetPos; 
    } 
    for (int i = 0; i < x.length; i++) 
    { 
     x[i] ^= HIGH_ORDER_BIT; 
    } 
    System.out.println("Result is " + new String(x)); 
    } 
} 

Answer 7

Confrontando 123456abcdef e 1a2b3c4d5e6f possiamo notare che solo il primo e l'ultimo carattere sono nella loro corretta posizione. Possiamo anche notare che per ogni restante n-2 caratteri possiamo calcolare la loro posizione corretta direttamente dalla loro posizione originale. Arriveranno lì e l'elemento che era lì sicuramente non era nella posizione corretta, quindi dovrà sostituirne un altro. Facendo n-2 tali passaggi tutti gli elementi si arriva a posizioni corrette:

void funny_sort(char* arr, int n){ 
    int pos = 1; // first unordered element 
    char aux = arr[pos]; 
    for (int iter = 0; iter < n-2; iter++) { // n-2 unordered elements 
     pos = (pos < n/2) ? pos*2 : (pos-n/2)*2+1;// correct pos for aux 
     swap(&aux, arr + pos); 
    } 
}