Judge Route Circle
Initially, there is a Robot at position (0, 0). Given a sequence of its moves, judge if this robot makes a circle, which means it moves back to the original place.
The move sequence is represented by a string. And each move is represent by a character. The valid robot moves are R (Right), L (Left), U (Up) and D (down). The output should be true or false representing whether the robot makes a circle.
Example 1:
Input: "UD"
Output: true
Example 2:
Input: "LL"
Output: false
R (Right), L (Left), U (Up) and D (down). The output should be true or false representing whether the robot makes a circle.
class Solution {
public:
bool judgeCircle(string moves) {
int size = moves.size();
int l = 0, r = 0, u = 0, d = 0;
for (int i = 0; i < size; i++) {
if (moves[i] == 'U') {
u++;
} else if (moves[i] == 'D') {
d++;
} else if (moves[i] == 'L') {
l++;
} else {
r++;
}
}
if (u == d && l == r) {
return true;
}
return false;
}
};
Find K Closest Elements
Given a sorted array, two integers
k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.
Example 1:
Input: [1,2,3,4,5], k=4, x=3 Output: [1,2,3,4]
Example 2:
Input: [1,2,3,4,5], k=4, x=-1 Output: [1,2,3,4]
Note:
- The value k is positive and will always be smaller than the length of the sorted array.
- Length of the given array is positive and will not exceed 104
- Absolute value of elements in the array and x will not exceed 104
class Solution {
public:
int binary_search(vector<int>&arr, int x) {
int index, size = arr.size();
int st = 0, end = size - 1;
while (st <= end) {
index = st + (end - st)/2;
if (arr[index] == x || index == 0 || index == end) {
return index;
} else if (arr[index] < x) {
st = index + 1;
} else {
end = index - 1;
}
}
return index;
}
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
vector<int> ans;
if (arr.size() == 0) {
return ans;
}
int index_in_arr = binary_search(arr, x);
int iter_left = index_in_arr, iter_right = index_in_arr;
if (x == arr[index_in_arr]) {
ans.push_back(x);
iter_left--;
iter_right++;
k--;
} else {
iter_right++;
}
while (iter_left >= 0 && iter_right <= arr.size() - 1 &&
k > 0) {
if (abs(x - arr[iter_left]) <= abs(arr[iter_right] - x)) {
ans.push_back(arr[iter_left--]);
} else {
ans.push_back(arr[iter_right++]);
}
k--;
}
while (k > 0) {
if (iter_left >= 0) {
ans.push_back(arr[iter_left--]);
}
if (iter_right <= arr.size() - 1) {
ans.push_back(arr[iter_right++]);
}
k--;
}
sort(ans.begin(), ans.end());
return ans;
}
};
No comments:
Post a Comment