Leetcode

1.两数之和(Two Sum)

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int>res;//用来存储结果的vector
        std::map<int ,int>mp;//hash表
        for(int i = 0; i <= nums.size() ;i++){
            map<int , int>::iterator iter;
            iter = mp.find(target - nums[i]);
            if(iter != mp.end()){//如果在hash表中找到了target-nums[i]
                res.push_back(mp[target-nums[i]]);
                res.push_back(i);
                return res;
            }
            else{//否则将该数插入hash表
                mp.insert(pair<int , int>(nums[i] , i));
            }
        }
        return res;
    }
};

9. 回文数(Palindrome Number)

class Solution {
public:
    bool isPalindrome(int x) {
        if(x < 0){//负数肯定不是回文数
            return false;
        }
        int sizex = 0;//记录数字位数
        int num = x;
        while(num){
            num = num/10;
            sizex++;
        }
        for(int i = 0; i < sizex/2 ; i++){//只用分析数字的一半即可
            if(((int)(x / pow(10 , sizex - i - 1))%10) != ((int)(x / pow(10 , i)) % 10)){
                return false;
            }
        }
        return true;
    }
};

13. 罗马数字转整数(Roman to Integer)

class Solution {
public:
    int romanToInt(string s) {
        int res = 0;//结果
        for(int i = 0; i < s.size() ;i++){
            if(i+1 != s.size()){//不是最后一位
                if(s[i] == 'I' && s[i+1] == 'V'){//先判断特殊情况
                    res = res + 4;
                    i++;
                }
                else if(s[i] == 'I' && s[i+1] == 'X'){
                    res = res + 9;
                    i++;
                }
                else if(s[i] == 'X' && s[i+1] == 'L'){
                    res = res + 40;
                    i++;
                }
                else if(s[i] == 'X' && s[i+1] == 'C'){
                    res = res + 90;
                    i++;
                }
                else if(s[i] == 'C' && s[i+1] == 'D'){
                    res = res + 400;
                    i++;
                }
                else if(s[i] == 'C' && s[i+1] == 'M'){
                    res = res + 900;
                    i++;
                }
                else{
                    if(s[i] == 'I'){
                        res = res + 1;
                    }
                    else if(s[i] == 'V'){
                        res = res + 5;
                    }
                    else if(s[i] == 'X'){
                        res = res + 10;
                    }
                    else if(s[i] == 'L'){
                        res = res + 50;
                    }
                    else if(s[i] == 'C'){
                        res = res + 100;
                    }
                    else if(s[i] == 'D'){
                        res = res + 500;
                    }
                    else if(s[i] == 'M'){
                        res = res + 1000;
                    }
                }
            }
            else{//是最后一位的情况
                if(s[i] == 'I'){
                    res = res + 1;
                }
                else if(s[i] == 'V'){
                    res = res + 5;
                }
                else if(s[i] == 'X'){
                    res = res + 10;
                }
                else if(s[i] == 'L'){
                    res = res + 50;
                }
                else if(s[i] == 'C'){
                    res = res + 100;
                }
                else if(s[i] == 'D'){
                    res = res + 500;
                }
                else if(s[i] == 'M'){
                    res = res + 1000;
                }
            }
        }
        return res;
    }
};

14. 最长公共前缀(Longest Common Prefix)

class Solution {
public:
    string longestCommonPrefix(string s1 , string s2){
        string res = "";
        int sizeS = min(s1.size() , s2.size());
        for(int i = 0; i < sizeS ;i++){
            if(s1[i] == s2[i]){
                res = res + s1[i];
            }
            else{
                break;
            }
        }
        return res;
    }

    string longestCommonPrefix(vector<string>& strs) {
        if(strs.size() == 0){
            return "";
        }
        else if(strs.size() == 1){
            return strs[0];
        }
        else if(strs.size() == 2){
            return longestCommonPrefix(strs[0] , strs[1]);
        }
        string res = longestCommonPrefix(strs[0] , strs[1]);
        for(int i = 2; i < strs.size() ;i++){
            res = longestCommonPrefix(strs[i] , res);
        }
        return res;
    }
};

