算法太差了，打算学习一下。leetcode一点点做，先从简单题开始，重点放在熟悉STL用法。

需要回看的题目：4 16 20

写完更新：记录了20题，虽然leetcode都标为简单题，但我感到难度差异很大。练手的目的应该是达到了，但记录起来效率比较低。以后只记录有必要回顾的题，每篇记录10题。

1 面试题58 - II. 左旋转字符串 难度：简单

我的土味解法：三次reverse

class Solution {
public:
    void reverse(string& s,int begin, int length){
        for(int i=0;i<length/2;i++){
            char temp=s[begin+i];
            s[begin+i]=s[begin+length-1-i];
            s[begin+length-1-i]=temp;
        }
    }
    string reverseLeftWords(string s, int n) {
        int l=s.length();
        reverse(s,0,l);
        reverse(s,0,l-n);
        reverse(s,l-n,n);
        return s;
    }
};

执行用时 :8 ms, 在所有 C++ 提交中击败了64.43% 的用户
内存消耗 :7.1 MB, 在所有 C++ 提交中击败了100.00%的用户

网友高级解法（作者：yzwz）

一行代码即可，把两个字符串拼起来，中间截取一部分

class Solution {
public:
    string reverseLeftWords(string s, int n) {
        return (s+s).substr(n,s.size());
    }
};

2 LCP 1. 猜数字 难度：简单

也太简单了，怎么跟平时在leetcode看到的简单题不一样。。

class Solution {
public:
    int game(vector<int>& guess, vector<int>& answer) {
        int count=0;
        for(int i=0;i<3;i++){
            if(guess[i]==answer[i]) count++;
        }
        return count;
    }
};

执行用时 :0 ms, 在所有 C++ 提交中击败了100.00% 的用户
内存消耗 :6.2 MB, 在所有 C++ 提交中击败了100.00%的用户

网友解法（作者：Lucky_dog）

一行异或。

class Solution {
public:
    int game(vector<int>& guess, vector<int>& answer) {
        return !(guess[0]^answer[0]) + !(guess[1]^answer[1]) + !(guess[2]^answer[2]);
    }
};

3 1342. 将数字变成 0 的操作次数 难度：简单

很简单。

class Solution {
public:
    int numberOfSteps (int num) {
        int count=0;
        while(num){
            if(num%2==0) num/=2;
            else num--;
            count++;
        }
        return count;
    }
};

执行用时 :0 ms, 在所有 C++ 提交中击败了100.00% 的用户
内存消耗 :6 MB, 在所有 C++ 提交中击败了100.00%的用户

4 1365. 有多少小于当前数字的数字 难度：简单

class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        vector<int> result;
        int length=nums.size();
        for(int i=0;i<length;i++){
            int count=0;
            for(int j=0;j<length;j++){
                if(nums[j]<nums[i]) count++;
            }
            result.push_back(count);
        }
        return result;
    }
};

执行用时 :52 ms, 在所有 C++ 提交中击败了13.57% 的用户
内存消耗 :7 MB, 在所有 C++ 提交中击败了100.00%的用户

网友解法（作者：huwt）

  • 学到了vector定义时可以用参数vector<int> num(nums.size(),0);跟数组差不多。
  • 我忽略了题目条件：所有数不大于100。遍历第一遍存放每个数出现次数；第二遍从小到大累加即可。
class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        int arr[101];
        memset(arr, 0, sizeof(arr));
        /* 初始化计数桶 */
        for (auto i : nums) {
            arr[i] ++;
        }
        /* 累加处理计数桶，使得 arr[i] 表示比 i 小的数字的个数 */
        int cnt = 0;
        for (int i = 0; i <= 100; i ++) {
            int temp = arr[i];
            arr[i] = cnt;
            cnt += temp;
        }
        vector<int> ret;
        /* 遍历 nums，取出对应桶 arr[i] 里的结果即可 */
        for (int i : nums) {
            ret.push_back(arr[i]);
        }
        return ret;
    }
};

改进我的解法

class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        vector<int> result;
        int a[102]={0};
        for(int i=0;i<nums.size();i++){
            a[nums[i]]++;
        }
        int count=0;
        for(int i=0;i<101;i++){
            int temp = a[i];
            a[i] = count;   /*严格小于*/
            count += temp;  /*把等于的加上*/
        }

        for(int i=0;i<nums.size();i++){
            result.push_back(a[nums[i]]);
        }
        
        return result;
    }
};

执行用时 :8 ms, 在所有 C++ 提交中击败了88.68% 的用户
内存消耗 :7.3 MB, 在所有 C++ 提交中击败了100.00%的用户

5 1281. 整数的各位积和之差 难度：简单

简单模拟

class Solution {
public:
    int subtractProductAndSum(int n) {
        int a=1,b=0;
        while(n){
            int t=n%10;
            a*=t;
            b+=t;
            n/=10;
        }
        return a-b;
    }
};

