记录在学习算法过程中没有归类的leetcode题目。

hash table

500 Keyboard Row

题目描述

Given a List of words, return the words that can be typed using letters of alphabet on only one row’s of American keyboard like the image below.

题目解析

给定字符串，返回可以用键盘的一行字母输出的字符串。可以用c++里的map。

class Solution {
public:
    vector<string> findWords(vector<string>& words){
        map<char,int> m;
        vector<string> s;
        vector<string> ans;
        s.push_back("qwertyuiop");
        s.push_back("asdfghjkl");
        s.push_back("zxcvbnm");
        int i,j;

        for(i=0;i<s.size();i++){
            for(j=0;j<s[i].length();j++){
                m[s[i][j]] = i;
            }
        }
        for(i=0;i<words.size();i++){
            for(j=0;j<words[i].length();j++){
                if(words[i][j] > 'z' || words[i][j] < 'a')
                    m[words[i][j]] = m[words[i][j]+32];
                if(m[words[i][j]] != m[words[i][0]])
                    break;
            }
            if(j == words[i].length())
                ans.push_back(words[i]);
        }
        return ans;
    }   
};

476 Number Complement

题目描述

Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation.

Note:
The given integer is guaranteed to fit within the range of a 32-bit signed integer.
You could assume no leading zero bit in the integer’s binary representation.

题目解析

给定一个正整数，求其反码。

class Solution {
public:
int findComplement(int num){
    int ans = 0;
    int i = 0;
    while(num){
        ans = ans + ((num%2)^1) * pow(2,i);
        num = num / 2;
        i++;
    }
    return ans;
}
};

1189 Maximum Number of Balloons

题目描述

Given a string text, you want to use the characters of text to form as many instances of the word “balloon” as possible.

You can use each character in text at most once. Return the maximum number of instances that can be formed.

题目解析

统计给定字符串中能组成“balloon”的数目，可以用map统计，注意’l’和’o’都出现了两次。看了其他人的答案，也可以用vector统计，下标是该字符与’a’的距离。

class Solution {
public:
    int maxNumberOfBalloons(string text) {
        int ans = 10000;
        map<char,int> m;
        string s = "balon";
        for(int i=0;i<text.length();i++){
            m[text[i]] += 1;
        }
        for(int i=0;i<s.length();i++){
            ans = min(m[s[i]],ans);
        }
        ans = min(ans,m['o']/2);
        ans = min(ans,m['l']/2);
        return ans;    
    }
};

136 Single Number

题目描述

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

题目解析

给定一个数组，数组中的元素有一个元素出现了1次，其他元素都出现了两次，找出这个出现一次的元素。我用的是哈希表，Memory Usage很高。

class Solution {
public:
int singleNumber(vector<int>& nums){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    map<int,int> m;
    int i;
    for(i=0;i<nums.size();i++){
        m[nums[i]] += 1;
    }
    for(i=0;i<nums.size();i++){
        if(m[nums[i]] == 1)
            break;
    }
    return nums[i];
}

};

看到一个比较靠前的答案，好机智啊，它把数组中所有的元素都进行异或，最后计算的结果就是只出现一次的元素，因为出现两次的都两两异或为0了。

class Solution {
public:
    int singleNumber(vector<int>& nums) noexcept {
        int result = 0;
        for (int num : nums) {
            result ^= num;
        }
        return result;
    }
};

884 Uncommon Words from Two Sentences

题目描述

We are given two sentences A and B. (A sentence is a string of space separated words. Each word consists only of lowercase letters.)

A word is uncommon if it appears exactly once in one of the sentences, and does not appear in the other sentence.

Return a list of all uncommon words.

You may return the list in any order.

题目解析

返回给定string中只出现一次的单词，用hash table来统计。

class Solution {
public:
    vector<string> uncommonFromSentences(string A, string B){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    map<string,int> m;
    vector<string> ans;
    string temp = "";
    for(int i=0;i<A.length();i++){
        if(A[i] != ' ')
            temp += A[i];
        else{
            m[temp] += 1;
            temp = "";
        }
    }
    m[temp] += 1;
    temp= "";
    for(int i=0;i<B.length();i++){
        if(B[i] != ' ')
            temp += B[i];
        else{
            m[temp] += 1;
            temp = "";
        }
    }
    m[temp] += 1;
    map<string,int>::iterator iter;
    for(iter=m.begin();iter!=m.end();iter++)
        if(iter->second == 1)
            ans.push_back(iter->first);
    return ans;

}
};

数组

985 Sum of Even Numbers After Queries

题目描述

We have an array A of integers, and an array queries of queries.

For the i-th query val = queries[i][0], index = queries[i][1], we add val to A[index]. Then, the answer to the i-th query is the sum of the even values of A.

(Here, the given index = queries[i][1] is a 0-based index, and each query permanently modifies the array A.)

Return the answer to all queries. Your answer array should have answer[i] as the answer to the i-th query.

题目解析

每次根据index和val的值，更新A[index] += val，更新数组后计算A中所有偶数的和，返回每次更新后偶数和的计算结果。
其实可以不用每次都重新计算一遍数组A中所有偶数的和，可以在更新之前先计算一遍，记为sum，然后根据每次A[index]和val，如果A[index]和val均为偶数，那么所求的结果是sum+val；如果A[index]和val均为奇数，那么计算结果为sum-val；否则如果A[index]为偶数，更新sum为sum-A[index]。最后再更新数组中的A[index] += val。

class Solution {
public:
vector<int> sumEvenAfterQueries(vector<int>& A, vector<vector<int> >& queries){
     vector<int> ans;
     int sum = 0,i=0;
     for(i=0;i<A.size();i++){
        if(A[i]%2 == 0)
            sum += A[i];
     }
     for(i=0;i<queries.size();i++){
        int val = queries[i][0];
        int index = queries[i][1];
        if((A[index]%2==0 && val%2==0)){
            sum += val;
            ans.push_back(sum);

        }
        else if(A[index]%2!=0 && val%2!=0){
            sum = sum + A[index] + val;
            ans.push_back(sum);
        }
        else{
            if(A[index] %2 == 0)
                sum -= A[index];
            ans.push_back(sum);
        }
        A[index] += val;
     }
     return ans;
 }
};

堆

1046 Last Stone Weight

题目描述

We have a collection of rocks, each rock has a positive integer weight.

Each turn, we choose the two heaviest rocks and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is:

If x == y, both stones are totally destroyed;
If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x.
At the end, there is at most 1 stone left. Return the weight of this stone (or 0 if there are no stones left.)

题目解析

给定一个数组，降序排列后，y为数组中的第一个元素，也就是最大的，x为数组中的第二个元素，如果x == y，则删除这两个元素；如果x != y，则更新y为y - x。
因为每次我们都要取出最大元素，x相当于删除y之后数组中的最大元素，如果x != y，则将y-x插入数组中。可以维护一个大顶堆，每次都取出堆顶元素，再根据比较值决定是否插入新元素。

class Solution {
public:
    int lastStoneWeight(vector<int>& stones){
    int x,y;
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    make_heap(stones.begin(),stones.end());
    while(1){
        if(stones.size() < 2)
            break;
        y = stones[0];
        pop_heap(stones.begin(),stones.end());
        stones.pop_back();
        //make_heap(stones.begin(),stones.end());
        x = stones[0];
        pop_heap(stones.begin(),stones.end());
        stones.pop_back();
        if(x != y){
            stones.push_back(y-x);
            push_heap(stones.begin(),stones.end());
        }
    }

    if(stones.size()==1)
        return stones[0];
    else
        return 0;
}

};

c++中的堆操作

#include<algorithm>
vector<int> A{1,2,3,5,8};
//建立大顶堆
make_heap(A.begin(),A.end());
//插入元素10，并恢复堆排序
A.push_back(10);
push_heap(A.begin(),A.end());
//删除堆顶元素，先将元素移至末尾，再删除
pop_heap(A.begin(),A.end());
A.pop_back();

参考

http://c.biancheng.net/view/481.html
https://blog.csdn.net/yhc166188/article/details/91538715

栈

682 Baseball Game

题目描述

You’re now a baseball game point recorder.

Given a list of strings, each string can be one of the 4 following types:

