current position:Home>leetcode 1222. Queens That Can Attack the King(python)
leetcode 1222. Queens That Can Attack the King(python)
2022-01-31 15:54:47 【Wang Daya】
「 This is my participation 11 The fourth of the yuegengwen challenge 16 God , Check out the activity details :2021 One last more challenge 」
describe
On an 8x8 chessboard, there can be multiple Black Queens and one White King.
Given an array of integer coordinates queens that represents the positions of the Black Queens, and a pair of coordinates king that represent the position of the White King, return the coordinates of all the queens (in any order) that can attack the King.
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 queen at [0,1] can attack the king cause they're in the same row.
The queen at [1,0] can attack the king cause they're in the same column.
The queen at [3,3] can attack the king cause they're in the same diagnal.
The queen at [0,4] can't attack the king cause it's blocked by the queen at [0,1].
The queen at [4,0] can't attack the king cause it's blocked by the queen at [1,0].
The queen at [2,4] can't attack the king cause it's not in the same row/column/diagnal as the king.
Copy code
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]]
Copy code
Example 3:
Input: queens = [[5,6],[7,7],[2,1],[0,7],[1,6],[5,1],[3,7],[0,3],[4,0],[1,2],[6,3],[5,0],[0,4],[2,2],[1,1],[6,4],[5,4],[0,0],[2,6],[4,5],[5,2],[1,4],[7,5],[2,3],[0,5],[4,2],[1,0],[2,7],[0,1],[4,6],[6,1],[0,6],[4,3],[1,7]], king = [3,4]
Output: [[2,3],[1,4],[1,6],[3,7],[4,3],[5,4],[4,5]]
Copy code
Note:
1 <= queens.length <= 63
queens[i].length == 2
0 <= queens[i][j] < 8
king.length == 2
0 <= king[0], king[1] < 8
At most one piece is allowed in a cell.
Copy code
analysis
According to the meaning , Give a 8x8 The chessboard of , There are many black queens and a white king . Given an array of integer coordinates representing the position of the black queen queens And a coordinate representing the position of the White King king , Return the coordinates of all queens who can attack the king ( In any order ).
Although I haven't played this game , I don't know how the queen attacked the king , But after looking at the example, I basically understand , When the queen and the king are in the same column or row or diagonal and there are no other pieces in the middle , Then the queen can attack the king . It's easy to solve the problem if you know this , There are only four diagonals from top to bottom, left and right, a total of eight directions , Find the position of the first queen, record it in the result and return it .
answer
class Solution(object):
def queensAttacktheKing(self, queens, king):
"""
:type queens: List[List[int]]
:type king: List[int]
:rtype: List[List[int]]
"""
result = []
x,y = king
# up
for r in range(x-1,-1,-1):
if [r,y] in queens:
result.append([r,y])
break
# down
for r in range(x+1, 8):
if [r,y] in queens:
result.append([r,y])
break
# left
for c in range(y-1,-1,-1):
if [x,c] in queens:
result.append([x,c])
break
# right
for c in range(y+1, 8):
if [x,c] in queens:
result.append([x,c])
break
tmp_x = x
tmp_y = y
# diagnal
for _ in range(8):
if tmp_x-1>=0 and tmp_y-1>=0 and [tmp_x-1,tmp_y-1] in queens:
result.append([tmp_x-1,tmp_y-1])
break
else:
tmp_x -= 1
tmp_y -= 1
tmp_x = x
tmp_y = y
# diagnal
for _ in range(8):
if tmp_x+1<8 and tmp_y+1<8 and [tmp_x+1,tmp_y+1] in queens:
result.append([tmp_x+1,tmp_y+1])
break
else:
tmp_x += 1
tmp_y += 1
tmp_x = x
tmp_y = y
# diagnal
for _ in range(8):
if tmp_x-1>=0 and tmp_y+1<8 and [tmp_x-1,tmp_y+1] in queens:
result.append([tmp_x-1,tmp_y+1])
break
else:
tmp_x -= 1
tmp_y += 1
tmp_x = x
tmp_y = y
# diagnal
for _ in range(8):
if tmp_x+1<8 and tmp_y-1>=0 and [tmp_x+1,tmp_y-1] in queens:
result.append([tmp_x+1,tmp_y-1])
break
else:
tmp_x += 1
tmp_y -= 1
return result
Copy code
Running results
Runtime: 28 ms, faster than 67.86% of Python online submissions for Queens That Can Attack the King.
Memory Usage: 13.4 MB, less than 75.00% of Python online submissions for Queens That Can Attack the King.
Copy code
analysis
Of course, the above solution is still too redundant , There are more ingenious solutions to the code , The core idea is the same as above , Find the position of the first queen from eight different directions and record it in the result , But the code is much simpler .
answer
class Solution(object):
def queensAttacktheKing(self, queens, king):
"""
:type queens: List[List[int]]
:type king: List[int]
:rtype: List[List[int]]
"""
result = []
for i, j in [[-1, -1], [-1, 0], [-1, 1], [0, 1], [1, 1], [1, 0], [1, -1], [0, -1]]:
x, y = king
while 0 <= x < 8 and 0 <= y < 8:
x += i
y += j
if [x, y] in queens:
result.append([x, y])
break
return result
Copy code
Running results
Runtime: 28 ms, faster than 67.86% of Python online submissions for Queens That Can Attack the King.
Memory Usage: 13.3 MB, less than 92.86% of Python online submissions for Queens That Can Attack the King.
Copy code
Original link :leetcode.com/problems/qu…
Your support is my greatest motivation
copyright notice
author[Wang Daya],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/01/202201311554453329.html
The sidebar is recommended
- Django (make an epidemic data report)
- Daily python, Part 8 - if statement
- Django model class 1
- The same Python code draws many different cherry trees. Which one do you like?
- Python code reading (Chapter 54): Fibonacci sequence
- Django model class 2
- Python crawler Basics
- Mapping 3D model surface distances using Python VTK
- How to implement encrypted message signature and verification in Python -- HMAC
- leetcode 1945. Sum of Digits of String After Convert(python)
guess what you like
-
leetcode 2062. Count Vowel Substrings of a String(python)
-
Analysis of Matplotlib module of Python visualization
-
Django permission management
-
Python integrated programming -- visual hot search list and new epidemic situation map
-
[Python data collection] scripy realizes picture download
-
Python interface automation test framework (basic part) -- loop statement of process control for & while
-
Daily python, Chapter 9, while loop
-
Van * Python | save the crawled data with docx and PDF
-
Five life saving Python tips
-
Django frequency control
Random recommended
- Python - convert Matplotlib image to numpy Array or PIL Image
- Python and Java crawl personal blog information and export it to excel
- Using class decorators in Python
- Untested Python code is not far from crashing
- Python efficient derivation (8)
- Python requests Library
- leetcode 2047. Number of Valid Words in a Sentence(python)
- leetcode 2027. Minimum Moves to Convert String(python)
- How IOS developers learn Python Programming 5 - data types 2
- leetcode 1971. Find if Path Exists in Graph(python)
- leetcode 1984. Minimum Difference Between Highest and Lowest of K Scores(python)
- Python interface automation test framework (basic) -- basic syntax
- Detailed explanation of Python derivation
- Python reptile lesson 2-9 Chinese monster database. It is found that there is a classification of color (he) desire (Xie) monsters during operation
- A brief note on the method of creating Python virtual environment in Intranet Environment
- [worth collecting] for Python beginners, sort out the common errors of beginners + Python Mini applet! (code attached)
- [Python souvenir book] two people in one room have three meals and four seasons: 'how many years is it only XX years away from a hundred years of good marriage' ~?? Just come in and have a look.
- The unknown side of Python functions
- Python based interface automation test project, complete actual project, with source code sharing
- A python artifact handles automatic chart color matching
- Python crawls the map of Gaode and the weather conditions of each city
- leetcode 1275. Find Winner on a Tic Tac Toe Game(python)
- leetcode 2016. Maximum Difference Between Increasing Elements(python)
- Run through Python date and time processing (Part 2)
- Application of urllib package in Python
- Django API Version (II)
- Python utility module playsound
- Database addition, deletion, modification and query of Python Sqlalchemy basic operation
- Tiobe November programming language ranking: Python surpasses C language to become the first! PHP is about to fall out of the top ten?
- Learn how to use opencv and python to realize face recognition!
- Using OpenCV and python to identify credit card numbers
- Principle of Python Apriori algorithm (11)
- Python AI steals your voice in 5 seconds
- A glance at Python's file processing (Part 1)
- Python cloud cat
- Python crawler actual combat, pyecharts module, python data analysis tells you which goods are popular on free fish~
- Using pandas to implement SQL group_ concat
- How IOS developers learn Python Programming 8 - set type 3
- windows10+apache2. 4 + Django deployment
- Django parser