walkingtospace

https://oj.leetcode.com/problems/pascals-triangle-ii/


Given an index k, return the kth row of the Pascal's triangle.
For example, given k = 3,
Return [1,3,3,1].
Note:
Could you optimize your algorithm to use only O(k) extra space?

/*

walkingtospace

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

/**
 * 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/set-matrix-zeroes/

/*
가장 간단한 in place 알고리즘은 은 for 루프를 이용, O(mn)만큼 순회하면서 처음에 0인 element는 -1 또는 아무 값으로 변경하고
그다음 다시 O(mn)만큼 순회하면서 이를 0으로 바꾸는 방법(문제의 정의에서, 나중에 바뀐 0에 해당하는 열과행은 set zero 하지 않아야 하므로

엄밀히 말해서 input에 어떤 integer 값이 들어올지 모르기 때문에 맞는 풀이는 아님.
*/

walkingtospace

https://oj.leetcode.com/problems/reverse-integer/

class Solution {
    public:
    int reverse(int x) {
        if(x < 10 && x > -10) return x;
        
        int result = 0;
        stringstream ss;
        ss << x;

walkingtospace

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

Given an 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?


/*
솔직히 이건.. 알고리즘적 사고 테스트라기보단, XOR을 이용한 trick에 가깝다.

walkingtospace

https://oj.leetcode.com/problems/best-time-to-buy-and-sell-stock/best-time-to-buy-and-sell-stock

/*
testcase1 [3,6,1,3,2,11]
testcase2 [3,1,2,6,7,8,1,11]
testcase3 [7,6,5,4,3,4]

O(n^2) : brute-forth
O(n) :  1. traverse first->end, init max = 0
        2. compare profit, if(profit > max) max = profit

walkingtospace

https://oj.leetcode.com/problems/rotate-list/

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

walkingtospace

https://oj.leetcode.com/problems/sum-root-to-leaf-numbers/

int sumNumbers(TreeNode *root) {
        if(!root) return 0;
        
        vector<int> sum;
        sum.push_back(root->val);
        
        if(!root->left && !root->right) return root->val;
        

walkingtospace

https://oj.leetcode.com/problems/largest-rectangle-in-histogram/

/*
O(n^2) : loop 두 개로 각 히스토그램마다 min, max를 이용해서 최대 크기를 구한다 : Time limit exceed

O(n) : O(n)알고리즘을 위해서는 index가 증가할때마다 실시간으로 계산하는 방식으로는 안됨 -> 계산 타이밍을 늦춰서 한꺼번에 계산할 수는 없을까? -> rectangle들을 저장해둘 extra space가 필요함 -> 순서를 기억하는 가장 적합한 자료구조인 stack 사용-> 오름차순으로 계속 스택에 저장하다가, top보다 작은 height[i]를 만나는 순간 미뤄왔던 계산 수행(while(s.top() > height[i]) -> 스택에는 항상 오름차순으로 유지.
while 루프가 끝난후, s.empty() == false이면 남은 rectangle 넓이 계산.

Time complexity : 
일반적인 경우, O(n)~ O(kn) 보장

walkingtospace

https://oj.leetcode.com/problems/remove-nth-node-from-end-of-list/

Given a linked list, remove the nth node from the end of list and return its head.

For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.
Note: