面试金典题解

数组与字符串

1.1 确定字符互异

描述：

给定一个字符串string str，请返回一个bool值,True代表字符串的所有字符全都不同，False代表存在相同的字符。保证字符串中的字符为ASCII字符且不允许使用额外的存储结构，字符串的长度小于等于3000。大小写字母算不同的字符

测试样例：

"aeiou"
返回：True
"BarackObama"
返回：False

假设不使用额外的数据结构。

解法：

假定字符集为ASCII，若字符串的长度大于字母表的字符个数，直接返回false；字母表一共只有256个字符。
构建一个布尔值的数组，索引值i对应的标记该字符串是否含有字母表的第i个字符。若这个字符第二次出现，返回false。

bool checkDifferent(string str) {
    if (str.size() > 256) return false;
    vector<bool> char_set(256, 0);
    for (int i = 0; i < str.size(); i++) {
        int val = str[i];
        if (char_set[val]) return false; // 这个字符已在字符串中出现过
        char_set[val] = true;
    }
    return true;
}

1.2 原串翻转

描述：

给定一个string iniString，请返回一个string，为该字符串翻转后的结果。要求不使用额外数据结构和储存空间，可以使用单个过程变量，保证字符串的长度小于等于5000。

测试样例：

1 2	"This is nowcoder" 返回："redocwon si sihT"

解法：

不分配额外空间，直接就地翻转字符串。

string reverseString(string iniString) {
    // write code here
    if (iniString.size() < 2) return iniString;
    char tmp;
    int i = 0, j = iniString.size() - 1;
    while (i < j) { // 字符串首尾开始交换两个字符，直至两个指针在中间碰头
        tmp = iniString[i];
        iniString[i++] = iniString[j];
        iniString[j--] = tmp;
    }
    return iniString;
}

1.3 确定两串乱序同构

描述：

给定string stringA和string stringB，编写程序确认两字符串包含的字符是否完全相同，注意大小写为不同字符，且考虑字符串中的空格，返回一个bool，代表两串是否由一样的字符组成。保证两串的长度都小于等于5000。

示例1
输入："This is nowcoder","is This nowcoder"
返回值：true

示例2
输入："Here you are","Are you here"
返回值：false

注：变位词区分大小写，空白也考虑在内。比较两个如果长度不同，就不可能是变位词。

解法1：排序字符串

bool checkSam(string stringA, string stringB) {
    // write code here
    if (stringA.size() != stringB.size()) return false;
    sort(stringA.begin(), stringA.end());
    sort(stringB.begin(), stringB.end());
    return stringA == stringB;
}

解法2：检查两个字符串的各字符数是否相等

bool checkSam(string stringA, string stringB) {
    // write code here
    if (stringA.size() != stringB.size()) return false;
    vector<int> letters(256, 0);
    for (char c : stringA) {
        letters[c]++;
    }
    for (char d : stringB) {
        letters[d]--;
        if (letters[d] < 0) return false;
    }
    return true;
}

1.4 空格替换

描述：

给定一个string iniString 及其长度 int len, 已知该字符串中有空格，现要求编写程序将字符串中空格替换为“%20”。返回更改后的string。假设该字符串有足够的空间存放新增的字符，并且知道原字符的长度(小于等于1000)，同时保证字符串由大小写的英文字母组成。

示例1
输入："Mr John Smith",13
返回值："Mr%20John%20Smith"

示例2
输入："Hello  World",12
返回值："Hello%20%20World"

解法：

处理字符串操作问题，常用做法是从字符串尾部开始编辑，从后向前反向操作。因为字符串尾部有额外的缓存，可以直接修改，不必担心会覆写原来的数据。

两次扫描，一次先数出字符串中有多少空格，从而算出最终的字符串的长度；第二次扫描反向编辑字符串。检测到空格将%20复制到下一个位置，若不是空白，就复制原来的字符。

string replaceSpace(string iniString, int length) {
    // write code here
    int count = 0, newLength = 0, i = 0;
    for (int i = 0; i < length; i++) {
        if (iniString[i] == ' ') count++;
    }
    newLength = length + 2 * count;
    string res(newLength, ' ');
    for (int i = length - 1; i >= 0; i--) {
        if (iniString[i] == ' ') {
            res[newLength - 1] = '0';
            res[newLength - 2] = '2';
            res[newLength - 3] = '%';
            newLength -= 3;
        } else {
            res[newLength - 1] = iniString[i];
            newLength--;
        }
    }
    return res;
}

1.5 基本字符串压缩

描述：

现给定一个string iniString字符串(长度小于等于10000)，请按连续重复字母压缩的方式将该字符串压缩，返回结果为string，比如，字符串“aabbcccccaaa”经压缩会变成“a2b2c5a3”，若压缩后的字符串没有变短，则返回原先的字符串。注意保证串内字符均由大小写英文字母组成。

示例1
输入："aabcccccaaa"
返回值："a2b1c5a3"

示例2
输入："welcometonowcoderrrrr"
返回值："welcometonowcoderrrrr"

