'leetcode'에 해당되는 글 20건
- 2020.08.20 :: 1289. Minimum Falling Path Sum II
- 2020.08.20 :: 1219. Path with Maximum Gold
- 2020.08.20 :: 931. Minimum Falling Path Sum
- 2020.08.20 :: 784. Letter Case Permutation
- 2020.08.20 :: 494. Target Sum
- 2020.08.20 :: 451. Sort Characters By Frequency
- 2020.08.20 :: 416. Partition Equal Subset Sum
- 2020.08.20 :: 347. Top K Frequent Elements
- 2020.08.20 :: 338. Counting Bits
- 2020.08.20 :: 303. Range Sum Query - Immutable
https://leetcode.com/problems/minimum-falling-path-sum-ii/
Minimum Falling Path Sum II - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
/**
* @param {number[][]} arr
* @return {number}
*/
var minFallingPathSum = function(arr) {
// ------------------------------
// DP를 구하기 위한 어레이 설정
// ------------------------------
const dp = arr.slice()
const rowSize = arr[0].length;
// ------------------------------
// Falling path 검색
// ------------------------------
var res = 65535;
for( let i=1; i<arr.length; ++i )
{
for( let j=0; j<rowSize; ++j )
{
let min = 65535;
for( let k=0; k<rowSize; ++k )
{
if( j == k ) continue;
min = min < arr[i-1][k] ? min : arr[i-1][k];
}
dp[i][j] = min + arr[i][j];
if( i == rowSize-1 )
res = res<dp[i][j] ? res : dp[i][j];
}
}
return res;
};
https://leetcode.com/problems/path-with-maximum-gold/
Path with Maximum Gold - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
/**
* @param {number[][]} grid
* @return {number}
*/
var getMaximumGold = function(grid) {
var maximum = 0;
var grid2 = [];
var visited=[];
var i=0;
var direction_y = [ -1,1,0,0 ];
var direction_x = [ 0,0,-1,1 ];
for( i=0; i<17; ++i )
{
grid2[i] = [];
visited[i] = [];
for( var j=0; j<17; ++j )
{
grid2[i][j] = 0;
visited[i][j]=0;
}
}
for( i=0; i<grid.length; ++i )
{
for( var j=0; j<grid[0].length; ++j )
{
grid2[i+1][j+1] = grid[i][j];
}
}
var find = function( p_y, p_x, p_visited, p_sum )
{
if( grid2[p_y][p_x] != 0 )
{
if( p_sum + grid2[p_y][p_x] > maximum )
maximum = p_sum + grid2[p_y][p_x];
for( var i=0; i<4; ++i )
{
const y = direction_y[i] + p_y;
const x = direction_x[i] + p_x;
if( y>0 && x>0 && y-1<visited.length && x-1<visited[0].length )
{
if( p_visited[y-1][x-1] == 0 )
{
p_visited[y-1][x-1] = 1;
find( y, x, p_visited, p_sum+grid2[p_y][p_x] )
p_visited[y-1][x-1] = 0;
}
}
}
}
}
for( var i=0; i<grid.length; ++i )
{
for( var j=0; j<grid[0].length; ++j )
{
if( grid2[i+1][j+1] != 0 )
{
visited[i][j]=1;
find(i+1,j+1,visited,0);
visited[i][j]=0;
}
}
}
return maximum;
};
https://leetcode.com/problems/minimum-falling-path-sum/
Minimum Falling Path Sum - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
/**
* @param {number[][]} A
* @return {number}
*/
var minFallingPathSum = function(A) {
// ------------------------------
// DP를 구하기 위한 어레이 설정
// ------------------------------
const rowsize = A.length +2;
const dp= Array( rowsize );
dp[0] = Array( rowsize ).fill(101);
for( let i=0; i<A.length; ++i )
{
dp[i+1] = Array( rowsize ).fill(101);
for( let j=0; j<A[0].length; ++j )
dp[i+1][j+1] = A[i][j];
}
// ------------------------------
// 끝
// ------------------------------
// ------------------------------
// Falling path 검색
// ------------------------------
for( let i=1; i<A.length; ++i )
{
for( let j=0; j<A[0].length; ++j )
dp[i+1][j+1] = Math.min( dp[i][j], dp[i][j+1], dp[i][j+2]) + A[i][j];
}
// ------------------------------
var res = 101;
for( let j=0; j<dp[0].length; ++j )
res = Math.min( res, dp[A.length][j] )
return res;
};
https://leetcode.com/problems/letter-case-permutation/
Letter Case Permutation - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
/**
* @param {string} S
* @return {string[]}
*/
var letterCasePermutation = function(S) {
var result = [];
var length = S.length;
var find = function( p_idx, p_str )
{
if( p_idx == length )
return result.push( p_str );
else
{
var letter = S.charAt(p_idx);
if( ( letter.toLowerCase() === letter.toUpperCase() ) == false )
{
find( p_idx+1, p_str + letter.toLowerCase() );
find( p_idx+1, p_str + letter.toUpperCase() );
}
else
find( p_idx+1, p_str + letter );
}
}
find( 0, '' );
return result;
};
https://leetcode.com/problems/target-sum/
Target Sum - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
/**
* @param {number[]} nums
* @param {number} S
* @return {number}
*/
var map = [];
var findTargetSumWays = function(nums, S) {
for( var i=0; i<20; ++i)
map[i] = [];
var find = function( p_idx, p_sum )
{
if( p_idx == nums.length )
{
if( p_sum == S) return 1;
return 0;
}
var res =0;
if( typeof(map[p_idx][p_sum]) != 'undefined' )
return map[p_idx][p_sum];
else
{
map[p_idx][p_sum] =find( p_idx+1, p_sum-nums[p_idx] ) + find( p_idx+1, p_sum+nums[p_idx] );
return map[p_idx][p_sum];
}
}
return find( 0, 0 );
};
https://leetcode.com/problems/sort-characters-by-frequency/
Sort Characters By Frequency - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
/**
* @param {string} s
* @return {string}
*/
var frequencySort = function(s) {
const hash = {};
for( var i=0; i<s.length; ++i )
hash[ s.charAt(i) ] = 0;
for( var i=0; i<s.length; ++i )
++hash[ s.charAt(i) ];
var res = s.split('').sort( (a,b)=>{
return hash[b]-hash[a] !=0 ? hash[b]-hash[a] : b.charCodeAt(0) - a.charCodeAt(0);
}).join('');
return res;
};
https://leetcode.com/problems/partition-equal-subset-sum/
Partition Equal Subset Sum - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
/**
* @param {number[]} nums
* @return {boolean}
*/
var canPartition = function(nums) {
const hash = Array(7000).fill(false)
var sum = 0;
for( var i=0 ; i<nums.length; ++i )
sum += nums[i];
sum/=2;
const find = function( p_idx, p_sum )
{
if( p_sum > sum ) return false;
if( hash[p_sum] ) return false;
if( !(p_sum-sum) ) return true;
if( p_idx < nums.length )
return find( p_idx+1, p_sum+nums[p_idx] ) || find( p_idx+1, p_sum );
else
{
hash[p_sum] = true;
return false;
}
}
return find(0,0)
};
https://leetcode.com/problems/top-k-frequent-elements/
Top K Frequent Elements - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var topKFrequent = function(nums, k) {
const res = {}, hash={};
for( var i=0; i<nums.length; ++i )
hash[ nums[i] ] = 0;
var keys = Object.keys(hash);
for( var i=0; i<nums.length; ++i )
++hash[ nums[i] ];
keys.sort( (b,a)=>{ return hash[a]-hash[b]; } );
return keys.slice(0,k);
};
https://leetcode.com/problems/counting-bits/
Counting Bits - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
/**
* @param {number} num
* @return {number[]}
*/
var countBits = function(num) {
const result = [];
for( let i=0; i<=num; ++i )
{
if( i<2 )
result.push(i);
else
result.push( result[Math.floor(i/2)] + i%2 );
}
return result;
};
https://leetcode.com/problems/range-sum-query-immutable/
Range Sum Query - Immutable - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
JS로 간단하게 연습삼아 짜본 코드를 생각나는 대로 올려보자.
/**
* @param {number[]} nums
*/
var NumArray = function(nums) {
this.nums = nums;
this.dp = [];
this.dp[0]= this.nums[0];
for( var i=1; i<nums.length; ++i )
this.dp[i]=(this.dp[i-1]+nums[i]);
};
/**
* @param {number} i
* @param {number} j
* @return {number}
*/
NumArray.prototype.sumRange = function(i, j) {
return this.nums[i]-this.dp[i] + this.dp[j];
};
/**
* Your NumArray object will be instantiated and called as such:
* var obj = new NumArray(nums)
* var param_1 = obj.sumRange(i,j)
*/