coding-interview/binary_search.h at master · XiaotaoChen/coding-interview · GitHub

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
#ifndef BINARY_SEARCH_ALGS_
#define BINARY_SEARCH_ALGS_

#include <vector>
#include "data_structs/base_struct.h"

namespace binary_search {

// https://leetcode-cn.com/problems/divide-two-integers/

int divide(int dividend, int divisor);

// https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
int search(std::vector<int>& nums, int target);
int dfs_search(std::vector<int>& nums, int start, int end , int target);

// https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
double findMedianSortedArrays(std::vector<int>& nums1, std::vector<int>& nums2);
int dfs_find_median_num(std::vector<int>& nums1, int low1, std::vector<int>& nums2, int low2, int k);

// https://leetcode-cn.com/problems/binode-lcci/
TreeNode* convertBiNode(TreeNode* root);
void dfs_binode(TreeNode* root, TreeNode*& pre);

// https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/
TreeNode* bstToGst(TreeNode* root);

void dfs_bstToGst(TreeNode* root, TreeNode*& pre);

// https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/
int dfs_max_path_sum(TreeNode* root, int& curr);
int maxPathSum(TreeNode* root);

// https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
std::vector<int> searchRange(std::vector<int>& nums, int target);
int dfs_searchrange(std::vector<int>& nums, int target, int left, int right);


std::vector<int> searchRange_v2(std::vector<int>& nums, int target);

// https://leetcode-cn.com/problems/search-a-2d-matrix/
bool dfs_searchmatrix(std::vector<std::vector<int>>& matrix, int start, int end, int target);

bool searchMatrix(std::vector<std::vector<int>>& matrix, int target);

// https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix/
int kthSmallest(std::vector<std::vector<int>>& matrix, int k);
int kthsmallest_cnt(std::vector<std::vector<int>> & matrix, int val);


// search next node
TreeLinkNode* next_node(TreeLinkNode* node);

// https://leetcode-cn.com/problems/search-insert-position/
int searchInsert(std::vector<int>& nums, int target);

int searchInsert_v2(std::vector<int>& nums, int target);

}

#endif