说明：welcometonowcoderrrrr转换成重复字母压缩的结果是w1e1l1c1o1m1e1t1o1n1o1w1c1o1d1e1r5，比原字符串的长度还要长，所以返回原先的字符串。

解法：

加入压缩长度检查，算出压缩后的长度，构建相应大小的字符串。

string zipString(string iniString) {
    // write code here
    int size = countCompression(iniString);
    if (size >= iniString.size()) return iniString;
    string res(size, ' ');
    int index = 1, count = 1;
    char last = iniString[0];
    res[0] = last;
    for (int i = 1; i < iniString.size(); i++) {
        if (iniString[i] == last) {
            count++;
        } else {
            last = iniString[i];
            string tmp = to_string(count);
            for (char d : tmp) {
                res[index++] = d;
            }
            res[index++] = last;
            count = 1;
        }
    }
    string tmp = to_string(count);
    for (char d : tmp) {
        res[index++] = d;
    }
    return res;
}
    
int countCompression(string str) {
    if (str.size() == 0) return 0;
    char last = str[0];
    int size = 0, count = 1;
    for (int i = 1; i < str.size(); i++) {
        if (str[i] == last) {
            count++;
        } else {
            last = str[i];
            size += 1 + to_string(count).size();
            count = 1;
        }
    }
    size += 1 + to_string(count).size();
    return size;
}

1.6 像素翻转

描述：

现有一个NxN的矩阵，阶数为N，请编写一个算法将矩阵顺时针旋转90度并将其作为返回值。要求不使用缓存矩阵，保证N不大于500，元素不大于256，每个元素用int表示。

1
2
3

测试样例：
[[1,2,3],[4,5,6],[7,8,9]],3
返回：[[7,4,1],[8,5,2],[9,6,3]]

解法：

按索引一个一个进行交换，从最外层开始逐渐向里，在每一层进行交换。

vector<vector<int> > transformImage(vector<vector<int> > mat, int n) {
    // write code here
    for (int layer = 0; layer < n / 2; layer++) {
        int first = layer, last = n - 1 - layer;
        for (int i = first; i < last; i++) {
            int offset = i - first;
            // 存储上边
            int top = mat[first][i];
            mat[first][i] = mat[last - offset][first]; // 左到上
            mat[last - offset][first] = mat[last][last - offset]; // 下到左
            mat[last][last - offset] = mat[i][last]; // 右到下
            mat[i][last] = top; // 上到右
        }
    }
    return mat;
}

1.7 清除行列

描述：给定一个N阶方阵int[][](C++中为vector<vector><int>>)mat及其阶数n，若方阵中某个元素为0，则将其所在的行与列清零。返回改变后的int[][]方阵(C++中为vector<vector><int>>)，保证n小于等于300，矩阵中的元素在nt范围内。

1
2
3

测试样例：
[[1,2,3],[0,1,2],[0,0,1]]
返回：[[0,0,3],[0,0,0],[0,0,0]]

解法：

避免陷阱将矩阵所有元素清零。用两个数组记录包含零的所有行与列，第二次遍历矩阵时，若所在行或列标记为零，则将元素清零。

vector<vector<int> > clearZero(vector<vector<int> > mat, int n) {
    // write code here
    vector<bool> row(n, 0);
    vector<bool> col(n, 0);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (mat[i][j] == 0) {
                row[i] = true;
                col[j] = true;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (row[i] || col[j]) {
                mat[i][j] = 0;
            }
        }
    }
    return mat;
}

1.8 翻转子串

描述：

给定2个字符串s1和s2，请判断s2是否为s1旋转而成，返回bool值。字符串中字符为英文字母和空格，区分大小写，字符串长度小于等于1000。

测试样例：
"Hello world","worldhello "
返回：false
"waterbottle","erbottlewat"
返回：true

解法：

假定s2由s1旋转而成，将s1划分为两部分：x和y，满足xy = s1和yx = s2.无论分割点在哪里，yx肯定是xyxy的子串，即s2为s1s1的子串。

bool checkReverseEqual(string s1, string s2) {
    // write code here
    int len = s1.size();
    if (len == s2.size() && len > 0) {
        string s1s1 = s1 + s1;
        if (s1s1.find(s2) != -1) return true;
    }
    return false;
}

链表

2.1 访问单个节点的删除

描述：

编写代码，移除未排序链表中的重复节点。
进阶：不使用临时缓冲区

解法：

使用散列表，直接迭代访问整个链表，将每个节点加入散列表，若发现重复元素，将该节点从链表中删除，然后继续迭代。一次扫描完成。

struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

void deleteDups(ListNode* n) {
    unordered_map<int, int> map;
    ListNode* pre = new ListNode(-1);
    while (n != nullptr) {
        if (map.find(n->val) != map.end()) {
            pre->next = n->next;
        } else {
            map[n->val] = 1;
            pre = n;
        }
        n = n->next;
    }
}

进阶：不使用缓冲区。
用两个指针来迭代：current迭代访问整个链表，runner用于检查后续的节点是否重复。

