JS LeetCode 배열 알고리즘 구현 (1)
5307 단어 LeetCode 알고리즘
1. 두 수의 합
4. 567917. 하나의 정수 배열 과 하나의 목표 치 를 정 하고 배열 과 목표 치 로 하 는 두 개의 수 를 찾 습 니 다
4. 567917. 모든 입력 이 하나의 답 에 만 대응 하고 같은 요 소 를 중복 적 으로 이용 할 수 없다 고 가정 할 수 있다
사고: 배열 을 옮 겨 다 니 며 배열 의 특정한 요 소 를 이 요소 뒤에 있 는 다른 요소 와 비교 하고 목표 값 과 비교 하 며 같 으 면 두 요소 의 색인 을 되 돌려 줍 니 다.코드 는 다음 과 같 습 니 다:
var twoSum = function(nums, target) {
for(var i=0; i < nums.length; i++){
for(var j = i+1; j < nums.length; j++){
if(nums[i] + nums[j] == target){
return [i,j]
}
}
}
};
더 좋 은 실현:
var twoSum = function(nums, target) {
var map = {};
for(var i=0; i
26. 정렬 배열 의 중복 항목 삭제
4. 567917. 정렬 배열 을 지정 합 니 다. 반복 되 는 요 소 를 제자리 에서 삭제 하고 모든 요 소 를 한 번 만 나타 나 게 해 야 합 니 다. 제거 한 배열 의 새로운 길 이 를 되 돌려 줍 니 다
4. 567917. 추가 배열 공간 을 사용 하지 마 십시오. 입력 배열 을 제자리 에서 수정 하고 O (1) 추가 공간 을 사용 하 는 조건 에서 완성 해 야 합 니 다
사고: 배열 의 두 번 째 요소 부터 배열 의 모든 요 소 를 그의 이전 요소 와 비교 하고 두 요소 가 같 지 않 으 면 현재 비교 요 소 를 0 에서 배열 에 저장 하고 두 숫자 가 같 으 면 다음 순환 을 계속 합 니 다.코드 는 다음 과 같 습 니 다:
var removeDuplicates = function (A) {
if (A == null || A.length == 0) {
return 0;
}
var index = 1;
for (var i = 1; i < A.length; i++) {
if (A[i] != A[i-1])
{
A[index] = A[i];
index++;
}
}
return index;
};
27. 원소 제거
4. 567917. 배열 을 지정 합 니 다. nums 값 val, 모든 수 치 를 제자리 에서 제거 해 야 합 니 다. val 제거 한 배열 의 새 길 이 를 되 돌려 줍 니 다
4. 567917. 추가 배열 공간 을 사용 하지 마 십시오. 입력 배열 을 제자리 에서 수정 하고 O (1) 추가 공간 을 사용 하 는 조건 에서 완성 해 야 합 니 다
4. 567917. 원소 의 순 서 는 바 꿀 수 있다.너 는 배열 에서 새로운 길이 뒤의 요 소 를 초과 하 는 것 을 고려 할 필요 가 없다
코드 는 다음 과 같 습 니 다:
var removeElement = function(nums, val) {
var index = 0;
for (var i = 0; i < nums.length; i++) {
if (nums[i] != val) {
nums[index] = nums[i];
index++;
}
}
nums = nums.slice(0,index);
return index;
};
더 좋 은 실현:
var removeElement = function(nums, val) {
for(let i = 0; i< nums.length; i++) {
if(nums[i] == val) {
nums.splice(i, 1)
i-- // ,
}
}
};
35. 삽입 위치 검색
4. 567917. 정렬 배열 과 목표 값 을 지정 하고 배열 에서 목표 값 을 찾 아 색인 을 되 돌려 줍 니 다.대상 값 이 배열 에 존재 하지 않 으 면 순서대로 삽 입 된 위 치 를 되 돌려 줍 니 다
4. 567917. 배열 에 중복 요소 가 없다 고 가정 할 수 있 습 니 다
사고방식: 여 기 는 세 가지 상황 으로 나 뉘 어야 한다. 삽입 위 치 는 첫 번 째, 중부, 끝 에 있다.첫 번 째 부분 에 삽입 할 때 0 을 되 돌려 줍 니 다.삽입 위치 가 끝 에 있 을 때 배열 의 길 이 를 되 돌려 줍 니 다.삽입 위치 가 중부 에 있 을 때 이분법 으로 요소 와 삽입 요 소 를 비교 하여 삽입 위 치 를 확인 합 니 다.코드 는 다음 과 같 습 니 다:
var searchInsert = function(nums, target) {
if (nums.indexOf(target) != -1) { //
return nums.indexOf(target);
} else { //
var start = 0, end = nums.length - 1;
if (target < nums[start]) { //
return 0;
} else if (target > nums[end]) { //
return nums.length;
} else { //
while (start < end - 1) { // star end
var center = parseInt((start + end) / 2);
if (nums[center] > target) {
end = center;
} else if (nums[center] < target) {
start = center;
} else {
return center;
}
}
if (nums[end] >= target) {
return end;
} else {
return end - 1;
}
}
}
};
더 좋 은 실현:
var searchInsert = function(nums, target) {
let len = nums.length
if (len === 0) {
return 0
}
for (let i = 0; i < len; i++) {
let num = nums[i]
if (target <= num ) {
return i
}
}
return len
};
53. 최대 하위 순서 와
4. 567917. 정수 배열 을 지정 합 니 다.
nums
,최대 와 연속 을 가 진 하위 그룹 (하위 그룹 은 최소 하나의 요 소 를 포함 합 니 다) 을 찾 아 최대 와.. 사고방식: 변수 저장 요소 서열 에 가장 큰 합 을 설정 합 니 다.배열 을 하나씩 추가 하고 특정한 요소 에 추가 할 때 마이너스 가 되면 현재 와 직접 0 을 설정 합 니 다. 매번 순환 할 때마다 현재 와 최대 와 비교 합 니 다. 현재 와 비교적 크 면 현재 와 설정 을 새로운 최대 와 합 니 다.코드 는 다음 과 같 습 니 다:
var maxSubArray = function(nums) {
if (nums.length == 0 || nums == null) { //
return 0;
}
var maxSum = 0, currSum = 0;
nums.forEach(function (value,index,nums) {
currSum += value;
if (currSum < 0) { // 0 0
currSum = 0;
}
maxSum = (maxSum < currSum) ? currSum : maxSum;
});
if (maxSum == 0) {
return Math.max(...nums);
}
return maxSum;
};
더 좋 은 실현:
var maxSubArray = function (nums) {
let count = nums[0], maxCount = nums[0]
for (let i = 1; i < nums.length; i++) {
count = Math.max(count + nums[i], nums[i])
maxCount = Math.max(maxCount, count)
}
return maxCount
};