LeetCode OJ – 第23页

LeetCode 477. Total Hamming Distance

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

Now your job is to find the total Hamming distance between all pairs of the given numbers.

Example:
Input: 4, 14, 2

Output: 6

Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case). So the answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.
Note:
Elements of the given array are in the range of 0 to 10^9
Length of the array will not exceed 10^4.

题目大意：两个数字的二进制表示中，相应的位不相同的个数即为这两个数的Hamming距离。给出一组数，计算他们每两对构成的Hamming距离的总和～

分析：遍历数组中所有数的相同某位，如果有cnt个1，n-cnt个0，则这一位能够构成的Hamming距离为cnt * (n – cnt)～所以从第0位开始一直计算到第32位，将所有位贡献的Hamming距离总和相加即可得到总的Hamming距离～

class Solution {
public:
    int totalHammingDistance(vector<int>& nums) {
        int result = 0, n = nums.size();
        for(int i = 0; i < 32; i++) {
            int cnt = 0;
            for(int j = 0; j < n; j++) {
                if(nums[j] >> i & 1 == 1)
                    cnt++;
            }
            result += cnt * (n - cnt);
        }
        return result;
    }
};

class Solution {

public:

int totalHammingDistance(vector<int>& nums) {

int result = 0, n = nums.size();

for(int i = 0; i < 32; i++) {

int cnt = 0;

for(int j = 0; j < n; j++) {

if(nums[j] >> i & 1 == 1)

cnt++;

}

result += cnt * (n - cnt);

}

return result;

}

};

LeetCode 445. Add Two Numbers II

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Follow up:
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7

题目大意：两个链表l1和l2，返回一个链表，其值为l1与l2的和～

分析：将l1和l2分别放入栈中，这样他们就被倒置了，然后依次出栈将结果相加，（不要忘记考虑进位问题），结果放入新的栈s中，然后将s弹栈，结果放入一个新链表中～～

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        stack<int> s1, s2, s;
        while(l1 != NULL) {
            s1.push(l1->val);
            l1 = l1->next;
        }
        while(l2 != NULL) {
            s2.push(l2->val);
            l2 = l2->next;
        }
        int carry = 0;
        while(!s1.empty() || !s2.empty()) {
            int tempsum = carry;
            if(!s1.empty()) {
                tempsum += s1.top();
                s1.pop();
            }
            if(!s2.empty()) {
                tempsum += s2.top();
                s2.pop();
            }
            carry = 0;
            if(tempsum >= 10) {
                carry = 1;
                tempsum = tempsum - 10;
            }
            s.push(tempsum);
        }
        if(carry == 1)
            s.push(1);
        ListNode* result = new ListNode(0);
        ListNode* cur = result;
        while(!s.empty()) {
            int top = s.top();
            s.pop();
            ListNode* node = new ListNode(top);
            cur->next = node;
            cur = cur->next;
        }
        return result->next;
    }
};

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* ListNode *next;

* ListNode(int x) : val(x), next(NULL) {}

* };

class Solution {

public:

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {

stack<int> s1, s2, s;

while(l1 != NULL) {

s1.push(l1->val);

l1 = l1->next;

}

while(l2 != NULL) {

s2.push(l2->val);

l2 = l2->next;

}

int carry = 0;

while(!s1.empty() || !s2.empty()) {

int tempsum = carry;

if(!s1.empty()) {

tempsum += s1.top();

s1.pop();

}

if(!s2.empty()) {

tempsum += s2.top();

s2.pop();

}

carry = 0;

if(tempsum >= 10) {

carry = 1;

tempsum = tempsum - 10;

}

s.push(tempsum);

}

if(carry == 1)

s.push(1);

ListNode* result = new ListNode(0);

ListNode* cur = result;

while(!s.empty()) {

int top = s.top();

s.pop();

ListNode* node = new ListNode(top);

cur->next = node;

cur = cur->next;

}

return result->next;

}

};

LeetCode 494. Target Sum

You are given a list of non-negative integers, a1, a2, …, an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and – as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

Example 1:
Input: nums is [1, 1, 1, 1, 1], S is 3.
Output: 5
Explanation:

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

There are 5 ways to assign symbols to make the sum of nums be target 3.
Note:
The length of the given array is positive and will not exceed 20.
The sum of elements in the given array will not exceed 1000.
Your output answer is guaranteed to be fitted in a 32-bit integer.

题目大意：给一个非负的整数数组，可以在每个元素前面加+或者-，给一个目标整数S，求问有多少种不同的添加方式，可以让数组中所有元素在添加符号之后相加的结果为S～

分析：深度优先搜索，尝试每次添加+或者-，当当前cnt为nums数组的大小的时候，判断sum与S是否相等，如果相等就result++。sum为当前cnt步数情况下的前面所有部分的总和～

