walkingtospace

https://oj.leetcode.com/problems/balanced-binary-tree/

/*
solution: modified preorder (O(n))
매 순회마다 left, right 의 depth를 비교해서 >1 이면 return false 
more than 1 이라고 했으므로 인터뷰어와   
    1   와 같은 예제도 balanced 인지 사전 논의 필요
    / 
   2

walkingtospace

https://oj.leetcode.com/problems/remove-element/

/*
이런 단순한 문제 일수록 문제의 의도를 정확하게 파악하기 위해 인터뷰어와 코딩 전 충분한 사전 토의가 필요.
단순히 주어진 element를 모두 지우고 새로운 length를 리턴하라는 것인지, remove후 정렬절차가 어떻게 될것인지 질문하기.
"The order of elements can be changed. It doesn't matter what you leave beyond the new length" -> element를 remove하고 left shift 해야함을 암시.

조심할 점: 주어진 n으로 보통 for i=[0,n) loop를 돌릴텐데, elem를 remove 할때마다 n이 점점 짧아지므로 loop가 자칫 의도대로 동작하지 않을 수 있음.

test case:

walkingtospace

https://oj.leetcode.com/problems/merge-two-sorted-lists/

/*
단순히 two runner를 이용해서 merge sort의 merge와 마찬가지로 O(n)에 sorted list를 merge 하는 알고리즘
한번에 accepted 했어야했는데.. linked list pointing 헷갈려서 2번 실패. 아직 pointer 부분 부족한듯
*/

/**
 * Definition for singly-linked list.
 * struct ListNode {

walkingtospace

https://oj.leetcode.com/problems/single-number-ii/

/*
사고의 전환이 필요. 일종의 트릭인데, array를 element 단위보다 더 작은 bit level 에서 볼 수 있고
bit level operation을 할 수 있느냐를 보는 문제.
"Given an array of integers, every element appears twice except for one. Find that single one." 와도 거의 같은 문제

ex 정수 12 = 1100 이고, A={12,12,12,1} == {1100,1100,1100,0001} 이면 맨 오른쪽 bit의 경우 1이 3회 반복되므로 이를 mod 3할 경우 0이 된다. 마찬가지로 두번째비트의 경우도 0, 3번째비트의 경우 모두 0이므로 0 네번째 비트의 경우 single one인 1만 1비트를 가지고 있으므로 mod 3의 경우 1이된다. 즉 모든 수의 비트를 count하여 mod3을 하면 3회 나타나는 수의 경우 모두 0이 되고, 1회 나타나는 수의 경우 그자신의 값으로 세팅된다. 이를 이용하면 어떤 정수가 n회씩 나타나는 정수 배열중 k회 나타나는 정수 1개의 값을 리턴하라. 라는 문제로 일반화 할 수 있다.

time complexity : O(kn) (k는 32 bit or 64 bit)

walkingtospace

https://oj.leetcode.com/problems/remove-duplicates-from-sorted-list/

/*
반드시 인접해있는 두 노드만 duplicated 되어있는지? -> YES
O(n) solution : 순회하면서 duplicated 노드 만나면 삭제(건너뛰고)연결
*/

/**
 * Definition for singly-linked list.
 * struct ListNode {

walkingtospace

https://oj.leetcode.com/problems/binary-tree-preorder-traversal/

/*
preorder를 loop로 구현하기 위해서 stack을 이용하여 실제 recursive call과 함수 콜스택의 동작을 모방하여 그대로 적용하면 될것.
loop로 구현시, 실제로 return 시 스택에서 unwinding(pop)을 하여 이전 제어 상태 다음으로 제어가 넘어가야되는 부분을 구현하는 것이 어려운데, 간단히 flag 를 하나두어 unwinding 중인지 아닌지를 구분하도록 구현하면 간단.
        
*/

/**
 * Definition for binary tree

walkingtospace

https://oj.leetcode.com/problems/maximum-depth-of-binary-tree/

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };

walkingtospace

https://oj.leetcode.com/problems/add-two-numbers/

/*
생각해야할 케이스 : 두 number의 길이가 다를 경우, carry 처리
발생한 Errors: 1)list pointer 처리 미숙 2)while loop 종료 후 carry ==1 일때 처리 빠뜨림 3)자리수 다를때 in loop에서 처리 미숙 

line 43: num = (num) % 10; 을 (num+carry)로 해둬서 carry를 두번 더하는 실수를 범했는데
이를 못찾아서 1시간 소비... 자책으로 끝낼수도있으나, 사실 근본 원인은 알고보면 의사코드를 제대로 정리하지 않고
코드를 컴파일러로 디버깅해가며 이라인 저라인 고쳐갔기 때문에 전체 code flow를 머리속에 제대로 정립하지 못했기 때문.

walkingtospace

https://oj.leetcode.com/problems/search-in-rotated-sorted-array/

/*
    binary search를 응용하여 해결 가능.
    
    test case [4,5,6,7,8,1,2,3] , 8
              [7,8,1,2,3,4,5,6] , 8
        
    suedo code:    
    if pivot == target return pivot                     

walkingtospace

https://oj.leetcode.com/problems/combinations/

/*
시간/공간 복잡도 : O(nCk) nCk = (n!/k!(n-k)!)? 시간 복잡도 계산이 은근히 복잡하다.
n회 루프 중 현재 원소의 갯수 n이 < k 일때까지 계속해서 재귀호출을 하므로..으

순열/조합 을 한번에 짜는게 의외로 잘 안된다. 이번에도 대여섯번 컴파일러에 의존해서 버그 수정 후 accepted. 연습이 필요할 듯
*/

class Solution {