/**
 第11章 使用类
 运算符重载
 友元函数
 重载<<运算符，以便于输出
 
 ========================
 状态成员
 使用rand()生成随机值；
 类的自动转换和强制转换；主要介绍了对象直接的类型转换，比如可以把一个double类型的变量转换成对象；
 类转换函数；
 */


#ifndef LEFClass11_hpp
#define LEFClass11_hpp

#include <stdio.h>
#include <iostream>

class Time {
private:
    int hours;
    int minutes;
    
public:
    Time();
    Time(int h, int m = 0);
    void AddMin(int m);
    void AddHr(int h);
    void Reset(int h = 0, int m = 0);
    // 参数是引用，但是返回值不是引用
    Time Sum(const Time & t) const;
    /**
     重载运算符，语法为：
     operator op(参数列表)
     只能重载已经存在的运算符，比如+、-、*，而不能重载@
     Time coding(2, 40);
     Time fixing(5, 55);
     Time sum;
     也可以通过 sum = coding.operator+(fixing); 这样的方式调用；
     【规则】：
     1、必须由一个操作数是自定义类型；
     2、使用运算符时不能违反运算符原来的句法规则，也不能修改运算符的优先级，比如不能 %x；
     3、不能创建新的运算符；
     4、不能重载特点的运算符，比如：sizeof
     */
    Time operator+(const Time & t) const;
    /**
     使用非成员函数重载运算符需要两个参数，而使用成员函数重载需要一个参数，因为
     其中一个参数可以通过 this 访问。
     【使用友元函数进行重载】
     friend Time operator+(const Time & t1, const Time & t2);
     */

    Time operator-(const Time & t) const;
    // time * 1.2
    Time operator*(double n) const;
    
    /**
     友元：
     提供了一种访问私有成员的方法，我们都知道访问私有成员只能通过成员函数访问。典型的是
     非成员函数无法访问私有变量。有一种特殊的非成员函数可以访问私有变量，它们就是【友元函数】。
     1.2 * time
     */
    friend Time operator*(double m, const Time & t);
    /**
     重载符号 <<:
     cout << adjust << ", the end";
     */
    friend std::ostream & operator<<(std::ostream & os, const Time & t);

    void Show() const;
};

/**
 定义一个向量
 */
namespace VECTOR {
    class Vector {
    public:
        // 定义枚举值，在类中可以作为常量定义
        enum Mode {RECT, POL};
    private:
        double x;
        double y;
        double mag;
        double ang;
        Mode mode;
        void set_mag();
        void set_ang();
        void set_x();
        void set_y();
    public:
        Vector();
        Vector(double n1, double n2, Mode form = RECT);
        void reset(double n1, double n2, Mode form = RECT);
        ~Vector();
        /**
         下面4个函数由于在类声明中定义的，所以自动成为了内联函数
         */
        double xval() { return x;};
        double yval() { return y;};
        double magval() { return mag;};
        double angval() { return ang;};
        
        void polar_mode();
        void rect_mode();
        
        /**
         重载运算符
         */
        Vector operator+(const Vector & b) const;
        Vector operator-(const Vector & b) const;
        Vector operator-() const;
        Vector operator*(double n) const;
        friend Vector operator*(double n, const Vector & a);
        friend std::ostream & operator<<(std::ostream & os, const Vector & v);
    };
}

#endif /* LEFClass11_hpp */

#include "LEFClass11.hpp"
#include <iostream>

Time::Time() {
    hours = 0;
    minutes = 0;
}

Time::Time(int h, int m) {
    hours = h;
    minutes = m;
}

void Time::AddMin(int m) {
    minutes += m;
    hours += minutes / 60;
    minutes %= 60;
}

void Time::AddHr(int h) {
    hours += h;
}

void Time::Reset(int h, int m) {
    hours = h;
    minutes = m;
}

Time Time::Sum(const Time &t) const {
    Time sum;
    sum.minutes = minutes + t.minutes;
    sum.hours = hours + t.hours + sum.minutes / 60;
    sum.minutes %= 60;
    return sum;
}

Time Time::operator+(const Time &t) const {
    Time sum;
    sum.minutes = minutes + t.minutes;
    sum.hours = hours + t.hours + sum.minutes / 60;
    sum.minutes %= 60;
    return sum;
}

Time Time::operator-(const Time &t) const {
    Time diff;
    int tot1, tot2;
    tot1 = t.minutes + 60 * t.hours;
    tot2 = minutes + 60 * hours;
    diff.minutes = (tot2 - tot1) % 60;
    diff.hours = (tot2 - tot1) / 60;
    return diff;
}

Time Time::operator*(double n) const {
    Time result;
    int totalMin = hours * n * 60 + minutes * n;
    result.hours = totalMin / 60;
    result.minutes = totalMin % 60;
    return result;
}

Time operator*(double m, const Time & t) {
    Time result;
    // 因为是友元函数，可以访问私有成员
    int totalMin = t.hours * m * 60 + t.minutes * m;
    result.hours = totalMin / 60;
    result.minutes = totalMin % 60;
    return result;
}

std::ostream & operator<<(std::ostream & os, const Time & t) {
    os << t.hours << " hours:," << t.minutes << " sminutes";
    // 返回 os 是为了可以使用 cout << adjust << ", the end";
    return os;
}

