头像

vincenyuan




离线:23小时前



vincenyuan
2019-09-27 05:25

题目描述

blablabla

样例

blablabla

算法1

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

使用归并,总的逆序对的个数就是二路归并的左边的逆序对个数和右边逆序对个数的加上横跨两边逆序对个数的和,
横跨两边逆序对个数的计算时,因为左边是有序的,右边也是有序的,所以当归并时,左边为i,右边为j,当i>j时,i和j构成逆序对,而因为是有序的,所以i到mid的元素也大于j的,即当i>j时,构成了mid-i+1个逆序对。
最后使用临时数组存储好归并的结果后,还要把原来的nums覆盖掉,返回归并好的数组

时间复杂度

参考文献

C++ 代码

blablabla

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla



vincenyuan
2019-09-27 05:03

算法1

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

unordered_map<char,int>count;
queue<char> q;
//Insert one char from stringstream
void insert(char ch){
    //当新的字符已经重复,则不插入,而且将队首有可能重复的pop出来。goo,当新来第二个O,
    //此时队首不重复的,证明O永远不会输出,所以此时O不用插入,省一点空间。队列里只存一个O,pop的时候,count里O是两个
    //所以O还是可以正常pop
    if(++count[ch] > 1)
    {
        while(q.size() && count[q.front()] > 1) q.pop();
    }
    else q.push(ch);
}
//return the first appearence once char in current stringstream
char firstAppearingOnce(){
    if(q.empty()) return '#';
    return q.front();
}



vincenyuan
2019-09-27 04:01

题目描述

blablabla

样例

blablabla

算法1

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

blablabla

时间复杂度

参考文献

C++ 代码

int longestSubstringWithoutDuplication(string s) {
    unordered_map<char,int> hash;
    int res = 0;
    for(int i = 0,j = 0;i< s.size(); i++)
    {
        hash[s[i]]++;
        while(hash[s[i]] > 1) hash[s[j++]]--;//如果出现重复元素,肯定是新加进来的是重复的元素,因此移动左边,并改变hash的值
        res = max(res,i-j+1);
    }
    return res;

}

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla



vincenyuan
2019-09-27 02:48

题目描述

blablabla

样例

blablabla

算法1

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

blablabla

时间复杂度

参考文献

C++ 代码

int getMaxValue(vector<vector<int>>& grid) {
    if (grid.empty()) return 0;
    int n= grid.size(),m = grid[0].size();
    int dp[n+1][m+1];
    dp[0][0] = grid[0][0];
    for(int i=1;i<n;i++){
        dp[i][0] = dp[i-1][0] + grid[i][0];
    }
    for(int i=1;i<m;i++){
        dp[0][i] = dp[0][i-1] + grid[0][i];
    }

    for (int i=1;i<n;i++){
        for(int j=1;j<m;j++){
            dp[i][j] = max(dp[i-1][j],dp[i][j-1]) + grid[i][j];

        }
    }
    return dp[n-1][m-1];
}

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla



vincenyuan
2019-09-26 14:40

算法

使用自定义比较函数

时间复杂度

参考文献

C++ 代码

static bool cmp(int &a, int &b) {
    string ab = to_string(a) + to_string(b);
    string ba = to_string(b) + to_string(a);
    return ab < ba;
}
string printMinNumber(vector<int>& nums) {
    string res;
    if(nums.empty()) return res;
    sort(nums.begin(),nums.end(),cmp);
    for(int i = 0;i<nums.size();i++)
    {
        res += to_string(nums[i]);
    }
    return res;
}




vincenyuan
2019-09-26 14:13

算法

$O(logN)$

数理概率题,分析数字规律,个位数有10个,2位数90个,三位数900个,四位数9000个
采用以下几个步骤:

  1. 定位是几位数的数字
  2. 定位到是哪个数值
  3. 定位这个数值的某位

时间复杂度

参考文献

C++ 代码

int digitAtIndex(int n) {
    long long i = 1,s = 9,base = 1;//i表示是几位数字,s表示几位数字的个数,base表示几位数字的起始
    //比如,i=2,表示的是两位数,10-99,s表示有90个(99-10+1),base为10,两位数起始为10
    while(n>i*s)
    {
        n -= i *s;
        i++;
        s *= 10;
        base *= 10;
    }
    //现在的n表示在i位数中第几位,换算成真正的数值,需要让n/i上取整等价于n+i-1
    int number = base + (n+i-1)/i-1;
    int r = n % i ==0 ? i : n % i;//r表示n是number的第几个数字,如果可以整除i说明是最后一个,即第i位,否则是n%i
    for(int j = 0;j<i-r;j++) number /= 10;//求数的第i - r位,取出第i - r位
    return  number % 10;
}

```




vincenyuan
2019-09-26 11:50

算法1

微信图片_20190926181105.png

时间复杂度 $O(logN)$

参考文献

C++ 代码

int NumberOf1Between1AndN_Solution(int n)
{
    // 统计次数
    int count = 0;
    for(int i = 1; i <= n; i *= 10){
        // 计算高位和低位
        int a = n / i, b = n % i;
        count += (a + 8) / 10 * i + (a % 10 == 1) * (b + 1);
    }
    return count;
}




vincenyuan
2019-09-26 11:42

算法

就是使用dfs,沿节点向下依次减值,注意,因为可能存在某一个路径是不合适的,因此回溯的时候,path需要之前放入的元素pop出来。恢复现场。

时间复杂度

参考文献

C++ 代码

int sum ;
    vector<vector<int>> res; 
    vector<int> path;
    vector<vector<int>> findPath(TreeNode* root, int sum) {

        sum = sum;
        dfs(root, sum);
        return res;
    }
    void dfs(TreeNode *root, int sum) {

        if(!root) return;
        path.push_back(root->val);
        sum = sum - root->val;
        if(!root->left && !root->right && !sum) res.push_back(path);
        //上面判断过了,所以不需要再额外判断
        dfs(root->left, sum);
        dfs(root->right, sum);
        path.pop_back();//恢复现场,那些不符合,回退的需要清理出去,不然就有可能加在正确的path里
    }



vincenyuan
2019-09-26 11:33

算法

就是使用dfs,沿节点向下依次减值,注意,因为可能存在某一个路径是不合适的,因此回溯的时候,path需要之前放入的元素pop出来。恢复现场。

时间复杂度

参考文献

C++ 代码

int sum ;
    vector<vector<int>> res; 
    vector<int> path;
    vector<vector<int>> findPath(TreeNode* root, int sum) {

        sum = sum;
        dfs(root, sum);
        return res;
    }
    void dfs(TreeNode *root, int sum) {

        if(!root) return;
        path.push_back(root->val);
        sum = sum - root->val;
        if(!root->left && !root->right && !sum) res.push_back(path);
        //上面判断过了,所以不需要再额外判断
        dfs(root->left, sum);
        dfs(root->right, sum);
        path.pop_back();//恢复现场,那些不符合,回退的需要清理出去,不然就有可能加在正确的path里
    }


活动打卡代码 AcWing 72. Edit Distance

vincenyuan
2019-09-22 08:36
int minDistance(string word1, string word2) {
    int n = word1.size(),m = word2.size();
    vector<vector<int>> f(n+1,vector<int>(m+1));
    for(int i = 0;i<=n;i++) f[i][0] = i;
    for(int i = 0;i<=m;i++) f[0][i] = i;
    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=m;j++)
        {
            if(word1[i-1] == word2[j-1]) f[i][j] = f[i-1][j-1];
            else f[i][j] = min(f[i-1][j],min(f[i][j-1],f[i-1][j-1]))+1;
        }
    return f[n][m];
}