walkingtospace

https://oj.leetcode.com/problems/sort-colors/

/*
O(n) 이자 multi pass(2회 순회)로 푸는 알고리즘은 금방 떠올릴 수 있음. 
2회 순회(1회: 2는 무조건 맨 마지막으로 swap, 2회: 1은 무조건 마지막 2의 앞으로 swap. 0은 자동으로 맨앞에 위치) 

사전질문: 0,1,2가 최소한 1번씩은 존재하는가? no could be like [0,0,0,0,0,0]
목표 : onepass, constant space 
결과 : 1시간 동안 고민한 끝에, swap 솔루션에 거의 근접했지만 swap 후 처리를 제대로 못해 좌절(if the swaped element is 2 or 1, how handle this?)
0은 앞에, 2는 맨뒤에 정렬하고 0과 2를 가리키는 포인터를 두어 불변식 A[0..i-1]은 0또는 1만 존재 && A[i+1...n-1]은 반드시 2만 존재함을 매 루프마다 

walkingtospace

https://oj.leetcode.com/problems/substring-with-concatenation-of-all-words/

//hint : no order
//the same length

/*
extra memory? Yes
L includes unique strings only? No
풀이 : L로 dictionary를 만들고 S를 처음부터 순회하면서 dictionary에 있는 단어인지를 체크해나가기
시간복잡도 : O(s*l)   s: S의 길이, l: L의 길이 

walkingtospace

https://oj.leetcode.com/problems/flatten-binary-tree-to-linked-list/

/*
대충 구현하여도 O(n)에 다 수행가능함. "문제는 어떻게 하면 elegant하게 구현할 수 있을까?"

preorder로 돌면서, 
1) parent의 leftchild가 있을 경우, left subtree의 rightmost 를 가리키는 포인터를 하나 두고, 
2) parent->right를 rightmost->right에 붙임.
3) left subtree를 parent->right에 붙임.
4) parent->left = NULL 처리.

walkingtospace

https://oj.leetcode.com/problems/jump-game/

/*
A[i]가 0인 elemant가 있을때, 이를 jump할 수 있는지 여부만 없는지만 판별하면 간단.

greedy algorithm으로 매 step마다 range 내에서 현재위치 i+x[i]가 maximum이 되도록 무조건 가장 높은 값을 선택하면서 i++로 순회한다.
i != n-1인데 값이 0일때, 현재까지 저장된 maxjump값이 현재 A[i]를 skip할 정도로 크다면(maxJump > i) i=maxJump로 이를 뛰어넘고, 그렇지 못하다면 return false. i가 n까지 무사히 증가한 경우에는 0이 없거나 무사히 0인 부분을 뛰어넘은 것이므로 return true 

시간복잡도 : O(n)
공간복잡도 : O(1)

walkingtospace

https://oj.leetcode.com/problems/merge-sorted-array/

/*
간단히 O(m+n) 알고리즘으로 해결하자면, mergesort에서 merge 알고리즘과 같이 하나씩 비교해서 채워나가고, 2개의 배열중 하나라도 끝까지 다 traversal 하면, 나머지 배열을 자동으로 끝까지 채워넣는 방식으로 해결 가능.

핵심은 A배열 뒷 공간의 index를 자유자재로 bug없이 활용할 수 있는지 여부

해볼 수 있는 사전 질문
정렬 방향은? 오름차순인지 내림차순인지?
중복된 숫자가 존재하는지, unique한지?

walkingtospace

https://oj.leetcode.com/problems/binary-tree-zigzag-level-order-traversal/

/*
BFS를 응용해서, 자료구조를 queue 대신에 deque 또는 vector를 이용, 한번은 front에서부터, 한번은 back 에서부터 pop 하면 될 듯
Time complexity : O(n)

순회순서는
 root(->)
 1 level depth(<-)
 2 level depth(->)

walkingtospace

https://oj.leetcode.com/problems/gray-code/

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1

walkingtospace

https://oj.leetcode.com/problems/maximum-subarray/

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.


class Solution {
    public:

walkingtospace

https://oj.leetcode.com/problems/swap-nodes-in-pairs/

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

/*

walkingtospace

https://oj.leetcode.com/problems/jump-game-ii/

/*
O(n^2) solution: 각 ele에 도달하는 mininum jump 수를 계산 
class Solution {
public:
    int jump(int A[], int n) {
        int* B = new int[n];
        int minJump = INT_MIN;