✅ 1200. 最小绝对差
描述
解答
- cpp
- py
✅ 897. 递增顺序查找树
描述
解答
- cpp
  - 指针问题？
  - fuck ptr
- py
✅ 183. 从不订购的客户
描述
解答
- sql todo rev me
✅ 575. 分糖果
描述
解答
- cpp
- py
✅ 136. 只出现一次的数字
描述
解答
- cpp
- py

✅ 1200. 最小绝对差

描述

给你个整数数组 arr，其中每个元素都 不相同。

请你找到所有具有最小绝对差的元素对，并且按升序的顺序返回。

 

示例 1：

输入：arr = [4,2,1,3]

输出：[[1,2],[2,3],[3,4]]

示例 2：

输入：arr = [1,3,6,10,15]

输出：[[1,3]]

示例 3：

输入：arr = [3,8,-10,23,19,-4,-14,27]

输出：[[-14,-10],[19,23],[23,27]]

 

提示：

2 <= arr.length <= 10^5

-10^6 <= arr[i] <= 10^6

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/minimum-absolute-difference

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解答

sort 后，进行查找相邻的两者差值，放入map

然后对map 的key 排序，打印出最小的key 对应的所有 values

实际上大家都如下，使用遍历数组，然后过程中记录minDiff，然后在原地做事情，没有使用map

这些个解答没有使用我自己想的map，因为key 可能重复，所以他用了数组：vector， list

cpp

class Solution {

public:

    vector<vector<int>> minimumAbsDifference(vector<int>& arr) {

        sort(arr.begin(), arr.end());

        int minest = INT_MAX;

        for(int i = 0; i < arr.size() - 1; i++) {

            int curDiff = arr[i+1] - arr[i];

            minest = minest >= curDiff ? curDiff: minest;

        }

        vector<vector<int>> res;

        for (int i = 0; i < arr.size() - 1; i++) {

            if(arr[i+1] - arr[i] == minest){

                res.push_back({arr[i], arr[i+1]});

                //两个 int 尺寸的int 被放入内层vector，然后作为一个vector 放入外层vector

            }

        }

        return res;

    }

};

/*执行用时 :

96 ms

, 在所有 C++ 提交中击败了

90.87%

的用户

内存消耗 :

17 MB

, 在所有 C++ 提交中击败了

72.87%

的用户*/

py

class Solution:

    def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:

        arr.sort()

        len1 = len(arr)

        len2 = len1 - 1

        mininum = [0] * len2

        for i in range (len2):

            mininum[i] = arr[i+1] - arr[i]# guess we dont need abs

        m = min(mininum)

        res = []

        for i in range (len2):

            if mininum[i] == m:

                res.append([arr[i], arr[i+1]])

        return res

'''

执行用时 :

484 ms

, 在所有 Python3 提交中击败了

41.26%

的用户

内存消耗 :

27.2 MB

, 在所有 Python3 提交中击败了

49.59%

的用户

'''

✅ 897. 递增顺序查找树

描述

给定一个树，按中序遍历重新排列树，使树中最左边的结点现在是树的根，并且每个结点没有左子结点，只有一个右子结点。

输入：[5,3,6,2,4,null,8,1,null,null,null,7,9]

       5

      / \

    3    6

   / \    \

  2   4    8

 /        / \

1        7   9

输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

 1

  \

   2

    \

     3

      \

       4

        \

         5

          \

           6

            \

             7

              \

               8

                \

                 9  

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/increasing-order-search-tree

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解答

cpp

my dont compile pass:

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

class Solution {

public:

    TreeNode* increasingBST(TreeNode* root) {

        if(!root) {

            return NULL;//blank tree

        }

        stack<TreeNode> s;

        TreeNode *res = (TreeNode *) malloc (sizeof(TreeNode));

        TreeNode *ret = res;

        while(root || !s.empty()) {

            while(root) {

                s.push(root);

                root = root->left;

            }

            root = s.top();

            s.pop();

            res = root;

            root = root->right;

            res = res->right;

        }

        return ret;

    }

};

指针问题？

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

class Solution {

public:

    TreeNode* increasingBST(TreeNode* root) {

        if(!root) {

            return NULL;//blank tree

        }

        stack<TreeNode> s;

        TreeNode *res = (TreeNode *) malloc (sizeof(TreeNode));

        TreeNode *ret = res;

        while(root || !s.empty()) {

            while(root) {

                s.push(*root);

                root = root->left;

            }

            //we must re-declare root ptr

            TreeNode *node = (TreeNode *) malloc (sizeof(TreeNode));

            *node = s.top();

            s.pop();

            printf(":%d:", node->val);

            res->right = node;

            res = res->right;

            root = node->right;

        }

        return ret->right;

    }

};

output:

fuck ptr

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

class Solution {

public:

    TreeNode* increasingBST(TreeNode* root) {

        if(!root) {

            return NULL;//blank tree

        }

        stack<TreeNode> s;

        TreeNode *res = (TreeNode *) malloc (sizeof(TreeNode));

        TreeNode *ret = res;

        while(root || !s.empty()) {

            while(root) {

                s.push(*root);

                root = root->left;

            }

            //we must re-declare node ptr

            TreeNode *node = (TreeNode *) malloc (sizeof(TreeNode));

            *node = s.top();

            s.pop();

            printf(":%d:", node->val);

            res->right = (TreeNode *) malloc(sizeof(TreeNode));

            res->right = node;

            res->left = NULL;

            res = res->right;

            root = node->right;

        }

        printf("bef ret");

        return ret;

    }

};

//  气死人！！！todo fuck me！！

py

# Definition for a binary tree node.

# class TreeNode:

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Solution:

    def increasingBST(self, root: TreeNode) -> TreeNode:

        s = []

        dummy = TreeNode(0)

        p = dummy

        while s or root:

            if root:

                s.append(root)

                root = root.left

            else:

                cur = s.pop()

                root = cur.right

                cur.left = None

                p.right = cur

                p = p.right

        return dummy.right

'''

执行用时 :

88 ms

, 在所有 Python3 提交中击败了

84.62%

的用户

内存消耗 :

13.2 MB

, 在所有 Python3 提交中击败了

43.45%

的用户

'''

✅ 183. 从不订购的客户

https://leetcode-cn.com/problems/customers-who-never-order/

描述

某网站包含两个表，Customers 表和 Orders 表。编写一个 SQL 查询，找出所有从不订购任何东西的客户。

Customers 表：

+----+-------+

| Id | Name  |

+----+-------+

| 1  | Joe   |

| 2  | Henry |

| 3  | Sam   |

| 4  | Max   |

+----+-------+

Orders 表：

+----+------------+

| Id | CustomerId |

+----+------------+

| 1  | 3          |

| 2  | 1          |

+----+------------+

例如给定上述表格，你的查询应返回：

+-----------+

| Customers |

+-----------+

| Henry     |

| Max       |

+-----------+

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/customers-who-never-order

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解答

sql todo rev me

# 498ms

select c.Name as Customers from Customers c left join Orders o on o.CustomerId = c.Id where o.Id is null;

# 532ms

select c.Name as Customers from Customers c where not exists (select 1 from Orders o where o.CustomerId = c.Id);

# 455ms

select c.Name as Customers from Customers c where c.Id not in (select distinct o.CustomerId from Orders o);

✅ 575. 分糖果

https://leetcode-cn.com/problems/distribute-candies/

描述

给定一个偶数长度的数组，其中不同的数字代表着不同种类的糖果，每一个数字代表一个糖果。你需要把这些糖果平均分给一个弟弟和一个妹妹。返回妹妹可以获得的最大糖果的种类数。

示例 1:

输入: candies = [1,1,2,2,3,3]

输出: 3

解析: 一共有三种种类的糖果，每一种都有两个。

     最优分配方案：妹妹获得[1,2,3],弟弟也获得[1,2,3]。这样使妹妹获得糖果的种类数最多。

示例 2 :

输入: candies = [1,1,2,3]

输出: 2

解析: 妹妹获得糖果[2,3],弟弟获得糖果[1,1]，妹妹有两种不同的糖果，弟弟只有一种。这样使得妹妹可以获得的糖果种类数最多。

