liuchuo – 第158页 – 我不管，反正我最萌～

LeetCode 357. Count Numbers with Unique Digits

Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10n.

Example:
Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding [11,22,33,44,55,66,77,88,99])

Hint:

A direct way is to use the backtracking approach.
Backtracking should contains three states which are (the current number, number of steps to get that number and a bitmask which represent which number is marked as visited so far in the current number). Start with state (0,0,0) and count all valid number till we reach number of steps equals to 10n.
This problem can also be solved using a dynamic programming approach and some knowledge of combinatorics.
Let f(k) = count of numbers with unique digits with length equals k.
f(1) = 10, …, f(k) = 9 * 9 * 8 * … (9 – k + 2) [The first factor is 9 because a number cannot start with 0].

题目大意：给一个数n，求0～n位数间所有数字中，每一位数字都各不相同的数字的个数～

分析：根据提示中所给的公式，1位数字有10个，第k位有f(k) = 9 * 9 * 8 * … (9 – k + 2)个，累加从2位到n位的f(k)的总和，再加上1位的10个数字，即为所求～

class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        if(n == 0) return 1;
        int result = 10, cnt = 9;
        for(int i = 2; i <= n; i++) {
            cnt *= (11 - i);
            result += cnt;
        }
        return result;
    }
};

class Solution {

public:

int countNumbersWithUniqueDigits(int n) {

if(n == 0) return 1;

int result = 10, cnt = 9;

for(int i = 2; i <= n; i++) {

cnt *= (11 - i);

result += cnt;

}

return result;

}

};

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();