void Time::Show() const {
    std::cout << hours << " hours:," << minutes << " minutes";
}

#include <cmath>
using std:: sqrt;
using std:: sin;
using std:: cos;
using std:: atan;
using std:: atan2;
using std:: cout;

namespace VECTOR {
    const double Rad_to_deg = 45.0 / atan(1.0);
    
    void Vector::set_mag() {
        mag = sqrt(x * x + y * y);
    }
    
    void Vector::set_ang() {
        if (x == 0.0 && y == 0.0) {
            ang = 0.0;
        } else {
            ang = atan2(y, x);
        }
    }
    
    void Vector::set_x() {
        x = mag * cos(ang);
    }
    
    void Vector::set_y() {
        y = mag * sin(ang);
    }
    
    Vector::Vector() {
        x = y = mag = ang = 0.0;
        mode = RECT;
    }
    
    Vector::Vector(double n1, double n2, Mode form) {
        mode = form;
        if (form == RECT) {
            x = n1;
            y = n2;
            set_mag();
            set_ang();
        } else if (form == POL) {
            mag = n1;
            ang = n2 / Rad_to_deg;
            set_x();
            set_y();
        } else {
            x = y = mag = ang = 0.0;
            mode = RECT;
        }
    }
    
    void Vector::reset(double n1, double n2, Mode form) {
        mode = form;
        if (form == RECT) {
            x = n1;
            y = n2;
            set_mag();
            set_ang();
        } else if (form == POL) {
            mag = n1;
            ang = n2 / Rad_to_deg;
            set_x();
            set_y();
        } else {
            x = y = mag = ang = 0.0;
            mode = RECT;
        }
    }
    
    Vector::~Vector() {
        
    }
    
    void Vector::polar_mode() {
        mode = POL;
    }
    
    void Vector::rect_mode() {
        mode = RECT;
    }
    
    Vector Vector::operator+(const Vector &b) const {
        return Vector(x + b.x, y + b.y);
    }
    
    Vector Vector::operator-(const Vector &b) const {
        return Vector(x - b.x, y - b.y);
    }
    
    Vector Vector::operator-() const {
        return Vector(-x, -y);
    }
    
    Vector Vector::operator*(double n) const {
        // 仅支持 vector * 1.2 这样的形式，不支持 1.2 * vector 这样的形式
        return Vector(n * x, n * y);
    }
    
    Vector operator*(double n, const Vector & a) {
        // 直接调用已经重载的函数，operator*
        return a * n;
    }
    
    std::ostream & operator<<(std::ostream & os, const Vector & v) {
        if (v.mode == Vector::RECT) {
            os << "RECT";
        } else if (v.mode == Vector::POL) {
            os << "POL";
        } else {
            os << "Mode is error";
        }
        return os;
    }
}

#include <stdio.h>
#include <string>

using namespace std;

/**
 【题目】
 从字符串中找到最长不重复的子字符串。
 
 【审题】
 题中要求：
 1.给的一个字符串 s
 2.找出最长不重复的子字符串，也就是说从字符串中查找没有重复的子字符串，必须连续
 
 【举例】
 Input: "abcabcbb"
 Output: 3
 Explanation: The answer is "abc", with the length of 3.
 
 Input: "bbbbb"
 Output: 1
 Explanation: The answer is "b", with the length of 1.
 
 Input: "pwwkew"
 Output: 3
 Explanation: The answer is "wke", with the length of 3.
 Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
 
 */


namespace LongestSubstring3 {
    class Solution {
    public:
        int lengthOfLongestSubstring(string s);
        int lengthOfLongestSubstring2(string s);
    };
}

#include <unordered_map>

using std::unordered_map;

namespace LongestSubstring3 {
    /**
     for(auto& v : record)
     printf("%c-%d", v.first, v.second);
     printf("\nmax: %d \n", max);
     
     printf("\ni=%d\n", i);
     
     // 好娄的算法
     Runtime: 712 ms, faster than 9.61% of C++ online submissions for Longest Substring Without Repeating Characters.
     Memory Usage: 149 MB, less than 9.61% of C++ online submissions for Longest Substring Without Repeating Characters.
     
     Runtime: 684 ms, faster than 9.87% of C++ online submissions for Longest Substring Without Repeating Characters.
     Memory Usage: 148.9 MB, less than 10.32% of C++ online submissions for Longest Substring Without Repeating Characters.
     
     【**】
     1.遍历字符串
     2.

     */
    int Solution::lengthOfLongestSubstring(string s) {
        //record用来记录遍历过的子字符串，通过它计算字符串的长度
        unordered_map<char, int> record;
        size_t len = s.size();
        int max = 0;
        for (int i = 0; i < len;) {
            char c = s[i];
//            printf("%c - %d\n", c, i);
            // "pwwkew"
            // 找到了重复的字符串，求得max
            if (record.find(c) != record.end()) {
                // 说明找到了重复的字符
                int f_index = record[c];
                int size = (int)record.size();
                max = max > size ? max : size;
                // 修改 i 的值重下一个元素开始遍历
                i = f_index+1;
                record.clear();
            } else {
                record[c] = i;
                i += 1;
            }
        }
        // 如果record中包含了字符串，需要计算它的长度
        int size = (int)record.size();
        max = max > size ? max : size;

        return max;
    }
    
