首页 > 其他分享 >[LeetCode] 1222. Queens That Can Attack the King

[LeetCode] 1222. Queens That Can Attack the King

时间:2023-09-16 09:04:29浏览次数:38  
标签:king King int attack Attack 皇后 Queens dir queens

On a 0-indexed 8 x 8 chessboard, there can be multiple black queens ad one white king.

You are given a 2D integer array queens where queens[i] = [xQueeni, yQueeni] represents the position of the ith black queen on the chessboard. You are also given an integer array king of length 2 where king = [xKing, yKing] represents the position of the white king.

Return the coordinates of the black queens that can directly attack the king. You may return the answer in any order.

Example 1:

Input: queens = [[0,1],[1,0],[4,0],[0,4],[3,3],[2,4]], king = [0,0]
Output: [[0,1],[1,0],[3,3]]
Explanation: The diagram above shows the three queens that can directly attack the king and the three queens that cannot attack the king (i.e., marked with red dashes).

Example 2:

Input: queens = [[0,0],[1,1],[2,2],[3,4],[3,5],[4,4],[4,5]], king = [3,3]
Output: [[2,2],[3,4],[4,4]]
Explanation: The diagram above shows the three queens that can directly attack the king and the three queens that cannot attack the king (i.e., marked with red dashes).

Constraints:

  • 1 <= queens.length < 64
  • queens[i].length == king.length == 2
  • 0 <= xQueeni, yQueeni, xKing, yKing < 8
  • All the given positions are unique.

可以攻击国王的皇后。

在一个 8x8 的棋盘上,放置着若干「黑皇后」和一个「白国王」。

给定一个由整数坐标组成的数组 queens ,表示黑皇后的位置;以及一对坐标 king ,表示白国王的位置,返回所有可以攻击国王的皇后的坐标(任意顺序)。

又是一道在棋盘上的模拟题。注意题目要求,需要返回的是在与国王分别在同一行,同一列,同一条对角线上的能最先攻击到国王的皇后的坐标。有几个地方题目没有点出,比如在同一行(同一列或者同一条对角线也是同理)上,国王的左边和右边各有一个与国王距离相等的皇后,那么这两个皇后都需要被记录。

具体做法是我先用一个二维 boolean 数组记录棋盘上所有皇后的位置,标记为 true。然后从国王的位置开始,往八个方向延伸(这是皇后能走的方向),在每个方向上只要遇到皇后就停下并把皇后的坐标加入结果集。

时间O(1) - 8x8

空间O(1) - 8x8

Java实现

 1 class Solution {
 2     public List<List<Integer>> queensAttacktheKing(int[][] queens, int[] king) {
 3         List<List<Integer>> res = new ArrayList<>();
 4         boolean[][] board = new boolean[8][8];
 5         for (int[] q : queens) {
 6             int qx = q[0];
 7             int qy = q[1];
 8             board[qx][qy] = true;
 9         }
10 
11         int[][] dirs = new int[][] {{-1, 0}, {-1, 1}, {-1, -1}, {0, 1}, {0, -1}, {1, 0}, {1, 1}, {1, -1}};
12         for (int[] dir : dirs) {
13             int x = king[0] + dir[0];
14             int y = king[1] + dir[1];
15             while (x >= 0 && x < 8 && y >= 0 && y < 8) {
16                 if (board[x][y] == true) {
17                     res.add(Arrays.asList(x, y));
18                     break;
19                 }
20                 x += dir[0];
21                 y += dir[1];
22             }
23         }
24         return res;
25     }
26 }

 

LeetCode 题目总结

标签:king,King,int,attack,Attack,皇后,Queens,dir,queens
From: https://www.cnblogs.com/cnoodle/p/17706256.html

相关文章

  • Codeforces Round 773 (Div. 2) B. Power Walking
    有\(n\)个增幅道具,第\(i\)个道具种类为\(a_i\),一个人的强度\(w\)为他所有道具的种类数。对于\(k]\in[1,n]\),询问将\(n\)个道具分配给\(k\)个人且每个人至少分配到一个道具后,能够得到的最想强度和\(\sum_{i=1}^{n}w_i\)。观察一:最低强度和\(\sum_{i=1}^{k}w......
  • 【刷题笔记】51. N-Queens
    题目Then-queenspuzzleistheproblemofplacingnqueensonann×nchessboardsuchthatnotwoqueensattackeachother.Givenaninteger n,returnalldistinctsolutionstothe n-queenspuzzle.Eachsolutioncontainsadistinctboardconfigurationoft......
  • KingBaseES与MySQL的区别
    KingBaseES与MySQL的区别当涉及到数据库管理系统(DBMS)时,Kingbase和MySQL是两个备受关注的选项。本文将详细介绍Kingbase和MySQL之间的区别,包括它们的特点、体系结构、功能和适用场景。我们将从多个方面进行比较,帮助读者更好地了解和选择适合自己需求的数据库管理系统。一、简介......
  • Skywalking链路跟踪
    中文文档:https://github.com/SkyAPM/document-cn-translation-of-skywalkinghttps://skywalking.apache.org/zh/2020-04-19-skywalking-quick-start/安装:https://blog.csdn.net/qq_33204709/article/details/121473297使用1、下载neget<PackageReferenceInclude="SkyAP......
  • Kingbase中手写Mysql底层函数DATE_FORMAT()
    Kingbase中手写Mysql底层函数DATE_FORMAT()分析底层函数的实现逻辑MySQL的DATE_FORMAT()函数其底层逻辑涉及多个组件和模块。以下是DATE_FORMAT()函数的大致实现逻辑:解析日期格式字符串:DATE_FORMAT()函数接受两个参数,一个是日期值,另一个是格式字符串。首先,MySQL解析格......
  • Java多线程____BlockingQueue阻塞队列使用
    packagecom.frame.base.thread;importjava.util.concurrent.BlockingQueue;importjava.util.concurrent.ArrayBlockingQueue;/***并发编程____阻塞队列*/publicclassBlockingQueueTest{ publicstaticvoidmain(String[]args)throwsInterruptedException{......
  • Working With Strings In Python.
    #字符串操作在Python中,`string`是一种不可变的数据类型,用于表示文本或字符序列,可以使用单引号或双引号将字符串括起来。<fontcolor="#C7EDCC">所有修改和生成字符串的操作的实现方法都是另一个内存片段中新生成一个字符串对象。</font>##创建字符串```pystr1="Lefti......
  • iOS YTKNetworking网络框架增加text/plain支持
    网络请求有时候报错"Requestfailed:unacceptablecontent-type:text/plain"解决办法:在基类初始化时新增以下方法即可-(void)converContentTypeConfig{YTKNetworkAgent*agent=[YTKNetworkAgentsharedAgent];NSSet*acceptableContentTypes=[NSSetsetWithOb......
  • Breaking Changes When Upgrading from EF Core 6 to 7: What You Need to Know
    EntityFrameworkCore(EFCore)isapopularObject-RelationalMapping(ORM)frameworkusedby.NETdevelopersfordatabaseoperations.WiththereleaseofEFCore7,manydevelopersareconsideringupgradingtheirprojectstotakeadvantageofthenewfe......
  • Seeing What You Said: Talking Face Generation Guided by a Lip Reading Expert 论
    最近一直在看虚拟人像. 最关键的论文就是wav2lip.目前项目中也是用的这个.一个视频加一个语音,就可以生成用视频里面的头,加语音的新视频.现在看这篇论文SeeingWhatYouSaid:TalkingFaceGenerationGuidedbyaLipReadingExpert.主要是搜了没有相关论文,所以就自己......