剑指Offer+常用手写算法(C++)

发表于   |   更新于 | 分类于

1、编写赋值运算符

四点：返回值、参数类型、释放已有内存、自身赋值特殊情况。
进阶：异常安全性。

1
2
3
4
5
6
7
8
9
10
11
CMyString& CMyString::operator=(const CMyString& rhs)
{
	if(this!=&rhs)
	{
		CMyString temp(rhs);//调用copy构造函数
		char* ptemp=temp.m_pData;
		temp.m_pData=m_pData;
		m_pData=ptemp;
	}
	return *this;
}

2、简单实现一个Singleton类。

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
class singleton
{
protected:
    singleton()
    {
        pthread_mutex_init(&mutex);
    }
public:
    static pthread_mutex_t mutex;
    static singleton* initance();
};

pthread_mutex_t singleton::mutex;
singleton* singleton::initance()
{
    pthread_mutex_lock(&mutex);
    static singleton obj;
    pthread_mutex_unlock(&mutex);
    return &obj;
}


class Singleton{
	private:
		Singleton(){}
		static Singleton instance;
		static object obj=new object();//一个互斥锁
	public:
		static Singleton& GetInstance{
			if(instance==NULL)
			{
				lock(obj){
					if(instance==NULL)
						instance=new Singleton();
				}
			}
			return instance;
}
};

3、找出数组中重复的数字。

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
int question3_3(vector<int>& vec)
{
	if (vec.empty())
		return NULL;
	for (int i = 0; i < vec.size(); i++)
		if (vec[i]<0 || vec[i]>vec.size() - 1)
			return NULL;
	for (int i = 0; i < vec.size(); i++)
	{
		
		while (vec[i] != i)
		{
			if (vec[i] == vec[vec[i]])
				return vec[i];
			int temp = vec[i];
			vec[i] = vec[temp];
			vec[temp] = temp;
		}
	}
}

//3.2：
int countRange(const vector<int>& numbers, int length, int start, int end)
{
	if (numbers.empty())
		return 0;

	int count = 0;
	for (int i = 0; i < length; i++)
		if (numbers[i] >= start && numbers[i] <= end)
			++count;
	return count;
}

int question3_02(vector<int>& numbers)
{
	if ( numbers.size() <= 0)
		return -1;

	int start = 1;
	int end = numbers.size() - 1;
	while (end >= start)
	{
		int middle = ((end - start) >> 1) + start;
		int count = countRange(numbers, numbers.size(), start, middle);
		if (end == start)
		{
			if (count > 1)
				return start;
			else
				break;
		}

		if (count > (middle - start + 1))
			end = middle;
		else
			start = middle + 1;
	}
	return -1;
}

4、二维数组中的查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
    bool Find(int target, vector<vector<int> > array) {
        int n=array.size();
        int m=array[0].size();
        if(n!=0&&m!=0&&array[n-1][m-1]<target)
            return false;
        for(int i=0,j=m-1;i<n&&j>=0;)
        {
            if(array[i][j]==target)
                return true;
            else if(array[i][j]<target)
                i++;
            else
                j--;
        }
        return false;
}

5、替换空格

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void replaceSpace(char *str,int length) {
       int spaceCnt=0;
       for(int i=0;i<length;i++)
           if(str[i]==' ')
               spaceCnt++;
       int newLength=length+2*spaceCnt;
       str[newLength]='\0';
       int i=0;
       newLength--;
       for(i=length-1;i>=0;i--)
       {
           if(str[i]==' ')
           {
               str[newLength--]='0';
               str[newLength--]='2';
               str[newLength--]='%';
           }
           else
               str[newLength--]=str[i];
       }
}

6、从尾到头打印链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
void Recursion(ListNode* head, vector<int> &res)
    {
        if(head->next)
            Recursion(head->next,res);
        res.push_back(head->val);
    }
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> res;
        if(!head)
            return res;
        Recursion(head,res);
        return res;
    }

反转链表：

1
2
3
4
5
6
7
8
9
10
11
12
13
ListNode* ReverseList(ListNode* head)
    {
        ListNode* pre=NULL;
        ListNode* next=NULL;
        while(head!=NULL)
        {
            next=head->next;
            head->next=pre;
            pre=head;
            head=next;
        }
        return pre;
    }

树的四种遍历七种写法：

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
void PreorderTra_Loop(TreeNode * root)//先序循环
{
	if (!root)
		return;
	stack<TreeNode*> sta;
	TreeNode* cur = root;
	while (cur || !sta.empty())
	{
		while (cur)//找到最左
		{
			cout << cur->val << " ";
			sta.push(cur);
			cur = cur->left;
		}
		
		if (!sta.empty())//弹出栈顶元素并将选择其右子树再次遍历
		{
			TreeNode* temp=sta.top();
			sta.pop();
			cur = temp->right;
		}
	}
}
void PreorderTra_Recur(TreeNode * root)//先序递归
{
	if (root)
	{
		cout << root->val << " ";
		PreorderTra_Recur(root->left);
		PreorderTra_Recur(root->right);
	}
}

void MidorderTra_Loop(TreeNode* root)
{
	if (!root)
		return;
	stack<TreeNode*> sta;
	TreeNode* cur = root;
	
	while (cur || !sta.empty())
	{
		while (cur)
		{
			sta.push(cur);
			cur = cur->left;
		}

		if (!sta.empty())
		{
			TreeNode* temp = sta.top();
			cout << temp->val << " ";
			sta.pop();
			cur = temp->right;
		}
	}
}
void MidorderTra_Recur(TreeNode * root)//中序递归
{
	if (root)
	{
		MidorderTra_Recur(root->left);
		cout << root->val << " ";
		MidorderTra_Recur(root->right);
	}
}
//后序循环需要检查一个节点是否是第一次位于栈顶，若是第一次则引入它的右孩子，否则弹出
void PostorderTra_Loop(TreeNode* root)
{
	if (!root)
		return;
	stack<TreeNode*> sta;
	TreeNode* cur = root;
	unordered_map<TreeNode*, int> m;
	while (cur || !sta.empty())
	{
		while (cur)
		{
			sta.push(cur);
			cur = cur->left;
		}

		if (!sta.empty())
		{
			TreeNode* temp = sta.top();
			if (m[temp] == 0)//第一次
			{
				cur = temp->right;
				m[temp]++;
			}
			else{
				cout << temp->val << " ";
				sta.pop();
			}		
		}
	}
}
void PostorderTra_Recur(TreeNode * root)//后序递归
{
	if (root)
	{	
		PostorderTra_Recur(root->left);
		PostorderTra_Recur(root->right);
		cout << root->val << " ";
	}
}
void LevelTra(TreeNode * root)//层次遍历
{
	if (!root)
		return;
	queue<TreeNode*> q;
	TreeNode* node = root;
	q.push(node);
	while (!q.empty())
	{
		TreeNode* front = q.front();
		if (front->left)
			q.push(front->left);
		if (front->right)
			q.push(front->right);
		cout << front->val << " ";
		q.pop();
	}
}

7、重建二叉树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
TreeNode* recursion(vector<int>& pre,const int preStart,const int preEnd,vector<int>& vin,const int vinStart,const int vinEnd)
    {
        if(preStart>preEnd||vinStart>vinEnd)
            return NULL;
        TreeNode* node=new TreeNode(pre[preStart]);
        
        for(int i=vinStart;i<=vinEnd;i++)
        {
            if(vin[i]==pre[preStart])
            {
                node->left=recursion(pre,preStart+1,i-vinStart+preStart,vin,vinStart,vinEnd-1);
                node->right=recursion(pre,i-vinStart+preStart+1,preEnd,vin,i+1,vinEnd);
                break;
            }
        }
        
        return node;
    }
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        TreeNode* root=recursion(pre,0,pre.size()-1,vin,0,vin.size()-1);
        return root;
    }

8、二叉树的下一节点

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
BinaryTreeNode* GetNext(BinaryTreeNode* pNode)
{
    if(pNode == nullptr)
        return nullptr;

    BinaryTreeNode* pNext = nullptr;
    if(pNode->m_pRight != nullptr)
    {
        BinaryTreeNode* pRight = pNode->m_pRight;
        while(pRight->m_pLeft != nullptr)
            pRight = pRight->m_pLeft;

        pNext = pRight;
    }
    else if(pNode->m_pParent != nullptr)
    {
        BinaryTreeNode* pCurrent = pNode;
        BinaryTreeNode* pParent = pNode->m_pParent;
        while(pParent != nullptr && pCurrent == pParent->m_pRight)
        {
            pCurrent = pParent;
            pParent = pParent->m_pParent;
        }
        pNext = pParent;
    }
    return pNext;
}

9、用两个栈实现队列

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
class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }
    int pop() {
        int res=0;
        if(!stack2.empty())
        {
            res=stack2.top();
            stack2.pop();
        }
        else{
            while(!stack1.empty())
            {
                int temp=stack1.top();
                stack1.pop();
                stack2.push(temp);
            }
            res=stack2.top();
            stack2.pop();
        }
        return res;
    }

private:
    stack<int> stack1;
    stack<int> stack2;
};

10、斐波那契数列。

最容易想到的是递归，但是递归效率低下，栈可能溢出，在面试中最好使用从下往上的循环而不用递归。
利用从下往上循环的DP解法如下：