20. 有效的括号(Valid Parentheses)

class Solution {
public:
    bool isValid(string s) {
        std::stack<char>st;
        for(int i = 0; i < s.length() ;i++){
            if(!st.empty()){
                if(s[i] == ')' && st.top() == '('){
                    st.pop();
                }
                else if(s[i] == ']' && st.top() == '['){
                    st.pop();
                }
                else if(s[i] == '}' && st.top() == '{'){
                    st.pop();
                }
                else{
                    st.push(s[i]);
                }
            }
            else{
                st.push(s[i]);
            }
        }
        if(st.empty()){
            return true;
        }
        else{
            return false;
        }
    }
};

21. 合并两个有序链表(Merge Two Sorted Lists)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list1 == NULL){
            return list2;
        }
        if(list2 == NULL){
            return list1;
        }
        ListNode* resList = new ListNode;
        ListNode* result = resList;
        resList->next = NULL;
        if(list1->val >= list2->val){
            result->val = list2->val;
            list2 = list2->next;
        }
        else{
            result->val = list1->val;
            list1 = list1->next;
        }
        while(list1 != NULL && list2 != NULL){
            ListNode *list = new ListNode;
            list->next = NULL;
            if(list1->val >= list2->val){
                list->val = list2->val;
                resList->next = list;
                resList = resList->next;
                list2 = list2->next;
            }
            else{
                list->val = list1->val;
                resList->next = list;
                resList = resList->next;
                list1 = list1->next;
            }
        }
        
        if(list1 == NULL){
            while(list2 != NULL){
                ListNode *list = new ListNode;
                list->next = NULL;
                list->val = list2->val;
                resList->next = list;
                resList = resList->next;
                list2 = list2->next;
            }
        }
        else if(list2 == NULL){
            while(list1 != NULL){
                ListNode *list = new ListNode;
                list->next = NULL;
                list->val = list1->val;
                resList->next = list;
                resList = resList->next;
                list1 = list1->next;
            }
        }
        return result;
    }
};

26.删除有序数组中的重复项(Remove Duplicates from Sorted Array)

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size() == 0){
            return 0;
        }
        else if(nums.size() == 1){
            return 1;
        }
        int flag = 0;
        int tmp = nums[0];//tmp记录前一个数
        for(int i = 1; i < nums.size() ;i++){
            if(nums[i] != tmp){//如果数字不同,放到第flag的位置
                flag++;
                tmp = nums[i];
                nums[flag] = nums[i];
            }
            else{//如果数字相同,什么都不做

            }
        }
        return flag+1;
    }
};

27.移除元素(Remove Element)

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int count = 0;//计数器,记录值等于val的数
        int flag = 0;//记录目前访问到了哪儿
        for(int i = 0; i < nums.size() ;i++){
            if(nums[i] == val){
                count++;
            }
            else{
                nums[flag] = nums[i];
                flag++;
            }
        }
        return nums.size() - count;
    }
};

28.实现strStr()(Implement strStr())

class Solution {
public:
    void getNext(int* next, const string& s) {
        int j = 0;
        next[0] = 0;
        for(int i = 1; i < s.size(); i++) {
            while (j > 0 && s[i] != s[j]) {
                j = next[j - 1];
            }
            if (s[i] == s[j]) {
                j++;
            }
            next[i] = j;
        }
    }
    int strStr(string haystack, string needle) {
        if (needle.size() == 0) {
            return 0;
        }
        int next[needle.size()];
        getNext(next, needle);
        int j = 0;
        for (int i = 0; i < haystack.size(); i++) {
            while(j > 0 && haystack[i] != needle[j]) {
                j = next[j - 1];
            }
            if (haystack[i] == needle[j]) {
                j++;
            }
            if (j == needle.size() ) {
                return (i - needle.size() + 1);
            }
        }
        return -1;
    }
};

