MisakaTang's Blog

发表于 更新于 分类于

题目及理解

题目链接
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: 

1
2
3
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:

  1. n is a positive integer, which is in the range of [1, 10000].
  2. All the integers in the array will be in the range of [-10000, 10000].

理解

题目很简单,就是对每两个数进行min操作,然后全部相加得到的数要最大.直接对数组进行排序,然后按顺序两两取最小(循环+2)然后相加即可.

代码

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public:    
    int arrayPairSum(vector<int>& nums) {        
        sort(nums.begin(), nums.end());        
        int maximum = 0;        
        for(int i = 0; i < nums.size(); i+=2){            
            maximum += nums[i];        
        }        
        return maximum;    
    }
};

发表于 更新于 分类于

题目及理解

题目链接
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: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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.

读题

简单题目,就是把两棵二叉树的各个结点加起来生成一棵新的树.只要遍历每个结点然后将值相加就好.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/** 
* Definition for a binary tree node. 
* struct TreeNode { 
*     int val; 
*     TreeNode *left; 
*     TreeNode *right; 
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 
* }; 
*/
class Solution {
    public:    
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {        
        TreeNode* t3;        
        if(t1 == NULL)            
        return t2;        
        if(t2 == NULL)            
        return t1;        
        t3 = new TreeNode(t1->val+t2->val);        
        t3->left = mergeTrees(t1->left,t2->left);        
        t3->right = mergeTrees(t1->right,t2->right);        
        return t3;    
    }
};

发表于 更新于 分类于

从这个博客开始打算坚持在LeetCode上刷一点算法题,之后可能也会有Python版本的现在还是用C++在写了,就先从简单题开始刷起了.

题目以及理解

题目链接-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: 

1
2
3
4
5
6
7
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就可以了.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public:    
        int hammingDistance(int x, int y) {        
            int z = x ^ y;        
            int c = 0;        
            while (z > 0){            
                if ((z & 1) == 1)                
                c++;            
                z >>= 1;        
            }        
        return c;    
    }
};
0%