제목 링크 난이도 풀이일 코드
[011] 274. H-Index LINK Medium 2024.04.21 class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int[] bucket = new int[n+1];
        for (int i = 0; i < n; i++) {
            int c = citations[i];
            if ( c>= n) {
                bucket[n]++;
            } else {
                bucket[c]++;
            }
        }
        int cnt = 0;
        for (int i = n; i >= 0; i--) {
            cnt += bucket[i];
            if (cnt >= i) {
                return i;
            }
        }
        return 0;
    }
}
[022] 380. Insert Delete GetRandom O(1) LINK Easy 2024.04.21 class RandomizedSet {

    Set<Integer> randomizedSet;
    

    public RandomizedSet() {
        if (randomizedSet == null) {
            randomizedSet = new HashSet();
        }
    }
    
    public boolean insert(int val) {
        if (randomizedSet.contains(val)) {
            return false;
        } else {
            randomizedSet.add(val);
            return true;
        }    
    }
    
    public boolean remove(int val) {
        if (randomizedSet.contains(val)) {
            randomizedSet.remove(val);
            return true;
        } else {
            return false;
        }   
    }
    
    public int getRandom() {
        Random random = new Random();
        int n = random.nextInt(randomizedSet.size());
        Object[] intArray = randomizedSet.toArray();
        return (int)intArray[n];
    }
}
[023] 238. Product of Array Except Self LINK Medium 2024.05.11 class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] left = new int[n];
        int[] right = new int[n];
        int[] answer = new int[n];
        left[0] = 1;
        for (int i = 1; i < n; i++) {
            left[i] = left[i-1] * nums[i-1];
        }
        right[n-1] = 1;
        for (int j = n-2; j >= 0; j--) {
            right[j] = right[j+1] * nums[j+1];
        }
        for (int i = 0; i < n; i++) {
            answer[i] = left[i] * right[i];
        }
        return answer; 
    }
}
         
         
         
         
         
저작자표시 (새창열림)

'코딩테스트 > Leetcode' 카테고리의 다른 글

Leetcode 문제풀이 001 - 010  (0) 2024.04.14
Leetcode 용어  (0) 2024.04.14
제목 링크 난이도 풀이일 코드
[001] 88. Merge Sorted Array LINK Easy 2024.03.09 class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        for (int i = m, j = 0; i < m+n; i++, j++) {
            nums1[i] = nums2[j];
        }
        Arrays.sort(nums1);
    }
}
[002] 27. Remove Element LINK E 2024.03.09 class Solution {
    public int removeElement(int[] nums, int val) {
        int head = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val) {
                nums[head++] = nums[i];
            }
        }
        return head;
    }
}
[003] 26. Remove Duplicates from Sorted Array LINK   2024.04.14 class Solution {
    public int removeDuplicates(int[] nums) {
        int j = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i-1] != nums[i]) {
                nums[j++] = nums[i];
            }
        }
        return j;    
    }
}
[004] 80. Remove Duplicates from Sorted Array II LINK M 2024.04.14 class Solution {
    public int removeDuplicates(int[] nums) {
        int j = 1;
        for (int i = 1; i < nums.length; i++) {
            if (j == 1 || nums[j-2] != nums[i]) {
                nums[j++] = nums[i];
            }
        }
        return j;
    }
}
[005] 169. Majority Element LINK E 2024.04.15 class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length /2];
    }
}
[006] 189. Rotate Array LINK M 2024.04.15 class Solution {
    public void rotate(int[] nums, int k) {
        int[] result = new int[nums.length];
        if (nums.length < k) {
            k = k % nums.length;
        }
        for (int i = 0; i < nums.length; i++) {
            if (i+k < nums.length) {
                result[i+k] = nums[i];
            } else {
                result[i+k-nums.length] = nums[i];
            }
        }
        for (int i = 0; i < result.length; i++) {
            nums[i] = result[i];
        }
    }
}
[007] 121. Best Time to Buy and Sell Stock LINK E 2024.04.15 class Solution {
    public int maxProfit(int[] prices) {
        int buy = prices[0];
        int profit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (buy > prices[i]) {
                buy = prices[i];
            } else if (prices[i] - buy > profit) {
                profit = prices[i] - buy;
            }   
        }
        return profit;
    }
}

