目录
335. 路径交叉 Self-crossing 🌟🌟🌟
336. 回文对 Palindrome Pairs 🌟🌟🌟
🌟 每日一练刷题专栏 🌟
Rust每日一练 专栏
Golang每日一练 专栏
Python每日一练 专栏
C/C++每日一练 专栏
Java每日一练 专栏
335. 路径交叉 Self-crossing
给你一个整数数组 distance 。
从 X-Y 平面上的点 (0,0) 开始，先向北移动 distance[0] 米，然后向西移动 distance[1] 米，向南移动 distance[2] 米，向东移动 distance[3] 米，持续移动。也就是说，每次移动后你的方位会发生逆时针变化。
判断你所经过的路径是否相交。如果相交，返回 true ；否则，返回 false 。
示例 1：
输入：distance = [2,1,1,2] 输出：true
示例 2：
输入：distance = [1,2,3,4] 输出：false
示例 3：
输入：distance = [1,1,1,1] 输出：true
提示：
1 <= distance.length <= 10^51 <= distance[i] <= 10^5
代码：
package main
import "fmt"
func isSelfCrossing(distance []int) bool {
n := len(distance)
if n <= 3 {
return false
}
for i := 3; i < n; i++ {
// 第四条边与第一条边相交
if distance[i] >= distance[i-2] && distance[i-1] <= distance[i-3] {
return true
}
// 第五条边与第一条边重叠或者相交
if i >= 4 && distance[i-1] == distance[i-3] && distance[i]+distance[i-4] >= distance[i-2] {
return true
}
// 第六条边与第一条边相交
if i >= 5 && distance[i-2]-distance[i-4] >= 0 && distance[i]+distance[i-4] >= distance[i-2] && distance[i-1]-distance[i-3] >= 0 && distance[i-1]-distance[i-3] <= distance[i-5] && distance[i-2]-distance[i-4] <= distance[i-1]-distance[i-3] {
return true
}
}
return false
}
func main() {
distance := []int{2,1,1,2}
fmt.Println(isSelfCrossing(distance ))
distance = []int{1,2,3,4}
fmt.Println(isSelfCrossing(distance ))
distance = []int{1,1,1,1}
fmt.Println(isSelfCrossing(distance ))
}
输出：
true
false
true
336. 回文对 Palindrome Pairs
给定一组 互不相同 的单词， 找出所有 不同 的索引对 (i, j)，使得列表中的两个单词， words[i] + words[j] ，可拼接成回文串。
示例 1：
输入：words = ["abcd","dcba","lls","s","sssll"] 输出：[[0,1],[1,0],[3,2],[2,4]] 解释：可拼接成的回文串为 ["dcbaabcd","abcddcba","slls","llssssll"]
示例 2：
输入：words = ["bat","tab","cat"] 输出：[[0,1],[1,0]] 解释：可拼接成的回文串为 ["battab","tabbat"]
示例 3：
输入：words = ["a",""] 输出：[[0,1],[1,0]]
提示：
1 <= words.length <= 50000 <= words[i].length <= 300-
words[i]由小写英文字母组成
代码：
package main
import "fmt"
func palindromePairs(words []string) [][]int {
res := [][]int{}
wordIndexMap := map[string]int{}
for i, word := range words {
wordIndexMap[word] = i
}
for i, word := range words {
for j := 0; j <= len(word); j++ {
prefix := word[:j]
suffix := word[j:]
if isPalindrome(prefix) {
reverseSuffix := reverseString(suffix)
if idx, ok := wordIndexMap[reverseSuffix]; ok && idx != i {
res = append(res, []int{idx, i})
}
}
if isPalindrome(suffix) {
reversePrefix := reverseString(prefix)
if idx, ok := wordIndexMap[reversePrefix]; ok && idx != i && len(suffix) > 0 {
res = append(res, []int{i, idx})
}
}
}
}
return res
}
func isPalindrome(s string) bool {
i, j := 0, len(s)-1
for i < j {
if s[i] != s[j] {
return false
}
i++
j--
}
return true
}
func reverseString(s string) string {
res := ""
for i := len(s) - 1; i >= 0; i-- {
res += string(s[i])
}
return res
}
func main() {
words := []string{"abcd","dcba","lls","s","sssll"}
fmt.Println(palindromePairs(words))
words = []string{"bat","tab","cat"}
fmt.Println(palindromePairs(words))
words = []string{"a", ""}
fmt.Println(palindromePairs(words))
}
输出：
[[1 0] [0 1] [3 2] [2 4]]
[[1 0] [0 1]]
[[0 1] [1 0]]
暴力循环：
package main
import "fmt"
func palindromePairs(words []string) [][]int {
res := [][]int{}
for i := 0; i < len(words); i++ {
for j := i + 1; j < len(words); j++ {
if isPalindrome(words[i] + words[j]) {
res = append(res, []int{i, j})
}
if isPalindrome(words[j] + words[i]) {
res = append(res, []int{j, i})
}
}
}
return res
}
func isPalindrome(s string) bool {
i, j := 0, len(s)-1
for i < j {
if s[i] != s[j] {
return false
}
i++
j--
}
return true
}
func main() {
words := []string{"abcd","dcba","lls","s","sssll"}
fmt.Println(palindromePairs(words))
// 输出: [[0 1] [1 0] [3 2] [2 4]]
words = []string{"bat","tab","cat"}
fmt.Println(palindromePairs(words))
// 输出: [[0 1] [1 0]]
words = []string{"a", ""}
fmt.Println(palindromePairs(words))
// 输出: [[0 1] [1 0]]
}🌟 每日一练刷题专栏 🌟
✨ 持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
☸ 主页：https://hannyang.blog.csdn.net/
|
|
Rust每日一练 专栏（2023.5.16~）更新中... |
|
|
Golang每日一练 专栏（2023.3.11~）更新中... |
|
|
Python每日一练 专栏（2023.2.18~2023.5.18）暂停更 |
|
|
C/C++每日一练 专栏（2023.2.18~2023.5.18）暂停更 |
|
|
Java每日一练 专栏（2023.3.11~2023.5.18）暂停更文章来源地址https://www.toymoban.com/news/detail-533426.html |
文章来源：https://www.toymoban.com/news/detail-533426.html到了这里，关于Golang每日一练(leetDay0116) 路径交叉、回文对的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
