447. 回旋镖的数量

给定平面上 n 对 互不相同 的点 points ，其中 points[i] = [xi, yi] 。回旋镖 是由点 (i, j, k) 表示的元组 ，其中 i 和 j 之间的距离和 i 和 k 之间的距离相等（需要考虑元组的顺序）。

返回平面上所有回旋镖的数量。

示例 1：

1
2
3
输入：points = [[0,0],[1,0],[2,0]]
输出：2
解释：两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]

示例 2：

1
2
输入：points = [[1,1],[2,2],[3,3]]
输出：2

示例 3：

1
2
输入：points = [[1,1]]
输出：0

解答：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 考虑数组顺序，可以用排列组合的方式,枚举一个个算距离，存储距离相同的点的个数放入哈希表中，最后取出哈希表中的数据，一个个排列组合
class Solution {
    public int numberOfBoomerangs(int[][] points) {
        int ans = 0;
        for (int [] p:points) {
            Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();
            for (int[] q : points) {
                int dis = ((p[0] - q[0])) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] -  q[1]);
                cnt.put(dis, cnt.getOrDefault(dis, 0) + 1);
            }
            for(Map.Entry<Integer, Integer> entry : cnt.entrySet()) {
                int m = entry.getValue();
                ans += m * (m-1);
            }
        }
        return ans;
    }
}

260. 只出现一次的数字 III

难度中等490收藏分享切换为英文接收动态反馈

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

进阶：你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

示例 1：

1
2
3
输入：nums = [1,2,1,3,2,5]
输出：[3,5]
解释：[5, 3] 也是有效的答案。

示例 2：

1
2
输入：nums = [-1,0]
输出：[-1,0]

示例 3：

1
2
输入：nums = [0,1]
输出：[1,0]

提示：

  • 2 <= nums.length <= 3 * 104
  • -231 <= nums[i] <= 231 - 1
  • 除两个只出现一次的整数外，nums 中的其他数字都出现两次

思路：建一个hashmap 把它每个算出来是多少然后遍历出来。

解答：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int[] singleNumber(int[] nums) {
        int [] ans = new int[2];
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i=0; i <nums.length; i++ ) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        int index = 0;
        for (int i=0; i <nums.length; i++ ) {
            if(map.get(nums[i]) == 1) ans[index++] = nums[i];
        }
        return ans;
    }
}

299. 猜数字游戏

难度中等164

你在和朋友一起玩 猜数字（Bulls and Cows）游戏，该游戏规则如下：

写出一个秘密数字，并请朋友猜这个数字是多少。朋友每猜测一次，你就会给他一个包含下述信息的提示：

  • 猜测数字中有多少位属于数字和确切位置都猜对了（称为 “Bulls”, 公牛），
  • 有多少位属于数字猜对了但是位置不对（称为 “Cows”, 奶牛）。也就是说，这次猜测中有多少位非公牛数字可以通过重新排列转换成公牛数字。

给你一个秘密数字 secret 和朋友猜测的数字 guess ，请你返回对朋友这次猜测的提示。

提示的格式为 "xAyB" ，x 是公牛个数， y 是奶牛个数，A 表示公牛，B 表示奶牛。

请注意秘密数字和朋友猜测的数字都可能含有重复数字。

示例 1:

1
2
3
4
5
6
输入: secret = "1807", guess = "7810"
输出: "1A3B"
解释: 数字和位置都对（公牛）用 '|' 连接，数字猜对位置不对（奶牛）的采用斜体加粗标识。
"1807"
  |
"7810"

示例 2:

1
2
3
4
5
6
7
输入: secret = "1123", guess = "0111"
输出: "1A1B"
解释: 数字和位置都对（公牛）用 '|' 连接，数字猜对位置不对（奶牛）的采用斜体加粗标识。
"1123"        "1123"
  |      or     |
"0111"        "0111"
注意，两个不匹配的 1 中，只有一个会算作奶牛（数字猜对位置不对）。通过重新排列非公牛数字，其中仅有一个 1 可以成为公牛数字。

示例 3：

1
2
输入：secret = "1", guess = "0"
输出："0A0B"

示例 4：

1
2
输入：secret = "1", guess = "1"
输出："1A0B"

提示：

  • 1 <= secret.length, guess.length <= 1000
  • secret.length == guess.length
  • secret 和 guess 仅由数字组成

思路：

  • 数字位置都对的 +1
  • 数字对位置不对的 哈希表存起来 +1
  • 对比 哈希表中的数字，取小的

解答：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public String getHint(String secret, String guess) {
        Map <Character, Integer> secret_map= new HashMap<>();
        Map <Character, Integer> guess_map= new HashMap<>();
        int bull=0, cow=0;
        for (int i=0; i<secret.length(); i++) {
            if(secret.charAt(i) == guess.charAt(i)) {
                bull++;
            }else {
                secret_map.put(secret.charAt(i), secret_map.getOrDefault(secret.charAt(i), 0)+1);
                guess_map.put(guess.charAt(i), guess_map.getOrDefault(guess.charAt(i), 0)+1);
            }
        }

        for(char k : secret_map.keySet()) {
            if (guess_map.containsKey(k)) cow = cow + Math.min(secret_map.get(k), guess_map.get(k));
        }

        return bull+"A"+cow+"B";
    }
}

NC61 两数之和

描述

给出一个整型数组 numbers 和一个目标值 target，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。

（注：返回的数组下标从1开始算起）

数据范围：2≤len(numbers)≤1500，−10≤numbers**i≤109，0≤targe**t≤109

要求：空间复杂度 O(n)O(n)，时间复杂度 O(nlogn)O(nlogn)

例如：

给出的数组为 [20, 70, 110, 150] , 目标值为90

返回一个数组 [1,2] ，因为 numbers _1+numbers _2=20+70=90numbers1+numbers2=20+70=90

示例1

输入：

1
[3,2,4],6

返回值：

1
[2,3]

说明：

1
因为 2+4=6 ，而 2的下标为2 ， 4的下标为3 ，又因为 下标2 < 下标3 ，所以返回[2,3]

示例2

输入：

1
[20,70,110,150],90

返回值：

1
[1,2]

思路：

  • 定义哈希表hashmap，其存放的键值对为<取值，下标>。
  • 从开始处遍历数组，对于第i个位置，在哈希表中寻找target-nums[i]是否存在，若存在，将两个下标放入数组中返回；若不存在，将其添加至表中，继续遍历。

解答：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.*;


public class Solution {
    /**
     * 
     * @param numbers int整型一维数组 
     * @param target int整型 
     * @return int整型一维数组
     */
    public int[] twoSum (int[] numbers, int target) {
        // write code here
        int tmp = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i=0; i< numbers.length; i++) {
            tmp = target - numbers[i];
            if (map.containsKey(tmp)) {
                return new int[] {map.get(tmp)+1, i+1};
            } else {
                map.put(numbers[i], i);
            }
        }
        return null;
        
    }
}