HHR的小站
享受代码带来的快乐吧
首页
您正在查看: 代码使人快乐 分类下的文章

给定两个数组,编写一个函数来计算它们的交集。

示例 1:

输入:nums1 = [1,2,2,1], nums2 = [2,2]
输出:[2,2]

示例 2:

输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出:[4,9]

说明:

  • 输出结果中每个元素出现的次数,应与元素在两个数组中出现的次数一致。
  • 我们可以不考虑输出结果的顺序。

进阶:

  • 如果给定的数组已经排好序呢?你将如何优化你的算法?
  • 如果 nums1 的大小比 nums2 小很多,哪种方法更优?
  • 如果 nums2 的元素存储在磁盘上,磁盘内存是有限的,并且你不能一次加载所有的元素到内存中,你该怎么办?

#include <vector>
#include <hash_map>

using namespace std;
using namespace __gnu_cxx;

class Solution {
public:
    vector<int> intersect(vector<int> &nums1, vector<int> &nums2) {
        hash_map<int, int> num, num2;
        vector<int> ans;
        for (auto n:nums1) {
            num[n]++;
        }
        for (auto n:nums2) {
            if (num.find(n) != num.end() && num[n] != 0) {
                num[n]--;
                ans.push_back(n);
            }
        }
        return ans;
    }
};

使用hashmap存储第一个数组的内容,然后对数组2中的元素进行遍历,找到重复元素返回

https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根,其中 x 是非负整数。

由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。

示例 1:

输入: 4
输出: 2

示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数,小数部分将被舍去。

class Solution {
public:
    static int mySqrt(int x) {
        int i = 0, j = x / 2 + 1;
        long long ans;
        while (i <= j) {
            ans = (i + j) / 2;
            if (ans * ans == x) {
                return ans;
            } else if (ans * ans > x) {
                j = ans - 1;
            } else {
                i = ans + 1;
            }
        }
        return j;
    }
};

对分查找,注意选好上界

https://leetcode-cn.com/problems/sqrtx/

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1:

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2:

输入: "cbbd"
输出: "bb"

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.length() == 0) return "";
        bool dp[1000][1000] = {{false}};
        int max = 0;
        string ans;
        for (int x = s.length(); x >= 0; x--) {
            for (int y = x; y < s.length(); y++) {
                if (y - x < 2) {
                    dp[x][y] = s[x] == s[y];
                } else {
                    dp[x][y] = dp[x + 1][y - 1] && (s[x] == s[y]);
                }
                if (dp[x][y] && y - x + 1 > max) {
                    max = y - x + 1;
                    ans = s.substr(x, y - x + 1);
                }
            }
        }
        return ans;
    }
};

第i到第j个char能否构成回文取决于
1.第i+1到第j-1个char是否回文
2.第i个char和第j个char是否相同
dp[i][j]=dp[i+1][j-1]&&s[i]==s[j]
注意考虑串为空的特殊情况
x自大到小,y从小到大,确保dp[x+1][y-1]已经完成定义

https://leetcode-cn.com/problems/longest-palindromic-substring/

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

示例 1:

输入:[7,1,5,3,6,4]
输出:5
解释:在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

示例 2:

输入: [7,6,4,3,1]
输出: 0
解释:在这种情况下, 没有交易完成, 所以最大利润为 0。

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        if (prices.empty()) return 0;
        int ans = 0, min = prices[0];
        for (int price:prices) {
            ans = max(ans, price - min);
            if (price < min) min = price;
        }
        return ans;
    }
};

到某天为止的最大盈利=max(前一天为止的最大盈利,如果今天卖出的最大盈利)
注意没有任何交易日的特殊情况

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/

2020-02-06 |HHR

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

注意:给定 n 是一个正整数。

示例 1:

输入: 2
输出: 2
解释: 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例 2:

输入: 3 
输出: 3 
解释: 有三种方法可以爬到楼顶。 
1.  1 阶 + 1 阶 + 1 阶 
2.  1 阶 + 2 阶 
3.  2 阶 + 1 阶 

class Solution {
public:
    int climbStairs(int n) {
        vector<int> ans;
        ans.push_back(1);
        ans.push_back(2);
        for (int x = 2; x < n; x++) {
            ans.push_back(ans[x - 1] + ans[x - 2]);
        }
        return ans[n-1];
    }
};

到每一阶的方法数是前两阶方法数之和

https://leetcode-cn.com/problems/climbing-stairs/