Code – 第157页

LeetCode 392. Is Subsequence

Given a string s and a string t, check if s is subsequence of t.

You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and s is a short string (<=100). A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ace” is a subsequence of “abcde” while “aec” is not). Example 1: s = “abc”, t = “ahbgdc” Return true. Example 2: s = “axc”, t = “ahbgdc” Return false. Follow up: If there are lots of incoming S, say S1, S2, … , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?

题目大意：判断s是否是t的子串～

分析：设立两个指针p和q，分别指向s[0]和t[0]，只要p和q没有超出s和t的长度范围，不断判断当前s[p]与t[q]是否相等，如果不相等就将q指针不断后移，直到相等为止～相等后p和q指针同时后移，依次判断～
最终判断p指针是否等于lens，即p指针是否指完了s字符串的所有字符～

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int p = 0, q = 0, lens = s.length(), lent = t.length();
        while(p < lens && q < lent) {
            while(q < lent && s[p] != t[q]) q++;
            if(s[p] == t[q]) {
                p++;
                q++;
            }
        }
        return p == lens;
    }
};

class Solution {

public:

bool isSubsequence(string s, string t) {

int p = 0, q = 0, lens = s.length(), lent = t.length();

while(p < lens && q < lent) {

while(q < lent && s[p] != t[q]) q++;

if(s[p] == t[q]) {

p++;

q++;

}

return p == lens;

}

};

LeetCode 384. Shuffle an Array

Shuffle a set of numbers without duplicates.

Example:

// Init an array with set 1, 2, and 3.
int[] nums = {1,2,3};
Solution solution = new Solution(nums);

// Shuffle the array [1,2,3] and return its result. Any permutation of [1,2,3] must equally likely to be returned.
solution.shuffle();

// Resets the array back to its original configuration [1,2,3].
solution.reset();

// Returns the random shuffling of array [1,2,3].
solution.shuffle();

题目大意：实现洗牌算法。给定一个没有重复元素的数组，写shuffle和set函数，shuffle函数要求对nums数组进行洗牌然后返回，set函数要求返回原来的nums数组～
分析：设立两个数组nums和origin，如果set就返回不会更改的origin数组，如果要洗牌，从nums的最后一位开始，设index为0～n-1中的一个随机数，产生后将index与最后一位元素进行交换，这样最后一位就算敲定了，然后再往前一位，假设当前位的下标是k，那就产生0～k之间的一个随机数，然后交换，以此类推，rand() % (i + 1)表示生成0～i中的一个随机数～直到第一位为止～

class Solution {
private:
    vector<int> nums;
    vector<int> origin;
public:
    Solution(vector<int> nums) {
        this->nums = nums;
        this->origin = nums;
    }
    
    /** Resets the array to its original configuration and return it. */
    vector<int> reset() {
        return origin;
    }
    
    /** Returns a random shuffling of the array. */
    vector<int> shuffle() {
        int n = nums.size();
        for(int i = n - 1; i >= 0; i--) {
            int index = rand() % (i + 1);
            swap(nums[i], nums[index]);
        }
        return nums;
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * vector<int> param_1 = obj.reset();
 * vector<int> param_2 = obj.shuffle();
 */

class Solution {

private:

vector<int> nums;

vector<int> origin;

public:

Solution(vector<int> nums) {

this->nums = nums;

this->origin = nums;

}

/** Resets the array to its original configuration and return it. */

vector<int> reset() {

return origin;

}

/** Returns a random shuffling of the array. */

vector<int> shuffle() {

int n = nums.size();

for(int i = n - 1; i >= 0; i--) {

int index = rand() % (i + 1);

swap(nums[i], nums[index]);

}

return nums;

}

};

/**

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

* Solution obj = new Solution(nums);

* vector<int> param_1 = obj.reset();

* vector<int> param_2 = obj.shuffle();

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

}

};