精华内容
下载资源
问答
  • 数据结构中关于线性表应用,这是一个关于两个集合异或的c语言版程序源代码,
  • 取两个字典key进行异或 a= {"i":1,"b":2} b = {"i":2} print(a.keys()) print(b.keys()) result = a.keys() ^ b.keys() print(result) 结果 dict_keys(['i', 'b']) dict_keys(['i']) {'b'} 可见可去掉了重复 ...

    所谓异或 相同为0,不同为1
    取两个字典的key进行异或

    a= {"i":1,"b":2}
    b = {"i":2}
    print(a.keys())
    print(b.keys())
    result = a.keys() ^ b.keys()
    print(result)
    

    结果

    dict_keys(['i', 'b'])
    dict_keys(['i'])
    {'b'}
    

    可见可去掉了重复的
    但取字典的值进行异或却不可以

    a= {"i":1,"b":2}
    b = {"i":2}
    print(a.values())
    print(b.values())
    print(a.values()^b.values())
    

    结果是不可以的

    dict_values([1, 2])
    dict_values([2])
    Traceback (most recent call last):
      File "F:/python/pythonProject1/dict.py", line 31, in <module>
        print(a.values()^b.values())
    TypeError: unsupported operand type(s) for ^: 'dict_values' and 'dict_values'
    

    那么字符串呢 是不可以的

    d = "i"
    c = "a"
    print(d^c)
    

    str结果

    `TypeError: unsupported operand type(s) for ^: 'str' and 'str
    

    列表也不可以

    d = ["i",2]
    c = ["i",4]
    print(d^c)
    

    列表结果

    TypeError: unsupported operand type(s) for ^: 'list' and 'list'
    

    元组不可以

    d = ("$", 4,)
    c = ("i",4,)
    print(c^d)
    

    元组结果

    TypeError: unsupported operand type(s) for ^: 'tuple' and 'tuple'
    

    集合可以异或!!!!!

    c = {"apple", "banana", "cherry"}
    d = {"apple1", "banana", "cherry"}
    print(c^d)
    
    

    结果异或成功!!

    {'apple1', 'apple'}
    

    根据归纳法
    字典的key(键) 和集合中的元素都具有唯一性、
    因此可以使用异或运算

    展开全文
  • 1.Trie字符串统计题目要求: 维护一个字符串集合,支持两种操作: ...对于每个询问指令”Q x”,都要输出一个整数作为结果,表示x在集合中出现次数。 每个结果占一行。 数据范围 1≤N≤2∗10^4 输入样例: 5 I

    1.Trie字符串统计

    维护一个字符串集合,支持两种操作:
    “I x”向集合中插入一个字符串x;
    “Q x”询问一个字符串在集合中出现了多少次。
    共有N个操作,输入的字符串总长度不超过 105,字符串仅包含小写英文字母。

    输入格式
    第一行包含整数N,表示操作数。
    接下来N行,每行包含一个操作指令,指令为”I x”或”Q x”中的一种。

    输出格式
    对于每个询问指令”Q x”,都要输出一个整数作为结果,表示x在集合中出现的次数。
    每个结果占一行。

    数据范围
    1≤N≤2∗10^4
    输入样例:
    5
    I abc
    Q abc
    Q ab
    I ab
    Q ab
    输出样例:
    1
    0
    1

    算法关键点:(两个数组和一个变量的理解)
    idx 表示的是当前正在处理的结点编号。
    son[N][26] 存放的是该节点所有的儿子即子节点对应的idx, 第一维是父节点对应的idx, 第二维是子节点的值(以a为例, 存放的是’a’ -‘a’=0)。
    cnt[N] 存放的是以当前点结尾的字符串个数。
    注意:下标是0的点,既是根节点,又是空节点。

    程序代码:

    #include <iostream>
    using namespace std;
    
    const int N = 100010;
    int son[N][26], cnt[N], idx;
    char str[N];
    
    void insert(char str[])
    {
        int p = 0; 
        for(int i = 0; str[i]; i ++)
        {
            int u = str[i] -'a';
            if(!son[p][u])  son[p][u] = ++ idx;//创建新节点
            p = son[p][u];
        }
        cnt[p]++;
    }
    
    int query(char str[])
    {
        int p = 0; 
        for(int i = 0; str[i]; i ++)
        {
            int u = str[i] -'a';
            if(!son[p][u])  return 0;
            p = son[p][u];
        }
        return cnt[p];
    }
    
    int main()
    {
        int n;
        cin >> n;
        while(n --)
        {
            char op[2];
            scanf("%s%s", op, str);
            if(op[0] == 'I')  insert(str);
            else  printf("%d\n", query(str));
        }
        return 0;
    }
    

    2.最大异或对

    在给定的N个整数A1,A2……AN中选出两个进行xor(异或)运算,得到的结果最大是多少?

    输入格式
    第一行输入一个整数N。
    第二行输入N个整数A1~AN。

    输出格式
    输出一个整数表示答案。

    数据范围
    1≤N≤105,
    0≤Ai<2^31
    输入样例:
    3
    1 2 3
    输出样例:
    3

    算法的基本思路:
    将每个数以二进制方式存入字典树,找的时候从最高位去找有无该位的异。异或最大的情况就是每位数上的数都不一样。若有异,则走与该位数相反的一边;若没有,则走相同的一边。

    程序代码:

    #include <iostream>
    using namespace std;
    
    const int N = 100010, M = 3000000;
    int son[M][2], a[N], idx;
    
    void insert(int x)
    {
        int p = 0;
        for(int i = 30; i >= 0; i --)
        {
            int &s = son[p][x >> i & 1];
            if(!s)  s = ++ idx;
            p = s;
        }
    }
    
    int query(int x)
    {
        int p = 0, res = 0;
        for(int i = 30; ~i; i --)//~i相当于i >= 0
        {
            int s = x >> i & 1;//将x的第i位数(0 或者1)写入s
            if(son[p][!s])
            {
                res += 1 << i;
                p = son[p][!s];
            }
            else p = son[p][s];
        }
        return res;
    }
    
    int main()
    {
        int n;
        cin >> n;
        for(int i = 0; i < n; i ++)
        {
            cin >> a[i];
            insert(a[i]);
        }
        
        int res = 0;
        for(int i = 0; i < n; i ++ )  res = max(res, query(a[i]));
        
        cout << res <<endl;
        
        return 0;
    }
    
    展开全文
  • 两个方法不同点在于采用了不同的数据结构来存储按位前缀。第一个方法在给定测试集下执行速度更快,但第二种方法更加普适,更加简单。 异或运算性质 解决这个问题,我们首先需要利用异或运算一个性质: 如果...

    题目

    地址

    image-20200630205029290

    分析

    题目要求 O(N)时间复杂度,下面会讨论两种典型的 O(N) 复杂度解法。

    1. 利用哈希集合存储按位前缀。
    2. 利用字典树存储按位前缀。

    这两种解法背后的思想是一样的,都是先将整数转化成二进制形式,再从最左侧的比特位开始逐一处理来构建最大异或值。两个方法的不同点在于采用了不同的数据结构来存储按位前缀。第一个方法在给定的测试集下执行速度更快,但第二种方法更加普适,更加简单。

    异或运算的性质

    解决这个问题,我们首先需要利用异或运算的一个性质:

    如果 a ^ b = c 成立,那么a ^ c = bb ^ c = a 均成立。

    如果有三个数,满足其中两个数的异或值等于另一个值,那么这三个数的顺序可以任意调换

    (说明:利用这条性质,可以不使用第 3 个变量而交换两个变量的值。)

    • 那么如何理解这个性质呢?因为异或运算其实就是 二进制下不进位的加法,你不妨自己举几个例子,在草稿纸上验证一下。

    如何应用到本题?

    这道题找最大值的思路是这样的:因为两两异或可以得到一个值,在所有的两两异或得到的值中,一定有一个最大值,我们推测这个最大值应该是什么样的?即根据“最大值”的存在性解题(一定存在)。在这里要强调一下:

    我们只用关心这个最大的异或值需要满足什么性质,进而推出这个最大值是什么,而不必关心这个异或值是由哪两个数得来的。

    (上面这句话很重要,如果读者一开始看不明白下面的思考,不妨多看几遍我上面写的这句话。)

    于是有如下思考:

    1、二进制下,我们希望一个数尽可能大,即希望越高位上越能够出现“1”,这样这个数就是所求的最大数,这是贪心算法的思想。

    2、于是,我们可以从最高位开始,到最低位,首先假设高位是 “1”,把这 n 个数全部遍历一遍,看看这一位是不是真的可以是“1”,否则这一位就得是“0”,判断的依据是上面“异或运算的性质”,即下面的第 3 点;

    3、如果 a ^ b = max 成立 ,max 表示当前得到的“最大值”,那么一定有 max ^ b = a 成立。我们可以先假设当前数位上的值为 “1”,再把当前得到的数与这个 n 个数的 前缀(因为是从高位到低位看,所以称为“前缀”)进行异或运算,放在一个哈希表中,再依次把所有 前缀 与这个假设的“最大值”进行异或以后得到的结果放到哈希表里查询一下,如果查得到,就说明这个数位上可以是“1”,否则就只能是 0(看起来很晕,可以看代码理解)。

    一种极端的情况是,这 n 个数在某一个数位上全部是 0 ,那么任意两个数异或以后都只能是 0,那么假设当前数位是 1 这件事情就不成立。

    4、如何得到前缀,可以用掩码(mask),掩码可以进行如下构造,将掩码与原数依次进行 “与” 运算,就能得到前缀。

    10000000000000000000000000000000
    11000000000000000000000000000000
    11100000000000000000000000000000
    11110000000000000000000000000000
    11111000000000000000000000000000
    11111100000000000000000000000000
    11111110000000000000000000000000
    11111111000000000000000000000000
    11111111100000000000000000000000
    11111111110000000000000000000000
    11111111111000000000000000000000
    11111111111100000000000000000000
    11111111111110000000000000000000
    11111111111111000000000000000000
    11111111111111100000000000000000
    11111111111111110000000000000000
    11111111111111111000000000000000
    11111111111111111100000000000000
    11111111111111111110000000000000
    11111111111111111111000000000000
    11111111111111111111100000000000
    11111111111111111111110000000000
    11111111111111111111111000000000
    11111111111111111111111100000000
    11111111111111111111111110000000
    11111111111111111111111111000000
    11111111111111111111111111100000
    11111111111111111111111111110000
    11111111111111111111111111111000
    11111111111111111111111111111100
    11111111111111111111111111111110
    11111111111111111111111111111111
    

    图片解释

    以题目中的数组 [3, 10, 5, 25, 2, 8] 为例,下面讲解这个最大的两两异或值是如何得到的,这里为了方便演示,只展示一个数二进制的低 8 位。

    img

    img

    img

    img

    img

    img

    方法一:利用哈希集合存储按位前缀

    参考代码:

    import java.util.HashSet;
    import java.util.Set;
    
    public class Solution {
    
        // 先确定高位,再确定低位(有点贪心算法的意思),才能保证这道题的最大性质
        // 一位接着一位去确定这个数位的大小
        // 利用性质: a ^ b = c ,则 a ^ c = b,且 b ^ c = a
    
        public int findMaximumXOR(int[] nums) {
            int res = 0;
            int mask = 0;
            for (int i = 30; i >= 0; i--) {
                // 注意点1:注意保留前缀的方法,mask 是这样得来的
                // 用异或也是可以的 mask = mask ^ (1 << i);
                mask = mask | (1 << i);
    
                // System.out.println(Integer.toBinaryString(mask));
                Set<Integer> set = new HashSet<>();
                for (int num : nums) {
                    // 注意点2:这里使用 & ,保留前缀的意思(从高位到低位)
                    set.add(num & mask);
                }
    
                // 这里先假定第 n 位为 1 ,前 n-1 位 res 为之前迭代求得
                int temp = res | (1 << i);
                for (Integer prefix : set) {
                    if (set.contains(prefix ^ temp)) {
                        res = temp;
                        break;
                    }
                }
            }
            return res;
        }
    }
    

    复杂度分析:

    • 时间复杂度:O(N),把整个数组看了 31 次,即 O(31N) = O(N)。
    • 空间复杂度:O(n),这里的 n是哈希表的长度,具体长度是多少,与输入的规模、扩容策略、负载因子和冲突策略等有关。例如 Java 在 JDK 1.8 以后,当哈希值冲突的时候,先把冲突的元素放在单链表上,当冲突的键值大于 8 的时候,再转成红黑树。

    方法二:逐位字典树

    为什么哈希集合不适合用来存储按位前缀?

    对于那些一定不能得到最终解的路径可以通过剪枝来舍弃,但是用哈希集合来存储按位前缀是没法做剪枝优化的。举个例子,两次异或操作之后为了得到 (11***)_2(11∗∗∗)2,显然只能让 25 和 最左侧为 0000 前缀的数字(2,3, 5)组合。

    3=(00011)23 = (00011)_2

    10=(01010)210 = (01010)_2

    5=(00101)25 = (00101)_2

    25=(11001)225 = (11001)_2

    2=(00010)22 = (00010)_2

    8=(01000)28 = (01000)_2

    因此,在计算第三位比特的时候,我们就没有必要计算所有可能的按位前缀组合了。光看前两位就知道一些组合已经不能得到最大异或值了。

    3=(000)23 = (000**)_2

    10=(010)210 = (010**)_2

    5=(001)25 = (001**)_2

    25=(110)225 = (110**)_2

    2=(000)22 = (000**)_2

    8=(010)28 = (010**)_2

    为了方便剪枝,我们要采用一种类树的存储结构。

    按位字典树:这是什么?怎么构建?

    假设数组为 [3, 10, 5, 25, 2],据此来构建按位字典树。

    3=(00011)23 = (00011)_2

    10=(01010)210 = (01010)_2

    5=(00101)25 = (00101)_2

    25=(11001)225 = (11001)_2

    2=(00010)22 = (00010)_2

    fig

    字典树中每条根节点到叶节点的路径都代表了 nums 中的一个整数(二进制形式),举个例子,0 -> 0 -> 0 -> 1 -> 1 表示 3。与之前的方法一样,所有二进制的长度都为 LL,其中 L=1+[log2M]L = 1 + [\log_2 M],这里 M 为 nums 中的最大数值。显然字典树的深度也为 L,同时叶子节点也都在同一层。

    字典树非常适合用来存储整数的二进制形式,例如存储 2(00010) 和 3(00011),其中 5 个比特位中有 4 个比特位都是相同的。字典树的构建方式也很简单,就是嵌套哈希表。在每一步,判断要增加的孩子节点(0,1)是否已经存在,如果存在就直接访问该孩子节点。如果不存在,需要先新增孩子节点再访问。

    TrieNode trie = new TrieNode();
    for (String num : strNums) {
      TrieNode node = trie;
      for (Character bit : num.toCharArray()) { 
        if (node.children.containsKey(bit)) {
          node = node.children.get(bit);
        } else {
          TrieNode newNode = new TrieNode();
          node.children.put(bit, newNode);
          node = newNode;
        }
      }  
    }
    

    字典树中给定数的最大异或值

    为了最大化异或值,需要在每一步找到当前比特值的互补比特值。下图展示了 25 在每一步要怎么走才能得到最大异或值:

    fig

    实现方式也很简单:

    • 如果当前比特值存在互补比特值,访问具有互补比特值的孩子节点,并在异或值最右侧附加一个 1。
    • 如果不存在,直接访问具有当前比特值的孩子节点,并在异或值最右侧附加一个 0。
    TrieNode trie = new TrieNode();
    for (String num : strNums) {
      TrieNode xorNode = trie;
      int currXor = 0;
      for (Character bit : num.toCharArray()) {
        Character toggledBit = bit == '1' ? '0' : '1';
        if (xorNode.children.containsKey(toggledBit)) {
          currXor = (currXor << 1) | 1;
          xorNode = xorNode.children.get(toggledBit);
        } else {
          currXor = currXor << 1;
          xorNode = xorNode.children.get(bit);
        }
      }
    }
    

    算法

    算法结构如下所示:

    • 在按位字典树中插入数字。
    • 找到插入数字在字典树中所能得到的最大异或值。

    算法的具体实现如下所示:

    • 将所有数字转化成二进制形式。
    • 将数字的二进制形式加入字典树,同时计算该数字在字典树中所能得到的最大异或值。再用该数字的最大异或值尝试性更新 max_xor
    • 返回 max_xor
    class TrieNode {
      HashMap<Character, TrieNode> children = new HashMap<Character, TrieNode>();
      public TrieNode() {}
    }
    
    class Solution {
      public int findMaximumXOR(int[] nums) {
        // Compute length L of max number in a binary representation
        int maxNum = nums[0];
        for(int num : nums) maxNum = Math.max(maxNum, num);
        int L = (Integer.toBinaryString(maxNum)).length();
    
        // zero left-padding to ensure L bits for each number
        int n = nums.length, bitmask = 1 << L;
        String [] strNums = new String[n];
        for(int i = 0; i < n; ++i) {
          strNums[i] = Integer.toBinaryString(bitmask | nums[i]).substring(1);
        }
    
        TrieNode trie = new TrieNode();
        int maxXor = 0;
        for (String num : strNums) {
          TrieNode node = trie, xorNode = trie;
          int currXor = 0;
          for (Character bit : num.toCharArray()) {
            // insert new number in trie  
            if (node.children.containsKey(bit)) {
              node = node.children.get(bit);
            } else {
              TrieNode newNode = new TrieNode();
              node.children.put(bit, newNode);
              node = newNode;
            }
    
            // compute max xor of that new number 
            // with all previously inserted
            Character toggledBit = bit == '1' ? '0' : '1';
            if (xorNode.children.containsKey(toggledBit)) {
              currXor = (currXor << 1) | 1;
              xorNode = xorNode.children.get(toggledBit);
            } else {
              currXor = currXor << 1;
              xorNode = xorNode.children.get(bit);
            }
          }
          maxXor = Math.max(maxXor, currXor);
        }
    
        return maxXor;
      }
    }
    

    复杂度分析

    • 时间复杂度:O(N)。在字典树插入一个数的时间复杂度为 O(L)O(L),找到一个数的最大异或值时间复杂度也为 O(L)O(L)。其中 L=1+[log2M]L = 1 + [\log_2 M],M 为数组中的最大数值,这里可以当做一个常量。因此最终时间复杂度为 O(N)。
    • 空间复杂度:O(1)。维护字典树最多需要$ O(2^L) = O(M)$ 的空间,但由于输入的限制,这里的 L 和 M 可以当做常数。
    展开全文
  • 集合有交集、并集、差集、异或、判断子集等运算操作。函数用来保存可执行代码,在需要时候进行多次调用;用def关键字创建函数;可以定义形参,在调用时也必须传递实参。可以为形参指定一个默认值;位置传参就是...

    一、集合的基本操作

    集合,即set,和列表基本一致。
    不同点为:
    1.集合只能存储不可变对象
    2.集合中存储的对象是无序的,不是按照元素插入的顺序来保存;
    3.集合中不能出现重复的元素。

    1.创建集合

    • 方式一:使用{}来创建集合

      s = {1,2,3,4}
      print(s,type(s))
      

      打印

      {1, 2, 3, 4} <class 'set'>
      

      当集合中插入新数据时

      s = {10,1,2,3,4}
      print(s,type(s))
      

      打印

      {1, 2, 3, 4, 10} <class 'set'>
      

      结果不是按照插入的顺序来保存的,即无序。
      当出现重复元素时

      s = {10,1,2,3,4,1,1,3,3,4,4,4}
      print(s,type(s))
      

      打印

      {1, 2, 3, 4, 10} <class 'set'>
      

      即会过滤掉重复的元素。
      当集合中出现可变对象时,会报错

      s = {[10,1,2,3,4],1,1,3,3,4,4,4}
      print(s,type(s))
      

      打印

      TypeError: unhashable type: 'list'
      
    • 方式二:用set()函数来创建集合
      创建空的字典用{},但是创建空的集合不能用{},要用set()
      set()函数可以将序列和字典转化成集合。

      s = set([10,1,2,3,4,1,1,2,2])
      print(s,type(s))
      

      打印

      {1, 2, 3, 4, 10} <class 'set'>
      

      又如

      s = set('Python')
      print(s,type(s))
      

      打印

      {'y', 'n', 'o', 'P', 'h', 't'} <class 'set'>
      

      当参数为字典时,

      s = set({'a':'Python','b':'Java'})
      print(s,type(s))
      

      打印

      {'b', 'a'} <class 'set'>
      

      ※使用set()函数将字典转化为集合的时候,只会包含字典的键。

    2.集合的访问

    集合不能通过索引访问,会报错

    s = {1,2,'a','b','3'}
    print(s[0])
    

    打印

    TypeError: 'set' object is not subscriptable
    

    可将集合转化成列表,再访问,如

    s = {1,2,'a','b','3'}
    s = list(s)
    print(s[0])
    

    打印

    1
    

    3.集合的使用

    (1)in和not in
    用来检查集合中的元素,结果返回一个布尔值

    s = {1,2,'a','b','3'}
    print('b' in s)
    

    打印

    True
    

    (2)len()
    获取集合中元素的个数(长度)

    s = {1,2,'a','b','3'}
    print(len(s))
    

    打印5

    -(3)add()
    可以向集合中添加元素

    s = {1,2,'a','b','3'}
    s.add(3)
    s.add(4)
    print(s)
    

    打印

    {'a', 1, 2, '3', 3, 4, 'b'}
    

    (4)update():
    将一个集合中的元素添加到当前集合中

    s = {1,2,'a','b','3'}
    s2 = set('Python')
    s.update(s2)
    print(s)
    

    打印

    {'3', 1, 2, 'o', 'b', 't', 'y', 'P', 'n', 'a', 'h'}
    

    (5)pop():
    随机删除集合中的一个元素,返回值为被删除的元素。

    s = {1,2,'a','b','3'}
    result = s.pop()
    print(s)
    print(result)
    

    打印

    {'a', 2, 'b', '3'}
    1
    

    (6)remove():
    删除集合中的指定元素

    s = {1,2,'a','b','3'}
    s.remove('b')
    print(s)
    

    打印

    {1, 2, '3', 'a'}
    

    (7)clear()
    清空集合

    s = {1,2,'a','b','3'}
    s.clear()
    print(s)
    打印
    
    set()
    

    本人本科学生,热爱Python、爬虫、数据分析和大数据等,愿与各位读者一起交流,建了一个QQ交流群,群里有一些Python和其他领域的学习资料,也有很多志同道合的朋友,可以点击 Python极客部落963624318 进群获取资料和交流,也可以扫码加群:
    Python极客部落群聊二维码

    二、集合的基本运算

    1.交集运算&

    s = {1,2,3,4,5}
    s2 = {3,4,5,6,7}
    result = s&s2
    print(result)
    

    打印

    {3, 4, 5}
    

    2.并集运算|

    s = {1,2,3,4,5}
    s2 = {3,4,5,6,7}
    result = s|s2
    print(result)
    

    打印

    {1, 2, 3, 4, 5, 6, 7}
    

    3.差集运算-

    s = {1,2,3,4,5}
    s2 = {3,4,5,6,7}
    result = s-s2
    print(result)
    

    打印

    {1, 2}
    

    当s和s2交换顺序时

    s = {1,2,3,4,5}
    s2 = {3,4,5,6,7}
    result = s2-s
    print(result)
    

    打印

    {6, 7}
    

    4.异或集^

    s = {1,2,3,4,5}
    s2 = {3,4,5,6,7}
    result = s2^s
    print(result)
    

    打印

    {1, 2, 6, 7}
    

    5.<=

    检查一个集合是否是另一个集合的子集,结果返回一个布尔值

    a = {1,2,3}
    b = {1,2,3,4,5}
    result = a <= b
    print(result)
    

    打印

    True
    

    6.<

    检查一个集合是否是另一个集合的真子集,结果返回一个布尔值

    a = {1,2,3}
    b = {1,2,3}
    result = a < b
    print(result)
    

    打印

    False
    

    7.>=

    检查一个集合是否是另一个集合的超集,结果返回一个布尔值

    a = {1,2,3}
    b = {1,2,3,4,5}
    result = b >= a
    print(result)
    

    打印

    True
    

    8.>

    检查一个集合是否是另一个集合的真超集,结果返回一个布尔值

    a = {1,2,3}
    b = {1,2,3}
    result = a > b
    print(result)
    

    打印

    False
    

    三、函数的介绍和基本使用

    1.定义

    表现形式:function
    对象是内存中专门用来存储数据的一块区域。
    函数也是一个对象

    函数出现的原因:
    便于程序维护;
    便于共享使用。

    函数可以用来保存一些可执行的代码,并且在需要的时候对这些语句进行多次调用。
    函数只有被调用才会被使用。

    2.创建函数

    语法:

    def 函数名([形参1,形参2,形参2,...]):
        代码块
    

    例如:

    def fn():
        print('First Function')
    print(fn)
    

    打印

    <function fn at 0x000002292FF23F78>
    

    即为函数保存的内存地址。
    被调用时,

    def fn():
        print('First Function')
    fn()
    

    打印

    First Function
    

    上例中fn是函数对象,fn()调用函数。

    3.函数的参数

    定义函数时,可以在后边的括号里定义数量不定的形参,形参之间用逗号隔开。
    形参,即形式参数,相当于在函数内部定义了变量,但是并没有赋值。
    实参,即实际参数,函数定义时指定了形参,那么调用函数的时候也必须传递实参,实参将会赋值给对应的形参,有几个形参就传几个实参。

    def sum(a,b):
        print('a =',a)
        print('b =',b)
    sum(11,23)
    

    打印

    a = 11
    b = 23
    

    又如

    def sum(a,b):
        print('a + b =',a+b)
    sum(11,23)
    

    打印

    a + b = 34
    

    四、函数参数的使用

    1.参数默认值

    定义形参时,可以为形参指定一个默认值:
    指定了默认值以后,如果用户传递了参数,默认值不会起作用;
    如果用户没有传递,则默认值生效。
    指定默认值时,

    def fn(a,b,c=10):
        print('a =',a)
        print('b =',b)
        print('c =',c)
    fn(1,2,3)
    

    打印

    a = 1
    b = 2
    c = 3
    

    c不为默认值10,而是指定的值3。
    未指定默认值时,

    def fn(a,b,c=10):
        print('a =',a)
        print('b =',b)
        print('c =',c)
    fn(1,2)
    

    打印

    a = 1
    b = 2
    c = 10
    

    c为默认值10。

    2.位置传参和关键字传参

    位置传参就是将对应位置的实参传递给对应位置的形参。
    也可以不按照形参定义的顺序去传参,而根据参数名来传递参数,即关键字传参

    关键字传参练习如下:

    def fn(a,b,c=10):
        print('a =',a)
        print('b =',b)
        print('c =',c)
    fn(b=2,a=3,c=5)
    

    打印

    a = 3
    b = 2
    c = 5
    

    关键字传参可以和位置传参混合使用:

    def fn(a,b,c=10):
        print('a =',a)
        print('b =',b)
        print('c =',c)
    fn(2,1,c=5)
    

    打印

    a = 2
    b = 1
    c = 5
    

    混合使用时,位置参数必须位于关键字参数前面,并且位置参数个数要与非默认值的参数个数一致,否则会报错。

    3.实参的类型

    函数在调用的时候,解释器不会检查实参的类型,实参类型可以是任意的对象。

    def fn(a,b,c=10):
        print('a =',a)
        print('b =',b)
        print('c =',c)
    
    def fn2(a):
        print('a =',a)
    fn2(fn)
    打印
    
    a = <function fn at 0x000002323DD53EE8>
    

    又如

    def fn(a,b):
        print(a+b)
    fn('123',456)
    

    打印

    TypeError: can only concatenate str (not "int") to str
    

    参数类型不同,报错
    再如

    def fn(a):
        a = 30
        print('a =',a)
    c = 10
    fn(c)
    print('c =',c)
    

    打印

    a = 30
    c = 10
    

    易知,在函数中对形参进行赋值不会影响其他的变量。

    def fn(a):
        a[0] = 5
        print('a = ',a)
    c = [1,2,3]
    fn(c)
    print('c =',c)
    

    打印

    a =  [5, 2, 3]
    c = [5, 2, 3]
    

    解释:形参在执行时,通过形参去修改对象,会影响到指向该对象的变量。
    如不希望改a影响到c,可以用copy()方法。

    def fn(a):
        a[0] = 5
        print('a = ',a)
    c = [1,2,3]
    fn(c.copy())
    print('c =',c)
    

    打印

    a =  [5, 2, 3]
    c = [1, 2, 3]
    

    还有一种方法

    def fn(a):
        a[0] = 5
        print('a = ',a)
    c = [1,2,3]
    fn(c[:])
    print('c =',c)
    

    输出结果相同。
    总结:传递的是可变对象时,但又不希望函数内部的操作影响到函数外部,可以传递参数的副本,不可变对象不用管。

    五、不定长参数和参数解包

    1.不定长参数

    在定义函数时,可以在形参前面加一个*,这样这个形参将会获取到所有的实参值,并将所有形参保存到一个元组中。

    def sum(*a):
        print(a,type(a))
    sum()
    

    打印

    () <class 'tuple'>
    

    有多个参数时,

    def sum(*a):
        print(a,type(a))
    sum(1,2,3,4,5,6)
    

    打印

    (1, 2, 3, 4, 5, 6) <class 'tuple'>
    

    即参数的打包过程,将所有参数保存到一个元组中。

    def sum(*a):
        r = 0
        for n in a:
            r += n
        print(r)
    sum(1,2,3,4,5,6)
    

    即实现求多个数的和,结果为21。

    def fn(a,b,*c):
        print('a =',a)
        print('b =',b)
        print('c =',c)
    fn(1,2,3,4,5,6)
    

    打印

    a = 1
    b = 2
    c = (3, 4, 5, 6)
    

    可变长参数不是必须位于最后,但是带*的参数后的参数必须以关键字的形式传参。

    def fn(*a,b,c):
        print('a =',a)
        print('b =',b)
        print('c =',c)
    fn(1,2,3,4,b=5,c=6)
    

    打印

    a = (1, 2, 3, 4)
    b = 5
    c = 6
    

    如果在形参的开头直接为*,则要求所有的参数要以关键字形式传递。

    def fn(*,a,b,c):
        print('a =',a)
        print('b =',b)
        print('c =',c)
    fn(a=4,b=5,c=6)
    

    打印

    a = 4
    b = 5
    c = 6
    

    形参可以接受其他的关键字参数,它会将这些参数统一保存到一个字典中,字典的key是参数名,value是参数的值,形参只能有一个,并且必须位于最后面。

    def fn(a,b,**c):
        print('a =',a)
        print('b =',b)
        print('c =',c)
    fn(a=4,b=5,d=1,e=2,f=3)
    

    打印

    a = 4
    b = 5
    c = {'d': 1, 'e': 2, 'f': 3}
    

    2.参数解包

    参数解包是将序列中的参数化为单个参数传入,要求序列中的元素个数必须和形参一致。

    def fn(a,b,c):
        print('a =',a)
        print('b =',b)
        print('c =',c)
    t = (1,2,3)
    fn(*t)
    

    打印

    a = 1
    b = 2
    c = 3
    

    并且可传入字典解包

    def fn(a,b,c):
        print('a =',a)
        print('b =',b)
        print('c =',c)
    d = {'a':1,'b':2,'c':3}
    fn(**d)
    

    打印

    a = 1
    b = 2
    c = 3
    
    展开全文
  • Java中,HashMap是我们经常使用到的集合,其底层数据结构是数组+链表+红黑树。当向一个map添加元素时map.put("a","b"),有以下几个过程:计算keyhashCode值将keyhashCode值高低16位异或得出codeValue将codeValue...
  • 数据结构

    2017-12-07 20:22:00
    线性结构集合无序,不可索引和切片。 可用set('abc')等方式生成 可用操作: <,>,>=,==,!= :指结合子集,超集等(注意,此处a>b和a < b都为False,不能说明其相等) |,&,-,^ : 与或,...
  • trie树 最大异或

    2021-05-14 00:02:11
    作用:用来快速的存储和查找字符串集合的数据结构 本质根据字符串的每个字符作为节点建树 #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using ...
  • 高效的存储和查找字符串集合的数据结构 int son[maxn][26],cnt[maxn],idx; void add(char *str){///将新的字符串插入到字典树里 int p=0,len=strlen(str); for(int i=0;i<len;i++){ ///遍历字符串的每一个...
  • java数据结构之Bitset

    2018-03-25 00:22:16
    这是一种位集合,操作一组布尔值时候可以通过(或or,与and,异或xor)等方法快速改变其组内某一部分值BitSet bits1 = new BitSet(10);BitSet bits2 = new BitSet(10);for(int i=1;i&lt;21;i++) { if(i%2==0) ...
  • 关于python的集合操作

    2020-09-08 10:53:19
    集合类型数据结构包括可变集合与不可变集合。 创建可变集合的方式有: (1)使用花括号创建(传入元素必须是不可变的) set = {'A','B','C'} (2)使用函数set创建 set1 = set([1,2,3]) #输出为{1,23} 创建不可变...
  • 集合可以有效表示布尔值的集合。 埃拉托斯特尼筛法 筛选掉从是其他数(从2开始)倍数那些数,最后剩下数都是素数。 处理二进制 1.按位运算符 And(与) Or(或) Not(非) Xor(异或) 两个运算数中只有一...
  • HashSet集合1.带着问题学习?...数据结构和算法,javaSE面向对象,进制转换,以及java一些运算符,比如位移,异或等等。 理解源码方式就是打断点一步一步跟踪,看源代码是如何执行,遇到看不懂
  • 谈一下HashMap的数据结构2.hash冲突是什么,该如何避免3.HashMap中如何设计hash算法4.hash()扰动函数为什么将hashcode右移16位?为什么要采用异或运算5.为什么JDK1.8中HashMap要使用红黑树这个数据结构来存储...
  • matlab 集合操作

    千次阅读 2016-08-01 00:03:57
    matlab 并未提供专门的表示集合的数据结构,仍然使用矩阵进行表示(unique() 函数去重)。 intersect(A, B):交集 union(A, B):并集 setdiff(A, B):差集(在A不在B) setxor(A, B):异或( = setdiff(union(A, B),...
  • HashMap以键值对(key-value)为单位,存储在数组的数据结构中,在put()元素时候,是根据hash算法计算hashCode,源码中使用 (n-1) &amp; hash 计算存储下标 其中hash使用 key.hashCode()) ^ (h &gt;&...
  • 线性基

    2019-09-28 15:21:21
    线性基是一种数据结构,可以在\(logn\)的时间内计算出所有数的异或最大和以及异或最 小值。 1.线性基里的数都由原数异或得来 2.线性基里任意几个数异或起来的结果都不相等。 3.线性基异或出来的结果的一个集合,与原...
  • HDU - 4825 字典树

    2017-11-07 22:20:29
    这个问题一开始是在不明白异或思想题目给数据量让我知道不用数据结构代码都是瞎BB。。。。 求一个数在一个集合最大异或,首先要了解一下异或思想 异或:相同为0,不同为1 思路:可以将其处理为一位一位...
  • 这篇讲LinkedHashMap很...LinkedHashMap可以说是HashMap和LinkedList的集合体,既使用了HashMap的数据结构,又借用了LinkedList双向链表结构,基本数据类型还是Entry静态内部类。其结构如下,before、after指向保证顺
  • 线性基入门

    2019-09-16 21:20:31
    线性基是一种擅长处理异或问题的数据结构.设值域为[1,NNN],就可以用一个长度为⌈log⁡2N⌉\lceil \log_2N \rceil⌈log2​N⌉数组来描述一个线性基。特别地,线性基第iii位上数二进制下最高位也为第iii位。 ...
  • 正题 ... 题目大意 定义一个序列子异和为所有自己...首先树链剖分是肯定,然后我们考虑用哪个数据结构。 从每个位单独分析,一个长度为nnn的集合,然后cntxcnt_xcntx​表示有多少数二进制第xxx位为000 然后对于一...
  • 题意:需要你模拟一个多重集合(初始拥有0),该集合拥有三个功能 1、+ x 增加一个x(可以同时存在多... x 输出在这个集合中和x异或最大值。 分析:有20万个操作,很容易想到树形数据结构,我们可以看到...
  • 此前一直对树这个数据结构理解不是很彻底很到位,以及围绕树相关算法也感觉很飘忽很神秘,所以本周就萌生了全方位总结树这个数据结构以及和它相关算法。 为什么需要树?当在面临大量输入...
  • lucky_pydemo:Python-源码

    2021-03-26 18:29:06
    其中包含python各个数据类型,如:整型长整型布尔浮点型串行列表元组字典集合等以及不同变量类型相互转换串联之间运算以及列表元组集合之间区别和常用函数等 赋值运算 逻辑运算 包含逻辑运算(not and or...
  • HashMap 是存储key,value双列数据的集合。他底层结构主要是 数组+ 链表+ 红黑树实现 。 HashMap中hash数组默认大小是16,增加方式是 old*2。加载因子是0.75,是线程不安全。 当put一个节点数据时,会根据...
  • Trie树(字典树)

    2021-01-26 23:44:30
    Trie树前言一、Trie树的使用AcWing 835. Trie字符串统计AcWing 143. 最大异或对 前言 单词查找树,Trie树,是一种树形结构,是一...Trie树是一种高效的存储和查找字符串集合的数据结构。 AcWing 835. Trie字符串统计 #
  • 题解合集

    千次阅读 2020-08-07 17:15:50
    数据结构 单链表 双链表 单调栈 单调队列(滑动窗口) KMP算法 trie字符串统计 最大异或对 合并集合 格子游戏 连通块中点数量 堆排序 模拟堆 模拟散列表 字符串哈希 合并集合 搭配购买 区间和 排序 快速排序 第K个...
  • yzy666

    2020-07-31 16:36:26
    数据结构 单链表 双链表 单调栈 单调队列(滑动窗口) KMP算法 trie字符串统计 最大异或对 合并集合 格子游戏 连通块中点数量 堆排序 模拟堆 模拟散列表 字符串哈希 合并集合 搭配购买 区间和 排序 快速排序 第K个...
  • 学通Java24堂课

    2014-01-17 13:19:41
    3.9.6 情景应用6——异或运算实现变量值交换 90 3.10 自我测试 91 3.11 行动指南 92 3.12 成功可以复制——知识改变命运、科技改变生活 93 第4堂课 流程控制语句 95 第5堂课 数组应用 131 第6堂课 面向对象...

空空如也

空空如也

1 2 3
收藏数 48
精华内容 19
关键字:

数据结构集合的异或

数据结构 订阅