11. strings

12 Jun 2020 | Algorithm

Character set/ASCII codes
character array
string
creating a string

Length of a string

int main()
{
  char * s = "welcome";
  int i;
  for(i=0; s[i]!='\n';i++)
  {
  }
  printf(" length is %d ", i);
  return 0;
}

changing case

int main()
{
  char A[] = "Welcome";
  int i ;
  for(i=0; A[i]!='\n',i++)
  {
    if(A[i]>=65 && A[i]<=90)
      A[i]=A[i]+32;
    else if(A[i]>='a'&&A[i]<=122)
      A[i]-=32;
  }

}

Counting Words

int main()
{
  char A[]="how are you";
  int i, word=1;
  for(i=0;A[i]!='\n';i++)
  {
    if(A[i]==' ')
      word ++;
  }
  printf("%d", word);
}

Counting words 2

int main()
{
  char A[]="how are you";
  int i, word=1;
  for(i=0;A[i]!='\n';i++)
  {
    if(A[i]==' ' && A[i-1]==' ')
      word ++;
  }
  printf("%d", word);
}

Counting Capital letter and small letter

Validate a string

int validate(char * name)
{
  int i;
  for(i=0; name[i]!='\n'; i++)
  {
    if(!(name[i]>=65 && name[i]=<90) && !(name[i]>=97 && name[i]<=122) && !(name[i]>=48 && name[i]<=59))
    {
      return 0;
    }
  }
  return 1;
}
int main()
{
  char * name="Ani?321";
  if(validate(name))
  {
    printf("valid string");
  }
  else
  {
    printf("no valid string");
  }
  return 0;
}

Reversing a strings

int main()
{
  char A[]="python"
  char B[7];
  int i;
  for(i=0; A[i]!='\n';i++)
  {
    i = i-1;
  }
  for(int j=0; i>=0; i--, j++)
  {
    B[j]=A[i];
  }
  B[j]='\n'
  printf("%s\n",B );
}

method 2

int main()
{
  char A[] = "python";
  char B[7], t;
  int i,j;
  for(j=0;A[j]!='\n';j++)
    j=j-1
  for(i=0;i<j;i++;j--;)
  {
    t = A[i];
    A[i]=A[j];
    A[j]=t;
  }
}

Comparing string & Palindrome

Example 1

int main()
{
  char A[]="painter";
  char B[]="painting";
  int i,j;
  for(i=0, j=0;A[i]!='\n'&&B[j]!='\n';j++,i++)
  {
    if(A[i]!=B[j])
      break;
    if(A[i]==B[j])
      printf("equal");
    else if(A[i]<B[j])
      printf("small");
    else
      printf("greater");
  }

}

Finding Duplicate in a string

compare with other letters
using Hash table as counting
using bits

int main()
{
  char A[]="finding";
  int H[26], i;
  for (i=0;A[i]!='\n';i++)
  {
    H[A[i]-97]+=1;
  }
  for(i=0;i<26;i++)
  {
    if(H[i]>1)
      printf("Dupicate", A[i]);
  }
}

Method2

using bitwise operation

left swift
bits Oring(Merging)
bits ANding(Masking)

int main()
{
  char A[]="finding";
  long int H=0, x=0;
  for(int i =0; A[i]!='\n';i++)
  {
    x=1;
    x=x<<A[i]-97'
    if(x&H>0)
    {
      printf("Duplicate")
    }
    else
      H=x:H;
  }
}

Check for Anagram

int main()
{
  char A[]="decimal"
  char B[]="Medical"
  int i, H[26]={0};
  for(i=0;A[i]!='\n';i++)
  {
    H[A[i]-97]+=1;
  }
  for(i=0;B[i]!='\n';i++)
  {
    H[B[i]-97]-=1;
    if(H[A[i]-97]<0)
    {
      printf("not anagram");
      break;
    }
  }
  if(B[i]=='\n')
    printf("its anagram");
}

permutation of string

void perm(char s[], int k)
{
  static int A[10] = {0};
  static char Res[10];
  int i;
  if(s[k]=='\n')
  {
    Res[k]='\n'
    printf("%s\n", );  
  }
  else
  {
    for(i=0;s[i]!="\n";i++)
    {
      if(A[i]==0)
      {
        Res[k]=s[i];
        A[i]=1;
        perm(s,k+1);
        A[i]=0;
      }
    }    
  }
}
int main()
{
  char s[]="ABC"''
  perm(s,0);
  return 0;
}

