Bit Manipulation
-
[LeetCode] Single Number알고리즘 2019. 12. 6. 16:14
문제 Given a non-empty array of integers, every element appears twice except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? Example 1: Input: [2,2,1] Output: 1 Example 2: Input: [4,1,2,1,2] Output: 4 Approach xor 비트연산으로 푼다. Code https://github.com/chi3236/algorithm/blob/master/LeetCode_SingleNumber.c c..
-
[LeetCode] Subsets알고리즘 2019. 11. 18. 17:30
문제 Given a set of distinct integers, nums, return all possible subsets (the power set). Note: The solution set must not contain duplicate subsets. Example: Input: nums = [1,2,3] Output: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ] Approach 전형적인 Bactracking문제로 n개의 요소로 된 집합에서 0개짜리 부분집합 ~ n개짜리 부분집합을 DFS등을 써서 backtracking으로 찾아가면 된다. Discussion을 보니까 bit manipulation으로 푸는 방법도 있던데 이건 좀 신박 Code h..