执行用时 :4 ms, 在所有 C++ 提交中击败了53.31% 的用户
内存消耗 :5.9 MB, 在所有 C++ 提交中击败了100.00%的用户

6 题目名称 难度：简单

依然是简单模拟，不用stl会快一点。
Dev C++编译to_string()出错，原因是不支持C++ 11的一些特性。需要设置环境。

class Solution {
public:
    int findNumbers(vector<int>& nums) {
        int count=0;
        string s;
        for(vector<int>::iterator it=nums.begin();it!=nums.end();it++){
            s = to_string(*it);
            if(s.size()%2==0){
                count++;
            }
        }
        return count;
    }
};

执行用时 :16 ms, 在所有 C++ 提交中击败了16.81% 的用户
内存消耗 :9.7 MB, 在所有 C++ 提交中击败了5.14%的用户

7 771. 宝石与石头 难度：简单

可以直接二重循环，也可以用stl。我用的hash。其实直接string.find(c)就可以。

class Solution {
public:
    int numJewelsInStones(string J, string S) {
        int count=0;
        bool hash[52]={0};
        for(int i=0;i<J.size();i++){
            if(J[i]>='A'&&J[i]<='Z') hash[J[i]-'A']=1;
            else if(J[i]>='a'&&J[i]<='z') hash[J[i]-'a'+26]=1;
        }
        for(int i=0;i<S.size();i++){
            if(S[i]>='A'&&S[i]<='Z'){
                if(hash[S[i]-'A']) count++;
            } 
            else if(S[i]>='a'&&S[i]<='z'){
                if(hash[S[i]-'a'+26]) count++;
            }
        }
        return count;
    }
};

执行用时 :4 ms, 在所有 C++ 提交中击败了76.45% 的用户
内存消耗 :6.3 MB, 在所有 C++ 提交中击败了100.00%的用户

网友解法（作者：jacder）

关于上面提到的各种容器，可以看看这篇解法。代码就不贴了。

8 1389. 按既定顺序创建目标数组 难度：简单

注意vector的insert()用法，第一个参数是迭代器，第二个参数是要存储的元素值。

class Solution {
public:
    vector<int> createTargetArray(vector<int>& nums, vector<int>& index) {
        vector<int> target;
        for(int i=0;i<nums.size();i++){
            target.insert(target.begin()+index[i], nums[i]);
        }
        return target;
    }
};

执行用时 :4 ms, 在所有 C++ 提交中击败了66.73% 的用户
内存消耗 :8.5 MB, 在所有 C++ 提交中击败了100.00%的用户

9 1108. IP 地址无效化 难度：简单

很简单

class Solution {
public:
    string defangIPaddr(string address) {
        string s;
        for(int i=0;i<address.size();i++){
            if(address[i]=='.') s+="[.]";
            else s+=address[i];
        }
        return s;
    }
};

执行用时 :0 ms, 在所有 C++ 提交中击败了100.00% 的用户
内存消耗 :6 MB, 在所有 C++ 提交中击败了100.00%的用户

10 1313. 解压缩编码列表 难度：简单

很简单

class Solution {
public:
    vector<int> decompressRLElist(vector<int>& nums){
        vector<int> vec;
        for(int i=1;i<nums.size();i+=2){
            for(int j=0;j<nums[i-1];j++) vec.push_back(nums[i]);
        }
        return vec;
    }
};

执行用时 :8 ms, 在所有 C++ 提交中击败了65.87% 的用户
内存消耗 :10.1 MB, 在所有 C++ 提交中击败了100.00%的用户

看了一下题解，可以使用vector的insert()函数，参数分别是：位置，个数，值

for(vector<int>::iterator iter = nums.begin(); iter != nums.end(); iter += 2) {
    vec.insert(vec.end(), *it, *(it + 1));
}

11 1266. 访问所有点的最小时间 难度：简单

数学题，我的想法是找到相差最大的维度即可。

class Solution {
public:
    int minTimeToVisitAllPoints(vector<vector<int>>& points) {
        int t=0;
        for(int i=0;i<points.size()-1;i++){
            int a=abs(points[i][0]-points[i+1][0]);
            int b=abs(points[i][1]-points[i+1][1]);
            int c=a>b?a:b;
            t+=c;
        }
        return t;
    }
};

执行用时 :8 ms, 在所有 C++ 提交中击败了89.64% 的用户
内存消耗 :9.6 MB, 在所有 C++ 提交中击败了100.00%的用户

12 1290. 二进制链表转整数 难度：简单

基本的链表操作题，进制转换题目往权值考虑。

class Solution {
public:
    int getDecimalValue(ListNode* head) {
        int sum=0;
        ListNode* p=head;
        while(p!=NULL){
            sum=sum*2+p->val;
            p=p->next;
        }
        return sum;
    }
};

