leetcode
[leetcode] 689. Maximum Sum of 3 Non-Overlapping Subarrays
[leetcode] 689. Maximum Sum of 3 Non-Overlapping Subarrays
2024.12.28https://leetcode.com/problems/maximum-sum-of-3-non-overlapping-subarrays/description/ 해당 문제는 정수배열 nums 와 k 가 주어졌을 때 겹치지 않는 최대합을 가지는 길이 k 의 부분 배열 3개를 찾아서 반환하는 문제입니다여기서 주의할 점은 정답이 여러개 인 경우 index 가 작은것 부터 반환해야 합니다. Approach해당 문제는 총 3개의 부분 배열을 반환해야 합니다 그러므로 3 개의 section 으로 분할 할 수 있고 이것을 left, middle, right 라고 정의 하겠습니다. 먼저 sliding window 를 통해 구간 합을 미리 구해 두겠습니다.val sums = IntArray(n) { i -> nums.sl..
leetcode - 862. Shortest Subarray with Sum at Least K
leetcode - 862. Shortest Subarray with Sum at Least K
2024.11.17https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/description/?envType=daily-question&envId=2024-11-17 Approach해당 문제를 O(N) 시간 복잡도로 문제를 해결 하기 위해서 PrefixSum 과 단조 증가 (Monotonic increasing) Queue 를 사용할 예정입니다. 해당 문제를 한글로 번역해보자면 다음과 같습니다. 정수 배열 nums와 정수 k가 주어졌을 때, 다음 조건을 만족하는 가장 짧은 부분 배열의 길이를 반환하세요:부분 배열의 합이 최소한 k 이상이어야 함부분 배열은 비어있지 않아야 함만약 이러한 조건을 만족하는 부분 배열이 존재하지 않는다면 -1을 반환여기서 **..
leetcode: Maximum Sum Circular Subarray (kadane 알고리즘)
leetcode: Maximum Sum Circular Subarray (kadane 알고리즘)
2024.11.10https://leetcode.com/problems/maximum-sum-circular-subarray/ 해당 문제는 kadane 알고리즘 방법으로 접근하여 문제를 해결 하였습니다. Approach Kadane's algorithm을 사용하여 일반적인 최대 부분합을 O(n)에 구합니다.순환하는 경우는 전체 합에서 최소 부분합을 빼서 구합니다.모든 원소가 음수인 경우는 별도로 처리합니다.시간복잡도: O(n) 공간복잡도: O(1)전체 배열의 합 (total): 5 + (-3) + 5 = 7최소 부분합 (minSum): -3연속된 부분 배열 중 가장 작은 합total - minSum = 7 - (-3) = 10이것이 바로 [5,5]를 선택했을 때의 합과 같습니다!이렇게 되는 이유는:순환 배열에서 양 끝의 ..
Leetcode - Gas Station
Leetcode - Gas Station
2024.03.02Problem There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i]. You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations. Given two integer arrays gas and cost, return the starting gas station's index if you ..
Leetcode86. partition list (kotlin)
Leetcode86. partition list (kotlin)
2023.04.22https://leetcode.com/problems/partition-list/ Partition List - LeetCode Can you solve this real interview question? Partition List - Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x. You should preserve the original relative order of the no leetcode.com Given the head of a linked list and a value x, partition..
Leetcode79. Word Search (w. kotlin)
Leetcode79. Word Search (w. kotlin)
2023.04.16Given an m x n grid of characters board and a string word, return true if word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once. Example 1: val board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]] val word = "SEE" Output: true..