35.搜索插入位置(Search Insert Position)

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        if(nums.size() == 0){
            return 0;
        }
        else if(nums.size() == 1){
            if(target > nums[0]){
                return 1;
            }
            else return 0;
        }
        else{//二分查找找到大概位置
            int right = nums.size();
            int left = 0;
            int mid = (right + left)/2;
            while(left < right && left != mid && right != mid){
                if(nums[mid] < target){
                    left = mid;
                    mid = (left + right)/2;
                }
                else{
                    right = mid;
                    mid = (left + right)/2;
                }
            }
            //对位置进行修正
            if(nums[mid] >= target){
                return mid;
            }
            else{
                return mid + 1;
            }
        }
    }
};

53.最大子数组和(Maximum Subarray)

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        //(1)不全为负数的情况下
        //要得到最大子数组和,第一个数必是正数
        //sum需要一直保持为正数
        //(2)全为负数的情况下,选最小的负数
        int sum = 0;
        int maxSum = nums[0];//nums中最大的和
        int maxOfNums = nums[0];//nums中最大的数
        for(int i = 0; i < nums.size() ;i++){
            if(nums[i] > maxOfNums){
                maxOfNums = nums[i];
            }
            sum = sum + nums[i];
            if(sum >= 0){
                if(sum > maxSum){
                    maxSum = sum;
                }
            }
            else{
                sum = 0;
            }
        }
        if(maxOfNums < 0){//如果最大的数都小于0的情况下说明该数组中所有数字都小于0
            return maxOfNums;
        }
        return maxSum;
    }
};

58.最后一个单词的长度(Length of Last Word)

class Solution {
public:
    int lengthOfLastWord(string s) {
        //将字符串翻转,读第一个单词的长度即可
        reverse(s.begin() , s.end());
        bool start = false;
        int count = 0;
        for(int i = 0; i < s.length() ;i++){
            if(s[i] != ' '){
                start = true;
                count++;
            }
            else{
                if(start){
                    break;
                }
            }
        }
        return count;
    }
};

66.加一(Plus One)

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int i = digits.size()-1;
        bool carry = true;//进位
        while(carry && i >= 0)
        if(digits[i]!=9){
            digits[i]++;
            carry = false;
        }
        else{
            digits[i] = 0;
            i--;
            carry = true;
        }
        if(i == -1 && carry){
            digits.push_back(0);
            digits[0] = 1;
        }
        return digits;
    }
};

67.二进制求和(Add Binary)

class Solution {
public:
    string addBinary(string a, string b) {
        int lengthOfA = a.length();
        int lengthOfB = b.length();
        int length = max(lengthOfA , lengthOfB);
        string result = "";
        int carry = 0;//进位标志位
        if(lengthOfA > lengthOfB){//a的长度大于或等于b
            //将b前面补0
            for(int i = 0; i < lengthOfA - lengthOfB ;i++){
                b = "0" + b;
            }
        }
        else if(lengthOfA == lengthOfB){//a的长度等于b
            //什么都不做

        }
        else{//a的长度小于b
            //将a前面补0
            for(int i = 0; i < lengthOfB - lengthOfA ;i++){
                a = "0" + a;
            }
        }
        for(int i = 0; i < length ;i++){
            int add = carry + (a[length - 1 - i] - '0') + (b[length - 1 - i] - '0');
            if(add % 2  == 0){
                result = "0" + result;
            }
            else if(add % 2 == 1){
                result = "1" + result;
            }
            if(add >= 2){
                carry = 1;
            }
            else if(add == 0 || add == 1){
                carry = 0;
            }
        }
        //全部计算完后如果还有进位
        if(carry == 1){
            result = "1" + result;
        }
        return result;
    }
};

69.Sqrt(x)

class Solution {
public:
    int mySqrt(int x) {
        //数据x的范围为0到2^31 - 1,显然需要使用二分法
        //返回值的范围为0到2^16(可以取到0,取不到2^16)
        unsigned int right = 1<<16;//1左移16位,就是2^16
        unsigned int left = 0;
        unsigned int mid = (right + left)/2;
        while(! (mid * mid <= x && (mid+1)*(mid+1) > x )){
            if( mid * mid > x){
                right = mid;
                mid = (left + right)/2;
            }
            else if( mid * mid <= x){
                left = mid;
                mid = (left + right)/2;
            }
            if(left + 1 == right){
                break;
            }
        }
        cout<<mid<<endl;
        //修正数值
        if(mid * mid < x && ((mid+1) * (mid + 1)) >= x){
            return mid;
        }
        else if(((mid+1)*(mid+1)) <= x){
            return mid + 1;
        }
        else if(mid * mid > x){
            return mid - 1;
        }
        return mid;
    }
};

