头像

小雨


访客:29042

离线:7个月前



小雨
2018-12-26 07:01

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析:blablabla

C++ 代码

/**
 * // This is the Master's API interface.
 * // You should not implement it, or speculate about its implementation
 * class Master {
 *   public:
 *     int guess(string word);
 * };
 */
class Solution {
public:
    void findSecretWord(vector<string>& wordlist, Master& master) {
        int match = 0;
        for (int i = 0; i < 10, match < 6; i++) {
            int guess_id = rand() % wordlist.size();
            match = master.guess(wordlist[guess_id]);
            reduceWordList(wordlist, match, wordlist[guess_id]);

        }
    }
    void reduceWordList(vector<string>& wordlist, int match, string cur) {
        vector<string> newWordList;
        for (int i = 0; i < wordlist.size(); i++) {
            if (isMatch(wordlist[i], cur, match)) {
                newWordList.push_back(wordlist[i]);
            }
        }
        wordlist = newWordList;
    }

    bool isMatch(string a, string b, int match) {
        int cnt = 0;
        if (a.size() != b.size()) {
            return false;
        }
        for (int i = 0; i < a.size(); i++) {
            if (a[i] == b[i]) {
                cnt++;
            }
        }
        return cnt == match;
    }
};





小雨
2018-12-02 19:46
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        // a friend remind of me that I can just do inorder traversal, I don't need to remove the nodes recursively
        TreeNode* cur = root;
        stack<TreeNode*> ss;
        while (cur) {
            ss.push(cur);
            cur = cur->left;
        }

        while(!ss.empty()) {
            // extract the first node from the stack
            TreeNode* cur = ss.top();
            ss.pop();
            if (k == 1) {
                return cur->val;
            } else {
                k--;
                if (cur->right) {
                    cur = cur->right;
                    while (cur) {
                        ss.push(cur);
                        cur = cur->left;
                    }
                }
            }
        }
    }
};

// time complexity: o(k)
// space complexity: o(n);



小雨
2018-12-02 18:43
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
class Solution {
public:
    int projectionArea(vector<vector<int>>& grid) {
        int topArea = 0, frontArea = 0, sideArea = 0;
        // for frontArea, just find the biggest value in each column,
        // for sideArea, just find the biggest value in each row;
        for (int i = 0; i < grid.size(); i++) {
            int max_row_val = INT_MIN;
            int max_col_val = INT_MIN;
            for (int j = 0; j < grid.size(); j++) {
                if (grid[i][j] > 0) {
                    topArea++;
                }
                max_row_val = max(max_row_val, grid[i][j]);
                max_col_val = max(max_col_val, grid[j][i]);

            }
            sideArea += max_row_val;
            frontArea += max_col_val;
        }
        return sideArea + frontArea + topArea;
    }
};


活动打卡代码 AcWing 326. Power of Three

小雨
2018-12-01 19:37
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
class Solution {
public:
    bool isPowerOfThree(int n) {
        // use recursion
        // because the question remaind of me that I need to use recursion
        // how to solve the case when n == 1 ? 
        //  我觉得这个题目一开始就不应该提醒我嘛,搞得我想不出自己的方法
        // 求观世音菩萨加持
        // special cases: 0 and 1;
        // ordinary cases: n % 3 == 0;
        // forgot about the corner case again
        if (n == 0) return false;
        while (n == 1 || n % 3 == 0) {
            if (n == 1) {
                return true;
            } else {
                n /= 3;
            }
        }
       return false;

    }
};


活动打卡代码 AcWing 66. Plus One

小雨
2018-12-01 18:39
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        //  这里为什么返回的是一个vector 呢,不是应该是一个整数么?
        // because I hope to process the number from the lower digit,
        // so I would like to reverse the array first
        reverse(digits.begin(), digits.end());
        int n = digits.size();
        // the key thing here is when we increment the last digit by 1, 
        // that might lead to the next higher digit also increment by 1
        int increment = 1;
        for (int i = 0; i < n; i++) {
            digits[i] += increment;
            if (digits[i] > 9) {
                digits[i] = 0;
                increment = 1;
            } else {
                increment = 0;
                break;
            }
        }
        //  I forgot about the corner case here,
        // when the case that after traversed all the digits, the increment still remains 1, then
        // I need to put one more 1 in the highest digit position. 
        if (increment) {
            digits.push_back(1);
        }
        reverse(digits.begin(), digits.end());
        return digits;
    }
};



小雨
2018-11-30 06:35

算法

(DFS)

时间复杂度分析:DFS 的时间复杂度是多少哇