    /**
     Runtime: 20 ms, faster than 97.41% of C++ online submissions for Longest Substring Without Repeating Characters.
     Memory Usage: 14.7 MB, less than 88.03% of C++ online submissions for Longest Substring Without Repeating Characters.
     
     Runtime: 20 ms, faster than 97.41% of C++ online submissions for Longest Substring Without Repeating Characters.
     Memory Usage: 14.7 MB, less than 87.06% of C++ online submissions for Longest Substring Without Repeating Characters.
     */
    int Solution::lengthOfLongestSubstring2(string s) {
        int freg[256] = {0};
        // 滑动窗口为 s[l...r]
        int l = 0, r = -1;
        int res = 0;
        while (l < s.size()) {
            if (r+1 < s.size() && freg[s[r+1]] == 0) {
                r++;
                freg[s[r]]++;
            } else {
                freg[s[l]]--;
                l++;
            }
            res = max(res, r-l+1);
        }
        return res;
    }

}

/**
 第10章 对象和类
 过程性编程和面向对象编程
 类概念
 如何定义和实现类
 公有访问和私有访问
 类方法（类成员函数）
 创建和使用对象
 类的构造函数和析构函数
 const成员函数；
 this指针；
 创建对象数组；
 类作用域；
 抽象数据类型；
 */

/**
 * 定义一个股票类，通常C++中回把接口（类定义）放到头文件中，
 * 并将实现放到源文件中。
 */
// 类定义使用关键字 class
class Stock
{
/**
 控制对成员的访问，private为私有的，company，shares等都是Stock的私有
 数据成员，如果使用非成员函数访问这些私有成员将报错。
 */
private:
    std::string company;
    long shares;
    double share_val;
    double total_val;
    void set_tot() { total_val = shares * share_val; }
public:
    /**
     默认函数，当为一个类提供了构造函数，必须提供一个默认构造函数
     隐式调用默认构造函数
     Stock stock;
     显式调用默认构造函数
     Stock stock = Stock();
     */
    Stock();
    /**
     构造函数，带有默认参数 n（shares）为0，pr（share_val）为 0.0
     1.默认参数可以省略
     Stock stock = Stock("Lefex");
     2.传递默认参数
     Stock stock4 = Stock("Lefex4", 10, 20);
     3.使用 new 关键字创建的对象需要使用 delete 移除，否则不会自动释放
     Stock *stock5 = new Stock();
     delete stock5;
     */
    Stock(const std::string & co, long n = 0, double pr = 0.0);
    /**
     析构函数，对象被销毁后将自动被调用，它主要用来做清理工作，比如通过new来
     分配内存，需要使用delete来释放内存。通常会在析构函数中使用delete来释放
     对像中的内存空间。
     */
    ~Stock();
    /**
     成员函数
     */
    void buy(long num, double price);
    void sell(long num, double price);
    void update(double price);
    void show();
    
    /**
     这个函数用来找出最大的Stock，改函数隐式地访问一个对象，
     而显式地访问另一个对象，并返回一个对象的引用。const说明：
     1、括号中的 const 表明该函数不会修改被显式访问的对象
     2、括号后的 const 表明该函数不会修改被隐式访问的对象
     3、由于返回的是两个 const 对象之一的引用，因此返回类型也为 const 类型
     */
    const Stock & topval(const Stock & s) const;
};

#endif /* LEFClass10_hpp */

#include "LEFClass11.hpp"
#include <iostream>

Time::Time() {
    hours = 0;
    minutes = 0;
}

Time::Time(int h, int m) {
    hours = h;
    minutes = m;
}

void Time::AddMin(int m) {
    minutes += m;
    hours += minutes / 60;
    minutes %= 60;
}

void Time::AddHr(int h) {
    hours += h;
}

void Time::Reset(int h, int m) {
    hours = h;
    minutes = m;
}

Time Time::Sum(const Time &t) const {
    Time sum;
    sum.minutes = minutes + t.minutes;
    sum.hours = hours + t.hours + sum.minutes / 60;
    sum.minutes %= 60;
    return sum;
}

Time Time::operator+(const Time &t) const {
    Time sum;
    sum.minutes = minutes + t.minutes;
    sum.hours = hours + t.hours + sum.minutes / 60;
    sum.minutes %= 60;
    return sum;
}

Time Time::operator-(const Time &t) const {
    Time diff;
    int tot1, tot2;
    tot1 = t.minutes + 60 * t.hours;
    tot2 = minutes + 60 * hours;
    diff.minutes = (tot2 - tot1) % 60;
    diff.hours = (tot2 - tot1) / 60;
    return diff;
}

Time Time::operator*(double n) const {
    Time result;
    int totalMin = hours * n * 60 + minutes * n;
    result.hours = totalMin / 60;
    result.minutes = totalMin % 60;
    return result;
}

Time operator*(double m, const Time & t) {
    Time result;
    // 因为是友元函数，可以访问私有成员
    int totalMin = t.hours * m * 60 + t.minutes * m;
    result.hours = totalMin / 60;
    result.minutes = totalMin % 60;
    return result;
}

std::ostream & operator<<(std::ostream & os, const Time & t) {
    os << t.hours << " hours:," << t.minutes << " sminutes";
    // 返回 os 是为了可以使用 cout << adjust << ", the end";
    return os;
}

void Time::Show() const {
    std::cout << hours << " hours:," << minutes << " minutes";
}

