leetcode 735 - Asteroid Collision

https://leetcode.com/problems/asteroid-collision/

We are given an array asteroids of integers representing asteroids in a row.

For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.

Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.

Example 1:

Input: asteroids = [5,10,-5]
Output: [5,10]
Explanation: The 10 and -5 collide resulting in 10. The 5 and 10 never collide.
Example 2:

Input: asteroids = [8,-8]
Output: []
Explanation: The 8 and -8 collide exploding each other.
Example 3:

Input: asteroids = [10,2,-5]
Output: [10]
Explanation: The 2 and -5 collide resulting in -5. The 10 and -5 collide resulting in 10.
Example 4:

Input: asteroids = [-2,-1,1,2]
Output: [-2,-1,1,2]
Explanation: The -2 and -1 are moving left, while the 1 and 2 are moving right. Asteroids moving the same direction never meet, so no asteroids will meet each other.

Constraints:

2 <= asteroids.length <= 104
-1000 <= asteroids[i] <= 1000
asteroids[i] != 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
26
27
28
29
30
31
32
class Solution {
public:
vector<int> asteroidCollision(vector<int>& asteroids) {
vector<int> result;

for (int a : asteroids) {
if (a > 0)
result.push_back(a);
else {
bool explode = false;

while (!result.empty() && result.back() > 0) {
if (-a > result.back())
result.pop_back();
else if (-a < result.back()) {
explode = true;
break;
} else {
result.pop_back();
explode = true;
break;
}
}

if (explode == false)
result.push_back(a);
}
}

return result;
}
};

leetcode 1610 - Maximum Number of Visible Points

https://leetcode.com/problems/maximum-number-of-visible-points/

You are given an array points, an integer angle, and your location, where location = [posx, posy] and points[i] = [xi, yi] both denote integral coordinates on the X-Y plane.

Initially, you are facing directly east from your position. You cannot move from your position, but you can rotate. In other words, posx and posy cannot be changed. Your field of view in degrees is represented by angle, determining how wide you can see from any given view direction. Let d be the amount in degrees that you rotate counterclockwise. Then, your field of view is the inclusive range of angles [d - angle/2, d + angle/2].

You can see some set of points if, for each point, the angle formed by the point, your position, and the immediate east direction from your position is in your field of view.

There can be multiple points at one coordinate. There may be points at your location, and you can always see these points regardless of your rotation. Points do not obstruct your vision to other points.

Return the maximum number of points you can see.

Example 1:

Input: points = [[2,1],[2,2],[3,3]], angle = 90, location = [1,1]
Output: 3
Explanation: The shaded region represents your field of view. All points can be made visible in your field of view, including [3,3] even though [2,2] is in front and in the same line of sight.
Example 2:

Input: points = [[2,1],[2,2],[3,4],[1,1]], angle = 90, location = [1,1]
Output: 4
Explanation: All points can be made visible in your field of view, including the one at your location.
Example 3:

Input: points = [[1,0],[2,1]], angle = 13, location = [1,1]
Output: 1
Explanation: You can only see one of the two points, as shown above.

Constraints:

1 <= points.length <= 105
points[i].length == 2
location.length == 2
0 <= angle < 360
0 <= posx, posy, xi, yi <= 100

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
class Solution {
public:
int visiblePoints(vector<vector<int>>& points, int angle, vector<int>& location) {
vector<double> radians;

int same = 0;

for (auto &point : points) {
if (point == location)
same++;
else
radians.push_back(atan2(point[1] - location[1], point[0] - location[0]));
}

int n = radians.size();
for (int i = 0; i < n; i++)
radians.push_back(radians[i] + 2 * M_PI);

sort(radians.begin(), radians.end());

double max_radians = angle * M_PI / 180;
int ans = 0;

for (int i = 0, j = 0; j < 2 * n; j++) {
while (radians[j] - radians[i] > max_radians)
i++;

ans = max(ans, j - i + 1);
}

return ans + same;
}
};

leetcode 1509 - Minimum Difference Between Largest and Smallest Value in Three Moves

https://leetcode.com/problems/minimum-difference-between-largest-and-smallest-value-in-three-moves/

Given an array nums, you are allowed to choose one element of nums and change it by any value in one move.

Return the minimum difference between the largest and smallest value of nums after perfoming at most 3 moves.

Example 1:

