Skip to content

Commit fa682d2

Browse files
da183da183
committed
binary op questions
1 parent c63d288 commit fa682d2

File tree

7 files changed

+625
-688
lines changed

7 files changed

+625
-688
lines changed

‎advanced_algorithm/binary_search_tree.md‎

Lines changed: 34 additions & 37 deletions
Original file line numberDiff line numberDiff line change
@@ -12,47 +12,44 @@
1212
> 验证二叉搜索树
1313
1414
```c++
15-
class Solution {
16-
public:
17-
struct Result {
18-
TreeNode *maxNode;
19-
TreeNode *minNode;
20-
bool isValidate;
15+
struct Result {
16+
TreeNode *maxNode;
17+
TreeNode *minNode;
18+
bool isValidate;
2119

22-
Result(bool validate = true, TreeNode *max = nullptr, TreeNode *min = nullptr)
23-
: isValidate(validate), maxNode(max), minNode(min) {
20+
Result(bool validate = true, TreeNode *max = nullptr, TreeNode *min = nullptr)
21+
: isValidate(validate), maxNode(max), minNode(min) {
2422

25-
}
26-
};
27-
bool isValidBST(TreeNode *root) {
28-
if (!root) {
29-
return true;
30-
}
31-
return helper(root).isValidate;
32-
}
33-
34-
Result helper(TreeNode *root) {
35-
if (!root) {
36-
return {};
37-
}
38-
auto left = helper(root->left);
39-
auto right = helper(root->right);
40-
if (!(left.isValidate && right.isValidate)) {
41-
return {false};
42-
}
43-
if (left.maxNode && left.maxNode->val >= root->val) {
44-
return {false};
45-
}
46-
if (right.minNode && right.minNode->val <= root->val) {
47-
return {false};
48-
}
49-
return {
50-
true,
51-
right.maxNode ? right.maxNode : root,
52-
left.minNode ? left.minNode : root,
53-
};
5423
}
5524
};
25+
bool isValidBST(TreeNode *root) {
26+
if (!root) {
27+
return true;
28+
}
29+
return helper(root).isValidate;
30+
}
31+
32+
Result helper(TreeNode *root) {
33+
if (!root) {
34+
return {};
35+
}
36+
auto left = helper(root->left);
37+
auto right = helper(root->right);
38+
if (!(left.isValidate && right.isValidate)) {
39+
return {false};
40+
}
41+
if (left.maxNode && left.maxNode->val >= root->val) {
42+
return {false};
43+
}
44+
if (right.minNode && right.minNode->val <= root->val) {
45+
return {false};
46+
}
47+
return {
48+
true,
49+
right.maxNode ? right.maxNode : root,
50+
left.minNode ? left.minNode : root,
51+
};
52+
}
5653
```
5754
5855
[insert-into-a-binary-search-tree](https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/)

‎basic_algorithm/binary_search.md‎

