我要评论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=0; i<numsize; i++){
for(int j=i+1; j<numsize; j++){
if(target-numsize(i) == nums[j]){
*returnsize = 2;
int* ret = (int*)malloc(2*sizeof(int));
ret[0] = i;
ret[1] = j;
return ret;
}
}
}
*returnsize = 0;
return null;
}
//c++
vector<int> twosum(vector<int>& nums, int target){
unordered_map<int, int> mymap;
for(int i=0; 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=0, carry=0;
listnode *ret, *tmp, *p=l1, *q=l2;
ret = tmp = new listnode(0);
while (carry || p || q){ //如果没有carry, [5] /[5] 时就会得[0,0]
sum = carry;
if(p)
sum += p->val;
if(q)
sum += q->val;
tmp->val = sum%10;
carry = sum/10;
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(0);
tmp = tmp->next;
}
return ret;
}
};
//3. longest substring without repeating characters
class solution { //abcdabcef
public:
int lengthoflongestsubstring(string s) {
vector<int> dict(256, -1);
int maxlen = 0, start = -1;
for (int i = 0; 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%2 == 0)
return (nums[size/2-1]+nums[size/2])/2.0; //(nums[size/2-1]+nums(size/2))/2. will not get xx.5
else
return nums[size/2];
}
//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=0, p2=0;
int count=0, loop=(m+n)/2+1;
int value=0, pre=0;
while(true){
value = 0;
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)%2)
return value;
else
return (pre+value)/2.0;
}
pre = value;
}
return 0;
}
};
// 5. longest palindromic substring “abbab” ->abba
string longestpalindrome(string s){
int len = s.size();
for(int sublen=len; sublen>0; sublen--){ //可能的最大串长度
int i=0, j=0; //开始判断是否有这么长的palindromic串
while(i+sublen<=len){
j = 0;
int loop = sublen/2;
while(j<loop){
if(s[i+j] != s[i+sublen-1-j]) //sublen长的串从最两端向里判断
break;
j++;
}
if(j == loop) return s.substr(i,sublen);
i+=1; //没找到，前进一个字符
}
}
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()<2) return s;
if(numrows<2) return s;
int strlen = s.size(), curr=0;
string rets="";
while(curr<strlen){
for(int i=0; i<numrows; i++){ //”|“/ fill the colume
if(curr<strlen)
str[i].push_back(s[curr++]);
else
break;
}
for(int i=numrows-2; i>0; i--){ // |”/” fill the other lines
if(curr<strlen)
str[i].push_back(s[curr++]);
else
break;
}
}
int i=0;
while(i<numrows){
for(int j=0; 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=0, div=0;
while(x){
div = x%10;
x = x/10;
ret = ret*10 + div;
}
return ret;
}
// 8. string to integer (atoi)
class solution {
public:
int myatoi(string str) {
if(str.empty()) return 0;
long retvalue = 0, j=0, minusflag=1, index=0, terminal=0;
while(str[j]){
switch(str[j]){
case ' ':
if(terminal) return retvalue;
break;
case '+':
if(terminal) return retvalue;
if(++index > 1) return 0;
terminal =1;
minusflag=1;
break;
case '-':
if(terminal) return retvalue;
if(++index > 1) return 0;
terminal =1;
minusflag=-1;
break;
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
terminal =1;
retvalue = retvalue*10 + minusflag*((str[j]-'0'));
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 = 0;
while(x){
if(abs(ret)>int_max/10) return 0;
ret = ret*10+x%10;
x=x/10;
}
return ret;
}
bool ispalindrome(int x){
if(x<0) return false;
int reverse = 0;
reverse = revert(x);
if(reverse == x)
return true;
else
return false;
}
// 13. roman to integer
symbol value
i 1
v 5
x 10
l 50
c 100
d 500
m 1000
• i can be placed before v (5) and x (10) to make 4 and 9.
• x can be placed before l (50) and c (100) to make 40 and 90.
• c can be placed before d (500) and m (1000) to make 400 and 900.
class solution {
public:
int romantoint(string s) {
int ret=0;
char *p =&s[0];
while(*p)
{
switch (*p){
case 'i':
if(*(p+1) == 'v')
{
ret += 4;
*p++;
}
else if(*(p+1) == 'x')
{
ret += 9;
*p++;
}
else
ret += 1;
break;
case 'v':
ret += 5;
break;
case 'x':
if(*(p+1) == 'l')
{
ret += 40;
*p++;
}
else if(*(p+1) == 'c')
{
ret += 90;
*p++;
}
else
ret += 10;
break;
case 'l':
ret += 50;
break;
case 'c':
if(*(p+1) == 'd')
{
ret += 400;
*p++;
}
else if(*(p+1) == 'm')
{
ret += 900;
*p++;
}
else
ret += 100;
break;
case 'd':
ret += 500;
break;
case 'm':
ret += 1000;
break;
default:
break;
}
p=p+1;
}
return ret;
}
};
// 14. longest common prefix
string longestcommonprefix(vector<string>& strs){
if(strs.empty())return “”;
string rets = “”;
for(int i=0; i<strs[0].size();i++){
for(int j=0; j<strs.size();j++){
if(strs[0][i] != strs[j][i])
return rets;
}
rets += strs[0][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 = 0; i<size-2; i++){
a = nums[i];
front = i+1;
end = size-1;
while(front < end){
if(nums[front]+nums[end]+a < 0)
front++;
else if(nums[front]+nums[end]+a > 0)
end--;
else{
vector<int> elem({a, nums[front], nums[end]});
ret.push_back(elem);
while(front<end && nums[front]==elem[1]) front++;//remove the duplicated nums.
while(front<end && nums[end]==elem[2]) end--;//remove the duplicated nums.
}
}
// processing duplicates of numbers
while (i + 1 < nums.size() && nums[i + 1] == 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=0; 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()-1);
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 0;
int i=0, j=1, size = nums.size();
for( ;j<size; j++){
if(nums[i] != nums[j])
nums[++i] = nums[j];
}
return i+1;
}
int removeduplicates(vector<int>& nums) {
if(nums.empty()) return 0;
vector<int>::iterator it;
for(it=nums.begin(); it<nums.end()-1; it++){
if(*it == *(it+1)){
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 0;
int i=0, j=0;
for(int j=0; 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 0;
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=0;
for(; i<size; i++){
if(nums[i] <target)
continue;
if(nums[i] >= target)
return i;
}
return i;
}
// 38. count and say
1. 1
2. 11
3. 21
4. 1211
5. 111221
string countandsay(int n) {
string res, tmp;
if (n == 1) return "1";
while (n>0){
int count = 1;
res = countandsay(--n);
tmp = "";
for (int i = 0; i<res.size(); i++){
if (res[i] == res[i + 1]) count++;
else{
tmp += to_string(count) + res[i];
count = 1;
}
}
return tmp;
}
return tmp;
}
string countandsay(int n) {
if(n == 1)return "1";
string ret="", s1 = "1", currs= s1;
int count = 1;
for(int i=2; i<=n; i++){
ret = "";
for(int j=0; j<currs.size(); j++){
if(currs[j] == currs[j+1]) count++;
else{
ret += to_string(count) + currs[j];
count = 1;
}
}
count = 1;
currs = ret;
}
return ret;
}
// 56. merge intervals
input: [[1,3],[2,6],[8,10],[15,18]]
output: [[1,6],[8,10],[15,18]]
vector<vector<int>> merge(vector<vector<int>>& intervals){
int len = intervals.size();
if(len<2) return intervals; //len=0,1 return
sort(intervals.begin(), intervals.end());
int j = 1;
vector<vector<int>> ret;
ret.push_back(intervals[0]);
for(;j<len;j++){
if(ret.back()[1]<intervals[j][0])
ret.push_back(intervals[j]);
else
if(ret.back()[1]<intervals[j][1])
ret.back()[1]=intervals[j][1];
}
return ret;
}
// 57. insert interval
input: intervals = [[1,3],[6,9]], newinterval = [2,5]
output: [[1,5],[6,9]]
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<=1) return merged;
ret.push_back(merged[0]);
for(int j=1; j<len; j++){
if(ret.back()[1]<merged[j][0])
ret.push_back(merged[j]);
else
ret.back()[1] = max(ret.back()[1],merged[j][1]);
}
return ret;
}
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请 点击进行留言回复，万千网友为您解惑！
网友评论