1
2
3
4
5
6
7
int Fibonacci(int n) {
        vector<int> dp(n+1,0);
        dp[1]=1;
        for(int i=2;i<=n;i++)
            dp[i]=dp[i-1]+dp[i-2];
        return dp[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
int Partition(vector<int>& data, int start, int end)
{
	if (data.empty()  || start<0 || end>data.size() - 1)
		throw new std::exception("Invalid Parameters");

	int index = (int)(rand() % (end - start + 1)) + start;
	swap(data[index], data[start]);

	int pivot = data[start];
	while (start < end){
		while (start < end&&data[end] >= pivot)
			end--;
		data[start] = data[end];
		while (start < end&&data[start] <= pivot)
			start++;
		data[end] = data[start];
	}
	data[start] = pivot;
	return start;
}
int Partition_2(vector<int>& data, int start, int end)//这种划分方法可保证小于的部分相对位置不变
{
	int x = data[end];
	int i = start - 1;
	for (int j = start; j <= end - 1; j++)
	{
		if (data[j] <= x)
		{
			++i;
			swap(data[i], data[j]);
		}
	}
	swap(data[i + 1], data[end]);
	return i + 1;
}
void QuickSort(vector<int>& data, int start, int end)
{
	if (start >= end)
		return;
	int index = Partition(data, start, end);
	if (index>start)
		QuickSort(data, start, index - 1);
	if (index < end)
		QuickSort(data, index + 1, end);
}

11、旋转数组的最小数字

最好利用二分查找，时间效率快。

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
int MinInOrder(vector<int> & rotateArray,int left,int right)
    {
        int small=rotateArray[left];
        for(int i=left+1;i<=right;i++)
            if(rotateArray[i]<small)
                small=rotateArray[i];
        return small;
    }

    int minNumberInRotateArray(vector<int> rotateArray) {
        if(rotateArray.size()<=0)
            return 0;
        int left=0,right=rotateArray.size()-1;
        int mid=left;
        while(rotateArray[left]>=rotateArray[right])
        {
            if(right-left==1)
            {
                mid=right;
                break;
            }
            mid=left+((right-left)>>1);
            //如果left、right、mid指向的三个数字相同，则只能进行顺序查找
            if(rotateArray[left]==rotateArray[right]&&rotateArray[right]==rotateArray[mid])
                return MinInOrder(rotateArray,left,right);
            
            if(rotateArray[left]<=rotateArray[mid])
                left=mid;
            else if(rotateArray[right]>=rotateArray[mid])
                right=mid;
        }
        return rotateArray[mid];
    }

12、矩阵中的路径（回溯法）

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
bool hasPathCore(const char* matrix, int rows, int cols, int row, int col, const char* str, int& pathLength, bool* visited);

bool hasPath(const char* matrix, int rows, int cols, const char* str)
{
    if(matrix == nullptr || rows < 1 || cols < 1 || str == nullptr)
        return false;

    bool *visited = new bool[rows * cols];
    memset(visited, 0, rows * cols);

    int pathLength = 0;
    for(int row = 0; row < rows; ++row)
    {
        for(int col = 0; col < cols; ++col)
        {
            if(hasPathCore(matrix, rows, cols, row, col, str,
                pathLength, visited))
            {
                return true;
            }
        }
    }
    delete[] visited;
    return false;
}

bool hasPathCore(const char* matrix, int rows, int cols, int row,
    int col, const char* str, int& pathLength, bool* visited)
{
    if(str[pathLength] == '\0')
        return true;

    bool hasPath = false;
    if(row >= 0 && row < rows && col >= 0 && col < cols
        && matrix[row * cols + col] == str[pathLength]
        && !visited[row * cols + col])
    {
        ++pathLength;
        visited[row * cols + col] = true;

        hasPath = hasPathCore(matrix, rows, cols, row, col - 1,
            str, pathLength, visited)
            || hasPathCore(matrix, rows, cols, row - 1, col,
                str, pathLength, visited)
            || hasPathCore(matrix, rows, cols, row, col + 1,
                str, pathLength, visited)
            || hasPathCore(matrix, rows, cols, row + 1, col,
                str, pathLength, visited);

        if(!hasPath)
        {
            --pathLength;
            visited[row * cols + col] = false;
        }
    }
    return hasPath;
}

13、机器人的运动范围

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
class Solution {
public:
    int movingCount(int threshold, int rows, int cols)
    {
        if(threshold<0||rows<=0||cols<=0)
            return 0;
        vector<vector<int>> visited(rows,vector<int>(cols,0));
        int cnt=0;
        backTracking(rows,cols,0,0,threshold,cnt,visited);
        return cnt;
    }
private:
    void backTracking(int rows,int cols,int i,int j,const int& threshold,int& cnt,vector<vector<int>>& visited)
    {
        if((digitSum(i)+digitSum(j))>threshold)
            return;
        if(i>=0&&i<rows&&j>=0&&j<cols&&visited[i][j]==0)
        {
            visited[i][j]=1;
            cnt++;
            backTracking(rows,cols,i-1,j,threshold,cnt,visited);
            backTracking(rows,cols,i,j-1,threshold,cnt,visited);
            backTracking(rows,cols,i+1,j,threshold,cnt,visited);
            backTracking(rows,cols,i,j+1,threshold,cnt,visited);
        }
    }
    int digitSum(int i)
    {
        int sum=0;
        while(i)
        {
            sum+=i%10;
            i/=10;
        }
        return sum;
    }
};

14、剪绳子

动态规划和贪婪法

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
//常规动态规划方法,要求至少剪一刀
int maxProductAfterCutting(int length)
{
	if (length < 2)
		return 0;
	if (length == 2)
		return 1;
	if (length == 3)
		return 2;
	vector<int> dp(length+1, 0);
	dp[0] = 0;
	dp[1] = 1;
	dp[2] = 2;
	for (int i = 3; i < length+1; i++)
	{
		int max = i ;
		for (int j = 1; j < i; j++)
		{
			int cur = dp[i - j] * dp[j];
			if (cur > max)
				max = cur;
		}
		dp[i] = max;
	}
	return dp[length];
}
//贪婪法：需要想到数学证明
int maxProductAfterCutting_2(int length)
{
	if (length < 2)
		return 0;
	if (length == 2)
		return 1;
	if (length == 3)
		return 2;

	int timeOf3 = length / 3;
	if (length % 3 == 1)
		timeOf3--;
	int timeOf2 = (length - 3 * timeOf3) / 2;
	return (int)(pow(3, timeOf3))*(pow(2, timeOf2));
}

15、判断二进制数中1 的个数

1
2
3
4
5
6
7
8
9
int  NumberOf1(int n) {
         int cnt=0;
         while(n!=0)
         {
             n=n&(n-1);
             cnt++;
         }
         return cnt;
     }

16、数值的整数次方

注意：本例虽然过了，但是double 型数值的比较建议使用范围比较

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
class Solution {
public:
    double PowerWithAbsexponent(double base,int exponent)
    {
        if(exponent==0)
            return 1;
        if(exponent==1)
            return base;
        double result=PowerWithAbsexponent(base,exponent>>1);
        result*=result;
        if((exponent&0x1)==1)
            result*=base;
        return result;
        
    }
    double Power(double base, int exponent) {
        if(exponent==0)
            return 1;
        if(base==0.0&&exponent<0)
        {
            InvalidInput=true;
            return 0.0;
        }
        int absExponent=(exponent>0)?exponent:(0-exponent);
        double result=PowerWithAbsexponent(base,absExponent);
        if(exponent<0)
            result=1/result;
        return result;
    }
private:
    bool InvalidInput=false;
};

17、打印从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
void Print1ToMaxOfNDigits_2(int n)
{
    if (n <= 0)
        return;

    char* number = new char[n + 1];
    number[n] = '\0';

    for (int i = 0; i < 10; ++i)
    {
        number[0] = i + '0';
        Print1ToMaxOfNDigitsRecursively(number, n, 0);
    }

    delete[] number;
}

void Print1ToMaxOfNDigitsRecursively(char* number, int length, int index)
{
    if (index == length - 1)
    {
        PrintNumber(number);
        return;
    }

    for (int i = 0; i < 10; ++i)
    {
        number[index + 1] = i + '0';
        Print1ToMaxOfNDigitsRecursively(number, length, index + 1);
    }
}

18

18-1、删除链表结点

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
void DeleteNode(ListNode** pListHead, ListNode* pToBeDeleted)
{
    if(!pListHead || !pToBeDeleted)
        return;

    // 要删除的结点不是尾结点
    if(pToBeDeleted->m_pNext != nullptr)
    {
        ListNode* pNext = pToBeDeleted->m_pNext;
        pToBeDeleted->m_nValue = pNext->m_nValue;
        pToBeDeleted->m_pNext = pNext->m_pNext;
 
        delete pNext;
        pNext = nullptr;
    }
    // 链表只有一个结点，删除头结点（也是尾结点）
    else if(*pListHead == pToBeDeleted)
    {
        delete pToBeDeleted;
        pToBeDeleted = nullptr;
        *pListHead = nullptr;
    }
    // 链表中有多个结点，删除尾结点
    else
    {
        ListNode* pNode = *pListHead;
        while(pNode->m_pNext != pToBeDeleted)
        {
            pNode = pNode->m_pNext;            
        }
 
        pNode->m_pNext = nullptr;
        delete pToBeDeleted;
        pToBeDeleted = nullptr;
    }
}

18-2 删除链表中重复结点

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
ListNode* deleteDuplication(ListNode* pHead)
    {
        if(!pHead)
            return NULL;
        ListNode* cur=pHead;
        ListNode* pre=new ListNode(0);
        pre->next=pHead;
        ListNode* next=NULL;
        ListNode* p=pre;
        bool duplicationFlag=false;
        while(cur)
        {
            duplicationFlag=false;
            next=cur->next;
            while(next&&next->val==cur->val)//next存在且和cur重复，就把next往前移
            {
                next=next->next;
                duplicationFlag=true;
            }
            if(!next)//next结束了，说明cur后面所有结点值都和cur相同
            {
                if (duplicationFlag)
					pre->next = NULL;
				cur = next;
            }
            else{
                if(duplicationFlag)
                    pre->next=next;
                else
                    pre=cur;
                cur=next;
            }
        }
        return p->next;
    }

19、正则表达式匹配

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
bool match(const char* str, const char* pattern)
{
    if(str == nullptr || pattern == nullptr)
        return false;

    return matchCore(str, pattern);
}

bool matchCore(const char* str, const char* pattern)
{
    if(*str == '\0' && *pattern == '\0')
        return true;

    if(*str != '\0' && *pattern == '\0')
        return false;

    if(*(pattern + 1) == '*')
    {
        if(*pattern == *str || (*pattern == '.' && *str != '\0'))
            // 进入有限状态机的下一个状态
            return matchCore(str + 1, pattern + 2)
            // 继续留在有限状态机的当前状态 
            || matchCore(str + 1, pattern)
            // 略过一个'*' 
            || matchCore(str, pattern + 2);
        else
            // 略过一个'*'
            return matchCore(str, pattern + 2);
    }

    if(*str == *pattern || (*pattern == '.' && *str != '\0'))
        return matchCore(str + 1, pattern + 1);

    return false;
}

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
bool isNumeric(const char* str)
{
    if(str == nullptr)
        return false;

    bool numeric = scanInteger(&str);

    // 如果出现'.'，接下来是数字的小数部分
    if(*str == '.')
    {
        ++str;

        // 下面一行代码用||的原因：
        // 1. 小数可以没有整数部分，例如.123等于0.123；
        // 2. 小数点后面可以没有数字，例如233.等于233.0；
        // 3. 当然小数点前面和后面可以有数字，例如233.666
        numeric = scanUnsignedInteger(&str) || numeric;
    }

    // 如果出现'e'或者'E'，接下来跟着的是数字的指数部分
    if(*str == 'e' || *str == 'E')
    {
        ++str;

        // 下面一行代码用&&的原因：
        // 1. 当e或E前面没有数字时，整个字符串不能表示数字，例如.e1、e1；
        // 2. 当e或E后面没有整数时，整个字符串不能表示数字，例如12e、12e+5.4
        numeric = numeric && scanInteger(&str);
    }

    return numeric && *str == '\0';
}

bool scanUnsignedInteger(const char** str)
{
    const char* before = *str;
    while(**str != '\0' && **str >= '0' && **str <= '9')
        ++(*str);

    // 当str中存在若干0-9的数字时，返回true
    return *str > before;
}

// 整数的格式可以用[+|-]B表示, 其中B为无符号整数
bool scanInteger(const char** str)
{
    if(**str == '+' || **str == '-')
        ++(*str);
    return scanUnsignedInteger(str);
}

21、调整数组顺序使奇数位于偶数前面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void reOrderArray(vector<int> &array) {
        if(array.empty())
            return;
        vector<int> res;
        for(int i = 0; i < array.size(); i++)
        {
            if((array[i] & 0x1) == 1)
                res.push_back(array[i]);
        }
        for(int i = 0; i < array.size(); i++)
        {
            if((array[i] & 0x1) == 0)
                res.push_back(array[i]);
        }
        array = res;
    }

23、找链表环的入口。

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
ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        if(!pHead)
            return NULL;
        ListNode* slow=pHead->next;
        if(!slow)
            return NULL;
        ListNode* fast=slow->next;
        while(fast&&slow)
        {
            if(fast==slow)
                break;
            slow=slow->next;
            fast=fast->next;
            if(fast)
                fast=fast->next;
        }
        if(!fast)//没有环
            return NULL;
        slow=pHead;//slow回到原点
        while(slow!=fast)
        {
            slow=slow->next;
            fast=fast->next;
        }
        return fast;
    }

24、反转链表

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
ListNode* ReverseList(ListNode* pHead) {
        if(!pHead)
            return NULL;
        ListNode* pre,*cur,*next;
        pre=NULL;
        cur=pHead;
        while(cur)
        {
            next=cur->next;
            cur->next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }
递归：
ListNode* ReverseList(ListNode* pHead) {
        if(!pHead||!pHead->next)
            return pHead;
        ListNode* next=pHead->next;
        pHead->next=NULL;
        ListNode* re=ReverseList(next);
        next->next=pHead;
        return re; 
    }

25、合并两个有序链表

递归：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        if(!pHead1&&!pHead2)
            return NULL;
        if(!pHead1)
            return pHead2;
        if(!pHead2)
            return pHead1;
        
        ListNode* node=NULL;
        if(pHead1->val<pHead2->val)
        {
            node=pHead1;
            node->next=Merge(pHead1->next,pHead2);
        }
        else
        {
            node=pHead2;
            node->next=Merge(pHead1,pHead2->next);
        }
        return node;
    }

26、树的子结构

递归

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
bool HasOrNo(TreeNode* r1, TreeNode* r2)
    {
        if(!r1&&r2)
            return false;
        if(!r2)
            return true;
        if(r1->val!=r2->val)
            return false;
        
        return HasOrNo(r1->left,r2->left)&&HasOrNo(r1->right,r2->right);
    }
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
    {
        if(!pRoot1)
            return false;
        if(!pRoot2)
            return false;
        
        bool flag=false;
        if(pRoot1->val==pRoot2->val)
            flag=HasOrNo(pRoot1,pRoot2);
        if(!flag)
            flag=HasOrNo(pRoot1->left,pRoot2);
        if(!flag)
            flag=HasOrNo(pRoot1->right,pRoot2);
        return flag;
    }

27、二叉树的镜像

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
void Mirror(TreeNode *pRoot) {
        if(!pRoot)
            return;
        TreeNode* left=pRoot->left;
        TreeNode* right=pRoot->right;
        if(left)//has left subtree
        {
            pRoot->right=left;
            if(!right)
                pRoot->left=NULL;
        }
        if(right)
        {
            pRoot->left=right;
            if(!left)
                pRoot->right=NULL;
        }
        Mirror(pRoot->left);
        Mirror(pRoot->right);
    }
//非递归：
void Mirror(TreeNode *pRoot) {
        if(!pRoot)
            return;
        stack<TreeNode*> st;
        st.push(pRoot);
        while(!st.empty())
        {
            TreeNode* temp=st.top();
            TreeNode* t=temp->left;
            temp->left=temp->right;
            temp->right=t;
            
            st.pop();
            if(temp->left)
                st.push(temp->left);
            if(temp->right)
                st.push(temp->right);
        }
    }

28、对称的二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool isSymmetrical(TreeNode* left,TreeNode* right)；
bool isSymmetrical(TreeNode* pRoot)
    {
        if(!pRoot)
            return true;
        return isSymmetrical(pRoot->left,pRoot->right);
    }
    bool isSymmetrical(TreeNode* left,TreeNode* right)
    {
        if(!left&&!right)
            return true;
        if(!left||!right)
            return false;
        if(left->val!=right->val)
            return false;
        return isSymmetrical(left->right,right->left)
             &&isSymmetrical(left->left,right->right);
    }

29、顺时针打印矩阵

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
void PrintMatrixInCircle(vector<vector<int> > &matrix,const int start,vector<int>& res)
    {
        int endX=matrix[0].size()-1-start;
        int endY=matrix.size()-1-start;
        //从左往右
        for(int i=start;i<=endX;i++)
            res.push_back(matrix[start][i]);
        //从上往下，至少有两行的时候才需要
        if(start<endY)
            for(int i=start+1;i<=endY;i++)
                res.push_back(matrix[i][endX]);
        //从右往左，至少两行两列才需要
        if(start<endX&&start<endY)
            for(int i=endX-1;i>=start;i--)
                res.push_back(matrix[endY][i]);
        //从下往上，至少三行两列才需要
        if(start<endX&&start<endY-1)
            for(int i=endY-1;i>=start+1;i--)
                res.push_back(matrix[i][start]);
    }
    vector<int> printMatrix(vector<vector<int> > matrix) {
        vector<int> res;
        if(matrix.size()==0||matrix[0].size()==0)
            return res;
        int start=0;
        while(matrix.size()>start*2&&matrix[0].size()>start*2)
        {
            PrintMatrixInCircle(matrix,start,res);
            start++;
        }
        return res;
    }

30、包含min的栈

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 {
private:
    stack<int> data;
    stack<int> m;
public:
    void push(int value) {
        data.push(value);
        if(m.empty())
            m.push(value);
        else
        {
            if(value<=m.top())
                m.push(value);
        }
    }
    void pop() {
        int value=data.top();
        data.pop();
        if(value==m.top())
            m.pop();
    }
    int top() {
        return data.top();
    }
    int min() {
        return m.top();
    }
};

31、栈的压入弹出序列

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
bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        if(pushV.empty()||popV.empty())
            return false;
        stack<int> data;
        data.push(pushV[0]);
        int i=1,j=0;//i指向pushV下标，j指向popV下标
        while(j<popV.size())
        {
            if(data.top()==popV[j])//弹出数字刚好是栈顶元素
            {
                data.pop();
                j++;
            }
            else{
                bool findFlag=false;
                for(;i<pushV.size();i++)
                {
                    data.push(pushV[i]);
                    if(pushV[i]==popV[j])
                    {
                        findFlag=true;
                        i++;
                        break;
                    }
                }
                if(!findFlag)
                    return false;
            }
        }
        return true;
    }

