LeetCode算法题解

1、给定两个正整数（二进制形式表示）A和B，问把A变为B需要改变多少位（bit）?也就是说，整数A和B的二进制表示中有多少位是不同的？(181)

解法一：举例说明，为了减少复杂度，就使用八位二进制吧。设 A = 0010 1011， B = 0110 0101.
1. C = A & B = 0010 0001；
2. D = A | B = 0110 1111；
3. E = C ^ D = 0100 1110；
4. 结果E中有4个1，那么也就是说将A变成B，需要改变4位（bit）。
至于如何判断E的二进制表示中有几个1，可以采用快速移位与方法。
算法原理如下：
1. A & B，得到的结果C中的1的位表明了A和B中相同的位都是1的位；
2. A | B， 得到的结果D中的1的位表明了A和B在该位至少有一个为1的位，包含了A 与 B 都是1的位数，
经过前两步的位运算，，C 中1的位表明了A 和 B在该位都是1，D中为0的位表明了A 和 B 在该位都是0 ，所以进行第三步。
3. C ^ D，E 中为1的位表明了A 和 B不同的位。

class Solution {
    /**
     *@param a, b: Two integer
     *return: An integer
     */
    public static int bitSwapRequired(int a, int b) {
        
       /* int getNum(int n)
        {
            if(n==0) 
            {
                return 0;
            }
            int count=0;
            while(n)
            {
                n &= (n-1);
                count++;
            }
            return count;
        } */
        int count = 0;
        int c = a & b;
        int d = a | b;
        int n = c ^ d;
        if(n == 0)
        {
            return 0;
        }
        while(n != 0)
        {
            n &= (n-1);
            count++;
        }
        
        
        return count;
    }
    
 
};

 2.dp

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        //use vector to represent 2 dimension array
        //hero num
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dp(m, <vector<int> (n));
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(i == 0){
                    if(j == 0){
                        dp[i][j] = grid[i][j];
                    }else{
                        dp[i][j] = dp[i][j-1] + grid[i][j];
                    }
                }else if(j == 0){
                    dp[i][j] = dp[i-1][j] + grid[i][j];
                }else{
                    dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + grid[i][j];
                }
            }
        }
        return dp[m-1][n-1];
    }
};

 3、问题描述：给定一个区间集合，合并有重叠的区间  解题思路：先对区间进行排序，按开始点进行排序，再一个一个进行合并

Total Accepted: 49133 Total Submissions: 211712 Difficulty: Hard

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        
        List<Interval> result = new ArrayList<Interval>();
        
        if(null == intervals || intervals.size() <= 0){
            return result;
        }
        
        Collections.sort(intervals, new Comparator<Interval>(){
           public int compare(Interval arg0, Interval arg1){
               return arg0.start - arg1.start;
           } 
        });
        
        Interval prev = null;
        for(Interval item: intervals){
            if(null == prev || prev.end < item.start){
                result.add(item);
                prev = item;
            }else if(prev.end < item.end){
                prev.end = item.end;
            }
        }
        
        return result;
        
    }
}

 附：上面采用java实现算法，其中排序使用了Collections.sort方法实现，这里研究一下对该方法实现排序的两种方法：
方法1：对列表对象实现Comparable接口

import java.util.*;

public class collection_sort{
    public static void main(String[] args){

        User user = new User();
        user.setName("jack");
        user.setOrder(3);

        User user1 = new User();
        user1.setName("randy");
        user1.setOrder(2);

        List<User> list = new ArrayList<User>();
        list.add(user);
        list.add(user1);
        Collections.sort(list);
        for(User u: list){
            System.out.println(u.getName());
        }
    }
}

class User implements Comparable<User>{
    private String name;
    private Integer order;

    public String getName(){
        return name;
    }
    public void setName(String name){
        this.name = name;
    }
    public Integer getOrder(){
        return order;
    }
    public void setOrder(Integer order){
        this.order = order;
    }

    public int compareTo(User arg0){
        return this.getOrder().compareTo(arg0.getOrder());
    }
}

方法2：根据Collections.sort方法重载实现

public class collection_sort{

    public static void main(String[] args){

        User user = new User();
        user.setName("jack");
        user.setOrder(3);

        User user1 = new User();
        user1.setName("randy");
        user1.setOrder(2);

        List<User> list = new ArrayList<User>();
        list.add(user);
        list.add(user1);
        

        Collections.sort(list, new Comparator<User>(){

            public int compare(User arg0, User arg1){
                return arg0.getOrder().compareTo(arg1.getOrder());
            }
        });

        for(User u: list){
            System.out.println(u.getName());
        }
    }
}

class User{
    private String name;
    private Integer order;

    public String getName(){
        return name;
    }
    public void setName(String name){
        this.name = name;
    }
    public Integer getOrder(){
        return order;
    }
    public void setOrder(Integer order){
        this.order = order;
    }
}