头像

s_9


访客:4672

离线:1个月前


活动打卡代码 AcWing 47. Permutations II

s_9
10个月前
class Solution {
public:
    vector<bool> st;
    vector<int> path;
    vector<vector<int>> res;
    int n;

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        n = nums.size();
        if(nums.empty()) return res;
        sort(nums.begin(), nums.end());
        st = vector<bool>(n);
        path = vector<int>(n);
        dfs(nums, 0, 0);
        return res;
    }

    void dfs(vector<int>& nums, int u, int start){
        if(u == n){
            res.push_back(path);
            return;
        }
           for(int i = start; i < n; i++){
            if(!st[i]){
                st[i] = true;
                //path.push_back(nums[u]);
                path[i] = nums[u];
                if(u + 1 < n && nums[u] == nums[u + 1]){
                    dfs(nums, u + 1, i + 1);
                }
                else{
                    dfs(nums, u + 1, 0);
                }
                //path.pop_back();
                st[i] = false;
            }
        }
   }
};


活动打卡代码 AcWing 46. Permutations

s_9
10个月前
class Solution {
public:
    vector<bool> st;
    vector<int> path;
    vector<vector<int>> res;
    vector<vector<int>> permute(vector<int>& nums) {
        if(nums.empty()) return res;
        st = vector<bool>(nums.size(), false);
        dfs(nums, 0);
        return res;
    }
    void dfs(vector<int>& nums, int u){
        //递归终止条件,所以不用n-1,要到最外面那层
        if(u == nums.size()){
            res.push_back(path);
            return;
        }
        for(int i = 0; i < nums.size(); i++){
            if(!st[i]){
                st[i] = 1;
                path.push_back(nums[i]);
                dfs(nums, u + 1);
                st[i] = 0;
                path.pop_back();
            }
        }

    }
};


活动打卡代码 AcWing 79. Word Search

s_9
10个月前
/*
    思路:
    1.搜索问题最重要就得是注意顺序问题
    2.从起点开始枚举,一次搜索下一个点的位置
    3.在枚举的过程中,要保证目标和单词匹配
*/

class Solution {
public:
    int n, m;
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    bool exist(vector<vector<char>>& nums, string word) {
        //边界问题,如果n,m没有 -1,那么后面使用的时候要么不能取等号,要么使用-1操作
        n = nums.size();
        m = nums[0].size() ;
        if(nums.empty() || nums[0].empty()) return false;
        //枚举所有的点
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(dfs(nums, i, j, 0, word))
                    return true;
            }
        }
        return false;
    }
    //DFS暴搜,回溯记得还原现场
    bool dfs(vector<vector<char>>& nums, int x, int y, int u, string &word){
        if(nums[x][y] != word[u]) return false;
        if(u == word.size() - 1) return true;

        nums[x][y] = '.';

        for(int i = 0; i < 4; i++){
            int a = x + dx[i], b = y + dy[i];
            if(a < n && a >= 0 && b < m && b >= 0)
                if(dfs(nums, a, b, u + 1, word)) return true;     
        }
        nums[x][y] = word[u];
        return false;
    }
};




s_9
10个月前
/*
    基本思路:
    1、从每一个字母里面挑一个,2里面挑一个,3里面挑一个,然后组合
*/
string chars[8] = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
class Solution {
public:
    vector<string> letterCombinations(string digits) {
       vector<string> str(1, "");
        if(digits.empty()) return vector<string>();

        for(auto i : digits){
            vector<string> news;
            for(auto j : chars[i - '2']){

                for(auto s : str){

                    news.push_back(s + j);
                    cout<<s + j<<' ';

                }

            }
            str = news;
        }
        return str;
    }
};



s_9
10个月前
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        if(nums.empty()) return 0;
        sort(nums.begin(), nums.end());
        int l = 0, r = nums.size() - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(nums[mid] <= mid) r = mid;
            else l = mid + 1;
        }
        return nums[r];
    }
};


活动打卡代码 AcWing 162. Find Peak Element

s_9
10个月前
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(nums[mid] > nums[mid + 1]) r = mid;
            else l = mid + 1;
        }
        return r;
    }
};


活动打卡代码 AcWing 278. First Bad Version

s_9
10个月前

278

// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        if(n == 1 || n == 0) return n;
        long long l = 1, r = n;
        while(l < r){
            long long mid =  l + r >> 1;
            if(isBadVersion(mid)) r = mid;
            else l = mid + 1;
        }
        return l;
    }
};



s_9
10个月前
class Solution {
public:
    int search(vector<int>& nums, int target) {
        if(nums.empty()) return -1;
        if(nums[0] < nums[nums.size() - 1]){
            int l = 0, r = nums.size() - 1;
            while(l < r){
            int mid = l + r >> 1;
            if(nums[mid] < target) l = mid + 1;
            else r = mid;
            }
            if(nums[l] != target) return -1;
            return r;
        }

        int l = 0, r = nums.size() - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(nums[mid] < nums[0]) r = mid;
            else l = mid + 1;
        }
        cout<<l<<endl;
        if(target >= nums[0]){
            r = l - 1;
            l = 0;

        }else{
            r = nums.size() - 1;
        }
        while(l < r){
            int mid = l + r >> 1;
            if(nums[mid] < target) l = mid + 1;
            else r = mid;
        }
        cout<<nums[l]<<endl;
        if(nums[l] != target) return -1;
        return l;

    }
};



s_9
10个月前
class Solution {
public:
    int findMin(vector<int>& nums) {
        if(nums.empty()) return 0;
        if(nums.size() == 1) return nums[0];
        if(nums[0] < nums[nums.size() -  1]) return nums[0];

        int l = 0, r = nums.size();
        while(l < r){
            int mid = l + r >> 1;
            if(nums[mid] < nums[0]) r = mid;
            else l = mid + 1;
        }
        return nums[l];
    }
};



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

        bool flag = false;

        for(auto i : nums){
            if(i == target) flag = true; 
        }
        if(!flag) 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;
        }
        int left = l;
        l = 0, r = nums.size() - 1;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(nums[mid] <= target) l = mid;
            else r = mid - 1;
        }
        int right = l;
        return {left, right};
    }
};