32、从上到下打印二叉树（即层次遍历，具体代码看上面树的遍历代码）

题目扩展：每一层结点占一行，换行打印

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
61
62
63
64
65
66
67
68
69
70
71
vector<vector<int> > Print(TreeNode* pRoot) {
            vector<vector<int> > res;
            if(!pRoot)
                return res;
            queue<TreeNode*> q;
            TreeNode* lineLast;
            TreeNode* nextLineLast;
            lineLast=nextLineLast=pRoot;
            vector<int> line;
            q.push(pRoot);
            while(!q.empty())
            {
                TreeNode* f=q.front();
                line.push_back(f->val);
                if(f->left)
                {
                    q.push(f->left);
                    nextLineLast=f->left;
                }
                if(f->right)
                {
                    q.push(f->right);
                    nextLineLast=f->right;
                }
                if(f==lineLast)
                {
                    res.push_back(line);
                    line.clear();
                    lineLast=nextLineLast;
                }
                q.pop();
            }
            return res;
        }
扩展二：之字形打印
vector<vector<int> > Print(TreeNode* pRoot) {
        vector<vector<int> > res;
	if (!pRoot)
		return res;
	vector<stack<TreeNode*>> stacks(2);
	int stacksIndex = 0;//stacks[0]从左到右

	stacks[0].push(pRoot);
	vector<int> line;
	while (!stacks[0].empty() || !stacks[1].empty())
	{
		TreeNode* f = stacks[stacksIndex].top();
		stacks[stacksIndex].pop();
		line.push_back(f->val);
		if (stacksIndex == 0)//下一层从右往左
		{
			if (f->right)
				stacks[1].push(f->right);
			if (f->left)
				stacks[1].push(f->left);
		}
		else{
			if (f->left)
				stacks[0].push(f->left);
			if (f->right)
				stacks[0].push(f->right);
		}
		if (stacks[stacksIndex].empty()){
			reverse(line.begin(), line.end());
			res.push_back(line);
			line.clear();
			stacksIndex = 1 - stacksIndex;
		}
	}
	return res;
    }

