标签：return struct int graph 练习 ++ 算法 cur

参考
labuladong 微信公众号

心得

计算机思维的理解

人总对有规律的数据处理更得心应手，同样计算机对有规律的数据处理也更加方便(计算机语言毕竟是人写的嘛)。为了处理不同的问题的数据，我们可以通过不同的数据结构来构建，然后通过与之对应的特殊算法来处理，从而高效解决问题。
计算机算法的本质是穷举，对应的操作无非就是访问加修改。

学算法的个人认为有如下三个问题

熟悉理解框架思维，学习计算机对不同数据结构的穷举方式
如何将问题转化，很多问题并不能直接就想出，这也是最难的一步
如何写出相应思路的代码

解题思路总结

任何有变化的东西都可以抽象成图，一个变化就是一个岔路
有序号有数据的本质是一个哈希，数组本身是一个哈希。
做动态规划要有树的概念，最优子结构实质就是递归树的子节点，状态转移就是产生一个岔路的条件
数组问题优先考虑排序是否能解决
数组本身就是最简单的哈希表，有些问题可以考虑能不能转化成哈希
树的遍历本质是将一个多叉型数据结构变成链式数据结构的访问
前序，中序，后序遍历分别对应某个节点操作的时间点，前序是刚进入节点，中序是某一边分支执行完，后序遍历是子分支都执行完后离开当前节点
中序遍历对于搜索二叉树很适合，遍历的顺序是一个有序数组
是否可以通过遍历一遍二叉树得到答案
是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案
无论使用哪一种思维模式，你都要明白二叉树的每一个节点需要做什么，需要在什么时候（前中后序）做
递归的时候，入参可以加上父亲节点，这样可以在子节点判断的时候查看父亲节点的情况
对于查找类的树的问题，基本都可以通过遍历一遍，然后记录相应的节点方式解决
回溯算法就是多叉树的遍历问题
明确【状态】 -> 定义dp数组含义 -> 明确【选择】 -> 明确【base case】
入栈不但可以入相应的数据还可以入相应数据的序号

基础

#include <stddef.h>
#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>

int sprintf(char *str, const char *format, ...);
int sscanf(const char *str, const char *format, ...);
void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*));
int atoi(const char *str);
int isalnum( int ch ); /* 数字或字母字符 */
int isalpha( int ch ); /* 字母字符 */
int islower( int ch ); /* 小写字母 */
int isupper( int ch ); /* 大写字母 */
int isdigit( int ch ); /* 数字 */
int isxdigit( int ch ); /* 16进制数字 */
double sqrt(double x); /* 平方根 */
double pow(double x, double y); /* 返回 x 的 y 次幂 */
char *strcat(char *dest, const char *src); /* 把 src 所指向的字符串追加到 dest 所指向的字符串的结尾 */
char *strstr(const char *haystack, const char *needle); /* 在字符串 haystack 中查找第一次出现字符串 needle（不包含空结束字符）的位置 */

scanf()的一些用法
"%ns" n为整数,读入的字符串最长不超过n,然后在末尾补'\0'
"%nf" 读入的浮点数最多有n位整数,位数多于n,会截断。
"%n[a-z]" 读入最多n个字符,如果遇到非a-z的字符,停止
"%[^=]" 读入任意多的字符,直到遇到"="停止
"%n[^=]" 读入"="号前的至多n 个字符
"*" 表示该输入项读入后不赋予任何变量，即跳过该输入值。
比如%[0-9]表示只读入'0'到'9'之间的字符，%[a-zA-Z]表示只读入字母，
'-'是范围连接符，也可以直接列出你需要读入的字符。

返回值
如果成功，该函数返回成功匹配和赋值的个数。如果到达文件末尾或发生读错误，则返回 EOF。

排序

冒泡排序

void BubbleSort(int* arr, int left, int right)
    for (int i = 0; i < arrLen; i++) {
        for (int j = i + 1; j < arrLen; j++) {
            if (arr[i] > arr[j]) {
                int tmp = arr[j];
                arr[j] = arr[i];
                arr[i] = tmp;
            }
        }
    }
}

快速排序

int partition(int* arr, int left, int right)
{
    int v = arr[right];
    while (left < right) {
        while (left < right && arr[left] < v) {
            left++;
        }
        if (left < right) {
            arr[right--] = arr[left];
        }
        while (left < right && arr[right] > v) {
            right--;
        }
        if (left < right) {
            arr[left++] = arr[right];
        }
    }
    arr[left] = v;

    return left;
}
void quickSort(int* arr, int left, int right)
{
    int pivot = partition(arr, left, right);
    if (left < pivot - 1) {
        quickSort(arr, left, pivot - 1);
    }
    if (pivot + 1 < right) {
        quickSort(arr, pivot + 1, right);
    }
}

堆排序

void heapify(int *arr, int i, int len)
{
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    int large = i;

    if (left < len && arr[left] > arr[large]) {
        large = left;
    }
    if (right < len && arr[right] > arr[large]) {
        large = right;
    }
    if (large != i) {
        int tmp = arr[large];
        arr[large] = arr[i];
        arr[i] = tmp;
        // 交换后子节点递归调整
        heapify(arr, large, len);
    }  
}
void buildMaxHeap(int *arr, int len)
{
    for (int i = (len / 2) - 1; i >= 0; i--) {
        heapify(arr, i, len);
    }
}
void heapSort(int *arr, int len)
{
    buildMaxHeap(arr, len);
    for (int i = len - 1; i > 0; i--) {
        int tmp = arr[0];
        arr[0] = arr[i];
        arr[i] = tmp;
        len--;
        heapify(arr, 0, len);
    }
}

数组

前缀和

用于解决一些连续子数组的问题

和为K的子数组

int subarraySum(int* nums, int numsSize, int k){
    int preSum[numsSize + 1];

    preSum[0] = 0;
    for (int i = 0; i < numsSize; i++) {
        preSum[i + 1] = preSum[i] + nums[i];
    }

    int cnt = 0;
    for (int i = 0; i <= numsSize; i++) {
        for (int j = 0; j < i; j++) {
            if (preSum[i] - preSum[j] == k) {
                cnt++;
            }
        }
    }

    return cnt;
}