Input: nums = [5,3,2,4]
Output: 0
Explanation: Change the array [5,3,2,4] to [2,2,2,2].
The difference between the maximum and minimum is 2-2 = 0.
Example 2:

Input: nums = [1,5,0,10,14]
Output: 1
Explanation: Change the array [1,5,0,10,14] to [1,1,0,1,1].
The difference between the maximum and minimum is 1-0 = 1.
Example 3:

Input: nums = [6,6,0,1,1,4,6]
Output: 2
Example 4:

Input: nums = [1,5,6,14,15]
Output: 1

Constraints:

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//O(NlogN)
class Solution {
public:
int minDifference(vector<int>& nums) {
if (nums.size() <= 3) return 0;

sort(nums.begin(), nums.end());
int n = nums.size();

//remove 3 smallest
int diff1 = nums[n-1] - nums[3];

//remove 3 largest
int diff2 = nums[n-4] - nums[0];

//remove 1 smallest, 2 largest
int diff3 = nums[n-3] - nums[1];

//remove 2 smallest, 1 largest
int diff4 = nums[n-2] - nums[2];

return min(min(min(diff1, diff2), diff3), diff4);
}
};

leetcode 843 - Guess the Word

https://leetcode.com/problems/guess-the-word/
https://leetcode.com/problems/guess-the-word/discuss/1394280/Java-Minimax-Solution-Explained-in-depth!

This is an interactive problem.

You are given an array of unique strings wordlist where wordlist[i] is 6 letters long, and one word in this list is chosen as secret.

You may call Master.guess(word) to guess a word. The guessed word should have type string and must be from the original list with 6 lowercase letters.

This function returns an integer type, representing the number of exact matches (value and position) of your guess to the secret word. Also, if your guess is not in the given wordlist, it will return -1 instead.

For each test case, you have exactly 10 guesses to guess the word. At the end of any number of calls, if you have made 10 or fewer calls to Master.guess and at least one of these guesses was secret, then you pass the test case.

Example 1:

Input: secret = “acckzz”, wordlist = [“acckzz”,”ccbazz”,”eiowzz”,”abcczz”], numguesses = 10
Output: You guessed the secret word correctly.
Explanation:
master.guess(“aaaaaa”) returns -1, because “aaaaaa” is not in wordlist.
master.guess(“acckzz”) returns 6, because “acckzz” is secret and has all 6 matches.
master.guess(“ccbazz”) returns 3, because “ccbazz” has 3 matches.
master.guess(“eiowzz”) returns 2, because “eiowzz” has 2 matches.
master.guess(“abcczz”) returns 4, because “abcczz” has 4 matches.
We made 5 calls to master.guess and one of them was the secret, so we pass the test case.
Example 2:

Input: secret = “hamada”, wordlist = [“hamada”,”khaled”], numguesses = 10
Output: You guessed the secret word correctly.

Constraints:

1 <= wordlist.length <= 100
wordlist[i].length == 6
wordlist[i] consist of lowercase English letters.
All the strings of wordlist are unique.
secret exists in wordlist.
numguesses == 10

leetcode 1277 - Count Square Submatrices with All Ones

https://leetcode.com/problems/count-square-submatrices-with-all-ones/

Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.

Example 1:

Input: matrix =
[
[0,1,1,1],
[1,1,1,1],
[0,1,1,1]
]
Output: 15
Explanation:
There are 10 squares of side 1.
There are 4 squares of side 2.
There is 1 square of side 3.
Total number of squares = 10 + 4 + 1 = 15.
Example 2:

Input: matrix =
[
[1,0,1],
[1,1,0],
[1,1,0]
]
Output: 7
Explanation:
There are 6 squares of side 1.
There is 1 square of side 2.
Total number of squares = 6 + 1 = 7.

Constraints:

1 <= arr.length <= 300
1 <= arr[0].length <= 300
0 <= arr[i][j] <= 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
//not optimized
class Solution {
public:
int countSquares(vector<vector<int>>& matrix) {
int rows = matrix.size();
int cols = matrix[0].size();

sum.resize(rows+1, vector<int>(cols+1, 0));

for (int r = 1; r <= rows; r++) {
for (int c = 1; c <= cols; c++) {
sum[r][c] = sum[r-1][c] + sum[r][c-1] - sum[r-1][c-1] + matrix[r-1][c-1];
}
}

int ans = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (matrix[r][c] != 1) continue;

int x = r, y = c;
while (x < rows && y < cols) {
int ones = get_sum(r, c, x, y);
if (ones == (x-r+1)*(x-r+1)) {
ans++;
x++;
y++;
} else {
break;
}
}
}
}