void deleteDups(ListNode* head) {
    if (head == nullptr) return;
    ListNode* current = head;
    while (current != nullptr) {
        // 移除后续值相同的节点
        ListNode* runner = current;
        while (runner->next != nullptr) {
            if (runner->next->val == current->val) {
                runner->next = runner->next->next;
            } else {
                runner = runner->next;
            }
        }
        current = current->next;
    }
}
// 空间复杂度O(1), 时间复杂度O(N^2)

2.2 倒数第k个节点

描述：

实现一个算法，找出单向链表中倒数第K个节点。

解法1：链表长度已知

若链表长度已知，那么倒数第k个节点就是第(length - k)个节点，直接迭代访问即可，比较简单。

解法2：递归

递归访问整个链表，当抵达链表末端时，该方法回传一个置为零的计数器，之后每次调用都会计数器加一。当计数器等于k时，表示访问的是倒数第k个节点。

ListNode* nthToLast(ListNode* head, int k, int& i) {
    if (head == nullptr) return nullptr;
    ListNode* node = nthToLast(head->next, k, i);
    i++;
    if (i == k) {
        return head;
    }
    return node;
}

int main() {
    ListNode* l1 = new ListNode(10);
    l1 = fun(l1);
    int i = 0;
    ListNode* node = nthToLast(l1, 3, i);
}

2.3 删除某个节点

描述：

实现一个算法，删除单向链表中间的某个节点，假定只能访问该节点。

解法：

访问不到链表的首节点，只能访问待删除节点。解法很简单，直接将后继节点的数据复制到当前节点，然后删除该节点。

bool deleteNode(ListNode* n) {
    if (n == nullptr || n->next == nullptr) {
        return false;
    }
    ListNode* next = n->next;
    n->val = next->val;
    n->next = next->next;
    delete next;
    return true;
}

注意，若待删除节点为链表的尾节点，则这个问题无解。

2.4 链表分割

描述：

现有一链表的头指针 ListNode* pHead，给一定值x，以x为基准将链表分割成两部分，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

解法：

不必移动和交换元素，直接创建两个链表，一个链表存储小于x的元素，一个链表存储大于等于x的元素。迭代访问整个链表，将元素插入before或after链表中。一旦抵达链表末端，表面拆分完成，最后合并两个链表。

ListNode* partition(ListNode* pHead, in
    // write code here
    ListNode* beforeStart = nullptr;
    ListNode* beforeEnd = nullptr;
    ListNode* afterStart = nullptr;
    ListNode* afterEnd = nullptr;
    ListNode* cur = pHead;
    
    // 分割链表
    while (cur != nullptr) {
        ListNode* next = cur->next; // 临时变量记录后继结点
        cur->next = nullptr;
        if (cur->val < x) {
            // 将节点插入before链表
            if (beforeStart == nullptr)
                beforeStart = cur;
                beforeEnd = cur;
            } else {
                beforeEnd->next = cur;
                beforeEnd = beforeEnd->
            }
        } else {
        	// 将节点插入after链表
            if (afterStart == nullptr) 
                afterStart = cur;
                afterEnd = cur;
            } else {
                afterEnd->next = cur;
                afterEnd = afterEnd->ne
            }
        }
        cur = next;
    }
    if (beforeStart == nullptr) return afterStart;
    // 合并链表
    beforeEnd->next = afterStart;
    return beforeStart;
}

2.5 链式A+B

描述：

将两个反向存储在链表中的整数求和（即整数的个位存放在了链表首部，一位数对应一个节点），返回的结果仍用链表形式。给定两个链表ListNode* A，ListNode* B，请返回A+B的结果(ListNode*)。

测试样例：
{1,2,3},{3,2,1}
返回：{4,4,4}
{7,1,6},{5,9,2}
返回：{2,1,9}

解法：

递归模拟，两个节点的值相加，如有进位则转入下一节点。

ListNode* plusAB(ListNode* a, ListNode* b) {
    // write code here
    return addList(a, b, 0);
}
ListNode* addList(ListNode* a, ListNode* b, int carry) {
    if (a == nullptr && b == nullptr && carry == 0) return nullptr;
    ListNode* res = new ListNode(0);
    int val = carry;
    if (a != nullptr) {
        val += a->val;
    }
    if (b != nullptr) {
        val += b->val;
    }
    res->val = val % 10;
    ListNode* more = addList(a == nullptr ? nullptr : a->next, b == nullptr ?
                             nullptr : b->next, val >= 10 ? 1 : 0);
    res->next = more;
    return res;
}

迭代遍历：

ListNode* plusAB(ListNode* a, ListNode* b) {
    // write code here
    ListNode* haha = b;
    while (a != NULL) {
        b->val += a->val;
        if (b->val >= 10) {
            b->val %= 10;
            if (b->next == NULL)
                b->next = new ListNode(1);
            else
                b->next->val++;
        }
        if (b->next == NULL){
            b->next = a->next;
            break;
        }
        a = a->next;
        b = b->next;

    }
    return haha;
}

2.6 有环链表的环路开头节点

描述：

给定一个有环链表，实现一个算法返回环路的开头节点。

解法：

