其他题目

9. 回文数

题目难度：简单 用时： 5 分钟 标记： 完成

class Solution {
public:
    bool isPalindrome(int x) {
        string s = to_string(x);
        for (int i = 0; i < s.size() /2; ++i) {
            if (s[i]!=s[s.size() -1 - i]) return false;
        }
        return true;
    }
};

14. 最长公共前缀

题目难度：简单 用时： 11 分钟 标记： 完成

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        for (int i = 0; i < strs[0].size(); ++i) {
            char ch = strs[0][i];
            for (int j = 0; j < strs.size(); ++j) {
                if (strs[j].size()<=i || strs[j][i] != ch) return strs[0].substr(0,i);
            }
        }
        return strs[0];
    }
};

21. 合并两个有序链表

题目难度：简单 用时： 20 分钟 标记： 完成

//方法一：链表
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* preHead = new ListNode(-1);
        ListNode* Header = preHead;
        while (list1 && list2)
        {
            if (list1->val > list2->val )
            {
                preHead->next = list2;
                list2 = list2->next;
            }
            else
            {
                preHead->next = list1;
                list1 = list1->next;
            }
            preHead = preHead->next;
        }
        if (!list1 && list2)preHead->next = list2;
        if (list1 && !list2)preHead->next = list1;
        return Header->next;
    }
};
//方法二：递归
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(!list1)return list2;
        if(!list2)return list1;
        if (list1->val > list2->val)
        {
            list2->next = mergeTwoLists(list1,  list2->next);
            return list2;
        }
        else
        {
            list1->next = mergeTwoLists(list1->next,  list2);
            return list1;
        }
    }
};

58. 最后一个单词的长度

题目难度：简单 用时： 10 分钟 标记： 完成

class Solution {
public:
    int lengthOfLastWord(string s) {
        while (s[s.size()-1]==' ')s.pop_back();
        return s.size() - s.rfind(' ') - 1;
    }
};

66. 加一

题目难度：简单 用时： 7 分钟 标记： 完成

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int po = 1 ;
        for (int i = digits.size() - 1; i >= 0; --i) {
            int re = digits[i] + po;
            digits[i] = re % 10;
            po = re / 10;
        }
        if (po) digits.insert(digits.begin(),1);
        return digits;
    }
};

67. 二进制求和

题目难度：简单 用时： 20分钟 标记： 完成

class Solution {
public:
    string addBinary(string a, string b) {
        a = a.size() < b.size() ? string(b.size() - a.size(),'0') + a: a;
        b = b.size() < a.size() ? string(-b.size() + a.size(),'0') + b : b;
        bool ji = 0;
        for (int i = a.size() - 1; i >= 0; --i) {
            int res = a[i] + b[i] + ji - '0' * 2;
            a[i] = '0' + res % 2;
            ji = res / 2;
        }
        if (ji) a = "1" + a;
        return a;
    }
};

83. 删除排序链表中的重复元素

题目难度：简单 用时： 5分钟 标记： 完成

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* header = head;
        while (head && head->next)
        {
            if (head->val == head->next->val)
            {
                head->next = head->next->next;
            } else{
                head = head->next;
            }
        }
        return header;
    }
};

88. 合并两个有序数组

题目难度：简单 用时： 11分钟 标记： 完成

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int p1 = 0,p2 = 0;
        nums1.resize(m+n);
        vector<int> res;
        while (p1 < m && p2 < n)
        {
            if (nums1[p1] > nums2[p2]) res.push_back(nums2[p2++]);
            else res.push_back(nums1[p1++]);
        }
        while (p1 == m && p2 != n) res.push_back(nums2[p2++]);
        while (p1 != m && p2 == n) res.push_back(nums1[p1++]);
        nums1.assign(res.begin(),res.end());
    }
};

面试经典 150 题

80. 删除有序数组中的重复项 II（未）

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size() <= 2) return nums.size();
        int index = 2;
        for(int i = 2; i < nums.size(); i++){
            if(nums[i] != nums[index-2])
                nums[index++] = nums[i];
        }
        return index;
    }
};

274. H 指数

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int count[1001] = {0};
        int maxs = 0;
        for(int i = 0; i < citations.size(); i++)
        {
            count[citations[i]]++;
            maxs = max(citations[i],maxs);
        }
        for(int i = 999; i >= 0; i--) 
        {
            count[i] += count[i + 1];
            if(count[i] >= i) return i;
        }
        return 0;
    }
};

