Leetcode_daily_practice(C++)

class Solution {
  bool Judge(vector<int>& bits){
    //从倒数第二项开始，统计连续1的个数
    int i = bit.size() - 2;
    while( i >= 0 && bits[i] == 1) i--;
    //若连续1的个数为奇数，则最后一项必然为2比特，否则为1比特
    return (bits.size() - i)%2 == 0;
  }
}

class solution{
  public:
  int findthevalue(vector<int>& arr1, vector<int>& arr2, int d){
    int cnt = arr1.size();
    for (int i = 0; i < arr1.size(); ++i){
      for (int j = 0; j < arr2.size(); ++j){
        if (abs(arr1[i] - arr[j]) <= d){
          cnt--;
          break;
        };
      }
    }
    return cnt;
  }
}

class solution{
public:
  int findthevalue(vector<int>& arr1, vector<int>& arr2, int d){
    //对arr2进行排序，使用STL中的排序算法，之后即可使用二分法
    sort(arr2.begin(), arr2.end());
    int cnt = arr1.size();
    for (int i = 0; i < arr1.size(); ++i){
      //使用STL库中的二分查找,得到距离
      //复习lower_bound的参数（数组开始，数组末尾，查找元素）
      //运用unsigned型变量可以直接使用距离绝对值
      unsigned p = lower_bound(arr2.begin(), arr2.end(), arr1[i]) - arr2.begin();
      book ok = true;
      //下述步骤的学习需巩固lower_bound的相关特性。
      //如果能够在区间内找到接近的p值，则看最接近的值是否小于距离
      if (p < arr2.size()) ok &= (arr2[p] - arr1[i] > d);
      //如果p被截断，则直接看最大元素即可
      if (p - 1 >= 0 && p - 1 <= arr2.size()) ok &= (arr[i] - arr[p - 1] > d);
      cnt += ok;
    }
    return cnt;
  }
}

class solution{
public:
  int findthejudge(int N, vector<vector<int>>& trust){
    //开辟一个二维数组存储信任度与被信任度
    vector<vector<int>> V(N+1, vector(2,0));
    for (int i = 0; i < trust.size(); ++i){
      V[trust[i][0]][0]++;
      V[trust[i][1]][1]++;
    }
    for (int i = 1; i <= N; ++i){
      if (V[i][0] == 0 && V[i][1] == N-1){
        return i;
      }
    }
    return -1;
  }
  
}

class Solution{
public:
  vector<vector<int>> subsets(vector<int>& nums){
    vector<vector<int>> ans;
    int size = nums.size();
    int N = 1 << size;//N为对应的二进制数，代表总的子集数目
    for (int i = 0; i < N; ++i){
      vector<int> v;
      for (int j = 0; j < size; ++j){//遍历，判断相应情况下取或者不取
        if (i & (1 << j)){//i的二进制表示其实就是取或者不取的含义
          v.push_back(nums[j]);
        }
      }
      ans.push_back(v);
    }
    return ans;
  }
}

/*代码说明：
a << b表示把a转为二进制后左移b位；
a >> b表示把a转为二进制后右移动b位；
&运算通常用作取位操作，取二者相同的位置；
事实上，位运算就是把数字转化为二进制后进行操作，但存储的变量本质上仍然是十进制
*/

class solution:
public:
  vector<int> dailyTemperatures(vector<int> T){
    int size = T.size();
    vector<int> ans(size,0);//开辟一个长度为size的数组，初始化为0
    stack<int> res;//设计一个栈，用于判断数值大小
    for (int i = 0; i < size; ++i){
      if (res.empty()) res.push(i);//如果栈为空，则放入当前元素，此处操作为防止越界问题
      while (!res.empty() && T[j] > T[res.top()]){ 
        ans[res.top()] = i - res.top();
        res.pop();
      }//若当前元素大于栈顶，则计算距离并存储，后去掉栈顶，继续判断
      res.push(i);//完成上述操作后，说明当前元素小于栈中所有元素，故将此时的元素放入栈中
    }
    return ans;
  }

class solution{
public:
  int findDuplicate(int[] nums){
    int slow = nums[0];
    int quick = nums[0];
    do{
      slow = nums[slow];
      quick = nums[nums[quick]];
    }while(slow != quick);
    
    int ptr_1 = nums[0];
    int ptr_2 = slow;
    while(ptr_1 != ptr_2){
      ptr_1 = nums[ptr_1];
      ptr_2 = nums[ptr_2];
    }
    return ptr_1;
  }
}

class solution{
  public int findDuplicate(int[] nums){
    int size = nums.length;
    int l = 1, r = size - 1;
    //二分查找基本思路
    while(l < r){
      int mid = (l + r)/2;
      for (int num:nums){
        if (num <= mid) cnt++;
      }
      
      if (cnt > mid){
        r = mid;
      }else{
        l = mid + 1;
      }
    }
    return l;
  }
}

