附上我的github倉庫，會(huì)不斷更新leetcode解題答案，提供一個(gè)思路，大家共勉
希望可以給star拗引，鼓勵(lì)繼續(xù)更新解題思路
author: thomas
Leetcode之javascript解題(No442/No485)
No442. Find All Duplicates in an Array(Medium)
題目
Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements that appear twice in this array.
Could you do it without extra space and in O(n) runtime?
Example:
Input:
[4,3,2,7,8,2,3,1]
Output:
[2,3]
這道題給了我們一個(gè)數(shù)組，數(shù)組中的數(shù)字可能出現(xiàn)一次或兩次幌衣，讓我們找出所有出現(xiàn)兩次的數(shù)字
思路
這類問題的一個(gè)重要條件就是
1 ≤ a[i] ≤ n (n = size of array)矾削，不然很難在O(1)空間和O(n)時(shí)間內(nèi)完成。-
方法一：正負(fù)替換的方法
這類問題的核心是就是找
nums[i]和nums[nums[i] - 1]的關(guān)系豁护，我們的做法是哼凯，對(duì)于每個(gè)nums[i]，我們將其對(duì)應(yīng)的nums[nums[i] - 1]取相反數(shù)（因?yàn)樽鴺?biāo)是從0開始）楚里，如果其已經(jīng)是負(fù)數(shù)了断部，說明之前存在過，我們將其加入結(jié)果res中即可當(dāng)然我們每次取值的時(shí)候是取當(dāng)前的絕對(duì)值來給對(duì)應(yīng)的位置取負(fù)數(shù)
Math.abs(elem) - 1;
方法二：遍歷數(shù)組班缎，用lastIndexOf方法蝴光，只要從后查找當(dāng)前值的位置和當(dāng)前不同，那就是我們?nèi)〉闹怠?code>arr.lastIndexOf(elem) !== i)
-
方法三(最優(yōu)解)：
- 在
nums[nums[i]-1]位置累加數(shù)組長度n达址，(注意nums[i]-1有可能越界)蔑祟，所以我們需要對(duì)n取余，最后要找出現(xiàn)兩次的數(shù)只需要看nums[i]的值是否大于2n即可沉唠，最后遍歷完nums[i]數(shù)組為[12, 19, 18, 15, 8, 2, 11, 9]疆虚，我們發(fā)現(xiàn)有兩個(gè)數(shù)字19和18大于2n，那么就可以通過i+1來得到正確的結(jié)果2和3了
- 在
代碼
// 方法一
let arr = [4,3,2,7,8,2,3,1];
var findDuplicates = function(arr) {
let res = [];
arr.forEach((elem, i) => {
let temp = Math.abs(elem) - 1;
if (arr[temp] < 0) {
res.push(temp + 1); // 取的負(fù)值位置+1
}
arr[temp] = -arr[temp]
})
return res;
};
// 方法三
var findDuplicates3 = function(arr) {
let res = [],
len = arr.length;
for (let i = 0; i < len; ++i) {
arr[(arr[i] - 1) % len] += len; // 對(duì)len取余满葛，防止越界
}
for (let i = 0; i < len; ++i) {
if (arr[i] > 2 * len) res.push(i + 1);
}
return res;
};
console.log(findDuplicates3(arr));
No485：Max Consecutive Ones(Easy)
題目
Given a binary array, find the maximum number of consecutive 1s in this array.
Example 1:
Input: [1,1,0,1,1,1]
Output: 3
Explanation: The first two digits or the last three digits are consecutive 1s.
The maximum number of consecutive 1s is 3.
- Note:
The input array will only contain 0 and 1.
The length of input array is a positive integer and will not exceed 10,000
思路
這道題讓我們求最大連續(xù)1的個(gè)數(shù)径簿，不是一道難題。我們可以遍歷一遍數(shù)組嘀韧，用一個(gè)計(jì)數(shù)器cnt來統(tǒng)計(jì)1的個(gè)數(shù)篇亭，方法是如果當(dāng)前數(shù)字為0，那么cnt重置為0乳蛾，如果不是0暗赶，cnt自增1鄙币，然后每次更新結(jié)果res即可
代碼
/**
* Created by zhoubowen on 2018/4/10.
*
* No 485. Max Consecutive Ones
*/
let arr = [1,1,0,1,1,1];
let findMaxconsecutiveOnes = function(arr) {
let max = 0,
count = 0;
arr.forEach((elem, i) => {
if (elem === 1) {
count += 1;
}else {
if (count > max) {
max = count;
}
count = 0;
}
});
// 單獨(dú)判斷以下最后一個(gè)結(jié)果的情況
max = count > max ? count:max;
return max;
};
console.log(findMaxconsecutiveOnes(arr));
