Binary

**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

/*
 * Function that add two numbers consisted of linked list
 * Assume that all allocated memory will be free by caller
 */

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
  
    /* The number of nodes in each linked list is in the range 1-100
       val in ListNode is in the range 1-9
    */
    
    /* Adding two numbers of linked list is very simillar with a way we normally sum two numbers 
       Start from units to higher. 
       When place value after adding is higher than 9, use carry 
    */
    
    /* Declare struct pointers will be used in loop */
    struct ListNode* ltNext1=l1;
    struct ListNode* ltNext2=l2;
    struct ListNode* ltRslt = malloc(sizeof(struct ListNode)); // pointer for return
    struct ListNode* ltPrev; // previous node for setting next pointer
    
    memset(ltRslt, 0x00, sizeof(struct ListNode));
    
    /* Declare variables will be used in loop */
    int liCnt = 0;
    int liCarry = 0; // carry for sum
    int liVal1 = 0; // l1's node value
    int liVal2 = 0; // l2's node value
    int liSum = 0;  // sum of each node's value for result
    
    while(liCnt < 100 )  // max node will be 100 
    {
        if( ltNext1 == 0x00 && ltNext2 == 0x00 && liCarry == 0 )
        {
            /* break if all nodes are null and there's no carry to sum */
            break;
        }
        
        liVal1 = 0;
        if( ltNext1 != 0x00 )
        {
            /* set list1 node's value and change ltNext1 for next loop */
            liVal1 = ltNext1->val;
            ltNext1 = ltNext1->next;
        }
        
        liVal2 = 0;
        if( ltNext2 != 0x00 )
        {
            /* set list2 node's value and change ltNext2 for next loop */
            liVal2 = ltNext2->val;
            ltNext2 = ltNext2->next;
        }
        
        liSum = liVal1 + liVal2 + liCarry;
        liCarry = 0; // set carry to 0 after using it
        if( liSum > 9 )
        {
            liSum = liSum - 10;
            liCarry = 1;
        }
        
        /* create node for result */
        if( liCnt == 0 )
        {
            ltRslt->val = liSum;
            ltPrev = ltRslt;
        }
        else
        {
            struct ListNode* ltTemp = malloc(sizeof(struct ListNode));
            memset(ltTemp, 0x00, sizeof(struct ListNode));
            
            ltPrev->next = ltTemp;
            ltTemp->val = liSum;
            
            ltPrev = ltTemp;
        }
        
        liCnt++;
    }
    
    return ltRslt;
    
}

linked list로 이루어진 두 개의 수를 더하는 함수.

각 자리수를 더한 뒤 캐리를 계산해주고 계속해서 리트스를 만들어서 각 자리수를 저장한 뒤 첫번째 자리수의 리스트를 반환한다.

이렇게 리스트를 사용하면 자릿수 한계 없이 덧셈이 가능하다.

https://github.com/binary-river/algorithms/blob/Master/addTwoNumbers.c

int lengthOfLongestSubstring(char * s)
{
    
    /* Longest string length */
    int liLgstLen = 0;
    
    /* On process string information */
    int liPrgrLen = 0;
    int liPrgrStrtIdx = 0;
    int liPrgrEndIdx = 0;
    
    
    /* iterate. Length of string will be under 50000 */
    for(int i=0; i< 50000; i++)
    {
        /* facing null */
        if( *(s+i) == 0x00 )
        {
            return liLgstLen;
        }
        
        /* first loop, not null, set 1 */
        if( i == 0 )
        {
            liPrgrLen = 1;
            liPrgrStrtIdx = 0;
            liPrgrEndIdx = 0;
            
            liLgstLen = liPrgrLen;
            continue;
        }
        
        
        /* search current(i) character in on process string */
        int liPrgrCharMatchedIdx = -1;
        for( int j=liPrgrEndIdx; j>=liPrgrStrtIdx; j-- )
        {
            if( *(s+j) == *(s+i) )
            {
                /* get last index of matched char in on process string */
                liPrgrCharMatchedIdx = j; 
                break;
            }
        }
        
        /* not found, add 1 to on process information */
        if( liPrgrCharMatchedIdx == -1 )
        {
            liPrgrLen++;
            liPrgrEndIdx++;
        }
        /* found, change on process information */
        else
        {
            liPrgrLen = i - liPrgrCharMatchedIdx;
            liPrgrStrtIdx = liPrgrCharMatchedIdx +1;
            liPrgrEndIdx = i;
        }
        
        
        if( liPrgrLen > liLgstLen )
        {
            liLgstLen = liPrgrLen;
        }
    }
      
    return liLgstLen;
}

입력된 값중, 중복된 문자를 포함하지 않는 가장 긴 문자열의 길이를 반환하는 함수

한칸씩 움직이면서 지나온 문자열에 동일한 문자가 포함되어있는지 확인하며 길이를 구한다.

깃허브 주소:

https://github.com/binary-river/algorithms/blob/Master/lengthOfLongestSubstring.c

