最长公共前缀
最长公共前缀
原题链接:https://leetcode.cn/problems/longest-common-prefix/
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串。
1.substr解法1:暴力循环 + substr字符串截取
runtime beats 73.15 % of cpp submissions
memory usage beats 27.86 % of cpp submissions (9 MB)
12345678910111213class Solution {public: string longestCommonPrefix(vector<string>& strs) { if (strs.size() == 0) return ""; string ans = strs[0]; for (int i = 1; i < strs.size(); ++i) { int index = 0; for (;index < max(strs[i].length(), ans.length()) && ans[index] == strs[i][index]; ++index); ans = strs[i].substr(0, index); } return ans; }};
2.+=操作解法2:暴力循环 + 字符串的+=操作(取消了对substr的引用,性能更优)
runtime beats 73.15 % of cpp submissions
memory usage beats 92.63 % of cpp submissions (8.8 MB)
1234567891011121314151617181920class Solution {public: string longestCommonPrefix(vector<string>& strs) { ...
罗马数字转整数
罗马数字转整数
原题链接:https://leetcode.cn/problems/roman-to-integer/
罗马数字包含以下七种字符:I, V, X, L,C,D 和 M。
12345678字符 数值I 1V 5X 10L 50C 100D 500M 1000
例如, 罗马数字 2 写做 II ,即为两个并列的 1 。12 写做 XII ,即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII 而是 IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值。同样地数字9表示为 IX。
这个特殊的规则只适用于以下六种情况:
I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边,来表示 400 和 900。
给定一个罗马数字,将其转换成整数。
1234567891011121314151617181920212223242526272829303132333435363738394041424344class Solution {public: int romanToInt(string s) { int ans = 0; for (int i = 0; i < s.length(); ++i) { if (s[i] == 'I') { //特殊判断 if (s[i + 1] == 'V' || s[i + 1] == 'X') { ans += (s[i + 1] == 'V' ...
回文数
回文数
原题链接:https://leetcode.cn/problems/palindrome-number/
给你一个整数 x ,如果 x 是一个回文整数,返回 true;否则返回 false。
回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。
提示:-231 <= x <= 231 - 1
1.整数反转利用整数反转的思想,来处理回文数字问题
12345678910111213class Solution {public: bool isPalindrome(int x) { if (x < 0) return false; long long ans = 0; long long raw = x; while (x) { ans = ans * 10 + x % 10; x /= 10; } return raw == ans; }};
2.字符串反转1234567891011121314class Solution {public: bool isPalindrome(int x) { if (x < 0) return false; string raw = to_string(x); string ans = raw; for (int i = 0, j = raw.length() - 1; i < j; ++i, --j) { char c = ans[i]; ans[i] = ans[j]; ans[j] = c; } return raw == ans; }};
整数反转
整数反转
原题链接:https://leetcode.cn/problems/reverse-integer/
给你一个 32 位的有符号整数 x ,返回其数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ,就返回 0。
假设环境不允许存储 64 位整数(有符号或无符号)(只允许使用int类型的变量)
提示:-231 <= x <= 231 - 1
1234input:120output:21input:0output:0
123456789101112131415161718class Solution {public: int reverse(int x) { int ans = 0; while (x) { if (ans > INT_MAX / 10 || ans < INT_MIN / 10 || ans == INT_MAX / 10 && x % 10 > 7 || ans == INT_MIN / 10 && x % 10 < -8 ) { ans = 0; break; } ans = ans * 10 + x % 10; x /= 10; } return ans; }};
两数之和
两数之和
原题链接:https://leetcode.cn/problems/two-sum/
给定一个整数数组nums和一个整数目标值target,请你在该数组中找出和为目标值target的那两个整数,并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
1.暴力法1234567891011121314class Solution {public: vector<int> twoSum(vector<int>& nums, int target) { int i, j; for (i = 0; i < nums.size(); ++i) { for (j = i + 1; j < nums.size(); ++j) { if (nums[i] + nums[j] == target) { return {i, j}; } } } return {i, j}; }};
2.二分查找思想:sort排序 + 二分查找
使用for循环遍历数组中的每一个数字
在for循环内部,使用target值减去当前遍历的数字值获取配对值ret,使用二分查找该数字ret
如果找到该数字则直接输出其下标(初始若有序的情况下)
实际是无序的!难点在于如何联系被sort打乱下标后的vec与未打乱的nums,并从其中找出目标数字的下标?
1234for (int j = 0; j < n; j++) { if (nums[j] == vec[i] || nums[j] == ret) result.push_back(j); if(result.size() == 2) return result;}
12345678910111213141516171819202122 ...
字符串括号匹配
字符串括号匹配
原题链接:https://oj.haizeix.com/problem/377
给出一个字符串,判断其中的左右圆括号是否匹配,
注:需同时判断左右圆括号 ( 和 ) ,左右中括号 [ 和 ],左右大括号 { 和 }
不需要考虑括号之间的优先级的问题,也就是说,小括号包含大括号,也是被允许的
输入:
一行一个字符串,以字符@为结尾
输出:
若匹配,输出 YES,若不匹配,则输出 NO
样例:
1a(cc[])bbb()@ YES
1a(cc[)]bbb()@ NO
代码1234567891011121314151617181920212223242526272829303132333435363738394041#include<iostream>#include<string>#include<stack>using namespace std;bool isValid(string str) { stack<char> stack; for (int i = 0; i < str.length(); ++i) { switch (str[i]) { case '(': case '[': case '{': stack.push(str[i]); break; case ')': if (stack.empty() || stack.top() != '(') return false; stack.pop(); break; case '}': if (stack.empty() || stack.top() != '{') return false; stack.pop(); break; case ']': if (stack.empty() || stack.top() != ...
括号画家
括号画家
原题链接:https://oj.haizeix.com/problem/265
Candela 是一名漫画家,她有一个奇特的爱好,就是在纸上画括号。
这一天,刚刚起床的 Candela 画了一排括号序列,其中包含小括号 ()、中括号 [] 和大括号 {},总长度为 N。
这排随意绘制的括号序列显得杂乱无章,于是 Candela 定义了什么样的括号序列是美观的。
1231.空的括号序列是美观的;2.若括号序列 A 是美观的,则括号序列 (A)、[A]、{A} 也是美观的;3.若括号序列 A、B 都是美观的,则括号序列 AB 也是美观的;
例如 [(){}]() 是美观的括号序列,而 )({)[}]( 则不是。
现在 Candela 想在她绘制的括号序列中找出其中连续的一段,满足这段子序列是美观的并且长度尽量大。你能帮帮她吗?
输入:
1 个长度为 N 的括号序列。(5 ≤ N ≤ 10000)
输出:
一个整数,表示最长的美观的连续子序列的长度。
样例:
1[[[[]]{}]]
110
代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include<iostream>#include<stack>#include<string>using namespace std;stack<char> stack1;stack<int> stack2;string str;int ans;void ansUpdate(int i) { stack1.pop(); stack2.pop(); ans = max(ans, i - stack2.top());}void stack12Clear(int i) { while (!stack1.empty()) { stack1.pop(); stack2.pop(); } stack1.push('#'); stack2.pus ...
仓库日志
仓库日志
原题链接:https://oj.haizeix.com/problem/379
某仓库购入新的货物并将一部分老货物发出,这个过程会有软件对数据以日志形式保存,规则如下:
该日志记录了两类操作:
第一类操作为入库操作,以及该次入库的货物数量;
第二类操作为出库操作。
这些记录都严格按时间顺序排列。入库和出库的规则为先进后出,即每次出库操作货物为当前在仓库里所有货物中最晚入库的货物。
为了便于分析,现在加入了第三类查询操作,每次查询时输出当前仓库数量最多的货物的数量。
输入:
包含 N+1行:
第一行为 1 个正整数 N,对应于日志内所含操作的总数。
接下来的 N 行,分别属于以下三种格式之一:
0 X :一次入库操作,正整数 X 表示该次入库的货物的数量
1 :一次出库操作,(就当时而言)最后入库的货物出库
2 :一次查询操作,要求分析程序输出当前仓库内数量最多的货物的数量
当仓库为空时你应该忽略出库操作,当仓库为空查询时你应该输出 0。
初始时仓库状态为空。
输出:
输出行数等于日志中查询操作的次数。每行为一个正整数,表示查询结果。
样例:
1234567891011121314130 10 220 40 221211212
1234524410
代码12345678910111213141516171819202122232425262728293031323334#include<iostream>#include<stack>using namespace std;stack<int> stack1;//存储仓库货物的数量stack<int> stack2;//存储当前仓库内数量最多的货物数量int main() { int n; cin >> n; for (int i = 0; i < n; ++i) { int x; cin >> x; switch (x) { case 0://入库操作(入栈操作) int num; cin >> num; stack1.push(num); if (stack1.size() == 1) stack2.push(num); else ...
讲话模式
讲话模式
原题链接:https://oj.haizeix.com/problem/577
每个人讲话都有口头禅,现在给出一个字符串,需要求出其中出现次数最多的单词。
输入:
输入一行,若干个长度小于或等于 10 的只包含大小写字母的字符串。
输出:
输出一行,为出现次数最多的单词和它出现的次数,以一个空格隔开。如果出现次数最多的单词有多个,则输出字典序最小的那个。这个单词必须完全以小写的形式输出。注意,所说的单词不区分大小写字母。
样例:
1Can a can can a can It can
1can 5
代码
解法1:定义两个变量string、int,轮回最终保留一个出现次数最多的结果,如果有多个则保留字典序最小的单词。
解法2:当处理完所有的数据后,遍历一遍数组保留最终的结果。
123456789101112131415161718192021222324252627282930#include<iostream>#include<map>#include<string>using namespace std;map<string, int> mp;string ans;//最终答案int count;//答案出现的次数int main() { string t; //大小写转换 while (cin >> t) { for (int i = 0; i < t.size(); ++i) { if (t[i] >= 'A' && t[i] <= 'Z') { t[i] += ('a' - 'A'); } } mp[t]++; } //数据处理 使用有序map for (auto it = mp.begin(); it != mp.end(); ++it) { if (it->second > count) { ans = it->first; count = it->second; } } cout << ...
上网统计
上网统计
原题链接:https://oj.haizeix.com/problem/566
在一个网络系统中有 N 个用户、 M 次上网记录。每个用户可以自己注册一个用户名,每个用户名只包含小写字母且长度小于 1000 的字符串,每次上网日志里都会有记录,现在请统计每个用户每次浏览了多少个网页。注意,有可能有用户没有访问记录。
输入:
第 1 行包含两个正整数 N (1 ≤ N ≤ 1000) 和 M (1 ≤ M ≤ 5000)。
第 2 ~ M+1 行,每行包含 2 个字符串,分别表示用户名和浏览的网页名。
输出:
共 x 行,x 表示有访问记录的用户数量,
每行的第一个字符串时用户名,接下来的若干字符串是这个用户依次浏览的网页名(之间用一个空格隔开)。
按照用户名出现的次序排序输出。
样例:
123456785 7goodstudyer bookshopalikespacea spacewebgoodstudyer bookshopblikespaceb spaceweblikespacec spaceweblikespacea juiceshopgameplayer gameweb
12345goodstudyer bookshopa bookshopblikespacea spaceweb juiceshoplikespaceb spaceweblikespacec spacewebgameplayer gameweb
代码12345678910111213141516171819202122232425262728293031323334353637#include<iostream>#include<string>#include<vector>#include<unordered_map>using namespace std;int cnt;//当前用户访问记录所在的行数int n;//用户的个数int recordNum;//上网记录的条数unordered_map<string, int> mp;//用于记录vector在第几行的信息(unordered_map满足按用户名出现的次序进行输出)int main() { cin >> n >> r ...