Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.
You must write an algorithm with O(log n) runtime complexity.
class Solution {
public:
int search(vector<int>& nums, int target) {
int len(nums.size());
int l(0), r(len-1);
while(l<=r){
int mid = l + (r - l)/2;
if(nums[mid] == target)
return mid;
if(nums[mid] > target)
r = mid -1;
else
l = mid + 1;
}
return -1;
}
};
You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.
Suppose you have n versions [1, 2, …, n] and you want to find out the first bad one, which causes all the following ones to be bad.
You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.
class Solution {
public:
int firstBadVersion(int n) {
int l = 1, h = n, mid;
while (l < h) {
mid = l + (h - l) / 2;
if (isBadVersion(mid)) h = mid;
else l = mid+1;
}
return l;
}
};
Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.
class Solution {
public:
vector<int> sortedSquares(vector<int>& A) {
int l = 0, r = A.size() - 1;
vector<int> ans(r+1);
for (int k = A.size() - 1; k >= 0; k--)
if (abs(A[r]) > abs(A[l])) ans[k] = A[r] * A[r--];
else ans[k] = A[l] * A[l++];
return ans;
}
};
Given an array, rotate the array to the right by k steps, where k is non-negative.
class Solution {
public:
void rotate(vector<int>& nums, int k) {
vector<int> ans;
int len(nums.size());
if(len == 1 || k == 0) return;
if(k>len) k = k%len;
int start = len-k;
for(int i = start; i<len; i++)
ans.push_back(nums[i]);
for(int i = 0; i<start; i++)
ans.push_back(nums[i]);
nums = ans;
}
};
class Solution {
public:
void rotate(vector<int>& nums, int k) {
k %=nums.size();
reverse(nums.begin(), nums.end());
reverse(nums.begin(), nums.begin()+k);
reverse(nums.begin()+k, nums.end());
}
};
Given an integer array nums, move all 0’s to the end of it while maintaining the relative order of the non-zero elements.
Note : that you must do this in-place without making a copy of the array.
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int curr=0, end=0, n(nums.size());
while(curr < n)
if(nums[curr] == 0) curr++;
else nums[end++] = nums[curr++];
while(end <n)
nums[end++] = 0;
}
};
Write a function that reverses a string. The input string is given as an array of characters s.
You must do this by modifying the input array in-place with O(1) extra memory.
class Solution {
public:
void reverseString(vector<char>& s) {
int n(s.size());
for(int i=0; i<n/2; i++)
swap(s[i], s[n-i-1]);
}
};
Given a string s, reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.
class Solution {
public:
string reverseWords(string s) {
int i = 0;
for (int j = 0; j < s.size(); ++j) {
if (s[j] == ' ') {
reverse(s.begin() + i, s.begin() + j);
i = j + 1;
}
}
reverse(s.begin() + i, s.end());
return s;
}
};
Given the head of a singly linked list, return the middle node of the linked list.
If there are two middle nodes, return the second middle node.
class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while(fast && fast->next){
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
};