差分数组

用于对原始数组频繁增减的情况

航班预订统计

int* corpFlightBookings(int** bookings, int bookingsSize, int* bookingsColSize, int n, int* returnSize){
    int diff[n];
    memset(diff, 0, n * sizeof(int));

    for (int i = 0; i < bookingsSize; i++) {
        diff[bookings[i][0] - 1] += bookings[i][2];
        if (bookings[i][1] < n) {
            diff[bookings[i][1]] -= bookings[i][2];
        }
    }

    int *res = malloc(n * sizeof(int));
    *returnSize = n;
    res[0] = diff[0];
    for (int i = 1; i < n; i++) {
        res[i] = res[i - 1] + diff[i];
    }

    return res;
}

字符串

KMP字符串比对算法

栈

单调栈

入栈有时候可以入数据，有时候也可以入数据的序号

对于环形数组，可以将数组长度翻倍，构造两倍长度的原数组

每日温度

int* dailyTemperatures(int* temperatures, int temperaturesSize, int* returnSize){
    int *answer = malloc(temperaturesSize * sizeof(int));
    *returnSize = temperaturesSize;
    int stack[temperaturesSize];
    int stackLen = 0;
    for (int i = temperaturesSize - 1; i >= 0; i--) {
        int end = stackLen;
        while (end > 0 && temperatures[stack[end - 1]] <= temperatures[i]) {
            end--;
        }
        answer[i] = (end == 0) ? 0 : (stack[end - 1] - i);
        stackLen = end;
        stack[stackLen++] = i;
    }

    return answer;
}

队列

单调队列

滑动窗口最大值

int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize){
    int queue[numsSize + numsSize];
    int queueStart = 0, queueEnd = 0;
    int *res = malloc(numsSize * sizeof(int));
    *returnSize = 0;

    for (int i = 0; i < numsSize; i++) {
        if (i < k - 1) {
            while (queueStart != queueEnd && queue[queueEnd - 1] < nums[i]) {
                queueEnd--;
            }
            queue[queueEnd++] = nums[i];
        } else {
            while (queueStart != queueEnd && queue[queueEnd - 1] < nums[i]) {
                queueEnd--;
            }
            queue[queueEnd++] = nums[i];
            res[*returnSize] = queue[queueStart];
            (*returnSize) += 1;
            if (nums[i - k + 1] == queue[queueStart]) {
                queueStart++;
            }
        }
    }

    return res;
}

优先队列

双指针

左右指针

三数之和

int cmp(void *a, void *b)
{
    return (*(int *)a - *(int *)b);
}
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){

    int **out = malloc(20000 * sizeof(int *));
    *returnColumnSizes = malloc(20000 * sizeof(int));
    for (int i = 0; i < 20000; i++) {
        out[i] = malloc(3 * sizeof(int));
        (*returnColumnSizes)[i] = 3;
    }
    *returnSize = 0;
    qsort(nums, numsSize, sizeof(int), cmp);
#if 0
    for (int i = 0; i < numsSize; i++) {
        printf("%d ", nums[i]);
    }
    printf("\n");
#endif
    for (int i = 0; i <= numsSize - 3; i++) {
        int left = i + 1;
        int right = numsSize - 1;
        int sum = 0 - nums[i];
        if (i > 0 && nums[i - 1] == nums[i]) {
            continue;
        }
        while (left < right) {
            if (nums[left] + nums[right] == sum) {
                out[*returnSize][0] = nums[i];
                out[*returnSize][1] = nums[left];
                out[*returnSize][2] = nums[right];
                (*returnSize) += 1;
                left++;
                right--;
                while(left < right && nums[left - 1] == nums[left]) {
                    left++;
                }
                while(left < right && nums[right + 1] == nums[right]) {
                    right--;
                }
            }
            if (nums[left] + nums[right] > sum) {
                right--;
            }
            if (nums[left] + nums[right] < sum) {
                left++;
            }
        }
    }

    return out;
}

滑动窗口

最小子串

char * minWindow(char * s, char * t){

    int sLen = strlen(s);
    int tLen = strlen(t);
    int need[256] = {0};
    int window[256] = {0};
    int needCnt = 0;
    int windowCnt = 0;

    for (int i = 0; i < tLen; i++) {
        if (need[t[i]] == 0) {
            needCnt++;
        }
        need[t[i]]++;   
    }
    
    int left = 0, right = 0;
    int minLen = sLen;
    int pos = -1;
    while (right < sLen) {
        /* 扩大窗口 */
        if (need[s[right]] != 0) {
            window[s[right]]++;
            if (window[s[right]] == need[s[right]]) {
                windowCnt++;
            }
        }
        right++;
        //printf("windowCnt=%d,needCnt=%d\n", windowCnt, needCnt);
        /* 缩小窗口 */
        while (windowCnt == needCnt) {
            if ((right - left) <= minLen) {
                minLen = right - left;
                pos = left;
            }
            if (need[s[left]] != 0) {
                window[s[left]]--;
                if (window[s[left]] < need[s[left]]) {
                    windowCnt--;
                }
            }
            left++;
        }
    }
    
    if (pos != -1) {
        char *out = malloc((minLen + 1) * sizeof(char));
        memcpy(out, &s[pos], minLen);
        out[minLen] = '\0';
        return out;
    }
    return "";
}

哈希

原地哈希

DFS

全排列

