算法之美

纯编程题

1. 两数之和

class Solution {
    public int[] twoSum(int[] nums, int target) {
//        return twoSum_violent(nums, target);
        return twoSum_hashmap(nums, target);
    }

    public int[] twoSum_hashmap(int[] nums, int target) {
        // 每遍历一个数，就记录该数所需的搭档数即该数的索引
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            Integer preIndex = map.get(nums[i]);
            if (preIndex != null) {
                return new int[]{preIndex, i};
            } else {
                map.put(target - nums[i], i);
            }
        }
        return null;
    }
    
    public int[] twoSum_violent(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length; j++) {
                if (j == i) {
                    continue;
                }
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return null;
    }
}

9. 回文数

public class LC9_palindrome_number {
    public boolean isPalindrome(int x) {
        return isPalindrome_V2(x);
    }

    // 奇数个数字回文 121，偶数个数字回文 1221
    // 不必完整构造出逆序数字，构造到一半就可以
    public boolean isPalindrome_V2(int x) {
        if (x == 0) return true;
        if (x < 0 || x % 10 == 0) return false; // 易忽略：数字是10倍数（末位是0）
        int reverse = 0 ;
        while (x > reverse) {
            reverse = reverse * 10 + x % 10;
            x /= 10;
        }
        return x == reverse || x == (reverse / 10);
    }

    // 通过不断对10取模、除以10，构建出逆序数字，与原数字比较
    private boolean isPalindrome_V1(int x) {
        if (x < 0) {
            return false;
        }
        int num = x;
        int k = 0;
        // num = 123
        while (num != 0) {
            k += num % 10; // k = 3, 32, 321
            num /= 10;  // m = 12, 1, 0
            if (num != 0) k *= 10; // k = 30, 320, 321
        }
        return k == x;
    }
}

26. 删除有序数组中的重复项

public class LC26_remove_duplicates_from_sorted_array {

    public static void main(String[] args) {
        LC26_remove_duplicates_from_sorted_array o = new LC26_remove_duplicates_from_sorted_array();
        System.out.println(o.removeDuplicates(new int[]{1, 1, 2}));;
    }

    public int removeDuplicates(int[] nums) {
        int len = nums.length;
        int cnt = 1;
        int base = nums[0], i = 1;
        // 每次循环以当前元素为基准，忽略连续的重复元素，将首个非重复元素向前移动并作为新的基准元素
        while (i < len) {
            // 跳过与当前元素相同的元素
            while (i < len && nums[i] == base) i++;
            // 来到末尾，结束
            if (i == len) break;
            // 来到新元素
            base = nums[i];
            nums[cnt++] = base;
        }
        return cnt;
    }
}

58. 最后一个单词的长度

public class LC58_length_of_last_word {
    public int lengthOfLastWord(String s) {
        int i = s.length() - 1;
        // 从后往前忽略空格
        while (i >= 0 && s.charAt(i) == ' ') i--;
        // i来到单词的最后一个字母，从后往前计数
        int cnt = 0;
        while (i >= 0 && s.charAt(i) != ' ') {
            i--;
            cnt++;
        }
        return cnt;
    }
}

125. 验证回文串

public class LC123_valid_palindrome {

    public static void main(String[] args) {
        String s = "A man, a plan, a canal: Panama";
        System.out.println(isPalindrome(s));
    }
    public static boolean isPalindrome(String s) {
        char[] str = s.toCharArray();
        int m = 0, n = 0;
        // 去掉非字母数字字符
        while (n < str.length) {
            if ((str[n] >= 'a' && str[n] <= 'z')
                    || (str[n] >= 'A' && str[n] <= 'Z')
                    || (str[n] >= '0' && str[n] <= '9')) {
                if (str[n] >= 'A' && str[n] <= 'Z') str[n] += 32;
                str[m++] = str[n++];
            } else {
                n++;
            }
        }
        if (m == 0) return false;
        return isPalindrome(str, 0, m - 1);
    }

    public static boolean isPalindrome(char[] str, int st, int ed) {
        while(st < ed) {
            if (str[st++] != str[ed--]) return false;
        }
        return true;
    }
}

344. 反转字符串

public class LC344_reverse_string {
    public void reverseString(char[] s) {
        int n = s.length;
        int k = 0;
        char ch;
        while (k < n - k - 1) {
            ch = s[k];
            s[k] = s[n - k - 1];
            s[n - k - 1] = ch;
            k++;
        }
    }
}

1108. IP 地址无效化

public class LC1108_defanging_an_ip_address {
    public String defangIPaddr(String address) {
        int n = address.length();
        char[] invalid = new char[n + 6];
        int k = 0;
        for (int i = 0; i < n; i++) {
            char ch = address.charAt(i);
            if (ch != '.') {
                invalid[k++] = address.charAt(i);
            } else {
                invalid[k++] = '[';
                invalid[k++] = '.';
                invalid[k++] = ']';
            }
        }
        return new String(invalid);
    }
}

LCR 122. 路径加密

public class LCR122_ti_huan_kong_ge_lcof {
    public String pathEncryption(String path) {
        char[] arr = path.toCharArray();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == '.') arr[i] = ' ';
        }
        return new String(arr);
    }
}

LCR 181. 字符串中的单词反转

public class LCR181_fan_zhuan_dan_ci_shun_xu_lcof {
    /**
     * 去掉前导、后缀以及多余空格
     * 紧挨的字符视为一个单词，包含数字、符号
     *
     * @param message
     * @return
     */
    public String reverseMessage(String message) {
        return reverseMessage_V2(message);
    }

    public String reverseMessage_V3(String message) {
        if(message == null || message.isEmpty()) {
            return "";
        }
        char[] str = message.toCharArray();
        // 去空格
        int n = trim(str);
        if (n == 0){
            return "";
        }
        // 整体翻转
        reverse(str, 0, n - 1);
        // 单词翻转
        int left = 0, right = 0;
        while(right < n) {
            while(right < n && str[right] != ' ') right++;
            // 遇到结尾或者空格
            reverse(str, left, right - 1);
            left = right + 1;
            right = left;
        }

        return new String(str, 0, n);
    }

    // 返回去空格后有效字符串的长度，"  abc  d e " => "abc d e"
    public int trim(char[] str) {
        int left = 0, right = str.length - 1;
        while(left < str.length && str[left] == ' ') left++;
        while(right >= 0 && str[right] == ' ') right--;
        // 记录有效字符串长度
        int k = 0;
        while(left <= right) {
            while(left <= right && str[left] != ' ') str[k++] = str[left++];
            // left来到了right或空格
            if (left <= right && str[left] == ' ') str[k++] = str[left++];
            while(left <= right && str[left] == ' ') left++;
        }
        return k;
    }

    public void reverse(char[] str, int start, int end) {
        while(start < end) {
            char tmp = str[start];
            str[start] = str[end];
            str[end] = tmp;
            start++;
            end--;
        }
    }


    /**
     * 逆序遍历字符串使用左右指针标记每个单词
     * @param message
     * @return
     */
    public String reverseMessage_V2(String message) {
        int n = message.length();
        char[] res = new char[n + 1];
        int left = 0, right = 0;
        int k = 0, i = n - 1;
        while (i >= 0) {
            //跳过前导空格
            while (i >= 0 && message.charAt(i) == ' ') {
                i--;
            }
            //记录单词右端索引
            right = i + 1;
            //跳过连续字符
            while (i >= 0 && message.charAt(i) != ' ') {
                i--;
            }
            //记录单词左端索引
            left = i + 1;
            // 拷贝单词
            for (; left < right; left++) {
                res[k++] = message.charAt(left);
                if (left == right - 1) {
                    res[k++] = ' ';
                }
            }
        }

        if (k == 0) {
            return "";
        }
        return new String(res, 0, k - 1);
    }

    /**
     * 顺序遍历字符串，使用双端队列记录单词，然后逆向拼接单词
     * 缺点：额外使用了队列，拼接单词多了一遍循环
     * @param message
     * @return
     */
    public String reverseMessage_V1(String message) {
        if (message == null || message.isEmpty()) {
            return message;
        }
        Deque<String> words = new LinkedList<>();
        //单词长度
        int wordLen = 0, totalWordLen = 0;
        for (int i = 0; i < message.length(); i++) {
            char ch = message.charAt(i);
            //遇到字符，增加单词长度
            if (ch != ' ') {
                wordLen++;
            } else { //遇到空格
                //空格前没有字符
                if (wordLen == 0) {
                    continue;
                }
                //空格前有字符
                String word = message.substring(i - wordLen, i);
                words.offer(word);
                totalWordLen += wordLen;
                wordLen = 0;
            }
        }
        //补偿最后一个单词后面没有空格的情况
        if (wordLen != 0) {
            String word = message.substring(message.length() - wordLen);
            words.offer(word);
            totalWordLen += wordLen;
        }
        //如果单词队列为空
        if (words.isEmpty()) {
            return "";
        }
        //逆向拼接单词
        char[] sentence = new char[totalWordLen + words.size() - 1];
        int k = 0;
        while (!words.isEmpty()) {
            char[] word = words.pollLast().toCharArray();
            for (char ch : word) {
                sentence[k++] = ch;
            }
            //非结尾单词增加空格
            if (!words.isEmpty()) {
                sentence[k++] = ' ';
            }
        }

        return new String(sentence);
    }
}

LCR 182. 动态口令

public class LCR182_zuo_xuan_zhuan_zi_fu_chuan_lcof {
    public String dynamicPassword(String password, int target) {
        int len = password.length();
        if (target <= 0 || target >= len) {
            return password;
        }
        char[] str = new char[len];
        for (int i = 0; i < len; i++) {
            char ch = password.charAt(i);
            if (i < target) {
                str[len - target + i] = ch;
            } else {
                str[i - target] = ch;
            }
        }
        return new String(str);
    }
}

LCR 192. 把字符串转换成整数 (atoi)

public class LCR192_ba_zi_fu_chuan_zhuan_huan_cheng_zheng_shu_lcof {
    public int myAtoi(String str) {
        if (str == null || str.isEmpty()) {
            return 0;
        }
        // 跳过前导空格
        int p = 0;
        while (p < str.length() && str.charAt(p) == ' ') p++;
        if (p == str.length()) return 0;
        // 判断正负号
        boolean negative = false;
        if (str.charAt(p) == '-' || str.charAt(p) == '+') {
            negative = (str.charAt(p) == '-');
            p++;
        }
        // 读取数字
        int res = 0;
        while (p < str.length() && str.charAt(p) >= '0' && str.charAt(p) <= '9') {
            int num = str.charAt(p) - '0';
            // 判断是否会越界
            if (checkOverflow(res, num, negative)) {
                return negative ? Integer.MIN_VALUE : Integer.MAX_VALUE;
            }
            res = res * 10 + num;
            p++;
        }
        if (negative) res = -res;
        return res;
    }

    private boolean checkOverflow(int res, int num, boolean negative) {
        if (res == 0) return false;
        int max = Integer.MAX_VALUE;
        int min = Integer.MIN_VALUE;
        if (negative) {
            if (res > -(min / 10)) return true;
            return num > -(min + res * 10);
        } else {
            if (res > (max / 10)) return true;
            return num > (max - res * 10);
        }
    }

    public static void main(String[] args) {
        LCR192_ba_zi_fu_chuan_zhuan_huan_cheng_zheng_shu_lcof o = new LCR192_ba_zi_fu_chuan_zhuan_huan_cheng_zheng_shu_lcof();
        System.out.println(o.myAtoi("   -42"));
    }
}

找规律题

48. 旋转图像

void swap4(int **matrix, int i1, int j1, int i2, int j2, int i3, int j3, int i4, int j4) {
    int tmp = matrix[i1][j1];
    matrix[i1][j1] = matrix[i4][j4];
    matrix[i4][j4] = matrix[i3][j3];
    matrix[i3][j3] = matrix[i2][j2];
    matrix[i2][j2] = tmp;
}

void rotate(int **matrix, int matrixSize, int *matrixColSize) {
    // 一圈一圈地旋转（先是最外层的行和列组成的一层）
    int n = matrixSize; // 当前要旋转的圈对应的矩阵维度
    int i1 = 0, j1 = 0;
    while (n > 1) {
        // 先确定四个角上的基准点
        int i2 = i1;
        int j2 = j1 + n - 1;
        int i3 = i1 + n - 1;
        int j3 = j1 + n - 1;
        int i4 = i1 + n - 1;
        int j4 = j1;
        // 依次旋转四个点，根据基准点依次推导后续要旋转的四个点的坐标
        for (int move = 0; move <= n - 2; ++move) {
            int p1_i = i1 + 0;
            int p1_j = j1 + move;
            int p2_i = i2 + move;
            int p2_j = j2 + 0;
            int p3_i = i3 + 0;
            int p3_j = j3 - move;
            int p4_i = i4 - move;
            int p4_j = j4 + 0;
            swap4(matrix, p1_i, p1_j, p2_i, p2_j, p3_i, p3_j, p4_i, p4_j);
        }

        // 更新下一圈的基准点
        i1++;
        j1++;
        // 每一圈对应的矩阵维度相差2（少两行、两列）
        n -= 2;
    }
}

void rotate_v1(int **matrix, int matrixSize, int *matrixColSize) {
    *matrixColSize = matrixSize;
    if (matrixSize == 1) {
        return;
    }
    // 矩阵变换，先转置再镜像
    for (int i = 0; i < matrixSize - 1; ++i) {
        for (int j = i + 1; j < matrixSize; ++j) {
            int tmp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = tmp;
        }
    }
    int loop = matrixSize / 2, j = 0;
    while (loop-- > 0) {
        for (int i = 0; i < matrixSize; ++i) {
            int tmp = matrix[i][j];
            matrix[i][j] = matrix[i][matrixSize - j - 1];
            matrix[i][matrixSize - j - 1] = tmp;
        }
        j++;
    }
}

void rotate_v2(int **matrix, int matrixSize, int *matrixColSize) {
    *matrixColSize = matrixSize;
    if (matrixSize == 1) {
        return;
    }
    int loop = matrixSize / 2;
    int i = 0, n = matrixSize - 1;
    while (loop-- > 0) {
        for (int j = i; j < n - i; ++j) {
            int tmp = matrix[i][j];
            matrix[i][j] = matrix[n - j][i];
            matrix[n - j][i] = matrix[n - i][n - j];
            matrix[n - i][n - j] = matrix[j][n - i];
            matrix[j][n - i] = tmp;
        }
        i++;
    }
}

int main() {
    const int n = 4;
    int *matrix[] = {
            (int[]) {5, 1, 9, 11},
            (int[]) {2, 4, 8, 10},
            (int[]) {13, 3, 6, 7},
            (int[]) {15,14,12,16}
    };
    int *matrixColSize = malloc(sizeof(int));
    rotate_v1(matrix, n, matrixColSize);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            printf("%d ", matrix[i][j]);
        }
        printf("\n");
    }
}

54. 螺旋矩阵

int* spiralOrder(int** matrix, int matrixSize, int* matrixColSize, int* returnSize) {
    int len = matrixSize * (*matrixColSize);
    int *res = malloc(sizeof(int) * len);
    int k = 0;
    int left, right, top, bottom;
    left = top = 0;
    bottom = matrixSize - 1;
    right = *matrixColSize - 1;

    // 从外到内，按圈遍历
    while (left <= right && top <= bottom) {
        // 从左到右
        for (int j = left; j <= right; ++j) {
            res[k++] = matrix[top][j];
        }
        // 从上到下
        for (int i = top + 1; i <= bottom; ++i) {
            res[k++] = matrix[i][right];
        }
        // 从右到左；只有一行的情况下跳过
        if (top != bottom) {
            for (int j = right - 1; j >= left; --j) {
                res[k++] = matrix[bottom][j];
            }
        }
        // 从下到上；只有一列的情况下跳过
        if (left != right) {
            for (int i = bottom - 1; i > top; --i) {
                res[k++] = matrix[i][left];
            }
        }
        // 缩小圈子
        left++;
        right--;
        top++;
        bottom--;
    }
    *returnSize = k;
    return res;
}

int* spiralOrder_v1(int** matrix, int matrixSize, int* matrixColSize, int* returnSize) {
    int row = matrixSize, col = *matrixColSize;
    *returnSize = row * col;
    int *res = malloc(sizeof(int) * (*returnSize));

    int min = row > col ? col : row;
    int loop = (min + 1) / 2;
    int start = 0, k = 0;
    int i, j;
    while (loop-- > 0) {
        i = j = start;
        if (row == 1) {
            while (j < start + col) {
                res[k++] = matrix[i][j];
                j++;
            }
            break;
        }
        if (col == 1) {
            while (i < start + row) {
                res[k++] = matrix[i][j];
                i++;
            }
            break;
        }
        while (j < start + col - 1) {
            res[k++] = matrix[i][j];
            j++;
        }
        while (i < start + row - 1) {
            res[k++] = matrix[i][j];
            i++;
        }
        while (j > start) {
            res[k++] = matrix[i][j];
            j--;
        }
        while (i > start) {
            res[k++] = matrix[i][j];
            i--;
        }
        start++;
        row -= 2;
        col -= 2;
    }

    return res;
}

int main() {
    int *matrix[] = {
            (int[]) {1,2,3},
            (int[]) {4,5,6},
            (int[]) {7,8,9}
    };
    int col = 3;
    int size = 0;
    int* res = spiralOrder(matrix, 3, &col, &size);
    for (int i = 0; i < 9; ++i) {
        printf("%d ", res[i]);
    }
    return 0;
}

55. 跳跃游戏

bool canJump(int* nums, int numsSize) {
    // 记录最大可达位置下标
    int max_position = 0;
    for (int i = 0; i < numsSize; ++i) {
        if (i > max_position) {
            return false;
        }
        if (i + nums[i] > max_position) {
            max_position = i + nums[i];
        }
        if (max_position >= numsSize - 1) {
            return true;
        }
    }
    return false;
}

bool canJump_v2(int* nums, int numsSize) {
    if (numsSize <= 1) {
        return true;
    }
    // 至少有两个位置，且第一个位置可跳步数为0
    if (nums[0] == 0) {
        return false;
    }
    // 从倒数第二个位置开始逆序遍历，挨个判断当前位置能否到达终点
    int least_step = 1; // 对于当前位置来说，至少需要跳几步才能到达终点
    for (int i = numsSize - 2; i >= 0; --i) {
        // 如果当前位置可跳步数满足least_step，则可将当前位置作为新的“终点”，并重置least_step
        //      nums[i] >= least_step时，当前位置可以尝试先到“新终点”再到达结尾，或者越过它再到达结尾；而已知“新终点”是一定能够到达结尾的，因此越过它能否到达结尾无关紧要
        //      nums[i] < least_step时，当前位置无法到达“终点”，后续位置需要在现有least_step上跳过该位置，因此least_step++
        if (nums[i] >= least_step) {
            least_step = 1;
        } else {
            least_step++;
        }
    }
    // 到达初始位置，
    return least_step == 1;
}

bool canJump_v1(int* nums, int numsSize) {
    if (numsSize <= 0) {
        return false;
    }
    if (numsSize == 1) {
        return true;
    }
    if (nums[0] == 0) {
        return false;
    }
    for (int i = numsSize - 2; i >= 0 ; --i) {
        if (nums[i] == 0) {
            int p = i - 1;
            while (p >= 0 && nums[p] <= i - p) {
                p--;
            }
            if (p == -1) {
                return false;
            }
        }
    }
    return true;
}

240. 搜索二维矩阵 II

// 从右上角出发，往左变小，往下变大，可类比二叉搜索树
bool searchMatrix(int **matrix, int matrixSize, int *matrixColSize, int target) {
    int m = matrixSize, n = *matrixColSize;
    if (matrix[0][0] == target) {
        return true;
    }

    int i = 0, j = n - 1;
    while (i < m && j >= 0) {
        if (matrix[i][j] == target) {
            return true;
        }
        if (matrix[i][j] < target) {
            i++; // 往下
        } else {
            j--; // 往左
        }
    }
    return false;
}

bool searchMatrix_not_pass(int **matrix, int matrixSize, int *matrixColSize, int target) {
    int m = matrixSize, n = *matrixColSize;
    if (matrix[0][0] == target) {
        return true;
    }

    int i = 0, j = 0;
    // 右边<target，向右移位，停止：右边>=target，或者到达末尾
    while (j + 1 < n && matrix[i][j + 1] < target) j++;
    if (j + 1 < n && matrix[i][j + 1] == target) {
        return true;
    }
    // 下边<target，向下移位
    while (i + 1 < m && matrix[i + 1][j] < target) i++;
    if (i + 1 < m && matrix[i + 1][j] == target) {
        return true;
    }

    i = j = 0;
    while (i + 1 < m && matrix[i + 1][j] < target) i++;
    if (i + 1 < m && matrix[i + 1][j] == target) {
        return true;
    }
    while (j + 1 < n && matrix[i][j + 1] < target) j++;
    if (j + 1 < n && matrix[i][j + 1] == target) {
        return true;
    }

    return false;
}

LCR 186. 文物朝代判断

bool checkDynasty(int *places, int placesSize) {
    int max = -1, min = 14, exist[14] = {0};
    for (int i = 0; i < placesSize; ++i) {
        int x = places[i];
        if (x == 0) {
            continue;
        }
        if(exist[x] == 1) {
            return false;
        } else {
            exist[x] = 1;
        }
        max = x > max ? x : max;
        min = x < min ? x : min;
    }
    if (max == -1 && min == 14) {
        return true;
    }
    return max - min <= 4;
}

int main() {
    int arr[] = {0,0,2,2,5};
    checkDynasty(arr, 5);
}

面试题 01.05. 一次编辑

size_t my_strlen(char *str) {
    const char *p = str;
    while (*str++);
    return str - p - 1;
}

size_t math_abs(size_t a, size_t b) {
    return a > b ? a - b : b - a;
}

bool oneEditAway(char *first, char *second) {
    size_t l1 = my_strlen(first), l2 = my_strlen(second);
    size_t gap = math_abs(l1, l2);
    // 两者长度之差超过1，一次编辑无法实现
    if (gap > 1) {
        return false;
    }
    // 两者长度相等，要么相同，要么有一个字符不同
    int diff_cnt = 0;
    if (gap == 0) {
        for (int i = 0; i < l1; ++i) {
            if (first[i] != second[i]) {
                diff_cnt++;
            }
        }
        return diff_cnt <= 1;
    }
    // 两者长度相差1
    int i = 0, j = 0;
    while (i < l1 && j < l2) {
        if (first[i] == second[j]) {
            i++;
            j++;
        } else {
            diff_cnt++;
            if (l1 > l2) {
                i++;
            } else {
                j++;
            }
        }
    }
    return diff_cnt <= 1;
}

