当前位置：首页 > article >正文

0224-leetcode-459.重复的子字符串、283. 移动零

article 2025/2/25 21:49:07

459.重复的子字符串

题目描述

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

示例 1:

输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。

示例 2:

输入: s = "aba"
输出: false

示例 3:

输入: s = "abcabcabcabc"
输出: true
解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)

提示：

1 <= s.length <= 104
s 由小写英文字母组成

解题思路：

假设字符串 s 的长度为 n，如果 s 可以由其一个子串重复构成，那么这个子串的长度必须是 n 的因子。
遍历所有 n 的因子（除了 n 本身），对于每个因子 i，检查 s 的前 i 个字符是否可以重复多次构成整个字符串 s。
如果找到这样的子串，则返回 true；如果遍历完所有因子都没有找到，则返回 false。

repeat()函数

在 JavaScript 中，repeat() 是字符串（String）对象的一个方法，它返回一个新字符串，该字符串包含了被连接在一起的指定数量的原始字符串的副本。

repeat() 方法的语法如下：

str.repeat(count)

str: 要被重复的原始字符串。
count: 一个整数，表示要重复的次数。这个参数必须大于等于 0，并且小于 Infinity。如果是 0 到 -1 之间的小数，会进行取整操作。如果 count 是负数或者 Infinity，会抛出 RangeError。如果 count 是 NaN，则会被视为 0。

以下是一些使用 repeat() 方法的例子：

console.log("abc".repeat(0)); // 输出: ""
console.log("abc".repeat(1)); // 输出: "abc"
console.log("abc".repeat(2)); // 输出: "abcabc"
console.log("abc".repeat(3.5)); // 输出: "abcabcabc" (3.5 被取整为 3)

如果使用 repeat() 方法时提供的 count 参数不是有效的数字，或者在 count 为负数或 Infinity 时，会抛出错误：

console.log("abc".repeat(-1)); // 抛出 RangeError
console.log("abc".repeat(Infinity)); // 抛出 RangeError
console.log("abc".repeat(NaN)); // 输出: ""

在前面给出的代码示例中，repeat() 方法用于创建一个由子串 pattern 构成的重复字符串，其重复次数等于原字符串 s 的长度除以子串 pattern 的长度。如果这个重复字符串与原字符串 s 相等，那么就说明原字符串可以由这个子串重复构成。

代码实现

var repeatedSubstringPattern = function(s) {
    const n=s.length;
    //如果字符串s长度是1，就不是由它的字串重复多次构成的，这是因为案例过不了才知道的
    if(n===1) return false;
    //遍历检查字符串的所有因子
    for(let i=1;i<n/2+1;i++){
        if(n%i===0){
            //所有可能的字串的长度：从1-s/2，分别遍历尝试
            const pattern=s.slice(0,i);
            //对于字串的长度i，如果是重复子字符串构成，也需要重复n/i次才能变成s
            let repeatedPattern=pattern.repeat(n/i);
            if(repeatedPattern===s){
                return true;
            }
        }
    }

    return false;
};

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
    let lastNonZeroFoundAt = 0; // 记录最后一个非零元素的位置
     // 将所有非零元素移动到数组前面
    for(let i=0;i<nums.length;i++){
        if (nums[i] !== 0) {
            nums[lastNonZeroFoundAt++] = nums[i];
        }
    }
     // 将剩余的位置填充为零
    for (let i = lastNonZeroFoundAt; i < nums.length; i++) {
        nums[i] = 0;
    }
    
};

283.移动零

题目描述

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]
输出: [0]

提示:

1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1

进阶：你能尽量减少完成的操作次数吗？

用一个指针（我们可以称之为insertPos）来记录下一个非0数字应该放置的位置。
遍历数组，每次找到非0的数字，就把它放到insertPos指向的位置，然后insertPos加1。
遍历完成后，所有非0数字都已经按原顺序排列在数组的前面了。
最后，从insertPos开始到数组末尾，把所有位置都设置为0。

解题思路

我们需要做的是把数组中的所有0都移动到数组的末尾，同时保持其他数字的顺序不变。可以通过以下步骤来完成这个任务：

用写指针（我们可以称之为writePointer）来记录下一个非0数字应该放置的位置。
通过读指针（readPointer）遍历数组，每次找到非0的数字，就把它放到writePointer指向的位置，然后writePointer加1。
遍历完成后，所有非0数字都已经按原顺序排列在数组的前面了。
最后，从writePointer开始到数组末尾，把所有位置都设置为0。

代码实现

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
    let writePointer = 0; // 写指针，指向下一个非零元素应该放置的位置

// 遍历数组，用读指针i 
for (let readPointer = 0; readPointer < nums.length; readPointer++) { 
    if (nums[readPointer] !== 0) 
    { // 如果当前元素不是0，就将其复制到写指针的位
    nums[writePointer] = nums[readPointer];
    writePointer++; // 写指针向前移动 
    } 
}

// 将写指针之后的所有位置填充为0 
for (let i = writePointer; i < nums.length; i++) 
{ nums[i] = 0; }
};

查看全文

http://www.kler.cn/a/560869.html