leetcode 0210

✅ 1207 独一无二的出现次数

https://leetcode-cn.com/problems/unique-number-of-occurrences

描述

给你一个整数数组 arr，请你帮忙统计数组中每个数的出现次数。

如果每个数的出现次数都是独一无二的，就返回 true；否则返回 false。

示例 1：

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

输出：true

解释：在该数组中，1 出现了 3 次，2 出现了 2 次，3 只出现了 1 次。没有两个数的出现次数相同。

示例 2：

输入：arr = [1,2]

输出：false

示例 3：

输入：arr = [-3,0,1,-3,1,1,1,-3,10,0]

输出：true

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/unique-number-of-occurrences

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

解答

我的思路： 用 一个book 数组，标记每一个数字出现的次数，最后尝试把book 数组每个 元素加入set，不能加入（因为已经加入了）就返回false，否则返回true。（另外，如果不知道set 有没有 add（重复）的 警告返回的话，就 return set.size() == book.length;

class Solution {

    public boolean uniqueOccurrences(int[] arr) {

        int book[] = new int[arr.length];

        for (int i : arr) {

            book[i]++;

        }

        Set<Integer> set = new HashSet<>();

        for(int j : book){

            set.add(j);

        }

        return set.size() == book.length;

    }

}

//failed

实际上，上面这个办法并不行，因为,book length 并不是你想的那么小，而是和arr。length 一样大。我们转而使用hashMap

java hashMap api

put

map.put("zhang", "31");//存放键值对

get

map.get("zhang");//获取值

containsKey

map.containsKey("zhang");//键中是否包含这个数据

remove

map.remove("zhang");//从键值中删除

map.keySet()

for (String key : map.keySet()) {

    System.out.println(key);

}

map.values()

for (String values : map.values()) {

   System.out.println(values);

}

map.entrySet()

for (Entry<String, String> entry : map.entrySet()) {

    String key = entry.getKey();

    String value = entry.getValue();

    System.out.println(key + "," + value);

}

java my final solution:

class Solution {

    public boolean uniqueOccurrences(int[] arr) {

        HashMap<Integer, Integer> book = new HashMap<>();

        for (int i : arr) {

            int val = 0;

            if(book.get(i) != null) {

                val = book.get(i) + 1;

            }

            book.put(i, val);

        }

        Set<Integer> set = new HashSet<>();

        for(Integer j : book.values()){

            set.add(j);

        }

        return set.size() == book.size();

    }

}

执行用时 :

3 ms

, 在所有 Java 提交中击败了

80.64%

的用户

内存消耗 :

35.9 MB

, 在所有 Java 提交中击败了

19.21%

的用户

c other's solution， 用两个 数组 统计

#include <stdlib.h>

bool uniqueOccurrences(int* arr, int arrSize){

    int a[2001] = {0}; int b[2001] = {0}; int i;

    /* step1：统计每个数字出现的次数到数组a中 */

    for (i = 0; i < arrSize; i++) {

        if (arr[i] < 0) {

            a[abs(arr[i]) + 1000]++;

        } else {

            a[arr[i]]++;

        }

    }

    /* step2: 在step1数组中 再按出现次数 统计到b,tt 把 a 统计到b 中 */

    for (i = 0; i < 2000; i++) {

        if (a[i] != 0) {

            b[a[i]]++;

        }

    }

    /* step3 :在b中出现超过1次的 即表示有出现相同次数 */

    for (i = 0; i < 2000; i++) {

        if (b[i] > 1) {

            return false;

        }

    }

    return true;

}

✅ 476 数字的补数

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

用时15min

描述

给定一个正整数，输出它的补数。补数是对该数的二进制表示取反。

注意:

给定的整数保证在32位带符号整数的范围内。

你可以假定二进制数不包含前导零位。

示例 1:

输入: 5

输出: 2

解释: 5的二进制表示为101（没有前导零位），其补数为010。所以你需要输出2。

示例 2:

输入: 1

输出: 0

解释: 1的二进制表示为1（没有前导零位），其补数为0。所以你需要输出0。

解答

估计这种题目，用c 的位操作非常方便。java 也有位操作

c 他人 cped！

//不懂二进制的看了好久。。就是num转为二进制，并看看总共x位二进制，然后与这全部的x位都是1的二进制进行异或运算（相同为0，不同为1）。就得出结果。

int temp = num, c = 0;

while(temp > 0){

     //根据判断条件

    //二进制右移并赋值给temp，

    temp >>= 1;

   //二进制左移之后结果+1 赋值给c

    c =  (c << 1) + 1;

}

return num ^ c;// 这里 ^ 是 异或的意思

/*执行用时 :

0 ms

, 在所有 C 提交中击败了

100.00%

的用户

内存消耗 :

6.7 MB

, 在所有 C 提交中击败了

91.73%

的用户*/

他人jav 解答

class Solution {

    public int findComplement(int num) {

        int res = 0;

        int i = 0;

        while(num>0){

        // 实际上就是把num 上的这一位去反，然后乘以 2 的 i 次方

          res +=  ((num&1)==0?1:0)*(1<<i++);// 这个nb，

          num = num >> 1;

        }

        return res;

    }

}

/*执行用时 :

1 ms

, 在所有 Java 提交中击败了

97.67%

的用户

内存消耗 :

33.3 MB

, 在所有 Java 提交中击败了

34.34%

的用户*/