创建两个指针：fast和slow；
slow每走1步，fast走2步；
两者碰在一起时，将slow指向链表的头节点head，fast保持不变
以相同的速度移动slow和fast，一次走1步，返回新的碰撞处。

ListNode* findBeginning(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    
    // 找出第一次相遇的位置
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) break;// 碰撞
    }
    // 错误检查：没有碰撞即没有环路
    if (fast == nullptr || fast->next == nullptr) {
        return nullptr;
    }
    // slow指向链表首部，fast不变，直到第二次相遇
    slow = head;
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }
    // 返回环路起始点
    return slow;
}

2.7 回文链表

描述：编写一个函数，检查链表是否为回文。

测试样例：
{1,2,3,2,1}
返回：true
{1,2,3,2,3}
返回：false

解法1：反转并比较

反转整个链表，然后比较反转链表和原始链表。若两者相同，则该链表为回文。
注意，在比较原始链表和反转链表时，其实只需比较链表的前半部分。若原始链表和反转链表的前半部分相同，那么，两者的后半部分肯定相同。

bool isPalindrome(ListNode* pHead) {
    // write code here
    ListNode* revered = reverseList(pHead);
    return isEqual(pHead, revered);
}

ListNode* reverseList(ListNode* head) {
    ListNode* res = nullptr;
    ListNode* cur = head;
    while (cur != nullptr) {
        ListNode* n = new ListNode(cur->val);
        n->next = res;
        res = n;
        cur = cur->next;
    }
    return res;
}

bool isEqual(ListNode* a, ListNode* b) {
    while (a != nullptr && b != nullptr) {
        if (a->val != b->val) {
            return false;
        }
        a = a->next;
        b = b->next;
    }
    return a == nullptr && b == nullptr;
}

解法2：迭代法

将链表前半部分反转，利用栈来实现。
入栈有两种方式，若链表长度已知：可以用for循环迭代访问前半部分节点，将每个节点入栈；
若链表长度未知，使用快慢指针，迭代访问链表，在快指针到达链表尾部时，慢指针刚好在链表中间位置。
至此，栈里就存放了链表前半部分的所有节点，不过顺序是相反的。接下来，只需迭代访问链表余下节点。每次迭代时，比较当前节点和栈顶元素，若完成迭代时比较结果完全相同，则该链表是回文序列。

bool isPalindrome(ListNode* pHead) {
    ListNode* slow = pHead;
    ListNode* fast = pHead;

    stack<int> st;
	// 链表前半部分元素入栈，偶数个节点fast最后指向nullptr，奇数个节点fast最后指向最后一个节点
    while (fast != nullptr && fast->next != nullptr) {
        st.push(slow->val);
        slow = slow->next;
        fast = fast->next->next;
    }
    // 奇数个节点，跳过中间节点
    if (fast != nullptr) {
        slow = slow->next;
    }
    while (slow != nullptr && !st.empty()) {
        int top = st.top();
        st.pop();
        // 判断回文
        if (top != slow->val) {
            return false;
        }
        slow = slow->next;
    }
    return true;
}

解法3：递归法

ListNode* myLeft = nullptr;
bool isPalindrome(ListNode* pHead) {
    myLeft = pHead;
    return tranverse(pHead);
}

bool tranverse(ListNode* right) {
    if(right == nullptr) return true;       
    bool res = tranverse(right->next);       
    res = (res && right->val == myLeft->val);
    myLeft = myLeft->next;                  
    return res; 
}

栈与队列

3.1 三合一

描述：

如何只用一个数组来实现三个栈。

解法：

固定分割：将整个数组三等分，并将每个栈的增长限制在各自的空间里。

class FixedMultiStack {
private:
    int numberOfStacks = 3;
    int stackCapacity;
    vector<int> values;
    vector<int> sizes;
public:
    FixedMultiStack(int stackSize) : stackCapacity(stackSize) {
        values.resize(stackSize * numberOfStacks);
        sizes.resize(numberOfStacks);
    }
    // 将值压入栈
    void push(int stackNum, int value) throws FullStackException { 
		/* 检查有空间容纳下一个元素 */ 
		if (isFull(stackNum)) { 
			throw new FullStackException(); 
		} 

        /* 对栈顶指针加 1 并更新顶部的值 */ 
        sizes[stackNum]++; 
        values[indexOfTop(stackNum)] = value; 
    }
    // 出栈
    int pop(int stackNum) {
        if (isEmpty(stackNum)) {
            throw new EmptyStackException();
        }
        int topIndex = indexOfTop(stackNum);
        int value = values[topIndex]; // 获取顶部元素
        values[topIndex] = 0; // 清零
        sizes[stackNum]--; // 缩减大小
        return value;
    }
    // 检查栈是否为空
    bool isEmpty(int stackNum) {
        return sizes[stackNum] == 0;
    }
    // 检查栈是否已满
    bool isFull(int stackNum) {
        return sizes[stackNum] == stackCapacity;
    }
    // 返回栈顶元素索引
    int IndexOfTop(int stackNum) {
        int offset = stackNum * stackCapacity;
        int size = sizes[stackNum];
        return offset + size - 1;
    }
     
};