bool oneEditAway_v1(char *first, char *second) {
    size_t l1 = my_strlen(first);
    size_t l2 = my_strlen(second);
    if (l1 == 0 || l2 == 0) {
        return l1 == l2 || l1 - l2 == 1 || l1 - l2 == -1;
    }
    if ((l1 > l2 && l1 - l2 > 1) || (l2 > l1 && l2 - l1 > 1)) {
        return false;
    }

    bool diff = false;
    int i = 0, j = 0;
    while (i < l1 && j < l2) {
        if (first[i] != second[j]) {
            if (diff) {
                return false;
            }
            diff = true;

            if (l1 < l2) {
                j++;
            } else if (l1 > l2) {
                i++;
            } else {
                i++;
                j++;
            }
        } else {
            i++;
            j++;
        }
    }
    return true;
}

int main() {
    bool b = oneEditAway("islander", "slander");
    return 0;
}

面试题 01.08. 零矩阵

void setZeroes(int** matrix, int matrixSize, int* matrixColSize){
    int m = matrixSize;
    int n = *matrixColSize;
    int row[m], col[n];
    memset(row, 0, sizeof(row));
    memset(col, 0, sizeof(col));

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (matrix[i][j] == 0) {
                row[i] = 1;
                col[j] = 1;
            }
        }
    }
    for (int i = 0; i < m; ++i) {
        if (row[i] == 1) {
            for (int j = 0; j < n; ++j) {
                matrix[i][j] = 0;
            }
        }
    }
    for (int j = 0; j < n; ++j) {
        if (col[j] == 1) {
            for (int i = 0; i < m; ++i) {
                matrix[i][j] = 0;
            }
        }
    }
}

void setZeroes_v1(int** matrix, int matrixSize, int* matrixColSize){
    bool row[matrixSize], col[*matrixColSize];
    for (int i = 0; i < matrixSize; ++i) {
        row[i] = false;
    }
    for (int i = 0; i < *matrixColSize; ++i) {
        col[i] = false;
    }

    for (int i = 0; i < matrixSize; ++i) {
        for (int j = 0; j < *matrixColSize; ++j) {
            if (matrix[i][j] == 0) {
                row[i] = true;
                col[j] = true;
            }
        }
    }
    for (int i = 0; i < matrixSize; ++i) {
        if (row[i] == true) {
            for (int j = 0; j < *matrixColSize; ++j) {
                matrix[i][j] = 0;
            }
        }
    }
    for (int j = 0; j < *matrixColSize; ++j) {
        if (col[j] == true) {
            for (int i = 0; i < matrixSize; ++i) {
                matrix[i][j] = 0;
            }
        }
    }
}

面试题 16.04. 井字游戏

#include "stdlib.h"
#include "stdbool.h"
#define PENDING "Pending"
#define DRAW "Draw"

char* tictactoe(char** board, int boardSize){
    // 1x1
    if (boardSize == 1) {
        if (board[0][0] == ' ') {
            return PENDING;
        }
        return board[0];
    }

    char *res = malloc(sizeof(char) * 2);
    res[1] = '\0';
    bool blank = false;
    // 检查是否存在某一行的棋子是一样的
    for (int i = 0; i < boardSize; ++i) {
        char ch = board[i][0];
        if (ch == ' ') {
            blank = true;
            continue;
        }
        int j = 1;
        while (j < boardSize && board[i][j] == ch) {
            j++;
        }
        if (j == boardSize) {
            res[0] = ch;
            return res;
        }
    }
    // 检查是否存在某一列的棋子是一样的
    for (int j = 0; j < boardSize; ++j) {
        char ch = board[0][j];
        if (ch == ' ') {
            blank = true;
            continue;
        }
        int i = 1;
        while (i < boardSize && board[i][j] == ch) {
            i++;
        }
        if (i == boardSize) {
            res[0] = ch;
            return res;
        }
    }
    // 检查对角线
    char ch = board[0][0];
    if (ch == ' ') {
        blank = true;
    } else {
        int i = 1;
        while (i < boardSize && board[i][i] == ch) {
            i++;
        }
        if (i == boardSize) {
            res[0] = ch;
            return res;
        }
    }

    ch = board[0][boardSize - 1];
    if (ch == ' ') {
        blank = true;
    } else {
        int i = 1;
        while (i < boardSize && board[i][boardSize - 1 - i] == ch) {
            i++;
        }
        if (i == boardSize) {
            res[0] = ch;
            return res;
        }
    }

    if (blank) {
        return PENDING;
    }
    return DRAW;
}

面试题 16.11. 跳水板

int* divingBoard(int shorter, int longer, int k, int* returnSize){
    if (k == 0) {
        *returnSize = 0;
        return NULL;
    }
    if (shorter == longer) {
        *returnSize = 1;
        int *res = malloc(sizeof(int));
        res[0] = shorter * k;
        return res;
    }

    int len = *returnSize = k + 1;
    int *res = malloc(sizeof(int) * len);
    for (int i = 0; i <= k; ++i) {
        res[i] = longer * i + shorter * (k - i);
    }
    return res;
}

面试题 16.15. 珠玑妙算

int *masterMind(char *solution, char *guess, int *returnSize) {
    *returnSize = 2;
    int hit = 0, pseudo_hit = 0;
    bool solution_used[4] = {false};
    bool guess_used[4] = {false};

    // 判断对位是否相同
    for (int i = 0; i < 4; ++i) {
        if (solution[i] == guess[i]) {
            hit++;
            solution_used[i] = guess_used[i] = true;
        }
    }

    // 判断错位是否相同
    for (int i = 0; i < 4; ++i) {
        if (guess_used[i] == true) {
            continue;
        }
        char ch = guess[i];
        for (int j = 0; j < 4; ++j) {
            if (solution_used[j] == false && solution[j] == ch) {
                pseudo_hit++;
                guess_used[i] = solution_used[j] = true;
                break;
            }
        }
    }

    int *res = malloc(sizeof(int) * 2);
    res[0] = hit;
    res[1] = pseudo_hit;
    return res;
}

int main() {
    char *solution = "RGRB";
    char *guess = "BBBY";
    int *size = malloc(sizeof(int));
    masterMind(solution, guess, size);
}

链表

链表定义

//
// Created by 86157 on 2024/9/14.
//

#ifndef LEETCODE_LINKEDLIST_H
#define LEETCODE_LINKEDLIST_H

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

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode *createList(const int *arr, int length) {
    struct ListNode *head = NULL;
    struct ListNode *pre = NULL;
    struct ListNode *p = NULL;
    for (int i = 0; i < length; ++i) {
        p = malloc(sizeof(struct ListNode));
        p->val = arr[i];
        p->next = NULL;
        if (i == 0) {
            head = p;
        }
        if (pre != NULL) {
            pre->next = p;
        }
        pre = p;
    }
    return head;
}

void printList(struct ListNode *head) {
    struct ListNode *p = head;
    while (p != NULL) {
        printf("%d ", p->val);
        p = p->next;
    }
    printf("\n");
}

#endif //LEETCODE_LINKEDLIST_H

2. 两数相加

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    if (l1 == NULL || l2 == NULL) {
        return l1 == NULL ? l2 : l1;
    }
    struct ListNode *virtual_head = malloc(sizeof(struct ListNode));
    struct ListNode *p = virtual_head;
    int carry = 0;
    while (l1 != NULL && l2 != NULL) {
        int sum = l1->val + l2->val + carry;
        p->next = malloc(sizeof(struct ListNode));
        p->next->val = sum % 10;
        carry = sum / 10;

        p = p->next;
        l1 = l1->next;
        l2 = l2->next;
    }

    if (l1 != NULL || l2 != NULL) {
        struct ListNode *remain = l1 == NULL ? l2 : l1;
        while (remain != NULL) {
            int sum = remain->val + carry;
            p->next = malloc(sizeof(struct ListNode));
            p->next->val = sum % 10;
            carry = sum / 10;

            p = p->next;
            remain = remain->next;
        }
    }

    if (carry == 1) {
        p->next = malloc(sizeof(struct ListNode));
        p->next->val = 1;
        p = p->next;
    }
    p->next = NULL;
    return virtual_head->next;
}

int main() {
    //[2,4,3]
    struct ListNode *l1 = malloc(sizeof(struct ListNode));
    l1->val = 2;
    l1->next = malloc(sizeof(struct ListNode));
    l1->next->val = 4;
    l1->next->next = malloc(sizeof(struct ListNode));
    l1->next->next->val = 3;
    l1->next->next->next = NULL;
    //[5,6,4]
    struct ListNode *l2 = malloc(sizeof(struct ListNode));
    l2->val = 5;
    l2->next = malloc(sizeof(struct ListNode));
    l2->next->val = 6;
    l2->next->next = malloc(sizeof(struct ListNode));
    l2->next->next->val = 4;
    l2->next->next->next = NULL;
    addTwoNumbers(l1, l2);
}

19. 删除链表的倒数第 N 个结点

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    if (head == NULL) {
        return NULL;
    }
    struct ListNode *p1, *p2;
    p1 = p2 = head;
    n = n - 1;
    while (n-- > 0) {
        p2 = p2->next;
        if (p2 == NULL) {
            return head;
        }
    }

    struct ListNode *pre = NULL;
    while (p2->next != NULL) {
        pre = p1;
        p1 = p1->next;
        p2 = p2->next;
    }
    if (pre == NULL) {
        struct ListNode *tmp = head->next;
        head->next = NULL;
        free(head);
        return tmp;
    }
    pre->next = p1->next;
    p1->next = NULL;
    free(p1);
    return head;
}

25. K 个一组翻转链表

void reverseKNodes(struct ListNode *p, int k);

struct ListNode *reverseKGroup_v2(struct ListNode *head, int k) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    struct ListNode *dummy_head = malloc(sizeof(struct ListNode));
    struct ListNode *tail = dummy_head;
    struct ListNode *left, *right;
    left = right = head;
    while (left != NULL) {
        int count = 1;
        while (right->next != NULL) {
            right = right->next;
            count++;
            if (count == k) {
                break;
            }
        }

        if (count == k) {
            struct ListNode* tmp = right->next;
            reverseKNodes(left, k);
            tail->next = right;
            tail = left;
            tail->next = NULL;
            left = right = tmp;
        } else {
            tail->next = left;
            return dummy_head->next;
        }
    }
    return dummy_head->next;
}

struct ListNode *reverseKGroup(struct ListNode *head, int k) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    struct ListNode *new_head = NULL;
    struct ListNode *left, *right, *pre;
    left = right = head;
    pre = NULL;
    int count = 1;
    while (right != NULL) {
        if (count % k != 0) {
            right = right->next;
            count++;
        } else {
            struct ListNode *tmp = right->next;
            reverseKNodes(left, k);
            if (pre == NULL) {
                new_head = right;
            } else {
                pre->next = right;
            }
            left->next = tmp;
            pre = left;
            left = right = tmp;
            count++;
        }
    }
    return new_head;
}

void reverseKNodes(struct ListNode *p, int k) {
    struct ListNode *pre, *tmp;
    pre = NULL;
    while (k-- > 0) {
        tmp = p->next;
        p->next = pre;
        pre = p;
        p = tmp;
    }
}

int main() {
    struct ListNode *head = malloc(sizeof(struct ListNode));
    head->val = 1;
    head->next = malloc(sizeof(struct ListNode));

    head->next->val = 2;
    head->next->next = malloc(sizeof(struct ListNode));

    head->next->next->val = 3;
    head->next->next->next = malloc(sizeof(struct ListNode));

    head->next->next->next->val = 4;
    head->next->next->next->next = malloc(sizeof(struct ListNode));

    head->next->next->next->next->val = 5;
    head->next->next->next->next->next = NULL;

    reverseKGroup_v2(head, 2);
}

83. 删除排序链表中的重复元素

struct ListNode* deleteDuplicates(struct ListNode* head) {
    if (head == NULL) {
        return NULL;
    }
    struct ListNode *p = head;
    while (p != NULL) {
        while (p->next != NULL && p->next->val == p->val) {
            struct ListNode *next = p->next;
            p->next = next->next;
            next->next = NULL;
            free(next);
        }
        p = p->next;
    }
    return head;
}

141. 环形链表

bool hasCycle(struct ListNode *head) {
    if (head == NULL || head->next == NULL) {
        return false;
    }
    if (head->next == head) {
        return true;
    }
    struct ListNode *slow, *fast;
    slow = fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            return true;
        }
    }
    return false;
}

160. 相交链表

struct ListNode *getIntersectionNode_v2(struct ListNode *headA, struct ListNode *headB) {
    if (headA == NULL || headB == NULL) {
        return headA == NULL ? headB : headA;
    }
    struct ListNode *p1 = headA, *p2 = headB;
    int l1 = 0, l2 = 0;
    while (p1 != NULL) {
        l1++;
        p1 = p1->next;
    }
    while (p2 != NULL) {
        l2++;
        p2 = p2->next;
    }

    p1 = headA;
    p2 = headB;
    if (l1 > l2) {
        int n = l1 - l2;
        while (n-- > 0) {
            p1 = p1->next;
        }
    } else {
        int n = l2 - l1;
        while (n-- > 0) {
            p2 = p2->next;
        }
    }

    while (p1 != NULL && p2 != NULL) {
        if (p1 == p2) {
            return p1;
        }
        p1 = p1->next;
        p2 = p2->next;
    }
    return NULL;
}

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if (headA == NULL || headB == NULL) {
        return headA == NULL ? headB : headA;
    }
    struct ListNode *p1, *p2;
    p1 = headA;
    p2 = headB;
    while (p1 != NULL && p2 != NULL) {
        p1 = p1->next;
        p2 = p2->next;
    }
    if (p1 == NULL) {
        p1 = headB;
    }
    if (p2 == NULL) {
        p2 = headA;
    }
    while (p1 != NULL && p2 != NULL) {
        p1 = p1->next;
        p2 = p2->next;
    }
    if (p1 == NULL) {
        p1 = headB;
    }
    if (p2 == NULL) {
        p2 = headA;
    }

    while (p1 != NULL && p2 != NULL) {
        if (p1 == p2) {
            return p1;
        }
        p1 = p1->next;
        p2 = p2->next;
    }
    return NULL;
}

203. 移除链表元素

struct ListNode *removeElements(struct ListNode *head, int val) {
    if (head == NULL) {
        return head;
    }
    struct ListNode *new_head = malloc(sizeof(struct ListNode));
    struct ListNode *pre, *p;
    pre = new_head;
    p = head;
    new_head->next = head;
    while (p != NULL) {
        if (p->val != val) {
            pre = p;
            p = p->next;
            continue;
        }
        pre->next = p->next;
        p->next = NULL;
        free(p);
        p = pre->next;
    }
    return new_head->next;
}

206. 反转链表

struct ListNode* reverseList(struct ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    struct ListNode *pre = NULL;
    struct ListNode *p = head;
    struct ListNode *latter;
    while (p != NULL) {
        latter = p->next;
        p->next = pre;
        pre = p;
        p = latter;
    }
    return pre;
}

234. 回文链表

struct ListNode *find_middle_node(struct ListNode *head);

struct ListNode *reverseList(struct ListNode *head);

bool isPalindrome_v2(struct ListNode* head) {
    if(head == NULL || head->next == NULL) {
        return true;
    }
    struct ListNode *mid_node = find_middle_node(head);
    struct ListNode *right_half_head = reverseList(mid_node);

    struct ListNode *p1, *p2;
    p1 = head;
    p2 = right_half_head;
    while (p2 != NULL) {
        if (p1->val != p2->val) {
            return false;
        }
        p1 = p1->next;
        p2 = p2->next;
    }
    return true;
}

