Algorithm/LeetCode12

• 

  [448]Find All Numbers Disappeared in an Array leetcode.com/problems/find-all-numbers-disappeared-in-an-array/ 다음 출처를 참고하여 해결하였습니다. ergate.tistory.com/entry/LeetCode-448-Find-All-Numbers-Disappeared-in-an-Array 중요한 성질 두 가지를 기억하면 됩니다. N: 배열의 길이 1. 배열 내의 값이 [0,N-1] 또는 [1,N] 범위 내로 주어진다면 이를 인덱스로 활용할 가능성이 높습니다. 2. 중복유무와 관계없이 한 번이라도 등장한 값과 등장하지 않은 값의 차이는 인덱스상에 표시할 수 있습니다. 위 1, 2번 성질을 활용하여 한 번이라도 등장한 숫자는 number는 arr[number-1] 숫자를 음수로 바꿔줍니다. 중복 방문하지.. Algorithm/LeetCode 2020. 9. 18.

• 

  [169]Majority Element leetcode.com/problems/majority-element/ 숫자가 나오는 갯수를 HashMap으로 관리한 후 절반이상 등장한 숫자를 리턴해주면 됩니다. HashMap map = new HashMap(); public int majorityElement(int[] nums) { for (int i = 0; i (nu.. Algorithm/LeetCode 2020. 9. 18.

• 

  [136]SingleNumber leetcode.com/problems/single-number/ 두 가지 이유로 XOR을 통해 해결할 수 있습니다. 1. XOR은 결합법칙과, 교환법칙이 성립합니다. 2. 자기 자신과의 XOR 결과는 0 입니다. 10^10 = 0, A^A = 0 주어진 리스트의 1개를 제외하고는 모두 2개라는 성질을 이용하면 ABCDEDCBA 위 예시 숫자를 교환법칙을 사용해서 두 쌍씩 괄호로 묶어줍니다. (AA)(BB)(CC)(DD)E 여기에 XOR을 하게 되면 결국 0 ^ E 만 남게 되어 하나짜리 E만 남는 형태입니다. public int singleNumber(int[] nums) { int xorResult = 0; for (int i = 0; i < nums.length; ++i) { xorResult = .. Algorithm/LeetCode 2020. 9. 18.

• 

  [009]Detect Capital 문제: https://leetcode.com/explore/challenge/card/august-leetcoding-challenge/549/week-1-august-1st-august-7th/3409/ 주어진 문자열이 조건에 맞는 문자열인지 확인하는 문제입니다. 주어진 조건은 3가지 입니다. 1. 모두 대문자 2. 모두 소문자 3. 첫 글자만 대문자, 나머지 소문자 class Solution { public boolean detectCapitalUse(String word) { String lowerCase = word.toUpperCase(); String upperCase = word.toLowerCase(); if (word.isEmpty()) return false; else if (word... Algorithm/LeetCode 2020. 8. 8.

• 

  [008]Find All Duplicates in an Array 문제: https://leetcode.com/explore/challenge/card/august-leetcoding-challenge/549/week-1-august-1st-august-7th/3414/ 주어지는 nums 배열을 hashMap처럼 사용하면 됩니다. 아래 두 가지 조건 때문에 가능한데요. 1. 주어지는 모든 수가 배열의 인덱스 번호 이하의 숫자. 2. 양수라는 조건. Single Number와 Duplicate Number의 차이점을 방문 표시 여부로 생각하면 됩니다. 특정한 nums[i] 값을 visited[] 배열에서의 index로 보게 되면, (int index = nums[i]) 1. nums[i] 값이 나오면 해당 인덱스 숫자 nums[nums[i]] (== nums[index].. Algorithm/LeetCode 2020. 8. 7.

• 

  [007]Add and Search Word - Data structure design 문제: https://leetcode.com/explore/challenge/card/august-leetcoding-challenge/549/week-1-august-1st-august-7th/3413/ 문자열 검색 문제. 와일드 카드 식별자가 존재해도 문자열 & 검색문제이므로 트라이로 해결이 가능합니다. class WordDictionary { public: static const int ALPHA_SIZE = 128; typedef struct Trie { Trie* next[ALPHA_SIZE]; bool isFinished; Trie() { fill(next, next + ALPHA_SIZE, nullptr); isFinished = false; } void insert(const char *k.. Algorithm/LeetCode 2020. 8. 6.