- AcWing 24. 机器人的运动范围">AcWing 24. 机器人的运动范围
- AcWing 25. 剪绳子">AcWing 25. 剪绳子
- AcWing 26. 二进制中1的个数">AcWing 26. 二进制中1的个数
- AcWing 27. 数值的整数次方">AcWing 27. 数值的整数次方
- AcWing 28. 在O(1)时间删除链表结点
- AcWing 29. 删除链表中重复的节点
- AcWing 30. 正则表达式匹配
- AcWing 31. 表示数值的字符串">AcWing 31. 表示数值的字符串
- AcWing 32. 调整数组顺序使奇数位于偶数前面
- AcWing 33. 链表中倒数第k个节点
- AcWing 34. 链表中环的入口结点
AcWing 24. 机器人的运动范围
解法
考察flood fill算法，因为合法区域可能是分块的，之间并不连通，不能简单的通过坐标计算获取最后的答案。
代码
class Solution {public:int cnt;int threshold, rows, cols;vector<vector<bool>> st;bool valid(int x, int y) {int sum = 0;while(x) {sum += x % 10;x /= 10;}while(y) {sum += y % 10;y /= 10;}return sum <= threshold;}void dfs(int x, int y) {cnt ++;st[x][y] = true;int dx[] = {1, 0, -1, 0};int dy[] = {0, 1, 0, -1};for (int i = 0; i < 4; i ++) {int a = x + dx[i];int b = y + dy[i];if (a >= 0 && a < rows && b >= 0 && b < cols && !st[a][b] && valid(a, b)) {dfs(a, b);}}}int movingCount(int _threshold, int _rows, int _cols){if (_threshold < 0 || _rows == 0 || _cols == 0) {return 0;}threshold = _threshold;rows = _rows;cols = _cols;cnt = 0;st = vector<vector<bool>>(rows, vector<bool>(cols, false));dfs(0, 0);return cnt;}};
AcWing 25. 剪绳子
解法
该题目要是分类的话算是一个数学题。
首先我们证明剪绳子每段的长度不超过4。反证：假设说有一段的长度为x(x >= 5)，那我们把x剪成两段，分别为3和x - 3。我们对比3(x - 3)和x的关系，由于x>=5，因此3(x-3)>x，因此最优解应该把x继续拆分，和假设矛盾，因此没段长度不超过4。
由于4 = 2*2，每个4都可以分成两个2的乘积，因此最终结果可以没有4。
因此最终答案只包含2、3，并且有尽可能多的3。
由于该题目需要划分为至少两段，因此小于3的长度要特殊处理。
代码
class Solution {
public:
int maxProductAfterCutting(int length) {
if (length == 2) {
return 1;
}
if (length == 3) {
return 2;
}
int product = 1;
while (length > 4) {
product *= 3;
length -= 3;
}
product *= length;
return product;
}
};
AcWing 26. 二进制中1的个数
解法
循环右移计算最后一位是否为1，注意，n为int，如果n为负数，右移的时候c++会再最左侧补1，而不是补0，因此需要转为unsigned int类型再计算。
代码
class Solution {
public:
int NumberOf1(int n) {
int cnt = 0;
unsigned t = (unsigned)n;
while(t) {
cnt += t & 1;
t = t >> 1;
}
return cnt;
}
};
AcWing 27. 数值的整数次方
解法
二进制思想。把指数写成二进制的形式，每一位对应不同的底数，比如2的5次方，5的二进制位101，从右数第一个1代表2^1，第二个1代表2^4。
另外，如果指数为负数的话，我们把底数取倒数，再进行计算。
这个地方没有考虑底数为0，指数为负数的情况。也没有考虑底数为0，指数为0的情况。
代码
class Solution {
public:
double Power(double base, int exponent) {
if (exponent < 0) {
return Power(1/ base, -1 * exponent);
}
double res = 1, p = base;
while(exponent) {
if (exponent & 1) {
res *= p;
}
p *= p;
exponent >>= 1;
}
return res;
}
};
AcWing 28. 在O(1)时间删除链表结点
解法
脑筋急转弯类题目。通过复制后一个节点，并删除后一个节点，达到删除的目的。
代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void deleteNode(ListNode* node) {
node->val = node->next->val;
node->next = node->next->next;
}
};
AcWing 29. 删除链表中重复的节点
解法
双指针算法。
为了代码统一，需要一个假的头结点，从假头结点的下一个节点开始判断，该节点是否为重复节点，如果重复，把tail节点往后移动到NULL或者不重复为止，再把中间节点一并删除。
代码
/**
* 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) {
ListNode * dummy = new ListNode(-1);
dummy->next = head;
ListNode* pre = dummy, * cur = dummy->next;
while(cur) {
// 判断cur是否为重复节点
if (cur->next && cur->val == cur->next->val) {
ListNode* tail = cur->next;
while(tail && tail->val == cur->val) {
tail = tail->next;
}
// 删除重复节点
pre->next = tail;
cur = tail;
} else {
pre = pre->next;
cur = pre->next;
}
}
return dummy->next;
}
};
AcWing 30. 正则表达式匹配
解法
动态规划。
状态表示：f(i, j)表示字符串s[1~i]和p[1~j]匹配。
状态转换：
- 如果p[j]为’a’-‘z’，则f[i][j] = f[i - 1][j - 1] && (s[i] == p[j])
- 如果p[j]为’.’，则p[j]和s[i]一定匹配，则f[i][j] = f[i - 1][j - 1]
- 如果p[j]为(x)*，这里的x表示’a’-‘z’或者’.’，那么f[i][j] = f[i][j-2] || f[i - 1][j - 2] && (s[i] 和p[j - 1]匹配) || f[i - 2][j - 2] && (s[i], s[i - 1]均和p[j - 1]匹配) || f[i - 3][j - 2] && (s[i], s[i - 1], s[i - 2]均和p[j - 1]匹配) … 我们把i - 1代入上述式子，得到f[i-1][j] = f[i - 1][j-2] || f[i - 2][j - 2] && (s[i - 1] 和p[j - 1]匹配) || f[i - 3][j - 2] && (s[i - 1], s[i - 2]均和p[j - 1]匹配) …
- 对比上述两个式子，利用逻辑运算的分配率，整理得到f[i][j] = f[i][j - 2] || (f[i - 1][j] && s[i]和p[j - 1]匹配)**
-
代码
class Solution { public: bool isMatch(string s, string p) { // f(i, j) represent s[1~i] and p[1~j] match int n = s.size(), m = p.size(); s = ' ' + s; p = ' ' + p; vector<vector<bool>> f(n + 1, vector<bool>(m + 1, false)); f[0][0] = true; for (int i = 0; i <= n; i ++) { for (int j = 1; j <= m; j ++) { if (j + 1 <= m && p[j + 1] == '*') { continue; } if (p[j] == '*') { f[i][j] = f[i][j - 2]; if (i) f[i][j] = f[i][j] || (f[i - 1][j] && (s[i] == p[j - 1] || p[j - 1] == '.')); } else { if (i) { f[i][j] = f[i - 1][j - 1] && (s[i] == p[j] || p[j] == '.'); } } } } return f[n][m]; } };AcWing 31. 表示数值的字符串
解法
该题目考察的依旧是思维。
里面总共有’e’, ‘.’, ‘+’, ‘-‘，怎么正确的保证顺序是关键。
建议在写代码之前先写出能想到的测试用例，边写边测。代码
class Solution { public: bool scanInt(string &s, int &idx) { if (s[idx] == '+' || s[idx] == '-') { idx ++; } int t = idx; while(idx < s.size() && s[idx] >= '0' && s[idx] <= '9') { idx ++; } return idx > t; } bool scanUInt(string &s, int &idx) { int t = idx; while(idx < s.size() && s[idx] >= '0' && s[idx] <= '9') { idx ++; } return idx > t; } bool isNumber(string s) { if (s.empty()) { return false; } // 如果要是需要去掉空格的话，写在这儿 int idx = 0; // 如果有小数点，扫描小数点前的数字 // 如果没有小数点，则直接扫描数字 // 这个数字可以带+/-号 bool is_valid = scanInt(s, idx); if (idx < s.size() && s[idx] == '.') { idx ++; // 如果有小数点，那么后面需要一个不带+/-号的数字 bool t_valid = scanUInt(s, idx); // 由于变态设定，允许.1, 1., +.1, -.1这种可以为数字，但'.','+.'不能成为数字 is_valid = is_valid || t_valid; } if (idx < s.size() && (s[idx] == 'E' || s[idx] == 'e')) { idx ++; // 如果有科学计数法，后面必须是要有数字的 is_valid = is_valid && scanInt(s, idx); } return idx == s.size() && is_valid; } };AcWing 32. 调整数组顺序使奇数位于偶数前面
解法
双指针算法，前面指针用来表示需要交换的偶数，后面指针用来表示需要交换的奇数，如果符合交换的条件（左指针小于右指针），则交换。
代码
class Solution { public: void reOrderArray(vector<int> &array) { int left = 0, right = array.size() - 1; int n = array.size(); while (left < right) { while (left < n && array[left] % 2 == 1) { left ++; } while (right >= 0 && array[right] % 2 == 0) { right --; } if (left < right) { swap(array[left], array[right]); } } } };AcWing 33. 链表中倒数第k个节点
解法
下述两个解法在时间复杂度上没有明显的差异，均为O(n)
先扫一遍，然后找到对应的偏移量，然后再扫一遍到第k个节点。
- 双指针算法，第一个指针先走k步，然后第二个指针出发，当第一个指针走到末尾时，第二个指针即第k个节点。
代码
这个地方最好在函数开头判断下k是否<=0，虽说k<=0也可以返回正确的值
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* findKthToTail(ListNode* pListHead, int k) { if (!pListHead) { return NULL; } ListNode* tail = pListHead; for (int i = 0; i < k; i ++) { if (!tail) { return NULL; } tail = tail->next; } ListNode *cur = pListHead; while(tail) { tail = tail->next; cur = cur->next; } return cur; } };AcWing 34. 链表中环的入口结点
解法
- 一个快指针，一个慢指针，快指针一次走两步，慢指针一次走一步。如果有环，两指针必然相遇。相遇之后，把慢指针重新指向出发位置，这是，快慢指针一次走一步，当两个指针再次相遇，相遇的点即是环的入口。
一个快指针，一个慢指针，快指针一次走两步，慢指针一次走一步。如果有环，两指针必然相遇。相遇之后，继续行走，得到环的节点数目n。重置指针时，第一个指针先走n，然后两个指针一起走，直到相遇。
证明
首先，慢指针走的距离一定为x + y。因为如果慢指针已经绕环一周，则一定会和快指针相遇。
- 因此，快指针走过的距离为x + n(y + z) + y，n表示转的圈数。
- 由于快指针路程是慢指针的两倍：则 x + n(y + z) + y = 2 x + 2 y，则x = z + (n - 1)(y + z)
- 因此，当我们重新设定好指针位置，向前移动，x和z在环的意义下是等长的，因此会在入口点相遇。
代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *entryNodeOfLoop(ListNode *head) {
if (!head) {
return NULL;
}
ListNode * slow = head;
ListNode * fast = head;
do {
slow = slow->next;
fast = fast->next;
if (fast) {
fast = fast->next;
}
} while(fast && fast != slow);
if (fast == NULL) {
return NULL;
}
fast = head;
while (fast != slow) {
fast = fast->next;
slow = slow->next;
}
return fast;
}
};
若有收获，就点个赞吧
0 人点赞