3.2 栈的最小值

描述：

请设计一个栈，除了 pop 与 push 函数，还支持 min 函数，其可返回栈元素中的最小值。执行 push、pop 和 min 操作的时间复杂度必须为O(1)。

解法：

每个节点记录当前最小值。这么一来，要找到 min，直接查看栈顶元素就能得到最小值。缺点是栈很大时，每个元素都要记录min，会浪费大量空间。改进：用其他的栈来记录。

class StackWithMin {
private:
    stack<int> s1; // 数据栈
    satck<int> s2; // 辅助栈
public:
    void push(int val) {
        if (val <= min()) {
            s2.push(val);
        }
        s1.push(val);
    }
    
    void pop() {
        int val = s1.top();
        if (val == min()) {
            s2.pop();
        }
        s1.pop();
    }

    int min() {
        if (s2.empty()) {
            return INT_MAX;
        } else {
            return s2.top();
        }
    }
};

3.3 集合栈

描述：

请实现一种数据结构SetOfStacks，由多个大小为size的栈组成，当前一个栈填满时，则新建一个栈，且也可以与普通栈一样拥有相同的push和pop操作。
现给定一个操作序列int[][2] ope(C++为vector<vector<int>>)，若执行push操作则第一个数为1，第二个数为应push的数字；若执行pop操作，则第一个数为2，第二个数为空。返回值为int[]，即为变动后的SetOfStacks，顺序从下到上，初始SetOfStacks为空，并保证数据合法。

vector<vector<int> > setOfStacks(vector<vector<int> > ope, int size) {
    // write code here
    int len = ope.size();
    vector<vector<int>> ans;
    for (int i = 0; i < len; i++) {
        if (ope[i][0] == 1) {
            if (ans.empty() || ans.back().size() == size) {
                ans.push_back({});
            }
            ans.back().push_back(ope[i][1]);
        } else {
            ans.back().pop_back();
            if (ans.back().empty()) {
                ans.pop_back();
            }
        }
    }
    return ans;
}

3.4 双栈排序

描述：

给定一个int[] numbers(C++中为vector<int>)，其中第一个元素为栈顶，请编写程序将栈进行升序排列（即最大元素位于栈顶），返回排序后的栈。要求最多使用一个额外的栈存放临时数据，但不得将元素复制到别的数据结构中。并注意这是一个栈，意味着排序过程中只能访问到最后一个元素。

1
2
3

测试样例：
[1,2,3,4,5]
返回：[5,4,3,2,1]

解法：

s1为原先的栈，s2为最终排好序的栈，若要对s1排序，可以从s1逐一弹出元素，然后按顺序插入s2中。

vector<int> twoStacksSort(vector<int> numbers) {
    // write code here
    stack<int> s1;
    for (auto num : numbers) {
        s1.push(num);
    }
    stack<int> tmp;
    while (!s1.empty()) {
        // 把s1中的每个元素有序地插入到tmp中
        int top = s1.top();
        s1.pop();
        while (!tmp.empty() && tmp.top() > top) {
            s1.push(tmp.top());
            tmp.pop();
        }
        tmp.push(top);
    }
    vector<int> res;
    // 将tmp中元素复制回s
    while (!tmp.empty()) {
        int top = tmp.top();
        s1.push(top);
        res.push_back(top);
        tmp.pop();
    }
    return res;
}

树与图

4.1 二叉树平衡检查

描述：

平衡的定义如下，已知对于树中的任意一个结点，若其两颗子树的高度差不超过1，则我们称该树平衡。现给定指向树根结点的指针TreeNode* root，请编写函数返回一个bool，表示该二叉树是否平衡。

解法：

递归访问整棵树，计算每个节点的两个子树的高度。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
bool isBalance(TreeNode* root) {
    // write code here
    if (root == nullptr) return true; // 终止条件
    int diff = getHeight(root->left) - getHeight(root->right);
    if (abs(diff) > 1) {
        return false;
    } else { // 递归
        return isBalance(root->left) && isBalance(root->right);
    }
}
// 计算树的高度
int getHeight(TreeNode* root) {
    if (root == nullptr) return 0; // 终止条件
    return max(getHeight(root -> left), getHeight(root->right)) + 1;
}

改进：getHeight函数不仅可以检查高度，还能检查这棵树是否平衡。从根节点递归向下检查每棵子树的高度，设计checkHeight函数，若子树平衡返回子树的实际高度，若子树不平衡返回-1并中断执行。

bool isBalance(TreeNode* root) {
    // write code here
    if (root == nullptr) return true;
    if (checkHeight(root) == -1) {
        return false;
    } else {
        return true;
    }
}
int checkHeight(TreeNode* root) {
    if (root == nullptr) return 0; // 高度为0
    // 检查左子树是否平衡
    int leftHeight = checkHeight(root->left);
    if (leftHeight == -1) return -1;
    // 检查右子树是否平衡
    int rightHeight = checkHeight(root->right);
    if (rightHeight == -1) return -1;
    // 检查当前节点是否平衡
    int diff = leftHeight - rightHeight;
    if (abs(diff) > 1) {
        return -1; // 不平衡
    } else {
        return max(leftHeight, rightHeight) + 1; // 返回高度
    }
}

