tantan的博客

Notes, ideas, and observations

发表于 分类于 ， 本文字数： 38 阅读时长 ≈ 1 分钟

leetcode medium 纯算法题偏少, 准备每日加一道PTA.

目标: 每天一道PTA甲级 [PAT (Advanced Level) Practice]

发表于 分类于 ， 本文字数： 201 阅读时长 ≈ 1 分钟

思路: 对于数字x = an ... ai+1 ai ... a1 a0, 如果任意相邻的ai+1,ai不符合单调递增, 就给原数字减去(ai + 1) * 10 ^ i, 减去之后得到的新数字即为y

可以发现, 若x与y不完全相同, 则最终结果在第一个不相同位之后的位必定全是9, 按此规律修正结果即可.

发表于 分类于 ， 本文字数： 303 阅读时长 ≈ 1 分钟

为什么要使用mongodb

  • 不需要预先定义schema即可存储数据, 适合于快速原型开发, 以及需求经常变更的情况

  • 存储使用的BSON格式非常灵活, 可以表示像数组, 字典这样的数据, 而在RDB中需要拆分成多个表

发表于 分类于 ， 本文字数： 68 阅读时长 ≈ 1 分钟

思路: 字符串排序后作为key, 存到map中再转成vector返回, AC

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        map<string, vector<string>> m;
        for(int i=0;i<strs.size();i++){
            string s=strs[i];
            sort(s.begin(),s.end());
            m[s].push_back(strs[i]);
        }
        vector<vector<string>> res;
        for(auto &k:m){
            res.push_back(k.second);
        }
        return res;
    }
};

发表于 分类于 ， 本文字数： 4 阅读时长 ≈ 1 分钟

满课, 摸了

发表于 分类于 ， 本文字数： 97 阅读时长 ≈ 1 分钟

思路: 先归并排序, 再寻找中间位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int i=0,j=0;
        int len1=nums1.size(),len2=nums2.size(),len=len1+len2;
        int t, lastt;
        while(i+j<=len/2){
            lastt=t;
            if(i<len1 && j< len2){
                int n1=nums1[i];
                int n2=nums2[j];
                if(n1<n2){
                    t=n1;
                    i++;
                }else{
                    t=n2;
                    j++;
                }
            }else if(i<len1){
                t=nums1[i++];
            }else{
                t=nums2[j++];
            }
            cout<<i+j<<":"<<t<<endl;
        }
        return (len%2?t:(t+lastt)/2.0);
    }
};

发表于 分类于 ， 本文字数： 160 阅读时长 ≈ 1 分钟

C++ STL中unique的用法

1
2
3
4
5
6
template <class ForwardIterator>
  ForwardIterator unique ( ForwardIterator first, ForwardIterator last );

template <class ForwardIterator, class BinaryPredicate>
  ForwardIterator unique ( ForwardIterator first, ForwardIterator last,
                           BinaryPredicate pred );

发表于 分类于 ， 本文字数： 78 阅读时长 ≈ 1 分钟

给定一个整数数组，判断是否存在重复元素。

如果任意一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。

发表于 分类于 ， 本文字数： 285 阅读时长 ≈ 1 分钟

思路: 先差分, 然后把所有0和相邻同号的数字(之一)去掉, 剩下的元素数量+2既是最终答案

注意: 元素个数为0, 元素个数为1, 差分后有0出现

0%