984. 不含 AAA 或 BBB 的字符串

相关标签：贪心算法



/*

递归 超时了 。。。。

剪枝 不对 ？ 所以递归没法写 
应该是on 的解法

想了一下啊 用递归简直不动脑子 


这个 只需要让 大的 走 2个 小的走1个 动态的往前走 


strcat
char * strcat ( char * destination, const char * source );


总结 ： 递归是 2 * N次方 
2**100 是很大的 
所以 即使递归肯定超时 ，即使剪纸也不行

因此 多半是 O（n）的解法
*/

// int recur(int A, int B, int cur, char *arr, int len)
// {
//     // printf("%d %d %d\n", A, B, cur);
//     if (cur == len) {
//         return 1;
//     }
//     if (A) {
//         if (cur > 1 && arr[cur - 1] == 'a' && arr[cur - 2] == 'a') {
            
//         } else {
//             arr[cur] = 'a';
//             // printf("A %d - %s\n", cur, arr);
//             if (recur(A - 1, B, cur + 1, arr, len) == 1) {
//                 return 1;
//             }
//             arr[cur] = '\0'; 
//         }
//     }
    
    
//     if (B) {
//         if (cur > 1 && arr[cur - 1] == 'b' && arr[cur - 2] == 'b') {
            
//         } else {
//             arr[cur] = 'b';
//             // printf("B %d - %s\n", cur, arr);
//             if (recur(A, B - 1, cur + 1, arr, len) == 1) {
//                 return 1;
//             } 
//             arr[cur] = '\0'; 
//         }
//     }
    
//     return 0;
// }


char * strWithout3a3b(int A, int B){

    char *res = (char *)malloc(sizeof(char) * (A + B + 1));
    memset(res, '\0', (A + B + 1));
    int cur = 0;
    while(A || B) {
        
        if (A > B) {
            if (cur > 1 && res[cur - 1] == 'a' && res[cur-2] == 'a') // aa
            {
                strcat(res, "b"); // 不能写‘a’ 要写”a“
                B--;
            } else {
                strcat(res, "a");
                A--;
            }
            
        } else {
            
            if (cur > 1 && res[cur - 1] == 'b' && res[cur-2] == 'b') // bb
            {
                strcat(res, "a");
                A--;
            } else {
                strcat(res, "b");
                B--;
            }
        }
        cur++;
        // printf("%s\n", res);

    }
       

    return res;
}

134. 加油站

相关标签：贪心算法

/*  

可以照着 每个点 都试一下 

差不对是 N2 的复杂度  居然过了。。。。。

看评论 是个 ON的解法 
我的办法显然不对 。。。。

*/

int recur(int cur, int target, int* gas, int* cost, int curgas, int size) {
    
    if (cur == target) {
        return 1;
    }
    //1. add gas
    curgas += gas[cur];
    //2 run
    if (cost[cur] > curgas) {
        return -1;
    } else {
        return recur( (cur + 1) % size, target, gas, cost, curgas - cost[cur], size);
    }

}

int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize){
    int curgas = 0;
    for (int start = 0; start < gasSize; start++) {
        curgas = gas[start];
        if (curgas >= cost[start]) {
            if (recur( (start + 1) % gasSize, start, gas, cost, curgas - cost[start], gasSize) == 1) {
                return start;
            }
        }

    }
    return -1;
}