第2章：LeetCode--第二部分

LeetCode -- Longest Palindromic Substring
class Solution {
public:
int isPalindromic(string s, int size, int len){
for(int i=; i+size<=len; i++){
//check s[i]~s[i+size-1]
int j = ;
while(j<size/){
if(s[i+j] != s[i+size--j])
break;
j+=;
}
if(j==size/) return i;
}
return -;
}
string longestPalindrome(string s) {
int len = s.size();
for(int sublen = len; sublen>; sublen--){
int ret = isPalindromic(s, sublen, len);
if(ret>=) return s.substr(ret, sublen);
}
return s;
}
};
//other guy's solution
class Solution {
public:
string longestPalindrome(string s)
{
int sLen = s.length(), maxLen = , maxStart = ;
int i = , l = , r = , len = ;
while(i<=sLen-maxLen/)
{
l = r = i;
while(r<sLen- && s[r+]==s[r]) r++;
i = r+;
while(l> && r<sLen- && s[r+]==s[l-]) l--, r++;
len = r-l+;
if(maxLen < len) maxLen = len, maxStart = l;
}
return s.substr(maxStart, maxLen);
}
};LeetCode--. Valid Parentheses
class Solution {
public:
bool isValid(string s) {
vector<char> OpStr;
int len = s.length();
char ee;
for(int i=; i<len; i++){
switch (s[i]){
case '(':
case '[':
case '{':
OpStr.push_back(s[i]);
break;
case ')':
if(OpStr.empty()) return false;
ee = OpStr.back();
if(ee == '(')
OpStr.pop_back();
else
return false;
break;
case ']':
if(OpStr.empty()) return false;
ee = *(OpStr.end()-);
if(ee == '[')
OpStr.pop_back();
else
return false;
break;
case '}':
if(OpStr.empty()) return false;
ee = *(OpStr.rbegin());
if(ee == '{')
OpStr.pop_back();
else
return false;
break;
default:
return false;
}
}
if(OpStr.empty())
return true;
else
return false;
}
};===Other Guy's Opetimazed solution====
#include <stack>
class Solution {
public:
bool isValid(string s) {
stack<char> paren;
for (char& c : s) {
switch (c) {
case '(':
case '{':
case '[': paren.push(c); break;
case ')': if (paren.empty() || paren.top()!='(') return false; else paren.pop(); break;
case '}': if (paren.empty() || paren.top()!='{') return false; else paren.pop(); break;
case ']': if (paren.empty() || paren.top()!='[') return false; else paren.pop(); break;
default: ; // pass
}
}
return paren.empty() ;
}
};
=======
bool isValid(string s) {
stack<char> st;
for(char c : s){
if(c == '('|| c == '{' || c == '['){
st.push(c);
}else{
if(st.empty()) return false;
if(c == ')' && st.top() != '(') return false;
if(c == '}' && st.top() != '{') return false;
if(c == ']' && st.top() != '[') return false;
st.pop();
}
}
return st.empty();//LeetCode -- 73. Set Matrix Zeroes
//https://www.cnblogs.com/feliz/p/11059445.htmlLeetCode -- . Valid Number
.Skip leading spaces.
.Skip sign bit.
.Integer, decimal point and fractional parts (make sure at least one digit exists)
.Exponential bit. (There may be sign bits again and make sure there is digit following)
.Skip following spaces.
.Make sure that's the end.bool isNumber(string s)
{
int n = s.size();
if(n == ) return false; int i = ;
//Skip leading spaces.
while(s[i] == ' ') i++; //Significand
if(s[i] == '+' || s[i] == '-') i++; int cnt = ;
//Integer part
while(isdigit(s[i]))
{
i++;
cnt++;
}
//Decimal point
if(s[i] == '.') i++;
//Fractional part
while(isdigit(s[i]))
{
i++;
cnt++;
}
if(cnt == ) return false; //No number in front or behind '.' //Exponential
if(s[i] == 'e')
{
i++;
if(s[i] == '+' || s[i] == '-') i++;
if(!isdigit(s[i])) return false; //No number follows
while(isdigit(s[i])) i++;
} //Skip following spaces;
while(s[i] == ' ') i++; return s[i] == '\0';
}

//暴力算法：
int GetMaxAddOfArray(int *arr, int sz)
{
int SUM = arr[];
for (int i = ; i < sz; i++)
{
int subOfArr = ; //临时最大值
for (int j = i; j < sz; j++)
{
subOfArr += arr[j]; if (subOfArr > SUM)
{
SUM = subOfArr;
}
}
}
return SUM;
}
---------------------
动态规划思想
思路分析
、状态方程 ： max( dp[ i ] ) = getMax( max( dp[ i - ] ) + arr[ i ] ,arr[ i ] )、上面式子的意义是：我们从头开始遍历数组，遍历到数组元素 arr[ i ] 时，连续的最大的和 可能为 max( dp[ i - ] ) + arr[ i ] ，也可能为 arr[ i ] ，做比较即可得出哪个更大，取最大值。时间复杂度为 n。代码实现
int GetMax(int a, int b) //得到两个数的最大值
{
return (a) > (b) ? (a) : (b);
}int GetMaxAddOfArray(int* arr, int sz)
{
if (arr == NULL || sz <= )
return ; int Sum = arr[]; //临时最大值
int MAX = arr[]; //比较之后的最大值 for (int i = ; i < sz; i++)
{
Sum = GetMax(Sum + arr[i], arr[i]); //状态方程 if (Sum >= MAX)
MAX = Sum;
}
return MAX;
}int main()
{
int array[] = { , , -, , , , -, , - };
int sz = sizeof(array) / sizeof(array[]);
int MAX = GetMaxAddOfArray(array, sz);
cout << MAX << endl;
return ;
}