错误笔记

middle = (int)(((long)start + (long)end)/2); => long -> /2 -> int => good.
middle = (int)((long)start + (long)end)/2; => long-> int -> /2 => wrong, negitive

bool CheckPermutation(char* s1, char* s2){
    // check length, false if not equal in length

    int s1len = strlen(s1);
    int s2len = strlen(s2);

    if (s1len != s2len){
        return false;
    }

    // printf("string len: %d\n", s1len);

    // if length is equal, 
    // pick one element, search over another array
    // if not found return false;
    // if found, remove both from array; continue until no element left.

    char *s1cur = s1;

    while (*s1cur != '\0'){
        // printf("current s1 char %c\n", *s1cur);
        // if (*s1cur == (char)-1) {
        //     s1cur++;
        //     continue;
        // }
        // search s1cur in s2
        char *s2cur = s2;
        bool found = false;
        while (*s2cur != '\0'){
            // printf("compare with s2 char: %c\n", *s2cur);
            if (*s2cur == (char)-1) {
                s2cur ++;
                continue;
            }
            if (*s1cur == *s2cur){
                // printf("found s1 char: %c in s2\n", *s1cur);
                found = true;
                *s1cur = (char)-1;
                *s2cur = (char)-1;
                break;
            }
            s2cur ++;
        }
        if (!found) return false;
        s1cur ++;
    }
    return true;
}

char* replaceSpaces(char* S, int length){
    if (length == 0) return NULL;

    int spaceLength = strlen(S);
    // two pointers, one to the end of length, another to the end of S
    char *end = S + spaceLength;

    // put a '\0' at the end of new S
    // and skip this char
    *end = '\0';
    end --;

    // scan the S from the last char in S.

    char *lastChar = S + length - 1;
    int currentLength = 0;

    // start moving every char at lastChar and replace space char with %20
    while (lastChar >= S && end >= S){

        // printf("handling char %c, lastChar at %d, end pointing to %d\n", 
        //         *lastChar, (lastChar - S), (end - S));
        if (*lastChar != ' '){
            // if lastChar is non-space, just copy it to *end
            // printf("move to end\n");
            *end = *lastChar;
            lastChar --;
            end --;
        }else if (*lastChar == ' '){
            // if lastChar is space, add %20 to *end
            // printf("refill with %20\n");
            *end = '0'; end --;
            *end = '2'; end --;
            *end = '%'; end --;
            lastChar --;
        }
        currentLength ++;

    }

    while (currentLength < length){
        // printf("there is still space left, fill in with %20\n");
        if (end > S){
            *end = '0'; end --;
            *end = '2'; end --;
            *end = '%'; end --;
            currentLength ++;
        }else{
            printf("Error? reaching the beginning of S, but still need more space to insert?\n");
            return S;
        }
    }
    if (lastChar < S && end >= S){
        S = ++end;
    }

    return S;

}

// struct CacheNode;
struct CacheNode {
    struct CacheNode *prev;
    struct CacheNode *next;
    int key;
    int value;
    int freq;
};
typedef struct CacheNode CacheNode;

typedef struct {
    CacheNode *head;
    CacheNode *tail;// least frequently used at tail.
    int size;
    int capacity;
} LFUCache;

void printCache(LFUCache *obj){
    int size = obj->size;
    CacheNode *cur = obj->head->next;
    int i = 0;
    while (i<size){
        printf("[%d] freq: %d, key: %d, value: %d\n",
             i, cur->freq, cur->key, cur->value);
        i ++;
        cur = cur->next;
    }
}

LFUCache* lFUCacheCreate(int capacity) {

    // printf("creating cache with capacity %d ...", capacity);
    LFUCache *cache = (LFUCache *)calloc(1,sizeof(LFUCache));
    // keep head as a special node as a fence node.
    CacheNode *head = (CacheNode *)malloc((capacity+1)*sizeof(CacheNode));
    cache->head = &head[0];

    cache->tail = cache->head; // tail pointing to last element
    cache->size = 0;
    cache->capacity = capacity;
    if (capacity > 0){
        // initialize the links between nodes

        head[0].prev=&head[capacity];
        head[0].next = &head[1];
        for (int i = 1; i < capacity; i++){
            head[i].next = &head[i+1];
            head[i].prev = &head[i-1];
        }

        head[capacity].prev = &head[capacity-1];
        head[capacity].next = &head[0];

    }
    
    // printf("done.\n");
    return cache;
}

// update the list after cur->freq is updated.
void postUpdateFreq(LFUCache *obj, CacheNode *cur){
    if (obj->capacity == 0) return;
    // move cur forward if cur->freq is larger, until it reaches the head
    // find the insertion point
    CacheNode *insertAfter = cur->prev;
    while (insertAfter != obj->head && insertAfter->freq <= cur->freq){
        // the node freq is equal or lower, then move cur before it
        // - equal case: this will guarantte the newest one accessed is always near to head.
        insertAfter = insertAfter->prev;
    }
    // the pointer does not move, cur is already at best position
    if (insertAfter == cur->prev) return;

    // move cur to the position after `insertAfter`

    // remove cur from original position
    CacheNode *prev = cur->prev;
    CacheNode *next = cur->next;
    prev->next = next;
    next->prev = prev;

    // update tail pointer if cur is tail
    if (cur == obj->tail) obj->tail = prev;

    // insert cur after 'insertAfter'
    prev = insertAfter;
    next = insertAfter->next;

    cur->next = next;
    cur->prev = prev;

    next->prev = cur;
    prev->next = cur;

}

int lFUCacheGet(LFUCache* obj, int key) {
    CacheNode *cur = obj->head->next;
    int ret = -1;
    // printf("searching key: <%d> .... ", key);
    for (int i = 0; i < obj->size; i ++){
        if (cur->key == key){
            // found = true;
            cur->freq ++;
            postUpdateFreq(obj, cur);
            ret = cur->value;
            // printf(" value: <%d>\n", ret);
            // printCache(obj);
            return ret;
        }
        cur = cur->next;
    }
    // printf(" value not found\n");
    // printCache(obj);
    return ret;
}

// void removeNode(LFUCache *obj, CacheNode *toRemove){
//     CacheNode *next = toRemove->next;
//     CacheNode *prev = toRemove->prev;
//     next->prev = prev;
//     prev->next = next;
//     // put node after the tail
//     toRemove->next = obj->tail->next;
//     obj->tail->next = toRemove;

// }

void lFUCachePut(LFUCache* obj, int key, int value) {

    if(obj->capacity <= 0) return;

    // printf("putting key,value: %d, %d\n", key, value);
    // search for the key
    CacheNode *cur = obj->head->next;

    for (int i = 0; i < obj->size; i ++){
        if (cur->key == key){
            // printf("found key\n");
            cur->value = value;
            cur->freq ++;
            postUpdateFreq(obj, cur);
            return;
        }
        cur = cur->next;
    }
    // key does not exist, insert it
    //
    // if size is full, remove last one
    // remove is just moving the tail cursor
    if (obj->size == obj->capacity){
        // remove last node, move tail pointer one ahead
        CacheNode *lastN = obj->tail->prev;
        obj->tail = lastN;
        obj->size --;
    }

    // printf("inserting <key,value>: <%d, %d> with size/capacity: %d/%d\n",
    //       key, value, obj->size, obj->capacity);
    // if size is 0 <= size < capacity, update tail pointer and insert it as last one
    // 
    cur = obj->tail->next;
    cur->freq = 1;
    cur->key = key;
    cur->value = value;

    obj->tail = cur;
    obj->size ++;

    // printf("update freq for <key,value>: <%d, %d>\n", key, value);
    // printCache(obj);
    // update freq to reflect latest usage
    postUpdateFreq(obj, cur);
    
    // printf("done put <key,value>: <%d, %d>\n", key, value);
    // printCache(obj);
}

void lFUCacheFree(LFUCache* obj) {

    free(obj->head);
    free(obj);
}

/**
 * Your LFUCache struct will be instantiated and called as such:
 * LFUCache* obj = lFUCacheCreate(capacity);
 * int param_1 = lFUCacheGet(obj, key);
 
 * lFUCachePut(obj, key, value);
 
 * lFUCacheFree(obj);
*/

// cost[i] : dp[i][target] = max(dp[i-1][target], dp[i-1][target-cost[i]])
// i is the number of digits in the number. from 1 to target.
// target is the total cost target, from 1 to target.
// dp[i][target] means the max number (string) with i digits and target.

char ***dp;

// return true if s1 > s2
int isGreater(char *s1, char*s2){
    int isG = 0;
    // compare string length
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    if (len1 > len2 ) isG = 1;
    else if (len1 < len2) isG = 0;
    else { // len1 == len2
        // check if equal
        if (strcmp(s1,s2) == 0) isG = 0;
        // compare each digits
        // find the first different digits and test which is bigger.
        for (int i = 0; i<len1; i++){
            int comp = s1[i] - s2[i];
            if (comp == 0) continue;
            else if (comp > 0){
                isG = 1;
                break;
            }else if (comp < 0){
                isG = 0;
                break;
            }
        }

    }
    return isG;
}

