walkingtospace

void merge(int input[], int left, int right, int mid) {
  int leftIt = left;
  int rightIt = mid+1;
  int temp[right];
  int cnt = 0;
  
  while(leftIt<=mid && rightIt<=right) {
    if(input[leftIt] < input[rightIt]) {
      temp[cnt++] = input[leftIt++];
    } else {

walkingtospace

/*
Question : Given two strings, write a method to decide if one is a permutation of the other.

가정:
문자열은 아스키코드로 구성
extra memory 사용가능.

해법: 
간단한 인덱스테이블을 생성 0으로 초기화 
첫번째 문자열의 아스키코드를 인덱스로 사용하여(0~126) 인덱스 테이블에 저장할때마다 해당 인덱스의 value ++1 씩 증가.

walkingtospace

Q. Given a linked list, determine if it has a cycle in it. Can you solve it without using extra space?


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

walkingtospace

/*
https://oj.leetcode.com/problems/median-of-two-sorted-arrays/

Q: There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

사고흐름: 이미 정렬됨, O(log(m+n)) hint 주어짐. -> 바이너리 서치 또는 merge소트 병합단계를 활용해야할듯?-> 바이너리 서치로는 안풀림 -> 머지소트 병합단계를 활용하면? -> 이미정렬되어있으므로 O(m+n)에는 가능.

O(log(m+n))에 어떻게 찾을 수 있을까?

*/

walkingtospace

//https://oj.leetcode.com/problems/valid-palindrome/

//empty string = valid
//extra memory = none
//only alphanumeric case
//solution : two runner(head, end) 끝에서부터 서로 비교하면서 만날때까지 증감.
//time complexity : O(2n)
//test case : "", "   ", "a", "aba", "abcba", "a a baa", "a b c d  e"
        

walkingtospace

1.5 Implement a method to perform basic string compression using the counts of repeated characters. For example, the string aabcccccaaa would become a2blc5a3. If the "compressed" string would not become smaller than the original string, your method should return the original string.

extra memory : none
Time complxity : O(n)
잘못된 입력은 없다고 가정.
test case : "", "a", "abc", "abbcc", "aabcc", "aabbc", "aaaaa"
test case 작성 기준 :빈문자열, 한글자, 모두 동일 substring, 1글자 짜리 substring의 위치(첫,중앙,끝), 나머지는 다 동일.

string compressStr(string input) {
    int length = input.length();

walkingtospace

//https://oj.leetcode.com/problems/climbing-stairs/

Q. You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

//n=2는 n=1에서 1걸음 더 간것
//n=3은 n=2에서 1걸음 더 간것 + n=1에서 2걸음 
//n=4는 n=3에서 1걸음 더 간것 + n=2에서 2걸음 
// .. => 재귀함수로 n을 감소시키면서 풀면 되겠다.
// n>2, f(n) = f(n-1) + f(n-2) 성립

walkingtospace

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

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

walkingtospace

void permutation(vector<vector<int>>& res, vector<int> input, int startIndex) {
    if(input.size() <= startIndex) {
        res.push_back(input);
    } else {
        for(int i=startIndex ; i<input.size() ; i++) {
            vector<int>temp = input;
            
            int tempElement = temp[i]; //swap
            temp[i] = temp[startIndex];
            temp[startIndex] = tempElement;

walkingtospace

https://oj.leetcode.com/problems/validate-binary-search-tree/


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