33、二叉搜索树的后序遍历序列

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
bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.empty())
            return false;
        int root=sequence[sequence.size()-1];//后序遍历中根节点是最后一个
        int i=0;
        for(;i<sequence.size()-1;i++)//找左子树
            if(sequence[i]>root)
                break;
        int j=i;
        for(;j<sequence.size()-1;j++)//找右子树
            if(sequence[j]<root)
                return false;//右子树中如果有比根节点值小的，则返回false
        bool left=true;
        if(i>0)
        {
            vector<int> le(sequence.begin(),sequence.begin()+i);
            left=VerifySquenceOfBST(le);
        }
        bool right=true;
        if(i<sequence.size()-1)
        {
            vector<int> ri(sequence.begin()+i,sequence.end()-1);
            right=VerifySquenceOfBST(ri);
        }
        return left&&right;
    }

34、二叉树中和为某一值的路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void backTracking(TreeNode* root,int expectNum,vector<vector<int> > &res,vector<int> &path)
    {
        path.push_back(root->val);
        if((!root->left)&&(!root->right))
        {
            if(accumulate(path.begin(),path.end(),0)==expectNum)
                res.push_back(path);
        }
        if(root->left)
            backTracking(root->left,expectNum,res,path);
        if(root->right)
            backTracking(root->right,expectNum,res,path);
        path.pop_back();
    }
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        vector<vector<int> > res;
        if(!root)
            return res;
        vector<int> path;
        backTracking(root,expectNumber,res,path);
        return res;
    }

35、复杂链表的复制

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
//1克隆节点
    void CloneNodes(RandomListNode* pHead)
    {
        RandomListNode* cloneNode=pHead;
        while(cloneNode)
        {
            RandomListNode* cc=new RandomListNode(0);
            cc->label=cloneNode->label;
            cc->next=cloneNode->next;
            cc->random=NULL;
            
            cloneNode->next=cc;
            cloneNode=cc->next;
        }
    }
    //2为每个新节点赋值random
    void ConnectRandomNode(RandomListNode* pHead)
    {
        RandomListNode* p=pHead;
        while(p)
        {
            RandomListNode* pp=p->next;
            if(p->random)
                pp->random=p->random->next;
            p=pp->next;
        }
    }
    //3将原链表拆成两个相同链表
    RandomListNode* ReconnectNode(RandomListNode* pHead)
    {
        RandomListNode* p=pHead;
        RandomListNode *cloneHead=NULL,*cloneNode=NULL;
        if(p)
        {
            cloneHead=p->next;
            cloneNode=p->next;
            p->next=cloneNode->next;
            p=p->next;
        }
        while(p)
        {
            cloneNode->next=p->next;
            cloneNode=cloneNode->next;
            p->next=cloneNode->next;
            p=p->next;
        }
        return cloneHead;
    }
    RandomListNode* Clone(RandomListNode* pHead)
    {
        CloneNodes(pHead);
        ConnectRandomNode(pHead);
        return ReconnectNode(pHead);
    }

36、二叉搜索树与双向链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void InOrder(TreeNode* root,TreeNode *&node)//指针的引用
    {
        if(root)
        {
            TreeNode* cur=root;
            InOrder(root->left,node);
            cur->left=node;
            if(node)
                node->right=cur;
            node=cur;
            InOrder(root->right,node);
        }
    }
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        if(!pRootOfTree)
            return NULL;
        TreeNode* node=NULL;
        InOrder(pRootOfTree,node);
        while(node&&node->left)
            node=node->left;
        return node;
    }

37、序列化二叉树

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
//牛客
char* Serialize(TreeNode *root) {
        if(!root)
            return "#,";
        string str;
        str=to_string(root->val);
        str+=",";
        char* left=Serialize(root->left);
        char* right=Serialize(root->right);
        char* res=new char[strlen(left)+strlen(right)+str.size()];
        strcpy(res,str.c_str());
        strcat(res,left);
        strcat(res,right);
        return res;
        
    }
    TreeNode* Deserialize(char *str) {
        return decode(str);
        
    }
private:
    TreeNode* decode(char *&str) {
        if(*str=='#'){
            str+=2;
            return NULL;
        }
        int num = 0;
        while(*str != ',')
            num = num*10 + (*(str++)-'0');
        str++;
        TreeNode *root = new TreeNode(num);
        root->left = decode(str);
        root->right = decode(str);
        return root;
    }
//书上
void Serialize(const BinaryTreeNode* pRoot, ostream& stream)
{
    if(pRoot == nullptr)
    {
        stream << "$,";
        return;
    }

    stream << pRoot->m_nValue << ',';
    Serialize(pRoot->m_pLeft, stream);
    Serialize(pRoot->m_pRight, stream);
}

bool ReadStream(istream& stream, int* number)
{
    if(stream.eof())
        return false;

    char buffer[32];
    buffer[0] = '\0';

    char ch;
    stream >> ch;
    int i = 0;
    while(!stream.eof() && ch != ',')
    {
        buffer[i++] = ch;
        stream >> ch;
    }

    bool isNumeric = false;
    if(i > 0 && buffer[0] != '$')
    {
        *number = atoi(buffer);
        isNumeric = true;
    }

    return isNumeric;
}

void Deserialize(BinaryTreeNode** pRoot, istream& stream)
{
    int number;
    if(ReadStream(stream, &number))
    {
        *pRoot = new BinaryTreeNode();
        (*pRoot)->m_nValue = number;
        (*pRoot)->m_pLeft = nullptr;
        (*pRoot)->m_pRight = nullptr;

        Deserialize(&((*pRoot)->m_pLeft), stream);
        Deserialize(&((*pRoot)->m_pRight), stream);
    }
}

38、字符串的排列

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
void Recursive(int index,string& str,vector<string>& res)
    {
        if(index>=str.size())
        {
            if(find(res.begin(),res.end(),str)==res.end())
                res.push_back(str);
            return;
        }
        for(int i=index;i<str.size();i++)
        {
            swap(str[index],str[i]);
            Recursive(index+1,str,res);
            swap(str[index],str[i]);
        }
    }
    vector<string> Permutation(string str) {
        vector<string> res;
        if(str=="")
            return res;
        Recursive(0,str,res);
        sort(res.begin(),res.end());//保证输出是按字典序排的，若题目不要求可注释
        return res;
    }
扩展：字符串的字符组合
void Recursive(int num, int index, string& str, vector<string>& res,string& s)
{
	if (num <=0)
	{
		if (find(res.begin(), res.end(), s) == res.end())
			res.push_back(s);
		return;
	}
	if (index >= str.size())
		return;
	//把index放入
	s += str[index];
	Recursive(num - 1, index + 1, str, res, s);
	s=s.substr(0, s.size()-1);//去掉最后一个字符，回溯
	//不放如index
	Recursive(num, index + 1, str, res, s);
}
vector<string> Permutation(string str) {
	vector<string> res;
	if (str == "")
		return res;
	sort(str.begin(), str.end());
	string s = "";
	for (int i = 1; i < str.size()+1; i++)//i表示组合中字符个数
		Recursive(i, 0,str, res,s);
	return res;
}

kmp算法实现：

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
int strStr(string haystack, string needle) {
        //使用KMP算法结题，实现KMP算法
        int n=needle.size();
        if(!n)
            return 0;
        vector<int> next=getNextArray(needle);//获取next数组
        int k=-1;//用来标志needle，也代表匹配程度
        for(int i=0;i<haystack.size();i++)
        {
            while(k>-1&&needle[k+1]!=haystack[i])//部分匹配但是接下来的不匹配，就计算往后退的步数，回溯
                k=next[k];
            if(needle[k+1]==haystack[i])//下一位相同，又匹配了一位，k++
                k++;
            if(k==n-1)//完全匹配
                return i-n+1;
        }
        return -1;
        
    }
    //要实现kmp算法，需要先实现针对needle的next数组
    vector<int> getNextArray(string &needle)
    {
        vector<int> next(needle.size(),0);
        next[0]=-1;//-1表示不存在相同最大前缀和最大后缀
        int k=-1;
        for(int i=1;i<needle.size();i++)
        {
            while(k>-1&&needle[k+1]!=needle[i])//如果k>-1并且下一个字符不同，k就往前回溯，找到与当前点相同的之前点
                k=next[k];
            if(needle[k+1]==needle[i])//如果下一个字符相同，k++
                k++;
            next[i]=k;//赋值next数组
        }
        return next;
    }