struct ListNode *find_middle_node(struct ListNode *head) {
    struct ListNode *slow, *fast;
    slow = fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

struct ListNode *reverseList(struct ListNode *head) {
    struct ListNode *pre, *p, *tmp;
    pre = NULL;
    p = head;
    while (p != NULL) {
        tmp = p->next;
        p->next = pre;
        pre = p;
        p = tmp;
    }
    return pre;
}

bool isPalindrome(struct ListNode* head) {
    if(head == NULL || head->next == NULL) {
        return true;
    }
    struct ListNode *p, *fast;
    p = fast = head;
    struct ListNode *pre, *tmp;
    pre = NULL;
    while (fast != NULL && fast->next != NULL) {
        fast = fast->next->next;
        tmp = p->next;
        p->next = pre;
        pre = p;
        p = tmp;
    }
    struct ListNode *p1, *p2;
    p1 = pre;
    p2 = fast == NULL ? p : p->next;
    while (p1 != NULL && p2 != NULL) {
        if (p1->val != p2->val) {
            return false;
        }
        p1 = p1->next;
        p2 = p2->next;
    }
    return true;
}

int main() {
    struct ListNode *head = malloc(sizeof(struct ListNode));
    head->val = 1;
    head->next = malloc(sizeof(struct ListNode));

    head->next->val = 2;
    head->next->next = malloc(sizeof(struct ListNode));

    head->next->next->val = 2;
    head->next->next->next = malloc(sizeof(struct ListNode));

    head->next->next->next->val = 1;
    head->next->next->next->next = NULL;

    isPalindrome_v2(head);
}

328. 奇偶链表

struct ListNode *oddEvenList_v2(struct ListNode *head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    struct ListNode *odd_head = malloc(sizeof(struct ListNode));
    struct ListNode *odd_tail = odd_head;
    struct ListNode *even_head = malloc(sizeof(struct ListNode));
    struct ListNode *even_tail = even_head;

    struct ListNode *p = head;
    int count = 1;
    while (p != NULL) {
        struct ListNode *tmp = p->next;
        p->next = NULL;
        if (count % 2 == 1) {
            odd_tail->next = p;
            odd_tail = p;
        } else {
            even_tail->next = p;
            even_tail = p;
        }
        p = tmp;
        count++;
    }

    odd_tail->next = even_head->next;
    return odd_head->next;
}

struct ListNode *oddEvenList(struct ListNode *head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    struct ListNode *virtual_head = malloc(sizeof(struct ListNode));
    struct ListNode *virtual_tail = virtual_head;
    struct ListNode *p, *pre;
    p = head;
    pre = NULL;
    int k = 1;
    while (p != NULL) {
        if (k % 2 == 1) {
            pre = p;
            p = p->next;
        } else {
            pre->next = p->next;
            p->next = NULL;
            virtual_tail->next = p;
            virtual_tail = p;
            p = pre->next;
        }
        k++;
    }
    pre->next = virtual_head->next;
    return head;
}

876. 链表的中间结点

struct ListNode* middleNode(struct ListNode* head) {
    if (head == NULL) {
        return NULL;
    }
    struct ListNode *slow, *fast;
    slow = fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

LCR 142. 训练计划 IV

struct ListNode* trainningPlan(struct ListNode* l1, struct ListNode* l2) {
    if (l1 == NULL) {
        return l2;
    }
    if (l2 == NULL) {
        return l1;
    }
    struct ListNode *virtual_head = malloc(sizeof(struct ListNode));
    struct ListNode *p = virtual_head;
    while (l1 != NULL && l2 != NULL) {
        if (l1->val < l2->val) {
            p->next = l1;
            l1 = l1->next;
            p = p->next;
        } else {
            p->next = l2;
            l2 = l2->next;
            p = p->next;
        }
    }
    struct ListNode *remaining = l1 == NULL ? l2 : l1;
    p->next = remaining;
    return virtual_head->next;
}

栈和队列

栈典型应用

155. 最小栈

// https://leetcode.cn/problems/min-stack/
// Created by 86157 on 2024/9/16.
//
#include "../stack.h"

typedef struct {
    Stack *dataStack;
    Stack *minStack;
} MinStack;


MinStack* minStackCreate() {
    MinStack *stack = malloc(sizeof(MinStack));
    stack->dataStack = stackCreate();
    stack->minStack = stackCreate();
    return stack;
}

void minStackPush(MinStack* obj, int val) {
    stackPush(obj->dataStack, val);
    if (stackEmpty(obj->minStack)) {
        stackPush(obj->minStack, val);
    } else {
        int min = stackPeek(obj->minStack);
        min = val < min ? val : min;
        stackPush(obj->minStack, min);
    }
}

void minStackPop(MinStack* obj) {
    if (stackEmpty(obj->dataStack)) {
        return;
    }
    stackPop(obj->dataStack);
    stackPop(obj->minStack);
}

int minStackTop(MinStack* obj) {
    if (stackEmpty(obj->dataStack)) {
        return -1;
    }
    return stackPeek(obj->dataStack);
}

int minStackGetMin(MinStack* obj) {
    if (stackEmpty(obj->minStack)) {
        return -1;
    }
    return stackPeek(obj->minStack);
}

void minStackFree(MinStack* obj) {
    if (obj != NULL) {
        stackFree(obj->dataStack);
        stackFree(obj->minStack);
        free(obj);
    }
}

225. 用队列实现栈

// https://leetcode.cn/problems/implement-stack-using-queues/
// Created by 86157 on 2024/9/16.
//

#include "../queue.h"

typedef struct {
    Queue *masterQueue;
    Queue *slaveQueue;
} MyStack;


MyStack* myStackCreate() {
    MyStack *stack = malloc(sizeof(MyStack));
    stack->masterQueue = queueCreate();
    stack->slaveQueue = queueCreate();
    return stack;
}

bool myStackEmpty(MyStack* obj) {
    return queueEmpty(obj->masterQueue);
}

void myStackPush(MyStack* obj, int x) {
    if (queueEmpty(obj->masterQueue)) {
        queueAppendTail(obj->masterQueue, x);
        return;
    }
    while (!queueEmpty(obj->masterQueue)) {
        queueAppendTail(obj->slaveQueue, queuePopHead(obj->masterQueue));
    }
    queueAppendTail(obj->masterQueue, x);
    while (!queueEmpty(obj->slaveQueue)) {
        queueAppendTail(obj->masterQueue, queuePopHead(obj->slaveQueue));
    }
}

int myStackPop(MyStack* obj) {
    if (queueEmpty(obj->masterQueue)) {
        return -1;
    }
    return queuePopHead(obj->masterQueue);
}

int myStackTop(MyStack* obj) {
    if (queueEmpty(obj->masterQueue)) {
        return -1;
    }
    return queuePeekHead(obj->masterQueue);
}

void myStackFree(MyStack* obj) {
    if (obj != NULL) {
        queueDestroy(obj->masterQueue);
        queueDestroy(obj->slaveQueue);
        free(obj);
    }
}

int main() {
    MyStack *stack = myStackCreate();
    myStackPush(stack, 1);
    myStackPush(stack, 2);
    myStackTop(stack);
    myStackPop(stack);
    myStackEmpty(stack);
}

// https://leetcode.cn/problems/implement-stack-using-queues/
// Created by 86157 on 2024/9/16.
//

#include "../queue.h"

typedef struct {
    Queue *queue;
    int cnt;
} MyStack;


MyStack* myStackCreate() {
    MyStack *stack = malloc(sizeof(MyStack));
    stack->queue = queueCreate();
    stack->cnt = 0;
    return stack;
}

bool myStackEmpty(MyStack* obj) {
    return queueEmpty(obj->queue);
}

void myStackPush(MyStack* obj, int x) {
    queueAppendTail(obj->queue, x);
    obj->cnt++;
    // 将前n-1个倒腾到队尾
    for (int i = 1; i < obj->cnt; ++i) {
        queueAppendTail(obj->queue, queuePopHead(obj->queue));
    }
}

int myStackPop(MyStack* obj) {
    if (obj->cnt == 0) {
        return -1;
    }
    int val = queuePopHead(obj->queue);
    obj->cnt--;
    return val;
}

int myStackTop(MyStack* obj) {
    if (obj->cnt == 0) {
        return -1;
    }
    return queuePeekHead(obj->queue);
}

void myStackFree(MyStack* obj) {
    if (obj != NULL) {
        queueDestroy(obj->queue);
        free(obj);
    }
}

int main() {
    MyStack *stack = myStackCreate();
    myStackPush(stack, 1);
    myStackPush(stack, 2);
    myStackTop(stack);
    myStackPop(stack);
    myStackEmpty(stack);
}

面试题 16.26. 计算器

// https://leetcode.cn/problems/calculator-lcci/description/
// Created by 86157 on 2024/9/17.
//

#include <stdbool.h>
#include <stdio.h>
#include "../stack.h"

bool isDigit(char ch) {
    return ch >= '0' && ch <= '9';
}

bool priorThan(char op1, char op2) {
    return (op1 == '*' || op1 == '/') && (op2 == '+' || op2 == '-') ||
            (op1 != '(' && op2 == '(');
}

int cal(int num1, int num2, char op) {
    switch (op) {
        case '+':
            return num1 + num2;
        case '-':
            return num1 - num2;
        case '*':
            return num1 * num2;
        case '/':
            return num1 / num2;
        default:
            return -1;
    }
}

void fetchAndCal(Stack *nums, Stack *ops) {
    char op = (char) stackPop(ops);
    int num2 = stackPop(nums);
    int num1 = stackPop(nums);
    int result = cal(num1, num2, op);
    stackPush(nums, result);
}

int calculate(char *s) {
    Stack *nums = stackCreate();
    Stack *ops = stackCreate();
    while (*s) {
        if (*s == ' ') {
            s++;
        } else if (isDigit(*s)) {
            int num = 0;
            while (isDigit(*s)) {
                num = num * 10 + (*s - '0');
                s++;
            }
            stackPush(nums, num);
        } else {
            // 运算符
            // 遇到")"，将运算符栈中"("之前的运算符都计算掉
            if (*s == '(' || *s == ')') {
                if (*s == '(') {
                    stackPush(ops, *s);
                } else {
                    while (stackPeek(ops) != '(') {
                        fetchAndCal(nums, ops);
                    }
                    stackPop(ops);
                }
            }
            // 运算符栈为空，或遇到的运算符优先级较高，则可以压栈，这样出栈时该运算符先算
            else if (stackEmpty(ops) ||
                priorThan(*s, (char) stackPeek(ops))) {
                stackPush(ops, *s);
            } else {
                // 遇到的运算符优先级相等或更低，将栈里高优先级和等优先级的运算符消除掉
                while (!stackEmpty(ops) &&
                       !priorThan(*s, (char) stackPeek(ops))) {
                    fetchAndCal(nums, ops);
                }
                stackPush(ops, *s);
            }
            s++;
        }
    }

    while (!stackEmpty(ops)) {
        // 还有运算符没算
        fetchAndCal(nums, ops);
    }
    return stackPeek(nums);
}

int main() {
    char *s = "3*(3+4*1-2)+3*2-5";
    int result = calculate(s);
    printf("%d", result);
}

LCR 125. 图书整理 II

// https://leetcode.cn/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/description/
// Created by 86157 on 2024/9/15.
//
#include "../stack.h"
#include "stdlib.h"

typedef struct {
    Stack *masterStack;
    Stack *slaveStack;
} CQueue;


CQueue* cQueueCreate() {
    CQueue *queue = malloc(sizeof(CQueue));
    queue->masterStack = stackCreate();
    queue->slaveStack = stackCreate();
    return queue;
}

void cQueueAppendTail(CQueue* obj, int value) {
    Stack *main = obj->masterStack;
    Stack *help = obj->slaveStack;
    if (stackEmpty(main)) {
        stackPush(main, value);
        return;
    }
    while (!stackEmpty(main)) {
        stackPush(help, stackPop(main));
    }
    stackPush(main, value);
    while (!stackEmpty(help)) {
        stackPush(main, stackPop(help));
    }
}

int cQueueDeleteHead(CQueue* obj) {
    Stack *main = obj->masterStack;
    if (stackEmpty(main)) {
        return -1;
    }
    return stackPop(main);
}

void cQueueFree(CQueue* obj) {
    stackFree(obj->masterStack);
    stackFree(obj->slaveStack);
    free(obj);
}

// https://leetcode.cn/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/description/
// Created by 86157 on 2024/9/15.
//
#include "../stack.h"
#include "stdlib.h"

typedef struct {
    // 用来保存入队的元素
    Stack *pushStack;
    // 用来保存可以直接出队的元素
    Stack *popStack;
} CQueue;


CQueue* cQueueCreate() {
    CQueue *queue = malloc(sizeof(CQueue));
    queue->pushStack = stackCreate();
    queue->popStack = stackCreate();
    return queue;
}

// 入队，压栈pushStack
void cQueueAppendTail(CQueue* obj, int value) {
    stackPush(obj->pushStack, value);
}

// 出队，如果popStack不为空，则直接出队，否则将pushStack倒腾到popStack再出队
// 均摊复杂度O(1)
int cQueueDeleteHead(CQueue* obj) {
    if (!stackEmpty(obj->popStack)) {
        return stackPop(obj->popStack);
    }
    while (!stackEmpty(obj->pushStack)) {
        stackPush(obj->popStack, stackPop(obj->pushStack));
    }
    if (stackEmpty(obj->popStack)) {
        return -1;
    }
    return stackPop(obj->popStack);
}

void cQueueFree(CQueue* obj) {
    stackFree(obj->pushStack);
    stackFree(obj->popStack);
    free(obj);
}

LCR 148. 验证图书取出顺序

// https://leetcode.cn/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/description/
// Created by 86157 on 2024/9/17.
//

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

bool validateBookSequences(int* putIn, int putInSize, int* takeOut, int takeOutSize) {
    if (putIn == NULL || takeOut == NULL || putInSize != takeOutSize) {
        return false;
    }
    if (putInSize == 0 && takeOutSize == 0) {
        return true;
    }
    int size = putInSize;
    int *stack = malloc(sizeof(int) * size);
    int cnt = 0;
    // 尝试按照putIn的顺序入栈，每次入栈后循环判断能否按照takeOut出栈
    for (int i = 0; i < size; ++i) {
        stack[cnt++] = putIn[i];
        while (cnt > 0 && stack[cnt - 1] == *takeOut) {
            cnt--;
            takeOut++;
        }
    }
    // 对应takeOut剩余元素进行出栈
    while (cnt > 0 && stack[cnt - 1] == *takeOut) {
        cnt--;
        takeOut++;
    }
    free(stack);
    return cnt == 0;
}

面试题 03.01. 三合一

// https://leetcode.cn/problems/three-in-one-lcci/


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

typedef struct {
    int stackSize;
    int *arr;
    int cnt1, cnt2, cnt3;
} TripleInOne;


TripleInOne* tripleInOneCreate(int stackSize) {
    TripleInOne *triple = malloc(sizeof(TripleInOne));
    triple->stackSize = stackSize;
    triple->arr = malloc(sizeof(int) * stackSize * 3);
    triple->cnt1 = triple->cnt2 = triple->cnt3 = 0;
    return triple;
}

int *getStackCnt(TripleInOne* obj, int stackNum) {
    switch (stackNum) {
        case 0:
            return &obj->cnt1;
        case 1:
            return &obj->cnt2;
        case 2:
            return &obj->cnt3;
        default:
            return NULL;
    }
}

bool tripleInOneIsEmpty(TripleInOne* obj, int stackNum) {
    int *cnt = getStackCnt(obj, stackNum);
    return *cnt == 0;
}

bool tripleInOneIsFull(TripleInOne* obj, int stackNum) {
    int *cnt = getStackCnt(obj, stackNum);
    return *cnt == obj->stackSize;
}

void tripleInOneFree(TripleInOne* obj) {
    if (obj == NULL) {
        return;
    }
    free(obj->arr);
    free(obj);
}

void tripleInOnePush(TripleInOne* obj, int stackNum, int value) {
    if (tripleInOneIsFull(obj, stackNum)) {
        return;
    }
    int *cnt = getStackCnt(obj, stackNum);
    obj->arr[*cnt + stackNum * obj->stackSize] = value;
    (*cnt)++;
}

int tripleInOnePop(TripleInOne* obj, int stackNum) {
    if (tripleInOneIsEmpty(obj, stackNum)) {
        return -1;
    }
    int *cnt = getStackCnt(obj, stackNum);
    int val = obj->arr[*cnt - 1 + stackNum * obj->stackSize];
    (*cnt)--;
    return val;
}

int tripleInOnePeek(TripleInOne* obj, int stackNum) {
    if (tripleInOneIsEmpty(obj, stackNum)) {
        return -1;
    }
    int *cnt = getStackCnt(obj, stackNum);
    return obj->arr[*cnt - 1 + stackNum * obj->stackSize];
}

// https://leetcode.cn/problems/three-in-one-lcci/


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

typedef struct {
    int capacity;
    int *arr;
    int *top;
} TripleInOne;


TripleInOne *tripleInOneCreate(int stackSize) {
    TripleInOne *triple = malloc(sizeof(TripleInOne));
    int capacity = stackSize * 3;
    triple->capacity = capacity;
    triple->arr = malloc(sizeof(int) * capacity);
    triple->top = malloc(sizeof(int) * 3);
    triple->top[0] = -3;
    triple->top[1] = -2;
    triple->top[2] = -1;
    return triple;
}

bool tripleInOneIsEmpty(TripleInOne *obj, int stackNum) {
    return obj->top[stackNum] < 0;
}

bool tripleInOneIsFull(TripleInOne *obj, int stackNum) {
    return (obj->top[stackNum] + 3) >= obj->capacity;
}

void tripleInOneFree(TripleInOne *obj) {
    if (obj) {
        free(obj->arr);
        free(obj->top);
        free(obj);
    }
}

void tripleInOnePush(TripleInOne *obj, int stackNum, int value) {
    if (tripleInOneIsFull(obj, stackNum)) {
        return;
    }
    obj->top[stackNum] += 3;
    obj->arr[obj->top[stackNum]] = value;
}

int tripleInOnePop(TripleInOne *obj, int stackNum) {
    if (tripleInOneIsEmpty(obj, stackNum)) {
        return -1;
    }
    int val = obj->arr[obj->top[stackNum]];
    obj->top[stackNum] -= 3;
    return val;
}

int tripleInOnePeek(TripleInOne *obj, int stackNum) {
    if (tripleInOneIsEmpty(obj, stackNum)) {
        return -1;
    }
    return obj->arr[obj->top[stackNum]];
}

int main() {
    TripleInOne *triple = tripleInOneCreate(1);
    tripleInOnePush(triple, 0, 1);
    tripleInOnePush(triple, 0, 2);
    tripleInOnePop(triple, 0);
    tripleInOnePop(triple, 0);
    tripleInOnePop(triple, 0);
    tripleInOneIsEmpty(triple, 0);
}

面试题 16.26. 计算器

// https://leetcode.cn/problems/calculator-lcci/description/
// Created by 86157 on 2024/9/17.
// 遇到一个运算符，如果不知道后一个运算符是否更优先计算，那么当前运算符需要先入栈；如果栈顶运算符不为空，且当前遇到的运算符
// 没有较高的优先级，那么可以将栈中较高或相等优先级的运算符弹出并计算

#include <stdbool.h>
#include <stdio.h>
#include "../stack.h"

bool isDigit(char ch) {
    return ch >= '0' && ch <= '9';
}

bool priorThan(char op1, char op2) {
    return (op1 == '*' || op1 == '/') && (op2 == '+' || op2 == '-');
}

int cal(int num1, int num2, char op) {
    switch (op) {
        case '+':
            return num1 + num2;
        case '-':
            return num1 - num2;
        case '*':
            return num1 * num2;
        case '/':
            return num1 / num2;
        default:
            return -1;
    }
}

void fetchAndCal(Stack *nums, Stack *ops) {
    char op = (char) stackPop(ops);
    int num2 = stackPop(nums);
    int num1 = stackPop(nums);
    int result = cal(num1, num2, op);
    stackPush(nums, result);
}

int calculate(char *s) {
    Stack *nums = stackCreate();
    Stack *ops = stackCreate();
    while (*s) {
        if (*s == ' ') {
            s++;
        } else if (isDigit(*s)) {
            int num = 0;
            while (isDigit(*s)) {
                num = num * 10 + (*s - '0');
                s++;
            }
            stackPush(nums, num);
        } else {
            // 运算符
            // 运算符栈为空，或遇到的运算符优先级较高，则可以压栈，这样出栈时该运算符先算
            if (stackEmpty(ops) ||
                priorThan(*s, (char) stackPeek(ops))) {
                stackPush(ops, *s);
            } else {
                // 遇到的运算符优先级相等或更低，可以将栈里的运算符都消掉
                while (!stackEmpty(ops) &&
                       !priorThan(*s, (char) stackPeek(ops))) {
                    fetchAndCal(nums, ops);
                }
                stackPush(ops, *s);
            }
            s++;
        }
    }

    while (!stackEmpty(ops)) {
        // 还有运算符没算
        fetchAndCal(nums, ops);
    }

    return stackPeek(nums);
}

int main() {
    char *s = "1+1-1";
    int result = calculate(s);
    printf("%d", result);
}

单调栈

42. 接雨水

int getMin(int a, int b) {
    return a < b ? a : b;
}

int getMax(int a, int b) {
    return a > b ? a : b;
}

// 单调栈的思想
int trap(int* height, int heightSize) {
    if (height == NULL || heightSize <= 0) {
        return 0;
    }
    // 存储单调递减的柱子高度，遇到比栈顶高的柱子时，尝试计算凹槽格子数
    int *stack = malloc(sizeof(int) * heightSize);
    int cnt = 0;
    int res = 0;
    for (int i = 0; i < heightSize; ++i) {
        int curHeight = height[i];
        if (cnt == 0 || curHeight <= height[stack[cnt - 1]]) {
            stack[cnt++] = i;
            continue; 
        }
        while (cnt > 0 && curHeight > height[stack[cnt - 1]]) {
            int popIndex = stack[cnt - 1];
            cnt--;
            if (cnt == 0) {
                break;
            }
            int leftIndex = stack[cnt - 1];
            int width = i - leftIndex - 1;
            int heightDif = getMin(curHeight, height[leftIndex]) - height[popIndex];
            res += (width * heightDif);
        }
        stack[cnt++] = i;
    }
    free(stack);
    return res;
}

// 前后缀思想
int trap_v2(int* height, int heightSize) {
    // 挨个计算每个柱子上的水格子数：min(该柱子左侧最高的柱子高度, 该柱子右侧最高的柱子高度) - 该柱子高度
    if (height == NULL || heightSize <= 2) {
        return 0;
    }
    // lmax[i]表示柱子i左侧最高柱子的高度，rmax表示右侧
    int *lmax = malloc(sizeof(int) * heightSize);
    int *rmax = malloc(sizeof(int) * heightSize);
    int max = 0;
    for (int i = 0; i < heightSize; ++i) {
        lmax[i] = max;
        max = getMax(max, height[i]);
    }
    max = 0;
    for (int i = heightSize - 1; i >= 0; --i) {
        rmax[i] = max;
        max = getMax(max, height[i]);
    }

    int res = 0;
    // 第一个和最后一个柱子上面不会积水
    for (int i = 1; i < heightSize - 1; ++i) {
        int dif = getMin(lmax[i], rmax[i]) - height[i];
        if (dif > 0) {
            res += dif;
        }
    }
    free(lmax);
    free(rmax);
    return res;
}

int main() {
    int height[] = {4,2,0,3,2,5};
    int res = trap(height, 6);
    printf("%d", res);
}

739. 每日温度

// https://leetcode.cn/problems/daily-temperatures/
// Created by 86157 on 2024/9/17.
//
#include "../stack.h"

int *dailyTemperatures_v2(int *temperatures, int temperaturesSize, int *returnSize) {
    if (temperatures == NULL || temperaturesSize <= 0) {
        return NULL;
    }
    *returnSize = temperaturesSize;
    int *result = malloc(sizeof(int) * temperaturesSize);
    int *stack = malloc(sizeof(int) * temperaturesSize * 2);
    int cnt = 0;
    for (int i = 0; i < temperaturesSize; ++i) {
        // 如果栈非空，且当前温度大于栈顶温度
        while (cnt > 0 && temperatures[i] > stack[cnt - 1]) {
            int dayIndex = stack[cnt - 2];
            result[dayIndex] = i - dayIndex;
            cnt -= 2;
        }
        // 入栈当前温度
        stack[cnt++] = i;
        stack[cnt++] = temperatures[i];
    }
    while (cnt > 0) {
        int dayIndex = stack[cnt - 2];
        result[dayIndex] = 0;
        cnt -= 2;
    }
    return result;
}

int *dailyTemperatures(int *temperatures, int temperaturesSize, int *returnSize) {
    if (temperatures == NULL || temperaturesSize <= 0) {
        return NULL;
    }
    *returnSize = temperaturesSize;

    int *result = malloc(sizeof(int) * temperaturesSize);
    // 用栈存放未知的答案（暂且不知道这一天之后的哪一天有更高的温度）
    Stack *stack = stackCreate();
    for (int i = 0; i < temperaturesSize; ++i) {
        // 遇到高温，将栈里的相对低温都出栈
        while (!stackEmpty(stack) && temperatures[i] > stackPeek(stack)){
            stackPop(stack);
            int index = stackPop(stack);
            result[index] = i - index;
        }
        // 将当前温度入栈
        stackPush(stack, i);
        stackPush(stack, temperatures[i]);
    }
    // 剩余的都是未知的
    while (!stackEmpty(stack)) {
        stackPop(stack);
        result[stackPop(stack)] = 0;
    }
    return result;
}

面试题 03.05. 栈排序

// https://leetcode.cn/problems/sort-of-stacks-lcci/description/
// Created by 86157 on 2024/9/16.
// 压栈时通过临时栈调整栈内元素单调递减（有点像插入排序），出栈时直接出栈栈顶元素

#include "../stack.h"

typedef struct {
    Stack *mainStack;
    Stack *minorStack;
} SortedStack;

SortedStack *sortedStackCreate() {
    SortedStack *stack = malloc(sizeof(SortedStack));
    stack->mainStack = stackCreate();
    stack->minorStack = stackCreate();
    return stack;
}

bool sortedStackIsEmpty(SortedStack *obj) {
    return stackEmpty(obj->mainStack);
}

void sortedStackFree(SortedStack *obj) {
    if (obj == NULL) {
        return;
    }
    stackFree(obj->mainStack);
    stackFree(obj->minorStack);
    free(obj);
}

void sortedStackPush(SortedStack *obj, int val) {
    if (stackEmpty(obj->mainStack)) {
        stackPush(obj->mainStack, val);
    } else {
        while (!stackEmpty(obj->mainStack) && stackPeek(obj->mainStack) < val) {
            stackPush(obj->minorStack, stackPop(obj->mainStack));
        }
        stackPush(obj->mainStack, val);
        while (!stackEmpty(obj->minorStack)) {
            stackPush(obj->mainStack, stackPop(obj->minorStack));
        }
    }
}

void sortedStackPop(SortedStack *obj) {
    if (!stackEmpty(obj->mainStack)) {
        stackPop(obj->mainStack);
    }
}

int sortedStackPeek(SortedStack *obj) {
    if (stackEmpty(obj->mainStack)) {
        return -1;
    }
    return stackPeek(obj->mainStack);
}

int main() {
    SortedStack *stack = sortedStackCreate();
    sortedStackPush(stack, 1);
    sortedStackPush(stack, 2);
    sortedStackPeek(stack);
    sortedStackPop(stack);
    sortedStackPeek(stack);
}

移除相邻的重复元素

20. 有效的括号

#include <stdbool.h>

// https://leetcode.cn/problems/valid-parentheses/description/
// Created by 86157 on 2024/9/17.
//
#include "../stack.h"

bool isLeftBracket(char c) {
    return c == '(' || c == '[' || c == '{';
}

char getMatchedLeftBracket(char c) {
    switch (c) {
        case ')':
            return '(';
        case ']':
            return '[';
        case '}':
            return '{';
        default:
            return -1;
    }
}

bool isValid(char* s) {
    Stack *stack = stackCreate();
    while (*s) {
        char ch = *s;
        if (isLeftBracket(ch)) {
            // 为左括号，直接入栈
            stackPush(stack, *s);
        } else {
            // 为右括号，是否与栈顶元素匹配
            if (stackEmpty(stack)) {
                return false;
            }
            char pop = (char) stackPop(stack);
            if (pop != getMatchedLeftBracket(ch)) {
                return false;
            }
        }
        s++;
    }
    return stackEmpty(stack);
}

1047. 删除字符串中的所有相邻重复项

// https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/
// Created by 86157 on 2024/9/17.
//

#include "../stack.h"

char *removeDuplicates(char *s) {
    Stack *stack = stackCreate();
    while (*s) {
        if (stackEmpty(stack) || stackPeek(stack) != *s) {
            stackPush(stack, *s);
        } else {
            stackPop(stack);
        }
        s++;
    }
    int size = stack->size;
    char *res = malloc(sizeof(char) * size + 1);
    res[size] = 0;
    for (int i = size - 1; i >= 0 ; --i) {
        res[i] = (char)stackPop(stack);
    }
    return res;
}

int main() {
    char *s = "abbaca";
    removeDuplicates(s);
}

1047. 删除字符串中的所有相邻重复项

// https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/
// Created by 86157 on 2024/9/17.
// 考虑三连消、四连消……的场景

#include "../stack.h"

/**
 * 方法一：将栈的泛型元素封装一下：字母+相邻重复次数
 * 方法二：先入栈重复相邻次数，再入栈字母
 */
char *removeDuplicates(char *s) {
    Stack *stack = stackCreate();
    while (*s) {
        if (stackEmpty(stack)) {
            stackPush(stack, 1);
            stackPush(stack, *s);
        } else if (stackPeek(stack) != *s) {
            int val = stackPop(stack);
            int cnt = stackPop(stack);
            if (cnt < 3) {
                stackPush(stack, cnt);
                stackPush(stack, val);
            }
        }
        else {
            int val = stackPop(stack);
            int cnt = stackPop(stack);
            stackPush(stack, cnt);
            stackPush(stack, val);
        }
        s++;
    }
    int size = stack->size;
    char *res = malloc(sizeof(char) * size + 1);
    res[size] = 0;
    for (int i = size - 1; i >= 0; --i) {
        res[i] = (char) stackPop(stack);
    }
    return res;
}

int main() {
    char *s = "abbaca";
    removeDuplicates(s);
}

递归和分治

LCR 123. 图书整理 I

// https://leetcode.cn/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/
// Created by 86157 on 2024/9/22.
//
#include <stdio.h>
#include "../linkedlist/linkedlist.h"

int getListSize(struct ListNode *head) {
    int cnt = 0;
    while (head != NULL) {
        cnt++;
        head = head->next;
    }
    return cnt;
}

// 逆序收集链表元素
void collectNodesInReversedOrder(struct ListNode *node, int *arr, int *index) {
    // 遇到空链表，递归终止
    if (node == NULL) {
        return;
    }
    // 逆序收集后继链表的元素成为一个子问题，假设子问题的解已知
    collectNodesInReversedOrder(node->next, arr, index);
    // 后继链表逆序收集完后，再收集当前节点
    arr[*index] = node->val;
    (*index)++;
}

int *reverseBookList(struct ListNode *head, int *returnSize) {
    int size = getListSize(head);
    *returnSize = size;
    if (size <= 0) {
        return NULL;
    }

    int *arr = malloc(sizeof(int) * size);
    int *index = malloc(sizeof(int));
    *index = 0;
    collectNodesInReversedOrder(head, arr, index);
    return arr;
}

int main() {
    //[3,6,4,1]
    struct ListNode *head = createList((int[]) {}, 0);
    int *retSize = malloc(sizeof(int));
    int *arr = reverseBookList(head, retSize);
    printf("");
}

LCR 126. 斐波那契数

// https://leetcode.cn/problems/fei-bo-na-qi-shu-lie-lcof/description/
// Created by 86157 on 2024/9/22.
//
#include "stdlib.h"

int fib_r(int n, int *record) {
    if (record[n] >= 0) {
        return record[n];
    }
    record[n] = (fib_r(n - 1, record) + fib_r(n - 2, record)) % 1000000007;
    return record[n];
}

int fib(int n) {
    // 输入非法
    if (n < 0) {
        return -1;
    }
    // 无需计算
    if(n == 0 || n == 1) {
        return n;
    }
    // 备忘录
    int record[n + 1];
    record[0] = 0;
    record[1] = 1;
    for (int i = 2; i < n + 1; ++i) {
        record[i] = -1;
    }
    int res = fib_r(n, record);
    return res % 1000000007;
}

LCR 127. 跳跃训练

// https://leetcode.cn/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/description/
// Created by 86157 on 2024/9/22.
//

int doTrainWays(int num, int *record) {
    if (record[num] >= 0) {
        return record[num];
    }
    record[num] = (doTrainWays(num - 1, record) + doTrainWays(num - 2, record))
                  % 1000000007;
    return record[num];
}

int trainWays(int num) {
    // 非法输入
    if (num < 0) {
        return -1;
    }
    if (num == 0 || num == 1) {
        return 1;
    }
    int record[num + 1];
    for (int i = 0; i < num + 1; ++i) {
        record[i] = -1;
    }
    record[0] = 1;
    record[1] = 1;
    return doTrainWays(num, record);
}

LCR 134. Pow(x, n)

// https://leetcode.cn/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/
// Created by 86157 on 2024/9/24.
//

#include <stdbool.h>
#include <math.h>
#include <limits.h>

double positivePow(double x, int n) {
    // 递归终止条件：x^0 = 1
    if (n == 0) {
        return 1;
    }
    // 假设求解过程已实现，获得子问题 x^(n/2) 的解 => 二分
    double tmp = positivePow(x, n / 2);
    tmp *= tmp;
    if (n % 2 == 1) {
        tmp *= x;
    }
    return tmp;
}

//-100.0 < x < 100.0
//-23^1 <= n <= 2^31 - 1
//-10^4 <= xn <= 10^4
double myPow(double x, int n) {
    if(n >= 0) {
        return positivePow(x, abs(n));
    }
    return 1/ (positivePow(x , -(n + 1)) * x);
}

LCR 141. 训练计划 III

// https://leetcode.cn/problems/fan-zhuan-lian-biao-lcof/description/
// Created by 86157 on 2024/9/24.
//
#include "../linkedlist/linkedlist.h"

struct ListNode *reverseList(struct ListNode *head) {
    // 递归终止条件：如果当前要翻转的链表只有一个节点
    if (head->next == NULL) {
        return head;
    }
    // 假设翻转过程已实现，将后继子链表翻转
    struct ListNode *tail = reverseList(head->next);
    // 将当前节点连接到后继子链表的末尾
    tail->next = head;
    head->next = NULL;
    // 翻转后，头结点为尾节点
    return head;
}

struct ListNode *trainningPlan(struct ListNode *head) {
    if (head == NULL) {
        return NULL;
    }
    struct ListNode *tail = head;
    while (tail->next != NULL) {
        tail = tail->next;
    }
    reverseList(head);
    return tail;
}

// https://leetcode.cn/problems/fan-zhuan-lian-biao-lcof/description/
// Created by 86157 on 2024/9/24.
//
#include "../linkedlist/linkedlist.h"

struct ListNode *reverseList(struct ListNode *head) {
    if(head == NULL){
        return NULL;
    }
    // 递归终止条件：链表只有一个节点（单节点链表的翻转结果是其本身）
    if(head->next == NULL) {
        return head;
    }
    // 翻转子链表
    struct ListNode *newHead = reverseList(head->next);
    head->next->next = head; // 不要忘了head.next还引用着新子链表的尾节点
    head->next = NULL;
    return newHead;
}

struct ListNode *trainningPlan(struct ListNode *head) {
    return reverseList(head);
}

LCR 142. 训练计划 IV

// https://leetcode.cn/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/
// Created by 86157 on 2024/9/24.
//
#include "../linkedlist/linkedlist.h"

/**
 * 合并两个有序链表，返回合并后新链表的头结点
 * @param l1 可以为空
 * @param l2 可以为空
 * @return
 */
struct ListNode *mergeSortedList(struct ListNode *l1, struct ListNode *l2) {
    // 递归终止条件：任意一个链表为空
    if (l1 == NULL || l2 == NULL) {
        return l1 == NULL ? l2 : l1;
    }
    // 当下出发，可以做的事情，从l1.head和l2.head中选出一个作为头结点
    struct ListNode *head = NULL;
    if (l1->val < l2->val) {
        head = l1;
        l1 = l1->next;
    } else {
        head = l2;
        l2 = l2->next;
    }
    // 假设合并过程已实现，得到子问题的解
    head->next = mergeSortedList(l1, l2);
    return head;
}

// 0 <= 链表长度 <= 1000
struct ListNode *trainningPlan(struct ListNode *l1, struct ListNode *l2) {
    return mergeSortedList(l1, l2);
}

int main() {
    struct ListNode *l1 = createList((int[]) {1, 2, 4}, 3);
    struct ListNode *l2 = createList((int[]) {1, 3, 4}, 3);
    trainningPlan(l1, l2);
}

面试题 08.01. 三步问题

int mod(int n) {
    return n % 1000000007;
}

int calc(int n, int *record) {
    if (record[n] > 0) {
        return record[n];
    }
    record[n] = mod(mod(calc(n - 1, record) + calc(n - 2, record)) + calc(n - 3, record));
    return record[n];
}

int waysToStep(int n) {
    if (n < 1) {
        return -1;
    }
    if (n == 1) {
        return 1;
    }
    if (n == 2) {
        return 2;
    }
    if (n == 3) {
        return 4;
    }
    int record[n + 1];
    for (int i = 0; i < n + 1; ++i) {
        record[i] = 0;
    }
    record[1] = 1;
    record[2] = 2;
    record[3] = 4;
    return calc(n, record);
}

// https://leetcode.cn/problems/three-steps-problem-lcci/
// Created by 86157 on 2024/9/22.
//
int mod(int n) {
    return n % 1000000007;
}
int waysToStep(int n) {
    if (n < 1) {
        return -1;
    }
    if (n == 1) {
        return 1;
    }
    if (n == 2) {
        return 2;
    }
    if (n == 3) {
        return 4;
    }
    int record[n + 1];
    record[1] = 1;
    record[2] = 2;
    record[3] = 4;
    for (int i = 4; i < n + 1; ++i) {
        record[i] = mod(mod(record[i - 1] + record[i - 2]) + record[i - 3]);
    }
    return record[n];
}

// https://leetcode.cn/problems/three-steps-problem-lcci/
// Created by 86157 on 2024/9/22.
//
int mod(int n) {
    return n % 1000000007;
}
int waysToStep(int n) {
    if (n == 1) {
        return 1;
    }
    if (n == 2) {
        return 2;
    }
    if (n == 3) {
        return 4;
    }
    int a = 1;
    int b = 2;
    int c = 4;
    int d;
    for (int i = 4; i <= n; ++i) {
        d = mod(mod(a + b) + c);
        a = b;
        b = c;
        c = d;
    }
    return d;
}

面试题 08.05. 递归乘法

// https://leetcode.cn/problems/recursive-mulitply-lcci/
// Created by 86157 on 2024/9/25.
//

#include <stdio.h>

// 递归乘法。 写一个递归函数，不使用 * 运算符，
// 实现两个正整数的相乘。可以使用加号、减号、位移，但要吝啬一些。
int multiply(int A, int B){
    // A,B为正整数
    // 递归终止条件，A二分至最小的正整数
    if(A == 1) {
        return B;
    }
    // 假设算法过程已实现，二分求解子问题
    int tmp = multiply(A >> 1, B);
    tmp = tmp << 1;
    if (A % 2 == 1) {
        // (A/2 + A/2 + 1) * B
        tmp += B;
    }
    return tmp;
}

int main() {
    printf("%d", multiply(3, 4));
}

排序

排序作为前置处理

56. 合并区间

// https://leetcode.cn/problems/merge-intervals/description/
// Created by 86157 on 2024/10/1.
//
#include <time.h>
#include "stdlib.h"

void quickSort(int **intervals, int begin, int end);

int partition(int **intervals, int begin, int end);

void swap(int **intervals, int i, int j);

int max(int a, int b);

int **merge(int **intervals, int intervalsSize, int *intervalsColSize, int *returnSize, int **returnColumnSizes) {
    *returnColumnSizes = intervalsColSize;
    if(intervals == NULL || intervalsSize <= 0) {
        *returnSize = 0;
        return NULL;
    }
    if(intervalsSize == 1) {
        *returnSize = 1;
        return intervals;
    }
    quickSort(intervals, 0, intervalsSize - 1);
    int p = 0;
    for (int i = 1; i < intervalsSize; ++i) {
        if(intervals[i][0] <= intervals[p][1]) {
            // have intersection, take the bigger one as the interval's right
            intervals[p][1] = max(intervals[p][1], intervals[i][1]);
        }else{
            intervals[++p] = intervals[i];
        }
    }
    *returnSize = p + 1;
    return intervals;
}

int max(int a, int b) {
    return a > b ? a : b;
}

void quickSort(int **intervals, int begin, int end) {
    if (begin >= end) {
        return;
    }
    srand(time(NULL));
    int pivotIndex = partition(intervals, begin, end);
    if (pivotIndex - 1 > begin) {
        quickSort(intervals, begin, pivotIndex - 1);
    }
    if (pivotIndex + 1 < end) {
        quickSort(intervals, pivotIndex + 1, end);
    }
}

int partition(int **intervals, int begin, int end) {
    int r = begin + rand() % (end - begin + 1);
    swap(intervals, r, end);

    int p = begin - 1;
    for (int i = begin; i <= end - 1; ++i) {
        if(intervals[i][0] < intervals[end][0]) {
            swap(intervals, i, ++p);
        }
    }
    swap(intervals, end, p + 1);
    return p + 1;
}

void swap(int **intervals, int i, int j) {
    if (i == j) {
        return;
    }
    int *tmp = intervals[i];
    intervals[i] = intervals[j];
    intervals[j] = tmp;
}

int main () {

}

242. 有效的字母异位词

// https://leetcode.cn/problems/valid-anagram/
// Created by 86157 on 2024/9/25.
//

#include <stdbool.h>
#include <stdio.h>
#include "../classic_sort/quick_sort.h"

bool isAnagram(char* s, char* t) {
    int cnt[26] = {0};
    while (*s) {
        cnt[*s - 'a']++;
        s++;
    }
    while (*t) {
        cnt[*t - 'a']--;
        t++;
    }
    for (int i = 0; i < 26; ++i) {
        if (cnt[i] != 0) {
            return false;
        }
    }
    return true;
}

int main() {
    int arr[] = {5,4,3,2,1};
    quickSort(arr, 0, 4);
    for (int i = 0; i < 5; ++i) {
        printf("%d ", arr[i]);
    }
}

// https://leetcode.cn/problems/valid-anagram/
// Created by 86157 on 2024/9/25.
//

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include "../classic_sort/quick_sort.h"

int strLen(char *s) {
    int len = 0;
    while (*s++) {
        len++;
    }
    return len;
}

int *sortStr(char *s, int len) {
    int *arr = malloc(sizeof(int) * len);
    for (int i = 0; i < len; ++i) {
        arr[i] = (int)s[i];
    }
    quickSort(arr, len);
    return arr;
}

bool isAnagram(char* s, char* t) {
    int l1 = strLen(s);
    int l2 = strLen(t);
    if (l1 != l2) {
        return false;
    }
    if (l1 == 0) {
        return true;
    }
    int *arr1 = sortStr(s, l1);
    int *arr2 = sortStr(t, l1);
    for (int i = 0; i < l1; ++i) {
        if (arr1[i] != arr2[i]) {
            return false;
        }
    }
    return true;
}

int main() {
    char *s = "anagram";
    char *t = "nagaram";
    isAnagram(s, t);
}

1502. 判断能否形成等差数列

// https://leetcode.cn/problems/can-make-arithmetic-progression-from-sequence/
// Created by 86157 on 2024/10/1.
//

#include <stdbool.h>
#include <time.h>
#include "stdlib.h"

void quickSort_r(int *arr, int begin, int end);

void quickSort(int *arr, int n);

int partition(int *arr, int begin, int end);

void swap(int *arr, int i, int j);

bool canMakeArithmeticProgression(int *arr, int arrSize) {
    if(arr == NULL || arrSize <= 2) {
        return true;
    }
    quickSort(arr, arrSize);
    int diff = arr[1] - arr[0];
    for (int i = 2; i < arrSize; ++i) {
        if (arr[i] - arr[i - 1] != diff) {
            return false;
        }
    }
    return true;
}

void quickSort(int *arr, int n) {
    if (arr == NULL || n <= 1) {
        return;
    }
    srand(time(NULL));
    quickSort_r(arr, 0, n - 1);
}

void quickSort_r(int *arr, int begin, int end) {
    if (begin >= end) {
        return;
    }
    int pivotIndex = partition(arr, begin, end);
    if (pivotIndex - 1 > begin) {
        quickSort_r(arr, begin, pivotIndex - 1);
    }
    if (pivotIndex + 1 < end) {
        quickSort_r(arr, pivotIndex + 1, end);
    }
}

int partition(int *arr, int begin, int end) {
    int r = begin + rand() % (end - begin + 1);
    swap(arr, r, end);

    // [begin, p] => lower than arr[end], [p+1, end] => others
    int p = begin - 1;
    // visit [begin, end-1] and put the lower into [begin, p] and extend p
    for (int i = begin; i <= end - 1; ++i) {
        if(arr[i] < arr[end]) {
            swap(arr, i, p + 1);
            p++;
        }
    }
    // arr => [begin, p], pivot, others
    swap(arr, end, p + 1);
    return p + 1;
}

void swap(int *arr, int i, int j) {
    if (i == j) {
        return;
    }
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

int main () {
   int arr[] = {-68,-96,-12,-40,16};
    canMakeArithmeticProgression(arr, 5);
}

变种排序

75. 颜色分类

// https://leetcode.cn/problems/sort-colors/description/
// Created by 86157 on 2024/10/1.
//
#include <stdbool.h>
#include <time.h>
#include "stdlib.h"

void quickSort_r(int *arr, int begin, int end);

void quickSort(int *arr, int n);

int partition(int *arr, int begin, int end);

void swap(int *arr, int i, int j);

void sortColors(int *nums, int numsSize) {
    quickSort(nums, numsSize);
}

void quickSort(int *arr, int n) {
    if (arr == NULL || n <= 1) {
        return;
    }
    srand(time(NULL));
    quickSort_r(arr, 0, n - 1);
}

void quickSort_r(int *arr, int begin, int end) {
    if (begin >= end) {
        return;
    }
    int pivotIndex = partition(arr, begin, end);
    if (pivotIndex - 1 > begin) {
        quickSort_r(arr, begin, pivotIndex - 1);
    }
    if (pivotIndex + 1 < end) {
        quickSort_r(arr, pivotIndex + 1, end);
    }
}

int partition(int *arr, int begin, int end) {
    int r = begin + rand() % (end - begin + 1);
    swap(arr, r, end);

    // [begin, p] => lower than arr[end], [p+1, end] => others
    int p = begin - 1;
    // visit [begin, end-1] and put the lower into [begin, p] and extend p
    for (int i = begin; i <= end - 1; ++i) {
        if (arr[i] < arr[end]) {
            swap(arr, i, p + 1);
            p++;
        }
    }
    // arr => [begin, p], pivot, others
    swap(arr, end, p + 1);
    return p + 1;
}

void swap(int *arr, int i, int j) {
    if (i == j) {
        return;
    }
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

LCR 139. 训练计划 I

// https://leetcode.cn/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/
// Created by 86157 on 2024/9/25.
//

#include "../../common.h"

// 需要将数组调整为【奇数区间，偶数区间】的形式
// 那么可以各用一个指针来动态扩大区间
int* trainingPlan(int* actions, int actionsSize, int* returnSize) {
    *returnSize = actionsSize;
    if (actionsSize <= 1) {
        return actions;
    }
    // [0, i)表示奇数区间，[j, end]表示偶数区间
    int i = 0, j = actionsSize - 1;
    while (i < j) { // 两个区间不应该重叠
        // 先尝试直接扩大两个区间
        if (actions[i] % 2 == 1) {
            i++;
            continue;
        }
        if (actions[j] % 2 == 0) {
            j--;
            continue;
        }
        // 两个区间都扩大不了，说明i上是偶数，j上是奇数
        swap(actions, i, j);
        i++;
        j--;
    }
    return actions;
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int size = 5;
    int *rSize = malloc(sizeof(int));
    trainingPlan(arr, size, rSize);
}

// https://leetcode.cn/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/
// Created by 86157 on 2024/9/25.
//

#include "../../common.h"

// 需要将数组调整为【奇数区间，偶数区间】的形式
// 那么可以各用一个指针来动态扩大区间
int* trainingPlan(int* actions, int actionsSize, int* returnSize) {
    *returnSize = actionsSize;
    if (actionsSize <= 1) {
        return actions;
    }
    // 利用[0, p]表示奇数区间，并在遍历时尝试将其扩大
    int p = -1;
    for (int i = 0; i < actionsSize; ++i) {
        if (actions[i] % 2 == 1) {
            swap(actions, i, p + 1);
            p++;
        }
    }
    return actions;
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int size = 5;
    int *rSize = malloc(sizeof(int));
    trainingPlan(arr, size, rSize);
}

TOP-K

215. 数组中的第K个最大元素

// https://leetcode.cn/problems/kth-largest-element-in-an-array/
// Created by 86157 on 2024/9/25.
//

#include <stdlib.h>
#include <time.h>
#include "../../common.h"

int partition(int *arr, int begin, int end) {
    int index = begin + rand() % (end - begin + 1);
    swap(arr, index, end);
    // 使用[begin,i]作为 大于pivot 的区间
    int i = begin - 1;
    for (int j = begin; j < end; ++j) {
        if (arr[j] > arr[end]) {
            swap(arr, j, i + 1);
            i++;
        }
    }
    swap(arr, end, i + 1);
    return i + 1;
}

int quickSort(int *arr, int begin, int end, int k) {
    if (begin == end) {
        return arr[begin];
    }
    int index = partition(arr, begin, end);
    int left = index - begin + 1;
    if (left == k) {
        return arr[index];
    }
    if (left > k) {
        return quickSort(arr, begin, index - 1, k);
    } else {
        return quickSort(arr, index + 1, end, k - (left));
    }
}

int findKthLargest(int* nums, int numsSize, int k) {
    srand(time(NULL));
    return quickSort(nums, 0, numsSize - 1, k);
}

int main() {
    int arr[] = {3, 2, 1, 5, 6, 4};
    int num = findKthLargest(arr, 6, 2);
    printf("%d", num);
}

面试题 17.14. 最小K个数

// https://leetcode.cn/problems/smallest-k-lcci/description/
// Created by 86157 on 2024/9/26.
//

#include <stddef.h>
#include <stdlib.h>
#include <time.h>
#include "../../common.h"

void quickSort(int *arr, int n, int k);

void quickSort_r(int *arr, int begin, int end, int k);

int partition(int *arr, int begin, int end);

int* smallestK(int* arr, int arrSize, int k, int* returnSize){
    *returnSize = k;
    if (arrSize <= 1 || k <= 0) {
        return arr;
    }
    quickSort(arr, arrSize, k);
    return arr;
}

// 利用快排过程，递归到partition之后，前半部分的元素个数为k即可
void quickSort(int *arr, int n, int k) {
    if (n <= 1) {
        return;
    }
    srand(time(NULL));
    quickSort_r(arr, 0, n - 1, k);
}

void quickSort_r(int *arr, int begin, int end, int k) {
    if (begin == end) {
        return;
    }
    int pivotIndex = partition(arr, begin, end);
    if (pivotIndex + 1 == k) {
        return;
    }
    if(pivotIndex + 1 < k) {
        quickSort_r(arr, pivotIndex + 1, end, k);
    } else {
        quickSort_r(arr, begin, pivotIndex - 1, k);
    }
}

int partition(int *arr, int begin, int end) {
    int r = begin + (rand() % (end - begin + 1));
    swap(arr, r, end);
    int i = begin - 1;
    for (int j = begin; j < end; ++j) {
        if (arr[j] < arr[end]) {
            swap(arr, j, i + 1);
            i++;
        }
    }
    swap(arr, end, i + 1);
    return i + 1;
}

int main() {
    int arr[] = {1,2,3};
    int k = 0;
    int *rSize = malloc(sizeof(int));
    int *ans = smallestK(arr, 8, k, rSize);
    printArr(ans, k);
}

排序

LCR 170. 交易逆序对的总数

#include <malloc.h>
#include <stdio.h>

// https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/description/
// Created by 86157 on 2024/10/1.
//
void mergeSort(int *arr, int begin, int end, int *pairs);

int reversePairs(int *record, int recordSize) {
    if(record == NULL || recordSize <= 1) {
        return 0;
    }
    int pairs = 0;
    mergeSort(record, 0, recordSize - 1, &pairs);
    return pairs;
}


void mergeSort(int *arr, int begin, int end, int *pairs) {
    if (begin >= end) {
        return;
    }
    int mid = begin + ((end - begin) / 2);
    mergeSort(arr, begin, mid, pairs);
    mergeSort(arr, mid + 1, end, pairs);
    int *tmp = malloc(sizeof(int) * (end - begin + 1));
    int l = begin, r = mid + 1, p = 0;
    while (l <= mid && r <= end) {
        if (arr[l] <= arr[r]) {
            tmp[p++] = arr[l++];
        } else {
            tmp[p++] = arr[r++];
            (*pairs) += (mid - l + 1);
        }
    }
    while (l <= mid) {
        tmp[p++] = arr[l++];
    }
    while (r <= end){
        tmp[p++] = arr[r++];
    }

    p = 0;
    for (int i = begin; i <= end; ++i) {
        arr[i] = tmp[p];
        p++;
    }
    free(tmp);
}

int main() {
    int arr[] = {7,5,6,4};
    int pairs = reversePairs(arr, 4);
    printf("%d ", pairs);
}

面试题 10.01. 合并排序的数组

// https://leetcode.cn/problems/sorted-merge-lcci/description/
// Created by 86157 on 2024/9/25.
//

void merge(int* A, int ASize, int m, int* B, int BSize, int n){
    // i从A数组的末尾向前
    int k = m + n;
    while (m > 0 && n > 0) {
        if (A[m - 1] > B[n - 1]) {
            A[k-1] = A[m - 1];
            m--;
        } else {
            A[k-1] = B[n - 1];
            n--;
        }
        k--;
    }
    while (n > 0) {
        A[k-1] = B[n - 1];
        n--;
        k--;
    }
}

二分查找

二分答案/逐次逼近

69. x 的平方根

// https://leetcode.cn/problems/sqrtx/
// Created by 86157 on 2024/10/9.
//

// 0 <= x <= 231 - 1
int mySqrt(int x) {
    int begin = 0;
    int end = x / 2 + 1;
    while (begin <= end) {
        int mid = begin + (end - begin) / 2;
        long square = (long) mid * mid;
        if (square == x) {
            return mid;
        }
        if (square < x) {
            // detect backward
            long tmp = (long) (mid + 1) * (mid + 1);
            if (tmp > x) {
                return mid;
            } else {
                begin = mid + 1;
            }
        } else {
            end = mid - 1;
        }
    }
    return -1;
}

367. 有效的完全平方数

#include <stdbool.h>

// https://leetcode.cn/problems/valid-perfect-square/description/
// Created by 86157 on 2024/10/9.
//
bool isPerfectSquare(int num) {
    // 1 <= num <= 231 - 1
    int max = num / 2 + 1;
    if(max > (1 << 16)) {
        max = (1 << 16);
    }
    int begin = 0;
    int end = max;
    while (begin <= end) {
        long mid = begin + (end - begin) /2 ;
        long square = mid * mid;
        if (square == num) {
            return true;
        }
        if (square > num) {
            end = mid - 1;
        } else {
            begin = mid + 1;
        }
    }
    return false;
}

875. 爱吃香蕉的珂珂

// https://leetcode.cn/problems/koko-eating-bananas/
// Created by 86157 on 2024/10/20.
//
#include <stdio.h>
#include "../../common/Com_Util.h"
int getHour(int *piles, int pilesSize, int speed) {
    int h = 0;
    for (int i = 0; i < pilesSize; ++i) {
        h += (piles[i] / speed);
        h += (piles[i] % speed) ? 1 : 0;
    }
    return h;
}

int minEatingSpeed(int *piles, int pilesSize, int h) {
    int minSpeed = 1;
    int maxSpeed = 1;
    for (int i = 0; i < pilesSize; ++i) {
        if (piles[i] > maxSpeed) {
            maxSpeed = piles[i];
        }
    }
    // 在最小和最大速度之间二分查找能在规定时间内吃完香蕉的最慢速度
    while (minSpeed <= maxSpeed) {
        int midSpeed = minSpeed + (maxSpeed - minSpeed) / 2;
        // 这个速度吃，需要hour小时
        int hour = getHour(piles, pilesSize, midSpeed);
        if (hour <= h) { // 我吃完了，警卫还没回呢！
            if(midSpeed > 1 && getHour(piles, pilesSize, midSpeed - 1) <= h) {
                // 我发现放慢点速度也可以在规定时间内吃完，那就慢一点！
                maxSpeed = midSpeed - 1;
            } else {
                // 我发现再放慢速度就要被警卫抓住啦！
                return midSpeed;
            }
        } else {
            // hour > h，这个速度吃完警卫都回来了。不行，我得加快速度！
            minSpeed = midSpeed + 1;
        }
    }
    return -1;
}

int main() {
    int piles[] = {312884470};
    int pilesSize = 1;
    int h = 312884469;
    int speed = minEatingSpeed(piles, pilesSize, h);
    Com_Util_LogInt(speed);
    return 0;
}

经典二分

35. 搜索插入位置

// https://leetcode.cn/problems/search-insert-position/
// Created by 86157 on 2024/10/6.
//

/**
 * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
 * 请必须使用时间复杂度为 O(log n) 的算法。
        1 <= nums.length <= 104
        -104 <= nums[i] <= 104
        nums 为 无重复元素 的 升序 排列数组
        -104 <= target <= 104
 * @param nums
 * @param numsSize
 * @param target
 * @return
 */
int searchInsert(int *nums, int numsSize, int target) {
    int left = 0;
    int right = numsSize - 1;
    // find the first element that is greater than target
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] >= target) {
            if (mid == 0 || nums[mid - 1] < target) {
                return mid;
            }
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return numsSize;
}

74. 搜索二维矩阵

// https://leetcode.cn/problems/search-a-2d-matrix/
// Created by 86157 on 2024/10/9.
//

#include <stdbool.h>

bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target) {
    int row = matrixSize, col = *matrixColSize;
    int begin = 0;
    int end = row * col - 1;
    while (begin <= end) {
        int mid = begin + (end - begin) / 2;
        int num = matrix[mid / col][mid % col];
        if (num == target) {
            return true;
        }
        if (num > target) {
            end = mid - 1;
        } else {
            begin = mid + 1;
        }
    }
    return false;
}

// https://leetcode.cn/problems/search-a-2d-matrix/
// Created by 86157 on 2024/10/9.
//

#include <stdbool.h>

bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target) {
    int row = matrixSize, col = *matrixColSize;
    int i = 0;
    while (i < row - 1 && matrix[i + 1][0] <= target) {
        i++;
    }
    for (int j = 0; j < col; ++j) {
        if (matrix[i][j] == target) {
            return true;
        }
    }
    return false;
}

374. 猜数字大小

// https://leetcode.cn/problems/guess-number-higher-or-lower/
// Created by 86157 on 2024/10/6.
//
/**
 * Forward declaration of guess API.
 * @param  num   your guess
 * @return 	     -1 if num is higher than the picked number
 *			      1 if num is lower than the picked number
 *               otherwise return 0
 * int guess(int num);
 */
int guess(int num);

int guessNumber(int n){
    int low = 0;
    int high = n;
    while (low <= high) {
        int mid = low + (high - mid) / 2;
        int guess_result = guess(mid);
        if (guess_result == 0) {
            return mid;
        }
        if (guess_result > 0) {
            // mid < target
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

704. 二分查找

// https://leetcode.cn/problems/binary-search/description/
// Created by 86157 on 2024/10/6.
//
int search(int* nums, int numsSize, int target) {
    int low = 0;
    int high = numsSize - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (nums[mid] == target) {
            return mid;
        }
        if(nums[mid] > target) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return  -1;
}

周围探测

34. 在排序数组中查找元素的第一个和最后一个位置

// https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
// Created by 86157 on 2024/10/6.
//
#include <stdlib.h>

int* searchRange(int* nums, int numsSize, int target, int* returnSize) {
    *returnSize = 2;
    int *result = malloc(sizeof(int) * 2);
    if(numsSize == 0) {
        result[0] = result[1] = -1;
        return result;
    }
    // find the first target and the last target respectively
    int left = 0;
    int right = numsSize - 1;
    int begin = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if(nums[mid] == target) {
            // detect forward
            if (mid == 0 || nums[mid - 1] < target) {
                begin = mid;
                break;
            }
            // [mid-1] == target
            right = mid - 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    int end = -1;
    left = 0;
    right = numsSize - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if(nums[mid] == target) {
            // detect backward
            if (mid == numsSize - 1 || nums[mid + 1] > target) {
                end = mid;
                break;
            }
            // [mid+1] == target
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    result[0] = begin;
    result[1] = end;
    return result;
}

658. 找到 K 个最接近的元素

// https://leetcode.cn/problems/find-k-closest-elements/
// Created by 86157 on 2024/10/20.
//
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include "../../common/Com_Util.h"

int* findClosestElements(int* arr, int arrSize, int k, int x, int* returnSize) {
    *returnSize = k;
    if (arrSize == 1) {
        return arr;
    }
    int left = 0, right = arrSize - 1;
    int p = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == x) {
            p = mid;
            break;
        }
        if (arr[mid] > x) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    int *res = malloc(sizeof(int) * k);
    if (right == -1) {
        memcpy(res, arr, sizeof(int) * k);
        return res;
    }
    if (left == arrSize) {
        memcpy(res, arr + arrSize - k, sizeof(int) * k);
        return res;
    }
    if(left > right) {
        p = abs(arr[left] - x) < abs(arr[right] - x) ? left : right;
    }
    int q = p;
    while (q - p + 1 < k) {
        if (p == 0) {
            q++;
        } else if (q == arrSize - 1) {
            p--;
        } else if (abs(arr[p - 1] - x) <= abs(arr[q + 1] - x)) {
            p--;
        } else {
            q++;
        }
    }
    memcpy(res, arr + p, sizeof(int) * k);
    return res;
}

int main() {
    int arr[] = {1,1,2,3,4,5};
    int arrSize = 5, k = 4, x= -1;
    int returnSize;
    int *res = findClosestElements(arr, arrSize, k, x, &returnSize);
    Com_Util_LogArr(res, k);
    return 0;
}

744. 寻找比目标字母大的最小字母

// https://leetcode.cn/problems/find-smallest-letter-greater-than-target/
// Created by 86157 on 2024/10/6.
//

/**
 * 寻找比目标字母大的最小字母
        2 <= letters.length <= 104
        letters[i] 是一个小写字母
        letters 按非递减顺序排序
        letters 最少包含两个不同的字母
        target 是一个小写字母
 * @param letters
 * @param lettersSize
 * @param target
 * @return
 */
char nextGreatestLetter(char *letters, int lettersSize, char target) {
    int low = 0;
    int high = lettersSize - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (letters[mid] > target) {
            // detect_around forward
            if (mid == 0 || letters[mid - 1] <= target) {
                return letters[mid];
            }
            // [mid-1] > target
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return letters[0];
}

特殊数组

162. 寻找峰值

// https://leetcode.cn/problems/find-peak-element/description/
// Created by 86157 on 2024/10/6.
//
int findPeakElement(int *nums, int numsSize) {
    if (numsSize == 1) {
        return 0;
    }
    if (numsSize == 2) {
        return nums[0] > nums[1] ? 0 : 1;
    }
    int left = 0;
    int right = numsSize - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        // 题目：你可以假设 nums[-1] = nums[n] = -∞ 。
        if (mid == 0) { // 边界情况：mid==0
            if (nums[mid] > nums[mid + 1]) {
                return mid;
            } else {
                left = mid + 1;
            }
        } else if (mid == numsSize - 1) { // 边界情况：mid==size-1
            if (nums[mid] > nums[mid - 1]) {
                return mid;
            } else {
                right = mid - 1;
            }
        } else if (nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]) { // mid命中
            return mid;
        } else if (nums[mid - 1] < nums[mid]) { // 缩小区间
            // mid之前是是上坡，[mid]到[n](-∞)肯定会经历峰值并下坡
            left = mid + 1;
        } else if (nums[mid - 1] > nums[mid]) { // 缩小区间
            // mid之前是下坡，[0](-∞)肯定上坡经历了峰值再下坡到mid
            right = mid - 1;
        }
    }
    return -1;
}

852. 山脉数组的峰顶索引

// https://leetcode.cn/problems/peak-index-in-a-mountain-array/description/
// Created by 86157 on 2024/10/6.
//

int peakIndexInMountainArray(int *arr, int arrSize) {
    int left = 0;
    int right = arrSize - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;c
        if (mid == 0) {
            left = mid + 1;
        } else if (mid == arrSize - 1) {
            right = mid - 1;
        } else if (arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]) {
            return mid;
        } else if (arr[mid] < arr[mid + 1]) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

33. 搜索旋转排序数组

// https://leetcode.cn/problems/search-in-rotated-sorted-array/
// Created by 86157 on 2024/10/6.
//
int search(int *nums, int numsSize, int target) {
    int left = 0;
    int right = numsSize - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        }
        if (nums[mid] > target) {
            // 哪些情况搜索左侧
            if (mid == right || nums[right] > nums[mid] || nums[left] <= target) {
                // [right] > [mid] 说明[mid, right]有序，搜索左侧
                // [right] < [mid] 说明[left, mid]有序，如果[left]<target<[mid]，搜索左侧
                right = mid - 1;
            }
            // 其他情况搜索右侧
            else {
                left = mid + 1;
            }
        } else { // [mid] < target
            if (mid == left || nums[left] < nums[mid] || nums[right] >= target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    return -1;
}

int main() {
    int nums[] = {3, 5, 1};
    search(nums, 3, 3);
}

// https://leetcode.cn/problems/search-in-rotated-sorted-array/
// Created by 86157 on 2024/10/6.
//
int search(int *nums, int numsSize, int target) {
    int left = 0;
    int right = numsSize - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        }
        if (nums[left] <= nums[mid]) { // 左侧区间严格有序(left=mid时nums[left]=nums[mid])
            // 判断target是否在左区间（判断target是否在有序区间很容易）
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else { // 右侧区间严格有序
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    return -1;
}

int main() {
    int nums[] = {3, 5, 1};
    search(nums, 3, 3);
}

153. 寻找旋转排序数组中的最小值

// https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/
// Created by 86157 on 2024/10/6.
//
int findMin(int *nums, int numsSize) {
    if (numsSize == 1) {
        return nums[0];
    }
    int left = 0;
    int right = numsSize - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < nums[(mid - 1 + numsSize) % numsSize]) {
            return nums[mid];
        }
        // [mid] >= [mid-1]
        if (nums[mid] <= nums[right]) { // 右侧严格有序，最小值在左侧
            right = mid - 1;
        } else { // 右侧循环有序，最小值在右侧
            left = mid + 1;
        }
    }
    return -1;
}

面试题 10.05. 稀疏数组搜索

// https://leetcode-cn.com/problems/sparse-array-search-lcci/
// Created by 86157 on 2024/10/6.
//

#include <stdio.h>

int str_cmp(char *p, char *q) {
    while (*p && *q) {
        if (*p != *q) {
            break;
        }
        p++;
        q++;
    }
    return *p - *q;
}

int findString(char **words, int wordsSize, char *s) {
    int left = 0;
    int right = wordsSize - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (str_cmp(words[mid], s) == 0) {
            return mid;
        }
        int tmp = mid;
        while (tmp >= 0 && str_cmp(words[tmp], "") == 0) {
            tmp--;
        }
        if (tmp < 0) {
            left = mid + 1;
            continue;
        }
        int cmp = str_cmp(words[tmp], s);
        if (cmp == 0) {
            return tmp;
        } else if (cmp > 0) {
            right = tmp - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

int main() {
    char *words[] = {"at", "", "", "", "ball", "", "", "car", "", "", "dad", "", ""};
    int i = findString(words, 13, "ball");
    printf("%d ", i);
}

哈希

二叉树

前中后序遍历（DFS）

递归实现

※非递归实现

144. 二叉树的前序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

#define MAX_STACK_SIZE 100

typedef enum {
    LEFT_SUBTREE_UNPROCESSED,
    RIGHT_SUBTREE_UNPROCESSED,
    SUBTREE_PROCESSED
} TraverseState;

typedef struct {
    struct TreeNode *node;
    TraverseState state;
} Frame;

typedef struct {
    Frame* frames[MAX_STACK_SIZE];
    int size;
} Stack;

void push(Stack* stack, Frame* frame) {
    if (stack->size == MAX_STACK_SIZE) {
        return;
    }
    stack->frames[stack->size++] = frame;
}

void pop(Stack* stack) {
    if (stack->size == MAX_STACK_SIZE) {
        return;
    }
    --stack->size;
}

bool isEmpty(Stack* stack) { return stack->size == 0; }

Frame* peek(Stack* stack) {
    if (isEmpty(stack)) {
        return NULL;
    }
    return stack->frames[stack->size - 1];
}

void pushNode(Stack* stack, struct TreeNode* node) {
    if (node != NULL) {
        Frame* tmp = malloc(sizeof(Frame));
        tmp->node = node;
        tmp->state = LEFT_SUBTREE_UNPROCESSED;
        push(stack, tmp);
    }
}

int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    *returnSize = 0;
    int *res = malloc(sizeof(int) * MAX_STACK_SIZE);

    Stack* stack = malloc(sizeof(Stack));
    stack->size = 0;
    pushNode(stack, root);

    while (!isEmpty(stack)) {
        Frame *frame = peek(stack);
        if (frame->state == LEFT_SUBTREE_UNPROCESSED) {
            res[(*returnSize)++] = frame->node->val;
            pushNode(stack, frame->node->left);
            frame->state = RIGHT_SUBTREE_UNPROCESSED;
            continue;
        } else if (frame->state == RIGHT_SUBTREE_UNPROCESSED) {
            pushNode(stack, frame->node->right);
            frame->state = SUBTREE_PROCESSED;
            continue;
        } else {
            pop(stack);
        }
    }
    return res;
}

94. 二叉树的中序遍历

void pushNode(Stack* stack, struct TreeNode* node) {
    if (node != NULL) {
        Frame* tmp = malloc(sizeof(Frame));
        tmp->node = node;
        tmp->state = LEFT_SUBTREE_UNPROCESSED;
        push(stack, tmp);
    }
}

int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    *returnSize = 0;
    if(root == NULL) return NULL;
    int *res = malloc(sizeof(int) * MAX_STACK_SIZE);

    Stack* stack = malloc(sizeof(Stack));
    stack->size = 0;
    pushNode(stack, root);

    while (!isEmpty(stack)) {
        Frame *frame = peek(stack);
        if (frame->state == LEFT_SUBTREE_UNPROCESSED) {
            pushNode(stack, frame->node->left);
            frame->state = RIGHT_SUBTREE_UNPROCESSED;
            continue;
        } else if (frame->state == RIGHT_SUBTREE_UNPROCESSED) {
            res[(*returnSize)++] = frame->node->val;
            pushNode(stack, frame->node->right);
            frame->state = SUBTREE_PROCESSED;
            continue;
        } else {
            pop(stack);
        }
    }
    return res;
}

145. 二叉树的后序遍历

void pushNode(Stack* stack, struct TreeNode* node) {
    if (node != NULL) {
        Frame* tmp = malloc(sizeof(Frame));
        tmp->node = node;
        tmp->state = LEFT_SUBTREE_UNPROCESSED;
        push(stack, tmp);
    }
}

int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    *returnSize = 0;
    if(root == NULL) return NULL;
    int *res = malloc(sizeof(int) * MAX_STACK_SIZE);

    Stack* stack = malloc(sizeof(Stack));
    stack->size = 0;
    pushNode(stack, root);

    while (!isEmpty(stack)) {
        Frame *frame = peek(stack);
        if (frame->state == LEFT_SUBTREE_UNPROCESSED) {
            pushNode(stack, frame->node->left);
            frame->state = RIGHT_SUBTREE_UNPROCESSED;
            continue;
        } else if (frame->state == RIGHT_SUBTREE_UNPROCESSED) {
            pushNode(stack, frame->node->right);
            frame->state = SUBTREE_PROCESSED;
            continue;
        } else {
            res[(*returnSize)++] = frame->node->val;
            pop(stack);
        }
    }
    return res;
}

589. N 叉树的前序遍历

590. N 叉树的后序遍历

按层遍历（BFS）

102. 二叉树的层序遍历

🌟方法一：由size来做每一层的分隔

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {
    if(root == NULL) {
        *returnSize = 0;
        *returnColumnSizes = 0;
        return NULL;
    }

    struct TreeNode* queue[2000];
    int head, tail;
    head = tail = 0;
    queue[tail++] = root; // enqueue root

    int** ans = malloc(sizeof(int*) * 2000);
    int *levelSizes = malloc(sizeof(int) * 2000);
    int level = 0;

    while(tail - head > 0) {
        levelSizes[level] = tail - head;
        ans[level] = malloc(sizeof(int) * levelSizes[level]);
        for(int j = 0; j < levelSizes[level]; j++) {
            struct TreeNode *node = queue[head++]; // dequeue
            ans[level][j] = node->val;
            if(node->left != NULL) {
                queue[tail++] = node->left;
            }
            if(node->right != NULL) {
                queue[tail++] = node->right;
            }
        }
        level++;
    }

    *returnSize = level;
    *returnColumnSizes = levelSizes;
    return ans;
}

方法二：记录层号

#include "stdlib.h"
#include "stdbool.h"
#include "../tree.h"
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
typedef struct TreeNode TreeNode_t;

struct _ListNode {
    TreeNode_t *treeNode;
    int level;
    struct _ListNode *next;
};

typedef struct _ListNode ListNode_t;


typedef struct {
    ListNode_t* head;
    ListNode_t* tail;
    int size;
} Queue;

Queue* initQueue() {
    ListNode_t* dummy = malloc(sizeof(ListNode_t));
    dummy->treeNode = NULL;
    dummy->level = -1;
    dummy->next = NULL;

    Queue *queue = malloc(sizeof(Queue));
    queue->head = queue->tail = dummy;
    queue->size = 0;
    return queue;
}

bool isEmpty(Queue *queue) {
    return queue->size == 0;
}

void offer(Queue *queue, TreeNode_t* treeNode, int level) {
    ListNode_t* node = malloc(sizeof(ListNode_t));
    node->treeNode = treeNode;
    node->level = level;
    node->next = NULL;

    queue->tail->next = node;
    queue->tail = node;
    queue->size++;
}

ListNode_t* poll(Queue *queue) {
    if(queue->size == 0) {
        return NULL;
    }
    ListNode_t *node = queue->head->next;
    queue->head->next = node->next;
    queue->size--;
    if(isEmpty(queue)) {
        queue->tail = queue->head;
    }
    return node;
}

int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {
    if(root == NULL) {
        *returnSize = 0;
        *returnColumnSizes = 0;
        return NULL;
    }

    int **res = malloc(sizeof(int*) * 2000);
    int i = 0;
    int *levelSizes = malloc(sizeof(int) * 2000);
    *returnColumnSizes = levelSizes;

    Queue* queue = initQueue();
    offer(queue, root, 0);
    int *level =  malloc(sizeof(int*) * 1000);
    int j = 0;
    while(!isEmpty(queue)) {
        // 出队元素
        ListNode_t *node = poll(queue);
        // 如果元素所在层级不等于当前要收集的层级，将之前已收集的层级保存到结果中
        if(node->level != i) {
            res[i] = level;
            levelSizes[i] = j; // 记录这一层的节点数量
            i++;
            // 开始下一层级的收集
            level = malloc(sizeof(int*) * 1000);
            j = 0;
        }
        TreeNode_t *treeNode = node->treeNode;
        // 收集数值
        level[j++] = treeNode->val;
        // 将子节点入队
        if(treeNode->left != NULL) {
            offer(queue, treeNode->left, node->level + 1);
        }
        if(treeNode->right != NULL) {
            offer(queue, treeNode->right, node->level + 1);
        }
    }
    res[i] = level;
    levelSizes[i] = j; // 记录这一层的节点数量
    i++;
    *returnSize = i;
    return res;
}

方法三：由null来做每层的分隔

int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {
    if(root == NULL) {
        *returnSize = 0;
        *returnColumnSizes = 0;
        return NULL;
    }

    int** ans = malloc(sizeof(int*) * 2000);
    int *levelSizes = malloc(sizeof(int) * 2000);
    int level = 0;

    struct TreeNode* queue[4000];
    int head, tail;
    head = tail = 0;
    queue[tail++] = root; // enqueue root
    queue[tail++] = NULL; // enqueue level separator

    int *levelVals = malloc(sizeof(int));
    int j = 0;
    while(tail - head > 0) {
        struct TreeNode *node = queue[head++];
        if(node != NULL) {
            levelVals[j++] = node->val;
            if(node->left != NULL) {
                queue[tail++] = node->left;
            }
            if(node->right != NULL) {
                queue[tail++] = node->right;
            }
        } else {
            levelSizes[level] = j;  // record level size
            ans[level++] = levelVals;   // record level values
            levelVals = malloc(sizeof(int) * (tail - head)); // store next level
            j = 0; // index of next level
            if(tail > head) {
                queue[tail++] = NULL; // separator for next level
            }
        }
    }

    *returnSize = level;
    *returnColumnSizes = levelSizes;
    return ans;
}

递归解法

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        dfs(root, 0, ans);
        return ans;
    }

    // 标准DFS遍历二叉树
    public void dfs(TreeNode node, int level, List<List<Integer>> ans) {
        if(node == null) return;

        // 前序遍历
        if(ans.size() <= level) ans.add(new ArrayList<Integer>()); // 初始化收集当前层节点的集合
        ans.get(level).add(node.val);

        dfs(node.left, level + 1, ans);
        dfs(node.right, level + 1, ans);
    }
}

剑指 Offer 32 - III. 从上到下打印二叉树 III（之字形）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** decorateRecord(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {
    if(root == NULL) {
        *returnSize = 0;
        return NULL;
    }
    struct TreeNode **q1 = malloc(sizeof(struct TreeNode *) * 501);
    struct TreeNode **q2 = malloc(sizeof(struct TreeNode *) * 501);
    int top1, top2;
    top1 = top2 = 0;
    
    int **ans = malloc(sizeof(int *) * 1000);
    int level = 0;
    int *levelSizes = malloc(sizeof(int) * 1000);
    bool reverse = false;

    q1[top1++] = root;
    while(top1 > 0) {
        int *arr = malloc(sizeof(int) * top1);
        int index = 0;
        while(top1 > 0) {
            struct TreeNode *node = q1[--top1];
            arr[index++] = node->val;
            if(reverse) {
                if(node->right != NULL) q2[top2++] = node->right;
                if(node->left != NULL) q2[top2++] = node->left;
            } else {
                if(node->left != NULL) q2[top2++] = node->left;
                if(node->right != NULL) q2[top2++] = node->right;
            }
        }
        reverse = !reverse;
        levelSizes[level] = index;
        ans[level] = arr;
        level++;
        
        struct TreeNode **tmp = q1;
        q1 = q2;
        q2 = tmp;
        int tmp2 = top1;
        top1 = top2;
        top2 = tmp2;
    }

    free(q1);
    free(q2);
    *returnSize = level;
    *returnColumnSizes = levelSizes;
    return ans;
}

513. 找树左下角的值

找出该二叉树的 最底层 最左边 节点的值

• 从上到下按层遍历
• 扩展左右子树时，先右后左
• 如此，遍历到的最后一个一个节点就是“最底层、最左边”

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int findBottomLeftValue(struct TreeNode* root) {
    struct TreeNode *queue[10001];
    int left = -1, right = -1;
    queue[++right] = root;
    int result = 0;
    while(left != right) {
        struct TreeNode *node = queue[++left];
        result = node->val;
        if(node->right != NULL) queue[++right] = node->right;
        if(node->left != NULL) queue[++right] = node->left;
    }
    return result;
}

二叉树上的递归

104. 二叉树的最大深度

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int maxDepth(struct TreeNode* root) {
    if (root == NULL) return 0;
    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);
    return 1 + fmax(leftDepth, rightDepth);
}

559. N 叉树的最大深度

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     int numChildren;
 *     struct Node** children;
 * };
 */