执行用时 :4 ms, 在所有 C++ 提交中击败了68.52% 的用户
内存消耗 :8.1 MB, 在所有 C++ 提交中击败了100.00%的用户

13 237. 删除链表中的节点 难度：简单

阅读理解题。就给了一个参数，意思是不删除节点，而是换掉节点存储的数的值。

class Solution {
public:
    void deleteNode(ListNode* node) {
        node->val=node->next->val;
        node->next=node->next->next;
    }
};

执行用时 :20 ms, 在所有 C++ 提交中击败了11.62% 的用户
内存消耗 :7.8 MB, 在所有 C++ 提交中击败了100.00%的用户

14 面试题 02.03. 删除中间节点 难度：简单

跟上一题一样。这次把不要的节点删了。

class Solution {
public:
    void deleteNode(ListNode* node) {
        ListNode* x=node->next;
        node->val=x->val;
        node->next=x->next;
        delete x;
    }
};

执行用时 :28 ms, 在所有 C++ 提交中击败了11.97% 的用户
内存消耗 :7.8 MB, 在所有 C++ 提交中击败了100.00%的用户

15 面试题 02.02. 返回倒数第 k 个节点 难度：简单

双指针

class Solution {
public:
    int kthToLast(ListNode* head, int k) {
        ListNode* a=head;
        ListNode* b=head;
        for(int i=0;i<k-1;i++) a=a->next;
        while(a->next!=NULL){
            a=a->next;
            b=b->next;
        }
        return b->val;
    }
};

执行用时 :4 ms, 在所有 C++ 提交中击败了75.90% 的用户
内存消耗 :10.4 MB, 在所有 C++ 提交中击败了100.00%的用户

16 面试题55 - I. 二叉树的深度 难度：简单

最基本的二叉树操作，后序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == NULL) return 0;
        int lDepth = 1, rDepth = 1;
        lDepth += maxDepth(root->left);
        rDepth += maxDepth(root->right);
        return lDepth>rDepth?lDepth:rDepth;
    }
};

执行用时 :16 ms, 在所有 C++ 提交中击败了47.13% 的用户
内存消耗 :19 MB, 在所有 C++ 提交中击败了100.00%的用户

17 面试题17. 打印从1到最大的n位数 难度：简单

简单题

class Solution {
public:
    vector<int> printNumbers(int n) {
        vector<int> vec;
        int max = 0; 
        while(n--){
            max = max*10 + 9;
        }
        for(int i=1;i<=max;i++){
            vec.push_back(i);
        }
        return vec;
    }
};

执行用时 :4 ms, 在所有 C++ 提交中击败了98.14% 的用户
内存消耗 :11.4 MB, 在所有 C++ 提交中击败了100.00%的用户

18 709. 转换成小写字母 难度：简单

简单题

class Solution {
public:
    string toLowerCase(string str) {
        for(int i=0;i<str.length();i++){
            if(str[i]>='A'&&str[i]<='Z'){
                str[i] -= ('Z' - 'z');
            }
        }
        return str;
    }
};

执行用时 :0 ms, 在所有 C++ 提交中击败了100.00% 的用户
内存消耗 :6.3 MB, 在所有 C++ 提交中击败了100.00%的用户

19 1323. 6 和 9 组成的最大数字 难度：简单

题解里学到一个函数string s = to_string(num);

class Solution {
public:
    int maximum69Number (int num) {
        vector<int> a;
        while(num!=0){
            a.push_back(num%10);
            num /= 10;
        }
        for(int i=a.size()-1;i>=0;i--){
            if(a[i]==6){
                a[i]=9;
                break;
            }
        }
        int r=0;
        for(int i=a.size()-1;i>=0;i--){
            r = r*10 + a[i];
        }
        return r;
    }
};

执行用时 :0 ms, 在所有 C++ 提交中击败了100.00% 的用户
内存消耗 :6 MB, 在所有 C++ 提交中击败了100.00%的用户

20 1323. 6 和 9 组成的最大数字 难度：简单

没想出来好解法，还是笨办法模拟。

class Solution {
public:
    int oddCells(int n, int m, vector<vector<int>>& indices) {
        vector<vector<int>> a(n, vector<int> (m, 0));
        int count = 0;
        for(int i=0;i<indices.size();i++){
            for(int j=0;j<m;j++){
                a[indices[i][0]][j]++;
            }
            for(int j=0;j<n;j++){
                a[j][indices[i][1]]++;
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(a[i][j]%2==1) count++;
            }
        }
        return count;
    }
};

执行用时 :8 ms, 在所有 C++ 提交中击败了51.03% 的用户
内存消耗 :8.1 MB, 在所有 C++ 提交中击败了100.00%的用户

这篇题解写了几种思路 作者：zerotrac2