목록전체 글 (179)
有希
주어진 string s가 abc라면 string t는 s의 순서가 무작위로 뒤바뀐 cab 같은 문자열인지 확인하는 문제. 아무튼 string을 이루는 알파벳들의 등장 횟수가 같은지 비교하면 된다. 문제에서는 follow up에 unicode도 되는지 해보라고 했으므로 map에 넣을때 키값을 wchar_t로 해주면 된다. class Solution { public: bool isAnagram(string s, string t) { unordered_map ms; if(s.size()!=t.size()) return false; for(int i=0; i
주어진 문제는 arg node를 지우는 것인데, 그러려면 이전의 next를 나의 next로 연결시켜야한다. 하지만 이전 녀석에는 접근 불가능 하다. 이용할 수 있는 방법은 내가 다음 녀석이 되면 된다. 다음 녀석의 값들을 복사하고 다음 녀석을 그냥 스킵시켜 버리면 된다. 여담으로, delete node->next 했는데 double free error가 발생한걸 보니 shared_ptr같은걸 사용한거 같다. /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: voi..
10^5 개 이니까 간단히 배열을 하나 만들어서 등장횟수를 세도 된다. 근데 그러면 메모리 낭비가 심하니 set을 써서 이전에 등장했는지 여부만 체크하면 된다. class Solution { public: bool containsDuplicate(vector& nums) { unordered_set precedent; for(auto num : nums) { if(precedent.find(num)==precedent.end()) { precedent.insert(num); } else { return true; } } return false; } };
중요한 점은 제곱 작업을 하다가 이전에 등장한 녀석이 나오면 무조건 끝이다. 어떻게 되는 이전에 등장한 녀석이 나왔다는 것은 순환이라는 말이기 때문에 끝이다. 또는 1이거나 음수가 나와도 끝이다. 아무튼, 더 이상 제곱하는 의마가 없다면 빠져나와서 1이랑 같은지 비교하고 out하면 된다. class Solution { public: bool isHappy(int n) { set precedents; while(n>1 && precedents.find(n) == precedents.end()) { precedents.insert(n); n = GetSquares(n); } return n==1; } int GetSquares(int n) { int sum=0; while(n>0) { sum += (n%10..
1이 몇 번 등장하는지 세면 된다. STL에서 bit 뭐시기를 이용해서 to_string한 다음 for문 돌며 세도 되지만 오버헤드가 심하다. 그냥 왼쪽으로 밀면서 1이랑 & 연산해서 더해주면 된다. class Solution { public: int hammingWeight(uint32_t n) { int ret =0 ; for(int i=0; i>i) & 1; } return ret; } };
1101을 예로 들면, 가장 오른쪽 1은 0번 오른쪽으로 밀고 1과 and 연산하면 0001이 되고 이를 31번 왼쪽으로 밀고 ans에 or연산하면 ans 는 32번째, 가장 왼쪽만 1이 되고 나머지는 0이 된다. 그 다음, 0도 마찬가지로 해주면 2번째 왼쪽이 0이 된다. 이렇게 한 글자씩 연산한다. class Solution { public: uint32_t reverseBits(uint32_t n) { int ans = 0; for(int i = 0 ; i >i)&1; ans = ans|(mask
10진법과 같다. 다만 자리수가 10의 제곱으로 증가하는 것이 아닌 26의 제곱으로 증가하는 것이다. 예시로, 32라는 숫자는 CB와 같다. 32는 10^1 * 3 + 10^0 * 2 로, CB는 26^1 * 3 + 26^0 * 2로 나타낼 수 있다. 마찬가지로 문제에서 주어진 예시인 ZY는 26^1 * 26 + 25 = 701로 맞아떨어짐을 볼 수 있다. class Solution { public: int titleToNumber(string columnTitle) { int ascValue = 0; if(columnTitle.length() == 1) { return (int(columnTitle[0])-64); } if(columnTitle.length() > 1) { for(int i=column..
342라는 숫자가 있으면 1의 자리부터 해서 노드가 2->4->3 으로 연결되어 있다. 주어진 두 개의 노드를 1의 자리부터 편안하게 더해가면 된다. leading zero도 없다고 하니 신경쓸 필요 없이 더하면 된다. 다만, 문제의 함정은 두 리스트의 길이가 항상 같지는 않다는 것. 그러면 2가지 케이스로 나뉜다. 1. 두 리스트의 길이가 같을때 한 쪽의 next 포인터가 nullptr이 아닐때까지 계속 이동하면서 더하면 된다. 2. 두 리스트의 길이가 다를때 1번의 방법을 이용한 후에 남은 쪽을 쭉 붙여주면 된다. 먼저 while문으로 두 녀석의 합을 구해서 쭉 붙인다. up은 이전 자리수의 합이 10이 넘을 경우 true가 된다. 처음에는 false로 초기화 ListNode* addTwoNumber..
굳이 새거 만들어서 하려면 머리가 아프다. 주어진 2개 중 하나를 골라서 다른 녀석을 합쳐주면 편하다. 하지만, 추후 공간 절약을 위해 두 녀석을 delete 해버리고 새로운 녀석 하나만 가지고 있는 것이 좋다. 그러면 굳이 새로 코드를 짤 필요 없이 root2에서 떼올때 root2->left나 right를 nullptr로 밀어주면 될거같다. class Solution { public: TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) { if(root1==nullptr) return root2; if(root2==nullptr) return root1; //양쪽 다 nullptr이 아니다 //진입해서 만들자 merge(root1, root2); retur..
문제 설명의 예시를 잘 읽어 보아야 한다. 그림만 봤다가는 최대 길이는 처음 root에서 좌우로 쪼개져서 최대 길이 찾은다음 더해서 반환하면 되겠거니 해버린다. 근데 왼쪽은 노드가 1개만 있고 오른쪽은 완전 이진트리로 깊이가 10이라면, 우리가 반환하는 값은 11인데 실제 정답은 19인가 20? 아무튼 훨씬 큰 값이다. 이를 염두해두고 풀어야 한다. class Solution { public: int maxi = 0; int diameterOfBinaryTree(TreeNode* root) { int temp = dfsHeight(root); return maxi; } int dfsHeight(TreeNode* root){ if(root == NULL) return 0; int lh = dfsHeight..