T1 2148. 元素计数

题目

给你一个整数数组 nums ，统计并返回在 nums 中同时具有一个严格较小元素和一个严格较大元素的元素数目。

P.S.

翻译的太离谱了，建议看一下英文题目方便理解

Given an integer array nums, return the number of elements that have both a strictly smaller and a strictly greater element appear in nums.

示例 1：

输入：nums = [11,7,2,15]
输出：2

解释：元素 7 ：严格较小元素是元素 2 ，严格较大元素是元素 11 。
元素 11 ：严格较小元素是元素 7 ，严格较大元素是元素 15 。
总计有 2 个元素都满足在 nums 中同时存在一个严格较小元素和一个严格较大元素。

示例 2：

输入：nums = [-3,3,3,90]
输出：2

解释：元素 3 ：严格较小元素是元素 -3 ，严格较大元素是元素 90 。
由于有两个元素的值为 3 ，总计有 2 个元素都满足在 nums 中同时存在一个严格较小元素和一个严格较大元素。

提示：

  • 1≤nums.length≤1001 \leq nums.length \leq 100
  • −105≤nums[i]≤105-10^5 \leq nums[i] \leq 10^5

题解

有严格小元素和严格大元素，其实就等价于比最小值严格大，比最大值严格小。

正常遍历两遍即可，第一次标记出最大值最小值，第二次直接判断计数即可。

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
27
28
29
30
31
func countElements(nums []int) int {
    min_val := 100001
    max_val := -100001
    for _, v := range nums {
        min_val = min(min_val, v)
        max_val = max(max_val, v)
    }
    res := 0
    for _, v := range nums {
        if v > min_val && v < max_val {
            res++
        }
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    } else {
        return b
    }
}

func min(a, b int) int {
    if a > b {
        return b
    } else {
        return a
    }
}

T2 2149. 按符号重排数组

题目

给你一个下标从 0 开始的整数数组 nums ，数组长度为 偶数 ，由数目相等的正整数和负整数组成。

你需要 重排 nums 中的元素，使修改后的数组满足下述条件：

  1. 任意 连续 的两个整数 符号相反
  2. 对于符号相同的所有整数，保留 它们在 nums 中的 顺序 。
  3. 重排后数组以正整数开头。

重排元素满足上述条件后，返回修改后的数组。

示例 1：

输入：nums = [3,1,-2,-5,2,-4]
输出：[3,-2,1,-5,2,-4]

解释：
nums 中的正整数是 [3,1,2] ，负整数是 [-2,-5,-4] 。
重排的唯一可行方案是 [3,-2,1,-5,2,-4]，能满足所有条件。
像 [1,-2,2,-5,3,-4]、[3,1,2,-2,-5,-4]、[-2,3,-5,1,-4,2] 这样的其他方案是不正确的，因为不满足一个或者多个条件。

示例 2：

输入：nums = [-1,1]
输出：[1,-1]
解释：
1 是 nums 中唯一一个正整数，-1 是 nums 中唯一一个负整数。
所以 nums 重排为 [1,-1] 。

