第1章：LeetCode--基础部分
2024-08-22 22:38:37
LeetCode刷题指导（不能只实现功能就行需要尽量写最优解）：
不可能刷遍所有题，只能通过刷题来恢复写代码的功力，熟悉常用算法(暴力算法、冒泡排序/快速排序、strStr KMP算法、二叉树遍历DFS/BFS算法、二叉树前序遍历/中序遍历/后序遍历算法)，以及一些常考题目(链表反转、快慢指针、链表插入删除)等。
可以先看TOP100里面的easy和medium的（本篇基础部分(1)），然后再按数组、链表、字符串类刷easy和medium的（参看后续篇章），大概刷完4,50道题后，要把题目归类总结，打印出来，经常看。
下面有一些刷题顺序的例子也可以参考：https://blog.csdn.net/love1055259415/article/details/80981337
#include <map>
#include <iostream>
#include <string>
#include <stack>
#include <queque>
using namespace std; //1.two-sum
//C
int* twoSum(int* nums, int numSize, int target, int* returnSize){
for(int i=; i<numSize; i++){
for(int j=i+; j<numSize; j++){
if(target-numSize(i) == nums[j]){
*returnSize = ;
int* ret = (int*)malloc(*sizeof(int));
ret[] = i;
ret[] = j;
return ret;
}
}
}
*returnSize = ;
return NULL;
}
//C++
vector<int> twoSum(vector<int>& nums, int target){
unordered_map<int, int> mymap;
for(int i=; i<nums.size(); i++){
if(mymap.find(target-nums[i]) != mymap.end())
return {mymap[target – nums[i]], i};
mymap[nums[i]] = i;
}
return {};
} // 2. Add Two Numbers
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
int sum=, carry=;
ListNode *ret, *tmp, *p=l1, *q=l2;
ret = tmp = new ListNode();
while (carry || p || q){ //如果没有carry, [5] /[5] 时就会得[0,0]
sum = carry;
if(p)
sum += p->val;
if(q)
sum += q->val;
tmp->val = sum%;
carry = sum/;
p = (p && p->next)? p->next : NULL; //如果不判断[1,8] / [0] 会出错
q = (q && q->next)? q->next : NULL;
if( !carry && !p && !q) break;//如果没有这个[7,0,8,0]
tmp->next = new ListNode();
tmp = tmp->next;
}
return ret;
}
}; //3. Longest Substring Without Repeating Characters
class Solution { //abcdabcef
public:
int lengthOfLongestSubstring(string s) {
vector<int> dict(, -);
int maxLen = , start = -;
for (int i = ; i < s.length(); i++) {
if (dict[s[i]] > start) //重复出现了字符，更改start位置
start = dict[s[i]];
dict[s[i]] = i; //更新字符对应的下标
maxLen = max(maxLen, i - start ); //返回最大值i-start
}
return maxLen;
}
}; //4.Median of two sorted Arrays
double findMedianSortedArrays(vector<int>& num1, vector<int>& num2){
vector<int> nums(nums1);
nums.insert(nums.end(), num2.begin(), num2.end());
sort(nums.begin(), nums.end());
int size = nums.size();
if(size% == )
return (nums[size/-]+nums[size/])/2.0; //(nums[size/2-1]+nums(size/2))/2. will not get xx.5
else
return nums[size/];
}
//A[i] B[j], i+j=(n+m+1)/2 Dont use STL, find the (m+n)/2 data:
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size();
int n = nums2.size();
int p1=, p2=;
int count=, loop=(m+n)/+;
int value=, pre=;
while(true){
value = ;
if(p1<m && p2<n){
if(nums1[p1]<nums2[p2])
value = nums1[p1++];
else
value = nums2[p2++];
}else if(p1>=m && p2<n){
value = nums2[p2++];
}else if(p1<m && p2>=n){
value = nums1[p1++];
}else
break;
count++;
if(count == loop){
if((m+n)%)
return value;
else
return (pre+value)/2.0;
}
pre = value;
}
return ;
}
}; // 5. Longest Palindromic Substring “abbab” ->abba
string longestPalindrome(string s){
int len = s.size();
for(int sublen=len; sublen>; sublen--){ //可能的最大串长度
int i=, j=; //开始判断是否有这么长的palindromic串
while(i+sublen<=len){
j = ;
int loop = sublen/;
while(j<loop){
if(s[i+j] != s[i+sublen--j]) //sublen长的串从最两端向里判断
break;
j++;
}
if(j == loop) return s.substr(i,sublen);
i+=; //没找到，前进一个字符
}
}
return s;
} // 6. ZigZag Conversion字母变成|/|/|/这种排列
class Solution {
public:
string convert(string s, int numRows) {
vector< vector<char> > str(numRows); //must give the lines, or Line 933: Char 34: runtime error: reference binding to null pointer
if(s.size()<) return s;
if(numRows<) return s;
int strLen = s.size(), curr=;
string rets="";
while(curr<strLen){
for(int i=; i<numRows; i++){ //”|“/ fill the colume
if(curr<strLen)
str[i].push_back(s[curr++]);
else
break;
}
for(int i=numRows-; i>; i--){ // |”/” fill the other lines
if(curr<strLen)
str[i].push_back(s[curr++]);
else
break;
}
}
int i=;
while(i<numRows){
for(int j=; j<str[i].size(); j++)
rets += str[i][j];
i++;
}
return rets;
}
}; // 7. Reverse Integer 123-321 -123 -321 120 12
int reverse(int x){
Int ret=, div=;
while(x){
div = x%;
x = x/;
ret = ret* + div;
}
return ret;
} // 8. String to Integer (atoi)
class Solution {
public:
int myAtoi(string str) {
if(str.empty()) return ;
long retValue = , j=, minusFlag=, index=, terminal=; while(str[j]){
switch(str[j]){
case ' ':
if(terminal) return retValue;
break;
case '+':
if(terminal) return retValue;
if(++index > ) return ;
terminal =;
minusFlag=;
break;
case '-':
if(terminal) return retValue;
if(++index > ) return ;
terminal =;
minusFlag=-;
break;
case '':
case '':
case '':
case '':
case '':
case '':
case '':
case '':
case '':
case '':
terminal =;
retValue = retValue* + minusFlag*((str[j]-''));
if(retValue<INT_MIN) return INT_MIN;
if(retValue>INT_MAX) return INT_MAX;
break;
default:
return retValue;
}
j++;
}
return retValue;
}
}; // 9. Palindrome Number 回文
int revert(int x){
Int ret = ;
while(x){
If(abs(ret)>INT_MAX/) return ;
ret = ret*+x%;
x=x/;
}
return ret;
}
bool isPalindrome(int x){
if(x<) return false;
int reverse = ;
reverse = revert(x);
if(reverse == x)
return true;
else
return false;
} // 13. Roman to Integer
Symbol Value
I
V
X
L
C
D
M
• I can be placed before V () and X () to make and .
• X can be placed before L () and C () to make and .
• C can be placed before D () and M () to make and .
class Solution {
public:
int romanToInt(string s) {
int ret=;
char *p =&s[];
while(*p)
{
switch (*p){
case 'I':
if(*(p+) == 'V')
{
ret += ;
*p++;
}
else if(*(p+) == 'X')
{
ret += ;
*p++;
}
else
ret += ;
break;
case 'V':
ret += ;
break;
case 'X':
if(*(p+) == 'L')
{
ret += ;
*p++;
}
else if(*(p+) == 'C')
{
ret += ;
*p++;
}
else
ret += ;
break;
case 'L':
ret += ;
break;
case 'C':
if(*(p+) == 'D')
{
ret += ;
*p++;
}
else if(*(p+) == 'M')
{
ret += ;
*p++;
}
else
ret += ;
break;
case 'D':
ret += ;
break;
case 'M':
ret += ;
break;
default:
break;
}
p=p+;
}
return ret;
}
}; // 14. Longest Common Prefix
string longestCommonPrefix(vector<string>& strs){
if(strs.empty())return “”;
string rets = “”;
for(int i=; i<strs[].size();i++){
for(int j=; j<strs.size();j++){
if(strs[][i] != strs[j][i])
return rets;
}
rets += strs[][i];
}
return rets;
}
/////////////////////////
/*if(strs.empty()) return "";
for(int idx = 0; strs[0][idx] != '\0'; ++idx)
{
for(auto& str : strs )
if(str[idx] != strs[0][idx]) return strs[0].substr(0,idx);
}
return strs[0];*/
///////////////////////// //15. 3Sum
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ret;
std::sort(nums.begin(), nums.end()); // Sort the nums
int size = nums.size(), a, b, c, front, end;
for(int i = ; i<size-; i++){
a = nums[i];
front = i+;
end = size-;
while(front < end){
if(nums[front]+nums[end]+a < )
front++;
else if(nums[front]+nums[end]+a > )
end--;
else{
vector<int> elem({a, nums[front], nums[end]});
ret.push_back(elem);
while(front<end && nums[front]==elem[]) front++;//remove the duplicated nums.
while(front<end && nums[end]==elem[]) end--;//remove the duplicated nums.
}
}
// Processing duplicates of Numbers
while (i + < nums.size() && nums[i + ] == nums[i])
i++;
}
return ret;
} // 20. Valid Parentheses '(', ')', '{', '}', '[' and ']' , determine if the input string is valid.
bool isValid(string s) {
vector<char> OpStr;
int len = s.length();
char ee;
for(int i=; i<len; i++){
switch (s[i]){
case '(':
case '[':
case '{':
OpStr.push_back(s[i]);
break;
case ')':
if(OpStr.empty()) return false;
ee = OpStr.back();
if(ee == '(')
OpStr.pop_back();
else
return false;
break;
case ']':
if(OpStr.empty()) return false;
ee = *(OpStr.end()-);
if(ee == '[')
OpStr.pop_back();
else
return false;
break;
case '}':
if(OpStr.empty()) return false;
ee = *(OpStr.rbegin());
if(ee == '{')
OpStr.pop_back();
else
return false;
break;
default:
return false;
}
}
if(OpStr.empty())
return true;
else
return false;
} // 21. Merge Two Sorted Lists
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(!l1) return l2;
if(!l2) return l1;
ListNode *head, *retList; if(l1->val <l2->val){
retList = head = l1;
l1 = l1->next;
}
else{
retList = head = l2;
l2 = l2->next;
} while(l1 && l2){
if(l1->val <l2->val){
head->next = l1;
l1 = l1->next;
head = head->next;
head->next = NULL;
}
else{
head->next = l2;
l2 = l2->next;
head = head->next;
head->next = NULL;
}
}
if(!l1) head->next = l2;
if(!l2) head->next = l1;
return retList;
} // 26. Remove Duplicates from Sorted Array [1,1,2],
int removeDuplicates(vector<int>& nums) {
if(nums.empty()) return ;
int i=, j=, size = nums.size();
for( ;j<size; j++){
if(nums[i] != nums[j])
nums[++i] = nums[j];
}
return i+;
}
int removeDuplicates(vector<int>& nums) {
if(nums.empty()) return ;
vector<int>::iterator it;
for(it=nums.begin(); it<nums.end()-; it++){
if(*it == *(it+)){
nums.erase(it--);
}
}
return nums.size();
} // 27. Remove Element [0,1,2,2,3,0,4,2], val = 2, return length = 5: 0, 1, 3, 0, and 4.
int removeElement(vector<int>& nums, int val) {
if(nums.empty()) return ;
int i=, j=;
for(int j=; j<nums.size(); j++){
if(nums[j] != val)
nums[i++] = nums[j];
}
return i;
}
int removeElement(vector<int>& nums, int val) {
if(nums.empty()) return ;
vector<int>::iterator it;
for(it=nums.begin(); it<nums.end(); it++){
if(*it == val)
nums.erase(it--);
}
return nums.size();
} // 28. Implement strStr() 参考KMP算法 // 35. Search Insert Position Input: [1,3,5,6], 5 Output: 2
int searchInsert(vector<int>& nums, int target) {
int size = nums.size(), i=;
for(; i<size; i++){
if(nums[i] <target)
continue;
if(nums[i] >= target)
return i;
}
return i;
} // 38. Count and Say
.
.
.
.
.
string countAndSay(int n) {
string res, tmp;
if (n == ) return "";
while (n>){
int count = ;
res = countAndSay(--n);
tmp = "";
for (int i = ; i<res.size(); i++){
if (res[i] == res[i + ]) count++;
else{
tmp += to_string(count) + res[i];
count = ;
}
}
return tmp;
}
return tmp;
}
string countAndSay(int n) {
if(n == )return "";
string ret="", s1 = "", currS= s1;
int count = ;
for(int i=; i<=n; i++){
ret = "";
for(int j=; j<currS.size(); j++){ if(currS[j] == currS[j+]) count++;
else{
ret += to_string(count) + currS[j];
count = ;
}
}
count = ;
currS = ret; }
return ret;
} // 56. Merge Intervals
Input: [[,],[,],[,],[,]]
Output: [[,],[,],[,]]
vector<vector<int>> merge(vector<vector<int>>& intervals){
int len = intervals.size();
if(len<) return intervals; //len=0,1 return
sort(intervals.begin(), intervals.end());
int j = ;
vector<vector<int>> ret;
ret.push_back(intervals[]);
for(;j<len;j++){
if(ret.back()[]<intervals[j][])
ret.push_back(intervals[j]);
else
if(ret.back()[]<intervals[j][])
ret.back()[]=intervals[j][];
}
return ret;
} // 57. Insert Interval
Input: intervals = [[,],[,]], newInterval = [,]
Output: [[,],[,]]
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
vector<vector<int>> ret, merged(intervals);
if(!newInterval.empty()) merged.push_back(newInterval);
sort(merged.begin(), merged.end());
int len = merged.size();
if(len<=) return merged;
ret.push_back(merged[]);
for(int j=; j<len; j++){
if(ret.back()[]<merged[j][])
ret.push_back(merged[j]);
else
ret.back()[] = max(ret.back()[],merged[j][]);
}
return ret;
}
最新文章
- APP开发：对于IOS APP应用的推广渠道有哪些？
- 转载分享----一线交付眼中的为何"项目总是迟迟无法交付”
- 【java】：多表关联、排序
- 分享一些App常用的模块
- 博弈的SG函数理解及模板
- 遍历并修改dictionary的值
- vim plugin 原理
- Educational Codeforces Round 9
- 浅析Java中的final关键字（转）
- SQLalchemy模块用法
- node.js零基础详细教程(4)：node.js事件机制、node异步IO操作
- Unrooted Tests错误
- python的eval函数
- 老男孩Python全栈开发（92天全）视频教程 自学笔记04
- ABP PUT、DELETE请求错误405.0 - Method Not Allowed 因为使用了无效方法(HTTP 谓词) 引发客户端错误 No 'Access-Control-Allow-Origin' header is present on the requested resource
- 【转】Linux从入门到精通——运维工程师成长路线图——CTO马哥Linux视频教学
- 2小时学会Spring Boot（IDE：eclipse）
- PEP8规范
- 用原生js来处理跨域的数据（jsonp）
- curl工具介绍和常用命令