Code – 第99页

LeetCode 599. Minimum Index Sum of Two Lists

Suppose Andy and Doris want to choose a restaurant for dinner, and they both have a list of favorite restaurants represented by strings.

You need to help them find out their common interest with the least list index sum. If there is a choice tie between answers, output all of them with no order requirement. You could assume there always exists an answer.

Example 1:
Input:
[“Shogun”, “Tapioca Express”, “Burger King”, “KFC”]
[“Piatti”, “The Grill at Torrey Pines”, “Hungry Hunter Steakhouse”, “Shogun”]
Output: [“Shogun”]
Explanation: The only restaurant they both like is “Shogun”.
Example 2:
Input:
[“Shogun”, “Tapioca Express”, “Burger King”, “KFC”]
[“KFC”, “Shogun”, “Burger King”]
Output: [“Shogun”]
Explanation: The restaurant they both like and have the least index sum is “Shogun” with index sum 1 (0+1).
Note:
The length of both lists will be in the range of [1, 1000].
The length of strings in both lists will be in the range of [1, 30].
The index is starting from 0 to the list length minus 1.
No duplicates in both lists.

题目大意：假设安迪和多丽丝想选择一家餐厅吃饭，他们有一串最喜欢的餐厅名单。你需要帮助他们用最小的指数总和找到他们的共同兴趣。如果答案有多个则没有顺序要求地返回所有答案在string数组中～

分析：当i+j比minSum小时将数组清空，minSum赋值为i+j，list1[i]放入ans数组中

class Solution {
public:
    vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
        vector<string> ans;
        int minSum = 2000;
        for (int i = 0; i < list1.size(); i++) {
            for (int j = 0; j < list2.size(); j++) {
                if (list1[i] == list2[j] && minSum > i + j) {
                    ans.clear();
                    ans.push_back(list1[i]);
                    minSum = i + j;
                } else if (list1[i] == list2[j] && minSum == i + j) {
                    ans.push_back(list1[i]);
                }
            }
        }
        return ans;
    }
};

class Solution {

public:

vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {

vector<string> ans;

int minSum = 2000;

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

for (int j = 0; j < list2.size(); j++) {

if (list1[i] == list2[j] && minSum > i + j) {

ans.clear();

ans.push_back(list1[i]);

minSum = i + j;

} else if (list1[i] == list2[j] && minSum == i + j) {

ans.push_back(list1[i]);

}

return ans;

}

};

LeetCode 581. Shortest Unsorted Continuous Subarray

Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too.

You need to find the shortest such subarray and output its length.

Example 1:
Input: [2, 6, 4, 8, 10, 9, 15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.
Note:
Then length of the input array is in range [1, 10,000].
The input array may contain duplicates, so ascending order here means <=.

题目大意：给定一个整数数组，你需要找到一个连续的子数组，如果你按升序对这个子数组排序，那么整个数组将也是升序。你需要找到最短的这样的子数组并输出它的长度。

分析：对v排序，i找到第一个和排序后的数组v不相等的元素，j找到最后一个和排序后的数组v不相等的元素，如果i<=j说明存在这样一个长度，长度为j-i+1，否则不存在这样一个长度，则返回0～

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        vector<int> v(nums);
        sort(v.begin(), v.end());
        int i = 0, j = nums.size() - 1;
        while (i < nums.size() && nums[i] == v[i]) i++;
        while (j >= 0 && nums[j] == v[j]) j--;
        return i <= j ? j - i + 1 : 0;
    }
};

class Solution {

public:

int findUnsortedSubarray(vector<int>& nums) {

vector<int> v(nums);

sort(v.begin(), v.end());

int i = 0, j = nums.size() - 1;

while (i < nums.size() && nums[i] == v[i]) i++;

while (j >= 0 && nums[j] == v[j]) j--;

return i <= j ? j - i + 1 : 0;

}

};

LeetCode 532. K-diff Pairs in an Array

Given an array of integers and an integer k, you need to find the number of unique k-diff pairs in the array. Here a k-diff pair is defined as an integer pair (i, j), where i and j are both numbers in the array and their absolute difference is k.

Example 1:
Input: [3, 1, 4, 1, 5], k = 2
Output: 2
Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
Although we have two 1s in the input, we should only return the number of unique pairs.
Example 2:
Input:[1, 2, 3, 4, 5], k = 1
Output: 4
Explanation: There are four 1-diff pairs in the array, (1, 2), (2, 3), (3, 4) and (4, 5).
Example 3:
Input: [1, 3, 1, 5, 4], k = 0
Output: 1
Explanation: There is one 0-diff pair in the array, (1, 1).
Note:
The pairs (i, j) and (j, i) count as the same pair.
The length of the array wont exceed 10,000.
All the integers in the given input belong to the range: [-1e7, 1e7].

题目大意：给定一个整数和一个整数k的数组，你需要找到数组中唯一的k-diff对的个数。这里k-diff对被定义为一个整数对（i，j），其中i和j都是数组中的数字，它们的绝对差值是k。

分析：对于当前遍历的nums[i]，在它前面找是否存在满足与它相差k的数字，如果找到了就将这对数字(i, j)中较大的一个数字放到set里，然后将这个数在map中标记为true表示存在这个数字等待它的后面的数字判断它是否存在（这样可以避免重复，也就是说每个数字只在它前面找是否有符合条件的数字），最后返回set的大小～

class Solution {
public:
    int findPairs(vector<int>& nums, int k) {
        if (k < 0) return 0;
        unordered_map<int, bool> m;
        unordered_set<int> s;
        for (int i = 0; i < nums.size(); i++) {
            if (m[nums[i] - k]) s.insert(nums[i]);
            if (m[nums[i] + k]) s.insert(nums[i] + k);
            m[nums[i]] = true;
        }
        return s.size();
    }
};