4.2 高度最小的BST

描述：

给定一个元素各不相同的有序序列int[] vals（升序排列）,请编写算法创建一棵高度最小的二叉查找树，并返回二叉查找树的高度。

解法：

递归方法创建高度最小的BST。将数组中间位置的元素插入树中，数组左半部分插入左子树，数组右半部分插入右子树，递归处理。

int buildMinimalBST(vector<int> vals) {
    // write code here
    TreeNode* root = createMinBST(vals, 0, vals.size() - 1);
    return getHeight(root);
}

TreeNode* createMinBST(vector<int> vals, int start, int end) {
    if (end < start) return nullptr;
    int mid = start + (end - start) / 2;
    TreeNode* n = new TreeNode(vals[mid]);
    n->left = createMinBST(vals, start, mid - 1);
    n->right = createMinBST(vals, mid + 1, end);
    return n;
}

int getHeight(TreeNode* root) {
    if (root == nullptr) return 0; // 终止条件
    return max(getHeight(root -> left), getHeight(root->right)) + 1;
}

4.3 输出单层节点

描述：

已知二叉树的根结点指针TreeNode* root以及链表上结点的深度，请设计算法返回一个链表ListNode，该链表代表该深度上所有结点的值，并按树上从左往右的顺序链接，深度不能超过树的高度，且树上结点的值为不大于100000的非负整数。

解法：

广度优先遍历，从根节点开始迭代，处于第i层时，表明访问过第i-1层的所有节点。

ListNode* getTreeLevel(TreeNode* root, int dep) {
    // write code here
    queue<TreeNode*> q;
    ListNode* node = new ListNode(-1);
    ListNode* res = node;
    q.push(root);
    int deep = 0;
    while (!q.empty()) {
        int len = q.size();
        for (int i = 0; i < len; i++) {
            TreeNode* cur = q.front();
            q.pop();
            if (deep == dep - 1) {
                ListNode* tmp = new ListNode(cur->val);
                node->next = tmp;
                node = node->next;
            }
            if (cur->left) q.push(cur->left);
            if (cur->right) q.push(cur->right);
        }
        deep++;
    }
    return res->next;
}

4.4 检查是否为BST

描述：

现给定树的根结点指针TreeNode* root，编辑函数返回一个bool值，判断该树是否为二叉查找树。

解法：

假定没有重复的值，可以采用中序遍历。BST中序遍历结果为递增序列。

bool checkBST(TreeNode* root) {
    // write code here
    vector<int> arr;
    process(arr, root);
    for (int i = 1; i < arr.size(); i++) {
        if (arr[i-1] > arr[i]) {
            return false;
        }
    }
    return true;
}
// 中序遍历BST
void process(vector<int>& arr, TreeNode* root) {
    if (root == nullptr) return;
    process(arr, root->left);
    arr.push_back(root->val);
    process(arr, root->right);
}

解法二：最小与最大法

二叉搜索树的条件：所有左边的节点必须小于或等于当前节点，而当前节点必须小于所有右边的节点。
迭代遍历整个树，自上而下传递最小与最大值，逐渐变窄的范围检查各个节点。

bool checkBST(TreeNode* root) {
    // write code here
    return check(root, INT_MIN, INT_MAX);
}

bool check(TreeNode* root, int minval, int maxval) {
    if (root == nullptr) return true;
    if (root->val < minval || root->val > maxval) {
        return false;
    }
    return check(root->left, minval, root->val) && 
        check(root->right, root->val, maxval);
}

4.5 寻找下一个节点

描述：

给定树的根结点指针TreeNode* root和结点的值int p，编写一个函数，寻找该二叉树中指定结点的下一个结点（即中序遍历的后继），并返回p结点的后继结点的值。保证结点的值是小于等于100000的正数且没有重复值，若不存在后继返回-1。

解法：

递归中序遍历。当节点值等于p，标记为true，返回遍历的下一个节点。

int findSucc(TreeNode* root, int p) {
    // write code here
    bool sign = false;
    return findSuccCore(root, p, sign);
}

int findSuccCore(TreeNode* root, int p, bool& sign) {
    if (root == nullptr) return -1;
    // 左子树中寻找
    int left = findSuccCore(root->left, p, sign);
    if (left != -1) return left;
    
    if (sign == true) return root->val;
    // 当前值等于p，将标记置为true
    if (root->val == p) sign = true;
    return findSuccCore(root->right, p, sign);
}

4.6 最近公共祖先

描述：

设计并实现一个算法，找出二叉树中某两个节点的第一个共同祖先。不得将其他的节点存储在另外的数据结构中。注意：这不一定是二叉搜索树。

解法：

顺着一条 p 和 q 都在同一边的链子查找，也就是说，若 p 和 q 都在某节点的左边，就到左子树中查找共同祖先，若都在右边，则在右子树中查找共同祖先。要是 p 和 q不在同一边，那就表示已经找到第一个共同祖先。

