Golang每日一练(leetDay0116) 路径交叉、回文对

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^5
• 1 <= 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 <= 5000
• 0 <= 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）暂停更