Palindrome Partitioning II

Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

Note: See the previous wrong answers

class Solution {
public:
    int minCut(string s) {
        int slen=s.size();
       
        if (slen<=1) return 0;
        vector<int> minc(slen+1,0);
        for (int i=0; i<slen+1; i++)
        {
            minc[i]=i-1;
        }
       
        for (int i=0; i<slen; i++)
        {
            for (int j=0; i-j>=0&&i+j<slen&&s[i-j]==s[i+j]; j++)
            {
                minc[i+j+1]=min(minc[i+j+1],minc[i-j]+1);
            }
           
            for (int j=1; i-j+1>=0&&i+j<slen&&s[i-j+1]==s[i+j]; j++)
            {
                minc[i+j+1]=min(minc[i+j+1],minc[i-j+1]+1);
            }
        }
       
        return minc[slen];
    }
};

Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

 https://oj.leetcode.com/discuss/13336/shortest-o-n-dp-solution-with-explanations

The key is to use a vector of 256 int to be hashmap and use i-startIdx+1 to denote the length of the string.

从左往右扫描，当遇到重复字母时，以上一个重复字母的index+1，作为新的搜索起始位置，

直到最后一个字母，复杂度是O(n)。

 

 

 

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int len=s.length();
       
        vector<int> v(256,-1);
        int ret=0, startIdx=0;
       
        for (int i=0; i<len; i++)
        {
            int j=s[i];
            startIdx = max(v[j]+1,startIdx);
            v[j]=i;
            ret = max(ret,i-startIdx+1);
        }
       
        return ret;
    }
};

Candy

There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:

• Each child must have at least one candy.
• Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

Idea: scan twice: find out the inversion and

correct the number of candies for the corresponding child.

class Solution {
public:
    int candy(vector<int> &ratings) {
        int n= ratings.size();
        if (n==0)  return 0;
        int total=0;
        vector<int> res(n,1);
        for (int i=1; i<n; i++)
        {
            if (ratings[i]>ratings[i-1])
            {
                res[i]=res[i-1]+1;
            }
        }
       
        for (int i=n-2; i>=0; i--)
        {
            if (ratings[i]>ratings[i+1]&&res[i]<=res[i+1])
            {
                res[i]=res[i+1]+1;
            }
        }
       
        for (int j=0; j<n; j++)
        {
           total+=res[j];
        }   
       
        return total;
    }
};

Best Time to Buy and Sell Stock III

Say you have an array for which the i^th element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Idea:

A very helpful discussion from
https://oj.leetcode.com/discuss/1381/any-solutions-better-than-o-n-2
'
First consider the case that when we are only allowed to make one transaction. we can handle this easily with DP. If we move forward, any new price we meet will only affect our history result by two ways:
will it be so low that it beats our previous lowest price? will it be so high that we should instead sell on this time to gain a higher profit (than the history record)? Similarly, we can move backward with the highest price and profit in record. Either way would take O(n) time. Now consider the two transaction case. Since there will be no overlaps, we are actually dividing the whole time into two intervals.??
We want to maximize the profit in each of them so the same method above will apply here. We are actually trying to break the day at each time instance, by adding the potential max profit before and after it together. By recording history and future for each time point, we can again do this within O(n) time.'


class Solution {
public:
    int maxProfit(vector<int> &prices) {
        int n=prices.size();
        if (n<2) return 0;
       
        int low=prices[0], hi=prices[n-1];
        vector<int> profit1(n,0);
        vector<int> profit2(n,0);
       
        for(int i=1; i<n; i++)
        {
            low = min(low, prices[i]);
            profit1[i]=max(prices[i]-low,profit1[i-1]);
        }
       
        for (int j=n-1; j>=0; j--)
        {
            hi = max( hi, prices[j]);
            profit2[j]=max(hi-prices[j],profit2[j]);
        }
       
        int maxProfit=0;
        for (int i=0; i<n;i++)
        {
            maxProfit = max(maxProfit, profit1[i]+profit2[i]);
        }
        return maxProfit;
    }
};

Best Time to Buy and Sell Stock

Say you have an array for which the i^th element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Idea: greedy method

My thought is to slide the window of minIdx and maxIdx. Another solution is much more concise.
1.
class Solution {
public:
    int maxProfit(vector<int> &prices) {
        int n=prices.size();
       
        if(n<2)
           return 0;
          
        int minp=prices[0], maxp=prices[1];
        int minIdx=0, maxIdx=1;
        int maxProfit = maxp-minp;
        for (int i=1; i<n; i++)
        {
            if (prices[i]<minp)
               {
                   minp=prices[i];
                   minIdx = i;
                   if (minIdx>=maxIdx)
                   {
                    maxp=prices[i];
                    maxIdx=i;                  
                   }
               }
            if (prices[i]>maxp)
                {
                    maxp=prices[i];
                    maxIdx=i;
                }
            int tmp = maxp-minp;
            if(tmp>maxProfit)
              {
                  maxProfit=tmp;
              }
        }
       
        return maxProfit;
    }
};

2.

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        int n=prices.size();
       
        if(n<2)
           return 0;
          
        int minp=prices[0],maxProfit = 0;
        for (int i=1; i<n; i++)
        {
            maxProfit = max(maxProfit, prices[i]-minp);
            minp=min(prices[i],minp);
        }
       
        return maxProfit;
    }
};

Jump Game II

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
For example:
Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)


https://oj.leetcode.com/discuss/422/is-there-better-solution-for-jump-game-ii?start=0#a_list_title

'The idea is to use "last" to keep track of the maximum distance that has been reached by using the minimum steps "ret", whereas "curr" is the maximum distance that can be reached by using "ret+1" steps.  curr = max(i+A[i]) where 0 <= i <= last.'

class Solution {
public:
    int jump(int A[], int n) {
       
        int ret=0,last=0,cur=0;
       
        for (int i=0;i<n; i++)
        {
            if (i>last)
            {
                if (cur==last&&last<n-1)
                   return -1;
               
                last=cur;
                ret++;
            }
           
            cur = max(cur,i+A[i]);
        }
        return ret;
    }
};

Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.

1. O(N) time complexity and O(1) space complexity

class Solution {
public:
    bool canJump(int A[], int n) {
       
        int maxdist=0;
       
        for (int i=0; i<=maxdist&&i<n;i++)
        {
            maxdist = max(maxdist, i+A[i]);
        }
       
        return maxdist>=n-1;
    }
};

2. My original solution. O(N^2) time complexity

class Solution {
public:
    bool canJump(int A[], int n) {
        int i=0;
        int j=0;
        int newI, newJ;
        while(j<n-1)
        {
            j=i+A[i];
            if(j>=n-1)
              return true;
            int nextMax=j+A[j];
            newI=j;
            for (int k=i; k<j; k++)
            {
                if (k+A[k]>nextMax)
                {
                    nextMax=k+A[k];
                    newI = k;
                }
            }
           
            i=newI;
            if (nextMax==j)
               return false;
        }
       
        return true;
    }
};