C++ 代码

class Solution {
public:
    int minTransfers(vector<vector<int>>& transactions) {
        // 原来一个二维矩阵就可以了啊,我还用hashmap 搞得这么复杂
        // DFS 
        // 这个题目一上来不知道怎么做啊
        // 先把transaction 变成 account balance
        // 然后dfs 每次drop 掉一个 account
        // 每次drop 掉一个account, 这是说最多drop n-1 么, n 是一开始的账户数目
        // why the answer ranked top 1 sets the res to INT_MAX?
        // don't know why
        // what is prev
        // 我感觉我好像有点看懂这个题目了
        // 每一次都找一个与当前account balance whose sign is different from the current account
        // and then drop out the current account by add the current account's balance to the one that found to have 
        // different sign balance from the current account
        // in this way, we can erase one account balance each time, in other words, make at least one account's balance equal to 0
        // by doing this step by step, we can make all the accounts' balance equal to 0, if all the accounts' balance equal to 0
        // which means the debts have been settled.
        // during that process, each time, when we erase one account, we add 1 to the current count of the transactions that have been processed
        // after all the debts have been settled, we have a transaction counter value, but that's just one way to settle all the transactions, we need to try out all the possible ways to settle the transaction, and keep track of the minimum value of the transaction counter needed to settle all the debts.
        // which means we need to try out all possible ways, and each time when we finish all the transactions, in other words, make all accounts' balance equal to 0, we then need to backtrack, to try other choices.
        // 好了, 我要开始写code 了
        // start 是为了去重用的
        // 首先 traverse 所有transactions, 把transactions 转化成 account balance
        // transactions: n X 3 matrix
        int max_transac = transactions.size();
        unordered_map<int, int> ac2bal;
        for (int i = 0; i < transactions.size(); i++) {
            vector<int> cur_transaction = transactions[i];
            ac2bal[cur_transaction[0]] -= cur_transaction[2];
            ac2bal[cur_transaction[1]] += cur_transaction[2];
        }
        // 因为unordered_map 不太好traverse, 所以把这个map  转化成 vector
        // 题目当中还特意提醒说index 没有关系,所以 index  是什么不重要,只要这是一个unique 的index, 可以代表这个账户就好,因此vector 的index 
        // 就可以代表这个账户了,或者说代表这个人了,所以其实这个人一开始的编号并不需要存下来
        vector<int> account_balance;
        for (auto pair : ac2bal) {
            if (pair.second) {
                account_balance.push_back(pair.second);
            }
        }
        // 然后我们就需要调用dfs helper function 去把这一堆不为0 的账户一个一个清掉了
          return dfs(account_balance, 0);        
    }
private:
    //  这里来写我们的helper function
    int dfs(vector<int>& account_balance, int start) {
        int n = account_balance.size();
        // start 就是我们当前要消除的账户, 这个账户的balance 不能为0,因为如果已经为0了还消除个啥,不用消除,直接跳过
        while (start < n && account_balance[start] == 0) {
            start++;
        }
        // 我们总是从第一个账户开始消除
        // 然后我们从第一个账户的下一个账户开始找起
        if (start == n) return 0;
        int res = INT_MAX;

        for (int i = start+1; i < n; i++) {
            // 如果他们刚好账户balance 正负相反,就可以消除了
            //  之所以不找正正的balance来消除,是因为明显这样消除,transaction 会越变越多的
            if ( account_balance[i] * account_balance[start] < 0) {
                // 满足条件了,我们来消除吧 ( 相加才是消除朋友们,debug了好久发现了这个问题)
                account_balance[i] += account_balance[start];
                // start 前面包括start 都是已经消除过的
                res = min(res, 1 + dfs(account_balance, start+1));
                account_balance[i] -= account_balance[start];
            }
        }
        return res;
    }
};



小雨
2018-11-29 07:30

算法

(DFS)

这个题目实在是太好了,感觉非常灵活,有变通性,直接想题目感觉根本不会想到 dfs的解法,但是后来理清思路了以后就发现其实是在一个图里面找是否存在这个路径,并且要把这个路径的距离返回,我的code 里面夹杂了我在写这个题目的思考过程,期间有想放弃看答案的时候,还好”观世音菩萨”加持住了,哈哈哈,忍住了没有看答案,最后还是自己写出来了。

时间复杂度分析:我先把这个时间复杂度分析留在这里,明天早上起来看看,因为我现在好困啊。

C++ 代码

