Difference between overriding and overloading in Java

Method Overloading

deals with the notion of having two or more methods in the same class with the same name but different arguments.

1	static int binarySearch(byte[] a, byte key);

2	static int binarySearch(byte[] a, int fromIndex, int toIndex, byte key)

Method Overriding

means having two methods with the same arguments, but different implementations. One of them would exist in the parent class, while another will be in the derived, or child class. 

01	class Animal{

02	protected int legs = 1;

03	public int getLegs(){

04	return legs*4;

05

}

06

}

07	class Bird extends Animal{

08	public int getLegs(){

09	return legs*2;

10

}

11

}

Also the dynamic binding and static binding issues are related to this topic

Look at the examples below

We overload the eat method

public class Animal{}


public class Dog extends Animal{}

public class AnimalActivity{

    public void eat(Animal a){
       System.out.println("Animal is eating");
    }

    public void eat(Dog d){
       System.out.println("Dog is eating");
    }
}

then in the main class:

public static void main(String args[])
{
    Animal a=new Animal();
    Animal d=new Dog();
    AnimalActivity aa=new AnimalActivity();
    aa.eat(a);
    aa.eat(d);
}

the result in both two cases will be: Animal is eating

Then we try to override the eat mehod of Animal class

public class Animal{
    public void eat(){
System.out.println("Animal is eating");
}
}

then:

public Class Dog extends Animal{
public void eat(){
    System.out.println("Dog is eating");
    }
}

then in the main class:

public static void main(String args[]){
Animal d=new Dog();
Animal a=new Animal();
a.eat();
d.eat();
}

now the result should be:
Animal is eating
Dog is eating
So we can conclude here
Overloading binds at compile time "static binding"  while
Overriding binds at run time "dynamic binding"

Read More

Leetcode- Sum of two integer

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

Example:
Given a = 1 and b = 2, return 3.

Solution: bit-wise manipulation

Here are two integers a and b, if there is no carry occurring in the process then  a+b=a⊗b，Here ⊗ represents the XOR. The Carry bits appears when 1+1 so the carry bits of a+b can be represented as  2×(a & b)，& means AND operation, multiply 2 to shift left.

After N times of operation, the carry bit would be 0 then we can return the result;

The program can be easily written in recursive form

int getSum(int a, int b) { if(a == 0) return b; int x = a ^ b; int c = (a & b) << 1; return getSum(c, x); }

x0+c0

Read More

Leetcode--Reverse String

Write a function that takes a string as input and returns the string reversed.

Example:
Given s = "hello", return "olleh".

---------------------------------------------------------------------------------------------

This is one of the easiest problem in leetcode.

To reverse the string, all we need to do is swap the first character with the last one and go on.

class Solution {
public:
    string reverseString(string s) {
        int left = 0, right = s.size() - 1;
        while (left < right) {
            char t = s[left];
            s[left++] = s[right];
            s[right--] = t;
        }
        return s;
    }
};

Read More

Leetcode-Perfect Squares

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

Solution 1：Lagrange four square theorem

From Lagrange four square theorem, we can know that any natural number can represented 

by 4 square numbers. So the answer of this problem has been limited to 1~4.

The number can be written in form  

Then the Three square theorem then suggested that any number can satisfy the theorem above can 

also be represented by 3 square numbers.

So the situations can be handled respectively.

class Solution {
public:
    int numSquares(int n) {
        while (n % 4 == 0) n /= 4;
        if (n % 8 == 7) return 4;

        for (int a = 0; a * a <= n; ++a) {
            int b = sqrt(n - a * a);
            if (a * a + b * b == n) {
                return !!a + !!b;
            }
        }

        return 3;
    }
};

Solution 2 : Dynamic programming.

The problem is similar to the Coin change problem.

class Solution {
public:
    int numSquares(int n) {
       

        vector<int> dp(n+1,n+1);
        
        dp[0]=0;
        
        for(int i=1;i<=n;i++)
            for(int j=0;j*j<=n;j++){
                if(j*j<=i)
                    dp[i]=min(dp[i],dp[i-j*j]+1);
            }    
            
        return dp.back();

 

    }
};

Read More

Leecode Combination Sum IV

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

nums = [1, 2, 3]
target = 4

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.

We can still apply the DFS method to count this, however, the cost will be too high that can't pass the time limit. This case is similar to the coin exchange problem. We can use dynamic programming concept to reuse the product during the process.

The code is also quite similar to coin exchange problem.

    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target + 1);
        dp[0] = 1;
        for (int i = 1; i <= target; ++i) {
            for (int x : nums) {
                if (i >= x) {
                    dp[i] += dp[i - x];
                }
            }
        }
        
        return dp[target];
    }

Noted that in Coin exchange problem 

dp[0] = 0. The definition was "the minimum coins used to combine the value", therefore

the minimum coins to combine "0" should be zero. And in coin exchange problem we initiate other elements in the vector to n+1 to make the min-comparison work.

Here,

the dp represents " all possible sets to combine the value" while we didn't initiate other elements in the vecotr. The empty set is also counted to combine the value 0 here. So dp[0] =1;

Read More