2、两数相加
注意的点：
- 同位相加大于10的情况注意进位
- 可能是极大的数字，转成整数直接相加不可行
class Solution
{
public:
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
{
ListNode *ret = new ListNode();
ListNode *head = ret;
int jinwei = 0;
ret->val = l1->val l2->val;
// 第一位如果有进位需要单独处理
if (ret->val >= 10)
{
jinwei = ret->val / 10;
ret->val = ret->val % 10;
}
// 遍历链表，还原整数
while (l1->next != nullptr || l2->next != nullptr)
{
ListNode *tmp = new ListNode();
if (l1->next != nullptr && l2->next != nullptr)
{
tmp->val = l1->next->val l2->next->val;
// 处理进位
if (jinwei > 0)
{
tmp->val = jinwei;
jinwei = 0;
}
if (tmp->val >= 10)
{
jinwei = tmp->val / 10;
tmp->val = tmp->val % 10;
}
l1 = l1->next;
l2 = l2->next;
}
else if (l1->next != nullptr)
{
tmp->val = l1->next->val;
// 处理进位
if (jinwei > 0)
{
tmp->val = jinwei;
jinwei = 0;
}
if (tmp->val >= 10)
{
jinwei = tmp->val / 10;
tmp->val = tmp->val % 10;
}
l1 = l1->next;
}
else
{
tmp->val = l2->next->val;
// 处理进位
if (jinwei > 0)
{
tmp->val = jinwei;
jinwei = 0;
}
if (tmp->val >= 10)
{
jinwei = tmp->val / 10;
tmp->val = tmp->val % 10;
}
l2 = l2->next;
}
ret->next = tmp;
ret = ret->next;
}
// 最后一位如果有进位需要单独处理
if (jinwei > 0)
{
ListNode *tmp = new ListNode();
tmp->val = jinwei;
jinwei = 0;
ret->next = tmp;
}
return head;
}
};1、两数之和
暴力枚举
该方法简单但是时间复杂度为O(n^2)。空间复杂度为O(1)。运行速度慢且内存空间消耗大。
代码语言：javascript复制class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ret;
vector<int>::iterator it1;
vector<int>::iterator it2;
int num1, num2;
for(it1 = nums.begin();it1!=nums.end();it1 ){
num1 = *it1;
for(it2 = it1 1;it2!=nums.end();it2 ){
num2 = *it2;
if((num1 num2) == target){
ptrdiff_t index1 = distance(nums.begin(), it1);
ptrdiff_t index2 = distance(nums.begin(), it2);
ret.push_back(static_cast<int>(index1));
ret.push_back(static_cast<int>(index2));
}
}
}
return ret;
}
};哈希-两次遍历
遍历一次将nums中的数据存储为<num[i], i>的键-值形式在哈希表中。再遍历一次，计算target-nums[i]这个键的出现次数，如果出现次数大于0则存在另一个数与当前nums[i]相加等于target，然后获取i与hash[target-nums[i]]即可。
代码语言：javascript复制class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
map<int, int> hash;
// 初始化一个大小为2，值为-1的容器b
vector<int> ret(2, -1);
for(int i = 0;i < nums.size();i ){
hash.insert(map<int,int>::value_type(nums[i],i));
}
for(int i = 0;i < nums.size();i ){
// 计算键target-nums[i]出现次数
if(hash.count(target - nums[i])>0 && (hash[target-nums[i]]!=i)){
ret[0] = i;
ret[1] = hash[target-nums[i]];
break;
}
}
return ret;
}
};哈希-一次遍历
遍历一次nums，计算hash中键target-nums[i]出现次数，如果大于0则找到了一个结果。如果未找到，则将<nums[i], i>放入hash中，继续遍历。
代码语言：javascript复制class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
map<int, int> hash;
vector<int> ret(2, -1);
for(int i = 0;i < nums.size();i ){
// 计算键target-nums[i]出现次数
if(hash.count(target - nums[i])>0){
ret[0] = hash[target-nums[i]];
ret[1] = i;
break;
}
hash[nums[i]] = i;
}
return ret;
}
};198、打家劫舍
动态规划。将问题划分成若干小问题。对于前k间房间，有两种偷窃情况，偷窃前k-1家和偷窃前k-2家与第k家，因此比较f(k-1)与f(k-2) v(k)的大小，然后更新到f(k)。需要确定f(0)=0和f(1)=v(0)的初始状态，然后进行迭代。
优化：每次迭代只用到f(k-1)与f(k-2)，因此可以只记录这两个状态。
代码语言：javascript复制class Solution {
public:
int rob(vector<int>& nums) {
if(nums.size()==0){
return 0;
}
int len = nums.size();
vector<int> dp(3, 0);
dp[0] = 0;
dp[1] = nums[0];
for(int k = 2;k<=len;k ){
dp[2] = max(dp[1], nums[k-1] dp[0]);
dp[0] = dp[1];
dp[1] = dp[2];
}
return dp[1];
}
};1583、统计不开心的朋友
用两个数组模拟，order[i][j]数组表示j在i中的排位，match[i]表示与i配对的对象序号。
有了这两个数组，就可以开始遍历所有人：首先找到与之配对的人y的下标index，然后遍历0-index寻找在x心中排位比y高的人u，找到后再通过match数组寻找与u配对的x。如果满足条件：
-
x与u的亲近程度胜过x与y，且 -
u与x的亲近程度胜过u与v
则不开心的人数加一
代码语言：javascript复制class Solution {
public:
int unhappyFriends(int n, vector<vector<int>>& preferences, vector<vector<int>>& pairs) {
int ret = 0;
int order[n][n];
for(int i=0;i<n;i ){
for(int j=0;j<n-1;j ){
// preferences[i][j]在i心中的排位
order[i][preferences[i][j]] = j;
}
}
int match[n];
for(int i=0;i<pairs.size();i ){
match[pairs[i][0]] = pairs[i][1];
match[pairs[i][1]] = pairs[i][0];
}
for(int x=0;x<n;x ){
// 找到与之配对的
int y = match[x];
int index = order[x][y];
// 寻找是否存在好感度更高的
for(int j=0;j<index;j ){
int u = preferences[x][j];
int v = match[u];
// 如果u也更想和x组队
if(order[u][x] < order[u][v]){
ret ;
break;
}
}
}
return ret;
}
};213、打家劫舍Ⅱ
与第198题的不同之处是，其中房屋是首尾相连的，因此第一间房屋和最后一间房屋不能在同一晚上偷窃。所以可以分成两种情况，偷窃1到n-1间房子和偷窃2到n间房子，然后对于分解出来的这两个范围再对其使用上述198题的方法即可。
代码语言：javascript复制class Solution {
public:
int rob(vector<int>& nums) {
if(nums.size()==0){
return 0;
}
int len = nums.size();
vector<int> dp(3, 0);
dp[0] = 0;
dp[1] = nums[0];
for(int k = 2;k<=len-1;k ){
dp[2] = max(dp[1], nums[k-1] dp[0]);
dp[0] = dp[1];
dp[1] = dp[2];
}
vector<int> dp1(3, 0);
dp1[0] = 0;
if(len > 1){
dp1[1] = nums[1];
}
for(int k = 3;k<=len;k ){
dp1[2] = max(dp1[1], nums[k-1] dp1[0]);
dp1[0] = dp1[1];
dp1[1] = dp1[2];
}
return max(dp[1], dp1[1]);
}
};337、打家劫舍Ⅲ
对于一个节点，有两种偷窃情况：1、偷窃该节点，不能偷窃子节点，保存状态f[node]为该节点权重 子树上不选中node的子节点的最大权重；2、不偷窃该节点，保存状态g[node]为node的子节点被选中或者不被选中两种情况下的最大值。
这样思路就清晰了，定义两个哈希表f、g，对该二叉树进行深度优先搜索，并更新f[node]与g[node]，前者为node->val g[node->left] g[node right]（该节点权重 子树上不选中node的子节点的最大权重），后者为max(f[node->left], g[node.left]) max(f[node->right], g[node.right])（node的子节点被选中或者不被选中两种情况下的最大值），最后的结果就是根节点root在f与g哈希表中的最大权值了。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
map <TreeNode*, int> f, g;
void dfs(TreeNode *node){
if(node == nullptr){
return;
}
dfs(node->left);
dfs(node->right);
f[node] = g[node->left] g[node->right] node->val;
g[node] = max(f[node->left], g[node->left]) max(f[node->right], g[node->right]);
}
int rob(TreeNode* root) {
dfs(root);
return max(f[root], g[root]);
}
};2560、打家劫舍Ⅳ
典型的最小化最大值问题。将小偷窃取的房屋中最大值upper初始化为nums中最大值，最小值lower设置为nums中最小值。使用二分查找，遍历nums，当该栋房子金额小于等于mid且前一栋房子未被偷窃则cnt 1，遍历结束后的cnt表示当最大偷窃能力为mid的情况下，可以偷窃的最大房屋数量。如果cnt比给出的k值大，说明此时的mid可能略大故让upper=mid向左收拢，否则使lower=mid 1向右收拢。迭代直到lower大于upper的情况，返回upper或者lower（最后lower==upper），即为至少偷窃k间房子的最小窃取能力。
代码语言：javascript复制class Solution {
public:
int minCapability(vector<int>& nums, int k) {
int lower = *min_element(nums.begin(), nums.end());
int upper = *max_element(nums.begin(), nums.end());
while(lower < upper){
int mid = (upper lower)/2;
int cnt = 0;
int visited = 0;
for(int x : nums){
if(x<=mid&&!visited){
cnt ;
visited = 1;
}else{
visited = 0;
}
}
if(cnt >= k){
upper = mid;
}else{
lower = mid 1;
}
}
return upper;
}
};1993、树上的操作
上锁和解锁的过程都十分简单，重点在于upgrade的过程。在canbeup函数中，首先判断是否为未上锁；然后判断是否存在至少一个上锁的后代节点，通过深度优先搜索遍历，将返回值的初始值设为false，当存在任一一个上锁的后代节点，则返回true，并且在递归调用时使用或操作，保证一个true的返回值可以在调用栈一直传递；最后判断是否存在上锁的父节点，利用parent数组迭代即可。如果可以升级，则直接利用深度优先搜索解锁所有后代节点并将当前节点上锁。
代码语言：javascript复制class LockingTree {
public:
LockingTree(vector<int>& parent) {
int len = parent.size();
this->parent = parent;
this->lockNodeUser = vector<int>(len, -1);
this->children = vector<vector<int>>(len);
for(int i = 0;i < len;i ){
int p = parent[i];
if(p != -1){
children[p].push_back(i);
}
}
}
bool lock(int num, int user) {
if(this->lockNodeUser[num] == -1){
this->lockNodeUser[num] = user;
return true;
}
return false;
}
bool unlock(int num, int user) {
if(this->lockNodeUser[num] == user){
this->lockNodeUser[num] = -1;
return true;
}
return false;
}
bool upgrade(int num, int user) {
if(!canbeup(num)){
return false;
}
// 将所有子孙节点解锁
unlockchildren(num);
// 给指定节点上锁
lock(num, user);
return true;
}
bool canbeup(int num){
// 当前节点未上锁
if(lockNodeUser[num] != -1){
return false;
}
// 至少有个上锁的子孙节点
if(!anyloackchild(num)){
return false;
}
if(anylockparent(num)){
return false;
}
return true;
}
// 深度优先
// 至少一个上锁的子孙节点
bool anyloackchild(int num){
int ret = false;
for(int i = 0;i < children[num].size();i ){
// 求或
ret = ret || anyloackchild(children[num][i]);
}
if(lockNodeUser[num] != -1){
return true;
}else{
return ret;
}
}
// 判断是否有上锁的祖先节点
bool anylockparent(int num){
num = parent[num];
while (num != -1) {
if (lockNodeUser[num] != -1) {
return true;
}
num = parent[num];
}
return false;
}
// 深度优先
// 解锁子孙节点
void unlockchildren(int num){
for(int i = 0;i < children[num].size();i ){
unlockchildren(children[num][i]);
}
this->lockNodeUser[num] = -1;
}
private:
vector<int> parent;
vector<int> lockNodeUser;
vector<vector<int>> children;
};
/**
* Your LockingTree object will be instantiated and called as such:
* LockingTree* obj = new LockingTree(parent);
* bool param_1 = obj->lock(num,user);
* bool param_2 = obj->unlock(num,user);
* bool param_3 = obj->upgrade(num,user);
*/146、LRU缓存
双向链表、哈希表、LRU（最近最少使用）算法。用哈希表模拟内存中的key-value对，用双向链表模拟内存中的key的使用情况，哈希表的value指向双向链表中对应的节点。当放入新页时，直接加到双向链表头部如果超过内存空间最大容量则移除链表尾部节点，当访问或者更新页时将节点放置在链表头部并更新value。
代码语言：javascript复制struct DLinkedNode {
int key, value;
DLinkedNode* prev;
DLinkedNode* next;
DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {}
DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}
};
class LRUCache {
public:
LRUCache(int capacity) {
this->mem = 0;
this->capacity = capacity;
head = new DLinkedNode();
tail = new DLinkedNode();
head->next = tail;
tail->prev = head;
}
int get(int key) {
if (cache.count(key) > 0) {
DLinkedNode* node = cache[key];
movetohd(node);
return node->value;
} else {
return -1;
}
}
void put(int key, int value) {
if (cache.count(key) > 0) {
DLinkedNode* node = cache[key];
node->value = value;
movetohd(node);
}else{
DLinkedNode* node = new DLinkedNode(key, value);
cache[key] = node;
addtohd(node);
mem ;
if(mem > capacity){
DLinkedNode* node = removetail();
cache.erase(node->key);
delete node;
mem--;
}
}
}
// 添加到头部
void addtohd(DLinkedNode* node) {
node->prev = head;
node->next = head->next;
head->next->prev = node;
head->next = node;
}
// 移动到头部
void movetohd(DLinkedNode* node){
node->prev->next = node->next;
node->next->prev = node->prev;
addtohd(node);
}
// 删除尾部
DLinkedNode* removetail(){
DLinkedNode* node = tail->prev;
node->prev->next = node->next;
node->next->prev = node->prev;
return node;
}
private:
map<int, DLinkedNode*> cache;
DLinkedNode* head;
DLinkedNode* tail;
int mem;
int capacity;
};
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/1333、餐厅过滤器
定义一个包含两个属性id和rating的结构体，并对该结构重定义运算符 > ，即rating更大的结构更大，rating相等的id更多的结构更大。在过滤函数中，首先遍历餐厅从中取出符合条件的餐厅赋值给新的结构体rest并存入ret当中。然后调用sort(ret.begin(), ret.end(), greater<rest>())函数进行排序，第三个参数表示自定义的比较函数也就是在结构体中重定义的运算符 > 。排序后将id数组返回即可。
class Solution {
public:
struct rest{
int id;
int rating;
bool operator> (const rest& a) const {
if (this->rating != a.rating) {
return this->rating > a.rating;
} else {
return this->id > a.id;
}
}
};
vector<int> filterRestaurants(vector<vector<int>>& restaurants, int veganFriendly, int maxPrice, int maxDistance) {
vector<rest> ret;
int cnt;
for(int i=0;i<restaurants.size();i ){
if(veganFriendly == 1 && restaurants[i][2]!=1){
continue;
}
if(restaurants[i][3] > maxPrice){
continue;
}
if(restaurants[i][4] > maxDistance){
continue;
}
struct rest r;
r.id = restaurants[i][0];
r.rating = restaurants[i][1];
ret.push_back(r);
}
sort(ret.begin(), ret.end(), greater<rest>());
vector<int> list;
for(int i = 0;i< ret.size();i ){
list.push_back(ret[i].id);
}
return list;
}
};2251、花期内花的数目
当第i个人到达时，时间为time，假设在time之前（包括time）开花的花数量为bloom，在time之前（不time）枯萎的花数量为fall，则time时刻第i个人能看到的花的数量为bloom-fall。将二维数组flowers中的花期开始与结束两个属性分别放在begin和end两个数组中，然后将这两个数组从小到大排序。
接下来遍历people数组，使用二分查找找到begin数组中小于等于time的元素数量（即在此刻即此刻之前开放的花），end数组中小于time的元素数量（即在此刻之前枯萎的花），第i个人能够观察到的花的数量为bloom-fall。
std::upper_bound函数返回在有序序列中大于给定值的第一个元素的迭代器。std::lower_bound函数返回在有序序列中大于等于给定值的第一个元素的迭代器。std::binary_search：该函数检查有序序列中是否存在与给定值匹配的元素，返回一个布尔值。
class Solution {
public:
vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& people) {
int NumofFlower = flowers.size();
int NumofPerson = people.size();
vector<int> ans(NumofPerson);
vector<int> begin(NumofFlower), end(NumofFlower);
for(int i = 0;i<NumofFlower;i ){
begin[i] = flowers[i][0];
end[i] = flowers[i][1];
}
sort(begin.begin(), begin.end());
sort(end.begin(), end.end());
for(int i =0;i<NumofPerson;i ){
int time = people[i];
int bloom, fall;
bloom = upper_bound(begin.begin(), begin.end(), time)-begin.begin();
fall = lower_bound(end.begin(), end.end(), time)-end.begin();
ans[i] = bloom-fall;
}
return ans;
}
};309、买卖股票的最佳时机含冷冻期
将每天的状态分为三类——持股、不持股且处于冷冻期、不持股且不处于冷冻期。今日持股状态下的最大收益=max(前日持股状态下的最大收益，前日不持股且处于非冷冻期最大收益-今日股价)，不持股且处于冷冻期状态下的最大收益=max(前日持股最大收益 今日股价，前日不持股且处于冷冻期状态下最大收益)，不持股且不处于冷冻期状态下的最大收益=max(前一日不持股且不处于冷冻期的最大收益，前一日不持股且处于冷冻期)。
因为最后一日之前肯定会将股票抛售，所以最后最大收益为max(最后一日不持股且不处于冷冻期的最大收益，最后一日不持股且处于冷冻期的最大收益)。
代码语言：javascript复制class Solution {
public:
int maxProfit(vector<int>& prices) {
int len = prices.size();
if(len == 1 || len == 0){
return 0;
}
vector<vector<int>> money(len, vector<int>(3));
money[0][0] = -prices[0];
money[0][1] = 0;
money[0][2] = 0;
for(int i = 1;i<len;i ){
// 当前状态为持有，则最大值为 前一日持有股票 和 前一日非冷冻期且不持股-今日股价 中的最大
money[i][0] = max(money[i-1][0], money[i-1][2]-prices[i]);
// 当前状态为无股票且处于冷冻期，则最大值为 前一日持有股票 今日出售 和 前一日冷冻期且不持股 中的最大
money[i][1] = max(money[i-1][1], money[i-1][0] prices[i]);
// 当前状态为无股票且不处于冷冻期，则最大值为 前一日无股 和 前一日冷冻期且不持股 中的最大
money[i][2] = max(money[i-1][1], money[i-1][2]);
}
return max(money[len-1][1], money[len-1][2]);
}
};714、买卖股票的最佳时机含手续费
将每天的状态分为三类——持股、不持股。今日持股的最大收益=max(前一日持股的最大收益，前一日不持股的最大收益-今日股价)，今日不持股的最大收益=max(前一日不持股的最大收益，前一日持股的最大收益 今日股价-手续费)。
代码语言：javascript复制class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int len = prices.size();
if(len == 1 || len == 0){
return 0;
}
vector<vector<int>> money(len, vector<int>(2));
money[0][0] = -prices[0];
money[0][1] = 0;
for(int i = 1;i<len;i ){
money[i][0] = max(money[i-1][0], money[i-1][1]-prices[i]);
money[i][1] = max(money[i-1][1], money[i-1][0] prices[i]-fee);
}
return money[len-1][1];
}
};11、盛最多水的容器
贪心 双指针。第一个指针指向数组开头，第二个指针指向数组末尾。面积大小只与两个指针距离和最低高度有关，所以对指针进行迭代同时记录最大面积（当两个指针相等时结束），每次迭代将高度较低的那个指针向前迭代。
代码语言：javascript复制class Solution {
public:
int maxArea(vector<int>& height) {
int begin=0, end=height.size()-1;
int size = 0;
int tmp = 0;
int lower = 0;
while(begin != end){
lower = min(height[begin], height[end]);
tmp =lower*(end-begin);
size = max(size, tmp);
if(height[begin] > height[end]){
end--;
}else{
begin ;
}
}
return size;
}
};12、整数转罗马数字
从高位转到低位就行，只需要考虑与4和9有关的特殊情况就行。
代码语言：javascript复制class Solution {
public:
string intToRoman(int num) {
map<int, string> map;
vector<int> nums = {1,5,10,50,100,500,1000};
map[1] = "I";
map[5] = "V";
map[10] = "X";
map[50] = "L";
map[100] = "C";
map[500] = "D";
map[1000] = "M";
string ret;
int lv;
int cnt;
for(int i=6;i>=0;i--){
lv = nums[i];
cnt = num/lv;
if(i%2==0 && i!=6 && cnt==4){
ret.append(map[lv]);
ret.append(map[nums[i 1]]);
num = num%lv;
}
else if(i%2==1 && num/nums[i-1]==9){
ret.append(map[nums[i-1]]);
ret.append(map[nums[i 1]]);
num = num%nums[i-1];
i--;
}
else{
for(int j=0;j<cnt;j ){
ret.append(map[lv]);
}
num = num%lv;
}
}
return ret;
}
};136、只出现一次的数字
异或
代码语言：javascript复制class Solution {
public:
int singleNumber(vector<int>& nums) {
int ret=0;
for(int i=0;i<nums.size();i ){
ret = ret^nums[i];
}
return ret;
}
};137、只出现一次的数字Ⅱ
计算数组里面所有数字的二进制第 i 位（0<=i<32）的和cnt，将其模3，得到的结果0或1就是只出现一次的数字的二进制的第 i 位（0<=i<32）。
代码语言：javascript复制class Solution {
public:
int singleNumber(vector<int>& nums) {
int ret = 0;
for(int i=0;i<32;i ){
int cnt=0;
for(int num : nums){
cnt = (num >> i)&1;
}
if(cnt%3 == 1){
ret |= (1 << i);
}
}
return ret;
}
};260、只出现一次的数字Ⅲ
把所有数字异或得到结果x，为最终的两个数字x1、x2的异或。计算x & -x，得到第 i 位为1，x1、x2在这一位上必不同。因此将所有数字分为两类，第 i 位位0和第 i 位位1的，再一次遍历nums，然后计算两类数字的异或能够得到x1和x2.
代码语言：javascript复制class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int x = 0;
vector<int> ret(2, 0);
for(int num : nums){
x ^= num;
}
int bit = 0;
if(x == INT_MIN){
bit = x;
}else{
bit = x & -x;
}
for(int num : nums){
if(num & bit){
ret[0] ^= num;
}else{
ret[1] ^= num;
}
}
return ret;
}
};80、删除有序数组中的重复项
双指针。
代码语言：javascript复制class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int curr=0, next=1;
int cnt = 0;
while(curr < nums.size()-1){
// 如果相等cnt 1
if(nums[curr] == nums[next]){
cnt ;
// 超过两个元素，则删除next指向的元素
if(cnt == 2){
auto iter= nums.begin() next;
nums.erase(iter);
// 减少一个
cnt--;
continue;
}
}else{
cnt = 0;
}
// 指针后移
curr ;
next ;
}
return nums.size();
}
};169、多数元素
对于多数元素，其二进制的每一位都是所有数据中最多的。
代码语言：javascript复制class Solution {
public:
int majorityElement(vector<int>& nums) {
int ret = 0;
for(int i = 0;i<32;i ){
int zero = 0;
int one = 0;
for(int num:nums){
if(num & (1 << i)){
one ;
}else{
zero ;
}
}
if(one > zero){
ret |= (1 << i);
}
}
return ret;
}
};