class Solution {
public:
    vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
        // 感觉就是dfs 的题目,好久没有做dfs了啊
        // 感觉就是找一条从起点到终点的路啊
        // 一条路一直走下去,如果走不下去的时候,就回头,回到上一次做选择的地方,再走其他的路。
        // 感觉就是这样做,这道题目
        // 怎么写呢,这道题目
        // 这个unordered_map 不行,怎么办呢? 用什么可以替换呢?
        // 好困啊,求观世音菩萨加持,让我把这个题目想出来
        unordered_map<string, double> map;
        unordered_map<string, vector<string>> start2end;
        // avoid loop


        for (int i = 0; i < equations.size(); i++) {

            string start = equations[i].first;
            string end = equations[i].second;


            map[start + end] = values[i];
            map[end + start] = 1.0/values[i];  

            start2end[start].push_back(end);
            start2end[end].push_back(start);
        }
        // define a return vector to store the result
        vector<double> res;
        // map 存好了以后就可以进行dfs
        for (int i = 0; i < queries.size(); i++) {
            unordered_set<string> visited;
            pair<string, string> curQuery = queries[i];
            // 怎么进行dfs 呢?
            // 首先需要 我们要找的路劲的起点和终点, 那我只需要定义一个起点和一个终点就好了啊
            string start = curQuery.first;
            string end = curQuery.second;
            // 知道起点和终点以后,我们就可以在我们存好的 hashmap 里面进行dfs了
            // 我觉得这道题目真的很好
            // 一开始把query 的结果定义为没有,直到找到以后再重新赋值
            double value = 1;
            value = dfs(start, end, map, start2end, value, visited);
            res.push_back(value);
        }
        return res;
        // unordered_map 里面应该怎么写, 当 a 走到 b 之后, b 不能再走回 a 了。 
        // 要怎么才可以消环呢?



    }
private:
    double dfs(string start, string end, unordered_map<string, double>& map, unordered_map<string, vector<string>>& start2end, double value, unordered_set<string>& visited)  {
        // the key here should be start, should not be the pair of the start and the end
        // in that way, we can query the hashmap if the start point exist in this map
        // however, how can I store both end point string and the double value into a single mapped value?
        //   观世音菩萨加持
        // 对啊,一个hashmap 存不下的时候就用两个hashmap 嘛
        //  在unordered_map里面走过一个就要erase 一个

        if (!start2end.count(start)) {
            return -1.0;
        } else {
            if (start == end) {
                return value;
            }
            // 不行我一定要自己写出来,不要看答案
            // 观世音菩萨加持 感觉这里应该是multimap, 而不是 unordered_map, 
            vector<string> nexts = start2end[start];
            visited.insert(start);
            for (int i = 0; i < nexts.size(); i++) {
                string next = nexts[i];
                if (visited.count(next)) {
                    continue;
                }
                // 观世音菩萨加持
                //pair<string, string> cur = make_pair(start, next);

                double tmp = dfs(next, end, map, start2end, value*map[start+next], visited);
                if (tmp > -1.0) {
                    return tmp;
                }
                visited.erase(start);
            }
            return -1.0;
            // 求观世音菩萨加持,让我把最后一个bug de 出来

        }

    }
};


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

小雨
2018-11-26 00:02
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int l = 1, r = n;
        while (l < r) {
            int mid = l + (r - l)/2;
            if (isBadVersion(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
};


活动打卡代码 AcWing 88. Merge Sorted Array

小雨
2018-11-25 06:18
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        // 直接写感觉好绕
        // 不要从前往后merge, 从后往前merge
        int pos1 = m - 1, pos2 = n - 1, pos = m + n - 1;
        while (pos1 >= 0 && pos2 >= 0) {
            if (nums1[pos1] >= nums2[pos2]) {
                nums1[pos--] = nums1[pos1--];
            } else {
                nums1[pos--] = nums2[pos2--];
            }
        }
       while (pos2 >= 0) {
           nums1[pos--] = nums2[pos2--];
       } 
    }
};


活动打卡代码 AcWing 88. Merge Sorted Array

小雨
2018-11-25 06:04
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        // 直接写感觉好绕
        // 不要从前往后merge, 从后往前merge
        int pos1 = m - 1, pos2 = n - 1, pos = m + n - 1;
        while (pos1 >= 0 && pos2 >= 0) {
            if (nums1[pos1] >= nums2[pos2]) {
                nums1[pos--] = nums1[pos1--];
            } else {
                nums1[pos--] = nums2[pos2--];
            }
        }
       while (pos2 >= 0) {
           nums1[pos--] = nums2[pos2--];
       } 
    }
};