No.1
题目链接：Container With Most Water
- 题目描述：
Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container and n is at least 2.
(1)思路：两个指针分别从容器的左右向中间移动直到相遇，检查移动的过程中形成容量最大的容器。
(2)代码：
class Solution {
public:
int maxArea(vector<int>& height) {
int n = height.size(), ans = -1, i = 0, j = n-1;
while (i < j) {
if (height[i] < height[j]) {
ans = ans > height[i]*(j-i) ? ans : height[i]*(j-i);
i++;
}
else {
ans = ans > height[j]*(j-i) ? ans : height[j]*(j-i);
j--;
}
}
return ans;
}
};
No.2
题目链接：Trapping Rain Water
- 题目描述：
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
For example,
Given
[0,1,0,2,1,0,1,3,2,1,2,1], return 6.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!
(1)思路：刚开始看到这个题目还觉得很难理解，不太明白题目要表达的意思，不过结合图表后就容易明白了。我的思路就是先找到数组里最大的数字，然后从头尾分别向最大元素靠近，因为这样只要分别逼近时前一个元素比后一个元素大就满足，把差值给结果，然后再把差值加到后一个元素上，继续和下一个比较。前后分别逼近结束后就得到了答案。
(2)代码：
int trap(int* height, int heightSize) {
int max = height[0];
int maxnum = 0;
int ans = 0;
for(int i = 0; i < heightSize; i++) {
if(height[i] > max) {
max = height[i];
maxnum = i;
}
}
for(int j = 0; j < maxnum; j++) {
if(height[j] > height[j+1]) {
ans += height[j] - height[j+1];
height[j+1] += height[j] - height[j+1];
}
}
for(int k = heightSize - 1; k > maxnum; k--){
if(height[k] > height[k-1]) {
ans += height[k] - height[k-1];
height[k-1] += height[k] - height[k-1];
}
}
return ans;
}
No.3
题目链接：Reverse Nodes in k-Group
- 题目描述：
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
ou may not alter the values in the nodes, only nodes itself may be changed.
nly constant memory is allowed.
or example, iven this linked list: 1->2->3->4->5
or k = 2, you should return: 2->1->4->3->5
or k = 3, you should return: 3->2->1->4->5
1)思路：申请链表，从头找到k个节点，然后循环反向链接这些节点到原有链表上，继续递归逆转后续节点，直至链表结束或者最后不满足k个节点。
2)代码：
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k){
ListNode*curr;
curr = head;
int count = 0;
while(curr != NULL && count != k){
curr = curr->next;
count++;
}
if (count == k) {
curr = reverseKGroup(curr, k);
while (count-- > 0) {
ListNode*tmp = head->next;
head->next = curr;
curr = head;
head = tmp;
}
head = curr;
}
return head;
}
};
No.4
题目链接：Valid Number
- 题目描述：
Validate if a given string is numeric.
ome examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true
Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.
update (2015-02-10):
he signature of the C++ function had been updated. If you still see your function signature accepts a const char * argument, please click the reload button to reset your code definition.
(1)思路：判断一个字符串是不是数字。
a.排除首尾空格
b.排除头部符号位
c.剩下的字符串再进行检查。
在碰到e之前，判断字符是否是 0-9 的数字或小数点。要注意.1 和1. 这种格式都是可以被判断为数字的。
碰到指数之后，后面不能有小数点，指数后面第一位可以是符号位，其余只能是数字。
(2)代码：
class Solution {
public:
bool isNumber(string s) {
auto realStart = s.find_first_not_of(' ');
auto realEnd = s.find_last_not_of(' ');
int num_count = 0, exp_count = 0, point_count = 0;
bool exp_flag = false;
if (s[realStart] == '+' || s[realStart] == '-') realStart++;
for (auto i = realStart; i <= realEnd; i++) {
if (exp_flag) {
if (exp_count == 0 && num_count == 0 && (s[i] == '+' || s[i] == '-')) exp_count = 1;
else if (s[i] <= '9' && s[i] >= '0') num_count++;
else return false;
}
else {
if (s[i] == 'e') {
if (num_count == 0) return false;
exp_flag = true;
num_count = 0;
}
else if (s[i] <= '9' && s[i] >= '0') num_count++;
else if (s[i] == '.') point_count++;
else return false;
}
}
if (num_count < 1 || point_count > 1) return false;
return true;
}
};