int isEqual(char *s1, char *s2){
    return (strcmp(s1,s2) == 0);
}
// insert a new digit into dest string, form a larger number
// result `dest` string will have a sorted digits
char * insertDigit(char *dest, char* newdigit){

    // check if dest is 0, just replace 0
    if (strcmp(dest, "0") == 0){
        dest[0] = newdigit[0];
        return dest;
    }

    int len = strlen(dest);
    // append a \0 to dest
    dest[len + 1] = '\0';
    int i = len;
    for ( ; i > 0; i --){
        // if the digit is smaller than newdigit, move to least significant bit
        if (dest[i-1] - newdigit[0] < 0){
            dest[i] = dest[i-1];
        }else{
            // found the insertion point dest[i]
            // jump out
            break;
        }
    }
    dest[i] = newdigit[0];

    return dest;
}

char * largestNumber(int* cost, int costSize, int target){

    // compute the maxDigits
    int maxDigits = target;
    // find the smallest cost
    int smallestCost = target;

    for (int i = 0; i < costSize; i ++){
        if (cost[i] < smallestCost) smallestCost = cost[i];
    }
    
    maxDigits = target/smallestCost + 1;

    // initialize the dp[0...maxDigits]
    // the largest possible value is |9...999999| with length of target
    dp = (char ***) malloc (sizeof (char*) * (maxDigits+1));
    for (int i = 0; i < maxDigits+1; i ++){

        dp[i] = (char **) malloc(sizeof(char*) * (target + 1));
        for(int j = 0; j < target + 1; j ++){
            dp[i][j] = (char *) malloc(maxDigits + 1);
            strcpy(dp[i][j], "0");
        }
    }

    // when there is only one digits in the number
    // update dp[1].
    for(int ti = 1; ti <= target; ti ++){
        // scan the costs find if there is a cost that is exactly = ti
        for (int i = 0; i < costSize; i ++){
            if (ti == cost[i]){
                char dig[2];
                sprintf(dig, "%d", i+1);
                // printf("digit: %s\n", dig);
                // choose the larger one
                if (isGreater(dig, dp[1][ti])){
                    strcpy(dp[1][ti], dig);
                    // printf("dp[1][%d] initialized to %s\n", ti, dp[1][ti]);
                }
            }
        }
    }

    // update dp[2->maxDigits]
    // dp[i][target] = max (dp[i-1][target], insertSort(dp[i-1][target-any(cost)], any(cost)))
    for (int i = 2; i <= maxDigits; i++){
        // compute the maxNumber with i digits for each targets

        // int updated = 0;

        for (int t = target; t > 0; t--){

            // no digits added. the oldMax.
            char *oldMax = dp[i-1][t];

            // printf("i = %d; t = %d, to compute, oldMax:%s\n",i,t, oldMax);

            // try to add one more digits to dp[i-1][t-costs[d]]
            char newMax[target + 1];
            strcpy(newMax, oldMax); // initialize as oldMax
            //printf("newMax initialized to %s\n", newMax);
            for (int d = 0; d < costSize; d ++){

                // printf("start iter d = %d\n", d);

                // ignore the cost if target is smaller
                if (t < cost[d]) continue;
                char *lessTarget = dp[i-1][t-cost[d]]; // a number with less digits
                // printf("Less Target: %s, dp[%d][%d]\n",
                //      lessTarget, i-1, t-cost[d]);
                // if dp[i-1][t-cost[d]] is 0, then invalid choice
                if ((t-cost[d]) > 0 && 
                    strcmp(lessTarget, "0") == 0) {
                        // printf("ignore\n");
                        continue;
                }
                // printf("i = %d, t = %d; cost[%d] = %d, lessTarget=%s\n",
                    // i, t, d, cost[d], lessTarget);
                char digit[2];
                sprintf(digit, "%d", d + 1);

                char tempMax[target+1];
                strcpy(tempMax, lessTarget); // backup the string
                // insert digit into lessTarget, to get a bigger number.
                char *newNumber = insertDigit(tempMax, digit);
                if (isGreater(newNumber, newMax)){
                    // update the newMax if get a bigger newNumber
                    // printf("update new max: %s (i=%d, t=%d, d=%d)\n", newNumber, i, t, d);
                    strcpy(newMax, newNumber);
                    // updated ++;
                }

                // printf("done iter d = %d\n", d);
            }

            // printf("i = %d; t = %d, done compute: %s\n",i,t, newMax);

            strcpy(dp[i][t], newMax);
            // printf("i = %d; t = %d, done compute: %s\n",i,t, newMax);

        }

        // if (updated < 1) break;
    }

    char *strRet = dp[maxDigits][target];

    return strRet;
}

???