Method 2

void perm(char s[], int l, int h)
{
  int i;
  if(l==h)
  {
    printf("%s\n",s);
  }
  else
  {
      for(i=l,l<=h;i++)
      {
        swap(s[l],s[i]);
        perm(s,l+1,h);
        swap(s[l],s[i]);
      }    
  }

}
int main()
{
  char s[]="ABC"
  int h = sizeof(s)/sizeof(s[0]);
  perm(s,0,h);
  return 0;
}

Comment Read more

10. Array ADT represented problem solving 2

11 Jun 2020 | Algorithm

Finding Missing Elements

Method 1

int sum = 0;
for(int i = 0; i<11; i++)
{
  sum=sum+A[i];
}
s = n*(n+1)/2 // n은 맨 마지막 element 12
int result = s - sum; // 78-71

즉 expected Sum 값인 n*(n+1)/2 와 실제 Sum 값을 뺴면 빠진 Value가 뭔지 알 수 있다.
O(n)

Method 2

for(int = 0; i < n; i++)
{
  if(A[i]-i!=diff)
    printf(i+d)
}

linear search를 통해 구한다
행령 element의 값과 항상 linear하게 증가하는 i의 값의 diff 값은 일정하다
만약 다르다면 missing이 있다는 뜻
time complext O(n)

Method 3

for loop를 사용하는게 아닌 hash table 사용하여 구하기

h = 12, n = 10, l=1
O(n)
array에 있는 element를 Hash table에 마크를 해서 체크(Hash table/bits)

for(int i=0; i<n; i++)
{
  H[A[i]]++;
}
for(int i = l; i<=h;i++)
{
  if(H[i]==0)
    printf("%d \n", i );
}

Finding Duplicate Elements

Finding Duplicate in sorted Array
Counting Duplicate in sorted Array

int n = 10;
int lastDuplicate = 0;
for(int i=0; i<n; i++)
{
  if(A[i]==A[i++] && A[i]!=lastDuplicate)
  {
    printf("(%d)\n", A[i] );
    lastDuplicate = A[i];
  }
}

O(n)

for(int = 0; i<n-1; i++)
{
  if(A[i]==A[i++])
  {
    j=i+1
    while(A[j]==A[i])
      j++;
    printf("%d is appearing %d times \n",A[i], j-i );
    i=j-1;
  }
}

O(n^2)

Method 2 using Hash Table

n = 10

for(int i=0; i<n;i++)
{
  H[A[i]]++;
}
for(int i=0; i<= max; i++)
{
  if(H[i]>1)
      printf("%d %d\n",i,H[i] );
}

Finding Duplicate Elements in unsorted Array

n = 10
count = 1+1+1

for(int i=0; i<n-1;i++)
{
  count=1;
  if(A[i]!==-1)
  {
    for(int j=i+1; j<n;j++)
    {
      if(A[i]==A[j])
        count++;
        A[j] = -1;
    }  
  }
  if(count>1)
    printf(%d %d, A[i],count);
}

Method 2 using hash Table

Find a pair with sum k(a+b=k)

Method 2 using hash table

for(int i=0; i<n; i++)
{
  if(H[k-A[i]] ! = 0)
    printf("%d + %d = %d",A[i], k-A[i], k);
  H[A[i]]++

}

Method 3 using array table

int i =0;
int j=n-1;
while(i<j)
{
  if(A[i]+A[j]==k)
  {
    printf("%d+%d = %d", A[i], A[j],k)
    i++;
    j--;
  }
  else if (A[i]+A[j]<k)
    i++;
  else
    j--;
}

O(n)

Finding Max and Min in a single scan

int min = A[0];
int max = A[0];
for(i=1; i<n; i++)
{
  if(A[i]<min)
    min = A[i];
  else if (A[i]>max)
    max = A[i];
}

Quiz

Comment Read more

9. Array ADT represented problem solving

03 Jun 2020 | Algorithm

Searching in a Array

