头像

MrLuo

国际DEBUG委员会委员


访客:7805

在线 


活动打卡代码 LeetCode 162. 寻找峰值

MrLuo
11秒前
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
          int l = 0 , r = nums.size() - 1;

          while(l < r)
          {
              int mid = l + r >> 1;
              if(nums[mid] > nums[mid + 1])r = mid;
              else l = mid + 1;
          }
          return l;
    }
};


活动打卡代码 LeetCode 160. 相交链表

MrLuo
3分钟前
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
       auto p = headA , q = headB;
        while( p != q)
        {
            p =( p == NULL) ? headB : p -> next;
            q = (q == NULL )? headA : q -> next;
        }
        return p;
    }
};


活动打卡代码 LeetCode 155. 最小栈

MrLuo
8分钟前
class MinStack {
public:
    /** initialize your data structure here. */stack<int> f , g;
    MinStack() {

    }

    void push(int x) {
        if(f.empty() || f.top() >= x)f.push(x);
        g.push(x);
    }

    void pop() {
        if(f.top() == g.top())f.pop();
        g.pop();
    }

    int top() {
        return g.top();
    }

    int getMin() {
        return f.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */



MrLuo
12分钟前
class Solution {
public:
    int findMin(vector<int>& nums) {
       int r = nums.size() - 1;
       while(r > 0 && nums[0] == nums[r])r--;
       if(nums[r] >= nums[0])return nums[0];

       int  l = 0;
       while( l < r)
       {
           int mid  = l + r  >> 1;
           if(nums[mid] < nums[0])r = mid;
           else l = mid + 1;
       }
       return nums[l];
    }
};



MrLuo
17分钟前
class Solution {
public:
    int findMin(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (nums[mid] <= nums.back()) r = mid;
            else l = mid + 1;
        }
        return nums[r];
    }
};



MrLuo
19分钟前
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int f =nums[0] ,  g = nums[0];
        int res = nums[0];
        for(int i = 1 ;i < nums.size() ;i++)
        {
            int a = nums[i] ,fa = f  * a  , gb = g * a;
            f = max(a,max(fa, gb));
            g = min(a  , min(fa ,gb)   );
            res = max(res  , f);
        }
        return res;
    }
};



MrLuo
41分钟前
class Solution {
public:
    string reverseWords(string s) {
        int k = 0;
       for(int i = 0 ;  i < s.size() ;i++)
       {
           if(s[i] == ' ')continue;
           int j = i , t = k;
           while(j < s.size() && s[j] != ' ')s[t++] = s[j++];
           reverse(s.begin() + k , s.begin() +  t);
           s[t++] = ' ';
           i = j , k = t;
       }
       if(k)k--;
       s.erase(s.begin() + k , s.end());
       reverse(s.begin() , s.end());
       return s;
    }
};


活动打卡代码 AcWing 1233. 全球变暖

MrLuo
10小时前
#include <iostream>
#include <queue>
using namespace std;

#define x first
#define y second

const int N = 1e3 + 10;

typedef pair<int,int> PII;

int n;
char map[N][N];
bool vis[N][N];
int dx[] = {-1, 0 , 1 , 0} ,dy[] = {0 , 1 , 0 , -1};

inline bool check(int a, int b)
{
  return a >= 0 && a < n && b >= 0 && b < n;
}

void bfs(int x,int y , int& total , int& bound)
{
  queue<PII> q;
  q.push({x , y});
  vis[x][y] = true;

  while(q.size())
   {
     auto t = q.front();
     q.pop();
     total ++;

     bool _isbound = false;
     for(int i = 0 ; i < 4 ; i++)
     {
       int a = t.x + dx[i] , b = t.y + dy[i];

       if(!check(a , b))continue;
       if(vis[a][b])continue;
       if(map[a][b] == '.')
       {
         _isbound  =true;
         continue;
       }
       vis[a][b] = true;
       q.push({a , b});
     }
     if(_isbound)bound++;
   }

}

int main(){
  cin >> n;

  for(int i = 0 ; i < n ; i++) 
     for(int j = 0 ; j < n;j++)
        cin >> map[i][j];

  int cnt = 0;
  for(int i = 0 ; i < n ; i++)
     for(int j = 0 ; j < n ; j++)
      if(!vis[i][j] && map[i][j] == '#')
      {
        int bound = 0, total = 0;

        bfs(i , j , total , bound);
        if(bound == total) cnt++;
      }
  cout << cnt <<endl;
  return 0;
}


活动打卡代码 AcWing 183. 靶形数独

MrLuo
12小时前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 9 , M = (1 << N) - 1;
#define lowbit(x) -x & x
int n;
int map[N][N];
int col[N],row[N],cell[4][4];
int low[M + 10],one[M + 10];
int ans = -1,cnt;