void dfs(int* nums, int numsSize, int* returnSize, int* returnColumnSizes, int *visted, int *tmp, int **out, int h)
{
    if (h == numsSize) {
        memcpy(out[*returnSize], tmp, numsSize * sizeof(int));
        returnColumnSizes[*returnSize] = numsSize;
        (*returnSize) += 1;
        return;
    }
    for (int i = 0; i < numsSize; i++) {
        if (visted[i] == 1) {
            continue;
        }
        
        if (i >= 1 && nums[i - 1] == nums[i] && visted[i - 1] == 0) {
            continue;
        }
        
        visted[i] = 1;
        tmp[h] = nums[i];
        dfs(nums, numsSize, returnSize, returnColumnSizes, visted, tmp, out, h + 1);
        visted[i] = 0;
    }
}
int cmp(void *a, void *b)
{
    return ((*(int *)a) - (*(int *)b));
}
int** permuteUnique(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){

    int tmp[numsSize];
    int visted[numsSize];
    for (int i = 0; i < numsSize; i++) {
        visted[i] = 0;
    }

    qsort(nums, numsSize, sizeof(int), cmp);
    for (int i = 0; i < numsSize; i++) {
        printf("%d ", nums[i]);
    }
    printf("\n");

    int **out = malloc(1000 * sizeof(int *));
    *returnColumnSizes = malloc(1000 * sizeof(int));
    *returnSize = 0;
    for (int i = 0; i < 1000; i++) {
        out[i] = malloc(numsSize * sizeof(int));
    }
    dfs(nums, numsSize, returnSize, *returnColumnSizes, visted, tmp, out, 0);

    return out;
}

数独

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

bool IsValid(int *buf, int x, int y)
{
    int cur = *(buf + x * 9 + y);
    
    for (int i = 0; i < 9; i++) {
        if (i == y) {
            continue;
        }
        if (cur == *(buf + x * 9 + i)) {
            return false;
        }
    }
    for (int i = 0; i < 9; i++) {
        if (i == x) {
            continue;
        }
        if (cur == *(buf + i * 9 + y)) {
            return false;
        }
    }
    for (int i = 3 * (x / 3); i < (3 * (x / 3)) + 3; i++) {
        for (int j = 3 * (y / 3); j < (3 * (y / 3)) + 3; j++) {
            if (i == x && j == y) {
                continue;
            }
            if (cur == *(buf + i * 9 + j)) {
                return false;
            }
        }
    }
    
    return true;
}

bool SudoKu(int *buf, int x, int y)
{
    if (x == 9 && y == 0) {
        return true;
    }
    
    int *p = (buf + x * 9 + y);
    int nextX = x, nextY = y + 1;
    if (nextY >= 9) {
        nextX += 1;
        nextY = 0;
    }
    if (*p == 0) {
        for (int cur = 1; cur <= 9; cur++) {
            *p = cur;
            if (IsValid(buf, x, y)) {
                if (SudoKu(buf, nextX, nextY)) {
                    return true;
                }
            }
            *p = 0;
        }
    } else {
        if (SudoKu(buf, nextX, nextY)) {
            return true;
        }
    }
    
    return false;
}
int main(void)
{
    int ret;
    int buf[9][9];
    for (int i = 0; i < 9; i++) {
             
    }
    for (int x = 0; x < 9; x++) {
        for (int y = 0; y < 9; y++) {
            scanf("%d", &buf[x][y]);
        }
    }
    
    SudoKu(buf, 0, 0);
    
    for (int x = 0; x < 9; x++) {
        for (int y = 0; y < 9; y++) {
            printf("%d ", buf[x][y]);
        }
        printf("\n");
    }
    
    return 0;
}

N皇后

bool isValid(char** board, int x, int y, int n)
{
    for (int i = 0; i < n; i++) {
        if (i != x && board[i][y] == board[x][y]) {
            return false;
        }
    }
    for (int i = 0; i < n; i++) {
        if (i != y && board[x][i] == board[x][y]) {
            return false;
        }
    }

    for (int i = x - 1, j = y - 1; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] == board[x][y]) {
            return false;
        }
    }
    for (int i = x + 1, j = y - 1; i < n && j >= 0; i++, j--) {
        if (board[i][j] == board[x][y]) {
            return false;
        }
    }
    for (int i = x - 1, j = y + 1; i >= 0 && j < n; i--, j++) {
        if (board[i][j] == board[x][y]) {
            return false;
        }
    }
    for (int i = x + 1, j = y + 1; i < n && j < n; i++, j++) {
        if (board[i][j] == board[x][y]) {
            return false;
        }
    }

    return true;
}
bool dfs(char** board, int x, int y, int n, int h, int *cnt)
{
    if (h >= n) {
        if (x == n) {
            (*cnt) += 1;
            return true;
        }
        return false;
    }
    if (x >= n) {
        return false;
    }

    int nextx = x;
    int nexty = y + 1;
    if (nexty >= n) {
        nextx = x + 1;
        nexty = 0;
    }
    for (int i = 0; i < n; i++) {
        board[x][i] = 'Q';
        if (isValid(board, x, i, n)) {
            dfs(board, x + 1, 0, n, h + 1, cnt);
        }
        board[x][i] = '.';
    }

    return false;
}
int totalNQueens(int n){
    char **board = malloc(n * sizeof(char *));
    for (int i = 0; i < n; i++) {
        board[i] = malloc(n * sizeof(char));
        for (int j = 0; j < n; j++) {
            board[i][j] = '.';
        }
    }

    int cnt = 0;
    dfs(board, 0, 0, n, 0, &cnt);
    return cnt;
}

BFS

打开转盘锁