TreeNode* commonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    // 错误检查，一个节点不在树中
    if (!cover(root, p) || !cover(root, q)) {
        return nullptr;
    }
    return helper(root, p, q);
}
// 辅助函数
TreeNode* helper(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root == nullptr || root == p || root == q) {
        return root;
    }
    bool pIsOnLeft = cover(root->left, p);
    bool pIsOnRight = cover(root->right, q);
    if (pIsOnLeft != pIsOnRight) { // 两个节点位于不同的两边
        return root;
    }
    TreeNode* childSize = pIsOnLeft ? root->left : root->right;
    return helper(childSize, p, q);
}
// 检查函数
bool cover(TreeNode* root, TreeNode* p) {
    if (root == nullptr) return false;
    if (root == p) return true;
    return cover(root->left, p) || cover(root->right, p);
}

4.7 求和路径

描述：

给定一棵二叉树，其中每个节点都含有一个整数数值（该值或正或负）。设计一个算法，打印节点数值总和等于某个给定值的所有路径。注意，路径不一定非得从二叉树的根节点或叶节点开始或结束，但是其方向必须向下（只能从父节点指向子节点方向）。

解法1：暴力解法

遍历每个节点。对于每个节点，用递归法尝试所有向下的路径，并随着递归的进行跟踪路径的和。每当得到目标和，将发现的路径数目加一。

int countPathWithSum(TreeNode* root, int target) {
    if (root == 0) return 0;
    // 从root开始，符合目标和的路径进行计数
    int pathFromRoot = countPathWithSumFromRoot(root, target, 0);
    
    // 左节点与右节点
    int pathFromLeft = countPathWithSum(root->left, target);
    int pathFromRight = countPathWithSum(root->right, target);
    
    return pathFromRoot + pathFromLeft + pathFromRight;
}

// 返回从根节点开始，符合目标和的路径总数
int countPathWithSumFromRoot(TreeNode* node, int target, int sum) {
    if (node == nullptr) return 0;
    
    sum += node->val;
    
    int totalPath = 0;
    if (sum == target) { // 找到一条从root开始的路径
        totalPath++;
    }
    totalPath += countPathWithSumFromRoot(node->left, target, sum);
    totalPath += countPathWithSumFromRoot(node->right, target, sum);
    return totalPath;
}

解法2：优化算法

使用哈希表减少重复计算。使用深度优先查找对树进行遍历。当我们访问每个节点时，执行以下操作。(1) 跟踪 runningSum 的值。我们将使该变量成为函数的一个参数，并对其增加 node.value。
(2) 在散列表中查找 runningSum - targetSum。我们从散列表获得的值为路径的总数。将变量 totalPaths 的值设置为该值。
(3) 如果 runningSum == targetSum，则发现了另外一条从根节点开始的路径。将变量 totalPaths加 1。
(4) 将 runningSum 加入到散列表中（如果 runningSum 已经存在，则将增加其值）。
(5) 对左子树和右子树进行递归，计算和为 targetSum 的路径的条数。
(6) 对左子树和右子树的递归调用结束后，减少散列表中 runningSum 对应的值。

int countPathWithSum(TreeNode* root, int target) {
    unordered_map<int, int> map;
    return process(root, target, 0, map);
}
// 辅助函数
int process(TreeNode* node, int target, int sum, unordered_map<int, int>& map) {
    if (node == nullptr) return 0; // 基础情况
    
    // 对终止于该节点，符合目标和的路径进行计数
    sum += node->val;
    int diff = sum - target;
    //map[diff] = 0;
    int totalPath = map[diff];
    if (sum == target) {
        totalPath++;
    }
    
    map[sum]++;
    totalPath += countPathWithSum(node->left, target, sum, map);
    totalPath += countPathWithSum(node->right, target, sum, map);
    map[sum]--;
    
    return totalPath;
}

递归与动态规划

5.1 加到n

描述：

给定一个正整数int n，从0开始加到n，每次可增加1、2或3，直到其大于等于n，请返回一个数，代表加到n的方案的个数。保证n小于等于100000，并为了防止溢出，请将结果Mod 1000000007。

测试样例1：
1
返回：1
测试样例2：
3
返回：4
测试样例3：
4
返回：7

解法：

暴力解求解：递归，指数级增长，会超时。

int countWays(int n) {
    if (n < 0) {
        return 0;
    } else if (n == 0) {
        return 1;
    } else {
        return countWays(n - 1) + countWays(n - 2) + countWays(n - 3);
    }
}

改进：制表法，利用memo数组记录中间过程的值

int countWays(int n) {
    // write code here
    vector<int> memo(n + 1, -1);
    //memo[1] = 1;
    return countWaysCore(n, memo);
}

int countWaysCore(int n, vector<int>& memo) {
    if (n < 0) {
        return 0;
    } else if (n == 0) {
        return 1;
    } else if (memo[n] > -1) {
        return memo[n];
    } else {
        memo[n] = ((countWaysCore(n - 1, memo)  
                    + countWaysCore(n - 2, memo))% 1000000007
                   + countWaysCore(n - 3, memo))% 1000000007;
        return memo[n];
    }
}

