JZ-C-50

剑指offer第五十题:树中两个结点的最低公共祖先:这里的树是普通树,且没有指向父结点的指针。

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
//============================================================================
// Name        : JZ-C-50.cpp
// Author      : Laughing_Lz
// Version     :
// Copyright   : All Right Reserved
// Description : 树中两个结点的最低公共祖先:这里的树是普通树,且没有指向父结点的指针。
//============================================================================
 
#include <iostream>
#include <stdio.h>
#include "Tree.h"
#include <list>
using namespace std;
 
using namespace std;
/**
 * 获得从树的根结点到某结点的路径
 */
bool GetNodePath(TreeNode* pRoot, TreeNode* pNode, list<TreeNode*>& path) {
    if (pRoot == pNode)
        return true;
 
    path.push_back(pRoot);
 
    bool found = false;
 
    vector<TreeNode*>::iterator i = pRoot->m_vChildren.begin(); //这里的树为普通树,甚至不是二叉树。所以这里按照前序遍历子树即可。
    while (!found && i < pRoot->m_vChildren.end()) {
        found = GetNodePath(*i, pNode, path);
        ++i;
    }
 
    if (!found)
        path.pop_back();
 
    return found;
}
/**
 * 获得两条路径的最后一个公共结点。
 */
TreeNode* GetLastCommonNode(const list<TreeNode*>& path1,
        const list<TreeNode*>& path2) {
    list<TreeNode*>::const_iterator iterator1 = path1.begin();
    list<TreeNode*>::const_iterator iterator2 = path2.begin();
 
    TreeNode* pLast = NULL;
 
    while (iterator1 != path1.end() && iterator2 != path2.end()) {
        if (*iterator1 == *iterator2)
            pLast = *iterator1; //遍历完两条路径,得到最后一个公共结点。
 
        iterator1++;
        iterator2++;
    }
 
    return pLast;
}
 
TreeNode* GetLastCommonParent(TreeNode* pRoot, TreeNode* pNode1,
        TreeNode* pNode2) {
    if (pRoot == NULL || pNode1 == NULL || pNode2 == NULL)
        return NULL;
 
    list<TreeNode*> path1;
    GetNodePath(pRoot, pNode1, path1);
 
    list<TreeNode*> path2;
    GetNodePath(pRoot, pNode2, path2);
 
    return GetLastCommonNode(path1, path2);
}
 
// ====================测试代码====================
 
void Test(char* testName, TreeNode* pRoot, TreeNode* pNode1, TreeNode* pNode2,
        TreeNode* pExpected) {
    if (testName != NULL)
        printf("%s begins: \n", testName);
 
    TreeNode* pResult = GetLastCommonParent(pRoot, pNode1, pNode2);
 
    if ((pExpected == NULL && pResult == NULL)
            || (pExpected != NULL && pResult != NULL
                    && pResult->m_nValue == pExpected->m_nValue))
        printf("Passed.\n");
    else
        printf("Failed.\n");
}
 
// 形状普通的树
//              1
//            /   \
//           2     3
//       /       \
//      4         5
//     / \      / |  \
//    6   7    8  9  10
void Test1() {
    TreeNode* pNode1 = CreateTreeNode(1);
    TreeNode* pNode2 = CreateTreeNode(2);
    TreeNode* pNode3 = CreateTreeNode(3);
    TreeNode* pNode4 = CreateTreeNode(4);
    TreeNode* pNode5 = CreateTreeNode(5);
    TreeNode* pNode6 = CreateTreeNode(6);
    TreeNode* pNode7 = CreateTreeNode(7);
    TreeNode* pNode8 = CreateTreeNode(8);
    TreeNode* pNode9 = CreateTreeNode(9);
    TreeNode* pNode10 = CreateTreeNode(10);
 
    ConnectTreeNodes(pNode1, pNode2);
    ConnectTreeNodes(pNode1, pNode3);
 
    ConnectTreeNodes(pNode2, pNode4);
    ConnectTreeNodes(pNode2, pNode5);
 
    ConnectTreeNodes(pNode4, pNode6);
    ConnectTreeNodes(pNode4, pNode7);
 
    ConnectTreeNodes(pNode5, pNode8);
    ConnectTreeNodes(pNode5, pNode9);
    ConnectTreeNodes(pNode5, pNode10);
 
    Test("Test1", pNode1, pNode6, pNode8, pNode2);
}
 