int maxDepth(struct Node* root) {
    if(root == NULL) {
        return 0;
    }
    int maxChildDepth = 0;
    for(int i = 0; i < root->numChildren; i++) {
        int childDepth = maxDepth(root->children[i]);
        maxChildDepth = fmax(childDepth, maxChildDepth);
    }
    return maxChildDepth + 1;
}

110. 平衡二叉树

在《递归求解树的高度》算法基础上

• 通过左右子树高度计算每个节点高度时，可顺便判断每个节点的左右子树高度是否超过1

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int height(struct TreeNode* node, bool *balanced);

bool isBalanced(struct TreeNode* root) {
    bool balanced = true;
    height(root, &balanced);
    return balanced;
}

// 平衡二叉树：所有节点的左右子树的高度相差不超过1
// 如果左右子树分别都是平衡二叉树，无法推出根节点是平衡二叉树，因为左右子树高度差不确定
// 将问题转换为递归求解树高度，求每个节点的树高度时需要知道左右子树的高度，这时可以顺便判断该节点是否平衡
// 先写出递归求解树高度的模板，再添加判断平衡的逻辑
int height(struct TreeNode* node, bool *balanced) {
    if(node == NULL) return 0;

    int lh = height(node->left, balanced);
    if(*balanced == false) return 0; // 剪枝
    int rh = height(node->right, balanced); 
    
    // 知道左右子树高度后，顺便判断一下平衡
    if(abs(lh - rh) > 1) *balanced = false;

    return fmax(lh, rh) + 1;
}

