leetcode题解日练--2016.8.8

不给自己任何借口

今日题目：

1、跳跃游戏 ； tag:贪心

2、回文分割 tag：回溯

今日摘录：

对面走过来一个人，撞上了叫做爱情；对面开过来一辆车，撞上了叫做车祸。可惜车与车总是撞，人与人却总是让。
——电影《推拿》

55. Jump Game | Difficulty: Medium

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.

tag：贪心
题意：数组每个元素代表当前最多能走的步数，判断当前这一数组能否走到最后位置。

思路：
1、贪心的思想，每一步都极可能的使下一步能走更远。比如A = [2,3,1,1,4]，当前首先是在pos=0的位置，可以有两种走法，i=1的时候，下一步能走nums[0+1]+1=4,i=1的时候能走nums[0+2]+2=3，所以下一步先走1步，依此类推。

class Solution {
public:
    bool helper(vector<int>&nums,int pos,int remain)
    {
        if(nums[pos]>=remain)   return true;
        else
        {
            int max = 0;
            int step = 0;
            for(int i=1;i<=nums[pos];i++)
            {
                if(nums[pos+i]+i>max) 
                {
                    max = nums[pos+i]+i;
                    step = i;
                }
            }
            if(step==0)  return false;
            return helper(nums,pos+step,remain-step);
        }
    }
    bool canJump(vector<int>& nums) {
        return helper(nums,0,nums.size()-1);
    }
};

结果：16ms

2、https://discuss.leetcode.com/topic/4911/linear-and-simple-solution-in-c/2的解法，思路类似但是代码简单很多

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int reach=0;
        for(int i=0;i<nums.size() && i<=reach;i++)
        {
            reach = max(i+nums[i],reach);
        }
        return reach>=nums.size()-1;
    }
};

结果：16ms

131. Palindrome Partitioning | Difficulty: Medium

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = “aab”,
Return

[
[“aa”,”b”],
[“a”,”a”,”b”]
]

tag：回溯
题意：给定一个字符串，返回所有该字符串的回文串。

思路：
1、套用回溯模板就可以搞定，从a|a|b开始，逐次判断a|ab、aa|b、aab这几种情况即可。

class Solution {
public:
    bool isPalindrome(string s,int begin,int end)
    {
        while(begin<=end)
        {
            if(s[begin++]!=s[end--])    return false;
        }
        return true;
    }

    void dfs(int index,string s,vector<vector<string>>&res,vector<string>&tmp)
    {
        if(index==s.size())
        {
            res.push_back(tmp);
            return;
        }
        for(int i=index;i<s.size();i++)
        {
            if(isPalindrome( s,index,i))
            {
            tmp.push_back(s.substr(index,i-index+1));
            dfs(i+1,s,res,tmp);
            tmp.pop_back();
            }
        }
    }
    vector<vector<string>> partition(string s) {
        vector<vector<string>>res;
        vector<string>  tmp;
        dfs(0,s,res,tmp);
        return res;
    }
};

结果：24ms