#include <cmath>
using std:: sqrt;
using std:: sin;
using std:: cos;
using std:: atan;
using std:: atan2;
using std:: cout;

namespace VECTOR {
    const double Rad_to_deg = 45.0 / atan(1.0);
    
    void Vector::set_mag() {
        mag = sqrt(x * x + y * y);
    }
    
    void Vector::set_ang() {
        if (x == 0.0 && y == 0.0) {
            ang = 0.0;
        } else {
            ang = atan2(y, x);
        }
    }
    
    void Vector::set_x() {
        x = mag * cos(ang);
    }
    
    void Vector::set_y() {
        y = mag * sin(ang);
    }
    
    Vector::Vector() {
        x = y = mag = ang = 0.0;
        mode = RECT;
    }
    
    Vector::Vector(double n1, double n2, Mode form) {
        mode = form;
        if (form == RECT) {
            x = n1;
            y = n2;
            set_mag();
            set_ang();
        } else if (form == POL) {
            mag = n1;
            ang = n2 / Rad_to_deg;
            set_x();
            set_y();
        } else {
            x = y = mag = ang = 0.0;
            mode = RECT;
        }
    }
    
    void Vector::reset(double n1, double n2, Mode form) {
        mode = form;
        if (form == RECT) {
            x = n1;
            y = n2;
            set_mag();
            set_ang();
        } else if (form == POL) {
            mag = n1;
            ang = n2 / Rad_to_deg;
            set_x();
            set_y();
        } else {
            x = y = mag = ang = 0.0;
            mode = RECT;
        }
    }
    
    Vector::~Vector() {
        
    }
    
    void Vector::polar_mode() {
        mode = POL;
    }
    
    void Vector::rect_mode() {
        mode = RECT;
    }
    
    Vector Vector::operator+(const Vector &b) const {
        return Vector(x + b.x, y + b.y);
    }
    
    Vector Vector::operator-(const Vector &b) const {
        return Vector(x - b.x, y - b.y);
    }
    
    Vector Vector::operator-() const {
        return Vector(-x, -y);
    }
    
    Vector Vector::operator*(double n) const {
        // 仅支持 vector * 1.2 这样的形式，不支持 1.2 * vector 这样的形式
        return Vector(n * x, n * y);
    }
    
    Vector operator*(double n, const Vector & a) {
        // 直接调用已经重载的函数，operator*
        return a * n;
    }
    
    std::ostream & operator<<(std::ostream & os, const Vector & v) {
        if (v.mode == Vector::RECT) {
            os << "RECT";
        } else if (v.mode == Vector::POL) {
            os << "POL";
        } else {
            os << "Mode is error";
        }
        return os;
    }
}

/**
 第13章 类继承
 is-a 关系的继承
 如何以公有方式从一个类派生出另一个类
 保护访问
 构造函数成员初始化列表
 向上向下强制转换
 虚成员函数
 早期（静态）联编与晚期（动态）联编
 抽象基类
 纯虚函数
 何时及如何使用公有继承
 */

#ifndef LEFClass13_hpp
#define LEFClass13_hpp

#include <stdio.h>
#include <string>

using std::string;



class TableTennisPlayer {
private:
    /**
     派生类无法访问这些私有数据成员
     */
    string firstname;
    string lastname;
    bool hasTable;
public:
    /**
     这些公有的成员函数都被继承，且做为派生类的方法
     */
    TableTennisPlayer(const string & fn = "none", const string & ln = "none", bool ht = false);
    void Name() const;
    bool HasTable() const { return hasTable; };
    void ResetTable(bool v) { hasTable = v; };
};

// 继承自 TableTennisPlayer
class RatePlayer : public TableTennisPlayer {
private:
    unsigned int rating;
public:
    /**
     派生类需要自己的构造函数，不能访问积累的私有成员，故只能通过构造函数初始化基类的私有
     数据成员。可以添加自己的数据成员，这里添加了 rating，并在析构函数中进行初始化d
     */
    RatePlayer(unsigned int r = 0, const string & fn = "none", const string & ln = "none", bool ht = false);
    RatePlayer(unsigned int r,  const TableTennisPlayer & tp);
    unsigned int Rating() const { return rating; };
    void ResetRating (unsigned int r) { rating = r;};
};
#endif /* LEFClass13_hpp */

#include "LEFClass13.hpp"
#include <iostream>

TableTennisPlayer:: TableTennisPlayer (const string & fn, const string & ln, bool ht) : firstname(fn), lastname(ln), hasTable(ht) {
}

void TableTennisPlayer::Name() const {
    std::cout << lastname << ", " << firstname;
}

/**
 派生类构造函数应通过成员初始化列表将基类信息传递给基类构造函数
 派生类构造函数应初始化派生类新增的数据成员
 */
RatePlayer:: RatePlayer(unsigned int r, const string & fn, const string & ln, bool ht) : TableTennisPlayer(fn, ln, ht){
    rating = r;
}

// 调用了基类的复制构造函数
RatePlayer::RatePlayer(unsigned int r,  const TableTennisPlayer & tp) : TableTennisPlayer(tp), rating(r) {
    
}

