Leetcode 55 solution

55. Jump Game

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example 1:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

Constraints:

1 <= nums.length <= 104
0 <= nums[i] <= 105

solution:

class Solution {
 bool solve(vector<int>&nums , int index , vector<int>&dp)
 {     
     if(dp[index] != -1)
     {
         return dp[index];
     }
     if(index == nums.size()-1)
     {
         return true;
     }
     if(nums[index] == 0)
     {
         return false;
     }
     bool x = false;
     if(index +nums[index] >= nums.size()-1)
         {
              return dp[index] = true;
         }
     for(int j = index+nums[index] ; j >= index+1 ; j--)
     {   
         
         if(j <= nums.size()-1)
         x = x | solve(nums , j, dp);
         if(x == true)
          break;
     }
     return dp[index] =  x;
 }
public:
    bool canJump(vector<int>& nums) {
         
         int i =0;
         vector<int>dp(nums.size() , -1);
         return solve(nums , i , dp );
    }
};

Comments

leetcode 48 solution

48 . Rotate Image You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise). You have to rotate the image in-place , which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation. Example 1: Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [[7,4,1],[8,5,2],[9,6,3]] Example 2: Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]] Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]] Constraints: n == matrix.length == matrix[i].length 1 <= n <= 20 -1000 <= matrix[i][j] <= 1000 solution: class Solution { public: void swap(int& a , int &b) { int c ; c = a; a = b; b = c; } void transpose (vector<vector<int>...

2485. Find the Pivot Integer | Binary search

Given a positive integer n , find the pivot integer x such that: The sum of all elements between 1 and x inclusively equals the sum of all elements between x and n inclusively. Return the pivot integer x . If no such integer exists, return -1 . It is guaranteed that there will be at most one pivot index for the given input. Example 1: Input: n = 8 Output: 6 Explanation: 6 is the pivot integer since: 1 + 2 + 3 + 4 + 5 + 6 = 6 + 7 + 8 = 21. Example 2: Input: n = 1 Output: 1 Explanation: 1 is the pivot integer since: 1 = 1. Example 3: Input: n = 4 Output: -1 Explanation: It can be proved that no such integer exist. Constraints: 1 <= n <= 1000 Solution : class Solution { publ ic: int pivotInteger( int n ) { int sum = (( n )*( n + 1 ))/ 2 ; int i = 1 ; int j =...

Regular Expression Matching Leetcode Solution

Regular Expression Matching Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where: '.' Matches any single character. '*' Matches zero or more of the preceding element. The matching should cover the entire input string (not partial). Example 1: Input: s = "aa", p = "a" Output: false Explanation: "a" does not match the entire string "aa". Example 2: Input: s = "aa", p = "a*" Output: true Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa". Example 3: Input: s = "ab", p = ".*" Output: true Explanation: ".*" means "zero or more (*) of any character (.)". Constraints: 1 <= s.length <= 20 1 <= p.length <= 20 s contains only lowercase English letters. p contains only lowercase Englis...

MY CODE VILLAGE

Search This Blog