提示：

  • 2≤nums.length≤2∗1052 \leq nums.length \leq 2 * 10^5
  • nums.length 是 偶数
  • 1 \leq \abs{nums[i}| \leq 10^5
  • nums 由 相等 数量的正整数和负整数组成

题解

我们按照顺序遍历一遍数组，然后写进新数组里就好了。

注意好及时更新负数和正数的指针位置就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func rearrangeArray(nums []int) []int {
    res := make([]int, len(nums))
    p, q := 0, 1
    for _, v := range nums {
        if v < 0 {
            res[q] = v
            q += 2
        } else {
            res[p] = v
            p += 2
        }
    }
    return res
}

T3 2150. 找出数组中的所有孤独数字

题目

给你一个整数数组 nums 。如果数字 x 在数组中仅出现 一次 ，且没有 相邻 数字（即，x + 1 和 x - 1）出现在数组中，则认为数字 x 是 孤独数字 。

返回 nums 中的 所有 孤独数字。你可以按 任何顺序 返回答案。

示例 1：

输入：nums = [10,6,5,8]
输出：[10,8]

解释：

  • 10 是一个孤独数字，因为它只出现一次，并且 9 和 11 没有在 nums 中出现。
  • 8 是一个孤独数字，因为它只出现一次，并且 7 和 9 没有在 nums 中出现。
  • 5 不是一个孤独数字，因为 6 出现在 nums 中，反之亦然。

因此，nums 中的孤独数字是 [10, 8] 。
注意，也可以返回 [8, 10] 。

示例 2：

输入：nums = [1,3,5,3]
输出：[1,5]
解释：

  • 1 是一个孤独数字，因为它只出现一次，并且 0 和 2 没有在 nums 中出现。
  • 5 是一个孤独数字，因为它只出现一次，并且 4 和 6 没有在 nums 中出现。
  • 3 不是一个孤独数字，因为它出现两次。

因此，nums 中的孤独数字是 [1, 5] 。
注意，也可以返回 [5, 1] 。

提示：

  • 1≤nums.length≤1051 \leq nums.length \leq 10^5
  • 0≤nums[i]≤1060 \leq nums[i] \leq 10^6

题解

简直就是纯纯的HashMap，都没啥好说的，对着题目说的做就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
func findLonely(nums []int) []int {
    m := map[int]int{}
    for _, v := range nums {
        m[v]++
    }
    res := []int{}
    for k, v := range m {
        if v == 1 && m[k - 1] == 0 && m[k + 1] == 0{
            res = append(res, k)
        }
    }
    return res
}

T4 2151. 基于陈述统计最多好人数

题目

游戏中存在两种角色：

  • 好人：该角色只说真话。
  • 坏人：该角色可能说真话，也可能说假话。

给你一个下标从 0 开始的二维整数数组 statements ，大小为 n x n ，表示 n 个玩家对彼此角色的陈述。具体来说，statements[i][j] 可以是下述值之一：

  • 0 表示 i 的陈述认为 j 是 坏人 。
  • 1 表示 i 的陈述认为 j 是 好人 。
  • 2 表示 i 没有对 j 作出陈述。

另外，玩家不会对自己进行陈述。形式上，对所有 0 <= i < n ，都有 statements[i][i] = 2 。

根据这 n 个玩家的陈述，返回可以认为是 好人 的 最大 数目。

示例 1：

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

解释：每个人都做一条陈述。

  • 0 认为 1 是好人。
  • 1 认为 0 是好人。
  • 2 认为 1 是坏人。

以 2 为突破点。

  • 假设 2 是一个好人：
    • 基于 2 的陈述，1 是坏人。
    • 那么可以确认 1 是坏人，2 是好人。
    • 基于 1 的陈述，由于 1 是坏人，那么他在陈述时可能：
      • 说真话。在这种情况下会出现矛盾，所以假设无效。
      • 说假话。在这种情况下，0 也是坏人并且在陈述时说假话。
    • 在认为 2 是好人的情况下，这组玩家中只有一个好人。
  • 假设 2 是一个坏人：
    • 基于 2 的陈述，由于 2 是坏人，那么他在陈述时可能：
      • 说真话。在这种情况下，0 和 1 都是坏人。
        • 在认为 2 是坏人但说真话的情况下，这组玩家中没有一个好人。
      • 说假话。在这种情况下，1 是好人。
        • 由于 1 是好人，0 也是好人。
        • 在认为 2 是坏人且说假话的情况下，这组玩家中有两个好人。

在最佳情况下，至多有两个好人，所以返回 2 。
注意，能得到此结论的方法不止一种。

示例 2：

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

解释：每个人都做一条陈述。

  • 0 认为 1 是坏人。
  • 1 认为 0 是坏人。

以 0 为突破点。

  • 假设 0 是一个好人：
    • 基于与 0 的陈述，1 是坏人并说假话。
    • 在认为 0 是好人的情况下，这组玩家中只有一个好人。
  • 假设 0 是一个坏人：
    • 基于 0 的陈述，由于 0 是坏人，那么他在陈述时可能：
      • 说真话。在这种情况下，0 和 1 都是坏人。
        • 在认为 0 是坏人但说真话的情况下，这组玩家中没有一个好人。
      • 说假话。在这种情况下，1 是好人。
        • 在认为 0 是坏人且说假话的情况下，这组玩家中只有一个好人。

在最佳情况下，至多有一个好人，所以返回 1 。
注意，能得到此结论的方法不止一种。

提示：

  • n == statements.length == statements[i].length
  • 2 <= n <= 15
  • statements[i][j] 的值为 0、1 或 2
  • statements[i][i] == 2

题解

看的晕头转向的…

转眼一看，数据大小2≤n≤152 \leq n \leq 15，那就没啥说的了，直接暴力一把梭开干。

我们使用状压枚举所有可能发生的情况，并去验证到底这种情况下是否可行，也就是我们暂定的好人的陈述不能和我们假定的情况自身矛盾。

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
27
func maximumGood(statements [][]int) int {
    n := len(statements)
    res := 0
p:  for i := 0; i < (1 << n); i++ {
        cnt := 0
        for j := 0; j < n; j++ {
            if i & (1 << j) != 0 { //如果j讲的真话
                cnt++
                for k, v := range statements[j] { //检查与假定情况是否相符
                    if v != 2 && v != i >> k & 1 { //如果做出了陈述，并且与i状态表示情况矛盾，就作废当前情况
                        continue p
                    }
                }
            }
        }
        res = max(res, cnt)
    }
    return res
}

func max(i, j int) int {
    if i > j {
        return i
    } else {
        return j
    }
}