617. 合并二叉树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* mergeTrees(struct TreeNode* root1, struct TreeNode* root2) {
    // 4. 递归终止条件
    if(root1 == NULL || root2 == NULL) return root1 == NULL ? root2 : root1;
    // 1. 假设左子树已经合并
    struct TreeNode* left = mergeTrees(root1->left, root2->left);
    // 2. 假设右子树已经合并
    struct TreeNode* right = mergeTrees(root1->right, root2->right);
    // 3. 合并根节点
    root1->val = root1->val + root2->val;
    root1->left = left;
    root1->right = right;
    return root1;
}

226. 翻转二叉树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* invertTree(struct TreeNode* root) {
    // 4. 递归终止条件
    if(root == NULL) return NULL;
    // 1. 假设左子树已经被翻转
    struct TreeNode* left = invertTree(root->left);
    // 2. 假设右子树已经被翻转
    struct TreeNode* right = invertTree(root->right);
    // 3. 翻转当前节点的左右子树
    root->left = right;
    root->right = left;
    return root;
}

※101. 对称二叉树

判断一个二叉树是否镜像对称 => 判断两个二叉树否镜像对称（去掉根节点，考虑其左右子树A、B）

• A.left 与 B.right 是否对称
• A.right 与 B.left 是否对称

递归理解：

