5271. 访问所有点的最小时间
平面上有 n 个点，点的位置用整数坐标表示 points[i] = [xi, yi]。请你计算访问所有这些点需要的最小时间（以秒为单位）。
你可以按照下面的规则在平面上移动：
- 每一秒沿水平或者竖直方向移动一个单位长度，或者跨过对角线（可以看作在一秒内向水平和竖直方向各移动一个单位长度）。
- 必须按照数组中出现的顺序来访问这些点。
示例 1：
输入：points = [[1,1],[3,4],[-1,0]] 输出：7 解释：一条最佳的访问路径是： [1,1] -> [2,2] -> [3,3] -> [3,4] -> [2,3] -> [1,2] -> [0,1] -> [-1,0] 从 [1,1] 到 [3,4] 需要 3 秒 从 [3,4] 到 [-1,0] 需要 4 秒 一共需要 7 秒
示例 2：
输入：points = [[3,2],[-2,2]] 输出：5
提示：
points.length == n1 <= n <= 100points[i].length == 2-1000 <= points[i][0], points[i][1] <= 1000
var minTimeToVisitAllPoints = function(points) {
// let res = 0;
// for(let i=0; i<points.length-1; i++){
// let [x, y] = points[i];
// let [x1, y1] = points[i+1];
// let xl = (y1-y)/(x1-x);
// if(xl>0){
// if(xl===1){
// // 斜率1，x的值也可能从大到小，所以y值也可能是递减
// res+=Math.abs(x1-x)
// }else{
// res+=(Math.abs(y1-x1)+Math.abs(x1-x))
// }
// }else{
// if(xl===-1){
// res+=Math.abs(x-x1)
// }else{
// res+=((-x1-y1)+Math.abs(x1-x))
// }
// }
// }
// return res
// };
/**
* @param {number[][]} points
* @return {number}
*/
var minTimeToVisitAllPoints = function(points) {
let result = 0;
for (let i = 1; i < points.length; i++) {
result += Math.max(Math.abs(points[i - 1][0] - points[i][0]), Math.abs(points[i - 1][1] - points[i][1]));
}
return result;
};
class Solution(object): def minTimeToVisitAllPoints(self, points): """ :type points: List[List[int]] :rtype: int """ ans = 0 ls = points[0] for v in points: dx = abs(v[0]-ls[0]) dy = abs(v[1]-ls[1]) ans += min(dx, dy) + abs(dx-dy) ls = v return ans
搜索推荐系统
给你一个产品数组 products 和一个字符串 searchWord ，products 数组中每个产品都是一个字符串。
请你设计一个推荐系统，在依次输入单词 searchWord 的每一个字母后，推荐 products 数组中前缀与 searchWord 相同的最多三个产品。如果前缀相同的可推荐产品超过三个，请按字典序返回最小的三个。
请你以二维列表的形式，返回在输入 searchWord 每个字母后相应的推荐产品的列表。
示例 1：
输入：products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
输出：[
["mobile","moneypot","monitor"],
["mobile","moneypot","monitor"],
["mouse","mousepad"],
["mouse","mousepad"],
["mouse","mousepad"]
]
解释：按字典序排序后的产品列表是 ["mobile","moneypot","monitor","mouse","mousepad"]
输入 m 和 mo，由于所有产品的前缀都相同，所以系统返回字典序最小的三个产品 ["mobile","moneypot","monitor"]
输入 mou， mous 和 mouse 后系统都返回 ["mouse","mousepad"]
示例 2：
输入：products = ["havana"], searchWord = "havana"
输出：[["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]
示例 3：
输入：products = ["bags","baggage","banner","box","cloths"], searchWord = "bags"
输出：[["baggage","bags","banner"],["baggage","bags","banner"],["baggage","bags"],["bags"]]
示例 4：
输入：products = ["havana"], searchWord = "tatiana"
输出：[[],[],[],[],[],[],[]]
提示：
1 <= products.length <= 1000
1 <= Σ products[i].length <= 2 * 10^4
products[i] 中所有的字符都是小写英文字母。
1 <= searchWord.length <= 1000
searchWord 中所有字符都是小写英文字母。
/** * @param {string[]} products * @param {string} searchWord * @return {string[][]} */ var suggestedProducts = function(products, searchWord) { const sortP = products.sort(); const result = []; result.push(sortP); for (let i = 0; i < searchWord.length; i++) { result.push([]); for (let j = 0; j < result[i].length; j++) { if (result[i][j][i] === searchWord[i]) { result[i+1].push(result[i][j]); } } } const r = []; for (let i = 0; i < searchWord.length; i++) { r.push([]); for (let j = 0; j < result[i+1].length;j++) { r[i].push(result[i+1][j]); if (j === 2) break; } } return r; };
找出井字棋的获胜者
A 和 B 在一个 3 x 3 的网格上玩井字棋。
井字棋游戏的规则如下：
玩家轮流将棋子放在空方格 (" ") 上。
第一个玩家 A 总是用 "X" 作为棋子，而第二个玩家 B 总是用 "O" 作为棋子。
"X" 和 "O" 只能放在空方格中，而不能放在已经被占用的方格上。
只要有 3 个相同的（非空）棋子排成一条直线（行、列、对角线）时，游戏结束。
如果所有方块都放满棋子（不为空），游戏也会结束。
游戏结束后，棋子无法再进行任何移动。
给你一个数组 moves，其中每个元素是大小为 2 的另一个数组（元素分别对应网格的行和列），它按照 A 和 B 的行动顺序（先 A 后 B）记录了两人各自的棋子位置。
如果游戏存在获胜者（A 或 B），就返回该游戏的获胜者；如果游戏以平局结束，则返回 "Draw"；如果仍会有行动（游戏未结束），则返回 "Pending"。
你可以假设 moves 都 有效（遵循井字棋规则），网格最初是空的，A 将先行动。
示例 1：
输入：moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
输出："A"
解释："A" 获胜，他总是先走。
"X " "X " "X " "X " "X "
" " -> " " -> " X " -> " X " -> " X "
" " "O " "O " "OO " "OOX"
示例 2：
输入：moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]]
输出："B"
解释："B" 获胜。
"X " "X " "XX " "XXO" "XXO" "XXO"
" " -> " O " -> " O " -> " O " -> "XO " -> "XO "
" " " " " " " " " " "O "
示例 3：
输入：moves = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]]
输出："Draw"
输出：由于没有办法再行动，游戏以平局结束。
"XXO"
"OOX"
"XOX"
示例 4：
输入：moves = [[0,0],[1,1]]
输出："Pending"
解释：游戏还没有结束。
"X "
" O "
" "
提示：
1 <= moves.length <= 9
moves[i].length == 2
0 <= moves[i][j] <= 2
moves 里没有重复的元素。
moves 遵循井字棋的规则。
class Solution {
public String tictactoe(int[][] ms) {
int a[][] = new int[3][3];
int l = ms.length;
for(int i=0;i<l;++i){
int s = i%2;
if(s==0){
s = -1;
}
a[ms[i][0]][ms[i][1]] = s;
if(win(a)){
return i%2==0?"A":"B";
}
}
if(l==9){
return "Draw";
}
return "Pending";
}
public boolean win(int a[][]){
for(int i=0;i<3;++i){
int hs = 0;int zs =0;
for(int j=0;j<3;++j){
hs += a[i][j];
zs += a[j][i];
}
if(hs==3||hs==-3||zs==3||zs==-3) return true;
}
int s1 = a[0][0]+a[1][1]+a[2][2];
int s2 = a[0][2]+ a[1][1]+a[2][0];
return s1==3||s1==-3||s2==3||s2==-3;
}
}
var tictactoe = function(moves) {
let mat = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
moves.forEach((move, index) => {
mat[move[0]][move[1]] = index % 2 ? 'B' : 'A'
})
for (let i = 0; i < 3; i ++) {
let cntA = 0
let cntB = 0
for (let j = 0; j < 3; j ++) {
if (mat[i][j] === 'A') {
cntA ++
}
if (mat[i][j] === 'B') {
cntB ++
}
}
if (cntA === 3) {
return 'A'
}
if (cntB === 3) {
return 'B'
}
}
for (let i = 0; i < 3; i ++) {
let cntA = 0
let cntB = 0
for (let j = 0; j < 3; j ++) {
if (mat[j][i] === 'A') {
cntA ++
}
if (mat[j][i] === 'B') {
cntB ++
}
}
if (cntA === 3) {
return 'A'
}
if (cntB === 3) {
// console.log(1)
return 'B'
}
}
let cntA = 0
let cntB = 0
for (let i = 0; i < 3; i ++) {
if (mat[i][i] === 'A') {
cntA++
}
if (mat[i][i] === 'B') {
cntB++
}
if (cntA === 3) {
return 'A'
}
if (cntB === 3) {
// console.log(2)
return 'B'
}
}
cntA = 0
cntB = 0
for (let i = 0; i < 3; i ++) {
if (mat[i][2 - i] === 'A') {
cntA++
}
if (mat[i][2 - i] === 'B') {
cntB++
}
if (cntA === 3) {
return 'A'
}
if (cntB === 3) {
// console.log(3)
return 'B'
}
}
return moves.length === 9 ? 'Draw' : 'Pending'
};
/**
* @param {number[][]} moves
* @return {string}
*/
var isSuccess = (arr)=>{
// let x0s = arr.reduce((init, val)=>init+val[0], 0);
// let x1s = arr.reduce((init, val)=>init+val[1], 0);
// 这个条件只能保证对称
// if(x0s === x1s && x0s ===3 && arr.length===3) return true;
if(arr.length>=3){
// 可能有4个元素
// let x0 = arr[0][0], y0 = arr[0][1];
// let res1 = arr.every(([x, y])=>{
// return x === x0
// })
// let res2 = arr.every(([x, y])=>{
// return y === y0
// })
// if(res1 || res1) return true;
let res1 = [], r1 = 0,r2 = 0,r3 = 0;
let res2 = [], n1 = 0,n2 = 0,n3 = 0;
res1 = arr.map(m=>m[0]);
res2 = arr.map(m=>m[1]);
for(let i=0, len=res1.length; i<len; i++){
let r = res1[i]
if(r===0){
r1++;
}
if(r===1){
r2++;
}
if(r===2){
r3++;
}
}
if(r1 ===3 || r2 ===3 || r3 ===3) return true
for(let i=0, len=res2.length; i<len; i++){
let n = res2[i]
if(n===0){
n1++;
}
if(n===1){
n2++;
}
if(n===2){
n3++;
}
}
if(n1 ===3 || n2 ===3 || n3 ===3) return true
let f1 = false, f2 = false,f3 = false;
for(let i=0, len=arr.length; i<len; i++){
let [x, y] = arr[i];
if(x===0 && y===0){
f1 = true;
}
if(x===2 && y===2){
f2 = true
}
if(x===1 && y===1){
f3 = true
}
}
if(f1 && f2 && f3) return true
let g1 = false, g2 = false,g3 = false;
for(let i=0, len=arr.length; i<len; i++){
let [x, y] = arr[i];
if(x===0 && y===2){
g1 = true;
}
if(x===1 && y===1){
g2 = true;
}
if(x===2 && y===0){
g3 = true;
}
}
if(g1 && g2 && g3) return true
}
return false
}
var tictactoe = function(moves) {
let xs =[], os=[];
moves.forEach((m, i)=>{
if(i%2===0){
xs.push(m)
}else{
os.push(m)
}
})
if(isSuccess(xs)){
return "A";
}
if(isSuccess(os)){
return "B";
}
if(!isSuccess(xs) && !isSuccess(os)){
if(moves.length === 9){
return "Draw"
}else{
return "Pending"
}
}
};
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-winner-on-a-tic-tac-toe-game
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。