锐客网

  1. 首页 > it技术 > >

剑指|剑指 week2

1.机器人的运动范围 是数位和，裸BFS，用pair存下标

class Solution { public: int book[55][55]; int get_sum(pairp) { int s=0,num1=p.first,num2=p.second; while(num1) { s+=(num1%10); num1/=10; } while(num2) { s+=(num2%10); num2/=10; } return s; }int movingCount(int threshold, int rows, int cols) { memset(book,0,sizeof book); queue >q; if(!rows||!cols)return 0; int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1}; int res=0; q.push({0,0}); while(!q.empty()) { auto top=q.front(); q.pop(); if(book[top.first][top.second]||get_sum(top)>threshold) continue; book[top.first][top.second]=1; res++; for(int i=0; i<4; i++) { int newx=top.first+dx[i],newy=top.second+dy[i]; if(newx>=0&&newx=0&&newy

2.剪绳子
class Solution { public: int maxProductAfterCutting(int length) { //dp[i]表示绳子长度为i的最大乘积i~[2,n] //由于必须切一刀，假设切在j位置，左边长度为j，则右边长度为i-j，对于右边长度，可切可不切 //dp[i]=max( j*(i-j) ,j*dp[i-j] ) int dp[length+10]; memset(dp,0,sizeof dp); for(int i=2; i<=length; i++) { for(int j=1; j

3.二进制中1的个数 采用unsigned int转化为无符号整数
class Solution { public: int NumberOf1(int _n) { unsigned int n=_n; int res=0; while(n) { if(n&1)res++; n>>=1; } return res; } };

4.快速幂 注意如果指数是负数的话，需要取倒数
class Solution { public: double Power(double x, int n) { typedef long long ll; bool is_min=n<0; double res=1; ll k=abs(ll(n)); while(k) { if(k&1) res*=x; x*=x; k>>=1; } if(is_min)res=1/res; return res; } };

5.在O(1)时间复杂度内删除链表结点 由于是单链表，因此我们无法找到它的前驱节点，我们可以换一种思路，将下一个节点的值复制到当前节点，然后将下一个节点删除即可。
时间复杂度为：O（1）
class Solution { public: void deleteNode(ListNode* node) { auto p=node ->next; node->val=p->val; node->next=p->next; delete p; } };

6.删除链表中的重复的节点 定义一个虚拟头节点（dummy），防止头节点被删除，然后往后扫描整个链表（p），每次扫描元素相同的一段，如果这段中的元素个数多于1个，则将整段元素直接删除。
剑指|剑指 week2
文章图片
/** * Definition for singly-linked list. * struct ListNode { *int val; *ListNode *next; *ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* deleteDuplication(ListNode* head) { auto dummy=new ListNode(-1); dummy->next=head; auto p=dummy; while(p->next) { auto q=p->next; while(q&&q->val==p->next->val) q=q->next; //q存在不要忘记掉 //间隔一个 if(p->next->next==q)p=p->next; //删掉大于等于2的间隔 else p->next=q; } returndummy->next; } };

7.正则表达式匹配 对于这一类两个字符串匹配问题，可以用二维动态规划来写
状态表示：dp[i][j]表示s[i....]和p[j.....]匹配
【剑指|剑指 week2】状态计算：
  • 1.p[j]是正常字符,dp[i][j]=s[i]==p[j]&&dp[i+1][j+1]
  • 2.p[j]是' . ' , dp[i][j]=dp[i+1][j+1]
  • 3.p[j+1]是' * '（p[j]是b * 这样的形式）
    第一种出现0次， dp[i][j]=dp[i][j+2] ( 跳两个格子 )
    第二种出现>=1次， dp[i][j]=dp[i+1][j]
8.调整数组顺序使奇数位于偶数前面 类似于快排的思想，利用两个指针，其中第一个指针从前往后找，第二个指针从后往前找，第一个指针遇到的为偶数，第二个指针遇到的是奇数，且满足不相遇，就把这两个指针交换
class Solution { public: void reOrderArray(vector &array) { int l=0,r=array.size()-1; while(l

9.链表中倒数第k个节点 双指针
class Solution { public: ListNode* findKthToTail(ListNode* pListHead, int k) { ListNode* fast=pListHead,*slow=pListHead; while(k--&&fast) fast=fast->next; if(k>=0) return NULL; else { while(fast) { fast=fast->next; slow=slow->next; } } return slow; } };

10.链表中环的入口地址 哈希表
class Solution { public: unordered_mapmp; ListNode *entryNodeOfLoop(ListNode *head) { for(auto i=head; i; i=i->next) { if(mp[i]!=0) { return i; } else { mp[i]=1; } } return NULL; } };

    推荐阅读


    上一篇：10.1|10.1 孔子于乡党，恂恂（xún）如也，似不能言者。其在宗庙朝廷，便便言，唯谨尔。

    下一篇：爱了很久的朋友