每日一题11.6

标签:mda   头文件   依次   列表   cond   for循环   传递   泛型   返回值   

11.6写题记录

每日一题 ?LeetCode1356

题目

根据数字二进制下1的数目排序

给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。

如果存在多个数字二进制中 1 的数目相同,则必须将它们按照数值大小升序排列。

请你返回排序后的数组。

题解

首先肯定是最简单的想法,把1~10001每个二进制数有几个1打表,再根据1的个数将其重新排序,1数目相等的升序排列。

C++

排序改写了一下sort函数,排序方式改成了题目所要求的。

class Solution {
public:
    int get(int a)
    {
        int n=0;
        for(a;a>0;a/=2)
            n+=a%2;
        return n;
    }
    vector<int> sortByBits(vector<int>& arr)
    {
        vector<int>bit(10001,0);
        for(auto x:arr)
            bit[x]=get(x);
        sort(arr.begin(),arr.end(),[&](int x,int y)
        {
            if(bit[x] < bit[y])
                return true;
            if(bit[x] > bit[y])
                return false;
            return x < y; 
        });
    return arr;
    }
};
Java

Java中没有vector,于是用ArryList和Collections来写。Collection中的sort与C++中的sort作用差不多,但操作对象一般是list。需要重写Comparator接口中的compare函数,该函数返回值大于小于等于0分别代表第一个数大于小于等于第二个数。

class Solution 
{
    public int[] sortByBits(int[] arr) 
    {
        int[] bit = new int[10001];
        List<Integer> list = new ArrayList<Integer>();
        for (int x : arr) 
        {
            list.add(x);
            bit[x] = get(x);
        }
        Collections.sort(list, new Comparator<Integer>() 
        {
            public int compare(Integer x, Integer y) 
            {
                if (bit[x] != bit[y]) 
                    return bit[x] - bit[y];
                else
                    return x - y;
            }
        });
        for (int i = 0; i < arr.length; ++i)
            arr[i] = list.get(i);
        return arr;
    }

    public int get(int x) 
    {
        int res = 0;
        while (x != 0) 
        {
            res += x % 2;
            x /= 2;
        }
        return res;
    }
}

PS:get函数里的for循环有些问题,不能像C++那样直接写for(a;a>0;a/=2)必须要for(int x=a;x>0;x=x/2) 没在网上找到合理的解释,猜测应该跟JVM有关。等看完深入理解JVM来解答。

时间复杂度\(O(nlogn)\)
空间复杂度\(O(n)\)

其他解法:
1.对于get(int a)函数的改进:

\( bit[i]=bit[i>>1]+(i\&1) \)

即 对于一个二进制数来说,它的1的个数等于右移一位的1的个数再加上其最后一位。

2.极(qi)简(ji)四(yin)行(qiao)写法
利用lamda表达式,bitset中的count函数,pair中默认比较大小的方式
\(\lambda\)\(\lambda\)\(\lambda\)\(\lambda\)\(\lambda\)\(\lambda\)\(\lambda\)\(\lambda\)\(\lambda\)\(\lambda\)\(\lambda\)

  • lamda表达式 ——C++11标准
    • 基本语法 [capture](parameters) mutable ->return-type{statement}

      • [capture]:捕捉列表。捕捉列表总是出现在Lambda函数的开始处。实际上,[]是Lambda引出符。编译器根据该引出符判断接下来的代码是否是Lambda函数。捕捉列表能够捕捉上下文中的变量以供Lambda函数使用;
      • (parameters):参数列表。与普通函数的参数列表一致。如果不需要参数传递,则可以连同括号“()”一起省略;
        mutable:mutable修饰符。默认情况下,Lambda函数总是一个const函数,mutable可以取消其常量性。在使用该修饰符时,参数列表不可省略(即使参数为空);
      • ->return-type:返回类型。用追踪返回类型形式声明函数的返回类型。我们可以在不需要返回值的时候也可以连同符号->一起省略。此外,在返回类型明确的情况下,也可以省略该部分,让编译器对返回类型进行推导;
      • {statement}:函数体。内容与普通函数一样,不过除了可以使用参数之外,还可以使用所有捕获的变量。
    • 注意到,lamda表达式,与普通函数,最大的不同,在于拥有捕获列表。捕获列表有一下几种形式

      • [var]表示值传递方式捕捉变量var;
      • [=]表示值传递方式捕捉所有父作用域的变量(包括this);
      • [&var]表示引用传递捕捉变量var;
      • [&]表示引用传递方式捕捉所有父作用域的变量(包括this);
      • [this]表示值传递方式捕捉当前的this指针。
    • 注意的是,捕获列表可以组合,但是不能重复。

