LeetCode 45 Jump Game II (C++, Python)

-
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
For example:
Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

Solution C++


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int jump(vector<int>& nums) {
        int i = 0;
        int steps = 0;
        while (i < nums.size() - 1) {
            steps ++;
            int tmp = 0;
            int reach = nums[i] + i;
            for (int j = i + 1; j <= reach; ++j) {
                if (j >= nums.size() - 1) {
                    tmp = j;
                    i = j;
                    break;
                }
                if (j + nums[j] > tmp) {
                    tmp = j + nums[j];
                    i = j;
                }
            }
            if (tmp == 0) {
                steps = numeric_limits<int>::max();
                break;
            }
        }
        return steps;
    }
};
Solution Python


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    # @param {integer[]} nums
    # @return {integer}
    def jump(self, nums):
        i = 0
        steps = 0
        while i < len(nums) - 1:
            steps += 1
            tmp = 0
            reach = i + nums[i]
            for j in range(i + 1, reach + 1):
                if j >= len(nums) - 1:
                    tmp = j
                    i = j
                    break
                if j + nums[j] > tmp:
                    tmp = j + nums[j]
                    i = j
            if tmp == 0:
                steps = None
                break
        return steps;

Popular posts from this blog

How Django Works (4) URL Resolution

-
Image
Why We Need URL Resolution Theoretically, we could write a single function to process all incoming HTTP requests. It would work well for very simple websites. For any real websites, it would be much more appropriate to categorize HTTP requests based on their URLs and process them separately in different handlers. For example, BASEURL/polls/ would be an application for polls whereas BASEURL/blogs/ would be an application for blogs. This way, different URLs can be considered different logic applications, so we can think of websites in terms of logic applications – a higher level of abstraction that HTTP request/response pairs. Fortunately, many modern web frameworks come default with mechanisms that do the categorization of HTTP requests based on URIs, which spares us the effort of having to reinvent the wheel.   Django's URL Resolution The official Django document has following description about how Django processes a request. https://docs.djangoproject.com/en/1.8/topic...
Read more

Python Class Method and Class Only Method

-
In this post, I will be discussing Python method especially class method. Example class Foo : def bar_inst ( self ): print ( self , "This is bar_inst" ) @staticmethod def bar_static (): print ( "This is bar_static" ) @classmethod def bar_class (cls): print (cls, "This is bar_class" ) >>> foo = Foo() >>> foo.bar_inst <bound method Foo.bar_inst of <test.Foo object at 0x025A0EB0>> >>> foo.bar_static <function Foo.bar_static at 0x025A34F8> >>> foo.bar_class <bound method type.bar_class of <class 'test.Foo'>> foo.bar_static just returns a function object as if bar_static were defined outside of class. (In Python 2, it would return an unbound method; Python 3 has removed the concept of unbound methods. So a function is either a bound method or a regular function object) How It Works -- Descriptor  Every ...
Read more

How Django Works (2) Built-in Server, Autoreload

-
Image
Django's built-in server Django comes with a built-in server for development and testing purpose. The command to start the built-in server is python manage . py runserver    Autoreload One notable feature of the built-in server is its ability to automatically reload once a file is changed. Accord to Official document, "The development server automatically reloads Python code for each request, as needed. You don’t need to restart the server for code changes to take effect. However, some actions like adding files don’t trigger a restart, so you’ll have to restart the server in these cases." The feature can be shut off by --noreload. This blog will examine in implementation detail how autoreload is implemented and how autoreload is used by Django built-in server. The file that implements autoreload is site-packages/django/utils/autoreload.py if django is installed. Or you can find it at https://github.com/django/django/blob/master/django/utils/autoreload.py ...
Read more