void up(char *s, int i)
{
    if(s[i] == '9') {
        s[i] = '0';
    } else {
        s[i] += 1;
    }
}
void down(char *s, int i)
{
    if(s[i] == '0') {
        s[i] = '9';
    } else {
        s[i] -= 1;
    }
}
int openLock(char ** deadends, int deadendsSize, char * target){
    char pwd[] = "0000";
    bool isDeadends[10000];
    for (int i = 0; i < 10000; i++) {
        isDeadends[i] = false;
    }
    for (int i = 0; i < deadendsSize; i++) {
        isDeadends[atoi(deadends[i])] = true;
    }
    bool visted[10000];
    for (int i = 0; i < 10000; i++) {
        visted[i] = false;
    }
    char queue[10000][5];
    int queueStart = 0, queueEnd = 0;
    int step = 0;

    strcpy(queue[queueEnd++], pwd);
    visted[atoi(pwd)] = true;
    while (queueStart != queueEnd) {
        char cur[5], next[5];
        int nowEnd = queueEnd;
        while (queueStart != nowEnd) {
            strcpy(cur, queue[queueStart++]);
            if (isDeadends[atoi(cur)]) {
                continue;
            }
            if (strcmp(cur, target) == 0) {
                return step;
            }
            for (int i = 0; i < 4; i++) {
                strcpy(next, cur);
                up(next, i);
                if (visted[atoi(next)] != true) {
                    strcpy(queue[queueEnd++], next);
                    visted[atoi(next)] = true;
                }
                strcpy(next, cur);
                down(next, i);
                if (visted[atoi(next)] != true) {
                    strcpy(queue[queueEnd++], next);
                    visted[atoi(next)] = true;
                }
            }
        }
        step++;
    }

    return -1;
}

动态规划

贪心算法

跳跃游戏

int jump(int* nums, int numsSize){
    int jump = 0, nextJump = 0;
    int cnt = 0;
    for (int i = 0; i < numsSize; i++) {
        if (i > jump) {
            cnt++;
            jump = nextJump;
        }
        if (i + nums[i] > nextJump) {
            nextJump = i + nums[i];
        }
    }

    return cnt;
}

主持人调度

#include <stdbool.h>
int cmp(int *a, int *b)
{
    if (*a < *b) return -1;
    if (*a > *b) return 1;
    return 0;
}
int minmumNumberOfHost(int n, int** startEnd, int startEndRowLen, int* startEndColLen ) {
    // write code here
    int start[startEndRowLen];
    int end[startEndRowLen];
    for (int i = 0; i < n; i++) {
        start[i] = startEnd[i][0];
        end[i] = startEnd[i][1];
    }
    qsort(start, startEndRowLen, sizeof(int), cmp);
    qsort(end, startEndRowLen, sizeof(int), cmp);
    for (int i = 0; i < n; i++) {
        printf("%d ", start[i]);
    }
    int cnt = 0;
    int max = 0;
    int s = 0, e = 0;
    while (s < startEndRowLen && e < startEndRowLen) {
        if (start[s] < end[e]) {
            cnt++;
            s++;
        } else {
            cnt--;
            e++;
        }
        if (cnt > max) {
            max = cnt;
        }
    }
    //printf("%d", max);

    return max;
}

树

字典树

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

#define TRIE_NUM 256
struct Trie {
    int cnt;
    bool isEnd;
    struct Trie *next[TRIE_NUM];
};

struct Trie *createTrie(void)
{
    struct Trie *root = (struct Trie *)malloc(sizeof(struct Trie));
    root->cnt = 0;
    root->isEnd = false;
    for (unsigned int i = 0; i < TRIE_NUM; i++) {
        root->next[i] = NULL;
    }
    return root;
}

bool searchTrie(struct Trie *root, char *s)
{
    struct Trie *p = root;
    unsigned int pos;
    while (*s != '\0') {
        pos = *s;
        if (p->next[pos] == NULL) {
           return false;
        } else {
            p = p->next[pos];
            if (p->cnt == 0) {
                return false;
            }
        }
        s++;
    }
    if (!p->isEnd) {
        return false;
    }
    return true;
}

void addTrie(struct Trie *root, char *s)
{
    if (searchTrie(root, s)) {
        return;
    }
    struct Trie *p = root;
    unsigned int pos;
    while (*s != '\0') {
        pos = *s;
        if (p->next[pos] == NULL) {
            p->next[pos] = createTrie();
            p = p->next[pos];
            p->cnt += 1;
        } else {
            p = p->next[pos];
            p->cnt += 1;
        }
        s++;
    }
    p->isEnd = true;
}


void delTrie(struct Trie *root, char *s)
{
    if (!searchTrie(root, s)) {
        return;
    }
    struct Trie *p = root;
    unsigned int pos;
    while (*s != '\0') {
        pos = *s;
        p = p->next[pos];
        p->cnt -= 1;
        s++;
    }
    p->isEnd = false;
}

int getPrefixTrieCount(struct Trie *root, char *s)
{
    struct Trie *p = root;
    unsigned int pos;
    while (*s != '\0') {
        pos = *s;
        if (p->next[pos] == NULL) {
           return 0;
        } else {
            p = p->next[pos];
            if (p->cnt == 0) {
                return 0;
            }
        }
        s++;
    }
    return p->cnt;
}
void dfsPrefixTrie(struct Trie *root, char **out, int *outSize, char *stack, int stackLen)
{
    if (root == NULL) {
        stack[stackLen] = '\0';
        strcpy(out[*outSize], stack);
        (*outSize) += 1;
        return;
    }
    if (root->isEnd) {
        stack[stackLen] = '\0';
        strcpy(out[*outSize], stack);
        (*outSize) += 1;
    }
    for (int i = 0; i < TRIE_NUM; i++) {
        if (root->next[i] != NULL) {
            stack[stackLen] = i;
            dfsPrefixTrie(root->next[i], out, outSize, stack, stackLen + 1);
        }
    }
}
int getPrefixTrie(struct Trie *root, char *s, char **out, int *outSize)
{
    struct Trie *p = root;
    char stack[100];
    int stackLen = 0;
    *outSize = 0;
    unsigned int pos;
    strcpy(stack, s);
    stackLen += strlen(s);
    while (*s != '\0') {
        pos = *s;
        if (p->next[pos] == NULL) {
           return 0;
        } else {
            p = p->next[pos];
            if (p->cnt == 0) {
                return 0;
            }
        }
        s++;
    }
    dfsPrefixTrie(p, out, outSize, stack, stackLen);
    return *outSize;
}