Lines changed: 63 additions & 77 deletions
Original file line numberDiff line numberDiff line change
@@ -266,33 +266,27 @@ int findMin(vector<int>& nums) {
266266
> 请找出其中最小的元素。(包含重复元素)
267267
268268
```c++
269-
func findMin(nums []int) int {
270-
// 思路：跳过重复元素，mid值和end值比较，分为两种情况进行处理
271-
if len(nums) == 0 {
272-
return -1
269+
int findMin(vector<int> &nums) {
270+
if (nums.empty()) {
271+
return -1;
273272
}
274-
start := 0
275-
end := len(nums) - 1
276-
for start+1 < end {
277-
// 去除重复元素
278-
for start < end && nums[end] == nums[end-1] {
279-
end--
273+
auto left = 0;
274+
auto right = nums.size() - 1;
275+
while (left + 1 < right) {
276+
while (left < right && nums[right] == nums[right - 1]) {
277+
--right;
280278
}
281-
for start < end && nums[start] == nums[start+1] {
282-
start++
279+
while (left < right && nums[left] == nums[left + 1]) {
280+
++left;
283281
}
284-
mid := start + (end-start)/2
285-
// 中间元素和最后一个元素比较（判断中间点落在左边上升区，还是右边上升区）
286-
if nums[mid] <= nums[end] {
287-
end = mid
282+
auto mid = left + (right - left) / 2;
283+
if (nums[mid] <= nums[right]) {
284+
right = mid;
288285
} else {
289-
start = mid
286+
left = mid;
290287
}
291288
}
292-
if nums[start] > nums[end] {
293-
return nums[end]
294-
}
295-
return nums[start]
289+
return (nums[left] >= nums[right]) ? nums[right] : nums[left];
296290
}
297291
```
298292

@@ -303,41 +297,40 @@ func findMin(nums []int) int {
303297
> 搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回  -1 。
304298
> 你可以假设数组中不存在重复的元素。
305299
306-
```go
307-
func search(nums []int, target int) int {
308-
// 思路：/ / 两条上升直线，四种情况判断
309-
if len(nums) == 0 {
310-
return -1
300+
```c++
301+
int search(vector<int> &nums, int target) {
302+
if (nums.empty()) {
303+
return -1;
311304
}
312-
start := 0
313-
end := len(nums) - 1
314-
for start+1 < end {
315-
mid := start + (end-start)/2
316-
// 相等直接返回
317-
if nums[mid] == target {
318-
return mid
305+
auto left = 0;
306+
auto right = nums.size() - 1;
307+
while (left + 1 < right) {
308+
auto mid = left + (right - left) / 2;
309+
if (nums[mid] == target) {
310+
return mid;
319311
}
320-
// 判断在那个区间，可能分为四种情况
321-
if nums[start] < nums[mid] {
322-
if nums[start] <= target && target <= nums[mid] {
323-
end = mid
312+
if (nums[left] < nums[mid]) {
313+
if (nums[left] <= target && target <= nums[mid]) {
314+
right = mid;
324315
} else {
325-
start = mid
316+
left = mid;
326317
}
327-
} else if nums[end] > nums[mid] {
328-
if nums[end] >= target && nums[mid] <= target {
329-
start = mid
318+
} else if (nums[mid] < nums[right]) {
319+
// 这个判断是必须的！当只有两个数的时候，可能两个都不满足！
320+
if (target >= nums[mid] && nums[right] >= target) {
321+
right = mid;
330322
} else {
331-
end = mid
323+
left = mid;
332324
}
333325
}
334326
}
335-
if nums[start] == target {
336-
return start
337-
} else if nums[end] == target {
338-
return end
327+
if (nums[left] == target) {
328+
return left;
329+
} else if (nums[right] == target) {
330+
return right;
331+
} else {
332+
return -1;
339333
}
340-
return -1
341334
}
342335
```
343336
@@ -351,46 +344,39 @@ func search(nums []int, target int) int {
351344
> ( 例如，数组  [0,0,1,2,2,5,6]  可能变为  [2,5,6,0,0,1,2] )。
352345
> 编写一个函数来判断给定的目标值是否存在于数组中。若存在返回  true，否则返回  false。(包含重复元素)
353346
354-
```go
355-
func search(nums []int, target int) bool {
356-
// 思路：/ / 两条上升直线，四种情况判断，并且处理重复数字
357-
if len(nums) == 0 {
358-
return false
347+
```c++
348+
bool search(vector<int>& nums, int target) {
349+
if (nums.empty()) {
350+
return false;
359351
}
360-
start := 0
361-
end := len(nums) - 1
362-
for start+1 < end {
363-
// 处理重复数字
364-
for start < end && nums[start] == nums[start+1] {
365-
start++
352+
auto left = 0;
353+
auto right = nums.size() - 1;
354+
while (left + 1 < right) {
355+
while (left < right && nums[left] == nums[left + 1]) {
356+
++left;
366357
}
367-
for start < end && nums[end] == nums[end-1] {
368-
end--
358+
while (left < right && nums[right] == nums[right - 1]) {
359+
--right;
369360
}
370-
mid := start + (end-start)/2
371-
// 相等直接返回
372-
if nums[mid] == target {
373-
return true
361+
auto mid = left + (right - left) / 2;
362+
if (nums[mid] == target) {
363+
return true;
374364
}
375-
// 判断在那个区间，可能分为四种情况
376-
if nums[start] < nums[mid] {
377-
if nums[start] <= target && target <= nums[mid] {
378-
end = mid
365+
if (nums[left] < nums[mid]) {
366+
if (nums[left] <= target && target <= nums[mid]) {
367+
right = mid;
379368
} else {
380-
start = mid
369+
left = mid;
381370
}
382-
} else if nums[end] > nums[mid] {
383-
if nums[end] >= target && nums[mid] <= target {
384-
start = mid
371+
} else if (nums[mid] < nums[right]) {
372+
if (nums[mid] <= target && nums[right] >= target) {
373+
left = mid;
385374
} else {
386-
end = mid
375+
right = mid;
387376
}
388377
}
389378
}
390-
if nums[start] == target || nums[end] == target {
391-
return true
392-
}
393-
return false
379+
return nums[left] == target || nums[right] == target;
394380
}
395381
```
396382

0 commit comments

Comments
 (0)