class Solution {
public:
    int result;
    int findTargetSumWays(vector<int>& nums, int S) {
        dfs(0, 0, nums, S);
        return result;
    }
    void dfs(int sum, int cnt, vector<int>& nums, int S) {
        if(cnt == nums.size()) {
            if(sum == S)
                result++;
            return ;
        }
        dfs(sum + nums[cnt], cnt + 1, nums, S);
        dfs(sum - nums[cnt], cnt + 1, nums, S);
    }
};

class Solution {

public:

int result;

int findTargetSumWays(vector<int>& nums, int S) {

dfs(0, 0, nums, S);

return result;

}

void dfs(int sum, int cnt, vector<int>& nums, int S) {

if(cnt == nums.size()) {

if(sum == S)

result++;

return ;

}

dfs(sum + nums[cnt], cnt + 1, nums, S);

dfs(sum - nums[cnt], cnt + 1, nums, S);

}

};

LeetCode 398. Random Pick Index

Given an array of integers with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array.

Note:
The array size can be very large. Solution that uses too much extra space will not pass the judge.

Example:

int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);

// pick(3) should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.
solution.pick(3);

// pick(1) should return 0. Since in the array only nums[0] is equal to 1.
solution.pick(1);

题目大意：给一个整数数组，里面可能有重复元素。给一个target，随机返回一个数组元素等于target的元素下标～

分析：将所有等于target的元素的下标存储在index数组中，然后根据rand() % index.size()的值随机从index中取一个值返回～

class Solution {
private:
    vector<int> nums;
public:
    Solution(vector<int> nums) {
        this->nums = nums;
    }
    
    int pick(int target) {
        vector<int> index;
        for(int i = 0; i < nums.size(); i++) {
            if(nums[i] == target)
                index.push_back(i);
        }
        return index[rand() % index.size()];
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int param_1 = obj.pick(target);
 */

class Solution {

private:

vector<int> nums;

public:

Solution(vector<int> nums) {

this->nums = nums;

}

int pick(int target) {

vector<int> index;

for(int i = 0; i < nums.size(); i++) {

if(nums[i] == target)

index.push_back(i);

}

return index[rand() % index.size()];

}

};

/**

* Your Solution object will be instantiated and called as such:

* Solution obj = new Solution(nums);

* int param_1 = obj.pick(target);

LeetCode 382. Linked List Random Node

Given a singly linked list, return a random node’s value from the linked list. Each node must have the same probability of being chosen.

Follow up:
What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space?

Example:

// Init a singly linked list [1,2,3].
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
Solution solution = new Solution(head);

// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
solution.getRandom();

题目大意：给一个单链表，返回一个随机结点的值，要求每一个结点都有同样的概率被选中～

分析：先求出链表的长度len，然后用rand() % len生成一个0～len-1之间的随机数cnt，然后从head开始遍历直到第cnt个结点，返回第cnt个结点的值～

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
private:
    ListNode* head;
    int len;
public:
    /** @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node. */
    Solution(ListNode* head) {
        this->head = head;
        len = 1;
        while(head->next != NULL) {
            head = head->next;
            len++;
        }
    }
    
    /** Returns a random node's value. */
    int getRandom() {
        ListNode* node = head;
        int cnt = rand() % len;
        while(cnt--) {
            node = node->next;
        }
        return node->val;
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(head);
 * int param_1 = obj.getRandom();
 */

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* ListNode *next;

* ListNode(int x) : val(x), next(NULL) {}

* };

class Solution {

private:

ListNode* head;

int len;

public:

/** @param head The linked list's head.

Note that the head is guaranteed to be not null, so it contains at least one node. */

Solution(ListNode* head) {

this->head = head;

len = 1;

while(head->next != NULL) {

head = head->next;

len++;

}

/** Returns a random node's value. */

int getRandom() {

ListNode* node = head;

int cnt = rand() % len;

while(cnt--) {

node = node->next;

}

return node->val;

}

};

/**

* Your Solution object will be instantiated and called as such:

* Solution obj = new Solution(head);

* int param_1 = obj.getRandom();

【C++】n_element的用法

n_element函数定义在头文件#include <algorithm>里面，用法是：

n_element(v.begin(), v.begin() + k, v.end());

表示假设v排序后v[k]应该存储的值为v[k]，则n_element函数的作用就是让v[k]这个值放在v[k]处，且让v[k]左边的数都小于v[k]，v[k]右边的数都大于v[k]。但是不保证他们是有序的。（即v[k]处存放的是第k+1大的数，并且左边数都比他小右边数字都比他大，比如假设k = 1，表示将v[1]处设置为第2大的数）

也可以自定义添加cmp函数，表示方法为：

n_element(v.begin(), v.begin() + k, v.end(), cmp);

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    vector<int> v{5, 6, 4, 3, 2, 6, 7, 9, 3};
    nth_element(v.begin(), v.begin() + v.size()/2, v.end());
    cout << "The median is " << v[v.size()/2] << '\n';
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int main() {

vector<int> v{5, 6, 4, 3, 2, 6, 7, 9, 3};

nth_element(v.begin(), v.begin() + v.size()/2, v.end());

cout << "The median is " << v[v.size()/2] << '\n';

}

输出为：

The median is 5