Given a string s, return the longest palindromic substring in s.
Example 1:
Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.
Example 2:
Input: s = "cbbd"
Output: "bb"
Constraints:
1 <= s.length <= 1000
s consist of only digits and English letters.
Solution
Approach #0
func longestPalindrome(s string) string {
n := len(s)
if n < 2 {
return s
}
dp := make([][]bool, n)
for i := 0; i < n; i++ {
dp[i] = make([]bool, n)
dp[i][i] = true
}
maxLen := 1
start := 0
for c := 2; c <= n; c++ {
for i := 0; i < n; i++ {
j := c + i - 1
if j >= n {
break
}
if s[i] != s[j] {
dp[i][j] = false
} else {
if j-i < 3 {
dp[i][j] = true
} else {
dp[i][j] = dp[i+1][j-1]
}
}
if dp[i][j] && j-i+1 > maxLen {
maxLen = j - i + 1
start = i
}
}
}
return s[start : start+maxLen]
}
Description
An integer array is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.
For example, [1,3,5,7,9], [7,7,7,7], and [3,-1,-5,-9] are arithmetic sequences.
Given an integer array nums, return the number of arithmetic subarrays ofnums.
A subarray is a contiguous subsequence of the array.
Example 1:
Input: nums = [1,2,3,4]
Output: 3
Explanation: We have 3 arithmetic slices in nums: [1, 2, 3], [2, 3, 4] and [1,2,3,4] itself.
Example 2:
Input: nums = [1]
Output: 0
Constraints:
1 <= nums.length <= 5000
-1000 <= nums[i] <= 1000
Solution
Approach #0: Too much memory used
func numberOfArithmeticSlices(nums []int) (ans int) {
n := len(nums)
if n < 3 {
return 0
}
v := make([]int, n-1)
for i := 0; i < n-1; i++ {
v[i] = nums[i+1] - nums[i]
}
for c := 3; c <= n; c++ {
for i := 0; i < n; i++ {
if i+c > n {
break
}
p := true
for j := i; j < i+c-2; j++ {
p = p && v[j] == v[j+1]
if !p {
break
}
}
if p {
ans++
}
}
}
return
}
Approach #1
func numberOfArithmeticSlices(nums []int) (ans int) {
n := len(nums)
if n == 1 {
return
}
d, t := nums[1]-nums[0], 0
for i := 2; i < n; i++ {
if nums[i]-nums[i-1] == d {
t++
} else {
d, t = nums[i]-nums[i-1], 0
}
ans += t
}
return
}