注意:

数组的长度为[2, 10,000]，并且确定为偶数。

数组中数字的大小在范围[-100,000, 100,000]内。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/distribute-candies

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解答

cpp

class Solution {

public:

    int distributeCandies(vector<int>& candies) {

        set<int> myset;

        set<int>::iterator it;

        for(int i: candies){

            myset.insert(i);

        }

        int halfCount = candies.size() / 2;

        int ans = 0;

        //add each kind in myset to sis

        int sisGet = 0;

        for(it = myset.begin(); it != myset.end(); ++it){

            //for each kind in myset, give it to sis

            sisGet++;

        }

        // sister got : more kinds, give the redundant kinds to bro

        // so sister left halfCount

        if(sisGet > halfCount) {

            return halfCount;

        }else if (sisGet < halfCount){

            // if there are so few kind, that's all sis can got, so return it

            return sisGet;

        }

        // sisGet == halfCount

        return halfCount;

    }

};

/*执行用时 :

424 ms

, 在所有 C++ 提交中击败了

39.25%

的用户

内存消耗 :

54.8 MB

, 在所有 C++ 提交中击败了

10.24%

的用户*/

//fuck me tdo, can't use set properly, now I can use c++ fucking set ok

py

niu's idea:

step1: first, we want to find all the unique candy?

推翻：

设想有糖果：蜜桃，蜜桃，蜜桃，大白兔，大白兔，四百木，巴达木，六百木

蜜桃 counter = 2

大白兔 counter = 2

四百木 counter = 1

当： if Counter[某个种类] == 1:

sis += 1

那么结果：妹妹，只得到：四百木

哥哥反而得到了：蜜桃，大白兔

class Solution:

    def distributeCandies(self, candies: List[int]) -> int:

        from collections import Counter

        sis = 0

        c = Counter(candies)

        # 首先分配给sis 所有稀有糖果

        for i in range(max(candies)):

            if c[i] == 1:

                # this is the unique fruit

                sis+=1

        if sis < (len(candies) // 2):

            # 如果妹妹没拿够

            # 那么如果 糖果本身 的种类 就少于 一半，那么 妹妹最多获得所有种类的水果

            # 也就是 return len(set(candies))

            if len(set(candies)) < (len(candies) // 2):

                return len(set(candies))

            else:

            # 如果呢，种类大于 一半，那么 妹妹就能拿 一半 数量的水果，每个水果

            # 就是一个种类

                return len(candies) // 2

        # 如果妹妹光拿稀有水果 就超过了 一半的数量，那么不要贪心，就拿一半，另一半还要

        # 给哥哥

        else:

            return len(candies) // 2

 '''

执行用时 :

1928 ms

, 在所有 Python3 提交中击败了

5.33%

的用户

内存消耗 :

15 MB

, 在所有 Python3 提交中击败了

48.59%

的用户

 '''

✅ 136. 只出现一次的数字

https://leetcode-cn.com/problems/single-number/

描述

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]

输出: 1

示例 2:

输入: [4,1,2,1,2]

输出: 4

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/single-number

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解答

cpp

 int singleNumber(vector<int>& nums) {

        int result = 0;

        for (int i = 0; i < nums.size(); i++) {

            bitset<4> bs1(result);

            bitset<4> bs2(nums[i]);

            cout<<bs1<<"^"<<bs2<<"=";

            result = result^nums[i];//二进制异或运算,

            bitset<4> bs3(result);

            cout<<bs3<<endl;

        }

        return result;

    }

//my

class Solution {

public:

    int singleNumber(vector<int>& nums) {

        int res;

        for(int num: nums) {

            res ^= num;

        }

        return res;

    }

};

todo fix 力扣SB：

py

class Solution:

    def singleNumber(self, nums: List[int]) -> int:

        from collections import Counter

        c = Counter(nums)

        print(c)

        for i in nums:

            if c[i] == 1:

                return i

'''

执行用时 :

96 ms

, 在所有 Python3 提交中击败了

80.27%

的用户

内存消耗 :

15.8 MB

, 在所有 Python3 提交中击败了

40.45%

的用户

'''

巴特西

leetcode 0218