leetcode---比较有意义的题目(一）

目前刷题目：《和为零的N个唯一整数》----简单题、通过率从高到低排序

1. strcmp函数是string compare(字符串比较)的缩写，用于比较两个字符串并根据比较结果返回整数。基本形式为strcmp(str1,str2)，若str1=str2，则返回零；若str1<str2，则返回负数；若str1>str2，则返回正数。

目录：

          1、宝石与石头；

          2、删除链表中的节点；

          3、按既定顺序创建目标数组；

          4、最小高度树；

          5、二叉树的深度；

          6、二叉树的镜像；

          7、数组中两元素的最大乘积

          8、删除最外层的括号

          9、二叉搜索树的范围和

          10、 通过翻转子数组使两个数组相等

1、宝石与石头：

解法一：遍历法；遍历一遍宝石和一遍石头，新建char arr[123] = {0}; 宝石置1，非宝石置0。判断手里石头在对应数组中位置是否为1，如果为1，则该石头为宝石，否则相反；

int numJewelsInStones(char * J, char * S) {
    if (J == NULL || S == NULL) {
        return 0;
    }
    int Res = 0;
    int LenJ = strlen(J), LenS = strlen(S);
    char arr[123] = { 0 };
    for (int i = 0; i < LenJ; ++i) {
        arr[J[i]-0] = 1;
    }
    for (int i = 0; i < LenS; ++i) {
        if (1 == arr[S[i]-0]) {
            Res++;
        }
    }
    return Res;
}

2、删除链表中的节点 ： node->val = node->next->val;node->next = node->next->next;

3、按既定顺序创建目标数组：

解法一： 思路为，首先要插入numsSize个数字，利用标志位flag，来记录已经插入了几个数字；当当flag小于index[i]时，说明目前还可以容纳当前数字，直接放入数字即可；当flag大于index[i]时，说明需要进行后移操作。res[j] = res[j-1];

这段代码其实有点问题，当我的index为[2,2,2,2,2]时怎么处理呢，或者正如题目说的，通过保证插入位置有效来解决吧；

int* createTargetArray(int* nums, int numsSize, int* index, int indexSize, int* returnSize) {
    *returnSize = numsSize;
    int *res = (int*)malloc(numsSize * sizeof(int));
    int flag = -1;
    for (int i = 0; i < numsSize; ++i) {
        ++flag;
        for (int j = flag; j > index[i]; --j) {
            res[j] = res[j-1];
        }
        res[index[i]] = nums[i];
    }
    *returnSize = numsSize;
    return res;
}

4、最小高度树：

解法一： 主要是LeetCode上面的题目，怎么说呢，就是首先选择一个根节点，根节点可以每次选择中间的那个点；

struct TreeNode* BuildTree(int *nums, int L, int R) {
    struct TreeNode *root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    if (L > R) {
        return NULL;
    }
    int mid = L + (R - L) / 2;
    root->val = nums[mid];
    root->left = BuildTree(nums, L, mid - 1);
    root->right = BuildTree(nums, mid + 1, R);
    return root;
}

struct TreeNode* sortedArrayToBST(int* nums, int numsSize) {
    if (nums == NULL || numsSize < 0) {
        return NULL;
    }
    struct TreeNode *res = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    int L = 0, R = numsSize - 1;
    res = BuildTree(nums, L, R);
    return res;
}

5、二叉树的深度：方法吗，递归吧，想到了就很简单，不会的话，翻剑指offer吧或者google;

int maxDepth (struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    int LenLeft = maxDepth(root->left) + 1;
    int LenRight = maxDepth(root->right) + 1;
    return LenLeft > LenRight ? LenLeft : LenRight;
}

6、二叉树的镜像：方法吗，递归吧，想到了就很简单，不会的话，翻剑指offer吧或者google;

struct TreeNode* mirrorTree(struct TreeNode* root) {
    if (root == NULL) {
        return NULL;
    }
    struct TreeNode* temp = root->left;
    root->left = mirrorTree(root->right);
    root->right = mirrorTree(temp);
    return root;
}

7、数组中两元素的最大乘积：先进行一遍循环找出最大的和次大的，然后求积就好了；

int maxProduct(int* nums, int numsSize) {
    if (nums == NULL || numsSize < 2) {
        return NULL;
    }
    int first = nums[0];
    int second = nums[1];
    int mid;
    if (first < second) {
        mid = first;
        first = second;
        second = mid;
    }
    for (int i = 2; i < numsSize; ++i) {
        if (nums[i] > first) {
            second = first;
            first = nums[i];
        } else {
            if(nums[i] > second) {
                second = nums[i];
            }
        }
    }
    int res = (first - 1) * (second - 1);
    return res;
}

8、删除最外层的括号，原地删除括号吧，挺精彩的；

char * removeOuterParentheses(char * S) {
    int len = strlen(S);
    int Num = 0, p = 0;
    
    for (int i = 0; i < len; ++i) {
        if(S[i] == '(') {
            if (Num != 0) {
                S[p++] = S[i];
            }
            Num++;
        } else {
            Num--;
            if (Num != 0) {
                S[p++] = S[i];
            }
        }
    }
    S[p] = '\0';
    return S;
}

9、二叉搜索树的范围和

int rangeSumBST(struct TreeNode* root, int L, int R){
    if (root == NULL) {
        return 0;
    }
    int res = 0;
    if (root->val >= L && root->val <= R) {
        res += root->val;
    }
    res += (rangeSumBST(root->left, L, R) + rangeSumBST(root->right, L, R));
    return res;
}

10、通过翻转子数组使两个数组相等

题目思路：首先如果两个数组通过翻转子数组后一样，说明这两个数组中所有数目都是相同的；由于两个数组长度一样。首先记录目标数组中每个数的数目，在记录当前数组中每个数的数目，记录过程中，如果有当前数组数字数目大于目标数组中对应数目，这说明两个数组最终翻转不可能一样。

bool canBeEqual(int* target, int targetSize, int* arr, int arrSize) {
    int arr1[1001] = { 0 };
    int arr2[1001] = { 0 };
    int flag = 1;
    for(int i = 0; i < targetSize; ++i) {
        arr1[target[i]]++;
    }
    for(int i = 0; i < arrSize; ++i) {
        arr2[arr[i]]++;
        if(arr2[arr[i]] > arr1[arr[i]]) {
            flag = 0;
            break;
        }
    }
    if(flag == 0) {
        return false;
    } else {
        return true;
    }
}