the | Coder
BAN USERNormal algorithm won't work if pivot is repeated. One more array is needed
def lowPivotHighSort(array, pivot)
smaller = []
equal = []
bigger = []
return nil if array.index(pivot).nil?
array.each do |elem|
smaller << elem if elem < pivot
equal << elem if elem == pivot
bigger << elem if elem > pivot
end
return smaller + equal + bigger
end
Using bitset will avoid the waste. To find the first non repeated a second scan of the string is needed.
- the | Coder June 10, 2013import re
def exploreString( str, k ):
if k < 0 :
print( "k cannot be negative" )
return "NONE"
match = re.findall( r"([a-z])([1-9]*)", str )
print( match )
iter = 0
for pattern in match:
letter = pattern[0]
rep = pattern[1]
if rep == "" :
rep = "1"
print( letter, rep )
rep = int( rep )
if k >= iter and k < iter + rep:
return letter
else:
iter = iter + rep
return "NONE"
if __name__ == "__main__":
str = "a2b2cd2"
print( exploreString( str, 4 ) )
def findMaxKxK( matrix, k ):
print( matrix )
if k == 0 or len( matrix ) < k or len( matrix[0] ) < k :
print( "Invalid k!" )
return None
m1_columns = len( matrix[0] ) - k + 1
m1 = []
for i in range( len( matrix ) ) :
m1.append( [0]*m1_columns )
for i in range( len( matrix ) ) :
for j in range( m1_columns ):
m1[i][j] = sum( matrix[i][j:j+k] )
m2 = []
m2_rows = len( m1 ) - k + 1
for i in range( m2_rows ) :
m2.append( [0]*m1_columns )
for i in range( m2_rows ) :
for j in range( m1_columns ):
add = 0
for iter in range( k ) :
add = add + m1[i+iter][j]
m2[i][j] = add
i_max = 0
j_max = 0
max = 0
for i in range( m2_rows ):
for j in range( m1_columns ):
if m2[i][j] > max:
max = m2[i][j]
i_max = i
j_max = j
max_matrix = []
for i in range( k ) :
max_matrix.append( [0]*k )
for i in range( k ) :
for j in range( k ) :
max_matrix[i][j] = matrix[i_max+i][j_max+j]
print( str(k) + "_max = ", max_matrix )
return max_matrix
if __name__ == "__main__":
findMaxKxK( [ [3,2,1,0], [5,6,4,0], [1,2,3,0] ], 2 )
findMaxKxK( [ [3,2,1,0], [5,6,4,0], [1,2,3,0] ], 1 )
findMaxKxK( [ [3,2,1,0], [5,6,4,0], [1,2,3,0], [1,2,3,0] ], 4 )
findMaxKxK( [ [3,2,1,0], [5,6,4,0], [1,2,3,0], [1,2,3,0] ], 2 )
findMaxKxK( [ [3,2,1,0], [5,6,4,0], [1,2,3,0], [1,2,3,0] ], 0 )
3 2 1
5 6 4
1 2 3
sum columns
5 3
11 10
3 5
sum rows
16 13
14 15
find max -> 16
Why are you returning bool? It should be int.
Additionally, you should start searching on the left, not on the right.
i.e. for
string s1 = "abcdefgefg";
string s2 = "efg";
your code will return 7 instead of 4
Best.
Edit: improved your code a little :)
#include <iostream>
#include <string>
using namespace std;
int CheckSubString( const char * Str1, const char * Str2, int len1, int len2)
{
int iter1 = 0;
int iter2 = 0;
int i = iter1;
int j = iter2;
if(len1 < len2)
{
return -1;
}
while( i < len1 && j < len2 )
{
if( Str1[i] == Str2[j] )
{
i++;
j++;
}
else
{
j = 0;
i++;
}
}
if(j >= len2 )
{
return i - len2;
}
return -1;
}
int main()
{
string s1 = "abcdefnefg";
string s2 = "efg";
printf( "%d", CheckSubString( s1.c_str( ), s2.c_str( ), s1.length( ), s2.length( ) ) );
getchar();
return 0;
}
- the | Coder September 08, 2012O(N) actually
- the | Coder September 08, 2012Probably how to fix this
- the | Coder September 08, 2012def findMinAbsSum( array ):
best = ( float( "inf" ), float( "inf" ) )
for i in range( 0, len( array ) ) :
for j in range( i + 1, len( array ) ) :
if array[i] + array[j] == 0:
return ( array[i], array[j] )
if abs( array[i] + array[j] ) < abs( sum( best ) ) :
best = ( array[i], array[j] )
return best
if __name__ == "__main__" :
print( findMinAbsSum( [2,5,8,-7,2,9] ) )
print( findMinAbsSum( [2,5,8,-7,2,9,7] ) )
print( findMinAbsSum( [] ) )
One line solution, O(nlogn) though. Still funny.
- the | Coder June 30, 2013