正文
题目1.两数相加
题目链接
题目大意：
给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
题目解析：
经典面试题。
用链表加法，注意进位的考虑，以及边界情况。
class Solution {
public:
ListNode* addTwoNumbers(ListNode* node1, ListNode* node2) {
if (!node1) {
return node2;
}
if (!node2) {
return node1;
}
ListNode *cur = NULL, *head = NULL;
int addition = 0;
while (node1 || node2) {
int sum = addition;
addition = 0;
if (node1) {
sum += node1->val;
node1 = node1->next;
}
if (node2) {
sum += node2->val;
node2 = node2->next;
}
if (sum >= 10) {
++addition;
sum -= 10;
}
if (!cur) {
cur = new ListNode(sum);
head = cur;
cur->next = NULL;
}
else {
cur->next = new ListNode(sum);
cur = cur->next;
cur->next = NULL;
}
}
if (addition) {
cur->next = new ListNode(addition);
cur = cur->next;
cur->next = NULL;
}
return head;
}
};
题目2.无重复字符的最长子串
题目链接
题目大意：
给出一个字符串str，求出str中最长子串的长度，要求子串里没有重复的字符。
样例：
Example 1:
Input: "abcabcbb"
Output: 3
最长子串是abc，长度是3；
Example 2:
Input: "bbbbb"
Output: 1
最长子串是b，长度是1；（bb的话出现重复的b）
题目解析：
如果没有重复字符的要求，那么str的最长子串就是自己；
基于此要求，我们考虑从左到右遍历字符串求subStr的时候，如果遇到某个字符subStr不存在，那么便把它加入subStr；
如果遇到某个字符是subStr已经有的，那么便把subStr已出现的字符的位置开始，左边的字符全部不要即可。
比如说对于题目的样例1，当我们枚举a/b/c的时候，都是直接加入subStr，得到abc；
当遇到第四个字符a时，把a去掉得到bc，再加入a，得到bca；
重复这个过程到字符串末尾，记录期间每个字符加入后的长度，可以得到满足要求的最长子串长度。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int vis[257] = {0};
int maxLen = 0, cur = 0;
for (int i = 0; i < s.length(); ++i) {
while (vis[s[i]]) {
vis[s[cur]] = 0;
++cur;
}
vis[s[i]] = 1;
maxLen = max(maxLen, i - cur + 1);
}
return maxLen;
}
};
题目3.Z 字形变换
题目链接
题目大意：
将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：
L C I R
E T O E S I I G
E D H N
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);
示例 1:
输入: s = "LEETCODEISHIRING", numRows = 3
输出: "LCIRETOESIIGEDHN"
示例 2:
输入: s = "LEETCODEISHIRING", numRows = 4
输出: "LDREOEIIECIHNTSG"
解释:
L D R
E O E I I
E C I H N
T S G
题目解析：
方法1：
找规律，模拟；
方法2:
vector暂存；
去掉x坐标的影响，直接计算y的变化。
trick就是nums=1的特殊判断。
这里使用方法2，代码较为直接：
const int N = 50000;
class Solution {
public:
string ans[N];
string convert(string s, int numRows) {
if (numRows <= 1) {
return s;
}
string ret;
for (int i = 0; i < numRows; ++i) {
ans[i].clear();
}
int y = 0, gap = 1;
for (int i = 0; i < s.length(); ++i) {
ans[y].push_back(s[i]);
y += gap;
if (y < 0) {
y = 1;
gap = 1;
}
else if (y >= numRows) {
y = numRows - 2;
gap = -1;
}
}
for (int i = 0; i < numRows; ++i) {
ret += ans[i];
}
return ret;
}
}leetcode;
题目4.盛最多水的容器
题目链接
题目大意：
给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例：
输入：[1,8,6,2,5,4,8,3,7]
输出：49
题目解析：
暴力，O(N^2)；
递增序列优化，常数优化；
面对1，2，3，4这种bad case，还是一样；
一种O(N)的解法如下：
对于数组height[0 ~ (n-1)]，假设最左边的数是x，最右边的数是y；
我们容易知道x和y组合形成的池子是width * min(x,y)；
假如x<y，那么对于节点x而言，选择节点y组成形成池子已经是最优解；（因为width * height的公式中，width已经是数组最大宽度，height已经是x的最大值）
那么保存完这个计算结果，实际上x已经可以抛弃！这样便减少了(n-1)次运算！
重复以上过程，可以使得算法时间复杂度为O(N)；
class Solution {
public:
int maxArea(vector<int>& height) {
int ans = 0;
int left = 0, right = height.size() - 1;
while (left < right) {
ans = max(ans, (right - left) * min(height[left], height[right]));
if (height[left] < height[right]) {
++left;
}
else {
--right;
}
}
return ans;
}
}leetcode;
总结
题目1 经典面试题，用来考察候选人的代码功底；
题目2 经典扫描线题目，从左到右遍历数组，记录一些状态以求最优解；
题目3 思维比较敏捷可以用找规律的方式，如果只是为了解决问题可以多用一些空间，直接去掉x坐标的影响；
题目4 也是比较常见的一类题目，暴力的做法比较简单，但是需要思考最优解。
