1.最长回文串
最长回文串
class Solution {
public :
int longestPalindrome ( string s) {
int hash[ 127 ] = {
0 } ;
for ( auto x: s)
{
hash[ x] ++ ;
}
int ret = 0 ;
for ( auto x: hash)
{
ret += x/ 2 * 2 ;
}
return ret< s. size ( ) ? ret+ 1 : ret;
}
} ;
2.增减字符串匹配
增减字符串匹配
class Solution {
public :
vector< int > diStringMatch ( string s) {
int left = 0 , right = s. size ( ) ;
vector< int > ret;
for ( auto ch: s)
{
if ( ch == 'I' ) ret. push_back ( left++ ) ;
else ret. push_back ( right-- ) ;
}
ret. push_back ( left) ;
return ret;
}
} ;
3.分发饼干
分发饼干
class Solution {
public :
int findContentChildren ( vector< int > & g, vector< int > & s) {
int ret = 0 , m = g. size ( ) , n = s. size ( ) ;
sort ( g. begin ( ) , g. end ( ) ) ;
sort ( s. begin ( ) , s. end ( ) ) ;
for ( int i= 0 , j= 0 ; i< m&& j< n; i++ , j++ )
{
while ( j< n&& s[ j] < g[ i] ) j++ ;
if ( j< n) ret++ ;
}
return ret;
}
} ;
4.最优除法
最优除法
class Solution {
public :
string optimalDivision ( vector< int > & nums) {
int n = nums. size ( ) ;
if ( n == 1 ) return to_string ( nums[ 0 ] ) ;
if ( n == 2 ) return to_string ( nums[ 0 ] ) + '/' + to_string ( nums[ 1 ] ) ;
string str = to_string ( nums[ 0 ] ) + "/(" + to_string ( nums[ 1 ] ) ;
for ( int i= 2 ; i< n; i++ )
{
str+= '/' + to_string ( nums[ i] ) ;
}
str += ')' ;
return str;
}
} ;
5.跳跃游戏II
跳跃游戏II
class Solution {
public :
int jump ( vector< int > & nums) {
int left = 0 , right = 0 , maxPos = 0 , ret = 0 , n = nums. size ( ) ;
while ( left<= right)
{
if ( maxPos>= n- 1 ) return ret;
for ( int i= left; i<= right; i++ )
{
maxPos = max ( maxPos, nums[ i] + i) ;
}
left = right+ 1 ;
right = maxPos;
ret++ ;
}
return - 1 ;
}
} ;
6.跳跃游戏
跳跃游戏
class Solution {
public :
bool canJump ( vector< int > & nums) {
int left = 0 , right = 0 , maxPos = 0 , n = nums. size ( ) ;
while ( left<= right)
{
if ( maxPos>= n- 1 ) return true ;
for ( int i= left; i<= right; i++ )
{
maxPos = max ( maxPos, nums[ i] + i) ;
}
left = right+ 1 ;
right = maxPos;
}
return false ;
}
} ;
7.加油站
加油站
class Solution {
public :
int canCompleteCircuit ( vector< int > & gas, vector< int > & cost) {
int n = gas. size ( ) ;
int step = n;
for ( int i= 0 ; i< n; i++ )
{
int rest = 0 ;
for ( int step= 0 ; step< n; step++ )
{
int index = ( i+ step) % n;
rest = rest+ gas[ index] - cost[ index] ;
if ( rest< 0 ) break ;
}
if ( rest>= 0 ) return i;
}
return - 1 ;
}
} ;
class Solution {
public :
int canCompleteCircuit ( vector< int > & gas, vector< int > & cost) {
int n = gas. size ( ) ;
for ( int i= 0 ; i< n; i++ )
{
int rest = 0 ;
int step = 0 ;
for ( ; step< n; step++ )
{
int index = ( i+ step) % n;
rest = rest+ gas[ index] - cost[ index] ;
if ( rest< 0 ) break ;
}
if ( rest>= 0 ) return i;
i = i+ step;
}
return - 1 ;
}
} ;
8.单调递增的数字
单调递增的数字
class Solution {
public :
int monotoneIncreasingDigits ( int n) {
string s = to_string ( n) ;
int i= 0 , m = s. size ( ) ;
while ( i+ 1 < m && s[ i] <= s[ i+ 1 ] ) i++ ;
if ( i+ 1 == m) return n;
while ( i- 1 >= 0 && s[ i] == s[ i- 1 ] ) i-- ;
s[ i] -- ;
for ( int j= i+ 1 ; j< m; j++ )
{
s[ j] = '9' ;
}
return stoi ( s) ;
}
} ;
9.坏了的计算器
坏了的计算器
class Solution {
public :
int brokenCalc ( int startValue, int target) {
int ret = 0 ;
while ( target> startValue)
{
if ( target% 2 == 0 ) target/= 2 ;
else target += 1 ;
ret++ ;
}
return ret+ startValue- target;
}
} ;