int main(void)
{
    struct Trie *root = createTrie();
    addTrie(root, "abc");
    addTrie(root, "abb");
    addTrie(root, "abc");
    addTrie(root, "abd");
    addTrie(root, "abdrfg");
    addTrie(root, "ab");
    delTrie(root, "ab");
    delTrie(root, "ab");
    addTrie(root, "ab");
    delTrie(root, "abc");
    delTrie(root, "abdrfg");
    printf("searchTrie(root, \"ab\") = %d\n", searchTrie(root, "ab"));
    printf("searchTrie(root, \"abdrfg\") = %d\n", searchTrie(root, "abdrfg"));

    char **out = malloc(100 * sizeof(char *));
    int outLen = 0;
    for (int i = 0; i < 100; i++) {
        out[i] = malloc(30 * sizeof(char));
    }
    int ret = getPrefixTrie(root, "ab", out, &outLen);
    printf("getPrefixTrieCount(root, \"ab\") = %d\n", getPrefixTrieCount(root, "ab"));
    for (int i = 0; i < outLen; i++) {
        printf("i=%d,%s\n", i, out[i]);
    }

    return 0;
}

图

并查集

省份数量

struct UnionStruct {
    int *parent;
    int cnt;
};

struct UnionStruct *CreateUnion(int n)
{
    struct UnionStruct *u = (struct UnionStruct *)malloc(sizeof(struct UnionStruct));
    u->parent = malloc(n * sizeof(int));
    u->cnt = n;
    for (int i = 0; i < n; i++) {
        u->parent[i] = i;
    }

    return u;
}

int FindUnion(struct UnionStruct *u, int x)
{
    while (u->parent[x] != x) {
        u->parent[x] = u->parent[u->parent[x]];
        x = u->parent[x];
    }

    return x;
}

void ConnectUnion(struct UnionStruct *u, int p, int q)
{
    int parentP = FindUnion(u, p);
    int parentQ = FindUnion(u, q);

    if (parentP == parentQ) {
        return;
    }

    u->parent[parentP] = parentQ;
    u->cnt--;
}

bool IsConnectedUnion(struct UnionStruct *u, int p, int q)
{
    return FindUnion(u, p) == FindUnion(u, q);
}

int ConnectCountUnion(struct UnionStruct *u)
{
    return u->cnt;
}

int findCircleNum(int** isConnected, int isConnectedSize, int* isConnectedColSize){
    struct UnionStruct *u = CreateUnion(isConnectedSize);
    
    for (unsigned int i = 0; i < isConnectedSize; i++) {
        for (unsigned int j = 0; j < isConnectedSize; j++) {
            if (isConnected[i][j]) {
                ConnectUnion(u, i, j);
            }
        }
    }

    return ConnectCountUnion(u);
}

图的遍历

void traverse(int** graph, int graphSize, int cur, bool *visted, bool *onPath, int *stack, int h, int **out, int* returnSize, int* returnColumnSizes)
{
    if (cur == graphSize - 1) {
        stack[h++] = cur;
        memcpy(out[*returnSize], stack, h * sizeof(int));
        returnColumnSizes[*returnSize] = h;
        (*returnSize) += 1;
        return;
    }/*
    if (visted[cur]) {
        return;
    }*/
    visted[cur] = true;
    onPath[cur] = true;
    stack[h] = cur;
    for (int i = 0; i < graphSize; i++) {
        if (graph[cur][i] == 1) {
            traverse(graph, graphSize, i, visted, onPath, stack, h + 1, out, returnSize, returnColumnSizes);
        }
    }
    onPath[cur] = false;
}
int** allPathsSourceTarget(int** graph, int graphSize, int* graphColSize, int* returnSize, int** returnColumnSizes){
    int **g = malloc(graphSize * sizeof(int *));
    for (int i = 0; i < graphSize; i++) {
        g[i] = malloc(graphSize * sizeof(int));
        for (int j = 0; j < graphSize; j++) {
            g[i][j] = 0; 
        }
    }
    for (int i = 0; i < graphSize; i++) {
        for (int j = 0; j < graphColSize[i]; j++) {
            g[i][graph[i][j]] = 1;
        }
    }
    int **out = malloc(10000 * sizeof(int *));
    *returnColumnSizes = malloc(10000 * sizeof(int));
    for (int i = 0; i < 10000; i++) {
        out[i] = malloc((graphSize + 2) * sizeof(int));
    }
    *returnSize = 0;
    int stack[graphSize + 2];
    bool visted[graphSize];
    for (int i = 0; i < graphSize; i++) {
        visted[i] = false;
    }
    bool onPath[graphSize];
    for (int i = 0; i < graphSize; i++) {
        onPath[i] = false;
    }
    traverse(g, graphSize, 0, visted, onPath, stack, 0, out, returnSize, *returnColumnSizes);
    return out;
}

图的环检测算法

dfs版

bool traverse(int** graph, int graphSize, int cur, bool *visited, bool *onPath)
{
    if (onPath[cur]) {
        return true;
    }
    if (visited[cur]) {
        return false;
    }
    visited[cur] = true;
    onPath[cur] = true;
    bool isCycle = false;
    for (int i = 0; i < graphSize; i++) {
        if (graph[cur][i] == 0) {
            continue;
        }
        if (traverse(graph, graphSize, i, visited, onPath)) {
            isCycle =  true;
            break;
        }
    }
    onPath[cur] = false;
    return isCycle;
}

bool canFinish(int numCourses, int** prerequisites, int prerequisitesSize, int* prerequisitesColSize){

    int **graph = malloc((numCourses + 1) * sizeof(int *));
    for (int i = 0; i < (numCourses + 1); i++) {
        graph[i] = malloc((numCourses + 1) * sizeof(int));
        for (int j = 0; j < (numCourses + 1); j++) {
            graph[i][j] = 0;
        }
    }
    for (int i = 0; i < prerequisitesSize; i++) {
        graph[prerequisites[i][1]][prerequisites[i][0]] = 1;
    }

#if 0
    for (int i = 0; i < (numCourses + 1); i++) {
        printf("[");
        for (int j = 0; j < (numCourses + 1); j++) {
            printf("%d, ", graph[i][j]);
        }
        printf("]\n");
    }
#endif

    bool visited[numCourses + 1];
    bool onPath[numCourses + 1];
    for (int i = 0; i < (numCourses + 1); i++) {
        visited[i] = false;
        onPath[i] = false;
    }
    for (int i = 0; i < (numCourses + 1); i++) {
        if (visited[i]) {
            continue;
        }
        if (traverse(graph, (numCourses + 1), i, visited, onPath)) {
            return false;
        }
    }
    return true;
}

