Neo's Blog

不抽象就无法深入思考
不还原就看不到本来面目!

0%

Posted on Edited on In , Valine:

二叉搜索树转有序双向链表-题目描述

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。

要求不能创建任何新的结点，只能调整树中结点指针的指向。

注意：

需要返回双向链表最左侧的节点。
例如，输入下图中左边的二叉搜索树，则输出右边的排序双向链表。

二叉搜索树转有序双向链表-总体思路

两种思路：

第一种思路，dfs的主要任务是返回子树对应链表的头尾节点；按照这种思路的话，我们的遍历方式是后序遍历。

第二种思路，dfs的主要任务就是按照顺序访问到每一个node，同时记录一个全局的pre，然后将pre与node建立双向关联即可。

二叉搜索树转有序双向链表-代码实现

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
pair<Node*, Node*> dfs(Node* root) {
    if (!(root->left) && !(root->right)) {
        root->left = root;
        root->right = root;
        return {root, root};
    }
    
    //访问左边
    pair<Node*, Node*>  left = {root, root};
    if (root->left) {
        left = dfs(root->left);
    }

    //访问右边
    pair<Node*, Node*>  right = {root, root};
    
    if (root->right) {
        right = dfs(root->right);
    }

    //访问中间节点
    if (left.first != root) {
        left.second->right = root;
        root->left = left.second;
    }

    if (right.first != root) {
        root->right = right.first;
        right.first->left = root;
    }
 
    return {left.first, right.second};
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void  dfs(Node* root) {
       if (!root) return;
       
       //访问左边
       dfs(root->left);

       //中序遍历
       if (!pre) {
           head = root;
       }
       else {
           pre->right = root;
           root->left = pre;
       }
       pre = root;

       //访问右边
       dfs(root->right);
   }

Posted on Edited on In , Valine:

判断该数组是不是某二叉搜索树的后序遍历的结果-题目描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。

如果是则返回true，否则返回false。

假设输入的数组的任意两个数字都互不相同。

样例
输入：[4, 8, 6, 12, 16, 14, 10]

输出：true

判断该数组是不是某二叉搜索树的后序遍历的结果-总体思路

分为几步：
（1）根据后序遍历序列的定义，最右边的元素是中间节点X，并且左子树的元素均小于X，右子树的元素均大于X
（2）顺序扫描，找到左右子树的分割点Y(分割点左边都小于X)
（3）从分割点Y继续扫描，确认是否有bad case，有的话，直接返回不合法
（4）递归处理左右两部分

判断该数组是不是某二叉搜索树的后序遍历的结果-代码实现

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
class Solution {
public:
    vector<int> s;
    bool dfs(int l, int r) {
        if (l >= r) return true;
        
        //找到分界点
        int k = l;
        while (k < r && s[k] < s[r]) k++;
        
        //确认分界点之后的元素是否都足够大
        for (int i = k; i< r; ++i) {
            if (s[i] < s[r]) {
                return false;
            }
        }
        
        //递归处理
        return dfs(l, k - 1) && dfs(k, r - 1);
        
    }
    
    bool verifySequenceOfBST(vector<int> sequence) {
        s = sequence;
        if (s.empty()) return true;
        return dfs(0, s.size() - 1);
    }
};

Posted on Edited on In , Valine:

反转单词-题目描述

输入一个英文句子，单词之前用一个空格隔开，且句首和句尾没有多余空格。翻转句子中单词的顺序，但单词内字符的顺序不变。

为简单起见，标点符号和普通字母一样处理。

例如输入字符串”I am a student.”，则输出”student. a am I”。

样例
输入：”I am a student.”

输出：”student. a am I”

反转单词-代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    void reverse(string& s, int i, int j) {
        while (i < j) {
            swap(s[i++], s[j--]);
        }
    }
    
    string reverseWords(string s) {
        int i = 0, j = 0;
        while (s[j] != '\0') {
            if (s[j] == ' ') {
                reverse(s, i, j - 1); //反转每一个
                i = j + 1;
            }
            j++;
        }
        reverse(s, i, j - 1); //处理上面的最后一次循环

        //整体反转一次
        reverse(s, 0, j - 1);
        return s;
    }
};

字符串左旋转-题目描述

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。

请定义一个函数实现字符串左旋转操作的功能。