70.爬楼梯(Climbing Stairs)

class Solution {
public:
    int climbStairs(int n) {
        if(n == 1){
            return 1;
        }
        else if(n == 2){
            return 2;
        }
        else{
            int a = 1;
            int b = 2;
            int c = 0;
            for(int i = 0; i < n-2 ;i++){
                c = a + b;
                a = b;
                b = c;
            }
            return c;
        }
    }
};

83.删除排序链表中的重复元素(Remove Duplicates from Sorted List)

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

88.合并两个有序数组(Merge Sorted Array)

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        if( n == 0 ){
            return;
        }
        vector<int>tmp(m+n);
        int flag1 = 0;
        int flag2 = 0;
        int count = 0;
        while(flag1 < m && flag2 < n){
            if(nums1[flag1] < nums2[flag2]){
                tmp[count] = nums1[flag1];
                count++;
                flag1++;
            }
            else{
                tmp[count] = nums2[flag2];
                count++;
                flag2++;
            }
        }
        if(flag1 == m){
            while(count < m+n ){
                tmp[count] = nums2[flag2];
                count++;
                flag2++;
            }
        }
        else if(flag2 == n){
            while(count < m+n ){
                tmp[count] = nums1[flag1];
                count++;
                flag1++;
            }
        }
        for(int i =0; i < m+n ;i++){
            nums1[i] = tmp[i];
        }
    }
};

94.二叉树的中序遍历(Binary Tree Inorder Traversal)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int>result;

    //中序遍历
    void midOrderTraversal(TreeNode* root) {
        if(root->left != NULL){
            midOrderTraversal(root->left);
        }
        result.push_back(root->val);
        if(root->right != NULL){
            midOrderTraversal(root->right);
        }
    }
    vector<int> inorderTraversal(TreeNode* root) {
        if(root == NULL){
            return result;
        }
        midOrderTraversal(root);
        return result;
    }
};

100.相同的树(Same Tree)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void traversal(TreeNode *p , TreeNode *q , bool &isSame){
        if(p == NULL && q== NULL){
            return;
        }
        else if(p == NULL && q != NULL){
            isSame = false;
            return;
        }
        else if(p != NULL && q == NULL){
            isSame = false;
            return;
        }
        if(p->val != q->val){
            isSame = false;
        }
        
        traversal(p->left , q->left , isSame);
        traversal(p->right , q->right , isSame);
    }

    bool isSameTree(TreeNode* p, TreeNode* q) {
        bool isSame = true;
        traversal(p , q , isSame);
        return isSame;
    }
};

101.对称二叉树(Symmetric Tree)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void traversal(TreeNode *p , TreeNode *q , bool &isSymmetric){
        if(p == NULL && q== NULL){
            return;
        }
        else if(p == NULL && q != NULL){
            isSymmetric = false;
            return;
        }
        else if(p != NULL && q == NULL){
            isSymmetric = false;
            return;
        }
        if(p->val != q->val){
            isSymmetric = false;
        }
        
        traversal(p->left , q->right , isSymmetric);
        traversal(p->right , q->left , isSymmetric);
    }
    bool isSymmetric(TreeNode* root) {
        if(root == NULL){
            return true;
        }
        bool result = true;
        traversal(root->left , root->right , result);
        return result;
    }
};

104.二叉树的最大深度(Maximum Depth of Binary Tree)

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

    int maxDepth(TreeNode* root) {
        traversal(root , 1);
        return maxDepthNum;
    }
};