char * longestPalindrome(char * s)
{
    int liLgstL = 1; // length of longest palindromic substring
    int liLgstS = 0; // start index of longest palindromic substring
    int liLgstE = 0; // end index of longest palindromic substring
    
    int liSLen = strlen(s);

    /* if length of palindromic substring is even number
       then there should be at least one couple of same character 
     */
    for(int i=0; i<liSLen; i++)
    {
        int iSt = i; /* start */
        int iEd = i; /* end   */
        
        /* Check same following characters */
        while( s[i] == s[i+1] && i+1 < liSLen )
        {
            i++;
            iEd++;
        }
        
        /* Check palindromic using iSt and iEd */
        while( iSt-1 >= 0 && iEd+1 < liSLen )
        {
            if( s[iSt-1] == s[iEd+1] )
            {
                iSt--;
                iEd++;
            }
        }
        
        /* Compare longer */
        if( iEd - iSt +1 > liLgstL )
        {
            liLgstL = iEd - iSt +1;
            liLgstS = iSt;
            liLgstE = iEd;
        }
    }
    
    char *lsRslt = malloc(liLgstL + 1);
    memcpy(lsRslt, &s[liLgstS], liLgstL);
    lsRslt[liLgstL] = 0x00;
    
    return lsRslt;
}

입력값에서 순서대로 읽어도, 거꾸로 읽어도 동일한 가장 긴 문자열을 찾는 함수. 

개인적으로는 나비가 날개를 펼치는 데칼코마니 형상이 생각나서 나비배열이라고 제목을 지었다.

동일한 문자열이 나오는 경우 계속해서 확장해가다가, 동일한 문자열이 나오지 않으면, 시작과 끝을 나비처럼 펼처서 Palindrome 문자를 찾는다.

깃허브 주소:

https://github.com/binary-river/algorithms/blob/Master/longestPalindrome_v2.c

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
        
    double ldRslt = 0.0;        // return value
    int liMergedSize = 0;     // merged array size
    int liMerging[2000];  // array for merging two sorted arrays
    
    memset(liMerging, 0x00, sizeof(liMerging));
    
    int i=0; // index of nums1
    int j=0; // index of nums2
    int k=0; // index of merged array
    int nums1N = 0; // element of nums1
    int nums2N = 0; // element of nums2
    
    /* all out of index, then break */
    while( i < nums1Size || j < nums2Size )
    {
        /* nums1 out of index, then set 9999999 */
        if( i >= nums1Size )
        {
            nums1N = 9999999;
        }
        else
        {
            nums1N = nums1[i];
        }
        
        if( j >= nums2Size )
        {
            nums2N = 9999999;
        }
        else
        {
            nums2N = nums2[j];
        }
        
        if( nums1N < nums2N )
        {
            liMerging[k++] = nums1N;
            i++;
        }
        else
        {
            liMerging[k++] = nums2N;
            j++;
        }
    }
    
    liMergedSize = k;
    
    int liMidIdx = liMergedSize / 2;
    
    if( liMergedSize % 2 == 0 )
    {
        ldRslt = ( liMerging[liMidIdx-1] + liMerging[liMidIdx] ) / 2.0;
    }
    else
    {
        ldRslt = liMerging[liMidIdx];
    }
    
    return ldRslt;
}

두 개의 정렬된 integer array를 사용하여 중간값을 구하는 함수.

두 배열을 합쳐 한개의 정렬된 배열로 만들어 중간값을 구한다.

중간값은 배열 개수가 짝수인 경우는 가운데 두 수의 평균값으로, 홀수인 경우는 가운데 수로 출력한다.

깃허브 주소:

https://github.com/binary-river/algorithms/blob/Master/medianOfTwoSortedArray.c

int reverse(int x){
    // Integer range -2147483648  ~  2147483647
    int liIntA = INT_MAX/10;
    int liRest = x;
    int liRev = 0;
    
    while(liRest != 0)
    {   
	// compare if reverse integer is bigger than maximun integer size in 32-bit system
        if( abs(liRev) > liIntA ) return 0;
        if( liRev == liIntA && liRest % 10 > 7 ) return 0;
        if( liRev == liIntA*-1 && liRest % 10 < -8 ) return 0;            

        liRev = liRev * 10;
        liRev += liRest % 10;
        liRest = liRest/10;
    }
    
    return liRev;
}

입력된 숫자를 거꾸로 하여 반환하는 함수. 

while 안의 liIntA를 사용한 if문 3개는 32bit 시스템에서 integer 값의 최소값 및 최대값을 검증하기 위한 용도.

만약 거꾸로 한 숫자가 integer의 최소최대값을 넘는다면 0을 반환한다.

10진수의 거꾸로 수를 만들기 때문에 곱하고 나누고, 나머지값을 구하는데 모두 10을 사용한다.

깃허브 주소:

https://github.com/binary-river/algorithms/blob/Master/reverseInteger.c

int* twoSum(int* nums, int numsSize, int target, int* returnSize)
{  
  int* ii_index = malloc(sizeof(int)*2);
  *returnSize = 2;
    
    for(int i=0;i<numsSize-1;i++)
    {
        for(int j=i+1;j<numsSize; j++)
        {
           if( *(nums+i) + *(nums+j) == target )
           {
               ii_index[0]=i;
               ii_index[1]=j;
               break;
           }
        }
    }

    return ii_index;
}

integer 배열을 받아 배열중에서 더해서 특정값이 되는 랜덤한 2개의 수의 인덱스를 찾아 반환하는 함수.(먼저 찾는 조합을 우선 반환)

리턴값에서 integer pointer를 반환하여야 하므로, 함수 내부에서 malloc을 사용했다. free는 caller 가 호출해줄 것이다. 깜빡하고 빼먹지 않는다면.

깃허브 링크:

https://github.com/binary-river/algorithms/blob/Master/twoSum.c