#include<stdio.h>
struct Array
{
  int A[10];
  int size;
  int length;
};
void Display(struct Array arr)
{
int i;
printf("\nElements are\n");
for(i=0;i<arr.length;i++)
printf("%d ",arr.A[i]);
}
void swap(int * x,int * y)
{
  int temp=* x;
  * x = * y;
  * y=temp;
}
int LinearSearch(struct Array *arr,int key)
{
  int i;
  for(i=0;i<arr->length;i++)
  {
    if(key==arr->A[i])
    {
      swap(&arr->A[i],&arr->A[0]);
      return i;
    }
  }
  return -1;
}
int main()
{
  struct Array arr1={2,23,14,5,6,9,8,12},10,8;
  // {}여기 더 붙여야한다.
  printf("%d",LinearSearch(&arr1,14));
  Display(arr1);
  return 0;
}

Binary Search in Array

#include<stdio.h>
struct Array
{
  int A[10];
  int size;
  int length;
};
void Display(struct Array arr)
{
  int i;
  printf("\nElements are\n");
  for(i=0;i<arr.length;i++)
    printf("%d ",arr.A[i]);
}
void swap(int * x,int *y)
{
  int temp=* x;
  * x=* y;
  * y=temp;
}
int BinarySearch(struct Array arr,int key)
{
  int l,mid,h;
  l=0;
  h=arr.length-1;
  while(l<=h)
  {
    mid=(l+h)/2;
    if(key==arr.A[mid])
      return mid;
    else if(key<arr.A[mid])
      h=mid-1;
    else
      l=mid+1;
  }
  return -1;
}
int RBinSearch(int a[],int l,int h,int key)
{
  int mid=0;
  if(l<=h)
  {
    mid=(l+h)/2;
    if(key==a[mid])
      return mid;
    else if(key<a[mid])
      return RBinSearch(a,l,mid-1,key);
  }
  else
    return RBinSearch(a,mid+1,h,key);
  return -1;
}
int main()
{
  struct Array arr1={2,3,9,16,18,21,28,32,35},10,9;
  // {}여기 더 붙여야한다.
  printf("%d",BinarySearch(arr1,16));
  Display(arr1);
  return 0;
}

Get Set Max Min on Array

#include<stdio.h>
struct Array
{
  int A[10];
  int size;
  int length;
};
void Display(struct Array arr)
{
  int i;
  printf("\nElements are\n");
    for(i=0;i<arr.length;i++)
      printf("%d ",arr.A[i]);
}
void swap(int *x,int *y)
{
  int temp=* x;
  * x=* y;
  * y=temp;
}
int Get(struct Array arr,int index)
{
  if(index>=0 && index<arr.length)
    return arr.A[index];
  return -1;
}
void Set(struct Array *arr,int index,int x)
{
  if(index>=0 && index<arr->length)
    arr->A[index]=x;
}
int Max(struct Array arr)
{
  int max=arr.A[0];
  int i;
  for(i=1;i<arr.length;i++)
  {
    if(arr.A[i]>max)
    max=arr.A[i];
  }
  return max;
}
int Min(struct Array arr)
{
  int min=arr.A[0];
  int i;
  for(i=1;i<arr.length;i++)
  {
    if(arr.A[i]<min)
    min=arr.A[i];
  }
  return min;
}
int Sum(struct Array arr)
{
  int s=0;
  int i;
  for(i=0;i<arr.length;i++)
    s+=arr.A[i];
  return s;
}
float Avg(struct Array arr)
{
return (float)Sum(arr)/arr.length;
}
int main()
{
  struct Array arr1={2,3,9,16,18,21,28,32,35},10,9;
  // {}여기 더 붙여야한다.
  printf("%d",Sum(arr1));
  Display(arr1);
  return 0;
}

Reversing Array