108.将有序数组转换为二叉搜索树(Convert Sorted Array to Binary Search Tree)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode * buildBST(vector<int>& nums , int left , int right){
        if(left > right){
            return nullptr;
        }
        int mid = (left + right)/2;
        TreeNode *root = new TreeNode(nums[mid]);
        root->left = buildBST(nums , left , mid - 1);
        root->right = buildBST(nums , mid + 1 , right);
        return root;
    }

    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return buildBST(nums , 0 , nums.size()-1);
    }
};

110.平衡二叉树(Balanced Binary Tree)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    //判断每一个结点的左子树最大深度和右子树最大深度是否相差1
    int maxDepthNum = 0;
    void traversal(TreeNode* root , int depth){
        if(root == NULL){
            return;
        }
        if(depth > maxDepthNum){
            maxDepthNum = depth;
        }
        traversal(root->left , depth + 1);
        traversal(root->right , depth + 1);
    }

    int maxDepth(TreeNode* root) {
        maxDepthNum = 0;
        traversal(root , 1);
        return maxDepthNum;
    }

    void isBalanced(TreeNode * root , bool &result){
        if(root == NULL){
            return;
        }
        int leftDepth = maxDepth(root->left);
        int rightDepth = maxDepth(root->right);
        cout<<leftDepth<<" "<<rightDepth<<endl;
        if(abs(leftDepth - rightDepth) > 1){
            result = false;
            return;
        }
        isBalanced(root->left , result);
        isBalanced(root->right , result);
    }

    bool isBalanced(TreeNode* root) {
        bool result = true;
        isBalanced(root , result);
        return result;
    }
};

111.二叉树的最小深度(Minimum Depth of Binary Tree)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int minDepthNum = 0;

    void tranversal(TreeNode* root , int depth){
        if(root == NULL){
            return;
        }
        if(root->left == NULL && root->right == NULL){
            if(minDepthNum > depth){
                minDepthNum = depth;
                return;
            }
        }

        tranversal(root->left , depth + 1);
        tranversal(root->right , depth + 1);
    }

    int minDepth(TreeNode* root) {
        if(root == NULL){
            return 0;
        }
        minDepthNum = INT_MAX;
        tranversal(root , 1);
        return minDepthNum;
    }
};

112.路径总和(Path Sum)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isPathSumExist = false;
    void DFS(TreeNode * root , int sum , int targetSum ){
        if(root == NULL){
            return;
        }
        sum = sum + root->val;
        if(root->left == NULL && root->right == NULL){
            if(sum == targetSum){
                isPathSumExist = true;
            }
        }
        DFS(root->left , sum , targetSum);
        DFS(root->right , sum , targetSum);
    }

    bool hasPathSum(TreeNode* root, int targetSum) {
        isPathSumExist = false;
        DFS(root , 0 , targetSum);
        return isPathSumExist;
    }
};

118.杨辉三角(Pascal’s Triangle)

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>>result;
        for(int i = 0; i < numRows ;i++){
            vector<int>tmp(i+1);
            if(i == 0){
                tmp[0] = 1;
                result.push_back(tmp);
            }
            else{
                tmp[0] = 1;
                tmp[i] = 1;
                if(i > 1){
                    for(int j = 1 ; j < i ; j++){
                        tmp[j] = result[i-1][j-1] + result[i-1][j];
                    }
                }
                result.push_back(tmp);
            }
        }
        return result;
    }
};

119.杨辉三角 II(Pascal’s Triangle II)

class Solution {
public:
    vector<int> generate(int numRows) {
        vector<vector<int>>result;
        for(int i = 0; i < numRows+1 ;i++){
            vector<int>tmp(i+1);
            if(i == 0){
                tmp[0] = 1;
                result.push_back(tmp);
            }
            else{
                tmp[0] = 1;
                tmp[i] = 1;
                if(i > 1){
                    for(int j = 1 ; j < i ; j++){
                        tmp[j] = result[i-1][j-1] + result[i-1][j];
                    }
                }
                result.push_back(tmp);
            }
        }
        return result[numRows];
    }

    vector<int> getRow(int rowIndex) {
        return generate(rowIndex);
    }
};

