276. (Locked)Paint Fence

Difficulty: Easy

Frequency: N/A

There is a fence with n posts, each post can be painted with one of the k colors.

You have to paint all the posts such that no more than two adjacent fence posts have the same color.

Return the total number of ways you can paint the fence.

Note: n and k are non-negative integers.


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:

class Solution {
public:
int numWays(int n, int k) {
if (n == 0) return 0;
if (n == 1) return k;
if (n == 2) return k * k;
int a = k, b = k * k, result;
for (int i = 3; i <= n; i++) {
result = (a + b) * (k – 1);
a = b;
b = result;
}
return result;
}
};


Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:
Advertisements

198. House Robber

Difficulty: Easy

Frequency: N/A

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that 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.


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size() <= 0) return 0;
        if (nums.size() == 1) return nums[0];
        if (nums.size() == 2) return max(nums[0], nums[1]);
        int m0 = nums[0], m1 = max(nums[0], nums[1]), m2 = max(nums[0] + nums[2], nums[1]);
        for (int i = 3; i < nums.size(); i++) {
            int m3 = max(m0, m1) + nums[i];
            m0 = m1;
            m1 = m2;
            m2 = m3;
        }
        return max(m1, m2);
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

070. Climbing Stairs

Difficulty: Easy

Frequency: N/A

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    int climbStairs(int n) {
        if (n <= 0) return 0;
        int p1 = 1, p2 = 1;
        for (int i = 2; i <= n; i++) {
            int cur = p1 + p2;
            p1 = p2;
            p2 = cur;
        }
        return p2;
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

135. Candy

Difficulty: Hard

Frequency: N/A

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

  • Each child must have at least one candy.
  • Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?


 

My solution:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        int result = 0;
        vector<int> candies(n, 1);
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1] && candies[i] <= candies[i - 1])
                candies[i] = candies[i - 1] + 1;
        }
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) 
                candies[i] = candies[i + 1] + 1;
        }
        for (int n : candies) result += n;
        return result;
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

316. Remove Duplicate Letters

Difficulty: Medium

Frequency: N/A

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example:

Given "bcabc"
Return "abc"

Given "cbacdcbc"
Return "acdb"


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    string removeDuplicateLetters(string s) {
        string result;
        int cnt[26] = {0};
        bool exists[26] = {false};
        for (char c : s) cnt[c - 'a']++;
        for (char c : s) {
            cnt[c - 'a']--;
            if (!exists[c - 'a']) {
                while (!result.empty() && c < result.back() && cnt[result.back() - 'a']) {
                    exists[result.back() - 'a'] = false;
                    result.pop_back();
                }
            }
            if (result.empty() || !exists[c - 'a']) {
                result += c;
                exists[c - 'a'] = true;
            }
        }
        return result;
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn: