书脊 | 这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.

Search in a Sorted Array of Unknown Size

给一个api,输入一个index, 返回元素值, 问怎么用这个api在一个不知道大小(并不是无限大)的已排序的数组上做二叉搜索.

二叉肯定要有右边的大小, 所以问题变成怎么快速找到右边的值, 用二次倍增法找

/**
 * // This is the ArrayReader's API interface.
 * // You should not implement it, or speculate about its implementation
 * class ArrayReader {
 *   public:
 *     int get(int index);
 * };
 */

class Solution {
public:
    int search(const ArrayReader& reader, int target) {
        int i = 0;
        int j = 1;
        while(reader.get(j) != 2147483647){
            j = j << 1;
        }
        while(i <= j) {
            int mid = i + (j - i) / 2;
            if(reader.get(mid) == target){
                return mid;
            }
            else if(reader.get(mid) > target){
                j = mid - 1;
            }else{
                i = mid + 1;
            }
        }
        return -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

/**

* // This is the ArrayReader's API interface.

* // You should not implement it, or speculate about its implementation

* class ArrayReader {

* public:

* int get(int index);

* };

*/

class Solution {

public:

int search(const ArrayReader& reader, int target) {

int i = 0;

int j = 1;

while(reader.get(j) != 2147483647){

j = j << 1;

}

while(i <= j) {

int mid = i + (j - i) / 2;

if(reader.get(mid) == target){

return mid;

}

else if(reader.get(mid) > target){

j = mid - 1;

}else{

i = mid + 1;

}

return -1;

}

};

Date May 10, 2021
Category Leetcode
Comments No Comments

Binary Tree Pruning

给一个二叉树, 求删除值为0并且左右两边都是nullptr的分支.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* pruneTree(TreeNode* root) {
        if(!root)
            return root;
        root->left = pruneTree(root->left);
        root->right = pruneTree(root->right);
        if(!root->val && !root->left && !root->right)
            return nullptr;
        else
            return root;
    }
};

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() : val(0), left(nullptr), right(nullptr) {}

* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

* };

*/

class Solution {

public:

TreeNode* pruneTree(TreeNode* root) {

if(!root)

return root;

root->left = pruneTree(root->left);

root->right = pruneTree(root->right);

if(!root->val && !root->left && !root->right)

return nullptr;

else

return root;

}

};

Date May 9, 2021
Category Leetcode
Comments No Comments

Diameter of N-Ary Tree

给一个n-ary的树, 求周长. 就是任意两个node之间的最长距离, 可以不经过root.

最长的路径出现在两个情况, 情况一是路径经过node, 那么就是左右两边的最长路径相加, 要不然就是一侧,就是最长路径. 所以要求出最长路径和次长路径, 然后比较一下.

/*
// 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:
     int res = 0;
     int dfs(Node* root) {
        if (!root) 
            return 0;
        vector<int> v;
        for (auto &c: root->children) {
            v.push_back(f(c));
        }
         sort(v.begin(), v.end(), greater<int>());
        auto l1 = 0, l2 = 0;
         int n = v.size();
         if(n > 0){
             l1 = v[0];
         }
         if(n > 1){
             l2 = v[1];
         }
        res = max(res, l1 + l2);
        return 1 + max(l1, l2);
    }
    
    int diameter(Node* root) {
        dfs(root);
        return res;
    }
    
};

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

/*

// 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:

int res = 0;

int dfs(Node* root) {

if (!root)

return 0;

vector<int> v;

for (auto &c: root->children) {

v.push_back(f(c));

}

sort(v.begin(), v.end(), greater<int>());

auto l1 = 0, l2 = 0;

int n = v.size();

if(n > 0){

l1 = v[0];

}

if(n > 1){

l2 = v[1];

}

res = max(res, l1 + l2);

return 1 + max(l1, l2);

}

int diameter(Node* root) {

dfs(root);

return res;

}

};

Date May 8, 2021
Category Leetcode
Comments No Comments

Find All Duplicates in an Array

给一个数组, 里面的数字出现一次或者两次, 求出现一次的数字的数组.

这题要用set很简单, 不用的话, 可以把负数当作set查重用. 当数字做为坐标的时候用abs取下值

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> res;
        int n = nums.size();
        for(int i = 0; i < n; i++){
            if(nums[abs(nums[i]) - 1] < 0){
                res.push_back(abs(nums[i]));
            }else{
                nums[abs(nums[i]) - 1] = -nums[abs(nums[i]) - 1];
            }
        }
        return res;
    }
};

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution {

public:

vector<int> findDuplicates(vector<int>& nums) {

vector<int> res;

int n = nums.size();

for(int i = 0; i < n; i++){

if(nums[abs(nums[i]) - 1] < 0){

res.push_back(abs(nums[i]));

}else{

nums[abs(nums[i]) - 1] = -nums[abs(nums[i]) - 1];

}

return res;

}

};

Date May 8, 2021
Category Leetcode
Comments No Comments

Queens That Can Attack the King

给一堆国际象棋的queen的坐标, 和一个king的坐标, 问那些queen可以找到king.

主要是看到queen坐标的边界是63, 然后8个方向dfs找即可.

class Solution {
public:
    int dirs[8][2] = {
        {1,1},
        {1,0},
        {1,-1},
        {0,1},
        {0,-1},
        {-1,1},
        {-1,0},
        {-1,-1}
    };
    vector<vector<int>> queensAttacktheKing(vector<vector<int>>& queens, vector<int>& king) {
        vector<vector<int>> res;
        int maxX = 0;
        int maxY = 0;
        set<pair<int, int>> qs;
        for(auto q : queens){
            maxX = max(maxX, q[0]);
            maxY = max(maxY, q[1]);
            qs.emplace(pair<int, int>(q[0], q[1]));
        }
        for(auto d : dirs) {
            int kx = king[0];
            int ky = king[1];
            while(kx >= 0 && ky >= 0 && kx <= 63 && ky <= 63){
                kx += d[0];
                ky += d[1];
                if(qs.find(pair<int, int>(kx,ky)) != qs.end()){
                    vector<int> vv{kx,ky};
                    res.push_back(vv);
                    break;
                }
            }
        }
        return res;         
    }
};

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

class Solution {

public:

int dirs[8][2] = {

{1,1},

{1,0},

{1,-1},

{0,1},

{0,-1},

{-1,1},

{-1,0},

{-1,-1}

};

vector<vector<int>> queensAttacktheKing(vector<vector<int>>& queens, vector<int>& king) {

vector<vector<int>> res;

int maxX = 0;

int maxY = 0;

set<pair<int, int>> qs;

for(auto q : queens){

maxX = max(maxX, q[0]);

maxY = max(maxY, q[1]);

qs.emplace(pair<int, int>(q[0], q[1]));

}

for(auto d : dirs) {

int kx = king[0];

int ky = king[1];

while(kx >= 0 && ky >= 0 && kx <= 63 && ky <= 63){

kx += d[0];

ky += d[1];

if(qs.find(pair<int, int>(kx,ky)) != qs.end()){

vector<int> vv{kx,ky};

res.push_back(vv);

break;

}

return res;

}

};

Date May 7, 2021
Category Leetcode
Comments No Comments

Maximum Difference Between Node and Ancestor

给一个二叉树, 求任意父节点和子节点的最大差.

按个找..

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxAncestorDiff(TreeNode root) {
        
    }
}

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.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode() {}

* TreeNode(int val) { this.val = val; }

* TreeNode(int val, TreeNode left, TreeNode right) {

* this.val = val;

* this.left = left;

* this.right = right;

* }

*/

class Solution {

public int maxAncestorDiff(TreeNode root) {

}

Date May 7, 2021
Category Leetcode
Comments No Comments

Two Sum BSTs

给两个bst, 然后看是不是能做two sum.

先用inorder变成array, 然后做two sum.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool twoSumBSTs(TreeNode* root1, TreeNode* root2, int target) {
        vector<int> v; 
        inorder(root1, v); 
        return twosum(v, root2, target);
    }
    void inorder(TreeNode* root, vector<int>& v){
        if(!root)
            return;
        inorder(root->left, v);
        v.push_back(root->val);
        inorder(root->right, v);
    } 
    bool twosum(vector<int>& v, TreeNode* root, int t) {
        if(!root)
            return false;
        return binary_search(v.begin(), v.end(), t - root->val) || twosum(v, root->left, t) || twosum(v, root->right, t);;
    }
};

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

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode() : val(0), left(nullptr), right(nullptr) {}

* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

* };

