zkkKillua's Blog
0%

发表于 更新于 分类于

1. 二分

要求复杂度是O(logn)，说明了是要二分。
结果只要求一个值，因此二分到nums[i-1] < nums[i] < nums[i+1]的i即可。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        int ans = 0;
        
        while (l <= r) {
            int mid = (l + r) / 2;
            if (l == r)
                ans = l++;
            else if (mid > 0 && nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]) {
                ans = mid;
                break;
            } else if (nums[mid] < nums[mid + 1])
                l = mid + 1;
            else if (nums[mid] > nums[mid + 1])
                r = mid - 1;
        }

        return ans;
    }
};

发表于 更新于 分类于

1. 朴素

直接O(n)扫描一遍，记录最大值索引。 

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int peakIndexInMountainArray(vector<int>& A) {
        int n = A.size();
        int ans = 0;
        for (int i = 0; i < n; i++)
            if (A[i] > A[ans])
                ans = i;
        
        return ans;
    }
};

2. 二分

二分根据mid判断是递增一侧还是递减一侧，复杂度O(logn)。

阅读全文 »

发表于 更新于 分类于

1. 递归

第一反应是双指针，s3判断一个，对应的s1或者s2向后移一位。
但问题在于，当s1和s2的当前位相同时，无法确定s1/s2向后移位。
如果加上回溯，则跟递归类似。
复杂度指数级。
可以通过记忆化降低复杂度。

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:
    bool isInterleave(string s1, string s2, string s3) {
        int m = s1.length(), n = s2.length();
        if (m + n != s3.length())
            return false;
      
        if (m == 0 && n == 0)
            return true;
        else if (m == 0) {
            if (s2[0] == s3[0])
                return isInterleave(s1, s2.substr(1), s3.substr(1));
            else
                return false;
        } else if (n == 0) {
            if (s1[0] == s3[0])
                return isInterleave(s1.substr(1), s2, s3.substr(1));
            else
                return false;
        } else {
            if (s1[0] == s3[0] && s2[0] != s3[0])
                return isInterleave(s1.substr(1), s2, s3.substr(1));
            else if (s1[0] != s3[0] && s2[0] == s3[0])
                return isInterleave(s1, s2.substr(1), s3.substr(1));
            else if (s1[0] == s3[0] && s2[0] == s3[0])
                return isInterleave(s1.substr(1), s2, s3.substr(1)) || isInterleave(s1, s2.substr(1), s3.substr(1));
            else
                return false;
        }
    }
};

2. 动态规划

f[i][j]代表s1的前i个字符和s2的前j个字符是否符合s3的前i+j个字符。

阅读全文 »

发表于 更新于 分类于

1. 动态规划

设G(n)是以1 … n为节点组成的二叉搜索树的种数，f(i)是以i为根节点的二叉搜索树的种数，则有：
G(n) = f(1) + f(2) + ... + f(n)
以f(i)为例，其左子树为1 … i-1节点组成的二叉搜索树，右子树为i+1 … n节点组成的二叉搜索树，即
f(i) = G(i - 1) * G(n - i)
综上，有：
G(n) = G(0)G(n-1) + G(1)G(n-2) + ... + G(n-1)G(0)
时间复杂度：(n^2)，需要算n个G(i)，每个需要O(n)。
空间复杂度：O(n)。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int numTrees(int n) {
        int* g = new int[n + 1]();
        // new的过程是 分配空间 - 使用默认构造函数初始化
        // 而对于内置数据类型，new仅分配内存而不进行初始化，需要加()表示进行初始化
        // int* a = new int [10](1, 2) 之类的这种在()内部指定值的方法是错误的
        // 上一行的()可以改为{}代表列表初始化
        g[0] = 1;
        g[1] = 1;

        for (int i = 2; i <= n; i++)
            for (int j = 0; j < i; j++)
                g[i] += g[j] * g[i - 1 - j];

        int ans = g[n];
        delete []g;

        return ans;
    }
};

发表于 更新于 分类于

1. 朴素

首先判断不删除字符的情况下，s本身是不是回文串。
之后遍历判断删除每个字符，剩下的部分是否是回文串。
时间O(n^2)，空间O(1)，超时。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool isPalindromic(const string& s) {
        int n = s.length();
        for (int i = 0; i < n / 2; i++) {
            if (s[i] != s[n - i - 1])
                return false;
        }
        return true;
    }
    bool validPalindrome(string s) {
        if (isPalindromic(s))
            return true;
        
        for (int i = 0; i < s.length(); i++) {
            if (isPalindromic(s.erase(i)))
                return true;
        }

        return false;
    }
};

