No.1
题目链接：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)思路：注意当前数字表示的是能跳的最大步数，也就是小于等于这个数字的地方都可以到达。先依次检查数字，如果不是0，就往前跳最大步数，看看是否可以超过数组末位；如果是0，就往回找，找到一个位置，当前位置序号加上它的数字可以超过刚才数字为0的位置。如果一直回退到了上一跳起点，那么就无法到达。还要注意[0, 1]，即一开始就是0的特殊情况。
(2)代码：
class Solution {
public:
bool canJump(vector<int>& nums) {
int pos = 0;
while(pos < nums.size() - 1) {
if(nums[pos] > 0) pos += nums[pos];
else {
int i = pos - 1;
for(i; i > 0; i--) {
if(i + nums[i] > pos) {
pos = nums[i] + i;
break;
}
}
if(i <= 0) return false;
}
}
return true;
}
};
No.2
题目链接：Maximum Subarray
- 题目描述：
Find the contiguous subarray within an array (containing at least one number) which has the largest sum. For example, given the array
[-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray[4,-1,2,1]has the largest sum = 6.
(1)思路：参考以下，Kadane算法。从数组头循环，使用两个计数变量sum和max分别记录当前扫描和以及已扫描的最大和，当sum为负时重置为0。
(2)代码：
class Solution {
public:
int maxSubArray(vector<int>& nums) {
if (nums.size() < 1) return 0;
int i, sum = 0;
int max = nums[0];
for (i = 0; i < nums.size(); ++i) {
sum += nums[i];
if (sum > max) max = sum;
if (sum < 0) sum = 0;
}
return max;
}
};
No.3
题目链接：Longest Valid Parentheses
- 题目介绍：
Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring. Another example is “)()())”, where the longest valid parentheses substring is “()()”, which has length = 4.
(1)思路：用ans计数匹配成功的前后括号数，把括号字符串依次使用stack进行压栈比较并将成功匹配的抛出。
(2)代码：
#include <stack>
class Solution {
public:
int longestValidParentheses(string s) {
int ans = 0;
stack<int> par;
par.push(-1);
for (int i = 0; i <= s.length(); i++) {
if(ans <= i-par.top()-1) ans = i-par.top()-1;
if (i == s.length()) break;
if (par.top() >= 0 && s[par.top()] == '(' && s[i] == ')') par.pop();
else par.push(i);
}
return ans;
}
};
No.4
题目链接：Letter Combinations of a Phone Number
- 题目描述：
Given a digit string, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given below.
Input:Digit string “23”
Output: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].
Note: Although the above answer is in lexicographical order, your answer could be in any order you want.
(1)思路:把每个按键上的字母先保存下来，然后读取输入的字符串，对于要求解的数字，暴力循环求解即可。
(2)代码：
class Solution {
public:
vector<string> letterCombinations(string digits) {
vector<string> bot, ans, tmp;
bot.push_back("");
bot.push_back("");
bot.push_back("abc");
bot.push_back("def");
bot.push_back("ghi");
bot.push_back("jkl");
bot.push_back("mno");
bot.push_back("pqrs");
bot.push_back("tuv");
bot.push_back("wxyz");
for (int i = 0; i < bot[digits[0] - '0'].size(); i++) {
char c = bot[digits[0] - '0'][i];
string str;
stringstream stream;
stream << c;
str = stream.str();
ans.push_back(str);
}
for (int i = 1; i < digits.length(); i++) {
tmp = ans;
ans.clear();
for (int k = 0; k < tmp.size(); k++) {
for (int j = 0; j < bot[digits[i] - '0'].size(); j++) {
ans.push_back(tmp[k] + bot[digits[i] - '0'][j]);
}
}
}
return ans;
}
};