return ans;
}

int get_sum(int r1, int c1, int r2, int c2) {
return sum[r2+1][c2+1] - sum[r1][c2+1] - sum[r2+1][c1] + sum[r1][c1];
}

private:
vector<vector<int>> sum;
};

//O(rows * cols)
class Solution {
public:
int countSquares(vector<vector<int>>& matrix) {
int rows = matrix.size();
int cols = matrix[0].size();

int ans = 0;

for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (matrix[r][c] != 1) continue;

if (r > 0 && c > 0)
matrix[r][c] = min({matrix[r-1][c], matrix[r][c-1], matrix[r-1][c-1]}) + 1;

ans += matrix[r][c];
}
}

return ans;
}
};

leetcode 729 - My Calendar I

https://leetcode.com/problems/my-calendar-i/

Implement a MyCalendar class to store your events. A new event can be added if adding the event will not cause a double booking.

Your class will have the method, book(int start, int end). Formally, this represents a booking on the half open interval [start, end), the range of real numbers x such that start <= x < end.

A double booking happens when two events have some non-empty intersection (ie., there is some time that is common to both events.)

For each call to the method MyCalendar.book, return true if the event can be added to the calendar successfully without causing a double booking. Otherwise, return false and do not add the event to the calendar.

Your class will be called like this: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)
Example 1:

MyCalendar();
MyCalendar.book(10, 20); // returns true
MyCalendar.book(15, 25); // returns false
MyCalendar.book(20, 30); // returns true
Explanation:
The first event can be booked. The second can’t because time 15 is already booked by another event.
The third event can be booked, as the first event takes every time less than 20, but not including 20.

Note:

The number of calls to MyCalendar.book per test case will be at most 1000.
In calls to MyCalendar.book(start, end), start and end are integers in the range [0, 10^9].

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
class MyCalendar {
public:
MyCalendar() {

}

bool book(int start, int end) {
IT left = events.lower_bound(start);
IT right = events.lower_bound(end);

if (left != events.begin()) {
if (prev(left)->second > start)
left = prev(left);
}

if (left != right) return false;

events[start] = end;
return true;
}

private:
typedef map<int,int>::iterator IT;

map<int,int> events;
};

/**
* Your MyCalendar object will be instantiated and called as such:
* MyCalendar* obj = new MyCalendar();
* bool param_1 = obj->book(start,end);
*/

leetcode 715 - Range Module

https://leetcode.com/problems/range-module/

A Range Module is a module that tracks ranges of numbers. Your task is to design and implement the following interfaces in an efficient manner.

addRange(int left, int right) Adds the half-open interval [left, right), tracking every real number in that interval. Adding an interval that partially overlaps with currently tracked numbers should add any numbers in the interval [left, right) that are not already tracked.
queryRange(int left, int right) Returns true if and only if every real number in the interval [left, right) is currently being tracked.
removeRange(int left, int right) Stops tracking every real number currently being tracked in the interval [left, right).
Example 1:
addRange(10, 20): null
removeRange(14, 16): null
queryRange(10, 14): true (Every number in [10, 14) is being tracked)
queryRange(13, 15): false (Numbers like 14, 14.03, 14.17 in [13, 15) are not being tracked)
queryRange(16, 17): true (The number 16 in [16, 17) is still being tracked, despite the remove operation)
Note:

A half open interval [left, right) denotes all real numbers left <= x < right.
0 < left < right < 10^9 in all calls to addRange, queryRange, removeRange.
The total number of calls to addRange in a single test case is at most 1000.
The total number of calls to queryRange in a single test case is at most 5000.
The total number of calls to removeRange in a single test case is at most 1000.

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
class RangeModule {
public:
RangeModule() {

}

//O(N)
void addRange(int left, int right) {
bool added = false;
vector<pair<int,int>> new_ranges;

int n = ranges.size();
int i = 0;

while (i < n || !added) {
pair<int,int> next;

if (i == n || (!added && left < ranges[i].first)) {
next = {left, right};
added = true;
} else {
next = ranges[i];
i++;
}

if (new_ranges.empty() || new_ranges.back().second < next.first)
new_ranges.push_back(next);
else
new_ranges.back().second = max(new_ranges.back().second, next.second);
}

ranges.swap(new_ranges);
}

//O(logN)
bool queryRange(int left, int right) {
int lo = 0, hi = ranges.size() - 1;

while (lo <= hi) {
int mid = lo + (hi - lo) / 2;

if (ranges[mid].first <= left)
lo = mid + 1;
else
hi = mid - 1;
}

if (lo == 0) return false;

int idx = lo - 1;
return ranges[idx].first <= left && ranges[idx].second >= right;
}

//O(N)
void removeRange(int left, int right) {
vector<pair<int,int>> new_ranges;

for (auto &range : ranges) {
if (range.first >= right || range.second <= left) {
new_ranges.push_back(range);
continue;
}

pair<int,int> left_range = {range.first, left};
if (left_range.first < left_range.second)
new_ranges.push_back(left_range);

pair<int,int> right_range = {right, range.second};
if (right_range.first < right_range.second)
new_ranges.push_back(right_range);
}

ranges.swap(new_ranges);
}

private:
vector<pair<int,int>> ranges;
};

/**
* Your RangeModule object will be instantiated and called as such:
* RangeModule* obj = new RangeModule();
* obj->addRange(left,right);
* bool param_2 = obj->queryRange(left,right);
* obj->removeRange(left,right);
*/

class RangeModule {
public:
RangeModule() {

}

//O(MlogN) m是erase的区间
void addRange(int left, int right) {
IT l, r;
get_overlap(left, right, l, r);

if (l != r) {
left = min(l->first, left);
right = max(prev(r)->second, right);
ranges.erase(l, r);
}

ranges[left] = right;
}

//O(logN)
bool queryRange(int left, int right) {
IT l, r;
get_overlap(left, right, l, r);

if (l == r)
return false;

return l->first <= left && l->second >= right;
}

//O(MlogN) m是erase的区间
void removeRange(int left, int right) {
IT l, r;
get_overlap(left, right, l, r);

if (l == r) return;

int start = min(left, l->first);
int end = max(right, prev(r)->second);
ranges.erase(l, r);

if (start < left)
ranges[start] = left;
if (end > right)
ranges[right] = end;
}

private:
map<int, int> ranges; //left ==> right

typedef map<int, int>::iterator IT;

void get_overlap(int left, int right, IT &l, IT &r) {
//return [l, r)
l = ranges.upper_bound(left);
r = ranges.upper_bound(right);

if (l != ranges.begin()) {
if (prev(l)->second >= left)
l--;
}
}
};

leetcode 1776 - Car Fleet II

https://leetcode.com/problems/car-fleet-ii/

There are n cars traveling at different speeds in the same direction along a one-lane road. You are given an array cars of length n, where cars[i] = [positioni, speedi] represents:

positioni is the distance between the ith car and the beginning of the road in meters. It is guaranteed that positioni < positioni+1.
speedi is the initial speed of the ith car in meters per second.
For simplicity, cars can be considered as points moving along the number line. Two cars collide when they occupy the same position. Once a car collides with another car, they unite and form a single car fleet. The cars in the formed fleet will have the same position and the same speed, which is the initial speed of the slowest car in the fleet.

Return an array answer, where answer[i] is the time, in seconds, at which the ith car collides with the next car, or -1 if the car does not collide with the next car. Answers within 10-5 of the actual answers are accepted.

Example 1:

Input: cars = [[1,2],[2,1],[4,3],[7,2]]
Output: [1.00000,-1.00000,3.00000,-1.00000]
Explanation: After exactly one second, the first car will collide with the second car, and form a car fleet with speed 1 m/s. After exactly 3 seconds, the third car will collide with the fourth car, and form a car fleet with speed 2 m/s.
Example 2:

Input: cars = [[3,4],[5,4],[6,3],[9,1]]
Output: [2.00000,1.00000,1.50000,-1.00000]

Constraints:

1 <= cars.length <= 10^5
1 <= positioni, speedi <= 10^6
positioni < positioni+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
class Solution {
public:
vector<double> getCollisionTimes(vector<vector<int>>& cars) {
int n = cars.size();
stack<int> stk;

vector<double> result(n, -1);

auto collision_time = [&](int a, int b) {
return (double)(cars[b][0] - cars[a][0]) / (cars[a][1] - cars[b][1]);
};

for (int i = n - 1; i >= 0; i--) {
/*不会与i相撞的stk top都可以remove,两种情况
1. stk top速度大于等于i
2. stk top速度小于i,但在i撞到stk top前,stk top已经与它前面的车相撞了
*/
while (!stk.empty()) {
int speed_a = cars[i][1];
int speed_b = cars[stk.top()][1];
if (speed_a <= speed_b || (result[stk.top()] != -1 &&
collision_time(i, stk.top()) > result[stk.top()]))
stk.pop();
else
break;
}

//当前i与stk top相撞
if (!stk.empty())
result[i] = collision_time(i, stk.top());

stk.push(i);
}

return result;
}
};