事实上,我认为lamda表达式就是一个用来增强代码可读性的函数,在泛型之上。

  • bitset ——C++98标准
    • 头文件和命名空间声明
      #include<bitset>
      using namespace std::bitset
      
    • 类声明时要给出长度值,如
      bitset<32> bitvec
    • 可用unsigned值和string对象来初始化bitset类(string对象可以是完整的也可以是一半,比如:
      string str("1111111000000011001101");
      bitset<32> bitvec5(str, 5, 4); // 4 bits starting at str[5], 1100
      bitset<32> bitvec6(str, str.size() - 4);     // use last 4 characters
    
    • 函数
    bitvec.any()              //有1吗
    bitvec.none()             //有0吗
    bitvec.count()            //1的个数
    bitvec.size()             //位数
    bitvec[pos]               //pos处的二进制位
    bitvec.test(pos)          //pos处的二进制位是1吗
    bitvec.set()              //置1
    bitvec.set(pos)           //pos处置1
    bitvec.reset()            //置0
    bitvec.reset(pos)         //
    bitvec.flip()             //取反
    bitvec.flip(pos)          //
    bitvec.to_ulong()         //返回一个unsigned long值
    os << bitvec              //位集输出到os流
    
  • pair ——C++98标准
    • 将2个数据合成一组数据的类,如map中的键值对。内部实现是一个结构体,两个成员变量是first和second。
    • 头文件和类模板
    #include <utility>
    template<class T1,class T2> struct pair
    
    • 函数
    pair<T1, T2> p1;            //创建一个空的pair对象(使用默认构造),它的两个元素分别是T1和T2类型,采用值初始化。
    pair<T1, T2> p1(v1, v2);    //创建一个pair对象,它的两个元素分别是T1和T2类型,其中first成员初始化为v1,second成员初始化为v2。
    make_pair(v1, v2);          // 以v1和v2的值创建一个新的pair对象,其元素类型分别是v1和v2的类型。
    p1 < p2;                    // 两个pair对象间的小于运算,其定义遵循字典次序:如 p1.first < p2.first 或者 !(p2.first < p1.first) && (p1.second < p2.second) 则返回true。
    p1 == p2;                  // 如果两个对象的first和second依次相等,则这两个对象相等;该运算使用元素的==操作符。
    p1.first;                   // 返回对象p1中名为first的公有数据成员
    p1.second;                 // 返回对象p1中名为second的公有数据成员
    
    • 创建pair对象时,必须提供两个类型名,两个类型名不必相同。定义时可以初始化。
    • pair对象作返回值时可以用std::tie来接收,比如:
    std::pair<std::string, int> getPreson() 
    {
        return std::make_pair("Sven", 25);
    }
    
    int main(int argc, char **argv) 
    {
        std::string name;
        int ages;
        std::tie(name, ages) = getPreson();
        std::cout << "name: " << name << ", ages: " << ages << std::endl;
        return 0;
    }
    
    • 我觉得pair是一个复杂的,对象化的结构体,具体应用还更复杂些,有空看看源码再回来补充。

题解:C++

class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
        sort(arr.begin(), arr.end(), [&](int a, int b){
            return make_pair(bitset<32>(a).count(), a) < make_pair(bitset<32>(b).count(), b);
        });
        return arr;
    }
};

class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
        sort(arr.begin(), arr.end(), [&](int a, int b){
            return pair{__builtin_popcount(a), a} < pair{__builtin_popcount(b), b};
        });
        return arr;
    }
};

来源:LeetCode:Monologue-S

总结

这个题算是比较简单的排序和位运算的题目,但是我位运算一直都比较辣鸡(准确地说,这是我动手写的第一道位运算题目orz),所以开始的过程也有些艰难,20行代码大概出了三四个bug,看题解也有些费劲,哐哐一顿查QAQ。但其实思路还挺清晰的。这个题目时间复杂度下界也一定就是\(O(n)\)了,毕竟每一位都要扫描到,空间复杂度下界是\(O(1)\)。优化主要在于对空间的优化和代码的可读性。

每日一题11.6

标签:mda   头文件   依次   列表   cond   for循环   传递   泛型   返回值   

原文地址:https://www.cnblogs.com/Oooval/p/13940643.html

版权声明:完美者 发表于 2020-11-07 17:33:05。
转载请注明:每日一题11.6 | 完美导航

暂无评论

暂无评论...