#include<stdio.h>
#include<stdlib.h>
struct Array
{
  int A[10];
  int size;
  int length;
};
void Display(struct Array arr)
{
  int i;
  printf("\nElements are\n");
  for(i=0;i<arr.length;i++)
    printf("%d ",arr.A[i]);
}
void swap(int *x,int *y)
{
    int temp=* x;
    * x=* y;
    * y=temp;
}
void Reverse(struct Array *arr)
{
    int * B;
    int i,j;
    B = new int[arr->length];
    for(i=arr->length-1,j=0;i>=0;i--,j++)
        B[j]=arr->A[i];
    for(i=0;i<arr->length;i++)
        arr->A[i]=B[i];
}
void Reverse2(struct Array *arr)
{
    int i,j;
    for(i=0,j=arr->length-1;i<j;i++,j--)
    {
        swap(&arr->A[i],&arr->A[j]);
    }
}
int main()
{
    struct Array arr1={2,3,9,16,18,21,28,32,35},10,9;
    // {}여기 더 붙여야한다.
    Reverse(&arr1);
    Display(arr1);
    return 0;
}

Checking if Array is sorted

#include<stdio.h>
#include<stdlib.h>
struct Array
{
  int A[10];
  int size;
  int length;
};
void Display(struct Array arr)
{
  int i;
  printf("\nElements are\n");
  for(i=0;i<arr.length;i++)
      printf("%d ",arr.A[i]);
}
int isSorted(struct Array arr)
{
  int i;
  for(i=0;i<arr.length-1;i++)
  {
    if(arr.A[i]>arr.A[i+1])
      return 0;
  }
  return 1;
}
int main()
{
  struct Array arr1={2,3,9,16,18,21,28,32,35},10,9;
  // {}여기 더 붙여야한다.
  printf("%d",isSorted(arr1));
  Display(arr1);
  return 0;
}

Merging 2 Arrays

#include<stdio.h>
#include<stdlib.h>
struct Array
{
    int A[10];
    int size;
    int length;
};
void Display(struct Array arr)
{
    int i;
    printf("\nElements are\n");
    for(i=0;i<arr.length;i++)
        printf("%d ",arr.A[i]);
}
struct Array* Merge(struct Array * arr1,struct Array * arr2)
{
    int i,j,k;
    i=j=k=0;
    struct Array * arr3 = new Array[20];
    while(i<arr1->length && j<arr2->length)
    {
        if(arr1->A[i]<arr2->A[j])
            arr3->A[k++]=arr1->A[i++];
        else
        arr3->A[k++]=arr2->A[j++];
    }
    for(;i<arr1->length;i++)
        arr3->A[k++]=arr1->A[i];
    for(;j<arr2->length;j++)
        arr3->A[k++]=arr2->A[j];
    arr3->length=arr1->length+arr2->length;
    arr3->size=10;
    return arr3;
}
int main()
{
    struct Array arr1={2,9,21,28,35},10,5;
    struct Array arr2={2,3,16,18,28},10,5;
    //{} 추가
    struct Array * arr3;
    arr3=Merge(&arr1,&arr2);
    Display(*arr3);
    return 0;
}

Set Operations on Arrays

#include<stdio.h>
#include<stdlib.h>
struct Array
{
    int A[10];
    int size;
    int length;
};
void Display(struct Array arr)
{
    int i;
    printf("\nElements are\n");
    for(i=0;i<arr.length;i++)
        printf("%d ",arr.A[i]);
}
struct Array* Union(struct Array * arr1,struct Array * arr2)
{
    int i,j,k;
    i=j=k=0;
    //struct Array * arr3=(struct Array * )malloc(sizeof(struct Array));
    struct Array * arr3= new Array[arr1->length*2];
    while(i<arr1->length && j<arr2->length)
    {
        if(arr1->A[i]<arr2->A[j])
            arr3->A[k++]=arr1->A[i++];
        else if(arr2->A[j]<arr1->A[i])
            arr3->A[k++]=arr2->A[j++];
        else
        {
            arr3->A[k++]=arr1->A[i++];
            j++;
        }
    }
    for(;i<arr1->length;i++)
        arr3->A[k++]=arr1->A[i];
    for(;j<arr2->length;j++)
        arr3->A[k++]=arr2->A[j];
        arr3->length=k;
        arr3->size=10;
    return arr3;
}
struct Array* Intersection(struct Array * arr1,struct Array* arr2)
{
    int i,j,k;
    i=j=k=0;
    //struct Array * arr3=(struct Array * )malloc(sizeof(struct Array));
    struct Array * arr3= new Array[arr1->length*2];
    while(i<arr1->length && j<arr2->length)
    {
        if(arr1->A[i]<arr2->A[j])
            i++;
        else if(arr2->A[j]<arr1->A[i])
            j++;
        else if(arr1->A[i]==arr2->A[j])
    {
        arr3->A[k++]=arr1->A[i++];
        j++;
    }
    }
    arr3->length=k;
    arr3->size=10;
    return arr3;
}
struct Array* Difference(struct Array* arr1,struct Array* arr2)
{
    int i,j,k;
    i=j=k=0;
    // struct Array * arr3=(struct Array * )malloc(sizeof(struct Array));
    struct Array * arr3= new Array[arr1->length*2];
    while(i<arr1->length && j<arr2->length)
    {
        if(arr1->A[i]<arr2->A[j])
            arr3->A[k++]=arr1->A[i++];
        else if(arr2->A[j]<arr1->A[i])
            j++;
        else
        {
            i++;
            j++;
        }
    }
    for(;i<arr1->length;i++)
        arr3->A[k++]=arr1->A[i];
        arr3->length=k;
        arr3->size=10;
    return arr3;
}
int main()
{
    struct Array arr1={2,9,21,28,35},10,5;
    // {}추가
    struct Array arr2={2,3,9,18,28},10,5;
    // {} 추가
    struct Array * arr3;
    arr3=Union(&arr1,&arr2);
    Display(*arr3);
    return 0;
}

