268. Missing Number

Summary

• https://leetcode.com/problems/missing-number/

Main Idea

• sum(1, n) 에서 input array 값을 모두 더한값을 빼주면 빠진 숫자를 알 수 있다. O(1) space and O(N) time
• sum(1, n) 을 수학적으로 구하는 법

1. n x (n + 1) / 2
2. https://adgw.tistory.com/entry/알고리즘-1-n까지-합을-구하는-원리

public class Solution {
  public int missingNumber(int[] nums) {
      int sum = 0;
      for(int num: nums)
          sum += num;
          
      return (nums.length * (nums.length + 1) )/ 2 - sum;
  }
}

• 수학을 모를 때

public class Solution {
  public int missingNumber(int[] nums) {
    int result = 0;
    for (int i = 1; i <= nums.length; i++) {
        result += i-nums[i-1];
    }
    return result;
  }
}

55. Jump Game

Summary

• https://leetcode.com/problems/jump-game/

Main Idea

• 최대 어디까지 갈 수 있는지 max값을 지정해 두는게 중요하다

public static boolean canJump(int[] A) {
    int max = 0; // 갈 수 있는 최대
    for(int i = 0; i < A.length; i++){
        if (i > max) { // 갈 수 있는 최대치로 현재위치에 올 수 없다면
            return false;
        }
        max = Math.max(A[i] + i, max);
    }
    return true;
}