데이터 구조 문제 풀이 (1) 2020.06.22 - 2020.06.28
현재 Leetcode 를 사용 하 는 가장 큰 문제: 한 문 제 를 푸 는 횟수 가 부족 하고 적어도 다섯 번 은 닦 습 니 다.알고리즘 최적화 사상: 1. 공간 교환 시간 2. 승 차원 (2 차원 으로 올 라 가기)
문제 가 어 리 석 을 때의 문제 풀이 방향:
2020.06.22 - 2020.06.28 부터 매일 이 블 로그 글 을 업데이트 하여 일주일 동안 힘 써 쓴 필기 와 지식의 총 결 을 기록 합 니 다!
배열, 링크, 도약 표
배열 작업 의 시간 복잡 도:
1. 조회: O (1) 2. 삽입: O (n) 3. 삭제: O (n) 4. 머리 삽입: O (n), O (1) 로 최적화 할 수 있 습 니 다. 사용 하 는 방식 은 비교적 큰 메모리 공간 을 신청 한 다음 에 배열 에서 처음에 일부 공간 을 미리 남 겨 두 고 prepend 를 할 때 머리 아래 표 시 를 한 위치 로 옮 길 수 있 습 니 다. 5. 꼬리 삽입: O (1)
링크 작업 시간 복잡 도:
1. 조회: O (n) 2. 삽입: O (1) 3. 삭제: O (1) 4. 머리 삽입: O (1) 5. 꼬리 삽입: O (1)
시계 건 너 뛰 기 (skip list):
점프 표 는 밸 런 스 트 리 와 2 분 검색 트 리 로 삽입, 삭제, 검색 이 모두 O (nlogn) 의 데이터 구조 입 니 다. 가장 큰 장점 은 원리 가 간단 하고 실현 하기 쉬 우 며 확장 이 편리 하고 효율 이 높다 는 것 입 니 다. 따라서 일부 인기 항목 에 서 는 밸 런 스 트 리 를 대체 하 는 데 사 용 됩 니 다. 예 를 들 어 redis 등 주의: 점프 표 는 질서 있 는 링크 에 적 용 됩 니 다.
제목 1: 0 이동
： nums， 0 ， 。
:
: [0,1,0,3,12]
: [1,3,12,0,0]
:
， 。
。
： （LeetCode）
：https://leetcode-cn.com/problems/move-zeroes
。 ， 。
사고: 1. 두 순환, 0 이 나타 난 위 치 를 기록 합 니 다. 2. 새 배열 은 0 이 아 닌 요 소 를 앞 에 놓 고 0 요 소 를 뒤에 놓 습 니 다. 3. index 작업 을 통 해 하 나 는 모든 배열 을 옮 겨 다 니 고 다른 하 나 는 0 이 아 닌 요소 가 배치 해 야 할 위 치 를 기록 합 니 다.
해법 (3 을 예 로 들 면):
class Solution {
public:
void moveZeros(vector<int>& nums) {
int j = 0;
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] != nums[j]) {
nums[j] = nums[i];
if (i != j)
nums[i] = 0;
j++;
}
}
}
제목 2: 두 수의 합
https://leetcode-cn.com/problems/two-sum/submissions/ 정수 배열 nums 와 목표 값 target 을 지정 합 니 다. 이 배열 에서 목표 값 의 두 정 수 를 찾 아 배열 아래 표 시 를 되 돌려 주 십시오.
모든 입력 이 하나의 답 에 만 대응 할 것 이 라 고 가정 할 수 있 습 니 다. 그러나 배열 의 같은 요 소 는 두 번 사용 할 수 없습니다.
예시:
nums = [2, 7, 11, 15], target = 9
nums[0] + nums[1] = 2 + 7 = 9
[0, 1]
출처: 스냅 백 (LeetCode) 링크:https://leetcode-cn.com/problems/two-sum 저작권 은 리베이트 네트워크 의 소유 입 니 다. 상업 전 재 는 정부 에 연락 하여 권한 을 부여 하 십시오. 비 상업 전 재 는 출처 를 밝 혀 주 십시오.
사고: 1. 폭력 해법, 직접 두 순환 으로 두 수의 합 이 존재 하 는 지 여 부 를 직접 옮 겨 다 니 며 시간 복잡 도 는 O (n2) 이다. 2. 해시 가속 으로 목표 치 와 nums [i] 차 이 를 찾 는 수 는 배열 에 존재 하 는 지, 시간 복잡 도 는 O (n) 3. 정렬 후 두 지침 의 방법 으로 한 번 옮 겨 다 니 며 시간 복잡 도 는 O (n) 해법 이다.
vector<int> twoSum(vector<int>& nums, int target) {
int temp;
vector<int> a;
for (int i = 0; i < nums.size(); ++i) {
temp = target - nums[i];
for (int j = 0; j < nums.size(); ++j) {
if (i != j && nums[j] == temp)
{
a.push_back(i);
a.push_back(j);
return a;
}
}
}
return a;
}
해법 2 (hash):
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ans;
map<int, int>hashmap;
for (int i=0; i < nums.size(); ++i) {
if (hashmap[target-nums[i]] && hashmap[target - nums[i] != i+1]){
ans.push_back(i);
ans.push_back(hashmap[target - nums[i]] - 1);
return ans;
}
hashmap[nums[i]] = i + 1;
}
return ans;
}
제목 3: 리스트 반전
단일 체인 시 계 를 반전 하 다.
예시:
: 1->2->3->4->5->NULL
: 5->4->3->2->1->NULL
진급: 당신 은 체인 시 계 를 교체 하거나 재 귀적 으로 반전 시 킬 수 있 습 니 다. 당신 은 두 가지 방법 으로 이 문 제 를 해결 할 수 있 습 니까?
출처: 스냅 백 (LeetCode) 링크:https://leetcode-cn.com/problems/reverse-linked-list 저작권 은 리베이트 네트워크 의 소유 입 니 다. 상업 전 재 는 정부 에 연락 하여 권한 을 부여 하 십시오. 비 상업 전 재 는 출처 를 밝 혀 주 십시오.
사고방식: 1. 교체 방식 반전 목록 2. 귀속 방식 반전 목록
1. 반복 방식 반전 목록
자신의 구현 버 전:
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == nullptr)
return head;
ListNode* pre = head;
ListNode* next = head->next;
ListNode* p_temp;
while(next)
{
p_temp = next->next;
next->next = pre;
pre = next;
next = p_temp;
}
head->next = NULL;
return pre;
}
};
leetcode 구현 버 전
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == nullptr)
return head;
ListNode* pre = nullptr;
ListNode* next = head;
while(next)
{
ListNode *p_temp = next->next;
next->next = pre;
pre = next;
next = p_temp;
}
return pre;
}
};
제목 4: 물 을 가장 많이 담 는 용기
n 개의 부정 정수 a1, a2,..., an 을 드 리 겠 습 니 다. 각 수 는 좌표 중의 한 점 (i, ai) 을 대표 합 니 다. 좌표 안에 n 개의 수직선 을 그 리 겠 습 니 다. 수직선 i 의 두 점 은 각각 (i, ai) 과 (i, 0) 입 니 다.. 그 중 두 개의 선 을 찾 아 x 축 과 함께 구 성 된 용기 에 가장 많은 물 을 수용 할 수 있 도록 한다. 설명: 용 기 를 기울 일 수 없고 n 의 값 은 최소 2 이다. 그림 에서 수직선 은 배열 [1, 8, 6, 2, 5, 4, 8, 3, 7] 을 입력 하 는 것 을 대표 한다. 이 경우 용 기 는 물 을 수용 할 수 있다 (파란색 부분 으로 표시) 의 최대 치 는 49 이다. 예시:
：[1,8,6,2,5,4,8,3,7]
：49
출처: 스냅 백 (LeetCode) 링크:https://leetcode-cn.com/problems/container-with-most-water 저작권 은 버클 네트워크 의 소유 입 니 다. 상업 전 재 는 공식 권한 수여 에 연락 하 십시오. 비 상업 전 재 는 출처 를 밝 혀 주 십시오. 사고: 1. 폭력 해법 2. 동태 계획
1. 폭력 해법:
int maxArea(vector<int>& height) {
int delta_index, sum_max, test_max;
sum_max = 0;
test_max = 0;
for (int i=0; i < height.size(); i++) {
for (int j=i+1; j < height.size(); j++) {
delta_index = abs(i-j);
test_max = min(height[i], height[j]);
if (test_max * delta_index > sum_max) {
sum_max = test_max * delta_index;
}
}
}
return sum_max;
}
2. 동적 기획
int maxArea(vector<int>& height) {
int i = 0, j = height.size()-1;
int res = 0;
while(i < j) {
res = max(res, min(height[i], height[j]) * abs(i-j));
if (height[i] < height[j]) i++;
else j--;
}
return res;
}
class Solution {
int maxArea(vector<int>& height) {
int max = 0;
for (int i = 0, j = height.size() - 1; i < j;) {
int minHeight = height[i] < height[j] ? height[i++] : height[j--];
int area = (j - i + 1) * minHeight;
max = max(max, area);
}
return max;
}
제목 5: 계단 오 르 기
만약 당신 이 계단 을 오 르 고 있다 고 가정 하 세 요. n 단계 가 있어 야 옥상 에 도착 할 수 있 습 니 다. 매번 1 또는 2 개의 계단 을 오 를 수 있 습 니 다. 당신 은 몇 가지 다른 방법 으로 옥상 에 올 라 갈 수 있 습 니까? 주의: n 은 정수 입 니 다. 예 1: 입력: 2 출력: 2 설명: 옥상 에 올 라 갈 수 있 는 두 가지 방법 이 있 습 니 다.
우 리 는 전이 방정식 과 경계 조건 을 통 해 시간 복잡 도와 공간 복잡 도 를 제시 하 는 것 이 어렵 지 않다. 그러나 이곳 의 f (x) f (x) f (x) f (x) 는 f (x - 1) f (x - 1) f (x - 1) 와 f (x - 2) f (x - 2) f (x - 2) f (x - 2) 와 관련 되 기 때문에 우 리 는 '스크롤 배열 사상' 으로 공간 복잡 도 를 O (1) O (1) O (1) 로 최적화 할 수 있다.
class Solution {
public:
int climbStairs(int n) {
int p = 0, q = 0, r = 1;
for (int i = 1; i <= n; ++i) {
p = q;
q = r;
r = p + q;
}
return r;
}
};
：LeetCode-Solution
：https://leetcode-cn.com/problems/climbing-stairs/solution/pa-lou-ti-by-leetcode-solution/
： （LeetCode）
。 ， 。
나의 해법:
class Solution {
public:
int climbStairs(int n) {
int a[n+1];
int k;
a[0] = 1;
a[1] = 2;
int sum = 0;
if (n <= 3)
return n;
else {
for(k = 2; k < n ; ++k) {
a[k] = a[k-1] + a[k-2];
}
return a[k-3] * 2 + a[k-4] * 1;
}
}
};
'1' (육지) 과 '0' (물) 으로 구 성 된 2 차원 격자 를 드 리 겠 습 니 다. 격자 에 있 는 섬의 수 를 계산 해 보 세 요.
섬 은 항상 물 에 둘러싸 여 있 고 모든 섬 은 수평 방향 이나 수직 방향 으로 인접 한 육지 로 만 연결 되 어 있다.
그 밖 에 이 격자 의 네 변 이 모두 물 에 둘러싸 여 있다 고 가정 할 수 있다.
예시 1:
:
11110
11010
11000
00000
: 1
예시 2:
:
11000
11000
00100
00011
: 3
설명: 모든 섬 은 수평 과 / 또는 수직 방향 으로 인접 한 육지 로 만 연결 할 수 있다.
출처: 스냅 백 (LeetCode) 링크:https://leetcode-cn.com/problems/number-of-islands 저작권 은 리베이트 네트워크 의 소유 입 니 다. 상업 전 재 는 정부 에 연락 하여 권한 을 부여 하 십시오. 비 상업 전 재 는 출처 를 밝 혀 주 십시오.
사고방식: 1. BFS 2. DFS 3.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