• 遍历A：左中右
• 遍历B：右中左

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool check(struct TreeNode* p, struct TreeNode* q) {
    // 3. 两个树镜像的前提条件 根节点相同
    if(p == NULL && q == NULL) return true;
    if((p == NULL && q != NULL) || (p != NULL && q == NULL) || p->val != q->val) 
        return false;
    // 1. 假设已经知道p的左子树和q的右子树是否为镜像
    // 2. 假设已经知道p的右子树和q的左子树是否为镜像
    return check(p->left, q->right) && check(p->right, q->left);
}

bool isSymmetric(struct TreeNode* root) {
    // 判断左右子树是否镜像
    return check(root->left, root->right);
}

※98. 验证二叉搜索树

方法一：DFS过程中收集子树的最值

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
typedef struct {
    int min;
    int max;
} Info;

Info NULL_INFO = {0};

bool result;

Info dfs(struct TreeNode* root) {
    Info info = {root->val, root->val}; // 当前树的min,max默认为root.val
    if(root->left != NULL) { // 左子树不为空才遍历，不然返回的Info没有意义
        Info left = dfs(root->left);
        if(result == false) return NULL_INFO; // 剪枝
        if(left.max >= root->val) {
            result = false;
            return NULL_INFO;
        }
        if(left.min < info.min) info.min = left.min;
    }
    if(root->right != NULL) {
        Info right = dfs(root->right);
        if(result == false) return NULL_INFO;
        if(right.min <= root->val) {
            result = false;
            return NULL_INFO;
        }
        if(right.max > info.max) info.max = right.max;
        return info;
    }
    return info;
}

bool isValidBST(struct TreeNode* root) {
    if(root == NULL) return true;
    result = true;
    dfs(root);
    return result;
}

方法二：DFS过程中判断子树节点值是否满足开区间

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool check(struct TreeNode *root, long min, long max) {
    if(root == NULL) return true;
    // 检查根节点是否在(min, max)中
    if(root->val <= min || root->val >= max) return false;
    // 检查左子树是否满足(min, root->val)、右子树是否满足(root->val, max)
    return check(root->left, min, root->val) && check(root->right, root->val, max);
}

bool isValidBST(struct TreeNode* root) {
    // 如果知道左子树、右子树是BST，也无法推到当前根节点是否为BST
    // 因此在遍历树的过程中要顺带验证左子树节点是否都小于根节点、右子树节点是否都大于根节点
    return check(root->left, LONG_MIN, root->val) && check(root->right, root->val, LONG_MAX);
}

方法三：验证中序遍历结果是否升序

中序遍历为有序序列 <=> 二叉树为有效BST

二叉查找树

230. 二叉搜索树中第 K 小的元素

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
// BST的前序遍历序列为递增的有序序列，在遍历过程中，每访问一个节点就更新计数值便可找到第N小的节点
// 举一反三：找第K大的节点，按照右、中、左的顺序遍历即可
void traverse(struct TreeNode* root, int *k, int *target) {
    if(root == NULL) return;
    traverse(root->left, k, target);
    if(k == 0) return; // 剪枝
    (*k)--;
    if(*k == 0) {
        *target = root->val;
        return;
    }
    traverse(root->right, k, target);
}

int kthSmallest(struct TreeNode* root, int k) {
    int target = 0;
    traverse(root, &k, &target);
    return target;
}

LCR 174. 寻找二叉搜索树中的目标节点

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

void traverse(struct TreeNode* root, int *cnt, int *target) {
    if(root == NULL) return;
    traverse(root->right, cnt, target);
    if(*cnt == 0) return; // 剪枝
    (*cnt)--;
    if(*cnt == 0) {
        *target = root->val;
        return; // 剪枝
    }
    traverse(root->left, cnt, target);
}

int findTargetNode(struct TreeNode* root, int cnt) {
    int target;
    traverse(root, &cnt, &target);
    return target;
}

538. 把二叉搜索树转换为累加树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
void traverse(struct TreeNode* root, int *sum) {
    if(root == NULL) return;
    traverse(root->right, sum);
    *sum += root->val;
    root->val = *sum;
    traverse(root->left, sum);
}


struct TreeNode* convertBST(struct TreeNode* root) {
    int sum = 0;
    traverse(root, &sum);
    return root;
}

面试题 04.06. 后继者

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

void traverse(struct TreeNode* root, struct TreeNode* p, struct TreeNode** target) {
    if(root == NULL) return;
    traverse(root->left, p, target);
    if(*target != NULL) return; // 剪枝
    if(*target == NULL && root->val > p->val) {
        *target = root;
        return; // 剪枝
    }
    traverse(root->right, p, target);
}

struct TreeNode* inorderSuccessor(struct TreeNode* root, struct TreeNode* p){
    struct TreeNode* target = NULL;
    traverse(root, p, &target);
    return target;
}

LCA最近公共祖先

236. 二叉树的最近公共祖先

节点p和q最近公共祖先x节点的特征：

1. p和q不是互为祖孙关系时：p、q分别分布在x的不同子树上
2. p和q互为祖孙关系时：x为p和q中的祖先节点

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* target;
// dfs过程中记录树中包含p/q的数量, 返回值：树中包含p/q的数量
static int dfs(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    if(root == NULL) return 0;
    int left = dfs(root->left, p, q);
    if(target != NULL) return 0; //剪枝
    int right = dfs(root->right, p, q);
    // 左右子树分别有一个p/q => 命中
    if (left == 1 && right == 1) {
        target = root;
        return 2;
    }
    // 根节点为p/q，只有一个子树有一个p/q => 命中
    bool rootHit = (root == p || root == q);
    if(rootHit && (left == 1 || right == 1)) {
        target = root;
        return 2;
    }
    // 没有命中，计算当前树中包含的p/q数量
    return left + right + (rootHit ? 1 : 0);
}

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
   // 问题转化：在递归过程中找最近祖先节点 => 在递归过程中记录树中包含p/q的数量
   //   1. 左右子树分别包含一个p/q，根节点为最近祖先节点
   //   2. 只有一个子树包含了一个p/q，根节点为p/q，根节点为最近祖先节点
   target = NULL;
   dfs(root, p, q);
   return target;
}

剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* lca; // latest common ancestor

// 在遍历过程中记录树中包含p/q的情况, 返回值：树中包含p/q节点的数量
int dfs(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    if(root == NULL) return 0;
    int left = dfs(root->left, p, q);
    if(lca) return 2; // 剪枝
    int right = dfs(root->right, p, q);
    // 如果左右子树各有一个p/q节点，则当前节点为LCA
    if(left == 1 && right == 1) {
        lca = root;
        return 2;
    }
    // 如果当前节点为p/q，且子树中有p/q，则当前节点为LCA
    bool rootHit = root == p || root == q;
    if(rootHit && (left == 1 || right == 1)) {
        lca = root;
        return 2;
    }
    return left + right + (rootHit ? 1 : 0);
}

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    lca = NULL;    
    dfs(root, p, q);
    return lca;
}

二叉树转单、双、循环链表

114. 二叉树展开为链表

• 构建链表技巧：dummyHead+append
• 在遍历过程中，将节点从树中剥离出来插入链表中；由于剥离会改变节点的left/right指针，因此需要事先保存相关引用

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* dummyHead;
struct TreeNode* tail; // tail insertion 

void dfs(struct TreeNode* root) {
    if(root == NULL) return;
    // save left/right subtree
    struct TreeNode* left = root->left;
    struct TreeNode* right = root->right;
    // insert node into linkedlist
    root->left = root->right = NULL;
    tail->right = root;
    tail = root;
    dfs(left);
    dfs(right);
}

void flatten(struct TreeNode* root) {
    dummyHead = malloc(sizeof(struct TreeNode));
    dummyHead->left = dummyHead->right = NULL;
    tail = dummyHead;
    dfs(root);
    free(dummyHead);
}

面试题 17.12. BiNode

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* dummyHead;
struct TreeNode* tail;

//把二叉搜索树转换为单向链表，要求依然符合二叉搜索树的性质
//即转换后的链表为BST的中序遍历序列
//通过中序遍历将节点依次加入结果链表即可满足要求
void inorder(struct TreeNode* root) {
    if(root == NULL) return;
    inorder(root->left);
    // 处理节点时机：中序遍历
    struct TreeNode* right = root->right;
    root->left = root->right = NULL;
    tail->right = root;
    tail = root;
    inorder(right);
}

struct TreeNode* convertBiNode(struct TreeNode* root) {
    dummyHead = malloc(sizeof(struct TreeNode));
    dummyHead->left = dummyHead->right = NULL;
    tail = dummyHead;

    inorder(root);
    struct TreeNode* result = dummyHead->right;
    free(dummyHead);
    return result;
}

剑指 Offer 36. 二叉搜索树与双向链表

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
// 已排序 => BST中序遍历序列
class Solution {
    Node* dummyHead;
    Node* tail;
public:
    Node* treeToDoublyList(Node* root) {
        if(root == NULL) return NULL;
        tail = dummyHead = new Node();
        dummyHead->left = dummyHead->right = NULL;
        inorder(root);
        Node* result = link(dummyHead->right, tail);
        delete dummyHead;
        return result;
    }
    void inorder(Node* root) {
        if(root == NULL) return;
        inorder(root->left);
        Node* right = root->right;
        root->left = root->right = NULL;
        tail->right = root;
        tail = root;
        inorder(right);
    }
    Node* link(Node* head, Node* tail) {
        Node* pre = tail;
        Node* p = head;
        while(p != tail) {
            p->left = pre;
            pre = p;
            p = p->right;
        }
        p->left = pre;
        p->right = head;
        return head;
    }
};

面试题 04.03. 特定深度节点链表

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
struct ListNode** result;
int resultSize;

struct ListNode** listOfDepth(struct TreeNode* tree, int* returnSize) {
    result = malloc(sizeof(struct ListNode*) * 1000);
    resultSize = 0;

    struct TreeNode* queue[1000];
    int queueHead, queueTail;
    queueHead = queueTail = -1;
    queue[++queueTail] = tree;

    while(queueTail > queueHead) {
        // 收集当前深度的所有节点
        int count = queueTail - queueHead;
        struct ListNode* dummy = malloc(sizeof(struct ListNode));
        struct ListNode* listTail = dummy;
        for(int i = 0; i < count; i++) {
            struct TreeNode* node = queue[++queueHead];
            // 子节点加入队列
            if(node->left) queue[++queueTail] = node->left;
            if(node->right) queue[++queueTail] = node->right;
            // 当前节点加入链表
            struct ListNode* p = malloc(sizeof(struct ListNode));
            p->val = node->val;
            p->next = NULL;
            listTail->next = p;
            listTail = p;
        }
        result[resultSize++] = dummy->next;
        free(dummy);
    }

    *returnSize = resultSize;
    return result;
}

按照遍历结果反向构建二叉树

105. 从前序与中序遍历序列构造二叉树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
// 前序区间[i,j] 中序区间[m,n]
struct TreeNode* myBuildTree(int* preorder, int i, int j, int* inorder, int m, int n)  {
    // 4. 递归终止条件
    if(i > j) return NULL;
    struct TreeNode* root = malloc(sizeof(struct TreeNode));
    // 3. 构建左右子树，需要确定前序/中序遍历序列中左右子树的区间
    // 前序遍历的第一个节点就是根节点，找到该节点在中序遍历中的位置后可确认左右子树的区间
    root->val = preorder[i];
    int p = m;
    while(inorder[p] != root->val) p++;
    int leftSize = p - m;
    // [i, j] => [i,i] [i+1, i+leftSize] [i+leftSize+1, j]
    // [m, n] => [m, p-1] [p,p] [p+1, n]
    // 1. 假设左子树构建好了
    root->left = myBuildTree(preorder, i + 1, i + leftSize, inorder, m, p - 1);
    // 2. 假设右子树构建好了
    root->right = myBuildTree(preorder, i + leftSize + 1, j, inorder, p + 1, n);
    return root;
}
struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize) {
    return myBuildTree(preorder, 0, preorderSize - 1, inorder, 0, inorderSize - 1);
}

889. 根据前序和后序遍历构造二叉树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
// preorder 先根后左右 postorder 先左右后根，重点：划分出左右子树对应的子序列
struct TreeNode* dfs(int* preorder, int i, int j, int* postorder, int m, int n) {
    if(i > j) return NULL;
    struct TreeNode* root = malloc(sizeof(struct TreeNode));
    root->val = preorder[i];
    if(i == j) {
        root->left = root->right = NULL;
        return root;
    }
    int leftRoot = preorder[i + 1];
    int p = m;
    while(postorder[p] != leftRoot) p++;
    int leftCnt = p - m + 1;
    // [i, j] => [i] [i+1, i+leftCnt] [i+leftCnt+1, j]
    // [m, n] => [m, p] [p+1, n-1] [n]
    root->left = dfs(preorder, i + 1, i + leftCnt, postorder, m, p);
    root->right = dfs(preorder, i + leftCnt + 1, j, postorder, p + 1, n - 1);
    return root;
}

struct TreeNode* constructFromPrePost(int* preorder, int preorderSize, int* postorder, int postorderSize) {
    return dfs(preorder, 0, preorderSize - 1, postorder, 0, postorderSize - 1);
}

106. 从中序与后序遍历序列构造二叉树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* dfs(int* inorder, int i, int j, int* postorder, int m, int n) {
    if(i > j) return NULL;
    int val = postorder[n];
    int p = i;
    while(inorder[p] != val) ++p;
    int left = p - i;
    struct TreeNode* root = malloc(sizeof(struct TreeNode));
    root->val = val;
    // [i, j] => [i, p - 1], [p], [p + 1, j]
    // [m, n] => [m, m + left - 1], [m + left, n - 1],[n]
    root->left = dfs(inorder, i, p - 1, postorder, m, m + left - 1);
    root->right = dfs(inorder, p + 1, j, postorder, m + left, n - 1);
    return root;
}
struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize) {
    return dfs(inorder, 0, inorderSize - 1, postorder, 0, postorderSize - 1);
}

剑指 Offer 33. 二叉搜索树的后序遍历序列

