剑指offer

一边看书一边刷题

1. 赋值运算符函数

类型CMyString，添加一个赋值运算符函数。

1
2
3
4
5
6
7
8
9
class CMyString
{
public:
	CMyString(char* pData=nullptr);
	CMyString(const CMyString& cMyString);
	~CMyString(void);
private:
	char* m_pData;
}
  • 返回值

str1=str2=str3（为了连续赋值的可能性）

将返回值设置为该类型的引用

1
return *this;
  • 传入参数

常量引用，如果传入的不是引用而是实例的话，那么从形参到实参，就会多调用一次拷贝构造函数，降低效率。

  • 释放内存

防止内存泄漏。

  • 细节

要判断传入的参数与赋值的是不是同一个，这样如果释放内存的话，就会导致传入的参数也被释放了。

1
2
3
4
5
6
7
8
9
10
11
12
CMyString& CMyString::Operator=(const CMyString& cMyString){
	if(this==&cMyString)
		return *this;
	// 释放原有的空间
	delete[] m_pData;
	m_pData=nullptr;
	// 申请一块新的空间，并赋值
	m_pData=new char[strlen(cMyString.m_pData)+1];
	strcpy(m_pData,cMyString.m_pData);
	
	return *this;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
CMyString& CMyString::Operator=(const CMyString& cMyString){
	if(this!=&cMyString)
	{
		// 新建一个临时的实例
		CMyString new_str(cMyString);
		// 指针指向这临时实例的地址
		char *temp = new_str.m_pData;
		// 临时实例的char指向赋值对象的地址
		new_str.m_pData = m_pData;
		// 赋值对象的地址指向指针的地址。
		m_pData = temp;
	} // 跳出if后，临时实例被析构，指向地址的空间被自动释放
	return *this;
}
  1. 把一个CMyString的实例赋值给另一个实例。
  2. 把一个CMyString的实例赋值给它自己。
  3. 连续赋值。

2. C# 单例模式


3. 数组

sizeof

  • int类型，一个占4字节。int a[]={1,2,3,4,5}, 则sizeof(a) = 20。

  • 对指针int* p = a, 则sizeof(p) = 4。

  • 当数组通过函数的参数进行传递时，数组就自动退化为同类型的指针。因此对于函数中的数组参数sizeof，结果也是4。

数组中重复元素

n个整数，a[i]∈[0,n-1]，a中有重复的数字，也不知道重复了几次，有几个数字重复，求所有的重复数字。

  1. a[5] = 3, 则另a[3] = n+a[3]，判断a[3] 是否>2n，如果大于2n，说明已重复；
  2. a[1] = 3，a[3]=2，a[8]=1，则另a[1]与a[3]交换，再a[1]与a[8]换，直到a[i]=i，如果在交换的过程中发现，a[i]已经等于i了，那么i重复了。

上述，时间复杂度为O(n)，空间复杂度O(1)。

如果不能修改数组呢？

  • 二分（需要自己写一下）

    长度为8的数组{2,3,5,4,3,2,6,7}，从中间数字4，分为1-4，5-7，那么先判断1~4的数字一共出现了几次，不难发现是5次，那么一定有重复的数字……

    这种方法不可保证能找到所有重复的数字。

二维数组中的查找

在一个二维数组中，每一行都按照从左到右递增，每一列从上到下递增。

输入这样的二维数组，判断该数组中是否含有某一整数。

思路：从右上角判断，剔除一列、一行，缩小范围。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        int curi,curj;
        int n,m;
        n=matrix.size();
        if(n==0) return false;
        m=matrix[0].size();
        bool flag = false;
        curi=0;
        curj=m-1;
        while((!flag)&&curi<n&&curj<m&&curi>=0&&curj>=0)
        {
            if(matrix[curi][curj]>target)
                curj=curj-1;
            else if(matrix[curi][curj]<target)
                curi=curi+1;
            else
                flag=true;
        }
        return flag;
    }
};

4. 字符串

比较
1
2
3
4
5
char s1[]="hello";
char s2[]="hello";
char* s3="hello";
char* s4="hello";
//判断s1与s2，s3与s4是否相同
替换空格

将字符串中每个空格替换成”%20”

思考：提前申请空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    string replaceSpace(string s) {
        int p1,p2;
        p1=s.length()-1;
        int cnt=0;
        for(int i=0;i<=p1;i++) //这里也可以for(char/auto c : s) if(c==' ') ..
        {
            if(s[i]==' ') 
                cnt++;
        }
        p2=p1+2*cnt;
        s+=string(cnt*2,' '); // 或者直接用char* c=new char[],然后s=string(c)
        // s.resize(p1+2*cnt);
        for(int i=p1;i>=0;i--)
        {
            if(s[i]!=' ')
                s[p2--]=s[i];
            else
            {
                s[p2--]='0';
                s[p2--]='2';
                s[p2--]='%';
            }
        }
        return s;
    }
};

5. 链表


6. 树

二叉树

先序遍历、中序遍历、后序遍历、层次遍历

重建二叉树

输入二叉树的前序、中序遍历的结果，重建该二叉树。假设输入的遍历结果中都不含重复的数字。

