HHR的小站
享受代码带来的快乐吧
首页
最新评论

在第一行我们写上一个 0。接下来的每一行,将前一行中的0替换为011替换为10

给定行数 N 和序数 K,返回第 N 行中第 K个字符。(K从1开始)

例子:

输入: N = 1, K = 1
输出: 0
输入: N = 2, K = 1
输出: 0
输入: N = 2, K = 2
输出: 1
输入: N = 4, K = 5
输出: 1
解释:
第一行: 0
第二行: 01
第三行: 0110
第四行: 01101001

class Solution {
public:
    int kthGrammar(int N, int K) {
        if (N != 1)
            return ((kthGrammar(N - 1, (K + 1) / 2)) + K % 2 + 1) % 2;
        return 0;
    }
};

https://leetcode-cn.com/problems/k-th-symbol-in-grammar/

给定两个正整数 x 和 y,如果某一整数等于 x^i + y^j,其中整数 i >= 0 且 j >= 0,那么我们认为该整数是一个强整数。

返回值小于或等于 bound 的所有强整数组成的列表。

你可以按任何顺序返回答案。在你的回答中,每个值最多出现一次。

示例 1:

输入:x = 2, y = 3, bound = 10
输出:[2,3,4,5,7,9,10]
解释: 
2 = 2^0 + 3^0
3 = 2^1 + 3^0
4 = 2^0 + 3^1
5 = 2^1 + 3^1
7 = 2^2 + 3^1
9 = 2^3 + 3^0
10 = 2^0 + 3^2

示例 2:

输入:x = 3, y = 5, bound = 15 
输出:[2,4,6,8,10,14] 

提示:

  • 1 <= x <= 100
  • 1 <= y <= 100
  • 0 <= bound <= 10^6

class Solution {
public:
    vector<int> powerfulIntegers(int x, int y, int bound) {
        set<int> num;
        if (x != 1 && y != 1) {
            for (int i = 0; i <= log(bound) / log(x); i++) {
                for (int j = 0; j <= log(bound - pow(x, i) / log(y)); j++) {
                    if (bound >= pow(x, i) + pow(y, j))
                        num.insert(pow(x, i) + pow(y, j));
                }
            }
        } else if (x == 1 && y == 1) {
            if (bound >= 2)
                num.insert(2);
        } else if (x == 1) {
            for (int j = 0; j <= log(bound - 1) / log(y); j++) {
                num.insert(pow(y, j) + 1);
            }
        } else {
            for (int i = 0; i <= log(bound - 1) / log(x); i++) {
                num.insert(pow(x, i) + 1);
            }
        }
        vector<int> ans;
        ans.assign(num.begin(), num.end());
        return ans;
    }
};

https://leetcode-cn.com/problems/powerful-integers/

给定二叉搜索树(BST)的根节点和要插入树中的值,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。

注意,可能存在多种有效的插入方式,只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。

例如, 

 给定二叉搜索树: 
      4        
     / \      
    2   7     
   / \     
  1   3 
和 插入的值: 5 

你可以返回这个二叉搜索树:

          4   
        /   \    
       2     7     
      / \   /     
     1   3 5 

或者这个树也是有效的:

            5   
          /   \  
         2     7  
        / \    
       1   3     
            \   
             4
 

class Solution {
public:
    TreeNode *insertIntoBST(TreeNode *root, int val) {
        if (val > root->val && root->right) {
            insertIntoBST(root->right, val);
        } else if (val < root->val && root->left) {
            insertIntoBST(root->left, val);
        } else if (val > root->val && !root->right) {
            root->right = new TreeNode(val);
        } else {
            root->left = new TreeNode(val);
        }
        return root;
    }
};

https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/

在歌曲列表中,第 i 首歌曲的持续时间为 time[i] 秒。

返回其总持续时间(以秒为单位)可被 60 整除的歌曲对的数量。形式上,我们希望索引的数字  i < j 且有 (time[i] + time[j]) % 60 == 0。

示例 1:

输入:[30,20,150,100,40]
输出:3
解释:这三对的总持续时间可被 60 整数:
(time[0] = 30, time[2] = 150): 总持续时间 180
(time[1] = 20, time[3] = 100): 总持续时间 120
(time[1] = 20, time[4] = 40): 总持续时间 60

示例 2:

输入:[60,60,60] 
输出:3 
解释:所有三对的总持续时间都是 120,可以被 60 整数。 

class Solution {
public:
    int numPairsDivisibleBy60(vector<int> &time) {
        int num[60] = {0}, sum = 0;
        for (int n:time) {
            num[n % 60]++;
        }
        //60+60
        sum += (num[0] - 1) * num[0] / 2;
        //30+30
        sum += (num[30] - 1) * num[30] / 2;
        //(1-29)+(31-59)
        for (int x = 1; x <= 29; x++) {
            sum += num[x] * num[60 - x];
        }
        return sum;
    }
};

https://leetcode-cn.com/problems/pairs-of-songs-with-total-durations-divisible-by-60/

我们有一个由平面上的点组成的列表 points。需要从中找出 K 个距离原点 (0, 0) 最近的点。

(这里,平面上两点之间的距离是欧几里德距离。)

你可以按任何顺序返回答案。除了点坐标的顺序之外,答案确保是唯一的。

示例 1:

输入:points = [[1,3],[-2,2]], K = 1
输出:[[-2,2]]
解释: 
(1, 3) 和原点之间的距离为 sqrt(10),
(-2, 2) 和原点之间的距离为 sqrt(8),
由于 sqrt(8) < sqrt(10),(-2, 2) 离原点更近。
我们只需要距离原点最近的 K = 1 个点,所以答案就是 [[-2,2]]。

示例 2:

输入:points = [[3,3],[5,-1],[-2,4]], K = 2
输出:[[3,3],[-2,4]]
(答案 [[-2,4],[3,3]] 也会被接受。)

class point {
public:
    int x, y, d;

    point(int x, int y) {
        this->x = x;
        this->y = y;
        d = x * x + y * y;
    }
};

bool cmp(point &p1, point &p2) {
    return p1.d < p2.d;
}

class Solution {
public:
    static vector<vector<int>> kClosest(vector<vector<int>> &points, int K) {
        vector<point> p;
        p.reserve(points.size());
        for (vector<int> P:points) {
            p.emplace_back(P[0], P[1]);
        }
        sort(p.begin(), p.end(), cmp);
        vector<vector<int>> ans;
        for (int x = 0; x < K; x++) {
            vector<int> tmp;
            tmp.push_back(p[x].x);
            tmp.push_back(p[x].y);
            ans.push_back(tmp);
        }
        return ans;
    }
};

https://leetcode-cn.com/problems/k-closest-points-to-origin/