/**
 【题目】
 有两个非空的单链表，链表中的元素为正整数，数组是按逆序存储的，且每个
 节点只有一个数字。求出两个两边的和并以链表的形式返回。
 
 【审题】
 题中要求：
 1.给定两个单链表，假如：l1: 2->4->3 , l2: 5->6->4
 2.把 l1 和 l2 进行相加，结果为：7->0->8，也就是342+465=708
 3.假设节点的值均为正整数，且只有一个数字
 
 【举例】
 Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
 Output: 7 -> 0 -> 8
 Explanation: 342 + 465 = 807.
 
 */

namespace AddTwoNum {
    // 定义一个单链表
    struct ListNode {
        int val;
        ListNode *next;
        ListNode(int x) : val(x), next(NULL) {}
    };
    
    class Solution {
    public:
        ListNode *addTwoNumbers(ListNode *l1, ListNode *l2);
        ListNode *addTwoNumbers2(ListNode *l1, ListNode *l2);
    };
}

/**
 【题目】
 有两个非空的单链表，链表中的元素为正整数，数组是按逆序存储的，且每个
 节点只有一个数字。求出两个两边的和并以链表的形式返回。
 
 【审题】
 题中要求：
 1.给定两个单链表，假如：l1: 2->4->3 , l2: 5->6->4
 2.把 l1 和 l2 进行相加，结果为：7->0->8，也就是342+465=708
 3.假设节点的值均为正整数，且只有一个数字
 
 【举例】
 Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
 Output: 7 -> 0 -> 8
 Explanation: 342 + 465 = 807.
 
 */

namespace AddTwoNum {
    // 定义一个单链表
    struct ListNode {
        int val;
        ListNode *next;
        ListNode(int x) : val(x), next(NULL) {}
    };
    
    class Solution {
    public:
        ListNode *addTwoNumbers(ListNode *l1, ListNode *l2);
        ListNode *addTwoNumbers2(ListNode *l1, ListNode *l2);
    };
}

#include "AddTwoNum.hpp"
#include <vector>
#include "iostream"
#include "stdlib.h"

using namespace std;

/**
 1.遍历节点 l1, 和 l2, 得到两个整数 i1 和 i2
 2.sum = i1 + i2
 3.创建节点
 
 Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
 Output: 7 -> 0 -> 8
 342 + 465 = 807
 */
namespace AddTwoNum {
    /**
     这种方法不可取，因为数据结构定义的为 int 类型，当数字太大的时候会发生栈溢出
     所有这种方法虽然实现了功能，但是程序上无法满足特殊情况。
     Line 34: Char 31: runtime error: signed integer overflow: 1000000000 * 9 cannot be represented in type 'int' (solution.cpp)
     
     [9]
     [1,9,9,9,9,9,9,9,9,9]
     */
    ListNode * Solution::addTwoNumbers(ListNode *l1, ListNode *l2) {
        int index = 0;
        int num1 = 0;
        int num2 = 0;
        
        // 求出 l1 代表的整数 sum1
        while (l1 != nullptr) {
            if (index == 0) {
                num1 = l1->val;
                index = 10;
            } else {
                num1 += index * l1->val;
                index = index * 10;
            }
            l1 = l1->next;
        }
        
        // 求出 l2 代表的整数 sum2
        index = 0;
        while (l2 != nullptr) {
            if (index == 0) {
                num2 = l2->val;
                index = 10;
            } else {
                num2 += index * l2->val;
                index = index * 10;
            }
            l2 = l2->next;
        }
        
        // 求出 sum1 和 sum2 的和
        int sum = num1 + num2;
        printf("sum = %d, sum1 = %d, sum2 = %d \n", sum, num1, num2);
        // 求整数有几位数
        int temp_sum = sum;
        ListNode *front = nullptr;
        ListNode *rear = nullptr;
        // 7 -> 0 - > 8
        /**
         7
         ret-next = null
         ret-val = 7
         
         0
         last-next = null
         ret-val = 0
         */
        // 相当于一个队列，不断的入队列
        // 根据求出的 sum 来创建一个单链表
        while (temp_sum != 0) {
            int value = temp_sum % 10;
            temp_sum /= 10;
            printf("value: %d, temp_sum:%d \n", value, temp_sum);
            // ListNode node = ListNode(value); 这种方式不可以，用指针
            ListNode *node = new ListNode(value);
            if (front == nullptr) {
                front = node;
            } else {
                rear->next = node;
            }
            rear = node;
        }
        return front;
    }
    
    ListNode * Solution::addTwoNumbers2(ListNode *l1, ListNode *l2) {
        /**
         其实这道题，开始就掉入一个陷阱了，因为链表中的数字是按照一个整数的逆序存储的，完全可以
         按照链表逐个相加，最后得出结果；这个加法正好匹配！！！
         
         2 -> 4 -> 3 -> null
         5 -> 6 -> 4 -> null
         7 -> 0 -> 7+1 -> null
         
         Runtime: 44 ms, faster than 66.16% of C++ online submissions for Add Two Numbers.
         Memory Usage: 19.2 MB, less than 44.18% of C++ online submissions for Add Two Numbers.
         
         Runtime: 40 ms, faster than 96.78% of C++ online submissions for Add Two Numbers.
         Memory Usage: 19 MB, less than 82.09% of C++ online submissions for Add Two Numbers.
         */
        ListNode *front = nullptr;
        ListNode *rear = nullptr;
        
        ListNode *tempL1 = l1;
        ListNode *tempL2 = l2;
        // 用来标记进位的值，如果大于等于10，则进位为1
        int num = 0;
        
        while (tempL1 != nullptr || tempL2 != nullptr) {
            int l1Value = 0;
            if (tempL1 != nullptr) {
                l1Value = tempL1->val;
                tempL1 = tempL1->next;
            }
            int l2Value = 0;
            if (tempL2 != nullptr) {
                l2Value = tempL2->val;
                tempL2 = tempL2->next;
            }
            int sum = l1Value + l2Value + num;
            int value = sum;
            if (sum >= 10) {
                num = 1;
                value = sum % 10;
            } else {
                num = 0;
            }
            
            // 创建一个单链表
            ListNode *node = new ListNode(value);
            if (front == nullptr) {
                front = node;
            } else {
                rear->next = node;
            }
            rear = node;
        }
        /**
         如果链表都为空了，但是进位为1，那么需要把进位单独创建一个节点
         */
        if (num > 0) {
            rear->next = new ListNode(num);
        }
        
        return front;
    }
}