leetcode 865 - Smallest Subtree with all the Deepest Nodes

Given the root of a binary tree, the depth of each node is the shortest distance to the root.

Return the smallest subtree such that it contains all the deepest nodes in the original tree.

A node is called the deepest if it has the largest depth possible among any node in the entire tree.

The subtree of a node is tree consisting of that node, plus the set of all descendants of that node.

Note: This question is the same as 1123: https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4]
Output: [2,7,4]
Explanation: We return the node with value 2, colored in yellow in the diagram.
The nodes coloured in blue are the deepest nodes of the tree.
Notice that nodes 5, 3 and 2 contain the deepest nodes in the tree but node 2 is the smallest subtree among them, so we return it.
Example 2:

Input: root = [1]
Output: [1]
Explanation: The root is the deepest node in the tree.
Example 3:

Input: root = [0,1,3,null,2]
Output: [2]
Explanation: The deepest node in the tree is 2, the valid subtrees are the subtrees of nodes 2, 1 and 0 but the subtree of node 2 is the smallest.

Constraints:

The number of nodes in the tree will be in the range [1, 500].
0 <= Node.val <= 500
The values of the nodes in the tree are unique.

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
/**
* 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:
pair<TreeNode *, int> helper(TreeNode *root) {
if (!root) return {NULL, 0};

auto left = helper(root->left);
auto right = helper(root->right);

if (left.second == right.second)
return {root, left.second+1};
else if (left.second > right.second)
return {left.first, left.second+1};
else
return {right.first, right.second+1};
}

TreeNode* subtreeWithAllDeepest(TreeNode* root) {
auto p = helper(root);

return p.first;
}
};

leetcode 81 - Search in Rotated Sorted Array II

https://leetcode.com/problems/search-in-rotated-sorted-array-ii/

There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).

Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]] (0-indexed). For example, [0,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].

Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.

Example 1:

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true
Example 2:

Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false

Constraints:

1 <= nums.length <= 5000
-104 <= nums[i] <= 10^4
nums is guaranteed to be rotated at some pivot.
-104 <= target <= 104

Follow up: This problem is the same as Search in Rotated Sorted Array, where nums may contain duplicates. Would this affect the runtime complexity? How and why?

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
class Solution {
public:
bool search(vector<int> &nums, int lo, int hi, int target) {
if (lo > hi) return false;

int mid = lo + (hi - lo) / 2;

if (nums[mid] == target)
return true;

bool left_sorted = false;
bool right_sorted = false;

if (mid - 1 >= 0 && nums[lo] < nums[mid-1])
left_sorted = true;
if (mid + 1 < nums.size() && nums[mid+1] < nums[hi])
right_sorted = true;

if (left_sorted) {
if (target >= nums[lo] && target <= nums[mid-1])
return search(nums, lo, mid-1, target);
else
return search(nums, mid+1, hi, target);
} else if (right_sorted) {
if (target >= nums[mid+1] && target <= nums[hi])
return search(nums, mid+1, hi, target);
else
return search(nums, lo, mid-1, target);
} else
return search(nums, lo, mid-1, target) || search(nums, mid+1, hi, target);
}

bool search(vector<int>& nums, int target) {
return search(nums, 0, nums.size()-1, target);
}
};

//简洁写法
class Solution {
public:
bool search(vector<int>& nums, int target) {
int i = 0, j = nums.size() - 1;

while (i <= j) {
int m = i + (j-i)/2;

if (nums[m] == target) return true;

//和第33题唯一的区别
if (nums[i] == nums[m] && nums[m] == nums[j]) {
i++;
j--;
continue;
}

bool left_sorted = nums[i] <= nums[m]; //false
if ((left_sorted && target >= nums[i] && target < nums[m]) ||
/* 1 3 */
(!left_sorted && (target < nums[m] || target > nums[j]))) {

j = m - 1;
} else {
i = m + 1;
}
}

return false;
}
};