typedef struct {
    int min;
    int max;
} DFSInfo;
bool isBST = true;
// 后根遍历的特点：先左右、后根节点
// BST的特点：左子树都比根小、右子树都比根大
// 如果找到区间[i, j]中第一个比根大的节点p，那么[i, p - 1]为左子树序列，[p, j - 1]为右子树序列
DFSInfo dfs(int* postorder, int i, int j) {
    int p = i;
    int root = postorder[j];
    DFSInfo info = {root, root};
    while(postorder[p] < root) ++p;
    if(p > i) { // 左子树存在
        DFSInfo left = dfs(postorder, i, p - 1);
        if(left.max > root) {
            isBST = false;
            return info;
        }
        info.min = left.min;
    }
    if(isBST == false) return info; // 剪枝
    if(p != j) { // 右子树存在
        DFSInfo right = dfs(postorder, p, j - 1);
        if(right.min < root) {
            isBST = false;
            return info;
        }
        info.max = right.max;
    }
    return info;
}
bool verifyTreeOrder(int* postorder, int postorderSize) {
    if(postorderSize <= 1) {
        return true;
    }
    isBST = true;
    dfs(postorder, 0, postorderSize - 1);
    return isBST;
}

二叉树上的最长路径和

543. 二叉树的直径

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int result;
// 最长路径肯定出现在某个子树上且经过该子树的根节点
int dfs(struct TreeNode* root) {
    if(root == NULL) return 0;
    int leftHeight = dfs(root->left);
    int rightHeight = dfs(root->right);
    int maxPath = (leftHeight + rightHeight + 1) - 1; // 边数=节点数-1
    if(maxPath > result) result = maxPath;
    return fmax(leftHeight, rightHeight) + 1;
}
int diameterOfBinaryTree(struct TreeNode* root) {
    result = -1;
    dfs(root);
    return result;
}

剑指 Offer 34. 二叉树中和为某一值的路径

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int* result[2500];
int resultCnt;
int resultColSize[2500];

int* takeSnapshot(int path[], int pathSize) {
    int* result = malloc(sizeof(int) * pathSize);
    memcpy(result, path, sizeof(int) * pathSize);
    return result;
}

void dfs(struct TreeNode* root, int target, int path[], int *pathSize, int pathSum)  {
    if(root == NULL) return;
    // 第一次来到该节点，将节点添加到路径中
    pathSum += root->val;
    path[*pathSize] = root->val;
    (*pathSize)++;
    // 如果该节点为叶子节点，判断路径和是否命中target
    if(root->left == NULL && root->right == NULL && pathSum == target) {
        result[resultCnt] = takeSnapshot(path, *pathSize);
        resultColSize[resultCnt] = *pathSize;
        resultCnt++;
    }

    dfs(root->left, target, path, pathSize, pathSum);
    // 第二次来到该节点
    dfs(root->right, target, path, pathSize, pathSum);
    // 第三次来到该节点，在出栈该节点前将其从路径中移除
    (*pathSize)--;
}
int** pathTarget(struct TreeNode* root, int target, int* returnSize, int** returnColumnSizes) {
    resultCnt = 0;
    int path[5000];
    int pathSize = 0;
    dfs(root, target, path, &pathSize, 0);
    *returnSize = resultCnt;
    *returnColumnSizes = resultColSize;
    return result;
}

124. 二叉树中的最大路径和

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int result;
int dfs(struct TreeNode* root) {
    if(root == NULL) return 0;
    // 得到左子树能够提供的最大路径和（非负）
    int left = dfs(root->left); 
    // 得到右子树能够提供的最大路径和（非负）
    int right = dfs(root->right); 
    int rootVal = root->val;
    // 计算当前树的最大路径和
    int maxPathSum = left + right + rootVal;
    result = fmax(result, maxPathSum);
    // 返回当前子树能向父节点提供的最大路径和
    return fmax(fmax(rootVal + left, rootVal + right), 0);
}
int maxPathSum(struct TreeNode* root) {
    result = INT_MIN;
    dfs(root);
    return result;
}

堆（优先级队列）

基础知识

堆上的操作

堆排序

215. 数组中的第K个最大元素

// 根据父节点索引i找左右子节点的索引
#define CHILD_LEFT(i) (2 * i + 1)
#define CHILD_RIGHT(i) (2 * i + 2)
// 找左右子节点的索引i找父节点的索引
#define PARENT_PARENT(i) ((i - 1) / 2)

void swap(int *nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

// 自上而下进行堆化：将index节点与其左右子节点比较，并于较大者交换，向下递归该过程直到节点大于左右子节点
void heapify(int *nums, int size, int index) { 
    while(1) {
        int greater = index; // 保存父节点、左右子节点之间较大者的索引
        int left = CHILD_LEFT(index), right = CHILD_RIGHT(index);
        if(left >= size)  return;
        if(nums[left] > nums[greater]) greater = left;
        if(right < size && nums[right] > nums[greater]) greater = right;
        if(greater == index) return; // 终止向下递归的堆化过程
        swap(nums, greater, index);
        index = greater; // 子节点作为新一轮堆化的父节点
    }
}

// 由数组索引从后向前进行堆化O(n)，比从前向后堆化效率高O(nlogn)
void buildHeap(int *nums, int size) {
    for(int index = size / 2; index >= 0; index--) { // 叶子节点不需要向下堆化，因此索引从size/2开始
        heapify(nums, size, index);
    }
}

int heapDelete(int *nums, int size) {
    swap(nums, 0, size - 1);
    heapify(nums, size - 1, 0);
    return nums[size - 1];
}

int findKthLargest(int* nums, int numsSize, int k) {
    if(numsSize <= 0 || k > numsSize) return -1;
    buildHeap(nums, numsSize);
    for(int i = 0; i < k; i++) {
        int val = heapDelete(nums, numsSize - i);
        if(i == k - 1) {
            return val;
        }
    }
    return -1;
}

优先级队列

23. 合并K个升序链表

// 根据父节点索引i找左右子节点的索引
#define CHILD_LEFT(i) (2 * i + 1)   
#define CHILD_RIGHT(i) (2 * i + 2)
#define PARENT(i) ((i - 1) / 2) // 根据子节点索引找父节点索引

void swap(struct ListNode* nodes[], int i, int j) {
    struct ListNode* tmp = nodes[i];
    nodes[i] = nodes[j];
    nodes[j] = tmp;
}

// 小顶堆：将数组中index上的节点向下堆化，直到该节点比左右子节点小
void heapify(struct ListNode* nodes[], int size, int index) { 
    while(1) {
        int lower = index; // 记录此次比较中，index节点及其子节点中值最小的节点索引
        int left = CHILD_LEFT(index), right = CHILD_RIGHT(index);
        if(left >= size)  return;
        if(nodes[left]->val < nodes[lower]->val) lower = left; // 左子节点更小，更新lower
        if(right < size && nodes[right]->val < nodes[lower]->val) lower = right; // 右子节点更小，更新lower
        if(lower == index) return; // index节点比左右子节点都小，不需要向下堆化了
        swap(nodes, lower, index);
        index = lower; // 发生了交换，尝试继续向下堆化
    }
}

// 由数组索引从后向前进行堆化O(n)，比从前向后堆化效率高O(nlogn)
void buildHeap(struct ListNode* nodes[], int size) {
    for(int index = size / 2; index >= 0; index--) { // 叶子节点不需要向下堆化，因此索引从size/2开始
        heapify(nodes, size, index);
    }
}

// 删除堆顶元素：将堆顶与末尾元素交换，size--表示删除，新的堆顶元素重新自上而下堆化
struct ListNode* heapDelete(struct ListNode* nodes[], int size) { 
    swap(nodes, 0, size - 1);
    heapify(nodes, size - 1, 0);
    return nodes[size - 1];
}

// 新增元素到堆中，先添加到数组末尾，然后自下而上进行堆化
void heapInsert(struct ListNode* nodes[], int index) {
    while(index > 0) { // 有父节点
        int parent = (index - 1) / 2;
        if(nodes[index]->val < nodes[parent]->val) {
            swap(nodes, index, parent);
            index = parent;
        } else { 
            break;
        }
    }
}

struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
    if(listsSize == 0) return NULL;
    struct ListNode* dummy = malloc(sizeof(struct ListNode));
    struct ListNode* tail = dummy; // 结果链表的头和尾
    struct ListNode** heap = malloc(sizeof(struct ListNode) * listsSize);
    int size = 0; // 堆大小
    for(int i = 0; i < listsSize; i++) {
        if(lists[i]) {
            heap[size++] = lists[i];
        }
    }

    if(size > 0) {
        buildHeap(heap, size);
        while(size > 0) {
            struct ListNode* node = heapDelete(heap, size);
            size--;
            tail->next = node;
            tail = node;
            if(node->next) {
                heap[size] = node->next;
                heapInsert(heap, size);
                size++;
            }
        }
    }

    tail->next = NULL;
    struct ListNode* result = dummy->next;
    free(dummy);
    return result;
}

TopK

347. 前 K 个高频元素

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        if (nums.length == 0) return new int[]{};
        HashMap<Integer, Integer> cntMap = new HashMap<>();
        for (int num : nums) {
            cntMap.merge(num, 1, Integer::sum);
        }
        PriorityQueue<Map.Entry<Integer, Integer>> heap = 
                new PriorityQueue<>(k, Comparator.comparingInt(Map.Entry::getValue));

        for (Map.Entry<Integer, Integer> entry : cntMap.entrySet()) {
            if (heap.size() < k) {
                heap.add(entry);
                continue;
            }
            if (entry.getValue() > heap.peek().getValue()) {
                heap.poll();
                heap.add(entry);
            }
        }

        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = heap.poll().getKey();
        }
        return res;
    }        
}

295. 数据流的中位数

class MedianFinder {
    PriorityQueue<Integer> maxHeap;
    PriorityQueue<Integer> minHeap;

    public MedianFinder() {
        maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
        minHeap = new PriorityQueue<>();
    }

    public void addNum(int num) {
        if (minHeap.isEmpty() || num > minHeap.peek()) {
            minHeap.add(num);
            if (minHeap.size() - maxHeap.size() > 1) {
                maxHeap.add(minHeap.poll());
            }
        } else {
            maxHeap.add(num);
            if (maxHeap.size() > minHeap.size()) {
                minHeap.add(maxHeap.poll());
            }
        }
    }

    public double findMedian() {
        if (maxHeap.size() == 0) return minHeap.peek();
        if (maxHeap.size() == minHeap.size()) return (double) (minHeap.peek() + maxHeap.peek()) / 2;
        return minHeap.peek();
    }
}

973. 最接近原点的 K 个点

208. 实现 Trie (前缀树)

Java

class Trie {
    char ch;
    Trie[] children = new Trie[26];
    boolean isEnding = false;
    public Trie() {
    }
    public Trie(char ch) {
        this.ch = ch;
    }
    
    public void insert(String word) {
        if(word == null || word.length() == 0) return;
        Trie p = this;
        for(int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';
            if(p.children[index] == null) {
                p.children[index] = new Trie(ch);
            }
            p = p.children[index];
        }
        p.isEnding = true;
    }

    public Trie findNode(String word) {
        if(word == null || word.length() == 0) return null;
        Trie p = this;
        for(int i = 0; i < word.length(); i++) {
            Trie child = p.children[word.charAt(i) - 'a'];
            if(child == null) return null;
            p = child;
        }
        return p;
    }
    
    public boolean search(String word) {
        Trie node = findNode(word);
        return node != null && node.isEnding;
    }
    
    public boolean startsWith(String prefix) {
        return findNode(prefix) != null;
    }
}

C

#define index(ch) (ch - 'a')
typedef struct {
    char ch;
    bool isEnding;
    void* children[26];
} Trie;

Trie* nodeCreate(char ch) {
    Trie* node = malloc(sizeof(Trie));
    node->ch = ch;
    node->isEnding = false;
    for(int i = 0; i < 26; i++) node->children[i] = NULL;
    return node;
}

Trie* trieCreate() {
    return nodeCreate('/');
}

void trieInsert(Trie* obj, char* word) {
    if(obj == NULL || word == NULL) return;
    Trie* p = obj;
    while(*word) {
        if(!p->children[index(*word)]) {
            p->children[index(*word)] = nodeCreate(*word);
        }
        p = p->children[index(*word)];
        word++;
    }
    p->isEnding = true;
}

Trie* findNode(Trie* root, char* word) {
    if(root == NULL || word == NULL) return NULL;
    Trie* p = root;
    while(*word) {
        if(!p->children[index(*word)]) return NULL;
        p = p->children[index(*word)];
        word++;
    }
    return p;
}

bool trieSearch(Trie* obj, char* word) {
    Trie* node = findNode(obj, word);
    return node != NULL && node->isEnding == true;
}

bool trieStartsWith(Trie* obj, char* prefix) {
    return findNode(obj, prefix) != NULL;
}

void trieFree(Trie* obj) {
    if(obj == NULL) return;
    for(int i = 0; i < 26; i++) trieFree(obj->children[i]);
    free(obj);
}

/**
 * Your Trie struct will be instantiated and called as such:
 * Trie* obj = trieCreate();
 * trieInsert(obj, word);
 
 * bool param_2 = trieSearch(obj, word);
 
 * bool param_3 = trieStartsWith(obj, prefix);
 
 * trieFree(obj);
*/

面试题 17.17. 多次搜索

class Trie {
    char ch;
    Trie[] children = new Trie[26];
    String word;
    public Trie() {
    }
    public Trie(char ch) {
        this.ch = ch;
    }
    public void insert(String word) {
        if(word == null || word.length() == 0) return;
        Trie p = this;
        for(int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';
            if(p.children[index] == null) {
                p.children[index] = new Trie(ch);
            }
            p = p.children[index];
        }
        p.word = word;
    }
    public List<String> search(String word) {
        if(word == null || word.length() == 0) return null;
        List<String> hits = new ArrayList<>();
        Trie p = this;
        for(int i = 0; i < word.length(); i++) {
            Trie child = p.children[word.charAt(i) - 'a'];
            if(child == null) break;
            if(child.word != null) hits.add(child.word);
            p = child;
        }
        return hits;
    }
}
class Solution {
    public int[][] multiSearch(String big, String[] smalls) {
        Trie trie = new Trie();
        for(String small: smalls) trie.insert(small);
        Map<String, List<Integer>> hits = new HashMap<>();
        for(int i = 0; i < big.length(); i++) {
            List<String> matchList = trie.search(big.substring(i));
            if(matchList == null) continue;
            for(String match: matchList) {
                if(!hits.containsKey(match)) {
                    hits.put(match, new ArrayList());
                }
                hits.get(match).add(i);
            }
        }

        int[][] res = new int[smalls.length][];
        for(int i = 0; i < res.length; i++) {
            if(hits.containsKey(smalls[i])) {
                res[i] = hits.get(smalls[i]).stream().mapToInt(Integer::intValue).toArray();;
            } else {
                res[i] = new int[0];
            }
        }
        return res;
    }
}

212. 单词搜索 II

class Solution {
    int[][] dirs = new int[][]{{-1, 0},{1,0},{0,-1},{0,1}};
    public List<String> findWords(char[][] board, String[] words) {
        Trie trie = new Trie();
        for(String word: words) trie.insert(word);
        Set<String> res = new HashSet<>();
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                dfs(board, trie, i, j, res);
            }
        }
        return new ArrayList(res);
    }

    public void dfs(char[][] board, Trie now, int i, int j, Set<String> res) {
        char ch = board[i][j];
        if(ch == '#') return;
        Trie child = now.children[ch - 'a'];
        if(child == null)  return;
        Optional.ofNullable(child.word).ifPresent(res::add);
        board[i][j] = '#'; // 同一个单元格内的字母在一个单词中不允许被重复使用
        for(int k = 0; k < dirs.length; k++) {
            int i1 = i + dirs[k][0];
            int j1 = j + dirs[k][1];
            if(i1 >= 0 && i1 < board.length && j1 >= 0 && j1 < board[0].length) {
                dfs(board, child, i1, j1, res);
            }
        }
        board[i][j] = ch;
    }
}

class Trie {
    char ch;
    Trie[] children = new Trie[26];
    String word;
    public Trie() {
    }
    public Trie(char ch) {
        this.ch = ch;
    }
    public void insert(String word) {
        if(word == null || word.length() == 0) return;
        Trie p = this;
        for(int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';
            if(p.children[index] == null) {
                p.children[index] = new Trie(ch);
            }
            p = p.children[index];
        }
        p.word = word;
    }
}

回溯

多阶段决策模型

经典问题

排列

组合

八皇后问题

0-1背包问题

正则匹配

练习

面试题 08.12. 八皇后

class Solution {
    List<List<String>> res = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        char[][] board = new char[n][n];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                board[i][j] = '.';
            }
        }
        backtrack(board, 0, n);
        return res;
    }

    /**
     * 可选列表：board上row行的所有列
     * 决策阶段：第row行该如何摆放一个皇后
     * 路径：已决策路径通过"Q"记录在board中
     */
    public void backtrack(char[][] board, int row, int n) {
        if(row == n) { // 结束条件（所有决策都已完成）
            res.add(snapshot(board)); // 如果所有阶段都成功做了决策，则说明是一个可行解
            return;
        }
        if(res != null)
            for(int j = 0; j < n; j++) { // 可选列表，尝试选择row行所有列
                if(isOk(board, row, j)) { // 需要满足不同列、不同对角线
                    board[row][j] = 'Q'; // 做选择
                    backtrack(board, row + 1, n); // 下一阶段决策
                    board[row][j] = '.'; // 撤销选择，回溯到上一阶段
                }
            }
    }

    public boolean isOk(char[][] board, int i, int j) {
        for(int k = 0; k < i; k++) { // 检查正上方是否有皇后
            if(board[k][j] == 'Q') return false;
        }
        int m = i - 1, n = j - 1; // 检查左上对角线是否有皇后
        while(m >= 0 && n >= 0) {
            if(board[m][n] == 'Q') return false;
            m--;
            n--;
        }
        m = i - 1;
        n = j + 1; // 检查右上对角线是否有皇后
        while(m >= 0 && n < board.length) {
            if(board[m][n] == 'Q') return false;
            m--;
            n++;
        }
        return true;
    }

    public List<String> snapshot(char[][] board) {
        List<String> list = new ArrayList(board.length);
        for(int i = 0; i < board.length; i++) list.add(new String(board[i]));
        return list;
    }
}

37. 解数独

class Solution {
    Set<Character> nums = new HashSet(Arrays.asList('1', '2', '3', '4', '5', '6', '7', '8', '9'));
    char[][] res = null;
    public void solveSudoku(char[][] board) {
        List<int[]> blankPoints = new ArrayList<>();
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board.length; j++) {
                if(board[i][j] == '.') blankPoints.add(new int[]{i, j});
            }
        }
        backtrack(board, blankPoints, 0);
        arrayCopy(res, board);
    }

    // blankPoints：空格点列表，每个元素为(x,y)，p：阶段（第几个空格放什么）
    public void backtrack(char[][] board, List<int[]> blankPoints, int p) {
        if(p == blankPoints.size()) { // 结束条件：所有空格已决策完成
            res = snapshot(board);
            return;
        }
        if(res != null) return;
        int[] point = blankPoints.get(p);
        Set<Character> options = optionalList(board, point); // 获取可选列表
        if(options.isEmpty()) return;
        for(char ch: options) {
            board[point[0]][point[1]] = ch; // 做选择
            backtrack(board, blankPoints, p + 1); // 下一阶段决策
            board[point[0]][point[1]] = '.'; // 返回上一阶段之前撤销选择
        }
    }

    public void arrayCopy(char[][] src, char[][] dest) {
        for(int i = 0; i < src.length; i++) {
            for(int j = 0; j < src.length; j++) {
                dest[i][j] = src[i][j];
            }
        }
    }

    public char[][] snapshot(char[][] board) {
        char[][] tmp = new char[board.length][board.length];
        arrayCopy(board, tmp);
        return tmp;
    }

    public Set<Character> optionalList(char[][] board, int[] point) {
        Set<Character> options = new HashSet<>(nums);
        int i = point[0], j = point[1];
        for(int k = 0; k < board.length; k++) { // 移除同行、同列上已出现过的数字
            if(board[i][k] != '.') options.remove(board[i][k]);
            if(board[k][j] != '.') options.remove(board[k][j]);
        }
        // 计算point所在3x3宫的左上角、右下角坐标
        int startI = i / 3 * 3, startJ = j / 3 * 3, endI = (i / 3 + 1) * 3, endJ = (j / 3 + 1) *3;
        for(int m = startI; m < endI; m++) { 
            for(int n = startJ; n < endJ; n++) {
                if(board[m][n] != '.') options.remove(board[m][n]); // 3x3宫内出现过的数字
            }
        }
        return options;
    }
}

17. 电话号码的字母组合

class Solution {
    char[][] map = new char[][] {
        {'a', 'b', 'c'},   // 数字 2 映射的字母
        {'d', 'e', 'f'},   // 数字 3 映射的字母
        {'g', 'h', 'i'},   // 数字 4 映射的字母
        {'j', 'k', 'l'},   // 数字 5 映射的字母
        {'m', 'n', 'o'},   // 数字 6 映射的字母
        {'p', 'q', 'r', 's'}, // 数字 7 映射的字母
        {'t', 'u', 'v'},   // 数字 8 映射的字母
        {'w', 'x', 'y', 'z'}  // 数字 9 映射的字母
    };
    List<String> res = new ArrayList<>();
    public List<String> letterCombinations(String digits) {
        if(digits == null || digits.length() == 0) return res;
        backtrack(digits, 0, new ArrayList<>());
        return res;
    }

    // 可选列表，数字对应的可选字母； 阶段：p；路径：path，记录已选择字母
    public void backtrack(String digits, int p, List<Character> path) { 
        if(p == digits.length()) { // 所有数字已完成决策，将路径添加到结果中
            String strpath = path.stream().map(String::valueOf).collect(Collectors.joining());
            res.add(strpath);
            return;
        }
        // 当前可选列表
        char[] chs = map[digits.charAt(p) - '2'];
        for(char ch: chs) {
            path.add(p, ch); // 当前阶段选择
            backtrack(digits, p + 1, path); // 下一阶段决策
            path.remove(p); // 回溯前撤销选择
        }
    }
}

77. 组合

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        backtrack(1, n, k, 0, new HashSet<>());
        return res;
    }

    // 可选列表：[start, end]中不在path中的数字；阶段：p；路径：path，已选择的数字
    public void backtrack(int start, int end, int k, int p, Set<Integer> path) {
        if(p == k) {
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i = start; i <= end; i++) { // 当前决策有[start, end]种选择
            path.add(i); // 做选择
            // 选择i之后，将可选列表缩小为[i+1, end]
            // 组合不考虑排序的情况，因此只记录同一种组合中升序排列的情况
            backtrack(i + 1, end, k, p + 1, path); 
            path.remove(i); // 撤销选择
        }
    }
}

78. 子集

