剑指offer01

运算符重载
一般运算符重载分为成员函数的操作符和非成员函数的重载

class CMyString{
public:
    CMyString(char* pData = nullptr);
    CMyString(const CMyString& str);
    CMyString& operator =(const CMyString& str);    //成员函数操作符重载
    ~CMyString();
private:
    char* m_pData;
}
CMyString& CMyString::operator =(const CMyString& str)
{
    if(this == &str)
        return *this;
    delete[] m_pData;
    m_pData = NULL;
    m_pData = new char[strlen(str.m_pData) + 1]; //重新分配str大小的内存
    strcpy(m_pData,str.m_pData);
    return *this;
}
//非成员函数操作符重载
ostream&  operator << (ostream& os, const complex& str)
{
    return os << str.m_pData;
}

剑指offer03

数组中任意一个重复的数字（）这里没有找出全部的重复元素
1、通过先将数组排序，然后遍历查找

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        for(int i=0; i<nums.size(); i++){
            if(nums[i] == nums[i+1])
                return nums[i];
        }
        return -1;
    }
};

2、原地交换思想：从头到尾遍历，一个萝卜一个坑（下标与元素值对应）
// 1. 所谓原地交换，就是如果发现这个坑里面的萝卜不是这个坑的，就看看你是哪家的萝卜，然后把你送到哪家，再把那家里那个萝卜拿回来。
// 2. 拿回来之后，再看看拿回来的这个萝卜应该是属于哪家的，再跟哪家交换。
// 3. 就这样交换萝卜，直到想把这个萝卜送回它家的时候，发现人家家里已经有了这个萝卜了（双胞胎啊），那这个萝卜就多余了，就把这个萝卜上交给国家。

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        for(int i=0; i<nums.size(); i++){
            while(nums[i] != i){    //原地归置数组
                //遇到重复元素直接返回
                if(nums[nums[i]] == nums[i]) 
                    return nums[i];
                //不然一直交换下标对应的元素位置，将他放回指定的位置
                std::swap(nums[i],nums[nums[i]]);
            }
        }
        return -1;
    }
};

剑指offer04

二维数组中的查找：数组的行与列都是递增的，判断输入的数字是否在数组中

//时间复杂度n2
class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        for(int i=0; i<matrix.size(); i++){
            for(int j=0; j<matrix[0].size(); j++){
                if(matrix[i][j] == target)
                    return true;
            }
        }
        return false;
    }
};

2、通过分析查找来缩小矩阵的大小，从右上角或者左下角开始查找，然后和目标元素比大小

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
      bool flag = false;
      if(matrix.size()>0 && matrix[0].size()>0)
      {
        int cow = 0;                              //行   
        int column = matrix[0].size()-1;          //列
        while(cow<matrix.size() && column>=0){
            if(matrix[cow][column] == target){
                flag = true;
                break;
            }
            else if(matrix[cow][column]>target)
                column--;
            else if(matrix[cow][column]<target)
                cow++;
        }
      }
      return flag;
    }
};

剑指offer05

替换空格：
1、有可用的额外空间，从前向后遍历
使用字符串变量s2暂存数据，通过string::append()函数将指定字符串%20连接到后面，剩余字符通过string::push_back()函数追加

class Solution {
public:
    string replaceSpace(string s) {
        string s2;
        for(int i=0; i<s.size(); i++){
            if(s[i] == ' ')
                s2.append("%20");
            else
                s2.push_back(s[i]);
        }
        return s2;
    }
};

2、没有可有的额外空间，在原字符串中修改，创建双指针从后向前遍历
先将原字符串扩容，然后通过双指针从后向前遍历（while），p1将所遍历的元素后移，如果遇到空格就停止遍历，同时p2追加02%，否则直接复制原元素。

