Home Week 2 | Grind 169 | Blind 75
Post
Cancel

Week 2 | Grind 169 | Blind 75

1. Ransom Note

Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.

Each letter in magazine can only be used once in ransomNote.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool canConstruct(string ransomNote, string magazine) {

    int hash[26] = {0};

    for(char ch:magazine)
        hash[ch-'a']++;

    for(char ch:ransomNote)
        if(hash[ch-'a'] <= 0)
            return false;
        hash[ch-'a']--;

    return true;    
}

2. Ransom Note

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

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

1
2
3
4
5
6
7
int climbStairs(int n, int rem = 0) {
    vector<int> dp(n+1);
    dp[0]=dp[1]=1;
    for(int i=2;i<=n;i++)   
        dp[i]=dp[i-1]+dp[i-2];
    return dp[n];
}

3. Longest Palindrome

Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters.

Letters are case sensitive, for example, Aa is not considered a palindrome here.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
    int longestPalindrome(string s) {
        int ans(0), n = s.size();
        bool inMiddle = false;
        if(n < 2) return 1;
        
        unordered_map<char, int> mp;
        
        for(char ch:s)
            mp[ch]++;
        
        for(auto e:mp){
            ans += e.second/2;
            
            if(!inMiddle and e.second % 2)
                inMiddle = true;
        }
        
        if(inMiddle)
            return (ans*2)+1;
        
        return ans*2;
    }

5. Reverse Linked List

Given the head of a singly linked list, reverse the list, and return the reversed list.

loading image

1
2
3
4
5
6
7
8
9
10
11
12
ListNode* reverseList(ListNode* head) {        
    ListNode *prev = NULL;

    while(head) {
        ListNode *next = head->next;
        head->next = prev;
        prev = head;
        head = next;
    }

    return prev;        
}

7. Add Binary

Given two binary strings a and b, return their sum as a binary string.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
string addBinary(string a, string b) {
        int i = a.length()-1;
        int j = b.length()-1;
        string ans;
        int carry = 0;
        
        while(i>=0 || j>=0){
            
            if(i>=0)
                carry += a[i--] - '0';
            
            if(j>=0)
                carry += b[j--] - '0';
            
            
            ans += (carry%2 + '0');
            carry = carry/2;
        }
        
        if(carry) ans += (carry%2 + '0');
    
        reverse(ans.begin(),ans.end());
        return ans;
    }

9. Depth of Binary Tree

Given the root of a binary tree, return its maximum depth.

A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

1
2
3
int maxDepth(TreeNode* root) {
    return root ? max(maxDepth(root->left), maxDepth(root->right))+1 : 0; 
}

8. Diameter of Binary Tree

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
    int height = 0;
    
    int dfs(TreeNode* root){        
        
        if(!root) return 0;
        
        int left = dfs(root->left);
        int right = dfs(root->right);
        
        if(left + right > height) 
            height = left + right;
        return max(left, right) + 1;     
    }
    
    int diameterOfBinaryTree(TreeNode* root) {        
        dfs(root);
        
        return height;
    }

9. Middle of the Linked List

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.

loading image

Two Pass

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
    ListNode* middleNode(ListNode* head) {
        ListNode* curr = head;
        int len = 0;
        while(curr != NULL)
        {
            len++;
            curr = curr->next;
        }
        
        len /=2;
        
        while(len--)
            head = head->next;
        return head;
    }

Single Pass

1
2
3
4
5
6
7
8
9
10
11
12
ListNode* middleNode(ListNode* head) {
        
        ListNode *slow = head, *fast = head;
        
        while(fast and fast->next){
            fast = fast->next->next;
            slow = slow->next;
        }
        
        return slow;
		
}

10. Depth of Binary Tree

Given the root of a binary tree, return its maximum depth.

A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

1
2
3
int maxDepth(TreeNode* root) {
    return root ? max(maxDepth(root->left), maxDepth(root->right))+1 : 0; 
}
This post is licensed under CC BY 4.0 by the author.

Week 1 | Grind 169 | Blind 75

June | 2022 | Leetcoding Challenge