39、数组中出现次数超过一半的数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int MoreThanHalfNum_Solution(vector<int> numbers) {
        if(numbers.empty())
            return 0;
        if(numbers.size()==1)
            return numbers[0];
        int value=numbers[0],cnt=1;
        for(int i=1;i<numbers.size();i++)
        {
            if(numbers[i]==value)
                cnt++;
            else
            {
                cnt--;
                if(cnt==0)
                {
                    value=numbers[i];
                    cnt=1;
                }
            }
        }
        if(count(numbers.begin(),numbers.end(),value)*2>numbers.size())
            return value;
        return 0;
    }

40、最小的k个数

以下实现使用最大堆，也可用基于红黑树实现的set。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> res;
        if(k>input.size()||k<=0||input.size()<=0)
            return res;
        for(int i=0;i<k;i++)
            res.push_back(input[i]);
        make_heap(res.begin(),res.end());//构造堆
        for(int i=k;i<input.size();i++)
        {
            if(input[i]<res[0])//比堆顶数小
            {
                res.push_back(input[i]);
                push_heap(res.begin(),res.end());
                pop_heap(res.begin(),res.end());
                res.pop_back();
            }
        }
        sort_heap(res.begin(),res.end());
        return res;
    }

41、数据流中的中位数

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
template<typename T> class DynamicArray
{
public:
    void Insert(T num)
    {
        if(((min.size() + max.size()) & 1) == 0)
        {
            if(max.size() > 0 && num < max[0])
            {
                max.push_back(num);
                push_heap(max.begin(), max.end(), less<T>());

                num = max[0];

                pop_heap(max.begin(), max.end(), less<T>());
                max.pop_back();
            }

            min.push_back(num);
            push_heap(min.begin(), min.end(), greater<T>());
        }
        else
        {
            if(min.size() > 0 && min[0] < num)
            {
                min.push_back(num);
                push_heap(min.begin(), min.end(), greater<T>());

                num = min[0];

                pop_heap(min.begin(), min.end(), greater<T>());
                min.pop_back();
            }

            max.push_back(num);
            push_heap(max.begin(), max.end(), less<T>());
        }
    }

    T GetMedian()
    {
        int size = min.size() + max.size();
        if(size == 0)
            throw exception("No numbers are available");

        T median = 0;
        if((size & 1) == 1)
            median = min[0];
        else
            median = (min[0] + max[0]) / 2;

        return median;
    }

private:
    vector<T> min;
    vector<T> max;
};

42、连续子数组的最大和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int FindGreatestSumOfSubArray(vector<int> array) {
        if(array.empty())
            return 0;
        if(array.size()==1)
            return array[0];
        vector<int> dp(array.size(),0);
        dp[0]=array[0];
        int maxSum=dp[0];
        for(int i=1;i<array.size();i++)
        {
            if(dp[i-1]>=0)
            {
                dp[i]=dp[i-1]+array[i];
            }
            else{
                dp[i]=array[i];
            }
            if(dp[i]>maxSum)
                    maxSum=dp[i];
        }
        return maxSum;
    }

43、1~n整数中1出现的次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int NumberOf1Between1AndN_Solution(int n)
    {
        int cnt = 0;
	    for (int i = 1; i <= n; i*=10)
	    {
		    int index = n % (i * 10) / i;//得到i位数
		    if (index > 1)//i位>1
			    cnt += i*(n / (i * 10) + 1);
		    else if (index == 1)//i位==1
			    cnt += i*(n / (i * 10)) + (n%i) + 1;
		    else //i位==0
			    cnt += i*(n / (i * 10));
	}
	return cnt;
    }

44、数字序列中某一位的数字

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
int countOfIntegers(int digits);
int digitAtIndex(int index, int digits);
int beginNumber(int digits);

int digitAtIndex(int index)
{
	if(index < 0)
		return -1;

	int digits = 1;
	while(true)
	{
		int numbers = countOfIntegers(digits);
		if(index < numbers * digits)
			return digitAtIndex(index, digits);

		index -= digits * numbers;
		digits++;
	}

	return -1;
}

int countOfIntegers(int digits)
{
	if(digits == 1)
		return 10;

	int count = (int) std::pow(10, digits - 1);
	return 9 * count;
}

int digitAtIndex(int index, int digits)
{
	int number = beginNumber(digits) + index / digits;
	int indexFromRight = digits - index % digits;
	for(int i = 1; i < indexFromRight; ++i)
		number /= 10;
	return number % 10;
}

int beginNumber(int digits)
{
	if(digits == 1)
		return 0;

	return (int) std::pow(10, digits - 1);
}

45、把数组排成最小的数

1
2
3
4
5
6
7
8
9
10
11
string PrintMinNumber(vector<int> numbers) {
        vector<string> stringNums;
        for(int i=0;i<numbers.size();i++)
            stringNums.push_back(to_string(numbers[i]));
        sort(stringNums.begin(),stringNums.end(),[](string s1,string s2)
             {return ((s1+s2).compare(s2+s1)<0) ? true : false; });
        string res="";
        for(int i=0;i<stringNums.size();i++)
            res+=stringNums[i];
        return res;
    }

46、把数字翻译成字符串

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
//dp
int GetTranslationCount(const string& number);

int GetTranslationCount(int number)
{
    if(number < 0)
        return 0;

    string numberInString = to_string(number);
    return GetTranslationCount(numberInString);
}

int GetTranslationCount(const string& number)
{
    int length = number.length();
    int* counts = new int[length];
    int count = 0;

    for(int i = length - 1; i >= 0; --i)
    {
        count = 0;
         if(i < length - 1)
               count = counts[i + 1];
         else
               count = 1;

        if(i < length - 1)
        {
            int digit1 = number[i] - '0';
            int digit2 = number[i + 1] - '0';
            int converted = digit1 * 10 + digit2;
            if(converted >= 10 && converted <= 25)
            {
                if(i < length - 2)
                    count += counts[i + 2];
                else
                    count += 1;
            }
        }

        counts[i] = count;
    }

    count = counts[0];
    delete[] counts;

    return count;
}

47、礼物的最大价值

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
int getMaxValue_solution1(const int* values, int rows, int cols)
{
    if(values == nullptr || rows <= 0 || cols <= 0)
        return 0;

    int** maxValues = new int*[rows];
    for(int i = 0; i < rows; ++i)
        maxValues[i] = new int[cols];

    for(int i = 0; i < rows; ++i)
    {
        for(int j = 0; j < cols; ++j)
        {
            int left = 0;
            int up = 0;

            if(i > 0)
                up = maxValues[i - 1][j];

            if(j > 0)
                left = maxValues[i][j - 1];

            maxValues[i][j] = std::max(left, up) + values[i * cols + j];
        }
    }

    int maxValue = maxValues[rows - 1][cols - 1];

    for(int i = 0; i < rows; ++i)
        delete[] maxValues[i];
    delete[] maxValues;

    return maxValue;
}

48.、最长不包含重复字符的子字符串

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
int longestSubstringWithoutDuplication_2(const std::string& str)
{
    int curLength = 0;
    int maxLength = 0;

    int* position = new int[26];
    for(int i = 0; i < 26; ++i)
        position[i] = -1;

    for(int i = 0; i < str.length(); ++i)
    {
        int prevIndex = position[str[i] - 'a'];
        if(prevIndex < 0 || i - prevIndex > curLength)
            ++curLength;
        else
        {
            if(curLength > maxLength)
                maxLength = curLength;

            curLength = i - prevIndex;
        }
        position[str[i] - 'a'] = i;
    }

    if(curLength > maxLength)
        maxLength = curLength;

    delete[] position;
    return maxLength;
}

49、丑数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int Min(int n1,int n2,int n3){
        return n1<=n2?(n1<=n3?n1:n3):(n2<=n3?n2:n3);
    }
    int GetUglyNumber_Solution(int index) {
        if(index<=0)
            return 0;
        vector<int> uglyNums;
        uglyNums.push_back(1);
        int multiple2=0,multiple3=0,multiple5=0;
        while(uglyNums.size()<index)
        {
            int tempNum=Min(2*uglyNums[multiple2],3*uglyNums[multiple3],5*uglyNums[multiple5]);
            uglyNums.push_back(tempNum);
            while(2*uglyNums[multiple2]<=uglyNums[uglyNums.size()-1])
                multiple2++;
            while(3*uglyNums[multiple3]<=uglyNums[uglyNums.size()-1])
                multiple3++;
            while(5*uglyNums[multiple5]<=uglyNums[uglyNums.size()-1])
                multiple5++;
        }
        return uglyNums[uglyNums.size()-1];
    }

50、第一次只出现一次的字符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int FirstNotRepeatingChar(string str) {
        map<char,int> charAndCnt;
        map<char,int> charFirstIndex;
        for(int i=0;i<str.size();i++)
        {
            if(charAndCnt[str[i]]==0)//第一次出现
                charFirstIndex[str[i]]=i;
            charAndCnt[str[i]]++;
        }
        int firstCharIndex=str.size()-1;
        for(auto p:charAndCnt)
        {
            if(p.second==1)
                if(charFirstIndex[p.first]<firstCharIndex)
                    firstCharIndex=charFirstIndex[p.first];
        }
        return firstCharIndex;
    }