拓扑排序

dfs版

bool traverse(int** graph, int graphSize, int cur, bool *visited, bool *onPath, int *out, int *returnSize)
{
    if (onPath[cur]) {
        return true;
    }
    if (visited[cur]) {
        return false;
    }
    visited[cur] = true;
    onPath[cur] = true;
    bool isCycle = false;
    for (int i = 0; i < graphSize; i++) {
        if (graph[cur][i] == 0) {
            continue;
        }
        if (traverse(graph, graphSize, i, visited, onPath, out, returnSize)) {
            isCycle =  true;
            break;
        }
    }
    onPath[cur] = false;
    out[*returnSize] = cur;
    (*returnSize) += 1;
    return isCycle;
}
int* findOrder(int numCourses, int** prerequisites, int prerequisitesSize, int* prerequisitesColSize, int* returnSize){
    int **graph = malloc((numCourses + 1) * sizeof(int *));
    for (int i = 0; i < (numCourses + 1); i++) {
        graph[i] = malloc((numCourses + 1) * sizeof(int));
        for (int j = 0; j < (numCourses + 1); j++) {
            graph[i][j] = 0;
        }
    }
    for (int i = 0; i < prerequisitesSize; i++) {
        graph[prerequisites[i][1]][prerequisites[i][0]] = 1;
    }

#if 0
    for (int i = 0; i < (numCourses + 1); i++) {
        printf("[");
        for (int j = 0; j < (numCourses + 1); j++) {
            printf("%d, ", graph[i][j]);
        }
        printf("]\n");
    }
#endif
    *returnSize = 0;
    int *out = malloc((numCourses + 1) * sizeof(int));
    bool visited[numCourses + 1];
    bool onPath[numCourses + 1];
    for (int i = 0; i < (numCourses + 1); i++) {
        visited[i] = false;
        onPath[i] = false;
    }
    for (int i = 0; i < numCourses; i++) {
        if (visited[i]) {
            continue;
        }
        if (traverse(graph, (numCourses + 1), i, visited, onPath, out, returnSize)) {
            *returnSize = 0;
            return NULL;
        }
    }
#if 0
    for (int i = 0; i < *returnSize; i++) {
        printf("%d ", out[i]);
    }
#endif
    int left = 0, right = (*returnSize) - 1;
    while (left < right) {
        int tmp = out[left];
        out[left] = out[right];
        out[right] = tmp;
        left++;
        right--;
    }
    return out;
}

BFS 版

int* findOrder(int numCourses, int** prerequisites, int prerequisitesSize, int* prerequisitesColSize, int* returnSize){
    
    int **graph = malloc((numCourses + 1) * sizeof(int *));
    for (int i = 0; i < (numCourses + 1); i++) {
        graph[i] = malloc((numCourses + 1) * sizeof(int));
        for (int j = 0; j < (numCourses + 1); j++) {
            graph[i][j] = 0;
        }
    }

    int indgree[numCourses];
    for (int i = 0; i < numCourses; i++) {
        indgree[i] = 0;
    }
    for (int i = 0; i < prerequisitesSize; i++) {
        graph[prerequisites[i][1]][prerequisites[i][0]] = 1;
        indgree[prerequisites[i][0]]++;
    }
    int zeroQueue[numCourses];
    int zeroQueueEnd = 0;
    int tmpZeroQueue[numCourses];
    int tmpZeroQueueEnd = 0;
    for (int i = 0; i < numCourses; i++) {
        if (indgree[i] == 0) {
            zeroQueue[zeroQueueEnd++] = i;
        }
    }
    //printf("%d", zeroQueueEnd);

    *returnSize = 0;
    int *out = malloc((numCourses + 1) * sizeof(int));
    int count = 0;
    while (zeroQueueEnd > 0) {
        for (int i = 0; i < zeroQueueEnd; i++) {
            count++;
            int cur = zeroQueue[i];
            out[*returnSize] = cur;
            (*returnSize) += 1;
            for (int i = 0; i < numCourses; i++) {
                if (graph[cur][i] == 0) {
                    continue;
                }
                indgree[i]--;
                if (indgree[i] == 0) {
                    tmpZeroQueue[tmpZeroQueueEnd++] = i;
                }
            }
        }
        memcpy(zeroQueue, tmpZeroQueue, tmpZeroQueueEnd * sizeof(int));
        zeroQueueEnd = tmpZeroQueueEnd;
        tmpZeroQueueEnd = 0;
        //printf("%d ", zeroQueueEnd);
    }
    if (count != numCourses) {
        *returnSize = 0;
        return NULL;
    }

    return out;
}

二分图判定

dfs版

bool traverse(int** graph, int graphSize, int cur, bool *visited, bool *color){
    visited[cur] = true;
    for (int i = 0; i < graphSize; i++) {
        if (graph[cur][i] == 0) {
            continue;
        }
        if (visited[i]) {
            if (color[cur] == color[i]) {
                return false;
            }
        } else {
            color[i] = !color[cur];
            if (!traverse(graph, graphSize, i, visited, color)) {
                return false;
            }
        }
    }

    return true;
}
bool isBipartite(int** graph, int graphSize, int* graphColSize){
    int **g = malloc(graphSize * sizeof(int *));
    for (int i = 0; i < graphSize; i++) {
        g[i] = malloc(graphSize * sizeof(int));
        for (int j = 0; j < graphSize; j++) {
            g[i][j] = 0; 
        }
    }
    for (int i = 0; i < graphSize; i++) {
        for (int j = 0; j < graphColSize[i]; j++) {
            g[i][graph[i][j]] = 1;
        }
    }

    bool visited[graphSize];
    bool color[graphSize];
    for (int i = 0; i < graphSize; i++) {
        visited[i] = false;
        color[i] = false;
    }

    for (int i = 0; i < graphSize; i++) {
        if (!visited[i]) {
            if (!traverse(g, graphSize, i, visited, color)) {
                return false;
            }
        }
    }

    return true;
}

