leetcode easy problem set
分类:
IT文章
•
2025-01-06 11:00:13
*勿以浮沙筑高台*
持续更新........ 题目网址：https://leetcode.com/problemset/all/?difficulty=Easy
1. Two Sum [4ms]
2. Reverse Integer [12ms]
题意：将一个32bit signed integer反转输出，如果反转之后超出32位补码范围 [-2^31,2^31-1]，则输出0
思路：边取模边算结果，结果存longlong判界
3. Palindrome Number [112ms]
题意：判断数字回文，且不要将数字转为字符串
思路：和第2题一样，非负反转判等
4. Roman to Integer [52ms]
题意：罗马数字串转为数字
方法：字符串hash
![]()
class Solution {
private:
int case_(int ch)
{
switch (ch)
{
case 'I': return 1;
case 'V': return 5;
case 'X': return 10;
case 'L': return 50;
case 'C': return 100;
case 'D': return 500;
case 'M': return 1000;
case 'I' * 55 + 'V': return 4;
case 'I' * 55 + 'X': return 9;
case 'X' * 55 + 'L': return 40;
case 'X' * 55 + 'C': return 90;
case 'C' * 55 + 'D': return 400;
case 'C' * 55 + 'M': return 900;
default:return 0;
}
}
public:
int romanToInt(string str) {
register int x = 0, i;
for (i = 1; i < str.size(); ++i)
{
register int t = case_(str[i - 1] * 55 + str[i]);
if (t)x += t, i++;
else
x += case_(str[i-1]);
}
if (i == str.size())x += case_(str[i - 1]);
return x;
}
};
View Code
5. Longest Common Prefix [4ms]
题意：一个字符串数组中所有元素的最长公共前缀
思路：暴力，注意数组可能为空，可能数组只含有一个空串
6. Valid Parentheses [4ms]
题意：括号合法匹配
方法：栈基本操作
class Solution {
public:
bool isValid(string s) {
char arr[10006] = { '#' };
unordered_map<char, char> P{ {'(',')'},{'{','}'},{'[',']'} };
int index = 1;
for (auto i : s)
{
if (i != P[arr[index - 1]])arr[index++] = i;
else index--;
}
return index == 1;
}
};
7. Merge Two Sorted Lists [8ms]
题意：合并两个已序链表
方法：模拟
![]()
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (!l1)return l2;
if (!l2)return l1;
ListNode* res, *cur, *newNode;
if (l1->val < l2->val)
{
res = new ListNode(l1->val);
res->next = NULL;
l1 = l1->next;
}
else
{
res = new ListNode(l2->val);
res->next = NULL;
l2 = l2->next;
}
cur = res;
while (l1 != NULL && l2 != NULL)
{
if (l1->val < l2->val)
{
newNode = new ListNode(l1->val);
newNode->next = NULL;
cur->next = newNode;
l1 = l1->next;
}
else
{
newNode = new ListNode(l2->val);
newNode->next = NULL;
cur->next = newNode;
l2 = l2->next;
}
cur = cur->next;
}
while (l1 != NULL)
{
newNode = new ListNode(l1->val);
newNode->next = NULL;
cur->next = newNode;
l1 = l1->next;
cur = cur->next;
}
while (l2 != NULL)
{
newNode = new ListNode(l2->val);
newNode->next = NULL;
cur->next = newNode;
l2 = l2->next;
cur = cur->next;
}
return res;
}
};
View Code
8. Remove Duplicates from Sorted Array [16ms]
题意：序列去重
.· 方法：STL-unique
9. Remove Element [4ms]
题意：移除序列中指定元素
方法：STL-remove_if
10. Implement strStr() [4ms]
题意：返回b串在a串中出现的首位置
方法：KMP
![]()
class Solution {
int next[100006];
void GetNext(string p) {
next[0] = -1;
int k = -1;
for (int q = 1; q <= (int)p.size() - 1; q++)
{
while (k > -1 && p[k + 1] != p[q])
k = next[k];
if (p[k + 1] == p[q])
k = k + 1;
next[q] = k;
}
}
public:
int strStr(string s, string p) {
if (p.empty())return 0;
GetNext(p);
register int i = 0, j = 0;
int k = -1;
for (int i = 0; i < s.size(); i++)
{
while (k >-1 && p[k + 1] != s[i])
k = next[k];
if (p[k + 1] == s[i])
k = k + 1;
if (k == p.size() - 1)
return i - p.size() +1;
}
return -1;
}
};
View Code
11. Divide Two Integers [12ms]
题意：两个32bit signed int 做除法，如果结果越界那么输出2^31-1
方法：存longlong，然后判界输出
12. Search Insert Position [4ms]
题意：已序序列中找一个数，如果存在，返回index，如果不存在返回插入后使序列仍有序的插入位置
方法：STL-lower_bound
13. Maximum Subarray [8ms]
题意：给定一个数字串，找出其中各个数字相加之和最大的一个子串，输出最大和。
方法：dp[ ]，dp[i]代表前 i 位的最优解，则转移方程为 dp[i] = max(dp[i] + nums[i], nums[i]);
14.Length of Last Word [4ms]
题意：给定一个字符串，里面的空格符将之分割为（0个或一个或）多个子字符串，求最后一个子串的长度
方法：利用字符串流将其顺序读出，返回长度
15. Plus One [0 ms]
题意：给定一个数组，这个数组代表一个数，比如【1,2,3】：123，让代表的数+1，然后返回新的数组，比如：【1,2,4】
解法：从后往前数，第一个不是9的数，让其+1，是9的，变为0
16. Add Binary [4ms]
题意：两个二进制字符串相加
方法：先反转两个字符串，使得低位对齐，然后遍历，进位标记做好即可
![]()
class Solution {
public:
string addBinary(string a, string b) {
string c = "";
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
int siz = min(a.size(), b.size()), key = 0, i;
for (i = 0; i < siz; ++i)
{
if (a[i] != b[i]) key ? c += '0' : c += '1';
else
{
if (key) c += '1', key = false;
else c += '0';
if (a[i] == '1')key++;
}
}
auto fun = [&](string& a) {
if (a.size() - siz)
{
if (key)
for (i = siz; i < a.size(); ++i)
if (a[i] == '1')c += '0';
else
{
a[i] = '1';
key = false;
break;
}
if (key)c += '1', key = false;
else c += string(a.begin() + i, a.end());
}
};
fun(a);
fun(b);
if (key)c += '1';
reverse(c.begin(), c.end());
return c;
}
};
View Code
class Solution {
vector<int> left,right;
public:
void trans(TreeNode* root, bool ispre)
{
if(root == NULL)
{
if(ispre)left.push_back(0);
else right.push_back(0);
return;
}
if(ispre)left.push_back(root->val);
else right.push_back(root->val);
if(ispre)trans(root->left, ispre);
trans(root->right, ispre);
if(!ispre)trans(root->left, ispre);
}
bool isSymmetric(TreeNode* root) {
if(root == NULL)return true;
trans(root,true);
trans(root,false);
return left == right;
}
};