class Solution {
public:
    string replaceSpace(string s) {
        int count=0;
        for(int i=0; i<s.size(); i++){
            if(s[i] == ' ')
                count++;
        }

        int p1 = s.size();
        s.resize(s.size() + count*2); //将原字符串长度扩展到s.size() + 空格数*2
        int p2 = s.size();
        while(p1>=0){
            if(s[p1] == ' '){
                s[p2--] = '0';
                s[p2--] = '2';
                s[p2--] = '%';
            }
            else
                s[p2--] = s[p1];
            p1--;
        }
        return s;
    }

};

单链表题目总结

C++实现单向链表类（通过循环找到前驱节点很重要！！！）

template<class T>
class Node
{
public:
    friend class List;         //将链表类声明为友元
private:
    T data;
    Node<T>* next;
}

template<class T>
class List
{
public:
    List();
    ~List();

    //在第k个位置插入元素x，返回插入后的链表
    List<T>& insert(const T& x, int k);
    //判断链表是否为空，空返回true
    bool isEmpty() const;
    //返回表中元素个数
    int getLenth() const;
        //将表中第k个元素保存到x中，若不存在则返回false
    bool getData(int k, T& x);
    //将表中第k个元素修改为x，若不存在则返回false
    bool modifyData(int k, const T& x);
    //返回x在表中的位置，如果不在表里返回0
    int find(const T& x);

    //按位置删除第k个元素，并把它保存到x中，返回删除后的线性表
    List<T>& removebyIndex(const int k, T& x);
    //按元素删除查找的元素，并把它保存到y中，返回删除后的线性表
    List<T>& removebyValue(const T& x, T& y);

    void outPut(ostream& out) const;

private:    
    int lenth;
    Node<T>* pHeader;
}

List::List()
{    
    pHeader = new List<T> ();    //创建头节点
}

List::~List()
{

}

List<T>& List::insert(const T& x, int k)
{    
    if(x == null)
        return *this;     
    int len = getLenth();
    if(k<1 || k>len +1)
    {
        cout << "下标越界！"<< endl;
        return *this;
    }

    //记录需要插入的节点
    Node<T>* newNode = new Node<T>;
    newNode->data = x;

    //临时变量p记录头节点
    Node<T>* p = pHeader;
    //通过循环遍历，找到需要插入位置的前一个节点p = k-1
    for(int i=1; i<k; i++)
    {
        p=p->next;
    }
    //循环完之后p->next = 第k个位置的节点
    newNode->next = p->next;     
    p->next = newNode;
    return *this;
}

bool List::isEmpty() const
{
    return pHeader->next == NULL;
}

int List::getLenth() const
{
    int flag=0;
    if(pHeader->next == NULL)
        return 0;
    Node<T>* p = pHeader->next;
    while(p)
    {
        flag++;
        p = p->next;
    }
    return flag;
}

bool List::getData(int k, T& x)
{
    int len=getLenth();
    if(k<1 || k>len+1)
        return false;
    Node<T>* node = new Node;
    node->data = x;
}

bool List::modifyData(int k, const T& x);

int List::find(const T& x);


List<T>& List::removebyIndex(const int k, T& x);

List<T>& List::removebyValue(const T& x, T& y);

void List::outPut(ostream& out) const;

1、offer06

从尾到头打印链表，因为我们在遍历链表时是从头到尾，而输出却要从尾到头（先进后出），用栈来实现链表

#include<stack>
void printlist_reverse(ListNode* pHead)
{
    stack<ListNode*> nodes;    //创建 节点栈 用于存储遍历的链表节点
    ListNode* p = pHead;
    while(p!=NULL){
        nodes.push(p);
        p=p->next;
    }
    while(!nodes.empty()){
        cout << "栈顶元素" << nodes.top()->data << ' ';
        nodes.pop();    //对栈顶元素进行出栈
    }
}

void printlist_reverse_recursive(ListNode* pHead)
{
    if(pHead!=NULL){
        if (pHead->next != nullptr)
        {
            printlist_reverse_recursive(pHead->next);
        }
        cout << pHead->data;
    }
}

c 学习笔记