leetcode记录 (2)

leetcode刷题笔记

21 面试题13. 机器人的运动范围难度：中等

奇奇怪怪bug：先检验x和y是否越界，再检验visited[x][y]是否访问。否则会出现诡异的越界错误。

注意vector二维数组的定义和初始化写法。

dfs思想，多加练习。

class Solution {
public:
    int movingCount(int m, int n, int k) {
        vector<vector<int> > visited (m, vector<int> (n, 0));
        return dfs(0, 0, m, n, k, visited);
    }
    int dfs(int x, int y, int m, int n, int k, vector<vector<int> >& visited){
        if(x>=m || y>=n ||visited[x][y] == 1 ||  (x/10 + x%10 + y/10 + y%10) > k){
            return 0;
        }
        visited[x][y] = 1;
        return 1 + dfs(x+1, y, m, n, k, visited) + dfs(x, y+1, m, n, k, visited);
    }
};

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

22 151. 翻转字符串里的单词难度：中等

我的方法：vector存储string，先后面加个空格就不用最后特殊判断了，用bool控制忽略连续的空格。

因为库用的比较多，应该很费时。

class Solution {
public:
    string reverseWords(string s) {
        s+=' ';
        vector<string> vec;
        int t=0;
        bool space=false;
        string temp;
        while(t<s.size()){
            if(s[t]!=' '){
                temp+=s[t];
                space=true;
            }
            else if(s[t]==' '){
                if(space==true){
                    vec.push_back(temp);
                    temp.clear();
                    space=false;	
                }
            }
            t++;
        }
        string s1;
        for(int i=vec.size()-1;i>=0;i--){
            if(i!=0){
                s1+=vec[i];
                s1+=' ';
            }
            else{
                s1+=vec[i];
            }
        }
        return s1;
    }
};

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

23 445. 两数相加 II 难度：中等

用的栈存储两个链表，头插法建立新链表。

很多其他思路可以看看题解区，反转链表，转字符串，也有原地操作的，等等。

坑：判断循环结束时，两栈空但有进位，不能结束循环。

定义节点的时候别忘了用构造函数初始化一下。

/**
 * 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;
        while(l1!=NULL){
            s1.push(l1->val);
            l1=l1->next;
        }
        while(l2!=NULL){
            s2.push(l2->val);
            l2=l2->next;
        }
        int carry=0,sum=0;
        ListNode* head = new ListNode(0);
        while(!s1.empty() || !s2.empty() || carry!=0){
            int a = s1.empty()?0:s1.top();
            int b = s2.empty()?0:s2.top();
            sum = a + b + carry;
            ListNode* l = new ListNode(sum%10);
            carry=sum/10;

            l->next = head->next;
            head->next = l;
            
            if(!s1.empty()) s1.pop();
            if(!s2.empty()) s2.pop();        
        }
        return head->next;
    }
};

执行用时 :64 ms, 在所有 C++ 提交中击败了12.70% 的用户
内存消耗 :73.8 MB, 在所有 C++ 提交中击败了11.11%的用户

24 11. 盛最多水的容器难度：中等

一看题目就知道有好算法，然后怒模拟：

class Solution {
public:
    int maxArea(vector<int>& height) {
        int m_a = 0;
        int l = height.size();
        for(int i=0;i<l-1;i++){
            for(int j=i+1;j<l;j++){
                int area = (j-i)*min(height[i], height[j]);
                m_a = area>m_a?area:m_a;
            }
        }
        return m_a;
    }
};

果然超出时间限制了！^ ^

根据题解，使用双指针：

class Solution {
public:
    int maxArea(vector<int>& height) {
        int max = 0;
        int head = 0, rear = height.size()-1;
        while(head<rear){
            int area = (rear - head) * min(height[head], height[rear]);
            if(area>max) max=area;

            if(height[head]>height[rear]) rear--;
            else head++;
        }
        return max;
    }
};

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

做到现在，99%的题依然感觉毫无思路，只能模拟。算法能力到底是见得太多–>看什么都熟悉–>立刻就知道往哪方面想，还是能凭空想出来好的解法？我暂且蒙在鼓里

25 206. 反转链表难度：中等

反转链表，双指针。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *p = head, *q = NULL;
        while(p!=NULL){
            ListNode* temp = p->next;
            p->next = q;
            q = p;
            p = temp;
        }
        return q;
    }
};

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

26 200. 岛屿数量难度：中等

我的代码很不优雅，dfs不够熟练。而且我的函数参数太多了注意一下网友的简洁解法。

有一个小坑：输入是空[]时要单独处理。

class Solution {
public:
    
    void search(int i, int j, vector<vector<char>>& grid){
        grid[i][j]='0';
        if(i<(grid.size()-1) && grid[i+1][j]=='1') search(i+1,j,grid);
        if(j<(grid[0].size()-1) && grid[i][j+1]=='1') search(i,j+1,grid);
        if(i>0 && grid[i-1][j]=='1') search(i-1,j,grid);
        if(j>0 && grid[i][j-1]=='1') search(i,j-1,grid);
    }
    int numIslands(vector<vector<char>>& grid) {
        if(grid.empty()) return 0;
        
        int num = 0;
        for(int i=0;i<grid.size();i++){
            for(int j=0;j<grid[0].size();j++){
                    if(grid[i][j] == '1'){
                        num++;
                        search(i,j,grid);
                    }    /* 是陆地 */ 
                
            }
        }
        return num;
    }
};

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