比如输入字符串”abcdefg”和数字2，该函数将返回左旋转2位得到的结果”cdefgab”。

注意：

数据保证n小于等于输入字符串的长度。
样例
输入：”abcdefg” , n=2

输出：”cdefgab”

字符串左旋转-代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    void reverse(string& s, int i, int j ) {
        //对撞指针，往中间凑
        while (i < j) {
            swap(s[i++], s[j--]);
        }
    }
    string leftRotateString(string str, int k) {
        int n = str.size();
        if (k == 0) return str;
        
        reverse(str, 0, k - 1);
        reverse(str, k, n - 1);
        reverse(str, 0, n - 1);
        return str;
    }
};

Posted on Edited on In Valine:

二数之和-题目描述

输入一个数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。

如果有多对数字的和等于s，输出任意一对即可。

你可以认为每组输入中都至少含有一组满足条件的输出。

样例

输入：[1,2,3,4] , sum=7

输出：[3,4]

二数之和-总体思路

（1）Hash $O(n)$

（2）排序后，双指针 $O(nlgn)$

二数之和-代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> findNumbersWithSum(vector<int>& nums, int target) {
        unordered_map<int, int> hash;
        for (int i = 0; i < nums.size(); ++i) {
            hash[nums[i]] = i;
        }
        vector<int> res(2, 0);
        for (int i = 0; i < nums.size(); ++i) {
            auto r = hash.find(target - nums[i]);
            if (r != hash.end()) {
                res[0] = nums[i];
                res[1] = nums[r->second];
            }
        }
        return res;
    }
};

连续序列和-题目描述

输入一个正数s，打印出所有和为s的连续正数序列（至少含有两个数）。

例如输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以结果打印出3个连续序列1～5、4～6和7～8。

样例
输入：15

输出：[[1,2,3,4,5],[4,5,6],[7,8]]

连续序列和-总体思路

首先最容易想到的思路：
（1）用两个下标i,j分别指向序列的开始结束位置
（2）用等差序列求和公式计算和是否等于S，如果等于S，则记录答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
        vector<vector<int> > findContinuousSequence(int t) {
        int i = 1, j = 1;
        int sum = 0;
        for (int i = 1; i < t; i++) { //结束位置
            for (j = 1; j < i; j++) { //开始位置
                if (S[i, j] == t) {
                    //add to result
                }
            }
        }
        return res; 
    }
};

以上时间复杂度为$O(n^2)$

这里有一个经验：
如果你的算法需要从$O(n^2)$优化到$O(n)$, 一般情况下我们可以考虑三种常用手段：双指针、单调队列、单调栈。这三种常用手段都充分利用了这个基本事实：内层循环变量j伴随外层循环变量i单调变化，此处单调变化指的是：i往前走一步，j也只会增加而不会回退。

根据上面的经验，我们重新审视变量j与变量i的关系发现，确实有单调性，所以我们可以通过双指针来优化。

还有一点特别重要，那就是代码模版，我们需要非常熟悉各种常见的算法模版，以下为双指针算法的代码模版：

1
2
3
4
5
6
7
8
void two_pointer() {
    int i, j;
    while (i < n) {
        //新来一个元素
        while (j < n && check(j)) j++; 
    }
}

连续序列和-代码实现

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
class Solution {
public:
        vector<vector<int> > findContinuousSequence(int t) {
        int i = 1, j = 1;
        int sum = 0;
        vector<vector<int> > res; //[i, j-1]的和，明确sum的含义
        while (j < t) {
            if (sum > t) {
                while (sum > t) {
                    sum -= i;
                    i++;
                }
            }
            else {
                sum += j;
                j++;
            }
            
            if (sum == t) {
                int p = i;
                vector<int> one;
                while (p <= j - 1) {
                    one.push_back(p++);
                }
                res.push_back(one);
            }
        }  

        return res; 
    }
};

Posted on Edited on In Valine:

找到仅出现一次的数，其他数出现二次

一个整型数组里除了两个数字之外，其他的数字都出现了两次。

请写程序找出这两个只出现一次的数字。

你可以假设这两个数字一定存在。

样例
输入：[1,2,3,3,4,4]

输出：[1,2]

实现思路-基于XOR