Integer (one round’s score): Directly represents the number of points you get in this round.
“+” (one round’s score): Represents that the points you get in this round are the sum of the last two valid round’s points.
“D” (one round’s score): Represents that the points you get in this round are the doubled data of the last valid round’s points.
“C” (an operation, which isn’t a round’s score): Represents the last valid round’s points you get were invalid and should be removed.
Each round’s operation is permanent and could have an impact on the round before and the round after.

You need to return the sum of the points you could get in all the rounds.

题目解析

相当于模拟了运算操作，+是相加，D是乘2，C是出栈，每次运算的结果需要记录在一个变量中，最后该变量。与我们熟悉的不同的是，除了C运算符以外，其他的操作都不把操作数出栈，每轮都要把运算结果入栈。

class Solution {
public:
   int calPoints(vector<string>& ops){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    stack<int> s;
    int ans = 0,op1=0,op2=0;
    for(int i=0;i<ops.size();i++){
        if(ops[i] == "C"){ //remove
            if(!s.empty()){
                ans -= s.top();
                s.pop();
            }
        }
        else if(ops[i] == "D"){
            if(!s.empty()){
                op1 = s.top();
                ans = ans + op1 * 2;
                s.push(op1*2);
            }
        }
        else if(ops[i] == "+"){
            if(!s.empty())
                op1 = s.top();
                s.pop();
            if(!s.empty())
                op2 = s.top();
            ans = ans + op1 + op2;
            s.push(op1);
            s.push(op1+op2);
        }
        else{
            s.push(atoi(ops[i].c_str()));
            ans += atoi(ops[i].c_str());
        }
    }
    while(!s.empty())
        s.pop();
    return ans;
}
};

496 Next Greater Element I

我的解法中没有用到栈，但是less than 100%的答案里用到了栈，题目的related topics也是stack，所以把它归到了栈里面。

题目描述

You are given two arrays (without duplicates) nums1 and nums2 where nums1’s elements are subset of nums2. Find all the next greater numbers for nums1’s elements in the corresponding places of nums2.

The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2. If it does not exist, output -1 for this number.

Example 1:

Input: nums1 = [4,1,2], nums2 = [1,3,4,2].
Output: [-1,3,-1]
Explanation:
    For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1.
    For number 1 in the first array, the next greater number for it in the second array is 3.
    For number 2 in the first array, there is no next greater number for it in the second array, so output -1.

题目解析

nums1是nums2的子集，在nums2中找到nums1中元素的greater number，greater number指的是nums2中这个元素右边第一个比它大的元素。我是用了两层循环，如果nums2[j]==num1[i]，flag=1，并进行下一次循环，开始找有没有比num1[i]大的元素。

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        ios::sync_with_stdio(0);
        cin.tie(0),cout.tie(0);
        vector<int> res(nums1.size(),-1);
        int i,j,flag = 0;
        for(int i=0;i<nums1.size();i++){
            for(int j=0;j<nums2.size();j++){
                if(nums2[j] == nums1[i]){
                    flag = 1;
                    continue;
                }
                if(flag){
                    if(nums2[j] > nums1[i]){
                        res[i] = nums2[j];
                        break;
                    }
                }
            }
            flag = 0;
        }
        return res;
    }
};

优化

使用栈的解法是先去寻找nums2所有元素的greater number，这里找的方法是维护一个栈，如果栈为空的话，压入nums2[i]，如果栈不为空，如果s.top() < nums2[i]，那么m[s.stop()] = nums2[i]，m是一个map容器，循环遍历栈里的元素，直至栈为空，再将nums2[i]压栈。开始我不理解为什么要循环遍历栈，因为循环尝试找栈里所有元素的greater number，而判断条件每次都是s.top() < nums2[i]，保证了栈里的元素不会彼此是greater number。

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        ios::sync_with_stdio(0);
        cin.tie(0),cout.tie(0);
        vector<int> res;
        map<int,int> m;
        stack<int> s;
        for(int i=0;i<nums2.size();i++){
            while(!s.empty() && s.top() < nums2[i]){
                m[s.top()] = nums2[i];
                s.pop();
            }
            s.push(nums2[i]);
        }
        for(int i=0;i<nums1.size();i++){
            if(m.count(nums1[i]))
                res.push_back(m[nums1[i]]);
            else
                res.push_back(-1);
        }
        
    return res;
    }
};