Leetcode 的动人之处 算法题解 in Swift ( 最小面积矩形 , 939 ) 及其 Code Review
Leetcode 的动人之处挺多的，本文继续指出看代码的姿势
在竞赛回顾里面查看
( Leetcode 的竞赛很强大，每个星期天都有 )
进入竞赛，
1.png
下滑到竞赛回顾，点击感兴趣的一场
（就是找到想做的题目）
2.png
下滑，选择更多
3.png
点击感兴趣的题目
4.png
看到代码。
（ 代码这么多，肯定看不完 ）
5.png
有了 Leetcode 讨论区，为什么还推荐这样看代码？
（ 虽然是很强的人，写的代码 ）
因为这是竞赛的时候写的代码，很赶时间。
哪里有后面的那么多的设计。
很不优雅，糙，快，直观。
题目做不出来，可以了解一下。
题目描述: 939. 最小面积矩形
给定在 xy 平面上的一组点，确定由这些点组成的矩形的最小面积，其中矩形的边平行于 x 轴和 y 轴。
如果没有任何矩形，就返回 0。
示例 1：
输入：[[1,1],[1,3],[3,1],[3,3],[2,2]]
输出：4
示例 2：
输入：[[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]
输出：2
提示：
1 <= points.length <= 500
0 <= points[i][0] <= 40000
0 <= points[i][1] <= 40000
所有的点都是不同的。
官方题解: 通过对角线找点
( 这个没有中文的，有英文的，在主站上。本文描述一下，简单点 )
直觉这么走:
对于数组中的每一对点，设想他们是一个矩形的对角线，然后就简单了。
矩形有两条对角线，如果另外一条对角线上面的点，也在给定的数组里面，就找出了一个满足要求的矩形。
用散列集合确认四个点。
举个例子:
有了两个点 (1, 1) 和 (5, 5) 。然后就看一下 (1, 5) 和 (5, 1) 有没有。
如果有，就找到了一个满足要求的矩形。
然后就是，找出最小的矩形。
算法这么走:
把所有的点，放入一个哈希集合。对于每一对点，如果哈希集合 set 中包含，相关矩形四个不同的顶点，（ 换句话说， 交换下 x 与 y， 如果能在哈希集合中找到另一条对角线的两个点）
该矩形的面积就是一个潜在的解。
题解 ( 改进前):
class Solution {
struct Point_Dng: Hashable{
var x: Int
var y: Int
init(_ x: Int, _ y: Int) {
self.x = x
self.y = y
}
var hashValue: Int{
return x * 100000 + y
}
static func == (_ lhs: Point_Dng, _ rhs: Point_Dng) -> Bool{
return lhs.x == rhs.x && lhs.y == rhs.y
}
}
func minAreaRect(_ points: [[Int]]) -> Int {
let points_new = points.map({ (point: [Int]) -> Point_Dng in
return Point_Dng(point[0], point[1])
})
let set = Set(points_new)
var ans = Int.max
for point in points{
for point_piece in points{
if point[0] != point_piece[0] , point[1] != point_piece[1] , set.contains(Point_Dng(point[0], point_piece[1])) ,set.contains(Point_Dng(point_piece[0], point[1])) {
ans = min(ans, abs((point_piece[1] - point[1] ) * (point_piece[0] - point[0])))
}
}
}
if ans == Int.max {
return 0
}
else{
return ans
}
}
}
Leetcode 的强大之处 算法题解 in Swift ( 有效的数独 , 36 ) 及其 Code Review
Leetcode 的强大之处，挺多的。
本文写的是，其强大的讨论区。
讨论区里面，有各种具有启发性的代码。
（换句话说，就是有很强的代码。看了，觉得脑洞大开，大神们把语言的语法特性发挥到了极致）
里面有各种常见语言的实现
( 这里指 Leetcode 主站的， 中文站点的同一功能弱了一点 )
进入 Leetcode 的题目，
1.png
进入讨论区，里面的讨论挺多的，这道题就有 470 个帖子。
本文推荐选择 "Most Votes",
事实就是得分高的代码，看起来爽
2.png
也可以搜索一下自己关心的，
一般是按语言来搜索。
3.png
就 Leetcode 算法题，本文认为有了 Leetcode 的讨论区，和官方题解 （有些没有，最近的题都有）
其他的资料...... ,都好像有些弱
(不喜欢英语的少年，除外)
题目描述: 36. 有效的数独
判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
1
上图是一个部分填充的有效的数独。
数独部分空格内已填入了数字，空白格用 '.' 表示。
示例 :
输入:
2
输出: true
题解 ( 改进前):
下面的解法，非常直观，
根据数独的成立条件，分三次检查数字，按行，按列，按块
（先横着来，再竖着来，最后一块一块来）
因为数独有数字的唯一性，这里使用散列集合
每一次处理，通过的情况分两种，
扫描一轮，1-9 刚刚好。或者含有 ''."， 其他的数字各不相同。
class Solution {
func isValidSudoku(_ board: [[Character]]) -> Bool {
let count = board.count
var set = Set<Character>()
for i in 0..<count{
// 横着来，按行，检查数字
set = Set(board[i])
var num = board[i].reduce(0 , {(result : Int, char : Character)
in
var cent = 0
if String(char) == "."{
cent = 1
}
return result + cent
})
// 每一次处理，通过本次循环的情况分两种，
// 扫描一轮，1-9 刚刚好。或者含有 ''."， 其他的数字各不相同。
// 这里做了一个针对处理
if num > 0 , count - num != set.count - 1{
return false
}
else if num == 0, set.count != count{
return false
}
// 竖着来，按列，检查数字
set = Set(board.reduce([Character]() , { resultArray, chars in
return resultArray + [chars[i]]
}))
num = board.reduce(0 , {(result : Int, chars : [Character])
in
var cent = 0
if String(chars[i]) == "."{
cent = 1
}
return result + cent
})
if num > 0 , count - num != set.count - 1{
return false
}
else if num == 0, set.count != count{
return false
}
// 一块一块来， 按块，检查数字
let characters = board.flatMap{
return $0
}
let fisrtMiddle = ( i/3 ) * 27 + ( i % 3 ) * 3 + 1
let secondMiddle = fisrtMiddle + 9
let thirdMiddle = fisrtMiddle + 18
// 找出每一块
let arrayThree = [characters[fisrtMiddle - 1], characters[fisrtMiddle], characters[fisrtMiddle + 1],
characters[secondMiddle - 1], characters[secondMiddle], characters[secondMiddle + 1],
characters[thirdMiddle - 1], characters[thirdMiddle], characters[thirdMiddle + 1]]
set = Set(arrayThree)
num = arrayThree.reduce(0 , {(result : Int, char : Character)
in
var cent = 0
if String(char) == "."{
cent = 1
}
return result + cent
})
if num > 0 , count - num != set.count - 1{
return false
}
else if num == 0, set.count != count{
return false
}
}
return true
}
}
Code Review ：
算法上的提高
没必要计算 "." 的个数。先处理数据，把 "." 过滤掉， 再创建散列集合。
按行，按列，按块查找重复数字，就直观了很多。不需要考虑 "." 的干扰。
命名要规范，
怎么知道 set 里面包含什么？
不清晰， 不知道 num 是什么的个数。
cent 和 arrayThree 是什么鬼?
改进代码
if String(char) == "." , 可以直接写成 if char == ".
因为 "." 是字符串的字面量，也是字符的字面量。不需要把字符转化为字符串。
改进闭包
按行，计算一次循环，不为 "." 的
var num = board[i].reduce(0 , {(result : Int, char : Character)
in
var cent = 0
if String(char) == "."{
cent = 1
}
return result + cent
})
1⃣️ 直接简写闭包，减少临时变量
var num = board[i].reduce(0 , {(result, char) in
char == "." ? result + 1 : result
})
这样处理更高效
let rowDigits = board[i].filter { $0 != "." }
if rowDigits.count != Set(rowDigits).count {
return false
}
set = Set(board.reduce([Character]() , { resultArray, chars in
return resultArray + [chars[i]]
}))
2⃣️ 科学类型转换
let column = board.map { $0[i]} // Column #i
set = Set(column)
// 找出每一块
let fisrtMiddle = ( i/3 ) * 27 + ( i % 3 ) * 3 + 1
let secondMiddle = fisrtMiddle + 9
let thirdMiddle = fisrtMiddle + 18
// 找出每一块
let arrayThree = [characters[fisrtMiddle - 1], characters[fisrtMiddle], characters[fisrtMiddle + 1],
characters[secondMiddle - 1], characters[secondMiddle], characters[secondMiddle + 1],
characters[thirdMiddle - 1], characters[thirdMiddle], characters[thirdMiddle + 1]]
3⃣️ 使用数组片段 ( slice ), 发挥高阶函数的威力
let firstRow = 3 * (i / 3)
let firstCol = 3 * (i % 3)
let block = board[firstRow..<firstRow+3].flatMap { $0[firstCol..<firstCol+3]}
最后的代码:
class Solution {
func isValidSudoku(_ board: [[Character]]) -> Bool {
for i in 0..<9 {
// 按行，检查数字
let rowDigits = board[i].filter { $0 != "." }
if rowDigits.count != Set(rowDigits).count {
return false
}
// 按列，检查数字
let colDigits = board.map { $0[i] }.filter { $0 != "." }
if colDigits.count != Set(colDigits).count {
return false
}
// 按块，检查数字
let firstRow = 3 * (i / 3)
let firstCol = 3 * (i % 3)
let blockDigits = board[firstRow..<firstRow+3].flatMap { $0[firstCol..<firstCol+3]}
.filter { $0 != "." }
if blockDigits.count != Set(blockDigits).count {
return false
}
}
return true
}
}
另一种解法, 更加的函数式，性能差一些
使用 27 的散列集合， 对应 9 次循环 X 三种方式 （ 按行， 按块，按列）
排除掉 "." , 有重复的数字，就返回错误。
两层遍历顺利完成后，返回成功。
class Solution {
func isValidSudoku(_ board: [[Character]]) -> Bool {
var rowSets = Array(repeating: Set<Character>(), count: 9)
var colSets = Array(repeating: Set<Character>(), count: 9)
var blockSets = Array(repeating: Set<Character>(), count: 9)
for (i, row) in board.enumerated() {
for (j, char) in row.enumerated() where char != "." {
if !rowSets[i].insert(char).inserted {
return false
}
if !colSets[j].insert(char).inserted {
return false
}
let block = (i / 3) + 3 * (j / 3)
if !blockSets[block].insert(char).inserted {
return false
}
}
}
return true
}
}
感谢 Martin R 大神 code review 我的代码
相关代码:
强大的代码: Python 实现
[SDK]新浪微博请求授权显示错误页面的解决方法(error:redirect_uri_mismatch)
今天在弄新浪微博分享的时候,再次遇到这个错误,由此想到可能很多人也会遭遇这个坑,特意写下来,以便后人.
在新浪微博开放平台创建了移动移动,然后把APP ID和 AppSecret填好后,轻车熟路地去调用授权页面,哦~哦~,出错了:"访问出错了.你所访问的站点在新浪微博的认证失败,请联系****或者稍后再试.(error:redirect_uri_mismatch) 新浪微博版权所有."
好吧,是祸躲不过,登录http://open.weibo.com ,选择[管理中心]->[我的应用]->["您的应用名"]->展开左侧[应用信息]->[高级信息]->OAuth2.0 授权设置 右上角[编辑]->在框里填入回调地址即可.(前期测试应用时随便填个公司主页即可.两个地址可以相同)
网友评论