// 树退化成一个链表
//               1
//              /
//             2
//            /
//           3
//          /
//         4
//        /
//       5
void Test2() {
    TreeNode* pNode1 = CreateTreeNode(1);
    TreeNode* pNode2 = CreateTreeNode(2);
    TreeNode* pNode3 = CreateTreeNode(3);
    TreeNode* pNode4 = CreateTreeNode(4);
    TreeNode* pNode5 = CreateTreeNode(5);
 
    ConnectTreeNodes(pNode1, pNode2);
    ConnectTreeNodes(pNode2, pNode3);
    ConnectTreeNodes(pNode3, pNode4);
    ConnectTreeNodes(pNode4, pNode5);
 
    Test("Test2", pNode1, pNode5, pNode4, pNode3);
}
 
// 树退化成一个链表,一个结点不在树中
//               1
//              /
//             2
//            /
//           3
//          /
//         4
//        /
//       5
void Test3() {
    TreeNode* pNode1 = CreateTreeNode(1);
    TreeNode* pNode2 = CreateTreeNode(2);
    TreeNode* pNode3 = CreateTreeNode(3);
    TreeNode* pNode4 = CreateTreeNode(4);
    TreeNode* pNode5 = CreateTreeNode(5);
 
    ConnectTreeNodes(pNode1, pNode2);
    ConnectTreeNodes(pNode2, pNode3);
    ConnectTreeNodes(pNode3, pNode4);
    ConnectTreeNodes(pNode4, pNode5);
 
    TreeNode* pNode6 = CreateTreeNode(6);
 
    Test("Test3", pNode1, pNode5, pNode6, NULL);
}
 
// 输入NULL
void Test4() {
    Test("Test4", NULL, NULL, NULL, NULL);
}
 
int main(int argc, char** argv) {
    Test1();
    Test2();
    Test3();
    Test4();
 
    return 0;
}

JZ-C-49

剑指offer第四十九题:把字符串转换为整数

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
//============================================================================
// Name        : JZ-C-49.cpp
// Author      : Laughing_Lz
// Version     :
// Copyright   : All Right Reserved
// Description : 把字符串转换为整数
//============================================================================
 
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
 
long long StrToIntCore(const char* str, bool minus);
 
enum Status {
    kValid = 0, kInvalid //此时kInvalid为1,如果没有定义enum变量的需求,枚举变量的值可以省略。在以上形式下,第一个值默认值为0,以下各个分别为上一个值加1。
};
int g_nStatus = kValid;//定义全局变量,反映输入是否合法
 
int StrToInt(const char* str) {
    g_nStatus = kInvalid;//初始为1:不合法
    long long num = 0;//用long long型存储转换的str,实际返回的则是int型★
 
    if (str != NULL && *str != '\0') {//考虑空指针NULL或字符串为空"",函数直接返回0,且全局变量g_nStatus为1,不合法
        bool minus = false;//考虑正负
        if (*str == '+')
            str++;
        else if (*str == '-') {
            str++;
            minus = true;
        }
 
        if (*str != '\0') {
            num = StrToIntCore(str, minus);
        }
    }
 
    return (int) num;//将long long型num转为int
}
 
long long StrToIntCore(const char* digit, bool minus) {
    long long num = 0;
 
    while (*digit != '\0') {
        if (*digit >= '0' && *digit <= '9') {
            int flag = minus ? -1 : 1;
            num = num * 10 + flag * (*digit - '0');
            //考虑溢出
            if ((!minus && num > 0x7FFFFFFF) //int所能表示的最大正整数
            || (minus && num < (signed int) 0x80000000)) { //int所能表示的最小负整数
                num = 0;
                break;
            }
 
            digit++;
        } else {
            num = 0;
            break;
        }
    }
 
    if (*digit == '\0') {
        g_nStatus = kValid;
    }
 
    return num;
}
 