50_2、字符流中出现一次的第一个字符

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
class Solution
{
public:
    Solution():index(0),occurence(256,-1){}
  //Insert one char from stringstream
    void Insert(char ch)
    {
        if(occurence[ch]==-1)
             occurence[ch]=index;
        else if(occurence[ch]>=0)
            occurence[ch]=-2;
        index++;
    }
  //return the first appearence once char in current stringstream
    char FirstAppearingOnce()
    {
        char ch='\0';
        int minIndex=index;
        for(int i=0;i<256;i++)
            if(occurence[i]>=0&&occurence[i]<=minIndex)
            {
                minIndex=occurence[i];
                ch=static_cast<char>(i);
            }
        if(minIndex==index)
            return '#';
        return ch;
    }
private:
    vector<int> occurence;
    int index;
};

51、数组中的逆序对

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
int InversePairs(vector<int> data) {
        vector<int> temp(data);
        long long cnt=MergeSort(data,temp,0,data.size()-1);
        return cnt%1000000007;
    }
    long long MergeSort(vector<int>& data,vector<int>& temp,int left,int right){
        if(left==right)
        {
            temp[left]=data[left];
            return 0;
        }
        
        int mid=left+((right-left)>>1);
        long long leftCnt=MergeSort(temp,data,left,mid);//temp和data需要调换位置，使递归的data部分有序
        long long rightCnt=MergeSort(temp,data,mid+1,right);
        int cnt=0;
        //开辟辅助空间，对左右两半数组进行归并排序，在归并排序的过程中统计逆序次数
        int leftIndex=mid,rightIndex=right,tempIndex=right;
        while(leftIndex>=left&&rightIndex>=mid+1)
        {
            if(data[leftIndex]>data[rightIndex])//左边大，出现逆序对
            {
                cnt+=rightIndex-mid;
                temp[tempIndex--]=data[leftIndex--];
                if(cnt>1000000007)
                    cnt=cnt%1000000007;
            }
            else{
                temp[tempIndex--]=data[rightIndex--];
            }
        }
        while(leftIndex>=left)//右半边结束了
            temp[tempIndex--]=data[leftIndex--];
        while(rightIndex>=mid+1)
            temp[tempIndex--]=data[rightIndex--];

        return cnt+leftCnt+rightCnt;
    }

52、两个链表的第一个公共结点

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
ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        if(!pHead1||!pHead2)
            return 0;
        int length1=1,length2=1;
        ListNode* p1=pHead1,*p2=pHead2;
        while(p1->next)
        {
            length1++;
            p1=p1->next;
        }
        while(p2->next)
        {
            length2++;
            p2=p2->next;
        }
        if(p1!=p2)
            return NULL;
        p1=pHead1;
        p2=pHead2;
        int n=(length1>length2)?(length1-length2):(length2-length1);
        while(n)
        {
            if(length1>length2)
                p1=p1->next;
            else
                p2=p2->next;
            n--;
        }
        while(p1!=p2){
            p1=p1->next;
            p2=p2->next;
        }
        return p1;
    }

53、数字在排序数组中出现的次数

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
int GetNumberOfK(vector<int> data ,int k) {
        if(data.size()<=0)
            return 0;
        int cnt=0;
        int first =getFirst(data,0,data.size()-1,k);
        int last=getLast(data,0,data.size()-1,k);
        if(first>-1&&last>-1)
            cnt=last-first+1;
        return cnt;
    }
    int getFirst(vector<int>& data,int start,int end,int k)
    {
        if(start>end)
            return -1;
        int mid=start+((end-start)>>1);
        int midData=data[mid];
        if(midData==k)
        {
            if((mid>0&&data[mid-1]!=k)||mid==0)
                return mid;
            else
                end=mid-1;
        }
        else if(midData>k)
            end=mid-1;
        else
            start=mid+1;
        return getFirst(data,start,end,k);
    }
    int getLast(vector<int>& data,int start,int end,int k)
    {
        if(start>end)
            return -1;
        int mid=start+((end-start)>>1);
        int midData=data[mid];
        if(midData==k)
        {
            if((mid<data.size()-1&&data[mid+1]!=k)||mid==data.size()-1)
                return mid;
            else
                start=mid+1;
        }
        else if(midData<k)
            start=mid+1;
        else
            end=mid-1;
        return getLast(data,start,end,k);
    }

53_2：0~n-1中缺失的数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int GetMissingNumber(const int* numbers, int length)
{
    if(numbers == nullptr || length <= 0)
        return -1;
    int left = 0;
    int right = length - 1;
    while(left <= right)
    {
        int middle = (right + left) >> 1;
        if(numbers[middle] != middle)
        {
            if(middle == 0 || numbers[middle - 1] == middle - 1)
                return middle;
            right = middle - 1;
        }
        else
            left = middle + 1;
    }
    if(left == length)
        return length;
    // 无效的输入，比如数组不是按要求排序的，
    // 或者有数字不在0到n-1范围之内
    return -1;
}

54、二叉搜索树的第k大节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
TreeNode* Inorder(TreeNode* root,int& k){
        TreeNode* target=NULL;
        if(root)
        {
            target=Inorder(root->left,k);
            
            if(!target)
            {
                if(k==1)
                    target=root;
                else
                    k--;
            }
            if(!target)
                target=Inorder(root->right,k);
        }
        return target;
    }
    TreeNode* KthNode(TreeNode* pRoot, int k)
    {
        if(k<=0||!pRoot)
            return NULL;
        return Inorder(pRoot,k);
    }

55、二叉树的深度

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
int TreeDepth(TreeNode* pRoot)
    {
        if(!pRoot)
            return 0;
        int left=TreeDepth(pRoot->left);
        int right=TreeDepth(pRoot->right);
        return (left>right)?(left+1):(right+1);
    }
判断是否是平衡二叉树：
bool IsBalanced_Solution(TreeNode* pRoot) {
        int depth=0;
        return JudgeBalanced(pRoot,depth);
    }
   bool JudgeBalanced(TreeNode* root,int & depth)
    {
        if(!root)
        {
            depth=0;
            return true;
        }
        int left,right;
        if(JudgeBalanced(root->left,left)&&JudgeBalanced(root->right,right))
        {
            int diff=left-right;
            if(diff<=1&&diff>=-1)
            {
                depth=(left>right)?(left+1):(right+1);
                return true;
            }
        }
        return false;
    }

56_1：数组中只出现一次的两个数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        if(data.size()<=0)
            return;
        int ORResult=0;
        for(auto i:data)
            ORResult=ORResult^i;
        int n=1;
        while(!(ORResult&n))
            n=n<<1;
        *num1=*num2=0;
        for(int i:data)
        {
            if(i&n)
                *num1^=i;
            else
                *num2^=i;
        }
    }

56_2：数组中唯一只出现一次的数字，其他数字出现三次

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
int FindNumberAppearingOnce(int numbers[], int length)
{
    if(numbers == nullptr || length <= 0)
        throw new std::exception("Invalid input.");

    int bitSum[32] = {0};
    for(int i = 0; i < length; ++i)
    {
        int bitMask = 1;
        for(int j = 31; j >= 0; --j)
        {
            int bit = numbers[i] & bitMask;
            if(bit != 0)
                bitSum[j] += 1;

            bitMask = bitMask << 1;
        }
    }

    int result = 0;
    for(int i = 0; i < 32; ++i)
    {
        result = result << 1;
        result += bitSum[i] % 3;
    }

    return result;
}

57_1、和为s的两个数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        vector<int> res;
        if(array.size()<=0)
            return res;
        int left=0,right=array.size()-1;
        while(left<=right)
        {
            int data=array[left];
            while(data+array[right]>sum)
                right--;
            if(data+array[right]==sum)
            {
                res.push_back(data);
                res.push_back(array[right]);
                return res;
            }
            left++;
        }
        return res;
    }

57_2、和为s的连续正数序列

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
vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int> > res;
        if(sum<3)
            return res;
        int begin=1,last=begin+1,finish=(sum>>1)+1;
        int curSum=begin+last;
        while(begin<finish)
        {
            if(curSum==sum)
            {
                vector<int> temp;
                for(int i=begin;i<=last;i++)
                    temp.push_back(i);
                res.push_back(temp);
                last++;
                curSum+=last;
            }
            else if(curSum>sum)
            {
                curSum-=begin;
                begin++;
            }
            else if(curSum<sum)
            {
                last++;
                curSum+=last;
            }
        }
        return res;
    }

58_1、翻转单词顺序

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
string ReverseSentence(string str) {
        if(str=="")
            return str;
        ReverseString(str,0,str.size()-1);//总体逆序
        int i=0,j=0;
        for(int i=0;i<str.size();i++)
        {
            if(str[i]==' ')
            {
                ReverseString(str,j,i-1);
                j=i+1;
            }
            else if(i==str.size()-1)
                ReverseString(str,j,i);
        }
        return str;
    }
    void ReverseString(string & str,int start,int end){
        while(start<end)
        {
            char c=str[start];
            str[start]=str[end];
            str[end]=c;
            start++;
            end--;
        }
    }

58_2：左旋转字符串

1
2
3
4
5
6
7
8
9
10
11
//ReverseString方法与上题相同
string LeftRotateString(string str, int n) {
        if(str.size()!=0&&n>str.size())
            n=n%str.size();
        if(str.size()<=0||n<=0)
            return str;
        ReverseString(str,0,n-1);
        ReverseString(str,n,str.size()-1);
        ReverseString(str,0,str.size()-1);
        return str;
    }

