[hyunahOh] 7월 5주차 과제

[hyunahOh]

Climbing Stairs - https://leetcode.com/problems/climbing-stairs/

// 시간 O(n), 공간 O(n)

const cache = [];

var climbStairs = function(n) {
  cache[0] = 1;
  cache[1] = 1;

  for (let i = 2; i<= n; i++) {
    cache[i] = cache[i-1] + cache[i-2];
  }

  return cache[n];
};

// 시간 O(n), 공간 O(1)

var climbStairs = function(n) {
  let a = 1;
  let b = 1;

  for (let i = 2; i<= n; i++) {
    if (i%2 === 0) {
      a += b;
    } else {
      b += a;
    }
  }

  if (n%2 === 0) {
    return a;
  } else {
    return b;
  }
} 

[hyunahOh]

• Maximum Subarray - https://leetcode.com/problems/maximum-subarray/

// 시간 O(n), 공간 O(n)

 /**
 [-2,1,-3,4,-1,2,1,-5,4]
 [-2,1,-2,4, 3,5,6, 1,5]
  */
var maxSubArray = function(nums) {
    const partial = [];

    partial.push(nums[0]);

    for (let i=1; i<nums.length; i++) {
        partial.push(Math.max(partial[i-1], 0) + nums[i]);
    }

    return Math.max(...partial);
};

// 시간 O(n), 공간 O(1)

 /**
 [-2,1,-3,4,-1,2,1,-5,4]
 [-2,1,-2,4, 3,5,6, 1,5]
  */
var maxSubArray = function(nums) {
    let partial = nums[0];
    let answer = partial;

    for (let i=1; i<nums.length; i++) {
        partial = Math.max(partial, 0) + nums[i];
        answer = Math.max(answer, partial)
    }

    return answer;
};

[hyunahOh]

Maximum Product Subarray - https://leetcode.com/problems/maximum-product-subarray/

// 시간 O(n), 공간 O(n)

var maxProduct = function(nums) {
    const partial = [];
    const partialMin = [];

    partial.push(nums[0]);
    partialMin.push(nums[0]);

    for (let i=1; i<nums.length; i++) {
        partial.push(Math.max(...[partial[i-1] * nums[i], partialMin[i-1] * nums[i], nums[i]]));
        partialMin.push(Math.min(...[partial[i-1] * nums[i], partialMin[i-1] * nums[i], nums[i]]));
    }

    return Math.max(...partial, ...partialMin);
};

// 시간 O(n), 공간 O(1)

var maxProduct = function(nums) {
    let partial = nums[0];
    let partialMin = nums[0];
    let answer = partial;
    let answerMin = partialMin;

    for (let i=1; i<nums.length; i++) {
        let _partial = Math.max(...[partial * nums[i], partialMin * nums[i], nums[i]]);
        partialMin = Math.min(...[partial * nums[i], partialMin * nums[i], nums[i]]);
        partial = _partial;

        answer = Math.max(answer, partial);
        answerMin = Math.min(answerMin, partialMin);
    }

    return answer;
};

[hyunahOh]

Find Minimum in Rotated Sorted Array - https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

var findMin = function(nums) {
    let leftPointer = 0;
    let rightPointer = nums.length - 1;

    while(leftPointer < rightPointer) {
        if (nums[leftPointer] < nums[rightPointer]) {
            // 내부 정렬된 상태
            break;
        } else if (leftPointer + 1 === rightPointer) {
            leftPointer = rightPointer;
            break;
        } 

        const centerPointer = Number.parseInt((leftPointer + rightPointer) / 2);
        if (nums[leftPointer] > nums[centerPointer]) {
            // 왼쪽이 내부정렬
            rightPointer = centerPointer;
        } else {
            leftPointer = centerPointer + 1;
        }
    }

    return nums[leftPointer];
};