// ====================测试代码====================
void Test(char* string) {
    int result = StrToInt(string);
    if (result == 0 && g_nStatus == kInvalid)
        printf("the input %s is invalid.\n", string);
    else
        printf("number for %s is: %d.\n", string, result);
}
 
int main(int argc, char** argv) {
    Test(NULL);
 
    Test("");
 
    Test("123");
 
    Test("+123");
 
    Test("-123");
 
    Test("1a33");
 
    Test("+0");
 
    Test("-0");
 
    //有效的最大正整数, 0x7FFFFFFF
    Test("+2147483647");
 
    Test("-2147483647");
 
    Test("+2147483648");
 
    //有效的最小负整数, 0x80000000
    Test("-2147483648");
 
    Test("+2147483649");
 
    Test("-2147483649");
 
    Test("+");
 
    Test("-");
 
    return 0;
}

JZ-C-48

剑指offer第四十八题:不能被继承的类:用C++设计一个不能被继承的类(如C#里关键字Sealed,Java里关键字final)

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
//============================================================================
// Name        : JZ-C-48.cpp
// Author      : Laughing_Lz
// Version     :
// Copyright   : All Right Reserved
// Description : 不能被继承的类:用C++设计一个不能被继承的类(如C#里关键字Sealed,Java里关键字final)
//============================================================================
 
#include <iostream>
using namespace std;
 
// ====================方法一:把构造函数设为私有函数====================
class SealedClass1 {
public:
    static SealedClass1* GetInstance() {
        return new SealedClass1();
    }
 
    static void DeleteInstance(SealedClass1* pInstance) {
        delete pInstance;
    }
 
private:
    SealedClass1() {//private
    }
    ~SealedClass1() {//private
    }
};
 
// 如果试图从SealedClass1继承出新的类型,
// 将会导致编译错误。
/*
 class Try1 : public SealedClass1
 {
 public:
 Try1() {}
 ~Try1() {}
 };
 */
 
// ====================方法二:利用虚拟继承virtual====================
template<typename T> class MakeSealed {
    friend T;//友元类
 
private:
    MakeSealed() {
    }
    ~MakeSealed() {
    }
};
 
class SealedClass2: virtual public MakeSealed<SealedClass2> {//
public:
    SealedClass2() {
    }
    ~SealedClass2() {
    }
};
 
// 如果试图从SealedClass1继承出新的类型,
// 将会导致编译错误。
/*
 class Try2 : public SealedClass2
 {
 public:
 Try2() {}
 ~Try2() {}
 };
 */
 
int main(int argc, char** argv) {
    return 0;
}

JZ-C-47

剑指offer第四十七题:不能用加减乘除做加法

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
//============================================================================
// Name        : JZ-C-47.cpp
// Author      : Laughing_Lz
// Version     :
// Copyright   : All Right Reserved
// Description : 不能用加减乘除做加法
//============================================================================
 
#include <iostream>
#include <stdio.h>
using namespace std;
 
int Add(int num1, int num2) {
    int sum, carry;
    do {
        sum = num1 ^ num2; //第一步:异或(各(★)位相加,先不考虑进位)
        carry = (num1 & num2) << 1; //第二步:先与运算再左移得到进位
 
        num1 = sum;
        num2 = carry;
    } while (num2 != 0); //第三步:前两个步骤的结果相加(重复前面两步,直到不产生进位为止)
 
    return num1;
}
 
// ====================测试代码====================
void Test(int num1, int num2, int expected) {
    int result = Add(num1, num2);
    if (result == expected)
        printf("%d + %d is %d. Passed\n", num1, num2, result);
    else
        printf("%d + %d is %d. Failed\n", num1, num2, result);
}
 
int main(int argc, char** argv) {
    Test(1, 2, 3);
    Test(111, 899, 1010);
    Test(-1, 2, 1);
    Test(1, -2, -1);
    Test(3, 0, 3);
    Test(0, -4, -4);
    Test(-2, -8, -10);
}

JZ-C-46

剑指offer第四十六题:求1+2+3+…+n:要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)

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
//============================================================================
// Name        : JZ-C-46.cpp
// Author      : Laughing_Lz
// Version     :
// Copyright   : All Right Reserved
// Description : 求1+2+3+...+n:要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)
//============================================================================
 