59_1、滑动窗口的最大值

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
vector<int> maxInWindows(const vector<int>& num, unsigned int size)
    {
        vector<int> res;
        if(num.size()<=0||size==0||size>num.size())
            return res;
        if(size==1)
            return num;
        int maxIndex=0;
        for(int i=0;i<size;i++)
            if(num[i]>num[maxIndex])
                maxIndex=i;
        res.push_back(num[maxIndex]);
        for(int i=1;i<num.size()-size+1;i++)
        {
            if(maxIndex<i)
            {
                maxIndex=i;
                for(int j=0;j<size;j++)
                    if(num[i+j]>num[maxIndex])
                        maxIndex=i+j;
            }
            else if(maxIndex>=i&&num[i+size-1]>=num[maxIndex])
                maxIndex=i+size-1;
            res.push_back(num[maxIndex]);
        }
        return res;
    }

60、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
void PrintProbability_Solution2(int number)
{
    if(number < 1)
        return;

    int* pProbabilities[2];
    pProbabilities[0] = new int[g_maxValue * number + 1];
    pProbabilities[1] = new int[g_maxValue * number + 1];
    for(int i = 0; i < g_maxValue * number + 1; ++i)
    {
        pProbabilities[0][i] = 0;
        pProbabilities[1][i] = 0;
    }
 
    int flag = 0;
    for (int i = 1; i <= g_maxValue; ++i) 
        pProbabilities[flag][i] = 1; 
    
    for (int k = 2; k <= number; ++k) 
    {
        for(int i = 0; i < k; ++i)
            pProbabilities[1 - flag][i] = 0;

        for (int i = k; i <= g_maxValue * k; ++i) 
        {
            pProbabilities[1 - flag][i] = 0;
            for(int j = 1; j <= i && j <= g_maxValue; ++j) 
                pProbabilities[1 - flag][i] += pProbabilities[flag][i - j];
        }
 
        flag = 1 - flag;
    }
 
    double total = pow((double)g_maxValue, number);
    for(int i = number; i <= g_maxValue * number; ++i)
    {
        double ratio = (double)pProbabilities[flag][i] / total;
        printf("%d: %e\n", i, ratio);
    }
 
    delete[] pProbabilities[0];
    delete[] pProbabilities[1];
}

61、扑克牌中的顺子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool IsContinuous( vector<int> numbers ) {
        if(numbers.size()!=5)
            return false;
        sort(numbers.begin(),numbers.end());
        int zeroCnt=0;
        int ZeroNeededCnt=0;
        for(int i=0;i<5;i++)
        {
            if(i>=1&&numbers[i]==numbers[i-1]&&numbers[i]!=0)//有对子
                return false;
            if(numbers[i]==0)
                zeroCnt++;
            if(i>=1&&numbers[i-1]!=0&&numbers[i]-numbers[i-1]>1)//计算需要用大小王代替的个数
                ZeroNeededCnt+=numbers[i]-numbers[i-1]-1;
        }
        if(zeroCnt>=ZeroNeededCnt)
            return true;
        return false;
    }

62、圆圈中最后剩下的数字（约瑟夫环）

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
//经典环状链表解决
int LastRemaining_Solution(int n, int m)
    {
        if(n<1||m<1)
            return -1;
        list<int> numbers;
        for(int i=0;i<n;i++)
            numbers.push_back(i);
        list<int>::iterator cur=numbers.begin();
        while(numbers.size()>1)
        {
            for (int i = 1; i < m; i++)
			{
				cur++;
				if (cur == numbers.end())
					cur = numbers.begin();
			}	
			cur = numbers.erase(cur);
			if (cur == numbers.end())
				cur = numbers.begin();
        }
        return *cur;
    }
//运用数学的解法
int LastRemaining_Solution(int n, int m)
    {
        if(n<1||m<1)
            return -1;
        int last=0;
        for(int i=2;i<=n;i++)
            last=(last+m)%i;
        return last;
    }

63、股票的最大利润

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int MaxDiff(const int* numbers, unsigned length)
{
    if(numbers == nullptr && length < 2)
        return 0;

    int min = numbers[0];
    int maxDiff = numbers[1] - min;

    for(int i = 2; i < length; ++i)
    {
        if(numbers[i - 1] < min)
            min = numbers[i - 1];

        int currentDiff = numbers[i] - min;
        if(currentDiff > maxDiff)
            maxDiff = currentDiff;
    }

    return maxDiff;
}

64、求1+2+3+……+n

1
2
3
4
5
int Sum_Solution(int n) {
        int sum=n;
        sum&&(sum+=Sum_Solution(n-1));
        return sum;
    }

65、不用加减乘除做加法

1
2
3
4
5
6
7
8
9
10
11
12
int Add(int num1, int num2)
    {
        int sum,carry;
        while(num2!=0)
        {
            sum=num1^num2;
            carry=(num1&num2)<<1;
            num1=sum;
            num2=carry;
        }
        return num1;
    }

66、构建乘积数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> multiply(const vector<int>& A) {
        vector<int> B;
        if(A.size()<=0)
            return B;
        for(int i=0;i<A.size();i++)
            B.push_back(1);
        vector<int> C(A.size(),1),D(A.size(),1);
        for(int i=1;i<A.size();i++)
        {
            C[i]=C[i-1]*A[i-1];
            D[D.size()-1-i]=D[D.size()-i]*A[A.size()-i];
        }
        for(int i=0;i<B.size();i++)
            B[i]=C[i]*D[i];
        return B;
    }

67、字符串转换成数字

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
class Solution {
public:
    int StrToInt(string str) {
        if(str=="")
        {
            inputStatus=inputInvalid;
            return 0;
        }
        bool minus=false;
        if(str[0]=='+')
            str=str.substr(1);
        else if(str[0]=='-')
        {
            minus=true;
            str=str.substr(1);
        }
        long long num=StrToInt(str,minus);
        return (int)num;
        
    }
 private:
    long long StrToInt(string& str,bool minus)
    {
        long long num=0;
        for(int i=0;i<str.size();i++)
        {
            if(str[i]>='0'&&str[i]<='9')
                num=num*10+(str[i]-'0');
            else{
                inputStatus=inputInvalid;
                return 0;
            }
            if((!minus&&num>0x7fffffff)||(minus&&num<(signed int)0x80000000))
            {
                num=0;
                break;
            }
        }
        if(minus)
            num=0-num;
        return num;
    }
    enum Status{inputInvalid=0,inputValid};//记录输入是否有错
    int inputStatus=inputValid;
};

68、二叉树公共父节点

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
bool GetNodePath(TreeNode* root, TreeNode* node, vector<TreeNode*>& path){
	if (root == node)
		return true;
	path.push_back(root);
	bool found = false;
	if (!found&&root->left)
		found = GetNodePath(root->left, node, path);
	if (!found&&root->right)
		found = GetNodePath(root->right, node, path);
	if (!found)
		path.pop_back();
	return found;
}

TreeNode* GetLastCommonNode(vector<TreeNode*> &path1, vector<TreeNode*> &path2){
	TreeNode *last = NULL;
	int i = 0, j = 0;
	while (i < path1.size() && j < path2.size()){
		if (path1[i] == path2[j])
			last = path1[i];
		i++;
		j++;
	}
	return last;
}

四个string函数

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
int my_strlen(const char* str)
{
	assert(str != NULL);
	int len = 0;
	while (*str)
	{
		len++;
		str++;
	}
	return len;
}
int my_strcmp(const char* str1, const char* str2)
{
	assert(str1 != NULL&&str2 != NULL);
	int ret = 0;
	while (*str1 && !(ret=*str1-*str2))
	{
		str1++;
		str2++;
	}
	if (ret < 0)
		return -1;
	else if (ret > 0)
		return 1;
	return 0;
}

char * my_strcat(char* strDest, const char * strSrc)
{
	char *add = strDest;
	assert((strDest != NULL) && (strSrc != NULL));
	while (*strDest)
		strDest++;
	while (*strDest++ = *strSrc++);
	//*strDest = '\0';
	return add;

}

char *my_strcpy(char *strDes, const char* strSrc)
{
	assert((strDes != NULL) && (strSrc != NULL));
	char *add = strDes;
	while (*strSrc)
	{
		*strDes = *strSrc;
		strDes++;
		strSrc++;
	}
	return add;
}

四个图算法

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
//迪杰斯特拉算法
void ShortestPath_DJS(vector<vector<int>>& dis, int v0){
	vector<int> visited(dis.size(), 0);
	vector<int> shortestDis(dis.size(), INT_MAX);
	vector<int> path(dis.size(),-1);

	//初始化
	for (int i = 0; i < dis.size(); i++){
		if (dis[v0][i] < INT_MAX){
			shortestDis[i] = dis[v0][i];
		}
	}

	shortestDis[v0] = 0;
	visited[v0] = 1;
	int v;
	// 主循环
	for (int i = 0; i < dis.size(); i++){
		if (i != v0){
			int min = INT_MAX;
			for (int w = 0; w < dis.size(); w++){
				if (!visited[w])
					if (shortestDis[w]<min){
						v = w;
						min = shortestDis[w];
					}
			}

			visited[v] = 1;
			// 更新
			for (int w = 0; w < dis.size(); w++){
				if (!visited[w] && dis[v][w] != INT_MAX&& min + dis[v][w] < shortestDis[w])
				{
					shortestDis[w] = min + dis[v][w];
					path[w] = v;
				}
			}
		}
	}

	//输出
	for (int i = 0; i < dis.size(); i++){
		if (i != v0){
			if (shortestDis[i] == INT_MAX)
				cout << v0 << "to" << i << ": no path" << endl;
			else
			{
				cout << v0 << "to" << i << ":" << shortestDis[i] << " path:0 ";
				int j = i;
				vector<int> p;
				while (j != -1){
					p.push_back(j);
					j = path[j];
				}
				while (!p.empty())
				{
					cout << p[p.size() - 1] << " ";
					p.pop_back();
				}
				cout << endl;
			}
		}
	}

}

