c++：vector的相关oj题（136. 只出现一次的数字、118. 杨辉三角、26. 删除有序数组中的重复项、JZ39 数组中出现次数超过一半的数字）

文章目录

• 1. 136. 只出现一次的数字
• • 题目详情
  • 代码(直接来异或）
  • 思路
  • 2. 118. 杨辉三角
  • • 题目详情
    • 代码1
    • 思路
    • 代码2
    • 思路2
    • 3. 26. 删除有序数组中的重复项
    • • 题目详情
      • 代码
      • 思路
      • 4. JZ39 数组中出现次数超过一半的数字
      • • 题目详情
        • 代码1（暴力）
        • 思路1
        • 代码2（Boyer-Moore 投票算法）
        • 思路2

          1. 136. 只出现一次的数字

          传送门

          题目详情

          

          代码(直接来异或）

          class Solution {
          public:
              int singleNumber(vector& nums) {
                  //根据：某个元素只出现一次   直接来异或
                  int ret=0;
                  for(auto e:nums)
                  {
                      ret=ret^e;
                  }
                  return ret;
              }
          };
          

          思路

          1. 异或运算的性质：异或运算（^）具有以下性质**（相同为0，相异为1）**
             • 任何数和0做异或运算，结果仍然是原来的数：a ^ 0 = a
             • 任何数和自身做异或运算，结果为0：a ^ a = 0
             • 异或运算满足交换律和结合律：a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b
             • 利用异或运算的性质：如果一个数出现两次，那么两次出现的数异或后结果为0；如果一个数只出现一次，那么异或后结果为该数本身。
             • 利用上述性质，遍历nums中的所有元素，并进行异或运算，最终得到的结果就是只出现一次的元素。

               

          2. 118. 杨辉三角

          传送门

          题目详情

          

          代码1

          class Solution {
          public:
              vector generate(int numRows) {
                  vector vv;
                  vv.resize(numRows);//先给好numRows个元素，即vv里能存vector
                  for(int i=0;i
                      vv[i].resize(i+1);//每一行里再开好对应的大小
                      vv[i].front()=vv[i].back()=1;//最左最右都是1
                  }
                  for(int i=2;i
                       for(int j=1;j
                           vv[i][j]=vv[i-1][j-1]+vv[i-1][j];
                       }
                   }
                  return vv;
              }
          };
          
          public:
              vector
                  vector
                      vv[i].resize(i+1,0);//每一行里再开好对应的大小
                      vv[i].front()=vv[i].back()=1;//最左最右都是1
                  }
                  for(int i=0;i
                      for(int j=0;j
                          if(vv[i][j]==0)
                          vv[i][j]=vv[i-1][j-1]+vv[i-1][j];
                      }
                  }
                  return vv;
              }
          };
          
          public:
              int removeDuplicates(vector
                  if(nums.size()==0)//处理0的情况
                  {
                      return 0;
                  }
                  int index=1;
                  int pre_index=0;
                  while(index
                      if(nums[index]!=nums[pre_index])
                      {
                          nums[pre_index+1]=nums[index];//赋值给下一个后加一，就是新位置了，再用后面的来比
                          pre_index++;
                      }
                      index++;
                  }
                  return pre_index+1;//下标加1才是元素个数
              }
          };
          
                  // write code here
                  int half=numbers.size()/2;
                  for(int i=0;i
                      int count=0;
                      for(int j=i+1;j
                          if(numbers[i]==numbers[j])
                          {
                              count++;
                          }
                          if(count=half)
                          {
                              return numbers[i];
                          }
                      }
                  }
                  return numbers[0];
              }
          };
          
                  // write code here
                  int count = 0;
                  int candidate=numbers[0];//一开始就假设第一个是候选者
                  for (auto num : numbers) {
                      if (count == 0) {
                          candidate = num;
                      }
                      count += (num == candidate) ? 1 : -1;//相等就+1，不等-1
                  }
                  return candidate;
              }
          };