Kruskal 最小生成树算法

struct UnionStruct {
    int *parent;
    int cnt;
};

struct UnionStruct *CreateUnion(int n)
{
    struct UnionStruct *u = (struct UnionStruct *)malloc(sizeof(struct UnionStruct));
    u->parent = malloc(n * sizeof(int));
    u->cnt = n;
    for (int i = 0; i < n; i++) {
        u->parent[i] = i;
    }

    return u;
}

int FindUnion(struct UnionStruct *u, int x)
{
    while (u->parent[x] != x) {
        u->parent[x] = u->parent[u->parent[x]];
        x = u->parent[x];
    }

    return x;
}

void ConnectUnion(struct UnionStruct *u, int p, int q)
{
    int parentP = FindUnion(u, p);
    int parentQ = FindUnion(u, q);

    if (parentP == parentQ) {
        return;
    }

    u->parent[parentP] = parentQ;
    u->cnt--;
}

bool IsConnectedUnion(struct UnionStruct *u, int p, int q)
{
    return FindUnion(u, p) == FindUnion(u, q);
}

int ConnectCountUnion(struct UnionStruct *u)
{
    return u->cnt;
}

struct points {
    int i;
    int j;
    int cost;
};

int cmp(struct points *a, struct points *b)
{
    return a->cost - b->cost;
}
int minCostConnectPoints(int** points, int pointsSize, int* pointsColSize){
    struct points buf[pointsSize * pointsSize];
    int bufLen = 0;
    
    for (int i = 0; i < pointsSize; i++) {
        for (int j = i + 1; j < pointsSize; j++) {
            buf[bufLen].i = i;
            buf[bufLen].j = j;
            buf[bufLen].cost = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]);
            bufLen++;
        }
    }
    qsort(buf, bufLen, sizeof(struct points), cmp);

    int mst = 0;
    struct UnionStruct *u = CreateUnion(pointsSize);
    for (int i = 0; i < bufLen; i++) {
        if (IsConnectedUnion(u, buf[i].i, buf[i].j)) {
            continue;
        }
        mst += buf[i].cost;
        ConnectUnion(u, buf[i].i, buf[i].j);
    }

    return mst;
}

Prim 最小生成树算法

struct points {
    int i;
    int j;
    int cost;
};
int cmp(struct points *a, struct points *b)
{
    return a->cost - b->cost;
}
void cut(int **graph, int graphSize, int cur, bool *visted, struct points *pq, int *pqStart, int *pqEnd)
{
    for (int i = 0; i < graphSize; i++) {
        if (graph[cur][i] == 0) {
            continue;
        }
        if (visted[i]) {
            continue;
        }
#if 1
        pq[*pqEnd].i = cur;
        pq[*pqEnd].j = i;
        pq[*pqEnd].cost = graph[cur][i];
        (*pqEnd) += 1;
#endif
#if 0
        int end = *pqEnd;
        struct points now;
        now.i = cur;
        now.j = i;
        now.cost = graph[cur][i];
        pq[end] = now;
        while (end > *pqStart) {
            if (pq[end].cost < pq[end - 1].cost) {
                pq[end] = pq[end - 1];
                pq[end - 1] = now;
            }
            end--;
        }
        (*pqEnd) += 1;
#endif
    }

    qsort(&pq[*pqStart], (*pqEnd) - (*pqStart), sizeof(struct points), cmp);
}
int minCostConnectPoints(int** points, int pointsSize, int* pointsColSize){
    int graphSize = pointsSize;
    int **graph = malloc(graphSize * sizeof(int *));
    for (int i = 0; i < graphSize; i++) {
        graph[i] = malloc(graphSize * sizeof(int));
        for (int j = 0; j < pointsSize; j++) {
            graph[i][j] = 0;
        }
    }
    for (int i = 0; i < pointsSize; i++) {
        for (int j = i + 1; j < pointsSize; j++) {
            graph[i][j] = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]);
            graph[j][i] = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]);
        }
    }
    bool visted[graphSize];
    for (int i = 0; i < graphSize; i++) {
        visted[i] = false;
    }

    struct points pq[200000];
    int pqStart = 0, pqEnd = 0;
    int mst = 0;
    visted[0] = true;
    cut(graph, graphSize, 0, visted, pq, &pqStart, &pqEnd);
    while (pqStart != pqEnd) {
        //printf("%d ", pop.jpop.jpop.jpop.j)
        struct points pop = pq[pqStart++];
        if (visted[pop.j]) {
            continue;
        }
        mst += pop.cost;
        visted[pop.j] = true;
        cut(graph, graphSize, pop.j, visted, pq, &pqStart, &pqEnd);
    }

    return mst;
}

Dijkstra 最短路径算法

struct queueNode {
    int cur;
    int dist;
};
struct queue {
    struct queueNode *buf;
    int maxLen;
    int start;
    int end;
};

struct queue *CreateQueue(int maxLen)
{
    struct queue *q = malloc(sizeof(struct queue));

    q->buf = malloc(maxLen * sizeof(struct queueNode));
    q->maxLen = maxLen;
    q->start = 0;
    q->end = 0;

    return q;
}

bool QueueIsEmpty(struct queue *q)
{
    return q->start == q->end;
}

