A.正解应该是二分找最大值,但暴力可以过,那没事了
#include <bits/stdc++.h> using namespace std; int num[100005]; int n; int main() { n = 0; int tmp; while(scanf("%d",&tmp)!=EOF){ num[++n] = tmp; } int ans = 0; sort(num+1,num+n); for(int i=1;i<n;i++){ for(int j=i+1;j<n;j++){ if(num[i]+num[j]<=num[n]) ans++; else break; } } printf("%d\n",ans); return 0; }
B. 将字符串分为三段,然后递归着去找相对应的字符,只有最后一段需要处理下
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 返回Sn的第k位字符 * @param n int整型 Sn的n * @param k int整型 需要返回的字符下标位 * @return char字符型 */ // Sn 2*n+1 char findKthBit(int n, int k) { // write code here int cnt = 1<<(n-1); if(k<cnt) return findKthBit(n-1, k); if(k==cnt) return 'a'+n-1; //大于n k = k-cnt; return 'a'+'z'-findKthBit(n-1, (1<<(n-1))-k); } };C. leetcode分发糖果的升级版,我只是多加了num[n]和num[1]的大小比较就过了,但其实没有那么清楚为啥只加这一个条件就过了,感觉这个问题挺复杂的,也许是数据水了
#include <bits/stdc++.h> using namespace std; int n; int num[1005]; int val[1005]; int main() { n = 0; int tmp; while(scanf("%d",&tmp)!=EOF) { num[++n] = tmp; } val[1] = 1; for(int i=2; i<=n; i++) { if(num[i]>num[i-1]) val[i] = val[i-1] + 1; else val[i] = 1; } for(int i=n-1; i>=1; i--) { if(num[i]>num[i+1]) { val[i] = max(val[i],val[i+1]+1); } } //只多加了这一行 if(num[n]>num[1]) val[n] = max(val[n],val[1]+1); int ans = 0; for(int i=1; i<=n; i++) ans = ans + val[i]; printf("%d\n",ans); return 0; }D.优先队列bfs裸题
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 计算最小航行费用 * @param input int整型vector<vector<>> 二维网格 * @return int整型 */ int dirx[4]= {0,0,1,-1}; int diry[4]= {1,-1,0,0}; int vis[105][105]; struct node { node(int xx,int yy,int s) { x = xx; y = yy; spend = s; } int x,y; int spend; friend bool operator<(const node& x,const node& y) { return x.spend>y.spend; } }; int minSailCost(vector<vector<int> >& input) { // write code here priority_queue<node>q; int n = input.size(); int m = input[0].size(); vis[0][0] = 1; q.push(node(0,0,0)); while(!q.empty()) { node now = q.top(); q.pop(); if(now.x==n-1&&now.y==m-1) return now.spend; for(int i=0; i<4; i++) { int dx = now.x + dirx[i]; int dy = now.y + diry[i]; if(dx<0||dy<0||dx>=n||dy>=m||vis[dx][dy]==1||input[dx][dy]==2) continue; vis[dx][dy] = 1; int v = now.spend; if(input[dx][dy]==1) v++; else v+=2; q.push(node(dx,dy,v)); } } return -1; } };
全部评论
(9) 回帖