121.买卖股票的最佳时机(Best Time to Buy and Sell Stock)

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //记录截止到每天的股价最小值,然后每天求出最大的差即可
        if(prices.size() <= 1){
            return 0;
        }
        int minPrice = prices[0];//截止到今日的最小股价
        int maxProfit = 0;//最大利润
        for(int i = 1; i < prices.size() ;i++){
            if(prices[i] < minPrice){
                minPrice = prices[i];
                //更新最小股价这天肯定不可能得到最大利润
            }
            else if(prices[i] - minPrice > maxProfit){
                maxProfit = prices[i] - minPrice;
            }
        }
        return maxProfit;
    }
};

125.验证回文串(Valid Palindrome)

class Solution {
public:
    bool isPalindrome(string s) {
        if(s.length() <= 1){
            //空字符串和只有一个字符的字符串一定是回文串
            return true;
        }
        //需要忽略大小写,所以先把所有大写转换为小写
        for(int i = 0; i < s.length() ;i++){
            if(s[i] >= 'A' && s[i] <= 'Z'){
                s[i] = s[i] - 'A' + 'a';
            }
        }
        //然后使用双指针法,一个从前往后,一个从后往前,同时只考虑字母和数字
        int left = 0;
        int right = s.length()-1;
        while(right > left){
            while(!(((s[left] >= '0') && (s[left] <= '9')) || ((s[left] >= 'a') && (s[left] <= 'z')))){
                left++;
                if(left > right){
                    return true;
                }
            }
            while(!(((s[right] >= '0') && (s[right] <= '9')) || ((s[right] >= 'a') && (s[right] <= 'z')))){
                right--;
                if(left > right){
                    return true;
                }
            }
            if(s[left] != s[right]){
                return false;
            }
            else{
                left++;
                right--;
            }
        }
        return true;
    }
};

136.只出现一次的数字(Single Number)

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        //将所有数字进行异或,偶数次的数会被抵消,由于该题所有数字只出现1次或2次,所以将所有数进行异或运算即可
        for(int i = 1; i < nums.size() ;i++){
            nums[0] = nums[0] ^ nums[i];
        }
        return nums[0];
    }
};

141.环形链表(Linked List Cycle)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        //定义两个指针指向头指针,然后两个指针不同的步伐向后遍历,若两个指针指向同一个结点时表示存在环
        //,若步伐大的那个指针指向NULL时表示不存在环
        ListNode *p = head;
        ListNode *q = head;
        while(p != NULL){
            p = p->next;
            if(p == NULL){
                return false;
            }
            p = p->next;
            if(p == NULL){
                return false;
            }
            q = q->next;
            if(p == q){
                return true;
            }
        }
        return false;
    }
};

144.二叉树的前序遍历(Binary Tree Preorder Traversal)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void traversal(TreeNode * root , vector<int>&nums){
        if(root == NULL){
            return;
        }
        nums.push_back(root->val);
        traversal(root->left , nums);
        traversal(root->right , nums);
    }

    vector<int> preorderTraversal(TreeNode* root) {
        vector<int>result;
        traversal(root , result);
        return result;
    }
};

145.二叉树的后序遍历(Binary Tree Postorder Traversal)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void traversal(TreeNode * root , vector<int>&nums){
        if(root == NULL){
            return;
        }
        traversal(root->left , nums);
        traversal(root->right , nums);
        nums.push_back(root->val);
    }

    vector<int> postorderTraversal(TreeNode* root) {
        vector<int>result;
        traversal(root , result);
        return result;
    }
};

155.最小栈(Min Stack)

class MinStack {
private:
    int minNum;
    vector<int>nums;
    int flag;//flag指向栈中最后一个数
public:
    MinStack() {
        flag = -1;
        minNum = INT_MAX;
    }
    
    void push(int val) {
        if(val < minNum){
            minNum = val;
        }
        if(flag == nums.size()-1){
            nums.push_back(val);
            flag++;
        }
        else{
            flag++;
            nums[flag] = val;
        }
    }
    
