Coding-everyday

# 1. 博弈

# 1.1. 跳格子问题

题目描述：

你和你的朋友正在玩棋子跳格子的游戏，而棋盘是一个由n个格子组成的长条，你们两人轮流移动一颗棋子，每次可以选择让棋子跳1-3格，先将棋子移出棋盘的人获得胜利。我们知道你们两人都会采取最优策略，现在已知格子数目，并且初始时棋子在第一格由你操作。请你计算你是否能获胜。

给定格子的数目n(n为不超过300的正整数)。返回一个整数，1代表能获胜，0代表不能获胜。

思路：

  1. 经过枚举发现，只要格子是4的倍数，先走的人必输。
  2. 所以只要格子数不是4的倍数，先走的人只要走一步，即可将剩下的格子弄成4的倍数，这样后走的人必输。
def checkWin(n):
  if (n - 1) % 4 == 0:  # 当前格子站一个格，因此后边有 n-1 格
    return 0
  return 1

# 1.2. 涂色问题

题目描述：

你要在一个nxm的格子图上涂色，你每次可以选择一个未涂色的格子涂上你开始选定的那种颜色。同时为了美观，我们要求你涂色的格子不能相邻，也就是说，不能有公共边，现在问你，在采取最优策略的情况下，你最多能涂多少个格子？

给定格子图的长n和宽m。请返回最多能涂的格子数目。

测试样例： 1,2

返回：1

def getMost(n, m):
  return (n * m + 1) // 2

# 1.3. 赛马问题

题目描述：

作为一个马场的主人，你要安排你的n匹赛马和另一个马场的n匹马比赛。你已经知道了对方马场的出战表，即参加每一场的马的强壮程度。当然你也知道你自己的所有马的强壮程度。我们假定比赛的结果直接由马的强壮程度决定，即更壮的马获胜(若相同则双方均不算获胜)，请你设计一个策略，使你能获得尽量多的场次的胜利。

给定对方每场比赛的马的强壮程度oppo及你的所有马的强壮程度horses(强壮程度为整数，且数字越大越强壮)同时给定n，请返回最多能获胜的场次。

测试样例： [1,2,3],[1,2,3],3

返回：2

def winMost(oppo, horses, n):
  res = 0
  i, j = 0, 0
  oppo.sort()
  horses.sort()

  while i < n and j < n:
    if oppo[i] < horses[j]:
      res += 1
      j += 1
    j += 1

  return res

# 1.4. AB矩阵中移动

题目描述：

A与B做游戏。 在一个n*m的矩阵中的出发点是（1，m），终点是（n,1），规则是只能向左移动一格，向下一格或向左下移动一格，先走到终点的为winner。 A先走。

给定两个整数n和m，请返回最后的获胜者的名字(A或B)。

测试样例： 5 3

返回：B

思路：

  1. 当棋盘大小是奇数 * 奇数大小时，先出走的人必输（后出走的人只要和先出走的人动作一样）。
  2. 所以只需要让对手陷入奇数*奇数的棋盘就赢。
def getWinner(n, m):
  if n % 2 == 1 and m % 2 == 1:
    return 'B'

  return 'A'

# 1.5. 四数相加 II

题目描述： 给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。

为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -228 到 228 - 1 之间，最终结果不会超过 231 - 1 。

例如:

输入: A = [ 1, 2] B = [-2,-1] C = [-1, 2] D = [ 0, 2]

输出: 2

解释: 两个元组如下:

  1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
  2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

思路：

  1. 如果保存四个字典的话，最后就要遍历四次，时间复杂度就是O(n^4)
  2. 现在把A+B保存到一个字典，C+D保存到另一个字典，时间复杂度是O(n^2)
function fourSumCount(A, B, C, D){
  let d = {}
  let d2 = {}
  let res = 0

  for (let item of A){
    for (let it of B) {
      d[item + it] = d[item + it] ? d[item + it] + 1 : 1
    }
  }

  for (let item of C){
    for (let it of D) {
      d2[item + it] = d2[item + it] ? d2[item + it] + 1 : 1
    }
  }

  for (let item in d) {
    let other = -item
    if (d2[other]) {
      res += d[item] * d2[other]
    }
  }

  return res
}

← greedy →