class Solution {
    public List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        backtrack(nums, 0, new ArrayList<>());
        return res;
    }

    // p阶段可选列表：选择nums[p]、不选择nums[p]
    // path：已选择的数字的路径
    public void backtrack(int[] nums, int p, List<Integer> path) {
        // 2. 结束条件：所有阶段决策已完成
        if(p == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        // 1. 当前阶段决策
        backtrack(nums, p + 1, path); // 不选择nums[p]
        path.add(nums[p]); // 选择nums[p]
        backtrack(nums, p + 1, path);
        path.remove(path.size() - 1); // 撤销选择
    }
}

90. 子集 II

class Solution {
    public List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        backtrack(nums, 0, new ArrayList<>(), false);
        return res;
    }

    // p阶段可选列表：选择nums[p]、不选择nums[p]
    // path：已选择的数字的路径；choosePre上一阶段是否选择了数字
    public void backtrack(int[] nums, int p, List<Integer> path, boolean choosePre) {
        // 2. 结束条件：所有阶段决策已完成
        if(p == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        // 1. 当前阶段决策
        backtrack(nums, p + 1, path, false); // 不选择nums[p]
        // 由于数组中有重复元素，为了避免生成重复子集，这里需要判断下
        // 如果前一个数和当前数相等，并且在上一阶段中没有被，那么选择当前数会导致生成重复子集，因此剪枝
        if(!choosePre && p - 1 >= 0 && nums[p - 1] == nums[p]) return;
        path.add(nums[p]); // 选择nums[p]
        backtrack(nums, p + 1, path, true);
        path.remove(path.size() - 1); // 撤销选择
    }
}

46. 全排列

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        backtrack(nums, 0, new ArrayList());
        return res;
    }

    // 可选列表：剩下的未选择的数字；阶段：当前阶段选择剩下的哪个数字；路径记录：已选择的列表
    public void backtrack(int[] nums, int p, List<Integer> path) {
        if(p == nums.length) {
            res.add(new ArrayList(path));
            return;
        }
        for(int i = 0; i < nums.length; i++) {
            if(path.contains(nums[i])) continue;
            path.add(nums[i]);
            backtrack(nums, p + 1, path);
            path.remove(path.size() - 1);
        }
    }
}

47. 全排列 II

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        int[] visit = new int[nums.length];
        backtrack(nums, visit, 0, new ArrayList<>());
        return res;
    }

    public void backtrack(int[] nums, int[] visit, int p, List<Integer> path) {
        if(p == nums.length) {
            res.add(new ArrayList(path));
            return;
        }
        for(int i = 0; i < nums.length; i++) {
            if(visit[i] == 1) continue;
            // 确保相邻重复元素被添加到路径中时，是重复序列中从左到右未被添加序列的第一个
            // 假设我们有 3 个重复数排完序后相邻，那么我们一定保证每次都是拿从左往右第一个未被填过的数字，即整个数组的状态其实是保证了 [未填入，未填入，未填入] 到 [填入，未填入，未填入]，再到 [填入，填入，未填入]，最后到 [填入，填入，填入] 的过程的，因此可以达到去重的目标。
            if(i > 0 && nums[i] == nums[i - 1] && visit[i - 1] == 0) continue;
            path.add(nums[i]);
            visit[i] = 1;
            backtrack(nums, visit, p + 1, path);
            path.remove(path.size() - 1);
            visit[i] = 0;
        }
    }
}

39. 组合总和

class Solution {
    List<List<Integer>> res;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        res = new ArrayList<>();
        backtrack(candidates, target, 0, new ArrayList<>());
        return res;
    }

    // 从左到右，每个数字都可以选择或不选择
    public void backtrack(int[] candidates, int target, int idx, List<Integer> combine) {
        // 结束条件：所有数字都已完成决策 或 目标达成
        if(idx == candidates.length) return; 
        if(target == 0) {
            res.add(new ArrayList<>(combine));
            return;
        }
        // 不选择
        backtrack(candidates, target, idx + 1, combine); 
        // 选择（有必要时才选择）
        if(target - candidates[idx] >= 0) {
            combine.add(candidates[idx]);
            backtrack(candidates, target - candidates[idx], idx, combine); // idx可以重复选择
            combine.remove(combine.size() - 1);
        }
    }
}

40. 组合总和 II

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        backtrack(candidates, target, 0, new ArrayList<>(), false);
        return res;
    }

    public void backtrack(int[] candidates, int target, int idx, List<Integer> path, boolean choosePre) {
         if(target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        if(idx == candidates.length) return;
        // 不选择，直接跳过candidates[idx]
        backtrack(candidates, target, idx + 1, path, false);
        // 选择，需要考虑相邻重复序列
        if(target - candidates[idx] < 0) return;
        if(idx > 0 && candidates[idx - 1] == candidates[idx] && choosePre == false) return;
        path.add(candidates[idx]);
        backtrack(candidates, target - candidates[idx], idx + 1, path, true);
        path.remove(path.size() - 1);
    }
}

216. 组合总和 III

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    // 从1-9中选出k个数，使相加之和为n
    public List<List<Integer>> combinationSum3(int k, int n) {
        int min = (k + 1) * k / 2;
        if(n < min) return res;
        backtrack(n, k, 0, new ArrayList<>(), 0);
        return res;
    }
    // 可以拆分为k个阶段，每个阶段从1-9中选出一个未选过的数
    public void backtrack(int n, int k, int p, List<Integer> path, int sum) {
        if(p == k) { // 结束条件：所有阶段决策已完成
            if(sum == n) res.add(new ArrayList<>(path));
            return;
        }
        int start = path.isEmpty() ? 1 : path.get(path.size() - 1) + 1;
        for(int i = start; i <= 9; i++) {
            path.add(i);
            backtrack(n, k, p + 1, path, sum + i);
            path.remove(path.size() - 1);
        }
    }
}

131. 分割回文串

class Solution {
    List<List<String>> res;
    public List<List<String>> partition(String s) {
        res = new ArrayList<>();
        backtrack(s, 0, new ArrayList<>(), 0);
        return res;
    }
    // 要对字符串进行分割，那么对于其中的每个字符，都可以选择其是否作为某子串的结束字符
    // p阶段决策：是否选择s[p]作为当前字串的结尾字符（start标识当前子串的开始位置）
    // path路径：记录整个决策过程中的所有回文子串
    public void backtrack(String s, int p, List<String> path, int start) {
        if(p == s.length()) {
            res.add(new ArrayList<>(path));
            return;
        }
        // 选择1：s[p]不作为当前子串结尾字符
        if(p < s.length() - 1) { // 特殊情况：对于s[len-1]，必须选择作为结尾字符
            backtrack(s, p + 1, path, start);
        }
        // 选择2：s[p]作为当前子串的结尾字符
        if(isPalindrome(s, start, p)) { // 前置条件：[start, p]是回文子串
            path.add(s.substring(start, p + 1)); // 做选择，将[start, p)分割为子串
            backtrack(s, p + 1, path, p + 1); // 继续下一阶段的选择，更新子串开始位置
            path.remove(path.size() - 1); // 撤销选择
        }
    }

    public boolean isPalindrome(String s, int start, int end) {
        while(start < end) {
            if(s.charAt(start) != s.charAt(end)) return false;
            start++;
            end--;
        }
        return true;
    }
}

93. 复原 IP 地址

class Solution {
    List<String> res;
    public List<String> restoreIpAddresses(String s) {
        res = new ArrayList<>();
        backtrack(s, 0, new ArrayList<>(), 0);
        return res;
    }

    public void backtrack(String s, int p, List<String> path, int start) {
        if(path.size() >= 5) return;
        if(p == s.length()) {
            if(path.size() == 4) res.add(path.stream().collect(Collectors.joining(".")));
            return;
        }
        // 不选择的条件：子串开始位置不是0 并且 增加下一个字符不会导致子串超过255
        if(s.charAt(start) != '0' && p < s.length() - 1 && Integer.parseInt(s.substring(start, p + 2)) <= 255) {
            backtrack(s, p + 1, path, start);
        }
        // 选择
        path.add(s.substring(start, p + 1));
        backtrack(s, p + 1, path, p + 1);
        path.remove(path.size() - 1);
    }
}

22. 括号生成

class Solution {
    List<String> res = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        char[] path = new char[n * 2];
        path[0] = '(';
        path[n * 2 - 1] = ')';
        backtrack(n - 1, n - 1, 1, path);
        return res;
    }
    // left/right：左右括号可用个数；index：当前位置使用什么括号
    public void backtrack(int left, int right, int index, char[] path) {
        if(left == 0 && right == 0) { // 所有括号都已用完
            res.add(new String(path));
            return;
        }
        if(left > 0) {
            path[index++] = '(';
            backtrack(left - 1, right, index, path);
            index--;
        }
         // 前面的字符序列中左括号的个数必须大于右括号的个数，当前位置才能填充右括号（同时考虑path[0]预先填充了左括号）
        if(right > 0 && right >= left) {
            path[index++] = ')';
            backtrack(left, right - 1, index, path);
            index--;
        }
    }
}

DFS&BFS

习题

剑指 Offer 13. 机器人的运动范围

int dirs[2][2] = {{0,1}, {1,0}};
bool check(int i, int j, int cnt) {
    int sum = 0;
    while(i > 0) {
        sum += (i % 10);
        i /= 10;
    }
    while(j > 0) {
        sum += (j % 10);
        j /= 10;
    }
    return sum <= cnt;
}
void dfs(int m, int n, int i, int j, int cnt, int *res, bool visit[m][n]) {
    (*res)++;
    visit[i][j] = true;
    for(int k = 0; k < 2; k++) {
        int i1 = i + dirs[k][0], j1 = j + dirs[k][1];
        if(i1 >= 0 && i1 < m && j1 >= 0 && j1 < n && visit[i1][j1] == false && check(i1, j1, cnt)) {
            dfs(m, n, i1, j1, cnt, res, visit);
        }
    }
}

int wardrobeFinishing(int m, int n, int cnt) {
    int res = 0;
    bool visit[m][n];
    memset(visit, 0, sizeof(visit) * sizeof(bool));
    dfs(m, n, 0, 0, cnt, &res, visit);
    return res;
}

面试题 08.10. 颜色填充

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int dirs[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}};
void dfs(int **image, int m, int n, int i, int j, int newColor, bool visit[m][n]) {
    visit[i][j] = true;
    int sameColor = image[i][j];
    image[i][j] = newColor;
    for(int k = 0; k < 4; k++) {
        int i1 = i + dirs[k][0], j1 = j + dirs[k][1];
        if(i1 >= 0 && i1 < m && j1 >= 0 && j1 < n && visit[i1][j1] == 0 && image[i1][j1] == sameColor) {
            dfs(image, m, n, i1, j1, newColor, visit);
        }
    }
}
int** floodFill(int** image, int imageSize, int* imageColSize, int sr, int sc, int newColor, int* returnSize, int** returnColumnSizes) {
    *returnSize = imageSize;
    *returnColumnSizes = imageColSize;
    bool visit[imageSize][imageColSize[0]];
    memset(visit, 0, sizeof(visit) * sizeof(bool));
    dfs(image, imageSize, imageColSize[0], sr, sc, newColor, visit);
    return image;
}

面试题 04.01. 节点间通路

class Solution {
    public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        for(int[] edge: graph) {
            if(!map.containsKey(edge[0])) {
                map.put(edge[0], new ArrayList<>());
            }
            map.get(edge[0]).add(edge[1]);
        }
        
        boolean[] visit = new boolean[n];
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        visit[start] = true;

        while(!queue.isEmpty()) {
            Integer node = queue.poll();
            List<Integer> list = map.get(node);
            if(list == null) continue;
            for(Integer next: list) {
                if(next == target) return true;
                if(visit[next] == false) {
                    queue.offer(next);
                    visit[next] = true;
                }
            }
        }
        return false;
    }
}

200. 岛屿数量（中等）

class Solution {
    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
    public int numIslands(char[][] grid) {
        boolean[][] visit = new boolean[grid.length][grid[0].length];
        int res = 0;
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                if(!visit[i][j] && grid[i][j] == '1') {
                    res++;
                    dfs(grid, i, j, visit);
                }
            }
        }
        return res;
    }

    public void dfs(char[][] grid, int m, int n, boolean[][] visit) {
        visit[m][n] = true;
        for(int i = 0; i < 4; i++) {
            int m1 = m + dirs[i][0];
            int n1 = n + dirs[i][1];
            if(m1 >= 0 && m1 < grid.length && n1 >= 0 && n1 < grid[0].length && !visit[m1][n1] && grid[m1][n1] == '1') {
                dfs(grid, m1, n1, visit);
            }
        }
    }
}

面试题 16.19. 水域大小

class Solution {
    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1}};
    int count = 0;
    public int[] pondSizes(int[][] land) {
        List<Integer> res = new ArrayList<>();
        boolean[][] visit = new boolean[land.length][land[0].length];
        for(int i = 0; i < land.length; i++) {
            for(int j = 0; j < land[0].length; j++) {
                if(!visit[i][j] && land[i][j] == 0) {
                    count = 0;
                    dfs(land, i, j, visit);
                    res.add(count);
                }
            }
        }
        return res.stream().sorted().mapToInt(Integer::intValue).toArray();
    }

    public boolean check(int[][] land, int m, int n, boolean[][] visit) {
        return m >= 0 && m < land.length && n >= 0 && n < land[0].length && !visit[m][n] && land[m][n] == 0;
    }

    public void dfs(int[][] land, int m, int n, boolean[][] visit) {
        visit[m][n] = true;
        count++;
        for(int i = 0; i < dirs.length; i++) {
            int m1 = m + dirs[i][0];
            int n1 = n + dirs[i][1];
            if(check(land, m1, n1, visit)) {
                dfs(land, m1, n1, visit);
            }
        }
    }
}

207. 课程表

BFS

class Solution {
    List<List<Integer>> edges; // 课程A->[以A为先修课的高级课程列表]
    int[] indegree; // 入度，indegree[i]表示课程i的入度数量
    int count;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        edges = new ArrayList<>(numCourses);
        indegree = new int[numCourses];
        // 构建邻接表，A->[B,C]表示A是B/C的先修课，可以从节点A到节点B/C
        for(int i = 0; i < numCourses; i++) {
            edges.add(new ArrayList<>());
        }
        for(int[] pre: prerequisites) {
            // pre[1]是高级课 pre[0]是先修课 
            edges.get(pre[1]).add(pre[0]);
            indegree[pre[0]]++;
        }
        count = 0;
        bfs();
        return count == numCourses;
    }

    public void bfs() {
        Queue<Integer> queue = new LinkedList<>();
        // 将入度为0的节点入队：没有先修课的课程可以直接学
        for(int i = 0; i < indegree.length; i++) {
            if(indegree[i] == 0) queue.offer(i);
        }
        while(!queue.isEmpty()) {
            // 出队表示该课程已学
            int course = queue.poll();
            count++;
            // 遍历以该课程为先修课的高级课，将其入度减1，表示完成了一门先修课
            for(int advanced: edges.get(course)) {
                indegree[advanced]--;
                // 入度为0时，表示所有先修课已学，该高级课也可以学了，将其入队
                if(indegree[advanced] == 0) {
                    queue.offer(advanced);
                }
            }
        }
    }
}

DFS

class Solution {
    List<List<Integer>> edges; // 课程A->[以A为先修课的高级课程列表]
    int[] indegree; // 入度，indegree[i]表示课程i的入度数量
    int[] visit; // 节点访问状态，0-待访问 1-访问中（未回溯） 2-已访问（已回溯）
    boolean hasCircle; // 是否有环形结构 例如A->B->A，学A要先学B，学B要先学A
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        edges = new ArrayList<>(numCourses);
        indegree = new int[numCourses];
        visit = new int[numCourses];
        // 建立邻接表
        for(int i = 0; i < numCourses; i++) {
            edges.add(new ArrayList<>());
        }
        for(int[] pre: prerequisites) {
            // pre[1]是高级课 pre[0]是先修课 
            edges.get(pre[1]).add(pre[0]);
            indegree[pre[0]]++;
        }
        // dfs遍历每个节点，判断是否有环
        hasCircle = false;
        for(int i = 0; i < indegree.length && !hasCircle; i++) {
            if(visit[i] == 0) dfs(i);
        }
        return !hasCircle;
    }

    public void dfs(int course) {
        visit[course] = 1; // 标记为访问中
        for(int advanced: edges.get(course)) { // 可选路径
            if(visit[advanced] == 0) {
                dfs(advanced);
                if(hasCircle) return; // 剪枝
            } else if(visit[advanced] == 1) { // 有环
                hasCircle = true;
            }
        }
        visit[course] = 2; // 标记为已访问
    }
}

79. 单词搜索

class Solution {
    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
    boolean exist;
    public boolean exist(char[][] board, String word) {
        exist = false;
        boolean[][] visit = new boolean[board.length][board[0].length];
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                if(board[i][j] == word.charAt(0)) {
                    dfs(board, word, i, j, visit, 0);
                    if(exist) return true;
                }
            }
        }
        return false;
    }

    public void dfs(char[][] board, String word, int m, int n, boolean[][] visit, int p) {
        if(p == word.length() - 1) {
            exist = true;
            return;
        }
        visit[m][n] = true;
        for(int i = 0; i < dirs.length; i++) {
            int m1 = m + dirs[i][0];
            int n1 = n + dirs[i][1];
            if(m1 >= 0 && m1 < board.length && n1 >= 0 && n1 < board[0].length 
                && !visit[m1][n1] && board[m1][n1] == word.charAt(p + 1)) {
                dfs(board, word, m1, n1, visit, p + 1);
            }
            if(exist) return;
        }
        visit[m][n] = false;
    }
}

1306. 跳跃游戏 III

class Solution {
    boolean result;
    public boolean canReach(int[] arr, int start) {
        result = false;
        boolean[] visit = new boolean[arr.length];
        dfs(arr, start, visit);
        return result;
    }

    public void dfs(int[] arr, int index, boolean[] visit) {
        if(arr[index] == 0) {
            result = true;
            return;
        }
        visit[index] = true;
        int left = index - arr[index], right = index + arr[index];
        if(left >= 0 && left < arr.length && !visit[left]) dfs(arr, left, visit);
        if(result == true) return;
        if(right >= 0 && right < arr.length && !visit[right]) dfs(arr, right, visit);
        visit[index] = false;
    }
}

752. 打开转盘锁

class Solution {
    public List<String> expend(String str) {
        List<String> list = new ArrayList<>(8);
        for (int i = 0; i < 4; i++) {
            char[] arr = str.toCharArray();
            char num = (char) (arr[i] - '0');
            arr[i] = (char) (((num - 1 + 10) % 10) + '0');
            list.add(new String(arr));
            arr[i] = (char) (((num + 1) % 10) + '0');
            list.add(new String(arr));
        }
        return list;
    }

    public int openLock(String[] deadends, String target) {
        Set<String> deadSet = new HashSet<>(Arrays.asList(deadends));
        if(deadSet.contains("0000")) return -1;
        int res = 0;
        Set<String> visit = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        queue.add("0000");
        visit.add("0000");
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String nums = queue.poll();
                if (nums.equals(target)) return res;
                List<String> options = expend(nums);
                for (String option : options) {
                    if (!visit.contains(option) && !deadSet.contains(option)) {
                        queue.offer(option);
                        visit.add(option);
                    }
                }
            }
            res++;
        }
        return -1;
    }
}

面试题 17.22. 单词转换

class Solution {
    List<String> result;
    boolean[] visit;
    public List<String> findLadders(String beginWord, String endWord, List<String> wordList) {
        result = new ArrayList<>();
        visit = new boolean[wordList.size()];
        List<String> path = new ArrayList<>();
        path.add(beginWord);
        dfs(beginWord, endWord, wordList, path);
        return result;
    }

    public boolean canTurn(String from, String to) {
        if(from.length() != to.length()) return false;
        int diff = 0;
        for(int i = 0; i < from.length(); i++) {
            if(from.charAt(i) != to.charAt(i)) {
                diff++;
                if(diff > 1) return false;
            }
        }
        return diff == 1;
    }

    public void dfs(String beginWord, String endWord, List<String> wordList, List<String> path) {
        if(beginWord.equals(endWord)) {
            result.addAll(path);
            return;
        }
        for(int i = 0; i < wordList.size(); i++) {
            String word = wordList.get(i);
            if(!visit[i] && canTurn(beginWord, word)) {
                visit[i] = true;
                path.add(word);
                dfs(word, endWord, wordList, path);
                if(!result.isEmpty()) return;
                path.remove(path.size() - 1);
                //visit[i] = false; 从该节点出发无法找到路径，后续不再进入该节点
            }
        }
    }
}

以下选做：

面试题 17.07. 婴儿名字

class Solution {
    public String[] trulyMostPopular(String[] names, String[] synonyms) {
        // 名字频率统计
        Map<String, Integer> cntMap = new HashMap<>();
        for(String str: names) {
            int i = str.indexOf("(");
            String name = str.substring(0, i);
            int count = Integer.parseInt(str.substring(i + 1, str.indexOf(")")));
            cntMap.put(name, count);
        }
        // 建立同义词邻接表 key：名字 value：同义词列表
        Map<String, List<String>> graph = new HashMap<>();
        for(String pair: synonyms) {
            int i = pair.indexOf(",");
            String str1 = pair.substring(1, i);
            String str2 = pair.substring(i + 1, pair.length() - 1);
            if(!graph.containsKey(str1)) graph.put(str1, new ArrayList<>());
            if(!graph.containsKey(str2)) graph.put(str2, new ArrayList<>());
            graph.get(str1).add(str2);
            graph.get(str2).add(str1);
        }
        // 对每个名字，在邻接表中进行搜索，收集该名字关联的所有同义词
        Set<String> visit = new HashSet<>();
        List<String> result = new ArrayList<>();
        for(String name: cntMap.keySet()) {
            if(visit.contains(name)) continue;
            List<String> synonymList = new ArrayList<>();
            dfs(graph, name, visit, synonymList);
            // 获取同义词中字典序最小的，将所有同义词频率进行合并
            Collections.sort(synonymList);
            int count = 0;
            for(String item: synonymList) {
                count += cntMap.getOrDefault(item, 0); // 同义词不一定给出了频率，则默认为0
            }
            result.add(synonymList.get(0) + '(' + count + ')');
        }
        return result.toArray(new String[0]);
    }

    // 如果名字有同义词，则进行dfs搜索，遍历图中所有与该名字连通的节点，并收集到synonyms
    public void dfs(Map<String, List<String>> graph, String name, Set<String> visit, List<String> synonyms) {
        visit.add(name);
        synonyms.add(name);
        if (graph.containsKey(name)) { 
            for(String item: graph.get(name)) {
                if(!visit.contains(item)) dfs(graph, item, visit, synonyms);
            }
        }
    }
}

529. 扫雷游戏（困难）

127. 单词接龙

126. 单词接龙 II

THE END