    void pop() {
        if(nums[flag] == minNum){
            minNum = nums[0];
            for(int i = 1; i < flag ;i++){
                if(nums[i] < minNum){
                    minNum = nums[i];
                }
            }
        }
        flag--;
        if(flag == -1){
            minNum = INT_MAX;
        }
    }
    
    int top() {
        return nums[flag];
    }
    
    int getMin() {
        return minNum;
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

160.相交链表(Intersection of Two Linked Lists)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(headA == NULL || headB == NULL){
            return NULL;
        }
        ListNode * rootA = headA;
        ListNode * rootB = headB;
        int lengthRootA = 0;
        int lengthRootB = 0;
        //先把A和B链表的长度测出来
        while(rootA){
            lengthRootA++;
            rootA = rootA->next;
        }
        while(rootB){
            lengthRootB++;
            rootB = rootB->next;
        }
        if(lengthRootA > lengthRootB){
            //链表A比链表B长
            for(int i = 0; i < lengthRootA - lengthRootB ;i++){
                //A先走相差的步数
                headA = headA->next;
            }
            while(headA != NULL || headB != NULL){
                if(headA == headB){
                    return headA;
                }
                else{
                    headA = headA->next;
                    headB = headB->next;
                }
            }
        }
        else{
            //链表B长度大于或等于A
            for(int i = 0; i < lengthRootB - lengthRootA ;i++){
                //B先走相差的步数
                headB = headB->next;
            }
            while(headA != NULL || headB != NULL){
                if(headA == headB){
                    return headA;
                }
                else{
                    headA = headA->next;
                    headB = headB->next;
                }
            }
        }
        return NULL;
    }
};

167.两数之和 II – 输入有序数组(Two Sum II – Input Array Is Sorted)

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        //将nums中的数全部初始化为-1
        vector<int>nums(4000 , -1);
        vector<int>result;
        //-1000存到1000中,0存到2000中,1000存到3000中
        for(int i = 0; i < numbers.size() ;i++){
            //判断target - number[i]是否存在
            if(nums[target - numbers[i]+2000] != -1){
                //若存在
                result.push_back(nums[target - numbers[i] + 2000]+1);
                result.push_back(i+1);
                break;
            }
            else{
                //若不存在
                nums[numbers[i] + 2000] = i;
            }
        }
        return result;
    }
};

168.Excel表列名称(Excel Sheet Column Title)

class Solution {
public:
    string convertToTitle(int columnNumber) {
        string result = "";
        //本质就是一个26进制转换
        while(columnNumber != 0){
            columnNumber = columnNumber - 1;
            result =  (char)((columnNumber % 26) + 'A') + result;
            columnNumber = columnNumber / 26;
        }
        return result;
    }
};

169.多数元素(Majority Element)

class Solution {
public:
//结果一定是数量大于一半的数,将每两个不同的数相互抵消,最后剩下的数就是要求的数
    int majorityElement(vector<int>& nums) {
        if(nums.size() == 1){
            return nums[0];
        }
        int result = nums[0];
        int resultCount = 1;
        for(int i = 1; i < nums.size() ;i++){
            if(resultCount == 0){
                result = nums[i];
                resultCount = 1;
                continue;
            }
            else if(nums[i] != result){
                resultCount--;
            }
            else if(nums[i] == result){
                resultCount++;
            }
        }
        return result;
    }
};

171.Excel 表列序号(Excel Sheet Column Number)

class Solution {
public:
    int titleToNumber(string columnTitle) {
        long int result = 0;
        long int base = 1;
        //本质就是一个26进制转换
        for(int i = columnTitle.size()-1 ; i >= 0 ; i--){
            result = result + (columnTitle[i] - 'A' + 1) * base;
            base = base * 26;
        }
        return result;
    }
};

190.颠倒二进制位(Reverse Bits)

class Solution {
public:
    //多次调用这个函数的时候将pow(2,0)~pow(2,31)全部事先计算出来并保存
    uint32_t reverseBits(uint32_t n) {
        uint32_t result = 0;
        int bit = 31;
        while(n != 0){
            if(n % 2 == 1){
                result = result + pow(2, bit);
                bit--;
            }
            else{
                bit--;
            }
            n = n/2;
        }
        return result;
    }
};

