第1章：LeetCode--基础部分

第1章：LeetCode--基础部分

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;
    }

 

原文链接:https://www.cnblogs.com/feliz/p/11424903.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有