代码实现-基于XOR

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
class Solution {
public:
        vector<int> findNumsAppearOnce(vector<int>& nums) {
        int s = 0;
        for (auto x: nums) {
            s ^= x;
        }

        int u = s & -s; //找到lowbit
        vector<int> g0, g1;

        for (auto x: nums) {
            if (x & u ) g1.push_back(x);
            else g0.push_back(x); 
        }

        vector<int> res(2, 0);
        for (auto x : g0) {
            res[0] ^= x;
        }
        for (auto x : g1) {
            res[1] ^= x;
        }

        return res;
    }
};

找到仅出现一次的数，其他数都出现三次

在一个数组中除了一个数字只出现一次之外，其他数字都出现了三次。

请找出那个只出现一次的数字。

你可以假设满足条件的数字一定存在。

思考题：

如果要求只使用 O(n) 的时间和额外 O(1) 的空间，该怎么做呢？
样例
输入：[1,1,1,2,2,2,3,4,4,4]

输出：3

实现思路-基于Bit位

如果可以用hash，存下每一个数字出现次数就可以了。

但是如果要求O(1)的时间复杂度呢？考虑用位运算。

代码实现-基于Bit位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int findNumberAppearingOnce(vector<int>& nums) {
        vector<int> bitmap(32, 0);
        for (auto x: nums) {
            for (int i = 0; i < 32; ++i) {
                if (x & (1 << i)) bitmap[i]++;
            }
        }
        int res = 0;
        for (int i = 0; i < 32; ++i) {
            if (bitmap[i] % 3) {
                res += 1 << i;
            }
        }
        return res;
    }
};

Posted on Edited on In Valine:

题目描述

输入一棵二叉树的根结点，判断该树是不是平衡二叉树。

如果某二叉树中任意结点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

注意：

规定空树也是一棵平衡二叉树。
样例
输入：二叉树[5,7,11,null,null,12,9,null,null,null,null]如下所示，
5
/ \
7 11
/ \
12 9

输出：true

实现思路

第一，我们要搞清楚几个概念：树的深度、一个节点的深度与高度。

第二，我们需要知道：深度是从上往下的，我们需要前序遍历。

第三，我们需要知道：高度是从下往上的，我们需要后序遍历。

最后，根节点比较特殊，树的深度，等于根节点的高度，也就是root到所有leaf的最长路径。

综上，该题目还是后序遍历。

代码实现

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 * 
 */
 
typedef pair<bool, int> PBI;
 
class Solution {
public:
    
    //没有正确使用全局变量
    PBI dfs(TreeNode* root) {
        if (!root) return {true, 0};

        auto lbi = dfs(root->left);
        if (!lbi.first) return {false, 0};

        auto rbi = dfs(root->right);
        if (!rbi.first) return {false, 0};

        if (abs(lbi.second - rbi.second) > 1) {
            return {false, 0};
        } 
        else {
            return {true, 1 + max(lbi.second, rbi.second)};
        }
    }

    //学会使用全局变量， flag
    int dfs(TreeNode* root) {
        if (!root) return 0;

        int lh = dfs(root->left);
        int rh = dfs(root->right);

        if (abs(lh - rh) > 1) {
            g_flag = false;
            return 0;
        }

        return 1 + max(lh, rh);
    }

    bool isBalanced(TreeNode* root) {
        return dfs(root).first;
    }
};

Posted on Edited on In , Valine:

题目描述

输入一棵二叉树的根结点，求该树的深度。

从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

样例
输入：二叉树[8, 12, 2, null, null, 6, 4, null, null, null, null]如下图所示：
8
/ \
12 2
/ \
6 4

输出：3

实现思路

第一，我们要搞清楚几个概念：树的深度、一个节点的深度与高度。

第二，我们需要知道：深度是从上往下的，我们需要前序遍历。

第三，我们需要知道：高度是从下往上的，我们需要后序遍历。

最后，根节点比较特殊，树的深度，等于根节点的高度，也就是root到所有leaf的最长路径。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int dfs(TreeNode* root) {
        if (!root) return 0;
        return 1 + max(dfs(root->right), dfs(root->left));

    }
    int treeDepth(TreeNode* root) {
        return dfs(root);
    }
};

Posted on Edited on In Valine:

题目描述

写一个函数，求两个整数之和，要求在函数体内不得使用＋、－、×、÷ 四则运算符号。

样例
输入：num1 = 1 , num2 = 2

输出：3

思路

经验知识1：位运算的特点之一是在二进制表示下不进位，参与位运算的各个bit之间是独立无关的。

