loading...

Daily Coding Challenge #111

wingkwong profile image Wing-Kam ・2 min read

About

This is a series of Daily Coding Challenge. Each day I show a few solutions written in C++. The questions are from coding practice/contest sites such as HackerRank, LeetCode, Codeforces, Atcoder and etc.


/*
Contains Duplicate III

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.

Example 1:

Input: nums = [1,2,3,1], k = 3, t = 0
Output: true
Example 2:

Input: nums = [1,0,1,1], k = 1, t = 2
Output: true
Example 3:

Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false
*/

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        set<long> s;
        int n = (int) nums.size();
        for(int i=0;i<n;i++){
            auto it=s.lower_bound((long)nums[i]-t);
            if(it!=s.end()&&*it<=(long)nums[i]+t) return true;
            s.insert(nums[i]);
            if(i>=k) s.erase(nums[i-k]);
        }
        return false;
    }
};

/*
House Robber II

ou are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2),
             because they are adjacent houses.
Example 2:

Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
             Total amount you can rob = 1 + 3 = 4.
*/

class Solution {
public:
    int rob(vector<int>& nums, int left, int right) {
        int cur=0, prev=0;
        for(int i=left;i<=right;i++){
            int tmp = max(prev+nums[i], cur);
            prev=cur;
            cur=tmp;
        }
        return cur;
    }
    int rob(vector<int>& nums) {
        // As we cannot sum the first element and the last element, this comes with two cases.

        // Sum from index 0 to n-2
        // Sum from index 1 to n-1
        // where n is the size of nums.

        // The answer is the max of them. Use prev and cur to optimise space.
        int n = nums.size();
        if(n<2) return n?nums[0]:0;
        return max(rob(nums,0,n-2), rob(nums,1,n-1));
    }
};

There are other programming solutions in the following repositories below. Star and watch for timely updates!

GitHub logo wingkwong / competitive-programming

🌟 My CP Journey - This repository contains CP solutions (mostly written in C++) from different OJs and contest sites 🌟

Posted on by:

wingkwong profile

Wing-Kam

@wingkwong

Consultant by day. Developer by night. AWS certified. Exploring #CloudNative currently.

Discussion

pic
Editor guide