*/

class Solution {

public:

bool twoSumBSTs(TreeNode* root1, TreeNode* root2, int target) {

vector<int> v;

inorder(root1, v);

return twosum(v, root2, target);

}

void inorder(TreeNode* root, vector<int>& v){

if(!root)

return;

inorder(root->left, v);

v.push_back(root->val);

inorder(root->right, v);

}

bool twosum(vector<int>& v, TreeNode* root, int t) {

if(!root)

return false;

return binary_search(v.begin(), v.end(), t - root->val) || twosum(v, root->left, t) || twosum(v, root->right, t);;

}

};

Date May 7, 2021
Category Leetcode
Comments No Comments

Distinct Numbers in Each Subarray

给一个数组和一个数字k, 求数组中k大小的subarray的不同的数字的个数.

用map当滑窗计算一下

class Solution {
public:
    vector<int> distinctNumbers(vector<int>& nums, int k) {
        vector<int> res;
        int n = nums.size();
        unordered_map<int, int> map; 
        for(int i = 0; i < n; i++){
            if(i < k){
                map[nums[i]]++;
            }else{
                res.push_back(map.size());
                map[nums[i - k]]--;
                if(map[nums[i - k]] == 0){
                    map.erase(nums[i - k]);
                }
                map[nums[i]]++;
            }
        }
        res.push_back(map.size());
        return res;
    }
};

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:

vector<int> distinctNumbers(vector<int>& nums, int k) {

vector<int> res;

int n = nums.size();

unordered_map<int, int> map;

for(int i = 0; i < n; i++){

if(i < k){

map[nums[i]]++;

}else{

res.push_back(map.size());

map[nums[i - k]]--;

if(map[nums[i - k]] == 0){

map.erase(nums[i - k]);

}

map[nums[i]]++;

}

res.push_back(map.size());

return res;

}

};

Date May 7, 2021
Category Leetcode
Comments No Comments

Replace All Digits with Characters

给一个string, 里面有偶数位的字符和奇数位的数字组成, 给一个方法decode这个string, 是用字符后的数字位个字符代替数字位. 求decoded string.

class Solution {
public:
    string replaceDigits(string s) {
        int n = s.size();
        for(int i = 1; i < n; i+=2){
            char c = (char)(s[i - 1] + (s[i] - '0'));
            s[i] = c;
        }
        return s;
    }
};

1

2

3

4

5

6

7

8

9

10

11

class Solution {

public:

string replaceDigits(string s) {

int n = s.size();

for(int i = 1; i < n; i+=2){

char c = (char)(s[i - 1] + (s[i] - '0'));

s[i] = c;

}

return s;

}

};

Date May 6, 2021
Category Leetcode
Comments No Comments

Seat Reservation Manager

设计一个座位预约系统.

用treeset,因为里面有可以直接访问第一个可用key的方法.

class SeatManager {
public:
    set<int> s;
    SeatManager(int n) {
        for(int i = 1; i <= n; i++){
            s.emplace(i);
        }
    }
    
    int reserve() {
        auto r = *s.begin();
        s.erase(*s.begin());
        return r;
    }
    
    void unreserve(int seatNumber) {
        s.emplace(seatNumber);
    }
};

/**
 * Your SeatManager object will be instantiated and called as such:
 * SeatManager* obj = new SeatManager(n);
 * int param_1 = obj->reserve();
 * obj->unreserve(seatNumber);
 */

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

class SeatManager {

public:

set<int> s;

SeatManager(int n) {

for(int i = 1; i <= n; i++){

s.emplace(i);

}

int reserve() {

auto r = *s.begin();

s.erase(*s.begin());

return r;

}

void unreserve(int seatNumber) {

s.emplace(seatNumber);

}

};

/**

* Your SeatManager object will be instantiated and called as such:

* SeatManager* obj = new SeatManager(n);

* int param_1 = obj->reserve();

* obj->unreserve(seatNumber);

*/

Date May 6, 2021
Category Leetcode
Comments No Comments

Search in a Sorted Array of Unknown Size

Binary Tree Pruning

Diameter of N-Ary Tree

Find All Duplicates in an Array

Queens That Can Attack the King

Maximum Difference Between Node and Ancestor

Two Sum BSTs

Distinct Numbers in Each Subarray

Replace All Digits with Characters

Seat Reservation Manager

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.

Categories

Tags