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

简介: 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)暂停更


目录
打赏
0
0
0
0
74
分享
相关文章
Java快速入门之数组、方法
### Java快速入门之数组与方法简介 #### 一、数组 数组是一种容器,用于存储同种数据类型的多个值。定义数组时需指定数据类型,如`int[]`只能存储整数。数组的初始化分为静态和动态两种: - **静态初始化**:直接指定元素,系统自动计算长度,如`int[] arr = {1, 2, 3};` - **动态初始化**:手动指定长度,系统给定默认值,如`int[] arr = new int[3];` 数组访问通过索引完成,索引从0开始,最大索引为`数组.length - 1`。遍历数组常用`for`循环。常见操作包括求和、找最值、统计特定条件元素等。
Java基础(六):数组
Java基础(六):数组
33 10
Java基础(六):数组
Java数组:静态初始化与动态初始化详解
本文介绍了Java中数组的定义、特点及初始化方式。
66 12
探索常见数据结构:数组、链表、栈、队列、树和图
探索常见数据结构:数组、链表、栈、队列、树和图
148 64
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
100 5
Java 数组
【10月更文挑战第19天】Java 数组是一种非常实用的数据结构,它为我们提供了一种简单而有效的方式来存储和管理数据。通过合理地使用数组,我们能够提高程序的运行效率和代码的可读性。更加深入地了解和掌握 Java 数组的特性和应用,为我们的编程之旅增添更多的精彩。
49 4
提高 Java 数组性能的方法
【10月更文挑战第19天】深入探讨了提高 Java 数组性能的多种方法。通过合理运用这些策略,我们可以在处理数组时获得更好的性能表现,提升程序的运行效率。
63 2
|
4月前
|
Java“(array) <X> Not Initialized” (数组未初始化)错误解决
在Java中,遇到“(array) &lt;X&gt; Not Initialized”(数组未初始化)错误时,表示数组变量已被声明但尚未初始化。解决方法是在使用数组之前,通过指定数组的大小和类型来初始化数组,例如:`int[] arr = new int[5];` 或 `String[] strArr = new String[10];`。
130 2
|
4月前
|
什么是带有示例的 Java 中的交错数组?
什么是带有示例的 Java 中的交错数组?
77 9
|
4月前
|
Java数组动态扩容和动态缩减
Java数组动态扩容和动态缩减
46 3
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等