jingtianjiang
BAN USERI revised you code as below. The main changes are:
static public void Test()
{
Console.WriteLine( "aaaaab - a*b - {0}", Match( "aaaaab", 0, "a*b", 0 ) );
Console.WriteLine( "aaaaabc - a*b - {0}", Match( "aaaaabc", 0, "a*b", 0 ) );
Console.WriteLine( "ab - a.b - {0}", Match( "ab", 0, "a.b", 0 ) );
Console.WriteLine( "acb - a.b - {0}", Match( "acb", 0, "a.b", 0 ) );
Console.WriteLine( "acccccccb - a*b - {0}", Match( "acccccccb", 0, "a*b", 0 ) );
Console.WriteLine( "acccccccb - a.*b - {0}", Match( "acccccccb", 0, "a.*b", 0 ) );
Console.WriteLine( "b - a*b - {0}", Match( "b", 0, "a*b", 0 ) );
}
static bool Match( string s, int scur, string r, int rcur )
{
if ( IsEmpty( r, rcur ) )
{
return IsEmpty( s, scur );
}
if ( r[rcur] == '*' )
{
if ( IsEmpty( s, scur ) & GetLength( r, rcur ) == 1 )
{
return true;
}
return MatchStar( s, scur, r, rcur, r[rcur - 1] );
}
if ( IsEmpty( s, scur ) )
{
return false;
}
if ( r[rcur] != s[scur] && r[rcur] != '.' )
{
if ( GetLength( r, rcur ) > 1 && r[rcur + 1] == '*' )
{
return Match( s, scur, r, rcur + 2 );
}
else
{
return false;
}
}
return Match( s, scur + 1, r, rcur + 1 );
}
static bool MatchStar( string s, int scur, string r, int rcur, char c )
{
if ( Match( s, scur, r, rcur + 1 ) )
{
return true;
}
for ( int i = scur + 1; i < s.Length; i++ )
{
if ( IsMatch( s[i - 1], c ) && Match( s, i, r, rcur ) )
{
return true;
}
}
return false;
}
static int GetLength( string s, int index )
{
return s.Length - index;
}
static bool IsEmpty( string s, int index )
{
return index == s.Length;
}
static bool IsMatch( char c1, char c2 )
{
if ( c1 == c2 || c2 == '.' )
{
return true;
}
else
{
return false;
}
}
it's not correct enough
try "acccbccb" and "a*b" please
<pre lang="" line="1" title="CodeMonkey8253" class="run-this">code in C#
class DNA : IComparable<DNA>
{
public int Start { get; set; }
public int End { get; set; }
public int Score { get; set; }
public DNA( int s, int e, int ds )
{
this.Start = s;
this.End = e;
this.Score = ds;
}
public int CompareTo( DNA d )
{
return this.End.CompareTo( d.End );
}
}
public static void FindMaxScore()
{
List<DNA> dnas = new List<DNA>();
// read input
dnas.Sort();
int N = 100;
int[] scores = new int[N];
int[] seleceted = new int[N];
for (int i = 0; i < dnas.Count; i++)
{
DNA d = dnas[i];
if (d.Score + scores[d.Start] >= scores[d.End - 1])
{
scores[d.End] = d.Score + scores[d.Start];
seleceted[d.End] = i+1;
}
else
{
scores[d.End] = scores[d.End - 1];
seleceted[d.End] = seleceted[d.End - 1];
}
int iEnd = N;
if (i < dnas.Count - 1)
{
iEnd = dnas[i + 1].End;
}
for (int j = d.End + 1; j < iEnd; j++)
{
scores[j] = scores[j - 1];
seleceted[j] = seleceted[j - 1];
}
}
//output max score
Console.WriteLine( scores[N - 1] );
//output selected DNA strings
int idx = seleceted[N - 1];
while (idx > 0)
{
Console.WriteLine( idx - 1 );
idx = seleceted[dnas[idx - 1].Start];
}
}</pre><pre title="CodeMonkey8253" input="yes">
</pre>
you don't need to sort the the right array in ascending order. Since you have traversed from the back, and found the "JustBig" number, the right array must be in desecending order, so you just need to reverse the right array.
if i am wrong, please correct me.
good
- jingtianjiang July 22, 2011
It's not enough. check [-1, 0, 3, 3, 5] and [-1, 1, 1, 4, 5] please.
- jingtianjiang November 29, 20111. min/max is -1/5 and -1/5, ok
2. sum is 10 and 10, ok
3. sum of squares is 44 and 44, ok
but they are not similar.
essentially, if there are N elements in a array, we should check the sums of power( i, N) for i in array