Student
more
Okay, so I tried to take notes but it was so boring. I’d rather do questions. There’s this thing called study plan on leetcode which I’m prolly just gonna follow. I clicked on all three study plans: algorithms and dynamic programming (DP). And lemme just say I kinda struggled with the two already for data structures. I started at around 12:30 PM and now it’s 2:06 PM.
The first question is Contains Duplicate. If the array has a duplicate, you return true as in yes there is a duplicate in the array. If the array does not have a duplicate, you return false–there’s no duplicate in the array. I used sort and then binary search, which might not be the best answer, but it worked. I think other solutions were just to sort and go through the sorted array.
bool containsDuplicate(vector<int>& nums) {
// can sort then do binary search
std::sort(nums.begin(),nums.end());
for(int i = 0; i < nums.size(); i++ ){
if(std::binary_search(nums.begin()+i+1, nums.end(),nums[i])){
return true;
}
}
return false;
}
The next question I actually couldn’t solve. I looked up the solution
So given an array of integers can be + or -, find the subarray that will give you the largest sum. So like
array(−2, 1, −3, 4, −1, 2, 1, −5, 4)
The answer would be [4,-1,2,1] and you would return 6.
I struggled a lot on this question… but the key idea (at least to me) was to set sum = 0 when you get negative values, so you can keep traversing along the array.. I was trying to save the negative sum so that I can maybe return the negative sum in the end. But to solve that issue is really set the temporary sum to smallest integer possible.
int maxSubArray(vector<int>& nums) {
int sum = 0, smax = INT_MIN;
for (int num : nums) {
sum += num;
smax = max(smax, sum); // See here the the negative sum is still possible.
if (sum < 0) {
sum = 0;
}
}
return smax;
}
I think I should try this question again tomorrow tbh. Okay, that’s it. See you later.
Two Sum Attempt to recall: Question is “Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.” Intersection of Two Arrays {% highlight cpp %} vector intersect(vector& nums1, vector& nums2) { vector ans; vector::iterator it; for(int i = 0; i < nums1.size(); i++){ it = find(nums2.begin(),nums2.end(),nums1[i]); if( it != nums2.end() ){ ans.push_back(nums1[i]); *it = -1; } }...
read more
i def did not skip a day Question 1: First Bad Version Today I got to solve a problem called first bad version. What you essentially do is try to find which is the bad version given that a function tells you whether or not it is a bad version. All versions after a bad version become bad. For example FFTTTTTTT, The index at 2 or the 3rd item is...
read more