写这篇的初衷是整理复习一遍自己刷过的题
- 1. 两数之和
- 2. 两数相加
- 3. 无重复字符的最长子串
- 5. 最长回文子串
- 6. Z 字形变换
- 7. 整数反转
- 8. 字符串转换整数 (atoi)
- 9. 回文数
- 11. 盛最多水的容器
- 12. 整数转罗马数字
- 13. 罗马数字转整数
- 14. 最长公共前缀
- 15. 三数之和
- 16. 最接近的三数之和
- 19. 删除链表的倒数第 N 个结点
- 70. 爬楼梯
- 300. 最长递增子序列
1. 两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
题解一：暴力，太慢了
class Solution
{
public:
vector twoSum(vector& nums, int target)
{
vectora;
for (int i = 0; i < nums.size() - 1; i++)
{
for (int j = i + 1; j < nums.size(); j++)
{
if (nums[i] + nums[j] == target);
{
a.push_back(i);
a.push_back(j);
return a;
}
}
}
return a;
}
};
解法二：哈希
注意：此题中unordered_map的第二个值是 i，而 i 可能是 0 ，所以判断 target - nums[i] 时，不能使用if（ target - nums[i]），需要用到迭代器
class Solution
{
public:
vector twoSum(vector& nums, int target)
{
unordered_mapa;
vectorarr;
for (int i = 0; i < nums.size(); ++i)
{
unordered_map::iterator it = a.find(target - nums[i]);
if (it != a.end())
{
arr.push_back(it->second);
arr.push_back(i);
break;
}
else
a[nums[i]] = i;
}
return arr;
}
};
解法三：哈希
为了解决解法二判断 target - nums[i] 时需要用到迭代器，可以令 a[nums[i]] = i+1；
class Solution
{
public:
vector twoSum(vector& nums, int target)
{
unordered_mapa;
vectorarr;
for (int i = 0; i < nums.size(); ++i)
{
if (a[target - nums[i]])
{
arr.push_back(a[target - nums[i]]-1);
arr.push_back(i);
break;
}
else
a[nums[i]] = i+1;
}
return arr;
}
};
2. 两数相加
2. 两数相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
参考了官方题解
只要L1或者L2不等于NULL，就一直在循环里
设置三个变量a、b、now、tmp（进位，初值为0）
a:L1的值，若L1为NULL，则为0
b:L2的值，若L2为NULL，则为0
now:a+b+tmp
tmp记录是否进位：now/10
class Solution
{
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
{
ListNode* head = NULL;
ListNode* tail = NULL;
int tmp = 0;
int a, b, now;
while (l1 || l2)
{
a = l1 ? l1->val : 0;
b = l2 ? l2->val : 0;
now = a + b + tmp;
tmp = now / 10;
if (!head)//head为空
{
head = tail = new ListNode(now % 10);
}
else
{
tail->next = new ListNode(now % 10);
tail = tail->next;
}
if (l1)
{
l1 = l1->next;
}
if (l2)
{
l2 = l2->next;
}
}
if (tmp)
{
tail->next = new ListNode(tmp);
}
return head;
}
};
忽然发现之前用C写的时间、空间效率都好很多很多
但C++那个程序更加简洁，可读性好
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2)
{
int len1 = 0, len2 = 0;
struct ListNode* p;
struct ListNode* q;
struct ListNode* head;
struct ListNode* r;
for (p = l1; p->next != NULL; p = p->next)
len1++;
for (q = l2; q->next != NULL; q = q->next)
len2++;
if (len1 > len2)
{
p = head = l1;
q = l2;
}
else
{
p = head = l2;
q = l1;
}
int tmp = 0;
int val;
while (p != NULL)
{
if (q != NULL)
{
val=p->val;
p->val = (p->val + q->val + tmp) % 10;
tmp = (val + q->val + tmp) / 10;
if (tmp == 1 && p->next == NULL)
{
r = (struct ListNode*)malloc(sizeof(struct ListNode));
p->next = r;
r->val = tmp;
r->next = NULL;
break;
}
q = q->next;
}
else
{
val=p->val;
p->val=(p->val+tmp)%10;
tmp=(val+tmp)/10;
if (p->next == NULL && tmp == 1)
{
r = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(r != NULL);
r->val = tmp;
r->next = NULL;
p->next = r;
break;
}
}
p = p->next;
}
return head;
}
3. 无重复字符的最长子串
3. 无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
注意：子串有顺序，子序列无
解法一：哈希，效率极差
class Solution
{
public:
int lengthOfLongestSubstring(string s)
{
unordered_mapa;
int max = 0;
int num = 0;
int i = 0, j = 0;
for (i = 0; i < s.length(); i++)
{
num = 0;
a.clear();
for (j = i; j < s.length(); j++)
{
if (a.empty() || a[s[j]] == 0)
{
a[s[j]]++;
num++;
}
else
{
max = fmax(max, num);
break;
}
}
if (j == s.length())
{
max = fmax(max, num);
if (max == s.length())
break;
}
}
return max;
}
};
解法二：哈希+滑动窗口
效率有变好一点
class Solution
{
public:
int lengthOfLongestSubstring(string s)
{
if (s.size() == 0)
return 0;
unordered_set a;
int max = 0;
int left = 0;
for (int right = 0; right < s.size(); right++)
{
while (a.find(s[right]) != a.end())//迭代器，不等于时，代表找到了
{
a.erase(s[left]);
left++;
}
max = fmax(max, right - left + 1);
a.insert(s[right]);
}
return max;
}
};
5. 最长回文子串
5. 最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。
动态规划，好好看官方题解，多看几遍就能看懂！！！然后多练
class Solution
{
public:
string longestPalindrome(string s)
{
int n = s.length();
if (n < 2)
return s;
vector>dp(n, vector(n));
for (int i = 0; i < n; i++)
{
dp[i][i] = true;
}
int begin = 0;
int maxlen = 1;
for (int len = 2; len <= n; len++)
{
for (int left = 0; left < n; left++)
{
int right = len + left - 1;
if (right >= n)
break;
if (s[left] != s[right])
{
dp[left][right] = false;
}
else
{
if (right - left < 3)
{
dp[left][right] = true;
}
else
{
dp[left][right] = dp[left + 1][right - 1];
}
}
if (dp[left][right] && right - left + 1 > maxlen)
{
maxlen = right - left + 1;
begin = left;
}
}
}
return s.substr(begin, maxlen);
}
};
以下是一个我很喜欢的博主：代码随想录 的题解
**定义dp[i] [j]：**范围[i,j] 的子串是否是回文子串，是为true，否则为false
**初始化：**false
当s[i]与s[j]相等时，有如下三种情况
情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串
情况二：下标i 与 j相差为1，例如aa，也是文子串
情况三：下标：i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1] [j - 1]是否为true。情况三是根据dp[i + 1] [j - 1]是否为true，再对dp[i] [j]进行赋值true的。
dp[i + 1] [j - 1] 在 dp[i] [j]的左下角
所以一定要从下到上，从左到右遍历，这样保证dp[i + 1] [j - 1]都是经过计算的。
class Solution {
public:
string longestPalindrome(string s) {
vector> dp(s.size(), vector(s.size(), 0));
int maxlenth = 0;
int left = 0;
int right = 0;
for (int i = s.size() - 1; i >= 0; i--) {
for (int j = i; j < s.size(); j++) {
if (s[i] == s[j]) {
if (j - i <= 1) { // 情况一 和 情况二
dp[i][j] = true;
} else if (dp[i + 1][j - 1]) { // 情况三
dp[i][j] = true;
}
}
if (dp[i][j] && j - i + 1 > maxlenth) {
maxlenth = j - i + 1;
left = i;
right = j;
}
}
}
return s.substr(left, right - left + 1);
}
};
6. Z 字形变换
6. Z 字形变换
将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 “PAYPALISHIRING” 行数为 3 时，排列如下：
P A H N
A P L S I I G
Y I R
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：“PAHNAPLSIIGYIR”。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);
示例 1：
输入：s = “PAYPALISHIRING”, numRows = 3
输出：“PAHNAPLSIIGYIR”
这个题说来还有一个故事，我秋招投的第一家公司的笔试题就是这个
class Solution
{
public:
string convert(string s, int numRows)
{
if (numRows == 1)
return s;
int tmp = 2 * (numRows - 1);
string s1;
for (int k = 0; k < numRows; k++)
{
for (int j = 0; j < s.length(); j++)
{
if ((j % tmp == k) || (j % tmp == tmp - k))
{
s1.push_back(s[j]);
}
}
}
return s1;
}
};
感觉整理题解比之前写都要难，这次在评论区发现一个新思路，来源于 Krahets
先创建一个numRows行的二维数组，初始化 i=0，flag=-1 （这个-1就很妙了）
思路是：先按顺序给每行一维数组赋值，Z字形在0行和numRows行会转变方向，所以i0||inumRows-1时flag=-flag来转换方向，也因此flag的初值为-1
eg.1,2,3,4,5,6,7 numRows=3
1给第一行，2给第二行，3给第三行，转变方向，
i又来到了第二行，4给第二行，5给第一行，转变方向，
6给第二行，7给第三行
（第一行对应下标0，第三行对应下标numRows-1）
class Solution
{
public:
string convert(string s, int numRows)
{
if (numRows == 1)
return s;
vector>a(numRows);
int i=0;
int flag=-1;
for(auto n:s)
{
a[i].push_back(n);
if(i==0||i==numRows-1)flag=-flag;
i+=flag;
}
string s1;
for(auto n:a)
{
for(auto m:n)
{
s1.push_back(m);
}
}
return s1;
}
};
7. 整数反转
7. 整数反转
给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。
示例 1：
输入：x = 123
输出：321
终于来到了一个简单题
不过，我之前的代码真的是不忍直视，又臭又长,贴出来图一乐，哈哈
当时沉迷于swap、字符串的reverse、atoi、itoa不能自拔
class Solution
{
public:
void swap(char& a, char& b)
{
char tmp = a;
a = b;
b = tmp;
}
int reverse(int x)
{
if(x==0)return 0;
int left = 0;
string s = to_string(x);
int right = s.size()-1;
if (x < 0)
{
left++;
}
while (s[right] == '0')
{
right--;
}
string s1(s.begin() + left, s.begin() + right+1);
left=0;
right=s1.length()-1;
while (left <= right)
{
swap(s1[left], s1[right]);
left++;
right--;
}
long long num = 0;
for (int i = 0; i < s1.length(); i++)
{
num = num*10+s1[i] - '0';
}
if (x < 0)
num = -num;
if (num > -1 + pow(2, 31) || num < -pow(2, 31))
return 0;
return num;
}
};
因为可能越界，所以x1的类型为long long 型，return之前判断一下就行
清晰明了、赏心悦目
class Solution
{
public:
int reverse(int x)
{
long long x1 = 0;
while (x)
{
x1 = 10 * x1 + x % 10;
x /= 10;
}
if (x1 > INT_MAX || x1 < INT_MIN)
return 0;
return x1;
}
};
8. 字符串转换整数 (atoi)
8. 字符串转换整数 (atoi)
请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。
函数 myAtoi(string s) 的算法如下：
-
读入字符串并丢弃无用的前导空格
-
检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
-
读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
将前面步骤读入的这些数字转换为整数（即，“123” -> 123， “0032” -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。 -
如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
-
返回整数作为最终结果。
注意：
本题中的空白字符只包括空格字符 ’ ’ 。
除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。
非常见得的字符串转数字：
条件1：前导空格跳过
条件2：+ - 符号可在最前边有（前导空格后）
条件3：后续只要不是数字就返回，只要超过int型范围就返回INT_MAX或者INT_MIN
class Solution
{
public:
int myAtoi(string s)
{
int len = s.length();
int i = 0;
while (s[i] == ' ')
{
i++;
}
int flag = 1;
if (s[i] == '-')
{
flag = -flag;
i++;
}
else if (s[i] == '+')
{
i++;
}
long long x = 0;
while (i < len)
{
if (!isdigit(s[i]) || x > INT_MAX)
break;
x = x * 10 + (s[i] - '0');
i++;
}
x = x * flag;
if (x > INT_MAX)
{
return INT_MAX;
}
else if (x < INT_MIN)
{
return INT_MIN;
}
return x;
}
};
9. 回文数
9. 回文数
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。
示例 1：
输入：x = 121
输出：true
class Solution
{
public:
bool isPalindrome(int x)
{
if (x < 0)
return false;
int x1 = x;
long long x2 = 0;
while (x1)
{
x2 = x2 * 10 + x1 % 10;
x1 /= 10;
}
if (x2 == x)
return true;
return false;
}
};
11. 盛最多水的容器
11. 盛最多水的容器
给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器。
示例 1：
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
c++写两个for循环超时
class Solution
{
public:
int maxArea(vector& height)
{
int left = 0;
int right = height.size() - 1;
int max = INT_MIN;
for (int i = 0; i < right; i++)
{
for (int j = i + 1; j <= right; j++)
{
int min = height[i] > height[j] ? height[j] : height[i];
max = fmax(max, min * (j - i));
}
}
return max;
}
};
双指针法:总是移动较小的那端
容纳的水量 = 两个指针指向的数字中较小值 ∗ 指针之间的距离
核心在于：如果移动较大端，y->y1，当y1>y时，计算容量时取的两端最小值x依然不会变，并且二者间距变小，容量变小；y1<=y时，容量必然变小，所以移动较小端；
也就是说：我们排除掉了较小段的这根柱子，以它为边界的容量在之后只会比当前少，不会比当前多
class Solution
{
public:
int maxArea(vector& height)
{
int left = 0;
int right = height.size() - 1;
int max = INT_MIN;
while(left
12. 整数转罗马数字
12. 整数转罗马数字
罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
- I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
- X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
- C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给你一个整数，将其转为罗马数字。
示例 1:
输入: num = 3
输出: “III”
非常简单的if…else…
把特殊情况都考虑进去就可以
class Solution
{
public:
string intToRoman(int num)
{
string s;
while (num)
{
if (num >= 1000)
{
s.push_back('M');
num -= 1000;
}
else if (num >= 900)
{
s.append("CM");
num -= 900;
}
else if (num >= 500)
{
s.push_back('D');
num -= 500;
}
else if (num >= 400)
{
s.append("CD");
num -= 400;
}
else if (num >= 100)
{
s.push_back('C');
num -= 100;
}
else if (num >= 90)
{
s.append("XC");
num -= 90;
}
else if (num >= 50)
{
s.push_back('L');
num -= 50;
}
else if (num >= 40)
{
s.append("XL");
num -= 40;
}
else if (num >= 10)
{
s.push_back('X');
num -= 10;
}
else if (num >= 9)
{
s.append("IX");
num -= 9;
}
else if (num >= 5)
{
s.push_back('V');
num -= 5;
}
else if (num >= 4)
{
s.append("IV");
num -= 4;
}
else if (num >= 1)
{
s.push_back('I');
num -= 1;
}
}
return s;
}
};
13. 罗马数字转整数
13. 罗马数字转整数
写个switch…case…用来累加，之后再判断6中特殊情况，注意是-2，-20，-200，而不是-1，-10，-100，因为在之前累加的时候多加了一次！！！
class Solution
{
public:
int num(char s)
{
int a;
switch (s)
{
case 'I':a = 1; break;
case 'V':a = 5; break;
case 'X':a = 10; break;
case 'L':a = 50; break;
case 'C':a = 100; break;
case 'D':a = 500; break;
case 'M':a = 1000; break;
}
return a;
}
int romanToInt(string s)
{
int sum = 0;
for (auto n : s)
{
sum += num(n);
}
for (int i = 0; i < s.size() - 1; i++)
{
if (s[i] == 'I' && (s[i + 1] == 'V' || s[i + 1] == 'X'))
sum -= 2;
else if (s[i] == 'X' && (s[i + 1] == 'L' || s[i + 1] == 'C'))
sum -= 20;
else if (s[i] == 'C' && (s[i + 1] == 'D' || s[i + 1] == 'M'))
sum -= 200;
}
return sum;
}
};
14. 最长公共前缀
14. 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。
示例 1：
输入：strs = [“flower”,“flow”,“flight”]
输出：“fl”
写一个返回值为string类型的longest函数，用来返回两个字符串之间的公共前缀
在longestCommonPrefix函数中进行遍历，s用来保存目前最短的公共前缀，s1保存相邻字符串的公共前缀，最后返回s即可
class Solution
{
public:
string longest(string a, string b)
{
string s;
for (int i = 0; i < a.length(); i++)
{
if (a[i] == b[i])
s.push_back(a[i]);
else
break;
}
return s;
}
string longestCommonPrefix(vector& strs)
{
if (strs.size() == 1)
return strs[0];
string s;
string s1;
for (int i = 0; i < strs.size()-1; i++)
{
if(i==0)
s= longest(strs[i], strs[i + 1]);
else
{
s1 = longest(strs[i], strs[i + 1]);
s = s
15. 三数之和
15. 三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
好长的代码
排序，固定i，如果nums[i]>0,退出循环，令left=i+1，right=nums.size()-1,遍历查找nums[i]+nums[left]+nums[right]==0的数组
注意：重复数组的情况
- i > 0 && nums[i] == nums[i - 1] 时contine
- sum == 0时，判断nums[left]与nums[left+1]，nums[right]与nums[right - 1]的情况
class Solution
{
public:
vector> threeSum(vector& nums)
{
vector>arr;
if (nums.size() < 3)
{
return arr;
}
sort(nums.begin(), nums.end());
int left;
int right;
int sum;
for (int i = 0; i < nums.size(); i++)
{
if (nums[i] > 0)
break;
if (i > 0 && nums[i] == nums[i - 1])
{
continue;
}
left = i + 1;
right = nums.size() - 1;
while (left < right)
{
sum = nums[i] + nums[left] + nums[right];
if (sum == 0)
{
arr.push_back({ nums[i],nums[left],nums[right] });
while (left < right && nums[left] == nums[left + 1])
{
left++;
}
while (left < right && nums[right] == nums[right - 1])
{
right--;
}
left++;
right--;
}
else if (sum > 0)
{
right--;
}
else
{
left++;
}
}
}
return arr;
}
};
16. 最接近的三数之和
16. 最接近的三数之和
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。
示例 1：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
和上一题思路基本上是一样的，在最接近target这块，新设了mina和minb分别保存abs(sum-target)、sum,当abs(sum-target)
class Solution
{
public:
int threeSumClosest(vector& nums, int target)
{
if (nums.size() == 3)
{
return nums[0] + nums[1] + nums[2];
}
sort(nums.begin(), nums.end());
int mina= INT_MAX, minb=INT_MAX;
int left, right, sum;
for (int i = 0; i < nums.size(); i++)
{
left = i + 1;
right = nums.size() - 1;
while (left < right)
{
sum = nums[i] + nums[left] + nums[right];
if (sum == target)
{
return target;
}
else if (sum < target)
{
if (target-sum < mina)
{
mina = target - sum;
minb = sum;
}
left++;
}
else
{
if (sum- target < mina)
{
mina = sum - target;
minb = sum;
}
right--;
}
}
}
return minb;
}
};
19. 删除链表的倒数第 N 个结点
19. 删除链表的倒数第 N 个结点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
写链表、二叉树这类给了初始化的习题时，一定要自己实现一下初始化过程！！不然面试笔试会吃亏
初始化的C实现
struct ListNode
{
int val;
struct ListNode* next;
};
初始化的C++实现
struct ListNode
{
int val;
ListNode* next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode* next) : val(x), next(next) {}
};
先遍历一遍求出链表长度len，n=len-n，将n变为正序的顺序
分为两种情况，新n==0时，直接令head=head->next； return head； 即可
另一种 i从0开始遍历，当i+1==n时，跳过该节点的下个节点即可
class Solution
{
public:
ListNode* removeNthFromEnd(ListNode* head, int n)
{
int len = 0;
for (ListNode* p = head; p != NULL; p = p->next)
{
len++;
}
n = len - n;
if (n==0)
{
head = head->next;
return head;
}
int i = 0;
for (ListNode* p = head; p != NULL; p = p->next)
{
if (i + 1 == n)
{
ListNode* q = p->next;
p->next = q->next;
break;
}
i++;
}
return head;
}
};
70. 爬楼梯
70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶
dp[i]： 爬到第i层楼梯，有dp[i]种方法
因为n是一个正整数，所以不需考虑0的情况，初始化：n=1有一种，n=2有两种
当i>=3时，从dp[i]可以看出，dp[i] 可以有两个方向推出
（1）dp[i - 1]，上i-1层楼梯，有dp[i - 1]种方法，那么再一步跳一个台阶就是dp[i]
（2）dp[i - 2]，上i-2层楼梯，有dp[i - 2]种方法，那么再一步跳两个台阶就是dp[i]
所以dp[i] = dp[i - 1] + dp[i - 2]
class Solution
{
public:
int climbStairs(int n)
{
if(n<3)
return n;
vectordp(n+1);
dp[1]=1;
dp[2]=2;
for(int i=3;i<=n;i++)
{
dp[i]=dp[i-1]+dp[i-2];
}
return dp[n];
}
};
300. 最长递增子序列
300. 最长递增子序列
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
class Solution
{
public:
int lengthOfLIS(vector& nums)
{
vector dp(nums.size(), 1);
int min;
for (int i = 1; i < nums.size(); i++)
{
for (int j = 0; j < i; j++)
{
if ((nums[i] > nums[j]))
{
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
return *max_element(dp.begin(), dp.end());
}
};