class Solution {

public:

int findPairs(vector<int>& nums, int k) {

if (k < 0) return 0;

unordered_map<int, bool> m;

unordered_set<int> s;

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

if (m[nums[i] - k]) s.insert(nums[i]);

if (m[nums[i] + k]) s.insert(nums[i] + k);

m[nums[i]] = true;

}

return s.size();

}

};

LeetCode 479. Largest Palindrome Product

Find the largest palindrome made from the product of two n-digit numbers.
Since the result could be very large, you should return the largest palindrome mod 1337.
Example:
Input: 2
Output: 987
Explanation: 99 x 91 = 9009, 9009 % 1337 = 987
Note:
The range of n is [1,8].

题目大意：找到由两个n位数字乘积得到的最大回文。由于结果可能非常大，返回最大回文的%1337后的结果。

分析：l是两位数的最小值，r是两位数的最大值，从r到1能够组成的回文是r的字符串+r倒置后的字符串组成的字符串，将这个回文字串转为long型的ans，j从r到根号ans中，判断是否有j可以满足能被ans整除的j，并且这个除以的结果是小于r的，如果找到了返回ans%1337的结果，因为如果n == 1的时候比较特殊，组成的回文串是9，所以如果for循环后依然没有返回，说明遇到了n=1，那么最后就单独返回9～

class Solution {
public:
    int largestPalindrome(int n) {
        int l = pow(10, n-1), r = pow(10, n) - 1;
        for (int i = r; i >= 1; i--) {
            string s = to_string(i);
            string t = s;
            reverse(t.begin(), t.end());
            long ans = stol(s + t);
            for (long j = r; j * j >= ans; j--)
                if (ans % j == 0 && ans / j <= r) return ans % 1337;
        }
        return 9;
    }
};

class Solution {

public:

int largestPalindrome(int n) {

int l = pow(10, n-1), r = pow(10, n) - 1;

for (int i = r; i >= 1; i--) {

string s = to_string(i);

string t = s;

reverse(t.begin(), t.end());

long ans = stol(s + t);

for (long j = r; j * j >= ans; j--)

if (ans % j == 0 && ans / j <= r) return ans % 1337;

}

return 9;

}

};

LeetCode 728. Self Dividing Numbers

A self-dividing number is a number that is divisible by every digit it contains.

For example, 128 is a self-dividing number because 128 % 1 == 0, 128 % 2 == 0, and 128 % 8 == 0.

Also, a self-dividing number is not allowed to contain the digit zero.

Given a lower and upper number bound, output a list of every possible self dividing number, including the bounds if possible.

Example 1:
Input:
left = 1, right = 22
Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]
Note:

The boundaries of each input argument are 1 <= left <= right <= 10000.

题目大意：一个自我分裂的数字是一个数字，它可以被每个数字所包含。例如，128是一个自分数，因为128％1 == 0，128％2 == 0和128％8 == 0。而且，一个自分数的数字不允许包含数字零。给定一个较低和较高的数字边界，输出每一个可能的自分数的列表，如果可能的话，包括边界。

分析：将left和right中每一个数字i转为string，对string的每一位取余，如果当前位等于0或者取余结果不为0则flag标记为false，把所有flag为true的数字放入ans数组中返回～

class Solution {
public:
    vector<int> selfDividingNumbers(int left, int right) {
        vector<int> ans;
        for (int i = left; i <= right; i++) {
            string s = to_string(i);
            bool flag = true;
            for (int j = 0; j < s.length(); j++) {
                if (s[j] == '0' || i % (s[j] - '0') != 0) {
                    flag = false;
                    break;
                }
            }  
            if (flag) ans.push_back(i);
        }
        return ans;
    }
};

class Solution {

public:

vector<int> selfDividingNumbers(int left, int right) {

vector<int> ans;

for (int i = left; i <= right; i++) {

string s = to_string(i);

bool flag = true;

for (int j = 0; j < s.length(); j++) {

if (s[j] == '0' || i % (s[j] - '0') != 0) {

flag = false;

break;

}

if (flag) ans.push_back(i);

}

return ans;

}

};

LeetCode 717. 1-bit and 2-bit Characters

We have two special characters. The first character can be represented by one bit 0. The second character can be represented by two bits (10 or 11).

Now given a string represented by several bits. Return whether the last character must be a one-bit character or not. The given string will always end with a zero.

Example 1:
Input:
bits = [1, 0, 0]
Output: True
Explanation:
The only way to decode it is two-bit character and one-bit character. So the last character is one-bit character.
Example 2:
Input:
bits = [1, 1, 1, 0]
Output: False
Explanation:
The only way to decode it is two-bit character and two-bit character. So the last character is NOT one-bit character.
Note:

1 <= len(bits) <= 1000.
bits[i] is always 0 or 1.

题目大意：我们有两个特殊字符。第一个字符可以用1位表示。第二个字符可以用2位（10或11）表示。现在给出一个由几位表示的字符串。返回最后一个字符是否是一位字符。给定的字符串将始终以0结束

分析：i从0开始遍历整个bits数组，当i遇到0时走一步，否则走2步，判断是否会走到最后一个元素～

class Solution {
public:
    bool isOneBitCharacter(vector<int>& bits) {
        int i = 0;
        while(i < bits.size()) {
            if (i == (bits.size() - 1)) return true;
            if (bits[i] == 0) i++;
            else i += 2;
        }
        return false;
    }
};

class Solution {

public:

bool isOneBitCharacter(vector<int>& bits) {

int i = 0;

while(i < bits.size()) {

if (i == (bits.size() - 1)) return true;

if (bits[i] == 0) i++;

else i += 2;

}

return false;

}

};