정렬된 배열의 제곱 LeetCode 779
추론
문제를 보고 가장 먼저 든 생각은 배열의 0보다 큰 부분과 0보다 작은 부분의 제곱 크기를 비교하는 것이었습니다. 이렇게 하면 O(n) 시간 복잡도를 달성할 수 있지만 새로운 배열을 추가하면 메모리 소비가 더 많아집니다.
O(n) 시간 복잡도:
java
class Solution {
public int[] sortedSquares(int[] nums) {
int n = nums.length;
int[] newNums = new int[n];
int index = 0;
for(;index < n;index++){
if(nums[index]>=0){
break;
}
}
int left=index-1,right=index;
index=0;
while((left>=0 && left<n) || (right<n && right>=0 )){
if(left>=0&&right<n){
if(nums[left]*nums[left]>nums[right]*nums[right]){
newNums[index]=nums[right]*nums[right];
right++;
}else{
newNums[index]=nums[left]*nums[left];
left--;
}
}else if(left>=0){
newNums[index]=nums[left]*nums[left];
left--;
}else if(right<n){
newNums[index]=nums[right]*nums[right];
right++;
}
index++;
}
return newNums;
}
}
O(n) 시간 복잡도:
java
class Solution {
public int[] sortedSquares(int[] nums) {
int right = nums.length - 1;
int left = 0;
int[] result = new int[nums.length];
int index = right;
while(left<=right){
if(nums[left]*nums[left] > nums[right]*nums[right]){
result[index] = nums[left]*nums[left];
left++;
}else{
result[index] = nums[right]*nums[right];
right--;
}
index--;
}
return result;
}
}
아이디어
- 처음 코드를 작성하기 시작했을 때는 0보다 작은 배열만 있다는 것을 고려하지 않았습니다.
- 작성된 코드를 분석해 보면 동일한 이중 포인터가 사용되었지만 배열의 첫 번째 위치에서 배열의 첫 번째 위치까지 작성된 코드가 배열의 첫 번째 위치에서 배열의 끝까지 작성된 코드에 비해 작성하기가 더 복잡하고 이해도가 떨어집니다.
- 그 후에는 펜을 종이에 쓰기 전에 한 가지 이상의 방법을 생각하고 더 철저하게 고려해야 합니다.
가장 작은 길이의 하위 배열 LeetCode 902
주제 링크: LeetCode 977 -
추론
처음 이 주제를 봤을 때 가장 작은 차수가 목표와 같은 연속적인 하위 배열을 찾는 것으로 보았습니다. 그리고 문제를 푸는 무차별 대입 방식만 생각했는데, 무차별 대입 방식에는 시간 제한이 있었습니다. 그래서 나중에 슬라이딩 윈도우로 변경하여 답을 찾았습니다.
슬라이딩 창 방식:
java
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int sum=0,left=0,result=Integer.MAX_VALUE;
for(int right = 0 ; right < nums.length; right++){
sum += nums[right];
while(sum>=target){
result = Math.min(result,right-left+1);
sum -= nums[left];
left++;
}
}
return (result==Integer.MAX_VALUE)?0:result;
}
}
폭력적인 솔루션:
java
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int result = Integer.MAX_VALUE;
for(int i = 0; i < nums.length; i++){
int sum = 0;
for(int j = i; j < nums.length; j++){
sum += nums[j];
if(sum >= target){
result = Math.min(result,j-i+1);
break;
}
}
}
return (result==Integer.MAX_VALUE)?0:result;
}
}
아이디어
- 질문을 볼 때 주의해야 할 몇 가지 중요한 조건이 있습니다.
- 슬라이딩 창에 대해 배웠습니다.
- 더 어려운 접두사 및 + 이진 조회가 있습니다:
첫째, 방법 1은 각 첨자에서 시작하여 모든 간격을 검색하는 가장 명확하고 이해하기 쉬운 방법이기도 한 폭력적인 열거를 사용합니다. 하지만 똑똑한 아이들은 이 탐색 과정을 시작하는 각 첨자가 1, 2, 3, 4 와 같이 반복되는 간격을 많이 계산한다는 것을 발견했습니다. 1을 +2, +3, +4를 계산할 때 첨자로, 2를 +3, +4를 계산할 때 첨자로 사용하는 등 구간을 반복적으로 계산하지 않도록 최적화하는 방법을 생각해냈고, 합계 문제의 어떤 구간에서도 O(1) 시간 안에 빠르게 구할 수 있는 접두사 합이라는 아이디어를 생각해냈습니다. 그런 다음 , s[j] - s[i] >=target을 구하도록 문제를 쉽게 개선할 수 있지만, 이 접근 방식은 변경하지 않으면 접두사 합계 배열에서 폭력 열거의 방법 1과 유사한 접두사 합계 배열, 첨자 j 뒤에 각 i의 열거 마지막으로이 선형 값 문제와 같이 약간의 변경으로 공동 이등분 조회를 수행하여 s[j] >=s[i] + target을 찾을 수 있음을 발견했습니다. 대상. 이것은 접두사 합계 + 이등분 검색으로 이어지며, 공식 솔루션은 실제로 순회 프로세스의 최적화에서 접두사 합계에서 이등분까지의 반복 계산을 피하기 위해 아이디어를 명확하게 설명하지 못할 수 있으므로 예제를 통해 배우는 것이 편리하도록 사고 순서를 명확히하는 것이 가장 좋습니다.
java
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int[] sums = new int[nums.length+1];
int result = Integer.MAX_VALUE;
for(int i = 1; i <= nums.length;i++){
sums[i] = sums[i-1] + nums[i-1];
}
for(int i = 1; i <= nums.length;i++){
int targetnum = target + sums[i-1];
int bound = Arrays.binarySearch(sums,targetnum);
if(bound<0){
bound = -bound - 1;
}
if(bound <= nums.length){
result = Math.min(result,bound - i + 1);
}
}
return result == Integer.MAX_VALUE ?0:result;
}
}
나선형 행렬 II LeetCode 59
주제 링크: LeetCode 209 -
추론
주제를 보고 아이디어는 있지만 코딩하는 방법을 모릅니다.
슬라이딩 창 방식:
java
class Solution {
public int[][] generateMatrix(int n) {
int[][] result = new int[n][n];
int i=0,j=0;
int num=1;
int loop=0,start=0;
while(loop++ < n / 2){
for(j=start;j<n-loop;j++){
result[start][j]=num++;
}
for(i=start;i<n-loop;i++){
result[i][j]=num++;
}
for(;j>=loop;j--){
result[i][j]=num++;
}
for(;i>=loop;i--){
result[i][j]=num++;
}
start++;
}
if (n % 2 == 1) {
result[start][start] = num;
}
return result;
}
}
아이디어
여전히 더 많은 알고리즘 문제 연습이 필요합니다.