[Mock] Random 4

---

27. Remove Element

Given an array nums and a value val, remove all instances of that value in-place and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means a modification to the input array will be known to the caller as well.

Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy)
int len = removeElement(nums, val);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

My Answer 1: Accepted (Runtime: 28 ms - 90.88% / Memory Usage: 14.2 MB - 75.20%)

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        while val in nums:
            nums.remove(val)
        
        return len(nums)

초간단 풀이..^^
nums 에 포함된 모든 val 들을 없애주고 길이 return

Solution 1: Accepted (Runtime: 24 ms - 98.04% / Memory Usage: 14.1 MB - 91.38%)

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        i = 0
        
        for j in range(len(nums)):
            if nums[j] != val:
                nums[i] = nums[j]
                i += 1
        
        return i

값을 삭제하지 않고 val 값 자리에 다음 값들을 당겨서 넣어줌
마치 삭제된듯이.. 속이기

Solution 2: Accepted (Runtime: 32 ms - 72.12% / Memory Usage: 14.3 MB - 12.63%)

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        i = 0
        n = len(nums)
        
        while i < n:
            if nums[i] == val:
                nums[i] = nums[n-1]
                n -= 1
            else:
                i += 1
        
        return n

포인터 두개 사용
이거도 삭제를 직접 하지 않고 i 자리에 val 이 아닌 값으로 채워주기 -> 정렬과 유사

---

39. Combination Sum

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

My Answer 1: Accepted (Runtime: 116 ms - 20.56% / Memory Usage: 14.2 MB - 76.52%)

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        
        def comb(candidates, arr, target):
            if sum(arr) == target:
                self.result.append(arr)
                return
            
            if sum(arr) > target:
                return
            
            for i in range(len(candidates)):
                comb(candidates[i:], arr+[candidates[i]], target)
        
        self.result = []
        
        comb(candidates, [], target)
        
        return self.result

comb 함수를 만들어서 모든 조합을 찾기
조합의 합이 target 과 같으면 result 에 넣고 크면 성립이 될 수 없으므로 그냥 return

루션이도 비슷한데 나처럼 arr 를 쓰지 않고 target 에서 값을 빼는 식으로 하는 듯