/**
 第12章 类和动态内存分配
 对类成员使用动态内存分配
 隐式和显式复制构造函数
 隐式和显式重载赋值预算符
 在构造函数中使用new所必须完成的工作
 使用静态类成员
 将定位new运算符用于对象
 使用指向对象的指针
 实现队列抽象数据类型（ADT）
 */

/**
 C++为类自动提供了下面这些成员函数：
 默认构造函数，如果没有定义构造函数
 默认析构函数，如果没有定义
 复制构造函数，如果没有定义
 赋值运算符，如果没有定义
 地址运算符，如果没有定义
 */

#ifndef LEFClass12_hpp
#define LEFClass12_hpp

#include <stdio.h>
#include <iostream>

// nullptr C++11 提供的空指针关键字

/**
 使用new关键字需要注意的地方：
 1、若在构造函数中使用new来初始化指针成员，则应在析构函数中使用delete
 2、new和delete必须兼容，new对应与delete，new[] 对于与 delete[]
 3、如果有多个构造函数，则必须以相同的方式使用 new，要么代中括号，要么不带
 4、应定义一个复制构造函数，通过深度复制将一个对象复制到另一个对象；
 5、应定义一个赋值运算符，通过深度复制将一个对象复制到另一个对象；
 */

/**
 有关返回对象的说明：
 返回对象可以是对象的引用、指向对象的const引用、const对象；
 返回指向const的引用：const Vector &
 返回指向非const的引用：Vector &
 返回对象：Vector
 返回const对象：const Vector

 */

class StringBad {
private:
    // str 是一个指针，因此构造函数必须提供内存用来存储
    char * str;
    int len;
    /**
     num_strings 定义为 static，意思是说所有的的StringBad对象共享一个内存空间，
     不管创建多少个StringBad对象，num_strings始终只有一个。
     */
    static int num_strings;
public:
    StringBad(const char * s);
    StringBad(const StringBad & s);
    StringBad & operator=(const StringBad & st);
    StringBad();
    ~StringBad();
    // 静态成员函数，只能调用静态变量，比如 num_strings，它与类本身无关
    static int HowManay();
    friend std::ostream & operator<<(std::ostream & os, const StringBad & st);
    // 重置赋值运算符 []，比如：str[0]，可修改，比如可以调用 str[0] = 'l'
    char & operator[](int i);
    // 重置赋值运算符 []，比如：str[0]，只读的，不可以调用 str[0] = 'l'
    const char & operator[](int i) const;
};

/**
 StringBad 是一个反例，String 是它的纠正版，从中可以了解到标准C++库是如何
 定义一个String类的。
 */

using std::ostream;
using std::istream;

class String {
private:
    char * str;
    int len;
    static int num_strings2;
    static const int CINLIM = 80;
public:
    String(const char * s);
    String();
    // 复制构造函数，两个字符串的复制将会调用这个构造函数
    String(const String &);
    ~String();
    int length() const { return len; };
    
    String & operator=(const String & st);
    String & operator=(const char *);
    // 重置赋值运算符 []，比如：str[0]，可修改，比如可以调用 str[0] = 'l'
    char & operator[](int i);
    // 重置赋值运算符 []，比如：str[0]，只读的，不可以调用 str[0] = 'l'
    const char & operator[](int i) const;
    
    // 重写比较运算符
    friend bool operator<(const String &st1, const String &st2);
    friend bool operator>(const String &st1, const String &st2);
    friend bool operator==(const String &st1, const String &st2);
    // 重写输出运算符
    friend ostream & operator<<(ostream & os, const String *st);
    // 重写输入运算符
    friend istream & operator>>(istream & is, const String *st);
    
    
};


/**
 模拟ATM机，表示顾客
 */
class Customer {
private:
    // 顾客到店时间
    long arrive;
    // 顾客在ATM机上的处理时间，它是一个随机数
    int processtime;
public:
    Customer() { arrive = processtime = 0; };
    void set(long when);
    long when() const { return arrive; };
    int ptime() const { return processtime; }
};

// 定义队列中的对象
typedef Customer Item;

/**
 模拟队列，使用单链表数据结构，队列中保存的是 Customer 对象
 
 -----------------------------------------------------------
 <- customer0  | customer1 | customer2 | customer3 | customer4 <--
 -----|------------------------------------------------|------
    front                                             rear
 */
