제목 링크 난이도 풀이일 코드
[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

+ Recent posts

티스토리툴바