int getscore(int a,int b,int t){
  return (min(min(a - 0 , 8 - a) , min(b - 0 , 8 - b) ) + 6)* t;
}

void draw(int i ,int j ,int x){

  int s = 1;

  if(x > 0)map[i][j] = x;
  else {
    s = -1;
    x = -x;
    map[i][j] = 0;
  }

  x--;
  col[j] -= (1 << x) * s;
  row[i] -= (1 << x) * s;
  cell[i / 3][j / 3] -= (1 << x) * s;
}
void init(){
  for(int i = 0 ; i < 9 ; i++)col[i] = row[i] = cell[i / 3][i % 3]= M;



  for(int i = 0 ; i < 9 ; i++)low[1 << i] = i;

  for(int i = 0 ; i < 1 << 9 ; i++)
     for(int j = i ; j ;j -= lowbit(j))
          one[i]++;
}
int get_one(int i ,int j){
  return col[j] & row[i] & cell[i / 3][j / 3];
}
void dfs(int cnt , int score)
{
  if(cnt == 0)
  {
    //cout << "true" <<endl;
    ans = max(ans , score);
    return ;
  }
  else
  {
    int minv = 10;
    int x , y;
    for(int i = 0 ; i < 9 ; i++)
       for(int j = 0 ; j < 9 ;j++)
          if(!map[i][j])
          {
            int t = one[get_one(i , j)];
            if(t < minv)
            {
              minv = t;
              x = i , y = j;
            }
          }


    for(int i = get_one(x , y) ; i ; i -= lowbit(i))
    {
      int t = low[lowbit(i)] + 1;
      draw(x , y ,t);
      dfs(cnt - 1 , score + getscore(x , y ,t));
      draw(x , y , -t);
    }

  }
}

int main(){
  init();
  int x = 0;
  int score = 0;
  for(int i = 0 ;i < 9 ; i++)
     for(int j = 0 ; j < 9 ; j++)
         {
            cin >> x;
            if(x)
            {
              draw(i , j , x);
              score += getscore(i , j ,x);
            }
            else cnt++;
         }

    dfs(cnt , score);    
    cout << ans << endl;
  return 0;
}


活动打卡代码 AcWing 194. 涂满它!

MrLuo
1天前
#include <iostream>
#include <cstring>
using namespace std;

const int N = 20;

int n;
int map[N][N];
bool vis[N],use[N];
int being[N][N];
int depth = 0;
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
int backbe[20][N][N];
inline int f(){//估价函数 F()
    int res=0;
    memset(vis,0,sizeof(vis));
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
    if(being[i][j]!=1&&!vis[map[i][j]]){
        vis[map[i][j]]=1;
        res++;
    }
    return res;
}
bool check(int a,int b){
  return a >= 0 && a < n && b >= 0 && b < n;
}
inline void operate(int x,int y,int c){//染色操作 
    being[x][y]=1;
    for(int i=0;i<4;i++){
        int nx=x+dx[i],ny=y+dy[i];
        if(nx<0||nx>=n||ny<0||ny>=n) continue;
        if(being[nx][ny]==1) continue;
        if(map[nx][ny]!=c) being[nx][ny]=2;
        else operate(nx,ny,c);
    }
}

bool dfs(int cur,int last){
  int price = f() ; 

  if(price == 0)return true;
  if(cur + price > depth)return false;


  for(int c = 0 ; c <= 5 ;c++)
   {
     if(c == last || !use[c])continue;
      int ff=0,tmp[N][N];
        for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            tmp[i][j]=being[i][j];
       bool flag = false;
        for(int i = 0 ; i < n ; i++)
           for(int j = 0 ; j < n ; j++)
           if(being[i][j] == 2 && map[i][j] == c)
           {
             operate(i , j ,c);
             flag = true;
           }
           if(!flag)continue;

           if(dfs(cur + 1 , c))return true;
           for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            being[i][j]=tmp[i][j];

   }
   return false;
}

int main(){

  while(cin >> n , n)
  {
    memset(use,false , sizeof(use));
    for(int i = 0 ; i < n ; i++)
       for(int j = 0 ; j < n ; j ++)
           {
             cin >> map[i][j] ;
             use[map[i][j]] = true;
           }
    memset(being,0 ,sizeof(being));
    depth = f() ;
    if(depth  == 1){cout << 0 << endl; continue;}
    operate(0 , 0 , map[0][0]);
    depth = 0;
    //cout << f() <<endl;
    while(!dfs(0 , -1)) depth++;
    cout << depth << endl;
  }  

  return 0;
}