num
, write a function which returns true
if num is a perfect square else false
.sqrt
./**
* @param {number} num
* @return {boolean}
*/
// 이중 for 문을 이용한 풀이
var isPerfectSquare = function(num) {
let base = 0;
while (num >= base**2) {
if (num === base**2) {
return true;
}
base++;
}
return false;
};
// binary search를 이용한 풀이
var isPerfectSquare = function(num) {
let low = 1;
let high = num;
let mid, square;
while (low <= high) {
mid = Math.floor((low + high)/2);
square = mid * mid;
if (num === square) {
return true;
}
if (num < square) {
high = mid - 1;
}
if (num > square){
low = mid + 1;
}
}
return false;
};
You are given an m x n
binary matrix mat
of 1
's (representing soldiers) and 0
's (representing civilians). The soldiers are positioned in front of the civilians. That is, all the 1
's will appear to the left of all the 0
's in each row.
A row i
is weaker than a row j
if one of the following is true:
i
is less than the number of soldiers in row j
.i < j.
Return the indices of the k
weakest rows in the matrix ordered from weakest to strongest.
Example 1:
mat = [[1,1,0,0,0],[1,1,1,1,0],[1,0,0,0,0], [1,1,0,0,0],[1,1,1,1,1]], k = 3
/**
* @param {number[][]} mat
* @param {number} k
* @return {number[]}
*/
// map, filer, sort를 사용한 풀이
var kWeakestRows = function(mat, k) {
const result = [];
let soldierArray = mat.map((array, index) => {
const soldierCount = array.filter((num) => num === 1).length;
return [soldierCount, index];
});
soldierArray.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
for (let i = 0; i < k; i++) {
result.push(soldierArray[i][1]);
}
return result;
};
Given an integer array nums
, return the length of the longest strictly increasing subsequence.
A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7]
is a subsequence of the array [0,3,1,6,2,2,7]
.
Example 1:
Example 2:
Example 3:
/**
* @param {number[]} nums
* @return {number}
*/
// forEach, findIndex를 사용한 풀이
var lengthOfLIS = function(nums) {
const subsequence = [nums[0]];
let numberIndex;
nums.forEach((number) => {
if (number > subsequence[subsequence.length - 1]) {
subsequence.push(number);
} else {
numberIndex = subsequence.findIndex((value) => value >= number);
subsequence[numberIndex] = number;
}
});
return subsequence.length;
};
// binary search를 사용한 풀이
var lengthOfLIS = function(nums) {
const subsequence = [];
let currNumber, index;
subsequence[0] = nums[0];
if(!nums.length) return 0;
for (let i = 1; i < nums.length; i++) {
currNumber = nums[i];
if (currNumber < subsequence[0]) {
subsequence[0] = nums[i];
} else if (currNumber > subsequence[subsequence.length - 1]) {
subsequence.push(nums[i]);
} else {
index = binarySearch(subsequence, currNumber);
subsequence[index] = currNumber;
}
}
function binarySearch(array, value) {
let start = 0;
let end = array.length - 1;
let middle;
while (start < end) {
middle = Math.floor((start + end)/2);
if (array[middle] >= value) {
end = middle;
} else {
start = middle + 1;
}
}
return end;
}
return subsequence.length;
};
n
, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times
가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.function solution(n, times) {
times.sort((a,b) => a - b);
let minTime = 0;
let maxTime = n * times.at(-1);
let midTime;
while (minTime <= maxTime) {
midTime = Math.floor((minTime + maxTime) / 2);
const count = times.reduce((count, time) => count + Math.floor(midTime/time), 0);
if (count >= n) {
maxTime = midTime - 1;
} else {
minTime = midTime + 1;
}
}
return minTime;
}
Given an array nums
containing n
distinct numbers in the range [0, n]
, return the only number in the range that is missing from the array.
Example 1:
Example 2:
/**
* @param {number[]} nums
* @return {number}
*/
var missingNumber = function(nums) {
nums.sort((a,b) => a - b);
let left = 0;
let right = nums.length;
let middle;
while(left < right) {
middle = Math.floor((left + right)/2);
console.log(middle, nums[middle]);
if (nums[middle] > middle) {
right = middle;
} else {
left = middle + 1;
}
}
return left;
};
An array arr
a mountain if the following properties hold:
arr.length >= 3
i
with 0 < i < arr.length - 1
such that:arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
Given a mountain array arr, return the index i
such that arr[0] < arr[1] < ... < arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
.
You must solve it in O(log(arr.length))
time complexity.
/**
* @param {number[]} arr
* @return {number}
*/
var peakIndexInMountainArray = function(arr) {
let start = 0;
let end = arr.length - 2;
let middle;
while (start <= end) {
middle = Math.floor((start + end)/2);
if (arr[middle] < arr[middle + 1]) {
start = middle + 1;
} else {
end = middle - 1;
}
}
return start;
};
A conveyor belt has packages that must be shipped from one port to another within days
days.
The ith
package on the conveyor belt has a weight of weights[i]
. Each day, we load the ship with packages on the conveyor belt (in the order given by weights
). We may not load more weight than the maximum weight capacity of the ship.
Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within days
days.
days
<= weights.length
<= 5 * 104weights[i]
<= 500/**
* @param {number[]} weights
* @param {number} days
* @return {number}
*/
var shipWithinDays = function(weights, days) {
let minCapacity = Math.max(...weights);
let maxCapacity = weights.reduce((a,b) => a + b, 0);
let midCapacity;
const calculateShipDays = (capacity) => {
let shipDays = 1;
let currentCapacity = capacity;
for (const weight of weights) {
if (weight > currentCapacity) {
currentCapacity = capacity;
shipDays++;
}
currentCapacity -= weight;
}
return shipDays;
};
while (minCapacity <= maxCapacity) {
midCapacity = Math.floor((minCapacity + maxCapacity)/2);
if (calculateShipDays(midCapacity) > days) {
minCapacity = midCapacity + 1;
} else {
maxCapacity = midCapacity - 1;
}
}
return minCapacity;
};