发表于   |   分类于 ，   |  

计算二进制中1的个数问题

题目大意

　　https://leetcode.com/submissions/detail/62797806/

　　计算从0到num中每个数字的二进制形式中1的个数

题目分析

　　这个题目，暴力解法复杂度在O(n*sizeof(integer))，这里integer就是某个i的二进制表示后的长度。可以用动态规划解此贴，但关键巧妙的店在于递推公式，就是计算ret[i] (结果数组用ret表示)如何利用ret[0]~ret[i-1]的结果

　　想计算数字i的二进制中1的数量，计算i&(i-1),i&(i-1)中1的数量一定比i中1的数量少1.

　　可以这样证明：i的最后一位是0或者1

  • 如果是0，那么i-1的最后一位是1，i的倒数第二位是0的话，i-1的倒数第二位为1…….直到i的某一位为1，i-1的该位为0。从这位往前推，i和i-1都是相同的。
  • 如果是1，那么i-1的最后一位是0，其他位跟i相同

　　综上两种情况，i&(i-1)中1的个数一定比i中1的个数少1.该算法复杂度就是O(n)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <vector>
using namespace std;
vector<int> countBits(int num) {
    vector<int> ret(num + 1, 0);
    for(int i = 1; i <= num; i++) {
        ret[i] = ret[i & (i - 1)] + 1;
    }
    return ret;
}
int main() {
    vector<int> ret = countBits(5);
    for(int i = 0;i <= 5; i++) {
        cout << ret[i] <<" " ;
    }
    cout <<endl;
    return 0;
}

发表于   |   分类于   |  

　　Capital One是一家庞大的机构。为了成为一家金融服务公司，Capital One 需要满足许多合规性问题。该公司同时也是亚马逊 AWS 云计算服务的客户。关于使用 AWS，该公司需要一款工具，制定高效的规则和策略。

　　Custodian是AWS 规则引擎，是跟AWS各项服务紧耦合的。安装其项目主页的描述“Policy rules engine for aws management, policies in yaml for query, filter, and take actions on resources” 是一款基于aws管理的规则引擎，基于yaml配置文件，能对aws资源进行查询，过滤，并采取某种操作。

　　我们看看针对ec2的使用例子，主要是Query，filter，action：

  • Query
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
EC2_VALID_FILTERS = {
   'architecture': ('i386', 'x86_64'),
   'availability-zone': str,
   'iam-instance-profile.arn': str,
   'image-id': str,
   'instance-id': str,
   'instance-lifecycle': ('spot',),
   'instance-state-name': (
       'pending',
       'terminated',
       'running',
       'shutting-down',
       'stopping',
       'stopped'),
   'instance.group-id': str,
   'instance.group-name': str,
   'tag-key': str,
   'tag-value': str,
   'tag:': str,
   'vpc-id': str}

　　查询模板中可以制定，region，镜像，实例状态，实例组等等。

  • Filters
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ebs
    Filter based on Volumes attached to Instance
Filter by State Transition Filter
    Filter instances by state (see Instance Lifecycle)
image-age
    Filter on the age of the instance AMI based on the ImageId CreationDate
image
    Filter on the ImageId of the instance
offhour
    Filter for c7n.resources.ec2.InstanceOffHour
onhour
    Filter for c7n.resources.ec2.InstanceOnHour
ephemeral
    Filter for instances that have ephemeral drives
instance-uptime
    Filter based on instance LaunchTime in days
instance-age
    Filter based on the AttachTime of the EBS Volumes in days

　　举个例子，onhour就是基于对实例的运行时间进行过滤的

  • Actions:

    • Start

      1
      Start a set of instances (presumably) already stopped, the start action will automatically filter instances to those that are already in the correct state.
      1
      This example will restart all stopped instances.
      1
      policies:

      • name: ec2-start

        1
        2
        resources: ec2
        actions:
        • start

    • Stop

      Will stop the instances. Stopped instances do not incur EC2 instance costs.

  • Terminate

    1
    Will terminate the instances. Use with caution!

可以根据过滤后的资源，采取行动，对ec2实例进行开启，停止，终止。

  • yaml文件例子：

    1
    policies:

    • name: remediate-extant-keys
      description: |

      1
      2
      Scan through all s3 buckets in an account and ensure all objects
      are encrypted (default to AES256).

      resource: s3
      actions:

      • encrypt-keys

      • name: ec2-require-non-public-and-encrypted-volumes
        resource: ec2
        description: |

        1
        2
        3
        Provision a lambda and cloud watch event target
        that looks at all new instances not in an autoscale group
        and terminates those with unencrypted volumes.

        mode:

        1
        2
        type: cloudtrail   
        events:
        • RunInstances
          filters:

      • Encrypted: false

        1
        actions:
        • terminate

      • name: tag-compliance
        resource: ec2
        description:

        1
        2
        Schedule a resource that does not meet tag compliance policies
        to be stopped in four days.

        filters:

        • State.Name: running
        • “tag:Environment”: absent
        • “tag:AppId”: absent
        • or:
          • “tag:OwnerContact”: absent
          • “tag:DeptID”: absent
            actions:
        • type: mark-for-op
          op: stop
          days: 4
  • 第一个是针对s3进行定义的，是扫描所有s3中的bucket，并将所有对象进行加密
  • 第二是底层调用了aws的lamda和cloud watch，目标是所有新的没有在autoscale group里边的实例，并且终止掉那些未被加密的volume卷。
  • 第三个是进行一个调度任务，找出符合条件tag的资源，然后在4天之内关闭。

　　我的理解，cloud-custodian工具底层基于aws提供的api进行封装的脚本工具，能够进行对aws资源进行查询，过滤，根据筛选出来的资源，采取某种操作的一款“规则引擎”。目前来看custodian跟aws是紧耦合的，它是针对aws资源进行筛选调度，更好的管理资源，提高资源利用率。

发表于   |   分类于   |  

题目大意

　　http://www.spoj.com/problems/MST1，缩减到1的最小步问题：一个数n它的下一步可以减一，或者除以2（可以被2整除的前提下），或者除以3（可以被3整除的前提下）,问n最少要多少步才可以为1？

题目分析

　　简单的dp，但需要注意，由于本题是有多组数据，所以要一次性的把n等于1到20000000的值都求出来保存，然后根据输入的值进行打印

阅读全文 »

发表于   |   分类于   |  

k8s就不用过多介绍了，是Google开源的一款强大的容器管理工具，现在更多的场景是用来管理docker集群，服务编排。

kubernetes主页

这里需要强调一下，本文是基于yum安装的k8s，通过yum安装的k8s的api并不完整，或者说不能使用全部k8s的功能（比如deployment），想在centos上使用k8s全部功能，建议源码编译安装

k8s的一些基本概念

这里部分参考了这篇文章 http://dockone.io/article/932

阅读全文 »