头像

麋鹿是森林的眼睛


访客:2107

离线:8小时前


活动打卡代码 LeetCode 40. 组合总和 II

class Solution {
public:
    vector<vector<int>>ans;
    vector<int>tmp;
    int target;
    vector<vector<int>> combinationSum2(vector<int>& candidates, int t) {
        target = t;
        sort(candidates.begin(),candidates.end());

        dfs(candidates, 0 , 0);

        return ans;
    }

    void dfs(vector<int>& candidates, int num , int sum)
    {
        if( sum == target)
        {
            ans.push_back(tmp);
            return;
        }
        if(num == candidates.size())return;

        if(sum + candidates[num] <= target)
        {
            tmp.push_back(candidates[num]);
            dfs(candidates, num + 1, sum + candidates[num]);
            tmp.pop_back();
        }

        int k = num + 1;
        while(k < candidates.size() && candidates[num] == candidates[k])k++;
        dfs(candidates, k, sum);
    }
};


活动打卡代码 LeetCode 39. 组合总和

class Solution {
public:
    vector<vector<int>>ans;
    int n;
    int t;
    vector<int>tmp;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        n = candidates.size();
        t = target;

        dfs(candidates,0,0);

        return ans;
    }

    void dfs(vector<int>&candidates, int num, int sum)
    {
        if(sum == t)
        {
            ans.push_back(tmp);
            //清空
            //tmp.clear();
            return ;
        }
        if(sum > t)return;
        if(candidates[num] > t)return;

        for(int i =num; i < n ;i ++)
        {
            if(sum + candidates[i] <= t)
            {
                tmp.push_back(candidates[i]);
                dfs(candidates,i,sum + candidates[i]);
                tmp.pop_back();

            }
            else return;
        }
        return;
    }
};


活动打卡代码 LeetCode 38. 外观数列

class Solution {
public:
    string countAndSay(int n) {
        string s = "1";

        for(int i = 0; i < n - 1; i ++)
        {
            string t;
            for(int j = 0;j < s.size() ; )
            {
                int k = j + 1;
                while(k < s.size() && s[j] == s[k])k ++;

                t += to_string(k - j) + s[j];

                j = k;
            }
            s = t;
        }
        return s;
    }
};


活动打卡代码 LeetCode 37. 解数独

//暴搜
class Solution {
public:
    int row[10][10];
    int col[10][10];
    int cell[4][4][10];
    void solveSudoku(vector<vector<char>>& board) {
        memset(row,0,sizeof row);
        memset(col ,0, sizeof col);
        memset(cell, 0, sizeof cell);

        for(int i =0; i < 9; i ++)
        {
            for(int j =0;j < 9; j ++)
            {
                if(board[i][j] != '.')
                {
                    int t = board[i][j] - '1';
                    row[i][t] = col[j][t] = cell[i / 3][j / 3][t] = 1;
                }
            }
        }

        dfs(board,0,0);
    }

    bool  dfs(vector<vector<char>>&board,int x,int y)
    {
        if(y == 9)x++, y = 0;
        if(x == 9)return true;

        if(board[x][y] != '.')return dfs(board,x, y + 1);

        for(int i = 0;i < 9; i ++)
        {
            if(!row[x][i] && !col[y][i] && !cell[x / 3][y / 3][i])
            {
                row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = 1;
                board[x][y] = i + '1';
                if(dfs(board, x, y + 1))return true;
                row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = 0;
                board[x][y] = '.';
            }
        }
        return false;
    }
};


活动打卡代码 LeetCode 36. 有效的数独

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        int N = 20;

        int st[N];



        for(int i = 0; i < 9; i ++)
        {
            memset(st,0,sizeof st);
            for(int j = 0;j < 9;j ++)
            {
                if(board[i][j] != '.')
                {
                    int t = board[i][j] - '1';
                    if(st[t])return false;
                    st[t] = 1;
                }
            }
        }


        for(int i = 0; i < 9; i ++)
        {
            memset(st,0,sizeof st);
            for(int j = 0;j < 9;j ++)
            {
                if(board[j][i] != '.')
                {
                    int t = board[j][i] - '1';
                    if(st[t])return false;
                    st[t] = 1;
                }
            }
        }



        for(int i =0; i < 9; i += 3)
        {
            for(int j = 0;j < 9; j += 3)
            {
               memset(st ,0 , sizeof st);

               for(int x = 0; x < 3;x ++)
               {
                   for(int y = 0; y < 3; y ++)
                   {
                       if(board[i + x][j + y] != '.')
                       {
                           int t = board[i + x][j + y] - '1';
                           if(st[t])return false;
                           st[t] = 1;
                       }
                   }
               }
            }
        }

        return true;

    }
};


活动打卡代码 LeetCode 35. 搜索插入位置

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        if(nums.empty())return 0;

        int k = 0;
        while(k < nums.size() && nums[k] < target) k ++;
        return k;
    }
};



class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if(nums.empty())return {-1,-1};

        int l = 0 , r = nums.size() - 1;

        while(l < r)
        {
            int mid = (l + r)>> 1;
            if(nums[mid] >= target) r = mid;
            else l = mid + 1;

        }

        if(nums[r] != target)return {-1,-1};

        int k = r;
        while(k < nums.size() && nums[k] == target)k++;

        return {r,k-1};


    }
};



class Solution {
public:
    int search(vector<int>& nums, int target) {
        if(nums.empty())return -1;

        int l = 0,r = nums.size() - 1;
        int x = nums[0];

        while(l <r)
        {
            int mid = (l + r + 1)>>1;
            if(nums[mid] >= x)l = mid;
            else r = mid - 1;
        }

        if(target >= nums[0])l = 0;
        else{
            l = r+1;
            r = nums.size() - 1;
        }

        while(l < r)
        {
            int mid = (l+r)>>1;
            if(nums[mid] >= target) r = mid;
            else l = mid + 1;
        }

        if(nums[r] == target)return r;//

        return - 1;
    }
};


活动打卡代码 LeetCode 31. 下一个排列

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        /*vector<int > tmp,ans;
        tmp = nums;

        next_permutation(tmp.begin(), tmp.end());

        if(tmp == nums)
        {
            reverse(nums.begin(), nums.end());

        }
        else
        {
            nums = tmp;
        }*/

        int k = nums.size() - 1;
        while(k > 0 && nums[k - 1] >= nums[k])k --;
        if(k <= 0)
        {
            reverse(nums.begin() , nums.end());
        }
        else{
            int t = k;
            while(t<nums.size() && nums[t] > nums[k - 1]) t++;
            swap(nums[k - 1],nums[t - 1]);
            reverse(nums.begin()+(k),nums.end());
        }
    }
};


活动打卡代码 LeetCode 31. 下一个排列

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        vector<int > tmp,ans;
        tmp = nums;

        next_permutation(tmp.begin(), tmp.end());

        if(tmp == nums)
        {
            reverse(nums.begin(), nums.end());

        }
        else
        {
            nums = tmp;
        }
    }
};