27 7. 整数反转难度：简单

这是道简单题，记录一下INT_MAX和INT_MIN的用法。

class Solution {
public:
    int reverse(int x) {
        int y=0;
        while(x){
            if(y>INT_MAX/10 || y<INT_MIN/10){
                return 0;
            }
            int t = x%10;
            y = y*10 + t;
            x /= 10;
        }
        return y;

    }
};

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

28 13. 罗马数字转整数难度：简单

也是简单题，复习map的用法。map赋值不用函数。

class Solution {
public:
    int romanToInt(string s) {
        unordered_map<char, int> mp;
        mp['I'] = 1;
        mp['V'] = 5;
        mp['X'] = 10;
        mp['L'] = 50;
        mp['C'] = 100;
        mp['D'] = 500;
        mp['M'] = 1000;

        int sum = 0;
        for(int i=0;i<s.size();i++){
            if(mp[s[i]] < mp[s[i+1]]){
                sum -= mp[s[i]];
            }
            else {
                sum += mp[s[i]];
            }
        }
        return sum;
    }
};

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

29 13. 罗马数字转整数难度：简单

跟本篇中的第23 是同一题，这次没用栈，用的直接操作链表，头插法。两种对比着看。

/**
 * 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) {
        ListNode* head = new ListNode(0);
        ListNode* r = head;
        int index = 0;
        while(l1!=NULL || l2!=NULL || index!=0){
            int sum = 0;
            if(l1){
                sum+=l1->val;
            }
            if(l2){
                sum+=l2->val;
            }
            sum+=index;
            ListNode* temp = new ListNode(sum%10);
            index = sum/10;
            head->next = temp;
            head = temp;
            if(l1){
                l1 = l1->next;
            }
            if(l2){
                l2 = l2->next;
            }  
        }
        return r->next;
    }
};

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

30 3. 无重复字符的最长子串难度：中等

滑动窗口经典题，本想用map记录位置，后面还是改成用set只记录值，然后设一个left指针记录起始位置。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> st;
        int maxlen = 0;
        int left = 0, i;
        for(i=0;i<s.size();i++){
            if(st.find(s[i]) == st.end()){
                st.insert(s[i]);
            }
            else{
                maxlen = max(maxlen, i - left);
                while(s[left] != s[i]){
                    st.erase(s[left]);
                    left++;
                }
                left++;
            }
        }
        maxlen = max(maxlen, i-left);
        return maxlen;
    }
};

执行用时 :40 ms, 在所有 C++ 提交中击败了36.23% 的用户
内存消耗 :9.2 MB, 在所有 C++ 提交中击败了78.89%的用户

21 面试题13. 机器人的运动范围 难度：中等

22 151. 翻转字符串里的单词 难度：中等

23 445. 两数相加 II 难度：中等

24 11. 盛最多水的容器 难度：中等

25 206. 反转链表 难度：中等

26 200. 岛屿数量 难度：中等

27 7. 整数反转 难度：简单

28 13. 罗马数字转整数 难度：简单

29 13. 罗马数字转整数 难度：简单

30 3. 无重复字符的最长子串 难度：中等