noobProg
BAN USERHave a "seen" and "arr" arrays, seen just monitors if the character has been seen before, arr keeps track of the first occurance of characters.
Every time we detect a repeat of the character, we reset the seen array, and set to begin searching from the next index of the first occurance of the repeated character.
for example:
dabcade
>the arr['a']=1 when we encounter 'a' again at i=3, we reset i=arr['a']+1=2, and start the search again. This works even for multiple repeated characters.
>In the end we check if the "currLen>maxLen", because i would have popped of after reaching the length of the string and there is a possibility the last run would have produced the longest length( like in this case).
#include<stdio.h>
#include<string.h>
void longSub(char str[])
{
int arr[256];
int seen[256];
int i;
int len=strlen(str);
for(i=0;i<256;i++)
{arr[i]=-1;seen[i]=-1;}
int j,maxLen=0,currLen=0,maxStart,currSt,temp;
int chFlag=0;
i=0;
while(i<len)
{
if(!chFlag) {currSt=i;chFlag=1;}
if(seen[str[i]]==-1)
{
arr[str[i]]=i;
currLen=currLen+1;
seen[str[i]]=1;
printf("%d , %c, %d, %d \n",i,str[i],seen[str[i]],arr[str[i]]);
i++;
}
else
{
printf("Repeat Detected\n");
chFlag=0;
if(currLen>=maxLen)
{maxLen=currLen;maxStart=currSt;}
i=arr[str[i]]+1;
for(j=0;j<256;j++) seen[j]=-1;
currLen=0;
}
}
if(currLen>=maxLen)
{maxLen=currLen;maxStart=currSt;}
for(i=maxStart;i<maxStart+maxLen;i++)
printf("%c",str[i]);
printf("\n");
}
int main()
{
char str[]="abcdefebcabcdef";
longSub(str);
return 0;
}
import java.util.*;
public class kLargest{
public static void main(String args[])
{
//int []arr={5,5,5,23,23,23,23,1,2,5,6,7,7,7,7,7,7,3,2,1,34,54,23,5,5,5};
int []arr={1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,3,3,3,4,4,5};
findkLarge(arr);
}
public static void findkLarge(int []a)
{
HashMap<Integer,Integer> hm=new HashMap<Integer,Integer>();
int i;
for(i=0;i<a.length;i++)
{
if(hm.get(a[i])==null)
hm.put(a[i],1);
else
hm.put(a[i],hm.get(a[i]).intValue()+1);
}
System.out.println(" "+hm);
Object [] keys = hm.keySet().toArray();
Integer max1val=Integer.MIN_VALUE;
Integer max2val=Integer.MIN_VALUE;
Integer max1key=0,max2key=0;
for(i=0;i<keys.length;i++)
{
if((Integer)hm.get(keys[i])>=max1val)
{
max2val=max1val;
max2key=max1key;
max1val=(Integer)hm.get(keys[i]);
max1key=(Integer)keys[i];
}
else if((Integer)hm.get(keys[i])>=max2val)
{
max2val=(Integer)hm.get(keys[i]).intValue();
max2key=(Integer)keys[i];
}
}
System.out.println("The Second Highest key: "+max2key+" value: "+max2val);
}
}
public class pivotSearch{
public static void main(String [] args)
{
int []arr={4,5,6,7,8,9,10,11,12,13,1,2,3};
int ind=piv(arr,0,arr.length-1);
int key=10;
System.out.println("The array is pivoted at :"+arr[ind]+" index: "+ind);
System.out.println("The array contains :"+key+" at "+pivotedSearch(arr,key,ind));
}
public static int pivotedSearch(int []data,int key,int pivot)
{
if(data[pivot]==key) return pivot;
else if(key>data[0])
return binSearch(data,key,0,pivot-1);
else
return binSearch(data,key,pivot+1,data.length-1);
}
public static int binSearch(int []data,int key,int low,int high)
{
int mid=(low+high)/2;
if(low>high) return -1;
if(data[mid]==key) return mid;
else if(data[mid]<key) return binSearch(data,key,mid+1,high);
else return binSearch(data,key,low,mid-1);
}
public static int piv(int []data,int low,int high)
{
int mid=(low+high)/2;
if(low>high) return -1;
if(data[mid]>data[mid+1])
{
return mid+1;
}
else if(data[low]>data[high])
{
return piv(data,mid+1,high);
}
else {
return piv(data,low,mid-1);
}
}
}
public class countOcc
{
public static void main(String []args)
{
int []arr={1,1,1,2,2,2,2,2,2,2,2,3,3,4,5,5,6,6,7,8,9,10,10,10,10,11};
for( int i=0;i<12;i++)
System.out.println("The occurance of "+i+" is: "+cntOcc(arr,i,0,arr.length));
}
public static int cntOcc(int []data,int key,int low,int high)
{
int temp,mid,lcount=0,rcount=0;
if(low>high) return 0;
mid=(low+high)/2;
if(data[mid]==key)
{
if((mid-1)>0)
lcount=cntOcc(data,key,low,mid-1);
if((mid+1)<data.length)
rcount=cntOcc(data,key,mid+1,high);
return (lcount+rcount+1);
}
else if(data[mid]>key)
{
return cntOcc(data,key,low,mid-1);
}
else {
return cntOcc(data,key,mid+1,high);
}
}
}
#include<stdio.h>
#include<string.h>
#include <conio.h>
int main()
{
char ch[1000];
printf("Please Enter the String\n");
gets(ch);
int i=0,k=0,j;
int len=strlen(ch);
while(ch[i]!='\0')
{
if(ch[i]==' '||ch[i]=='\t') {i++;}
else{
while((ch[i++]!=' '&& i<len)&&(ch[i++]!='\t' && i<len));
k++;
}
}
printf("The number of words is=%d", k);
getch();
}
haha, why the fancy swapping without a temp variable!, makes your code less readable.
- noobProg March 20, 2013