Array C++ class

#include <iostream>
using namespace std;
template<class T>
class Array
{
private:
    T * A;
    int size;
    int length;
public:
    Array()
    {
        size=10;
        A=new T[10];
        length=0;
    }
    Array(int sz)
    {
        size=sz;
        length=0;
        A=new T[size];
    }
    ~Array()
    {
    delete []A;
    }
    void Display();
    void Insert(int index,T x);
    T Delete(int index);
};
template<class T>
void Array<T>::Display()
{
    for(int i=0;i<length;i++)
    cout<<A[i]<<" ";
    cout<<endl;
}
template<class T>
void Array<T>::Insert(int index,T x)
{
    if(index>=0 && index<=length)
    {
        for(int i=length-1;i>=index;i--)
            A[i+1]=A[i];
        A[index]=x;
        length++;
    }
}
template<class T>
T Array<T>::Delete(int index)
{
    T x=0;
    if(index>=0 && index<length)
    {
        x=A[index];
        for(int i=index;i<length-1;i++)
            A[i]=A[i+1];
        length--;
    }
    return x;
}
int main()
{
    Array<char> arr(10);
    arr.Insert(0,'a');
    arr.Insert(1,'c');
    arr.Insert(2,'d');
    arr.Display();
    cout<<arr.Delete(0)<<endl;
    arr.Display();
    return 0;
}

Comment Read more

8. Array ADT

02 Jun 2020 | Algorithm

Array Abstract Data type (ADT)

Data
1. Array space
2. size
3. Length(number of element)
Operation
1. Display()

for (int i=0; i<length; i++)
{
  cout<<A[i]<<endl;
}

Add(x)/Append(x)

A[length] = x;
Length++;

Insert(index, x)

for (i=length; i > index; i--){
  A[i] = A[i-1];
}
A[length] = x;
length ++;

Delete(index)

void delet(int index)
{
  int x = A[index];
  for (int i = index; i<Length-1; i++)
  {
    A[i] = A[i+1];
  }
}

Search(x)
- Linear Search
- Binary Search

int binsearch(int l,int r,int key)
{
  int mid = (l+r)/2;
  if(l=<r)
  {
    if(A[mid]==key)
    {
      return mid;
    }
    else if(key<A[mid])
      return binsearch(l,mid-1,key);
    else
      return binsearch(mid+1, r,key);
  }
  return -1;
}

O(logn+1)-> O(logn)
1. Get(index)

int get(int index)
{
  if(index>=0 && index<length)
  {
    return A[index];
  }
}

Set(index, x)

set(index,x)
{
  if(index>=0 && index<length)
  {
    A[index]=x;
  }
}

max()/min()

int max()
{
  max = A[0];
  for(int i = 1; i<length; i++1)
  {
    if(A[i]>max)
      max=A[i];
  }
  return max;
}

Reverse()