class Queue {
private:
    /**
     定义一个结构体，表示链表的节点，每一个节点保存了节点的数据和下一个节点的指针
     它在类声明中定义，所以Node的作用域为整个类，由于声明为私有部分，只能在本类中
     使用，外部不可以使用。如果声明为公有部分则外部可以使用 Queue::Node 调用
     */
    struct Node { Item item; struct Node *next; };
    enum { Q_SIZE = 10};
    // 要跟踪链表，必须知道第一个节点的地址
    Node * front;
    // 由于队列是先进后出的，保存最后一个节点的地址对入队非常方便
    Node * rear;
    // 队列中当前的大小
    int items;
    // 队列的最大限制，它是常量，只能初始化，但不能给它赋值
    const int qsize;
    /**
     定义复制函数，防止队列进行复制操作，因为是私有函数，外部无法调用
     定义赋值函数，防止队列进行赋值（=）操作，因为是私有函数，外部无法调用
     */
    Queue(const Queue & q) : qsize(0) {};
    Queue & operator=(const Queue & q) { return *this; };
public:
    Queue(int qs = Q_SIZE);
    ~Queue();
    bool isempty() const;
    bool isfull() const;
    int queuecount() const;
    bool enqueue(const Item & item);
    bool dequeue(Item & item);
    
};
#endif /* LEFClass12_hpp */

#include "LEFClass12.hpp"
#include <cstring>

using std::cout;

/**
 初始化静态成员，不能再声明处初始化，声明描述了如何分配内存，但并不分配内存。可以在
 类的单独之外进行初始化是因为，静态成员不是类的组成部分，它是单独存储的。如果静态成员是
 const枚举或整数类型则可以在类声明中初始化。
 */
int StringBad::num_strings = 0;

StringBad::StringBad(const char * s) {
    len = (int)std::strlen(s);
    str = new char[len+1];
    std::strcpy(str, s);
    num_strings++;
    cout << num_strings;
    cout << std::endl;
}

// 复制函数
StringBad::StringBad(const StringBad & s) {
    num_strings++;
    len = s.len;
    str = new char [len+1];
    std::strcpy(str, s.str);
}

// 提供赋值运算符
StringBad & StringBad::operator=(const StringBad & st) {
    if (this == &st) {
        return *this;
    }
    // 释放掉旧的内存，分配新的内存
    delete [] str;
    len = st.len;
    str = new char[len + 1];
    std::strcpy(str, st.str);
    return *this;
}

StringBad::StringBad(){
    len = 4;
    str = new char[4];
    std::strcpy(str, "C++");
    num_strings++;
    cout << num_strings;
    cout << std::endl;
}

StringBad::~StringBad() {
    cout << str << " object deleted!\n";
    --num_strings;
    cout << num_strings << " left \n";
    // str 指向了 new 创建的内存空间，当对象销毁后，这块内存也需要销毁
    /**
     在构造函数中使用new来分配内存时，必须在析构函数中使用delete来释放内存，如果
     分配内存使用的时new [] ,则在析构函数中必须使用 delete []。
     */
    delete [] str;
}

std::ostream & operator<<(std::ostream & os, const StringBad & st) {
    os << st.str;
    return os;
}

// 静态成员函数只能访问静态变量，因此不能访问 len 和 str 属性
int StringBad::HowManay() {
    return num_strings;
}


/////////////////////////////////
int String::num_strings2 = 0;


String::String(const char * s) {
    len = (int)std::strlen(s);
    str = new char[len+1];
    std::strcpy(str, s);
    num_strings2++;
    cout << num_strings2;
    cout << std::endl;
}

String::String(){
    len = 4;
    str = new char[1];
    str[0] = '\0';
    num_strings2++;
    cout << num_strings2;
    cout << std::endl;
}

String::String(const String & st) {
    num_strings2++;
    len = st.len;
    str = new char[len+1];
    std::strcpy(str, st.str);
}

String::~String() {
    --num_strings2;
    delete [] str;
}

String & String::operator=(const String & st) {
    if (this == &st) {
        return *this;
    }
    delete [] str;
    len = st.len;
    str = new char [len+1];
    std::strcpy(str, st.str);
    return *this;
}

String & String::operator=(const char *s) {
    delete [] str;
    len = (int)std::strlen(s);
    str = new char [len+1];
    std::strcpy(str, s);
    return *this;
}

char & String::operator[](int i) {
    return str[i];
}

const char & String::operator[](int i) const {
    return str[i];
}

bool operator<(const String &st1, const String &st2) {
    return std::strcmp(st1.str, st2.str) < 0;
}

bool operator>(const String &st1, const String &st2) {
    return st2 < st1;
}

bool operator==(const String &st1, const String &st2) {
    return std::strcmp(st1.str, st2.str) == 0;
}

//ostream & operator<<(ostream & os, const String &st) {
//    os << st.str;
//    return os;
//}

//istream & operator>>(istream & is, String & st) {
////    char temp[String::CINLIM];
//}

/**
 顾客
 */
void Customer::set(long when) {
    // 处理时间为一个随机数
    processtime = std::rand() % 3 + 1;
    arrive = when;
}

/**
 队列
 
 初始化列表：
 只能用于构造函数；
 对于const类成员，必须使用这种语法
 对于声明为引用的类成员，也必须使用这种语法
 Class::Classy(int n, int m) : mem1(n), mem2(0), mem3(n*m + 2) { }
 */
