leetcode

leetcode刷题地址：https://leetcode.com/problemset/algorithms/

344. Reverse String

算法思路

倒序输出~~

编码实现

    /**
     * 344. Reverse String
     * Example:
     * Given s = "hello", return "olleh".
     * @param s
     * @return
     */
    public String reverseString(String s) {
        if(s.length()<=1){
            return s;
        }
        StringBuffer sbf=new StringBuffer();
        for(int i=s.length()-1;i>=0;i--){
            sbf.append(s.charAt(i));
        }
        return sbf.toString();
    }

461. Hamming Distance

问题描述

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.

Note: 0 ≤ x, y < 231.

Example:

Input: x = 1, y = 4

Output: 2

Explanation: 1 (0 0 0 1) 4 (0 1 0 0) ↑ ↑

The above arrows point to positions where the corresponding bits are different.

算法思路

按位求异或，然后将结果转换为二进制，输出为1的个数。

编码实现

 	/**
     * 461  汉明距离
     * @param x
     * @param y
     * @return
     */
    public int hammingDistance(int x, int y) {
        String result=Integer.toBinaryString(x^y);
        int diff=0;
        for(int i=0;i<result.length();i++){
            if(result.charAt(i)=='1'){
                diff++;
            }
        }
        return diff;
    }

617. Merge Two Binary Trees

问题描述

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.

You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.

Example 1: Input: Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
Output: Merged tree: 3 /
4 5 / \ \ 5 4 7

Note: The merging process must start from the root nodes of both trees.

算法思路

用到递归的方法，用二叉树前序遍历的方法，依次求出值，最后返回根节点。

编码实现

	public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if(t1==null&&t2==null){
            return null;
        }else if(t1==null&&t2!=null){
            return t2;
        }else if(t1!=null&&t2==null){
            return t1;
        }else{
            t1.val+=t2.val;
            t1.left=mergeTrees(t1.left,t2.left);
            t1.right=mergeTrees(t1.right,t2.right);
        }
        return t1;
    }

561. Array Partition I

问题描述

Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), …, (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.

Example 1: Input: [1,4,3,2]

Output: 4 Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).

Note:

n is a positive integer, which is in the range of [1, 10000].

All the integers in the array will be in the range of [-10000, 10000].

编码实现

自己尝试实现了一个版本，但是系统反应Submission Result: Time Limit Exceeded ，自己的算法版本效率太低，oh,my god!下面是我实现的

	public class Solution {
	     public int arrayPairSum(int[] nums) {
	        for(int i=0;i<nums.length-1;i++){
	            for(int j=0;j<nums.length-i-1;j++){
	                if(nums[j]>nums[j+1]){
	                    int tmp=nums[j];
	                    nums[j]=nums[j+1];
	                    nums[j+1]=tmp;
	                }
	            }
	        }
	        int sum=0;
	        for(int m=0;m<nums.length-1;m+=2){
	            sum+=nums[m];
	        }
	        return sum;
	    }
	}

然后又从网上看了下发现人家用Array.sort(),Array.sort底层用的快速排序平均时间复杂度为O(n*log2n)，而冒泡时间复杂度O(n2)，显然当n很大时用快速排序效果会更好。下面是更改后的实现算法，完美通过。

 	public int arrayPairSum(int[] nums) {
        Arrays.sort(nums);
        int sum=0;
        for(int m=0;m<nums.length-1;m+=2){
            sum+=nums[m];
        }
        return sum;
    }

赏 支付宝打赏 微信打赏

您的打赏是对我最大的鼓励！