5.2 机器人走方格I

描述：

给定两个正整数int x,int y，代表一个x乘y的网格，现有一个机器人要从网格左上角顶点走到右下角，每次只能走一步且只能向右或向下走，返回机器人有多少种走法。保证x＋y小于等于12。

1
2
3

测试样例：
2,2
返回：2

解法：

假设网格r行c列，移动到(r, c), 需要先移动到相邻点(r-1, c)或(r, c-1)。
动态规划，用一个二维表dp记录每个点的走法，dp[r][c] = dp[r - 1][c] + dp[r][c - 1].
需要注意边界的情况。

int countWays(int x, int y) {
    // write code here
    int dp[x + 1][y + 1];
    //dp[1][1] = 1;
    for (int i = 1; i <= x; i++) {
        dp[i][1] = 1;
    }
    for (int j = 1; j <= y; j++) {
        dp[1][j] = 1;
    }
    for (int i = 2; i <= x; i++) {
        for (int j = 2; j <= y; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return dp[x][y];
}

5.3 机器人走方格II

描述：

给定一个int[][] map(C++ 中为vector >)网格图，若map[i][j]为1则该点不是障碍点，否则为障碍点。另外给定int x,int y，表示网格的大小。现有一个机器人要从网格左上角走到右下角，只能走格点且只能向右或向下走。请返回机器人从(0,0)走到(x - 1,y - 1)有多少种走法。请将结果Mod 1000000007以防止溢出，并保证x和y均小于等于50。

解法：

动态规划，建立dp表存储中间结果，如果map[r][c]值不为1，则dp[r][c] = 0。

int countWays(vector<vector<int> > map, int x, int y) {
    // write code here
    vector<vector<int>> dp(x, vector<int>(y, 0));
    dp[0][0] = 1;
    for (int i = 0; i < x; i++) {
        if (map[i][0] != 1) {
            dp[i][0] = 0;
            break;
        }
        dp[i][0] = 1;
    }
    for (int j = 0; j < y; j++) {
        if (map[0][j] != 1) {
            dp[0][j] = 0;
            break;
        }
        dp[0][j] = 1;
    }
    for (int i = 1; i < x; i++) {
        for (int j = 1; j < y; j++) {
            if (map[i][j] == 1) {
                dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1000000007;
            } else {
                dp[i][j] = 0;
            }
        }
    }
    return dp[x - 1][y - 1];
}

5.4 魔术索引

描述：

已知数组A[0..n-1]和数组大小n（升序数组，元素值各不相同），若存在A[i]=i则称该数组有魔术索引，请判断该数组是否存在魔术索引，返回值为bool，要求复杂度优于o(n)。

1
2
3

测试样例：
[1,2,3,4,5]
返回：false

解法：

有序数组，二分查找，要找出元素k，会先拿它跟数组中间的元素 x比较，确定k位于x的左边还是右边。递归二分查找：（数组中没有重复的值）

bool findMagicIndex(vector<int> A, int n) {
    // write code here
    return process(A, 0, A.size() - 1);
}
bool process(vector<int> arr, int start, int end) {
    if (start > end) return false;
    int mid = start + (end - start) / 2;
    if (arr[mid] == mid) {
        return true;
    } else if (arr[mid] > mid){ 
        return process(arr, start, mid - 1); 
    } else { 
        return process(arr, mid + 1, end); 
    }
}

进阶：数组中有重复的值，判断是否存在魔术索引。

解法：如果数组元素有重复值，前面的算法就会失效。如果 A[mid] < mid，我们无法断定魔术索引位于数组哪一边。它可能在数组右侧，也可能在左侧。
二分递归：（也适用于不存在重复的值，暴力解法）

bool findMagicIndex(vector<int> A, int n) {
    // write code here
    return process(A, 0, A.size() - 1);
}
bool process(vector<int> arr, int start, int end) {
    if (start > end) return false;
    int mid = start + (end - start) / 2;
    if (arr[mid] == mid) {
        return true;
    } 

    return process(arr, start, mid - 1) || process(arr, mid + 1, end); 
}

5.5 子集

描述：

已知数组A和其大小n，请返回A的所有非空子集。要求A中元素个数不大于20且互异。各子集内部从大到小排序,子集间字典逆序排序。

1
2
3

测试样例：
[123,456,789]
返回：{[789,456,123],[789,456],[789,123],[789],[456 123],[456],[123]}

解法：

递归，path记录中间过程。

vector<vector<int>> res;
vector<int> path;
vector<vector<int> > getSubsets(vector<int> A, int n) {
    // write code here
    sort(A.begin(), A.end(),[](int a, int b) {return a > b;});
    // res.clear();
    // path.clear();
    recur(A, 0);
    reverse(res.begin(), res.end());
    return res;
}

void recur(vector<int>& arr, int index) {
    if (!path.empty()) res.push_back(path);

    if (index >= arr.size()) return;

    for (int i = arr.size() - 1; i >= index; i--) {
        path.push_back(arr[i]);
        recur(arr, i + 1);
        path.pop_back();
    }
}