HZOJ Logo 张义丰的博客

博客

面试笔试算法(上)听课笔记 05-06

2021-05-06 21:01:41 By 张义丰

05-06——leetcode习题讲解----------------

OJ-599 两数之和1

暴力解法,时间复杂度O(n^2) 空间复杂度O(1)

二分解法,时间复杂度O(n*logn) 空间复杂度O(1)

unordered_map解法,时间复杂度O(n) 空间复杂度O(n)

/*************************************************************************
    > File Name: 599_3.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Thu 06 May 2021 06:06:24 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int a[1000005], n, t;
unordered_map <int, int> m;
int main(){
    cin >> n >> t;
    for (int i=0; i<n; ++i){
        scanf("%d", a+i);
        m[a[i]] = i;
    }
    for (int i=0; i<n; ++i){
        if (m.count(t - a[i]) == 1){
            cout << i << ' ' << m[t-a[i]] << endl;
            break;
        }
    }
    return 0;
}

双指针解法,时间复杂度O(n) 空间复杂度O(1)

/*************************************************************************
    > File Name: 599.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Thu 06 May 2021 06:06:24 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int a[1000005], n, t;
int main(){
    cin >> n >> t;
    for (int i=0; i<n; ++i){
        scanf("%d", a+i);
    }
    int i=0, j = n-1;
    while (1){
        if (a[i]+a[j] == t){
            cout << i << ' ' << j << endl;
            break;
        }else if (a[i]+a[j] < t){
            i++;
        }else{
            j--;
        }
    }
    return 0;
}

OJ-600 杨氏矩阵

从左下角开始找

/*************************************************************************
    > File Name: 600.cpp
    > Author: dianjin
    > Mail: 3528956319@qq.com
    > Created Time: Thu 06 May 2021 06:51:14 PM CST
 ************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int n, m, t, a[3003][3003];
int main(){
    cin >> n >> m;
    for (int i=1; i<=n; ++i){
        for (int j=1; j<=m; ++j){
            scanf("%d", &a[i][j]);
        }
    }
    cin >> t;
    int i=n, j=1;
    while (i>0 && j<=m){
        if (a[i][j] == t){
            cout << i << ' ' << j << endl;
            break;
        }else if (a[i][j] < t){
            j++;
        }else {
            i--;
        }
    }
    return 0;
}

和上一题的关系:把矩阵中的每个数看做是对应下标两数之和

Leetcode-1,7,9,13,14,26,35,69,278,38,136,66(自己做)

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。