思路：先序中取得根节点，在中序中查找根节点，左边的是左子树，右边的是右子树，递归。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int getMe(vector<int>& inorder,int cur,int l,int r){
        for(int i=l;i<=r;i++)
            if(inorder[i]==cur)
                return i;
        return l;
    };
   
    TreeNode* solve(vector<int>& preorder, vector<int>& inorder,int l,int r,int cur){
        if(l>r) return nullptr;
        TreeNode* tree = new TreeNode(preorder[cur]);
        int x = getMe(inorder,preorder[cur],l,r);
        tree->left = solve(preorder,inorder,l,x-1,cur+1);
        tree->right = solve(preorder,inorder,x+1,r,cur+1+x-l);
        return tree;
    };
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int size=preorder.size();
        if(size==0)
            return nullptr;
        return solve(preorder,inorder,0,size-1,0);
    };
};
二叉树的下一个节点

给定一棵二叉树和其中一个节点，如何找出中序遍历序列的下一个节点？树中的节点除了两个左右子树的指针，还有一个父节点指针。

讲一下思路，这里的思路就是分类讨论：

类型 做法
存在右子节点 找到右子节点的最左节点
不存在右子节点，是父节点的左子节点 父节点
不存在右子节点，是父节点的右子节点 向上寻找，直到找到一个点是父节点的左子节点
中序遍历二叉树（递归与非递归）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // 递归实现
    void recurse_solve(TreeNode* p,vector<int>& vv){
        if(p->left!=nullptr)
            recurse_solve(p->left,vv);
        vv.push_back(p->val);
        if(p->right!=nullptr)
            recurse_solve(p->right,vv);

    }
    // 栈非递归实现
    void stack_solve(TreeNode* root, vector<int>& vv){
        stack<TreeNode*>myst;
        TreeNode* p = root;
        while(p!=nullptr||!myst.empty())
        {
            if(p!=nullptr)
            {
                myst.push(p);
                p=p->left;
            }
            else
            {
                p=myst.top();
                myst.pop();
                vv.push_back(p->val);
                p=p->right;
            }
        }
    }
    // 主函数
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int>vv;
        if(root==nullptr) return vv;
        stack_solve(root,vv);
        return vv;
    }
};
二叉搜索树

O(logn)

堆
红黑树

把树中的节点定义为红、黑两种颜色，并通过规则确保从根节点到叶子节点的最长路径的长度不超过最短路径的两倍。

在C++的STL中，set、multiset、map、multimap等数据结构都是基于红黑树实现的。


7. 栈和队列

用两个栈实现队列
1
略
求斐波那契数列n项
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
public:
    const int MOD = 1e9+7;
    int eMarix[2][2]={1,1,1,0};

    // 递归
    int recurse(int n){
        if(n==0) return 0;
        if(n==1) return 1;
        return (fib(n-1)+fib(n-2))%MOD;
    }
    // 普通
    int normal(int n){
        if(n==0) return 0;
        if(n==1) return 1;
        int last1=0,last2=1,temp;
        for(int i=2;i<=n;i++)
        {
            temp = last2;
            last2 = (last1+last2)%MOD;
            last1 = temp;
        }
        return last2;
    }
    void marix_solve(int a[2][2],int b[2][2]){
        long long temp[2][2]={0};
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)
            {
                for(int k=0;k<2;k++)
                {
                    temp[i][j]+=1ll*a[i][k]*b[k][j]%MOD;
                }
                temp[i][j]%=MOD;
            }
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)
                a[i][j]=temp[i][j];
        
    }
    // 矩阵快速幂
    int marix(int n){
        if(n==0) return 0; // 0,1,1,2,3,5,8
        if(n==1) return 1;
        int curMarix[2][2]={1,0,0,1};
        while(n)
        {
            if(n&1)
                marix_solve(curMarix,eMarix);
            marix_solve(eMarix,eMarix);
            n>>=1;
            
        }
        return curMarix[1][0];
    }
    // 主函数
    int fib(int n) {
        return marix(n);
    }
};

$$ {矩阵快速幂}
\begin{bmatrix}f(n) & f(n-1) \ f(n-1) & f(n-2)\ \end{bmatrix}
=
\begin{bmatrix}1 & 1 \ 1 & 0 \end{bmatrix}^{n-1}
$$

8. 查找和排序

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
// 求非降序范围内第一个不小于value的位置
int lower_bound(int array[],int n,int value){
	int mid,l=0,r=n-1;
	while(l<r){
		mid = l+(r-l)/2;
		if(array[mid]<value) l=mid+1;
		else r=mid;
	}
	return l;//or return r;
}
//stl 
lower_bound(a,a+n,value)-a // 第一个不小于value的位置
upper_bound(a,a+n,value)-a // 第一个大于value的位置
旋转数组的最小数

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int solve(vector<int>& numbers){
        int len=numbers.size();
        int mid,l=0,r=len-1;
        while(l<r) // 如果当前值要比最后的值小，说明要往前找（包括本身）；如果当前值要比最后的值大，说明要往后找，还没到；如果相等，有可能还在前面（包括本身：1 3 3/5 4 4）……
        {
            mid=l+r>>1;
            if(numbers[mid]<numbers[r])
                r=mid;
            else if(numbers[mid]>numbers[r])
                l=mid+1;
            else
                r--;
        }
        return numbers[l];
    }
    int minArray(vector<int>& numbers) {
        return solve(numbers);
    }
};

快速排序

1

交换数字

1
2
3
4
5
6
7
8
// 只能对int 和 char
x=x^y; 
y=x^y;
x=x^y;

x=x+y;
y=x-y;
x=x-y;

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

小可爱的小可爱，<br/>拖肥的娘亲，<br/>划水的ACMer，<br/>努力中的小菜鸡，<br/>想要自信和一往无前的勇气。