#include <iostream>
#include <stdio.h>
using namespace std;
// ====================方法一:利用构造函数求解====================
class Temp {
public:
    Temp() {
        ++N;
        Sum += N;
    }
 
    static void Reset() { //注意这里是静态方法
        N = 0;
        Sum = 0;
    }
    static unsigned int GetSum() { //注意这里是静态方法
        return Sum;
    }
 
private:
    static unsigned int N; //注意这里是静态变量
    static unsigned int Sum; //注意这里是静态变量
};
 
unsigned int Temp::N = 0;
unsigned int Temp::Sum = 0;
 
unsigned int Sum_Solution1(unsigned int n) {
    Temp::Reset();
 
    Temp *a = new Temp[n]; //这里创建的是对象数组
    delete[] a;
    a = NULL;
 
    return Temp::GetSum();
}
 
// ====================方法二:利用虚函数求解====================
/**
 * 一个函数充当递归函数的角色,另一个函数处理终止递归的情况,因此使用布尔变量,若n不为0,!!n为1;若n为0,!!n为0;
 */
class A;
A* Array[2];
 
class A {
public:
    virtual unsigned int Sum(unsigned int n) {
        return 0;
    }
};
 
class B: public A {
public:
    virtual unsigned int Sum(unsigned int n) {
        return Array[!!n]->Sum(n - 1) + n;
    }
};
 
int Sum_Solution2(int n) {
    A a;
    B b;
    Array[0] = &a; //递归结束,调用的为父类Sum方法
    Array[1] = &b;
 
    int value = Array[1]->Sum(n);
 
    return value;
}
 
// ====================方法三:利用函数指针求解====================
typedef unsigned int (*fun)(unsigned int); //函数指针定义
 
unsigned int Solution3_Teminator(unsigned int n) {
    return 0;
}
 
unsigned int Sum_Solution3(unsigned int n) {
    static fun f[2] = { Solution3_Teminator, Sum_Solution3 };
    return n + f[!!n](n - 1);
}
 
// ====================方法四:利用模板类型求解====================
template<unsigned int n> struct Sum_Solution4 {
    enum Value {//enum:枚举类型
        N = Sum_Solution4<n - 1>::N + n
    };
};
 
template<> struct Sum_Solution4<1> {
    enum Value {
        N = 1
    };
};
 
template<> struct Sum_Solution4<0> {
    enum Value {
        N = 0
    };
};
 
// ====================测试代码====================
void Test(int n, int expected) {
    printf("Test for %d begins:\n", n);
 
    if (Sum_Solution1(n) == expected)
        printf("Solution1 passed.\n");
    else
        printf("Solution1 failed.\n");
 
    if (Sum_Solution2(n) == expected)
        printf("Solution2 passed.\n");
    else
        printf("Solution2 failed.\n");
 
    if (Sum_Solution3(n) == expected)
        printf("Solution3 passed.\n");
    else
        printf("Solution3 failed.\n");
}
 
void Test1() {
    const unsigned int number = 1;
    int expected = 1;
    Test(number, expected);
    if (Sum_Solution4<number>::N == expected)
        printf("Solution4 passed.\n");
    else
        printf("Solution4 failed.\n");
}
 
void Test2() {
    const unsigned int number = 5;
    int expected = 15;
    Test(number, expected);
    if (Sum_Solution4<number>::N == expected)
        printf("Solution4 passed.\n");
    else
        printf("Solution4 failed.\n");
}
 
void Test3() {
    const unsigned int number = 10;
    int expected = 55;
    Test(number, expected);
    if (Sum_Solution4<number>::N == expected)
        printf("Solution4 passed.\n");
    else
        printf("Solution4 failed.\n");
}
 
void Test4() {
    const unsigned int number = 0;
    int expected = 0;
    Test(number, expected);
    if (Sum_Solution4<number>::N == expected)
        printf("Solution4 passed.\n");
    else
        printf("Solution4 failed.\n");
}
 
int main(int argc, char** argvb) {
    Test1();
    Test2();
    Test3();
    Test4();
 
    return 0;
}