void QueuePush(struct queue *q, int cur, int dist)
{
#if 0
    struct queueNode node;
    int end = (q->end - 1 < 0) ? (q->maxLen - 1) : (q->end - 1 < 0);
    int start = (q->start - 1 < 0) ? (q->maxLen - 1) : (q->start - 1 < 0);
    node.cur = cur;
    node.dist = dist;
    q->buf[q->end] = node;
    while (end != start && q->buf[end].dist > dist) {
        int nextEnd = ((end + 1) >= q->maxLen) ? (0) : (end + 1);
        q->buf[nextEnd] = q->buf[end];
        q->buf[end] = node;
        end--;
        if (end < 0) {
            end = q->maxLen - 1;
        }
    }
#endif
#if 1
    q->buf[q->end].cur = cur;
    q->buf[q->end].dist = dist;
#endif
    q->end = q->end + 1;
    if (q->end >= q->maxLen) {
        q->end = 0;
    }
}

struct queueNode QueuePop(struct queue *q)
{
    struct queueNode res = q->buf[q->start];
    q->start = q->start + 1;
    if (q->start >= q->maxLen) {
        q->start = 0;
    }

    return res;
}

int networkDelayTime(int** times, int timesSize, int* timesColSize, int n, int k){
    int graphColSize = n + 1;
    int **graph = malloc(graphColSize * sizeof(int *));

    for (int i = 0; i < graphColSize; i++) {
        graph[i] = malloc(graphColSize * sizeof(int));
        for (int j = 0; j < graphColSize; j++) {
            graph[i][j] = -1;
        }
    }

    for (int i = 0; i < timesSize; i++) {
        graph[times[i][0]][times[i][1]] = times[i][2];
    }

    int distTo[graphColSize];
    for (int i = 0; i < graphColSize; i++) {
        distTo[i] = INT_MAX;
    }
    distTo[k] = 0;

    struct queue *q = CreateQueue(1000);
    QueuePush(q, k, 0);

    while (!QueueIsEmpty(q)) {
        struct queueNode node = QueuePop(q);
        if (distTo[node.cur] < node.dist) {
            continue;
        }
        for (int next = 1; next < graphColSize; next++) {
            if (graph[node.cur][next] < 0) {
                continue;
            }
            int distToNext = distTo[node.cur] + graph[node.cur][next];
            if (distTo[next] > distToNext) {
                distTo[next] = distToNext;
                QueuePush(q, next, distToNext);
            }
        }
    }

    int max = 0;
    for (int i = 1; i < graphColSize; i++) {
        if (distTo[i] == INT_MAX) {
            return -1;
        }
        if (max < distTo[i]) {
            max = distTo[i];
        }
    }

    return max;
}

状态机

有限状态机

有效数字

enum {
    C_BLK = 0,
    C_SIGN,
    C_DIGTAL,
    C_DOT,
    C_EXP,
    C_OTHER,
};
enum {
    ST_PER,
};

int StTab[][C_OTHER + 1] = {
    {0, 1, 2, 6, -1, -1,},
    {-1, -1, 2, 6, -1, -1,},
    {-1, -1, 2, 8,  3, -1,},
    {-1, 4, 5, -1, -1, -1,},
    {-1, -1, 5, -1, -1, -1,},
    {-1, -1, 5, -1, -1, -1,},
    {-1, -1, 7, -1, -1, -1,},
    {-1, -1, 7, -1, 3, -1,},
    {-1, -1, 7, -1, 3, -1,},
};

bool final[] = {
    false, false, true, false, false, true, false, true, true,
};

int GetCharType(char c)
{
    if (c >= '0' && c <= '9') {
        return C_DIGTAL;
    }

    switch (c) {
        case ' ':
            return C_BLK;
            break;
        case '+':
        case '-':
            return C_SIGN;
            break;
        case '.':
            return C_DOT;
            break;
        case 'e':
        case 'E':
            return C_EXP;
            break;
    }

    return C_OTHER;
}

bool isNumber(char * s){

    int st = 0;
    while (*s != '\0') {
        st = StTab[st][GetCharType(*s)];
        if (st == -1) {
            return false;
        }
        s++;
    }
    printf("st=%d\r\n", st);
    return final[st];
}

数学

两数相除

long long divv(long long  a, long long b)
{
    if (a < b) return 0;
    long long tb = b;
    long long cnt = 1;
    while (tb + tb <= a) {
        cnt += cnt;
        tb += tb;
    }
    return cnt + divv(a - tb, b);
}
int divide(int dividend, int divisor){
    if (dividend == 0) return 0;
    if (divisor == 1) return dividend;
    if (divisor == -1) {
        if (dividend > INT_MIN)
            return -dividend;
        return INT_MAX;
    }
    int sign = 0;
    if ((dividend < 0 && divisor > 0) ||
    (dividend > 0 && divisor < 0)) {
        sign = 1;
    }
    long long a = dividend, b = divisor;
    if (a < 0) {
        a = -a;
    }
    if (b < 0) {
        b = -b;
    }
    long long res = divv(a, b);
    if (sign == 1) return -res;
    return res;//res > INT_MAX ? INT_MAX : res;
}

质数

思路
欧几里德算法求最大公约数，公约数为1的则互质。

代码实现

int gcd(int x, int y)
{
    int t;
    while(y % x != 0) {
        t = x;
        x = y % x;
        y = t;
    }
    return x;
}

标签：return,struct,int,graph,练习,++,算法,cur
From： https://www.cnblogs.com/weizhidianzi/p/16757069.html

算法练习C

心得

计算机思维的理解

学算法的个人认为有如下三个问题

解题思路总结

基础

排序

冒泡排序

快速排序

堆排序

数组

前缀和

和为K的子数组

差分数组

航班预订统计

字符串

KMP字符串比对算法

栈

单调栈

队列

单调队列

滑动窗口最大值

优先队列

双指针

左右指针

三数之和

滑动窗口

最小子串

哈希

原地哈希

DFS

全排列

数独

N皇后

BFS

打开转盘锁

动态规划

贪心算法

跳跃游戏

主持人调度

树

字典树

图

并查集

省份数量

图的遍历

图的环检测算法

拓扑排序

dfs版

BFS 版

二分图判定

dfs版

Kruskal 最小生成树算法

Prim 最小生成树算法

Dijkstra 最短路径算法

状态机

有限状态机

有效数字

数学

两数相除

质数

相关文章

赞助商

阅读排行