✅ 1237 找出给定方程的正整数解

https://leetcode-cn.com/problems/find-positive-integer-solution-for-a-given-equation

描述

给出一个函数  f(x, y) 和一个目标结果 z，请你计算方程 f(x,y) == z 所有可能的正整数 数对 x 和 y。

给定函数是严格单调的，也就是说：

f(x, y) < f(x + 1, y)

f(x, y) < f(x, y + 1)

函数接口定义如下：

interface CustomFunction {

public:

  // Returns positive integer f(x, y) for any given positive integer x and y.

  int f(int x, int y);

};

如果你想自定义测试，你可以输入整数 function_id 和一个目标结果 z 作为输入，其中 function_id 表示一个隐藏函数列表中的一个函数编号，题目只会告诉你列表中的 2 个函数。 (如下 示例 1/2） 

你可以将满足条件的 结果数对 按任意顺序返回。

 

示例 1：

输入：function_id = 1, z = 5

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

解释：function_id = 1 表示 f(x, y) = x + y

示例 2：

输入：function_id = 2, z = 5

输出：[[1,5],[5,1]]

解释：function_id = 2 表示 f(x, y) = x * y

 

提示：

1 <= function_id <= 9

1 <= z <= 100

题目保证 f(x, y) == z 的解处于 1 <= x, y <= 1000 的范围内。

在 1 <= x, y <= 1000 的前提下，题目保证 f(x, y) 是一个 32 位有符号整数。

解答

这些答案让我读懂了题目：

jav 双指针

public List<List<Integer>> findSolution(CustomFunction customfunction, int z) {

  List<List<Integer>> res = new LinkedList<>();

  int start = 1, end = 1000;

  while (start <= 1000 && end >= 1) {

      int r = customfunction.f(start, end);

      if (r == z) {

          List<Integer> tmp = new LinkedList<>();

          tmp.add(start);

          tmp.add(end);

          res.add(tmp);

          start++;

          end--;

      } else if (r > z)

          end--;

      else/* r<z */

          start++;

  }

  return res;

}

jav 解释这道题的目的，暴力法

class Solution {

    public List<List<Integer>> findSolution(CustomFunction customfunction, int z) {

        List<List<Integer>> result = new ArrayList<List<Integer>>();

        for(int i=1;i<=z;i++){

            for(int j=1;j<=z;j++){

               if(customfunction.f(i,j)==z) {

                   List<Integer> temp = new ArrayList<Integer>();

                   temp.add(i);temp.add(j);

                   result.add(temp);

               }

            }

        }

        return result;

    }

}

py3 similar like above jav

class Solution:

    def findSolution(self, customfunction: 'CustomFunction', z: int) -> List[List[int]]:

        ans = []

        x = 1

        y = z

        while x <= z and y > 0:

            tmp = customfunction.f(x, y)

            if tmp > z:

                y -= 1

            elif tmp < z:

                x += 1

            elif tmp == z:

                ans.append([x,y])

                x +=1

                y -=1

        return ans

my py3 cped above:

class Solution:

    def findSolution(self, customfunction: 'CustomFunction', z: int) -> List[List[int]]:

        ans = []

        x = 1

        y = z

        while x <= z and y > 0:

            tmp = customfunction.f(x, y)

            if tmp > z:

                y -= 1

            elif tmp < z:

                x += 1

            else:

                ans.append([x,y])

                x += 1

                y -= 1

        return ans

'''执行用时 :

24 ms

, 在所有 Python3 提交中击败了

99.78%

的用户

内存消耗 :

13 MB

, 在所有 Python3 提交中击败了

52.73%

的用户'''

✅ 908 最小差值 I

https://leetcode-cn.com/problems/smallest-range-i

描述

给定一个整数数组 A，对于每个整数 A[i]，我们可以选择任意 x 满足 -K <= x <= K，并将 x 加到 A[i] 中。

在此过程之后，我们得到一些数组 B。

返回 B 的最大值和 B 的最小值之间可能存在的最小差值。

 

示例 1：

输入：A = [1], K = 0

输出：0

解释：B = [1]

示例 2：

输入：A = [0,10], K = 2

输出：6

解释：B = [2,8]

示例 3：

输入：A = [1,3,6], K = 3

输出：0

解释：B = [3,3,3] 或 B = [4,4,4]

解答

出题人语文及格了没!

翔一样的问题描述

得到数组B？数组B是谁，怎么得到的，这题目是哪个国学大师出的，能用凡人的组织方式解释一哈么 --！

---

py3 当你语文过关后的解答：

class Solution:

    def smallestRangeI(self, A: List[int], K: int) -> int:

        if max(A) - min(A) > K * 2:

            return max(A) - min(A) - K * 2

        else:

            return 0

他人java， 多了很多边界检查的代码

 public int smallestRangeI(int[] A, int k) {

    //边界检查的代码

        if(A==null){

            return 0;

        }

        //边界检查的代码

        int len = A.length;

        if(len==1){

            return 0;

        }

        //core 1 排序，能帮助找大小，这么多 也就是py 里的一行 ：max（list）

        Arrays.sort(A);

        int max = A[len-1];

        int min = A[0];

        // core2 类似上面py 的思路

        if(max -k>min+k){

            return max-min-2*k;

        }

        return 0;

    }