191.位1的个数(Number of 1 Bits)

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int count = 0;
        while(n != 0){
            if(n % 2 == 1){
                count++;
            }
            n = n/2;
        }
        return count;
    }
};

202.快乐数(Happy Number)

class Solution {
public:
    bool isHappyTranversal(int n , std::map<int , int>&happy){
        if(n == 1){
            return true;
        }
        else if(happy.find(n) != happy.end()){
            return false;//无限循环
        }
        else{
            happy.insert(pair<int , int>(n , 1));
        }
        int tmp = 0;
        while(n != 0){
            tmp = tmp + (n % 10)*(n % 10);
            n = n / 10;
        }
        return isHappyTranversal(tmp , happy);
    }

    bool isHappy(int n) {
        map<int , int>happyMap;
        return isHappyTranversal(n , happyMap);
    }
};

203.移除链表元素(Remove Linked List Elements)

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

205.同构字符串(Isomorphic Strings)

class Solution {
public:
    bool isIsomorphicSimple(string s, string t) {
        map<char , char>dicts;
        for(int i = 0; i < s.length() ;i++){
            if(dicts.find(s[i]) == dicts.end()){
                dicts.insert(pair<char , char>(s[i] , t[i]));
                s[i] = t[i];
            }
            else{
                s[i] = dicts[s[i]];
            }
        }
        for(int i = 0; i < s.length() ;i++){
            if(s[i] != t[i]){
                return false;
            }
        }
        return true;
    }

    bool isIsomorphic(string s, string t) {
        //正反判断都一样才能保证是同构的(因为不同字符不能映射到同一个字符上)
        if(isIsomorphicSimple(s , t) == true && isIsomorphicSimple(t , s) == true){
            return true;
        }
        else{
            return false;
        }
    }
};

206.反转链表(Reverse Linked List)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    //利用外部空间的情况下使用一个栈保存链表内容并重新遍历链表并赋值即可
    //不利用太多外部空间的情况下使用头插法,每次遍历到一个非NULL的结点,将该结点插到头部
    ListNode* reverseList(ListNode* head) {
        //这里使用头插法
        if(head == NULL){
            return head;
        }
        ListNode *q = head->next;
        ListNode *p = head;
        p->next = NULL;
        head = p;
        while(q != NULL){
            //将q插入头部
            p = q;
            q = q->next;
            p->next = head;
            head = p;
        }
        p = NULL;
        return head;
    }
};

217.存在重复元素(Contains Duplicate)

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        set<int>numsSet;
        for(int i = 0; i < nums.size() ;i++){
            if(numsSet.find(nums[i]) == numsSet.end()){
                numsSet.insert(nums[i]);
            }
            else{
                return true;
            }
        }
        return false;
    }
};

219.存在重复元素 II(Contains Duplicate II)

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        //利用一个map的value存距离目前遍历的位置最近的一个索引即可
        map<int,int>numsMap;
        for(int i = 0; i < nums.size() ;i++){
            if(numsMap.find(nums[i]) == numsMap.end()){
                numsMap.insert(pair<int , int>( nums[i] , i));
            }
            else{
                if(i - numsMap[nums[i]] <= k){
                    return true;
                }
                else{
                    numsMap[nums[i]] = i;
                }
            }
        }
        return false;
    }
};

225.用队列实现栈(Implement Stack using Queues)

226.翻转二叉树(Invert Binary Tree)

228.汇总区间(Summary Ranges)

231.2的幂(Power of Two)

232.用栈实现队列(Implement Queue using Stacks)

234.回文链表(Palindrome Linked List)

235.二叉搜索树的最近公共祖先(Lowest Common Ancestor of a Binary Search Tree)

237.删除链表中的节点(Delete Node in a Linked List)

242.有效的字母异位词(Valid Anagram)

257.二叉树的所有路径(Binary Tree Paths)

258.各位相加(Add Digits)

263.丑数(Ugly Number)

268.丢失的数字(Missing Number)

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注