73. 矩阵置零

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        unordered_set<int> col , row;
        for(int i = 0; i < matrix.size();i++)
        {
            for(int j = 0; j < matrix[0].size();j++)
            {
                if(matrix[i][j] == 0) 
                {
                    col.insert(i);
                    row.insert(j);
                }
            }
        }
        for(int i : col)
        {
            for(int j = 0; j < matrix[0].size();j++)
            {
                matrix[i][j] = 0;
            }
        }
        for(int i : row)
        {
            for(int j = 0; j < matrix.size();j++)
            {
                matrix[j][i] = 0;
            }
        }
    }
};

289. 生命游戏

class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        vector<vector<int>> res = board;
        function<int(int,int)> findpre = [&](int i , int j)->int{
            if(i < 0 || i >= res.size() || j < 0 || j >= res[0].size()) return 0;
            return res[i][j];
        };
        function<int(int,int)> findx = [&](int i , int j)->int{
            int resp = findpre(i + 1, j + 1) + findpre(i + 1, j) + findpre(i, j + 1) + findpre(i - 1, j + 1) + 
            findpre(i + 1, j - 1) + findpre(i - 1, j - 1) + findpre(i - 1, j ) + findpre(i , j - 1);
            return resp;
        };
        
        for(int i = 0; i < res.size();i++)
        {
            for(int j = 0; j < res[0].size();j++)
            {
                int x = findx(i,j);
                if(x < 2) board[i][j] = 0;
                else if(res[i][j] && (x == 2 || x == 3)) board[i][j] = 1;
                else if(res[i][j] && x > 3) board[i][j] = 0;
                else if(!res[i][j] && x == 3) board[i][j] = 1;
            }
        }
    }
};

290. 单词规律

class Solution {
public:
    bool wordPattern(string pattern, string s) {
        unordered_map<char,string> umap;
        unordered_map<string,char> umap_string;
        stringstream ss(s);
        string temp;
        int i = 0;
        while(getline(ss,temp,' '))
        {
            if(i >= pattern.size()) return false;
            if(umap.find(pattern[i]) == umap.end())umap[pattern[i]] = temp;
            else if(umap[pattern[i]] != temp) return false;
            i++;
        }
        for(auto x:umap)
        {
            umap_string[x.second] = x.first;
        }
        return i == pattern.size() && umap.size() == umap_string.size();
    }
};

228. 汇总区间

class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        if(nums.size() == 0) return {};
        if(nums.size() == 1) return {to_string(nums[0])};
        vector<string> res;
        int a = nums[0],b = nums[0];
        for(int i = 1; i < nums.size();i++)
        {
            if(b + 1 != nums[i])
            {
                if(a == b) res.push_back(to_string(b));
                else res.push_back(to_string(a)+"->"+to_string(b));
                a = nums[i];
            }
            b = nums[i];
        }
        if(a == b) res.push_back(to_string(b));
        else res.push_back(to_string(a)+"->"+to_string(b));
        return res;
    }
};

57. 插入区间

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        if(intervals.size() == 0) return {newInterval};
        int r = 0;
        while(r < intervals.size() && intervals[r][0] <= newInterval[0]) r++;
        intervals.insert(intervals.begin() + r,newInterval);
        vector<vector<int>> res;
        intervals.push_back({INT_MAX,INT_MAX});
        for(int i = 1; i < intervals.size(); i++)
        {
            if(intervals[i][0] > intervals[i - 1][1]) res.push_back({intervals[i - 1][0],intervals[i - 1][1]});
            else
            {
                intervals[i][0] = intervals[i - 1][0];
                intervals[i][1] = max(intervals[i][1],intervals[i - 1][1]);
            }
        }
        return res;
    }
};

71. 简化路径

class Solution {
public:
    string simplifyPath(string path) {
        stringstream ss(path);
        vector<string> res;
        string temp;
        while(getline(ss,temp,'/'))
        {
            if(temp == "." || temp == "") continue;
            if(res.size() > 0 && temp == "..")res.pop_back();
            if(temp != "..")res.push_back(temp);
        }
        string s = "/";
        for(auto x: res) s += x + '/';
        if(res.size() > 0) s.pop_back();
        return s;
    }
};