经验知识2: XOR又称作无进位加法

经验知识3: 计算机便是通过XOR，与操作，移位操作来实现加法的，具体的做法可以见下面的代码。

相信如果你有上面三块知识储备，想出该题目的解法是没有问题的。

这里多说一句，为什么别人可以想出正确的解法，而我们不可以。原因有两个：

第一，别人知道某块知识，而我们不知道。

第二，（需要使用到的知识我们是知道的）别人能够通过发散思维，或者启发式思考调取需要用到的知识储备，而我们却不行。

针对以上两点，我们的解法是：

第一，学习更多的知识、经验、技巧，有更多的知识储备。

第二，不仅仅要学习知识、经验、技巧，还要去尝试着去做深度、广度的思考。深度的话，我们多问几个为什么，去剖析本质，找到他们的第一性原理。广度的话，我们要去做类比，要去做关联，了解两块知识的区别与联系。

第三，去做更多的刻意练习：多刷题，多解题，多推理证明，保证自己思维的严密性。

代码

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
class Solution {
public:
    int add(int num1, int num2){
        while (num2) {
            /*
            经过XOR操作后，1/0,0/1,0/0都已经符合预期了，只是1/1？ 本来应该成为10，却变成了0？
            我们怎样才能找回丢失的进位呢？ 只有&操作才能将两个1变为1，也许是我们好的选择？
            实际上，这就是计算机执行加法的底层原理。
            */
            int sum = num1 ^ num2;
            int carry = (num1 & num2) << 1;
            num1 = sum;
            num2 = carry;
            //用计算出来的结果重新赋值，有点辗转相除法的感觉。
        }
        return num1;
    }

    int sub(int num1, int num2) {
        //a - b = a + (-b)
        return add(num1, add(~num2, 1)))
    }

    
    int mul(int a, int b) {
        //最笨的方法是for循环--b次； 有没有更好的办法呢？ 
        //都转为正数先
        int a1 = a >= 0 ? a : add(~a, 1);
        int b1 = b >= 0 ? b : add(~b, 1);
        int sum = 0;
        //整个过程跟手动乘法类似
        while (b1) {
            if (b1 & 0x01) {
                sum = add(sum, a1);
            }
            a1 <<= 1;
            b1 >>= 1;
        }

        //异号，相反数
        if (a ^ b < 0) {
            sum = add(-sum, 1);
        }

        return sum;
    }

    int div(int a, int b, int& reminder) {
        int r = 0;
        //都转为正数先
        int a1 = a >= 0 ? a : add(~a, 1);
        int b1 = b >= 0 ? b : add(~b, 1);
        for (int i = 31; i >= 0; i--) {
            if ((a1 >> i) >= b1) { // a >= (b << i)
                r = add(r, 1 << i);
                a1 = sub(a1, b1 << i);
            }
        }

         //异号，相反数
        if (a ^ b < 0) {
            r = add(~r, 1);
        }

        reminder = a1;
        return r;
    }
};


Posted on Edited on Valine:

求1+2+…+n,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

样例
输入：10

输出：55

思路

常用技巧： 通过!n来判定n是否等于0

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
typedef int (*handler)(int);
handler fn[2]; 

int dfs(int n) {
    handler myfn= fn[!!n];
    return myfn(n);
}

int dfs_base(int n) {
    return 0;    
}

int dfs_normal(int n) {
    return n + dfs(n - 1);
}

class Solution {
public:
    int getSum(int n) {
        fn[0] = dfs_base;
        fn[1] = dfs_normal;
        return dfs(n);
    }
};

Posted on Edited on In Valine:

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

输入一个升序的数组的一个旋转，输出旋转数组的最小元素。

例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。

数组可能包含重复项。

注意：数组内所含元素非负，若数组大小为0，请返回-1。

样例
输入：nums=[2,2,2,0,1]

输出：0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int findMin(vector<int>& nums) {
        if (nums.empty()) return -1;
        int n = nums.size() - 1;
        //特判
        while (nums[0] == nums[n]) {n--;}
        //特判
        if (nums[0] <= nums[n]) {
            return nums[0];
        }
        
        //二分模版
        int l = 0, r = n;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[0] > nums[mid]) r = mid;
            else  l = mid + 1;
        }
        
        return nums[r];
    }
};