NO : O(N^2) : stupid
class Solution {
    public int maxProfit(int[] prices) {
        int maxprofit = 0;
        for (int i = 0 ; i < prices.length; i++) {
            if (prices[i] < prices[j]) {
                for (int j = i+1; j < prices.length; j++) {
                    if (prices[i] < prices[j]) {
                        int current_profit = prices[j] - prices[i];
                        if (maxprofit < current_profit) {
                            maxprofit = current_profit;
                        }
                    }     
                }
            }
        }
        if (maxprofit > 0) {
            return maxprofit;
        } else {
            return 0;
        }
    }
}
[008] 122. Best Time to Buy and Sell Stock II LINK M 2024.04.16 class Solution {
    public int maxProfit(int[] prices) {
        boolean hasStock = false;
        int buy = 0;
        int profit = 0;
        for (int i = 0; i < prices.length; i++) {
            if (i+1 < prices.length && prices[i] < prices[i+1] && hasStock == false) {
                // buy
                buy = prices[i];
                hasStock = true;
            }
            if (i+1 < prices.length && prices[i] > prices[i+1] && hasStock == true) {
                // sell;
                profit += (prices[i] - buy);
                hasStock = false;
            }
            if (i+1 == prices.length && hasStock == true) {
                // sell;
                profit += (prices[i] - buy);
                hasStock = false;
            }
        }
        return profit;        
    }
}

// better
class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;
        for(int i=1;i<prices.length;i++) {
            if(prices[i] > prices[i-1]) {
                profit += prices[i] - prices[i-1];
            }
        }
        return profit;
    }
}
[009] 55. Jump Game LINK M 2024.04.16 // wrong
class Solution {
    public static boolean canJump(int[] nums) {
        int reach = nums[0];
        for (int i = 0; i < nums.length;i++) {
            if (reach == nums.length-1) {
                return true;
            } else if (reach > nums.length-1) {
                return false;
            }
            reach = reach + nums[i];
            System.out.println(String.format("nums[i]=%s", i));
        }
        return false;
    }
}

// better
class Solution {
    public boolean canJump(int[] nums) {
        int reach = 0;
        for (int i = 0 ; i < nums.length; i++) {
            if (i > reach) {
                return false;
            }
            reach = Math.max(reach, i+nums[i]);
        }
        return true;
    }
}
[010] 45. Jump Game II LINK M 2024.04.16 class Solution {
    public int jump(int[] nums) {
        int jumps = 0, curEnd = 0, curFarthest = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            curFarthest = Math.max(curFarthest, i + nums[i]);
            if (i == curEnd) {
                jumps++;
                curEnd = curFarthest;
            }
        }
        return jumps;
    }
}

https://bcp0109.tistory.com/280
저작자표시 (새창열림)

'코딩테스트 > Leetcode' 카테고리의 다른 글

Leetcode 문제풀이 011 - 020  (0) 2024.04.21
Leetcode 용어  (0) 2024.04.14

non-decreasing order :  비내림차순

같은 수에 대해서는 알아서 처리해도 별다른 문제가 발생하지 않을 것

오름차순으로 정렬 : 같은 수가 있나요? 있다면 어떻게 처리해야하나요? 

비내림차순으로 정렬 : 리스트에 같은 수들이 있을수도 있음

strinctly increasing : 오름차순

같은 수가 있으면 오름 차순으로 보기 어려움.

그래서 비내림차순은 같은 수가 있어도 됨.

오름차순 정렬을 하라고 하면 애초에 strictly increasing

 

in-place : 현재 변수에서 바로 변경, 실시간으로, 바로 변경 이런 의미

in-place : 다른데 저장하지 말고, 해당 변수 바로 수정해야한다는 의미

 

relative order : 

A sorting method is stable if it preserves the relative order of equal keys in the array.

정렬 후에도 같은 키들의 상대적인 순서가 정렬 이전과 동일하게 유지되는 정렬 방법을 안정 정렬이라고 부른다.

 

The relative order of the elements should be kept the same

같은 것에 대해서 정렬을 했을 때 원래의 순서를 유지해야한다는 의미로

이 1980, 강, 1970, 강 1976 을 이름으로 정렬했을때  

강, 1970, 강 1976, 이 1980 이렇게 되면 순서 유지이고

강, 1976, 강 1970, 이 1980 이렇게 되면 순서 유지가 안된 것

비내림차순 : 오름차순인데, 같은 값이 있을 수 있다는 의미

 

remove some duplicates in-place such that each unique element appears at most twice

A such that B : B 한 범위내에서 A를 해라

각 고유 요소가 최대 두 번만 나타나는 범위내에서 일부 중복을 제자리에서 제거해라

 

the majority element

대부분의 요소를 차지하는 요소

The majority element is the element that appears more than ⌊n / 2⌋ times

 

rotate the array to the right by k steps

reverse algorithm

reverse[0, n]

reverse[0, k-1]

reverse[k, n]

 

at most one

많아야 하나

저작자표시 (새창열림)

'코딩테스트 > Leetcode' 카테고리의 다른 글

Leetcode 문제풀이 011 - 020  (0) 2024.04.21
Leetcode 문제풀이 001 - 010  (0) 2024.04.14

+ Recent posts

티스토리툴바