class solution{
  public:
  void setZeroes(vector<vector<int>> matrix){
    int m = matrix.size(), n = matrix[0].size();
    if (m == 0||n == 0) return;
    vector<int> label_i, label_j;
    for (int i = 0; i < m; ++i){
      for (int j = 0; j < n; ++j){
        if (matrix[i][j] == 0){
          label_i.push_back(i);
          label_j.push_back(j);
        }
      }
    }
    int len = label_i.size();
    for (int k = 0; k < len; ++K){
      int tmpi = label_i[k], tmpj = label_j[k];
      for (int i = 0; i < m; ++i) matrix[i][tmpj] = 0;
      for (int j = 0; j < n; ++j) matrix[tmpi][j] = 0;
    }
  }
}

struct TreeNode{
  int val;
  TreeNode* left;
  TreeNode* right;
};

class solution{
  public:
  TreeNode lowestCommonAncestor(TreeNode *root, int p, int q){
    //若root为空或者等于p或者q中的一个，则返回root
    if (!root || root == p || root == q) return root;
    //查询左子树和右子树
    TreeNode *left = lowestCommonAncestor(root->left, p, q);
    TreeNode *right = lowestCommonAncestor(root->right, p, q);
    //若左右均有返回值，则说明p,q位于两侧，直接返回此时的根节点
    if (left && right) return root;
    //若只有一侧有返回值，则返回此时非空变量即可
    else return left?left: right;
  }
}

struct TreeNode{
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode(int x): val(x), left(NULL), right(NULL){}
};

class solution:
public:
   int sum = 0;
   queue<int> qu;
   void sum_num(TreeNode *root){
     if(root){
       sum_num(root->left);
       sum += root->val;
       qu.push(root->val);
       sum_num(root->right);
     }
   }
   void insertval(TreeNode *root){
     if(root){
       insertval(root->left);
       root->val = sum;
       sum -= qu.front();
       qu.pop();
       insertval(root->right);
     }
   }
   TreeNode* bstToGst(TreeNode* root){
     sum_num(root);
     insertval(root);
     return root;
   }

double FastPow(double x, int n){
  if(n == 0) return 1.0;
  double half = FastPow(x, n/2);
  if(n%2 == 0){
    return half*half;
  }else{
    return half*half*x;
  }
}

double pow(double x, int n){
  if(n == 0) return 1.0;
  if(n < 0){
    x = 1/x;
    n = -n;
  }
  return FastPow(x,n);
}

class solution:
public:
  vector<vector<int>> ans(TreeNode* root){
    if(root == NULL) return{};
    vector<vector<int>> ans;
    queue<TreeNode*> qu;
    qu.push_back(root);
    while(!qu.empty()){
      vector<int> tmp;//开启新的一层
      int n = qu.size();//现存的队列长度为该层的元素个数
      while(n>0){
        TreeNode* t = qu.front();
        qu.pop();
        tmp.push_back(t->val);
        //放入非空的结点
        if(t->left != NULL) qu.push(t->left);
        if(t->right != NULL) qu.push(t->right);
        n--;
      }
      ans.push_back(tmp);//算好一层后放入一层
    }
    return ans;//返回层序遍历结果
  }

//使用cstring库
int strStr(string text, string pattern){
  if(text.find(pattern) == text.npos) return -1;
  else return text.find(pattern);
}

//设计双指针，一个表示前序，一个表示后序
vector<int> next(pattern.size() + 1);
int j = -1, i = 0;
next[i] = j;//对于第一个元素，只能满足前-1个元素
//利用i 指针进行遍历
while(i < pattern.size()){
  //当无法匹配时，则j自动跳至next[j]指的位置进行判定
  while(j >= 0 && pattern[i] != pattern[j]) j = next[j];
  i++, j++;
  b[i] = j;
}

class solution{
public:
  int strStr(string text, string pattern){
    if(pattern.size() == 0) return 0;
    if(text.size() == 0) return -1;
    //构造next数组，i为沿着pattern前进的指针，j为计数器
    int j = -1, i = 0;
    vector<int> next(pattern.size() + 1);
    next[i] = j;
    while(i < pattern.size()){
      while(j >= 0 && pattern[i] != pattern[j]) j = b[j];
      i++, j++;
      next[i] = j;
    }
    //开始对两个数组进行匹配判断，i沿着pattern前进，j沿着text前进
    j = 0, i = 0;
    while(j < text.size()){
      while(i >= 0 && pattern[i] != text[j]) i = b[i];
      i++, j++;
      if(i == pattern.size()) return j - pattern.size();
    }
    return -1;
  }
}