11주차 일요일 1 - LeetCode-Study-Team/solutions GitHub Wiki

1509 Minimum Difference Between Largest and Smallest Value in Three Moves

  • 문제 요약: 배열에서 최대 3개까지 변경해서, 배열 안의 최대값과 최소의 차이가 최소가 되게 만들기. (즉, 3개 지워서, 최소와 최대 차이 최소로 만들기)
Input: [5,3,2,4]
Output: 0 
이유: 아무 값으로 나머지를 바꾼다.

Input: [1,5,0,10,14] // 0 1 5 10 14
Output: 1
이유: 0 or 1로 [5, 10, 14]를 바꾼다 

Input: [6,6,0,1,1,4,6]
Output: 2
이유: 4로 바꾼다. 

Input: [1,5,6,14,15]
Output: 1

풀이

  • 4가지만 고려 링크
    • kill 3 biggest elements
    • kill 2 biggest elements + 1 smallest elements
    • kill 1 biggest elements + 2 smallest elements
    • kill 3 smallest elements
1 1 1    1      1     1
11     1   1111      1 
1     1   1111     1 1
1      1     1    1 1 1   

public int minDifference2(int[] nums) {
    if (nums.length < 5) return 0;
    Arrays.sort(nums);
    int min = Integer.MAX_VALUE;

    for (int i = 4; i > 0; --i) {
        min = Math.min(min, nums[nums.length - i] - nums[4 - i]);
    }

    return min;
}

1110 Delete Nodes And Return Forest

  • 구글 페이스북 아마존에 여러번 나온 문제

솔루션 1

private Set<Integer> to_delete_set;
private List<TreeNode> res;

public List<TreeNode> delNodes1(TreeNode root, int[] to_delete) {
    to_delete_set = new HashSet<>();
    res = new ArrayList<>();
    for (int i : to_delete)
        to_delete_set.add(i);
    helper1(root, true);
    return res;
}

private TreeNode helper1(TreeNode node, boolean is_root) {
    if (node == null) return null;
    boolean deleted = to_delete_set.contains(node.val); // flag 사용
    if (is_root && !deleted) res.add(node);
    node.left = helper1(node.left, deleted);
    node.right = helper1(node.right, deleted);
    return deleted ? null : node;
}

솔루션 2

// 솔루션 2: flag 사용 안한 코드
// 이유: not necessary, root 노드만 사용함 (확인 필요)
public List<TreeNode> delNodes2(TreeNode root, int[] to_delete) {
    Set<Integer> set = new HashSet<>();
    for (int i : to_delete) set.add(i);
    List<TreeNode> res = new ArrayList<>();
    if (!set.contains(root.val)) res.add(root);
    dfs2(root, set, res);
    return res;
}

private TreeNode dfs2(TreeNode node, Set<Integer> set, List<TreeNode> res) {
    if (node == null) return null;
    node.left = dfs2(node.left, set, res);
    node.right = dfs2(node.right, set, res);
    if (set.contains(node.val)) {
        if (node.left != null) res.add(node.left);
        if (node.right != null) res.add(node.right);
        return null;
    }
    return node;
}
⚠️ **GitHub.com Fallback** ⚠️