Queue::Queue(int qs) : qsize(qs) {
    front = rear = nullptr;
    items = 0;
}

Queue::~Queue() {
    // 队列销毁时，删除所有的节点
    Node *temp;
    while (front != nullptr) {
        temp = front;
        front = front->next;
        delete temp;
    }
}

bool Queue::isempty() const {
    return items == 0;
}

bool Queue::isfull() const {
    return items == qsize;
}

int Queue::queuecount() const {
    return items;
}

bool Queue::enqueue(const Item &item) {
    // 队列已满，不能入队
    if (isfull()) {
        std::cout << "Enqueue Queue isfull: " << items << std::endl;
        return false;
    }
    // 创建一个新的节点
    Node *add = new Node;
    // Item 为节点的数据部分
    add->item = item;
    // 由于它是对尾的节点，所以它的下一个节点为空
    add->next = nullptr;
    
    items++;
    // 空队列时，第一次加入，那么队头和队尾都是 add
    if (front == nullptr) {
        front = add;
    } else {
        // 队列中已经有节点了, 直接把队尾的指针指向 add
        /**
         模拟队列，使用单链表数据结构，队列中保存的是 Customer 对象
         
         -----------------------------------------------------------
         <- customer0  | customer1 | customer2 | customer3 | customer4 <--
         -----|------------------------------------------------|------
            front                                             rear
         */
        rear->next = add;
    }
    // 修改队尾的节点
    rear = add;
    
    std::cout << "Enqueue Queue count: " << items << std::endl;
    return true;
}

bool Queue::dequeue(Item &item) {
    // 队列中没有成员，如何删除？
    if (front == nullptr) {
        std::cout << "Dequeue Queue isEmpty: " << items << std::endl;

        return false;
    }
    /**
     -----------------------------------------------------------
     <- customer0  | customer1 | customer2 | customer3 | customer4 <--
     -----|------------------------------------------------|------
        front                                             rear
     出队列，从头开始
     */
    // 将第一个节点给调用者，通过引用传递
    item = front->item;
    items--;
    // 保存头节点，以便删除
    Node *temp = front;
    // 头结点指向下一个节点
    front = front->next;
    // 删除头结点
    delete temp;
    // 如果是最后一个节点，
    if (items == 0) {
        rear = nullptr;
    }
    std::cout << "Dequeue Queue count: " << items << std::endl;
    return true;
}

#include <stdio.h>
#include <vector>
#include <unordered_map>

using namespace std;
using std::unordered_map;

/**
 【题目】
 给出一个整形数组和一个目标值，找出数组中，两个成员的和是目标值所在数组中的下标。
 你可以假定每次输入只对应一种答案，且不能使用数组中同样的元素。
 
 【审题】
 题中要求：
 1.给定一个数组和一个目标值，假如数组为 nums = [2, 7, 11, 15], 目标值为：target = 9
 2.找出目标值 9 是数组 nums 中哪两个元素的和
 3.返回找到元素的下标，比如 return [0, 1].
 
 【举例】
 Given nums = [2, 7, 11, 15], target = 9,
 
 Because nums[0] + nums[1] = 2 + 7 = 9,
 return [0, 1].
 
 【方法】
 1. 两次遍历找到和为 target 的两个元素
 2. a.使用一个unordered_map用来保存 nums 中元素和它的下标
    b.每次查找找到 target - nums[i] 的差值，查找就是下一个要找的元素
 */

/**
 【C++向量 Vector】
 向量（Vector）是一个封装了动态大小数组的顺序容器（Sequence Container）。
 跟任意其它类型容器一样，它能够存放各种类型的对象。可以简单的认为，向量是一个能够存放任意类型的动态数组
 */
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target);
    vector<int> twoSum2(vector<int>& nums, int target);
};

/**
 nums = [2, 7, 11, 15], target = 9
 两次遍历找到和为 target 的两个元素
 时间复杂度为：O(n*n)
 空间复杂度为：
 
 Runtime: 124 ms, faster than 37.43% of C++ online submissions for Two Sum.
 Memory Usage: 9.6 MB, less than 62.01% of C++ online submissions for Two Sum.
 */
vector<int>  Solution::twoSum(vector<int> &nums, int target) {
    for (int i = 0; i < nums.size(); i++) {
        int fnum = nums[i];
        for (int j = i+1; j < nums.size(); j++) {
            int snum = nums[j];
            if (fnum + snum == target) {
                return {i, j};
            }
        }
    }
    return vector<int>();
};

/**
 1.使用一个unordered_map用来保存 nums 中元素和它的下标
 2.每次查找找到 target - nums[i] 的差值，查找就是下一个要找的元素
 
 Runtime: 12 ms, faster than 97.81% of C++ online submissions for Two Sum.
 Memory Usage: 10.4 MB, less than 33.11% of C++ online submissions for Two Sum.
 */
vector<int> Solution::twoSum2(vector<int> &nums, int target) {
    unordered_map<int, int> record;
    for (int i = 0; i < nums.size(); i++) {
        int sub = target - nums[i];
        if (record.find(sub) != record.end()) {
            // 找到了
            return {record[sub], i};
        } else {
            record[nums[i]] = i;
        }
    }
    return vector<int>();
};