头像

萌王赛高


访客:4114

在线 



class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        for(auto x:nums2)
            nums1[m++] = x;
        sort(nums1.begin(),nums1.end());
    }
};



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



/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        unordered_map<int,int> m;
        vector<int> nums;
        ListNode* tail = new ListNode(-1),* h = tail,* h1 = head;
        while(h1)
        {
            m[h1->val] += 1;
            h1 = h1->next;
        }
        while(head)
        {
            if(m[head->val] == 1) nums.push_back(head->val);
            head = head->next;
        }
        for(auto x: nums)
        {
            ListNode* p = new ListNode(x);
            tail->next = p;
            tail = p;
        }
        return h->next;
    }
};



class Solution {
public:
    int find(int l, int r, vector<int> nums, int target)
    {
        while(l < r)
        {
            int mid = (l + r) >> 1;
            if(nums[mid] > target)r = mid - 1;
            else if(nums[mid] == target) return mid;
            else l = mid + 1;
        }
        return l;
    }
    bool search(vector<int>& nums, int target) {
        int n = nums.size(),k = 0;
        if(!n) return false;
        while(k + 1 < n && nums[k+1] >= nums[k]) k++;
        int l1 = 0, r1 = k, l2 = k+1, r2 = n - 1;
        if(k == n - 1) l2 = l1 , r2 = r1;
        int t1 = find(l1, r1, nums, target), t2 = find(l2, r2, nums, target);
        if(nums[t1] != target && nums[t2] != target) return false;
        return true;
    }
};


活动打卡代码 LeetCode 77. 组合

class Solution {
public:
    vector<vector<int>> res;
    vector<int> ans;
    void dfs(int n,int k,int sidx)
    {
        if(!k)
        {
            res.push_back(ans);
            return;
        }
        for(int i = sidx;i <= n; i++)
        {
            ans.push_back(i);
            dfs(n, k - 1, i + 1);
            ans.pop_back();
        }
    }
    vector<vector<int>> combine(int n, int k) {
        dfs(n,k,1);
        return res;
    }
};


活动打卡代码 LeetCode 73. 矩阵置零

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int n = matrix.size(),m = matrix[0].size();
        typedef pair<int,int> PII;
        vector<PII> res;
        if(!n || !m)return;
        for(int i = 0 ; i < n; i++)
            for(int j = 0 ; j < m; j++)
            {
                if(matrix[i][j] == 0)
                {
                    res.push_back({i,j});
                }
            }
        for(int i = 0 ; i < res.size();i++)
        {
            int a = res[i].first,b = res[i].second;
            for(int col = 0 ; col < m; col++)matrix[a][col] = 0;
            for(int row = 0 ; row < n; row++)matrix[row][b] = 0;
        }
        return;
    }
};



活动打卡代码 LeetCode 64. 最小路径和

class Solution {
public:
    int minPathSum(vector<vector<int>>& g) {
        int n = g.size();
        if(!n) return 0;
        int m = g[0].size();
        int f[n+1][m+1];
        memset(f,0,sizeof f);
        vector<vector<int>> w(n+2,vector<int>(m+2));
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                w[i+1][j+1] = g[i][j];

        for(int i = 1;i<=n;i++)
            for(int j = 1;j<=m;j++)
            {
                if(i == 1 && j == 1)f[i][j] = w[i][j];
                else
                {
                    f[i][j] = 0x3f3f3f3f;
                    if(i>1)f[i][j] = min(f[i][j],f[i-1][j] + w[i][j]);
                    if(j>1)f[i][j] = min(f[i][j],f[i][j-1] + w[i][j]);
                }
            }
        return f[n][m];
    }
};


活动打卡代码 LeetCode 63. 不同路径 II

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int n = obstacleGrid.size();
        if(!n)return 0;
        int m = obstacleGrid[0].size();

        if(obstacleGrid[n-1][m-1] || obstacleGrid[0][0])return 0;
        int f[n][m];
        memset(f,0,sizeof f);
        for(int i = 0; i < n; i++)if(obstacleGrid[i][0])break;else f[i][0] = 1;
        for(int i = 0; i < m; i++)if(obstacleGrid[0][i])break;else f[0][i] = 1;

        for(int i = 1; i < n; i++)
            for(int j = 1; j < m; j++)
            {
                if(obstacleGrid[i][j])continue;
                if(!obstacleGrid[i-1][j])
                {
                    f[i][j] = f[i-1][j];
                    if(!obstacleGrid[i][j-1])f[i][j] += f[i][j-1];
                }
                if(!obstacleGrid[i][j-1])
                {
                    f[i][j] = f[i][j-1];
                    if(!obstacleGrid[i-1][j])f[i][j] += f[i-1][j];
                }
            }
        return f[n-1][m-1];
    }
};



class Solution {
public:
    int lengthOfLastWord(string s) {
        stringstream  ss(s);
        string res;
        while(ss>>res){}
        return res.length();
    }
};
class Solution {
public:
    int lengthOfLastWord(string s) {
        if(!s.size()) return 0;
        int cnt = 0;
        int i = s.size()-1;
        while(i >= 0 && s[i] == ' ')i--;
        for(; i >= 0; i--)
        {
            if(s[i] == ' ')break;
            cnt++;
        }
        return cnt;
    }
};


活动打卡代码 LeetCode 69. x 的平方根

class Solution {
public:
    int mySqrt(int x) {
        if(!x)return 0;
        int res = 0;
        for(int i = 1; i <= x ; i++)
        {
            if(i <= x / i && (i + 1) > x / (i + 1))
            {
                res = i;
                break;
            }
        }
        return res;
    }
};