轮转数组
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
示例 2:
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]
思路：都是在数组末尾和开头做操作 直接用数组方法,
不过用数组方法并没有体现算法思想，用算法思想来搞反转三次，第一次反转整个数组，第二次反转前k个，第三次反转剩余部分，
// 最快方法
var rotate = function(nums,key){
nums.unshift(...nums.splice(nums.length - k % nums.length, k))
}
//此方法超时
var rotate = function(nums, k) {
let nums1 = [...nums]
for(let i = 0 ; i < k ; i++){
let res = nums1.pop()
nums1.unshift(res)
}
return nums1
};
//用算法做
const reverse = (nums, start, end) => {
while (start < end) {
[nums[start++], nums[end--]] = [nums[end], nums[start]];
}
}
function rotate(nums, k) {
if (!nums || nums.length === 0) {
return [];
}
k %= nums.length;
if (k <= 0) {
return nums;
}
reverse(nums, 0, nums.length - 1);
console.log(nums)
reverse(nums, 0, k - 1);
console.log(nums)
reverse(nums, k, nums.length - 1);
console.log(nums)
return nums;
}
//[ 6, 5, 4, 3, 2, 1 ]
//[ 4, 5, 6, 3, 2, 1 ]
//[ 4, 5, 6, 1, 2, 3 ]
除自身以外数组的乘积
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 **不要使用除法，**且在 O(_n_) 时间复杂度内完成此题。
示例 1:
输入: nums = [1,2,3,4]
输出: [24,12,8,6]
示例 2:
输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]
思路:前缀和和后缀和相乘 两次for循环
var productExceptSelf = function(nums) {
let answer = new Array(nums.length).fill(1)
let prefix = 1;
for (let i = 1; i < nums.length; i++) {
prefix = nums[i -1] * prefix
answer[i] *= prefix
}
let suffix = 1;
for(let i = nums.length -2; i >= 0; i--){
suffix = nums[i + 1] *suffix
answer[i] *= suffix
}
return answer
};
找到字符串中所有字母异位词
中等
相关标签
相关企业
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
示例 1:
输入: s = “cbaebabacd”, p = “abc”
输出: [0,6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。
示例 2:
输入: s = “abab”, p = “ab”
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 “ab”, 它是 “ab” 的异位词。
起始索引等于 1 的子串是 “ba”, 它是 “ab” 的异位词。
起始索引等于 2 的子串是 “ab”, 它是 “ab” 的异位词。
思路：维护一个滑动窗口 用charCodeat方法获取字母的ascall码值.
var findAnagrams = function(s, p) {
const len = s.length
// 首先定义一个长度为26的数组charNumList，用来存放每个小写字母出现的次数。
const charNumList = new Array(26).fill(0)
const res = []
let left = 0, right = 0
for (let i = 0; i < p.length; i++) {
// 对于字符串p中的每个字母，通过p[i].charCodeAt() - 97获取其ASCII码值，并将其减去97，
// 得到该字母在charNumList中对应的下标。将该下标的元素值+1，表示该字母出现了一次。
charNumList[p[i].charCodeAt() - 97]++
}
while (right < len) {
// charNumList[s[right].charCodeAt() - 97]-- 将当前字符对应的元素值-1，表示该字符出现了一次。
charNumList[s[right].charCodeAt() - 97]--
// charNumList[s[right].charCodeAt() - 97] < 0，
// 当前字符在s中出现的次数已经超过了p中出现的次数，
// 则需要移动左指针进行调整，直到当前字符在s中出现的次数小于等于p中出现的次数。
while (charNumList[s[right].charCodeAt() - 97] < 0) {
charNumList[s[left].charCodeAt() - 97]++
left++
}
//说明找到了一个满足条件的“字母异位词”，将left保存在结果数组res中
if (right - left + 1 === p.length) {
res.push(left)
}
right++
}
return res
};