413. 等差数列划分

如果一个数列 至少有三个元素 ,并且任意两个相邻元素之差相同,则称该数列为等差数列。

  • 例如,[1,3,5,7,9][7,7,7,7][3,-1,-5,-9] 都是等差数列。
    给你一个整数数组 nums ,返回数组 nums 中所有为等差数组的 子数组 个数。

  • 子数组 是数组中的一个连续序列。

  1. 示例 1:

    1
    2
    3
    输入:nums = [1,2,3,4]
    输出:3
    解释:nums 中有三个子等差数组:[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。
  2. 示例 2:

    1
    2
    输入:nums = [1]
    输出:0
  • 提示:

    1. 1 <= nums.length <= 5000
    2. -1000 <= nums[i] <= 1000

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 差分 + 计数
var numberOfArithmeticSlices = function(nums) {
const n = nums.length;
if (n === 1) {
return 0;
}

let d = nums[0] - nums[1], t = 0;
let ans = 0;
// 因为等差数列的长度至少为 3,所以可以从 i=2 开始枚举
for (let i = 2; i < n; ++i) {
if (nums[i - 1] - nums[i] === d) {
++t;
} else {
d = nums[i - 1] - nums[i];
t = 0;
}
ans += t;
}
return ans;
};

139. 单词拆分

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明:

  • 拆分时可以重复使用字典中的单词。

  • 你可以假设字典中没有重复的单词。

  • 示例 1:

    1
    2
    3
    输入: s = "leetcode", wordDict = ["leet", "code"]
    输出: true
    解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"
  • 示例 2:

    1
    2
    3
    4
    输入: s = "applepenapple", wordDict = ["apple", "pen"]
    输出: true
    解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"
    注意你可以重复使用字典中的单词。
  • 示例 3:

    1
    2
    输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
    输出: false

题 解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> wordDictSet = new HashSet(wordDict);
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
}