for(int i=0, j=Length-1;i<j; i++, j--)
{
  temp=A[i];
  A[i] = A[j]
  A[j] = temp;
}

switch()/rotate()

for (i=0; i<length; i++)
{
  if(key==A[i])
  {
    swap(A[i],A[i-1])
    return i-1;
  }
}

sorted

bool isSorted(int[] A, n)
{
  for(int i=0; i<n-1; i++)
  {
    if(A[i]>A[i+1])
    return false
  }
  return true
}

Merge

- Append
- Concat
- compare
- copy

int i = 0;
int j = 0;
int k = 0;
while (i<m && j<n)
{
  if(A[i]<B[j])
  {
    C[k++] = A[i++]
  }
  else
  {
    C[k++] = B[j++]
  }
}

 - Time Complexity O(m+n)

Comment Read more

7. Array representation

02 Jun 2020 | Algorithm

what is an Array
Declaring and initializing
Accessing Array

Static Array

int x = 10 // Scalar
int A[5] // Vector
A[2] = 15
cout<<A[2]; // output 15;

Dynamic Array

int* p = new int[5]
delet []p;

//or

std::unique_ptr<int> p(new int[5]);

int* p = new int[5]
delet []p;

p = 5;

pointer는 기본적으로 array first element를 addressing 한다.

Example

#include <stdio.h>
#include <stdlib.h>
int main()
{
int A[5]={2,4,6,8,10};
int * p;
int i;
p=(int * )malloc(5*sizeof(int));
p[0]=3;
p[1]=5;
p[2]=7;
p[3]=9;
p[4]=11;
for(i=0;i<5;i++)
printf("%d ",A[i]);
printf("\n");
for(i=0;i<5;i++)
printf("%d ",p[i]);
return 0;
}

2D array

Example

#include <stdio.h>
#include <stdlib.h>
int main()
{
int * p,* q;
int i;
p=(int * )malloc(5*sizeof(int));
p[0]=3;p[1]=5;p[2]=7;p[3]=9;p[4]=11;
q=(int * )malloc(10*sizeof(int));
for(i=0;i<5;i++)
q[i]=p[i];
free(p);
p=q;
q=NULL;
for(i=0;i<5;i++)
printf("%d \n",p[i]);
return 0;
}

Array in compiler(Mapping address in Array)

Example

#include <stdio.h>
#include <stdlib.h>
int main()
{
int A[3][4]={1,2,3,4},{2,4,6,8},{1,3,5,7};
// {}여기 더 붙여야한다.
int * B[3];
int ** C;
int i,j;
B[0]=(int * )malloc(4*sizeof(int));
B[1]=(int * )malloc(4*sizeof(int));
B[2]=(int * )malloc(4*sizeof(int));
C=(int ** )malloc(3*sizeof(int *));
C[0]=(int * )malloc(4*sizeof(int));
C[1]=(int * )malloc(4*sizeof(int));
C[2]=(int * )malloc(4*sizeof(int));
for(i=0;i<3;i++)
{
for(j=0;j<4;j++)
printf("%d ",C[i][j]);
printf("\n");
}
return 0;
}

Comment Read more

Older Newer

for Robot Artificial Inteligence

11. strings

Length of a string

changing case

Counting Words

Counting words 2

Counting Capital letter and small letter

Validate a string

Reversing a strings

method 2

Comparing string & Palindrome

Example 1

Finding Duplicate in a string

Method2

using bitwise operation

Check for Anagram

permutation of string

Method 2

10. Array ADT represented problem solving 2

Finding Missing Elements

Method 1

Method 2

Method 3

Finding Duplicate Elements

Method 2 using Hash Table

Finding Duplicate Elements in unsorted Array

Method 2 using hash Table

Find a pair with sum k(a+b=k)

Method 2 using hash table

Method 3 using array table

Finding Max and Min in a single scan

Quiz

9. Array ADT represented problem solving

Searching in a Array

Binary Search in Array

Get Set Max Min on Array

Reversing Array

Checking if Array is sorted

Merging 2 Arrays

Set Operations on Arrays

Array C++ class

8. Array ADT

Array Abstract Data type (ADT)

7. Array representation

Static Array

Dynamic Array

Example

2D array

Example

Array in compiler(Mapping address in Array)

Example