2. 双指针+贪心

初始双指针指在s的左右两侧。

阅读全文 »

发表于 更新于 分类于

1. hash表

直接hash表记录次数，但是空间占用有点多。
时间O(n)，空间O(n). 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int, int> hashTable;
        for (int i = 0; i < nums.size(); i++)
            hashTable[nums[i]]++;
        
        int ans;
        for (unordered_map<int, int>::iterator it = hashTable.begin(); it != hashTable.end(); ++it)
            if (it->second == 1) {
                ans = it->first;
                break;
            }

        return ans;
    }
};

2.　位运算异或

偶数个相同的数据异或之后变成0，而任何数异或0还是它本身。
时间O(n)，空间O(1)。

阅读全文 »

发表于 更新于 分类于

相关

  1. 二叉树的前序遍历：144
  2. 二叉树的后序遍历：145

1. 递归

左根右直接递归实现。
时间O(n)，空间O(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
/**
 * 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:
    vector<int> inorderTraversal(TreeNode* root) {
        if (root == nullptr)
            return {};
        vector<int> ans;
        vector<int> leftAns = inorderTraversal(root->left);
        vector<int> rightAns = inorderTraversal(root->right);
        ans.insert(ans.end(), leftAns.begin(), leftAns.end());
        ans.push_back(root->val);
        ans.insert(ans.end(), rightAns.begin(), rightAns.end());

        return ans;
    }
};
阅读全文 »

发表于 更新于 分类于

相关

  1. 二叉树的前序遍历：144
  2. 二叉树的中序遍历：94
  3. 二叉树的后序遍历：145
  4. N叉树的后序遍历：590

1. 递归

跟二叉树一样，时间O(n)，空间O(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
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<int> preorder(Node* root) {
        if (root == nullptr)
            return {};
        
        vector<int> ans;
        ans.push_back(root->val);
        for (int i = 0; i < root->children.size(); i++) {
            vector<int> subArray = preorder(root->children[i]);
            ans.insert(ans.end(), subArray.begin(), subArray.end());
        }

        return ans;
    }
};
阅读全文 »

发表于 更新于 分类于

1. queue实现层次遍历

时间O(n)，空间O(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
/**
 * 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:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> q;
        vector<vector<int>> ans;

        if (root != nullptr)
            q.push(root);
        while (!q.empty()) {
            vector<int> sub;
            int qsz = q.size();
            while (qsz--) {
                TreeNode* temp = q.front();
                q.pop();
                sub.push_back(temp->val);
                if (temp->left != nullptr)
                    q.push(temp->left);
                if (temp->right != nullptr)
                    q.push(temp->right);
            }
            ans.push_back(sub);
        }

        return ans;
    }
};

发表于 更新于 分类于

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
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
class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {
        vals = new int[10];
        capacity = 10;
        minLoc = 0;
        size = 0;
    }
    
    ~MinStack() {
        delete []vals;
        vals = nullptr;
    }
    
    void push(int x) {      // 时间复杂度均摊`O(1)`
        if (size == capacity) {
            int* temp = new int[capacity * 2];
            capacity *= 2;
            for (int i = 0; i < size; i++)
                temp[i] = vals[i];
            
            delete []vals;
            vals = temp;
        }

        vals[size++] = x;
        if (x < vals[minLoc])
            minLoc = size - 1;
    }
    
    void pop() {            // 时间复杂度最坏`O(n)`
        if (size == 0)
            return;
        
        size--;
        if (minLoc == size) {
            minLoc = 0;
            for (int i = 1; i < size; i++)
                if (vals[i] < vals[minLoc])
                    minLoc = i;
        }
    }
    
    int top() {
        if (size == 0)
            return -1;
        return vals[size - 1];
    }
    
    int getMin() {
        if (size == 0)
            return -1;
        return vals[minLoc];
    }

private:
    int* vals;
    int capacity;
    int minLoc;
    int size;
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

2. 辅助栈

用一个辅助栈记录过程中的最小值，用额外O(n)的空间将pop()的复杂度降低为O(1)。
以下两种方式都可以：

阅读全文 »