vector<vector<int>> dis2 = {
	{ 0, 4, 11 },
	{ 6, 0, 2 },
	{3, INT_MAX, 0}
};
//弗洛伊德 ，其实 动规
void ShortestPath_FLOYD(vector<vector<int>>& dis2){
	int n = dis2.size();
	vector<vector<int>> path(n, vector<int>(n,-1));//path[i][j]表示从i到j的最短路径之前的一个端点，-1表示两点直连
	//dp[i][j][k]存的是从j到k中间顶点序号不超过i-1的最短路径
	vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(n, vector<int>(n)));
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			dp[0][i][j] = dis2[i][j];

	//动规求解，递推公式如下
	for (int i = 1; i < n + 1; i++){
		for (int j = 0; j < n; j++){
			for (int k = 0; k < n; k++){
				{
					int t = dp[i - 1][j][i - 1] + dp[i - 1][i - 1][k];
					dp[i][j][k] = dp[i - 1][j][k] > t ? t : dp[i - 1][j][k];
					if (t < dp[i - 1][j][k])
					{
						path[j][k] = i - 1;
					}
				}
			}
		}
	}

	// 输出
	cout << "shortest distance: " << endl;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
			cout<<dp[n][i][j]<<" ";
		cout << endl;
	}
	cout << "path: " << endl;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
			cout << path[i][j] << " ";
		cout << endl;
	}
}


vector<vector<int>> dis3= {
	{ INT_MAX,6,1,5,INT_MAX,INT_MAX },
	{ 6,INT_MAX,5,INT_MAX,3,INT_MAX},
	{ 1,5,INT_MAX,5,6,4},
	{ 5,INT_MAX,5,INT_MAX,INT_MAX,2 },
	{ INT_MAX,3,6,INT_MAX,INT_MAX,6 },
	{ INT_MAX,INT_MAX,4,2,6,INT_MAX }
};

//普里姆算法的时间复杂度 邻接矩阵：v2  邻接表：elogv，边数多选择普里姆
void MST_PRIM(vector<vector<int>>& dis,int v0){
	// 初始化辅助数组
	vector<vector<int>> closeEdge(dis.size(),vector<int>(2,-1));
	for (int i = 0; i < dis.size(); i++){
		{
			if (i != v0){
				closeEdge[i][0] = v0;
				closeEdge[i][1] = dis3[v0][i];
			}
		}
	}
	closeEdge[v0][1] = 0;//0表示节点v0被放入S集合中

	for (int i = 0; i < dis.size(); i++){
		if (i != v0){
			int min = INT_MAX;
			int index;
			int k;
			for (int j = 0; j < dis.size(); j++){
				if (closeEdge[j][1]>0 && closeEdge[j][1] < min){
					min = closeEdge[j][1];
					index = closeEdge[j][0];
					k = j;
				}
			}

			cout << index<<" to "<< k << endl;
			closeEdge[k][1] = 0;
			for (int j = 0; j < dis.size(); j++){
				if (closeEdge[j][1] > dis[k][j])
				{
					closeEdge[j][0] = k;
					closeEdge[j][1] = dis[k][j];
				}
			}
		}
	}

}

//克鲁斯卡尔，对边按照权重排序，eloge，边数少选择这个
struct Edge{
	int weight;
	int start;
	int end;
};

void MST_KRUSKAL(vector<vector<int>>& dis){
	//边初始化并按边长排序
	vector<Edge> edges;
	for (int i = 0; i < dis.size(); i++){
		for (int j = i+1; j < dis.size(); j++){
			if (dis[i][j] != INT_MAX){
				Edge t = { dis[i][j], i, j };
				edges.push_back(t);
			}
		}
	}
	sort(edges.begin(), edges.end(), [](Edge& e1, Edge& e2){
		return e1.weight < e2.weight;
	});

	//初始化集合，同一个集合中的数字代表是最小值
	vector<int> father(dis.size());
	for (int i = 0; i < dis.size(); i++)
		father[i] = i;
	
	for (int i = 0; i < edges.size(); i++){
		if (father[edges[i].start] != father[edges[i].end]){
			cout << "get edge: " << edges[i].start << " to " << edges[i].end << endl;
			//合并集合
			int min = father[edges[i].start] > father[edges[i].end] ? father[edges[i].end] : father[edges[i].start];
			int max = father[edges[i].start] < father[edges[i].end] ? father[edges[i].end] : father[edges[i].start];
			for (int i = 0; i < dis.size(); i++)
			{
				if (father[i] == max){
					father[i] = min;
				}
			}
		}
	}
}

常用排序算法总结

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
//冒泡排序
int* bubbleSort(int* A, int n) {
        // write code here
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                if(A[i]>A[j])
                {
                    int t=A[i];
                    A[i]=A[j];
                    A[j]=t;
                }
            }
        }
        return A;
    }
//选择排序
int* selectionSort(int* A, int n) {
        // write code here
        for(int i=0;i<n;i++)
        {
            int k=i;
            for(int j=i+1;j<n;j++)
            {
                if(A[k]>A[j])
                    k=j;
            }
            int t=A[i];
            A[i]=A[k];
            A[k]=t;
        }
        return A;
    }
//插入排序：
int* insertionSort(int* A, int n) {
        // write code here
        for(int i=0;i<n;i++)
        {
            //寻找插入点
            int j;
            for(j=i-1;j>=0;j--)
            {
                if(A[i]>=A[j])
                    break;
            }
            //插入
            int t=A[i];
            for(int k=i;k>j+1;k--)
                A[k]=A[k-1];
            A[j+1]=t;
        }
        return A;
    }
//归并：
int* mergeSort(int* A, int n) {
        // write code here
        mergeSortCore(A,0,n-1);
        return A;
    }
 private:
    void mergeSortCore(int* &A,int startIndex,int endIndex){
        if(endIndex==startIndex)
            return ;
        int mid=startIndex+((endIndex-startIndex)>>1);
        //分别处理左右，分治
        mergeSortCore(A,startIndex,mid);
        mergeSortCore(A,mid+1,endIndex);
        //合并
        Merge(A,startIndex,mid,endIndex);
    }
    
    void Merge(int* &A,int left,int mid,int right){
        int temp[right-left+1];
        int rbegin=mid+1;
        int l=left;
        int i=0;
        while(left<=mid&&rbegin<=right)
        {
            if(A[left]<=A[rbegin])
                temp[i++]=A[left++];
            else
                temp[i++]=A[rbegin++];
        }
        while(rbegin<=right)
            temp[i++]=A[rbegin++];
        while(left<=mid)
            temp[i++]=A[left++];
        for(int j = 0; j < i; j++)
            A[l+j] = temp[j];
    }
//快速排序：
int* quickSort(int* A, int n) {
        // write code here
        if(!A)
            return NULL;
        quickSort(A,0,n-1);
        return A;
    }
private:
    void quickSort(int* &A,int start,int end)
    {
        if(start>=end)
            return;
        int index=Partition(A,start,end);
        if(index>start)
            quickSort(A,start,index-1);
        if(index<end)
            quickSort(A,index+1,end);
    }
    
    int Partition(int* &A,int start,int end){
        int mid=start+((end-start)>>1);
        int index=A[mid]<A[start]?(A[mid]<A[end]?mid:end):(A[start]<A[end]?start:end);
        swap(A[index],A[start]);
        int p=A[start];
        while(start<end)
        {
            //从后往前找到第一个比p小的数字，说明该交换了
            while(start<end&&A[end]>=p)
                end--;
            A[start]=A[end];
            //从前往后找到第一个比p大的数字
            while(start<end&&A[start]<=p)
                start++;
            A[end]=A[start];
        }
        A[start]=p;
        return start;
    }

//堆排序：
int* heapSort(int* A, int n) {
        // write code here
        //构造最大堆
        make_heap(A,0,n-1);
        //堆排序
        for(int i=n-1;i>0;i--)
        {
            int t=A[0];
            A[0]=A[i];
            A[i]=t;
            make_heap(A,0,i-1);
        }
        return A;
    }
 private:
    //构造大根堆
    void make_heap(int* A,int start ,int end)
    {
        for(int i=1;i<=end;i++)
        {
            int index=i;
            int parentIndex=(i-1)/2;//父节点下标
            while(index-1>=0)//向上调整，直到头结点
            {
                if(A[parentIndex]<A[index])
                {
                    int t=A[parentIndex];
                    A[parentIndex]=A[index];
                    A[index]=t;
                    index=parentIndex;
                    parentIndex=(parentIndex-1)/2;
                }
                else
                    break;
            }
        }
    }
//希尔排序：
int* shellSort(int* A, int n) {
        // write code here
        if(!A|| n<2)
            return nullptr;
        for(int inc = n/2;inc>0;inc = inc/2){//inc是步伐长度
            int index=0;
            for(int i=inc;i<n;i++)
            {
                index=i;
                while(index>0){
                    if(index-inc>=0&&A[index]<A[index-inc])
                    {
                        int t=A[index];
                        A[index]=A[index-inc];
                        A[index-inc]=t;
                        index-=inc;
                    }
                    else
                        break;
                }
            }
        }
         return A;
    }