- [73. 矩阵置零](https://leetcode.cn/problems/set-matrix-zeroes/)
- [202. 快乐数](https://leetcode.cn/problems/happy-number/)
- [剑指 Offer 04. 二维数组中的查找](https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/)
- [131. 分割回文串](https://leetcode.cn/problems/palindrome-partitioning/)
- [144. 二叉树的前序遍历](https://leetcode.cn/problems/binary-tree-preorder-traversal/) --迭代版
- [347. 前 K 个高频元素](https://leetcode-cn.com/problems/top-k-frequent-elements/)
题目要求原地修改，故使用数组第一行第一列作为标记位，bool flag用来判断标记位是否需要全部置零。
依次遍历除标记位外数组，如果=0在标记位记录。
通过标记位对二维数组置零，最后处理标记位
时间复杂度：O(mn)
class Solution {
public:
void setZeroes(vector>& matrix) {
int m = matrix.size(), n = matrix[0].size();
bool row_flag = false, column_flag = false;
for (int i = 0; i < m; ++i) {
if (matrix[i][0] == 0) {
column_flag = true;
break;
}
}
for (int i = 0; i < n; ++i) {
if (matrix[0][i] == 0) {
row_flag = true;
break;
}
}
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
if (matrix[i][j] == 0) {
matrix[i][0] = matrix[0][j] = 0;
}
}
}
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
if (matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
}
if (row_flag) {
for (int i = 0; i < n; ++i) {
matrix[0][i] = 0;
}
}
if (column_flag) {
for (int i = 0; i < m; ++i) {
matrix[i][0] = 0;
}
}
}
};
202. 快乐数
Hash记录冲突
set.find() != set.end()证明环路，return false
res == 1 return true
class Solution {
public:
set st;
bool Square(int n) {
int res = 0;
while (n) {
int temp = n % 10;
n /= 10;
res += pow(temp, 2);
}
if (st.find(res) != st.end()) {
return false;
}
st.insert(res);
return res == 1 || Square(res);
}
bool isHappy(int n) {
// Hash
return Square(n);
}
};
龟兔赛跑问题
快慢指针，相交证明成环 return false
fast == 1 return true
class Solution {
public:
int Square(int n) {
int res = 0;
while (n) {
int temp = n % 10;
n /= 10;
res += pow(temp, 2);
}
return res;
}
bool isHappy(int n) {
// slow fast point
int slow = n, fast = Square(n);
if (fast == 1) return true;
while (slow != fast) {
slow = Square(slow);
fast = Square(fast);
if (fast == 1) return true;
fast = Square(fast);
if (fast == 1) return true;
}
return false;
}
};
剑指 Offer 04. 二维数组中的查找
从右上角开始遍历，matrix[i][j] == target直接退出
class Solution {
public:
bool searchMatrix(vector>& matrix, int target) {
int m = matrix.size(), n = matrix[0].size();
int i = 0, j = n - 1;
while (i < m && j >= 0) {
if (matrix[i][j] < target) {
++i;
} else if (matrix[i][j] > target) {
--j;
} else {
return true;
}
}
return false;
}
};
131. 分割回文串
动态规划dp标记i到j是否为回文子串
回溯，类似全排列组合过程
class Solution {
public:
vector> res;
vector> dp;
vector str;
void dfs(const string& s, int idx) {
if (idx == s.length()) {
res.push_back(str);
return;
}
for (int i = idx; i < s.length(); ++i) {
if (dp[idx][i]) {
str.push_back(s.substr(idx, i - idx + 1));
dfs(s, i + 1);
str.pop_back();
}
}
}
vector> partition(string s) {
int len = s.length();
dp.resize(len, vector(len, 1));
for (int i = 1; i < len; ++i) {
for (int j = 0; j < len - i; ++j) {
if (i == 1) {
dp[j][j + i] = (s[j] == s[j + i] ? true : false);
} else {
dp[j][j + i] = (s[j] == s[j + i] ? dp[j + 1][j + i - 1] : false);
}
}
};
dfs(s, 0);
return res;
}
};
144. 二叉树的前序遍历 --迭代版
可以用迭代的方式实现方法一的递归函数，两种方式是等价的，区别在于递归的时候隐式地维护了一个栈，而在迭代的时候需要显式地将这个栈模拟出来。
class Solution {
public:
vector preorderTraversal(TreeNode* root) {
if (root == nullptr) {
return {};
}
vector res;
stack sk;
TreeNode* node = root;
while (!sk.empty() || node != nullptr) {
while (node != nullptr) {
res.push_back(node->val);
sk.push(node);
node = node->left;
}
node = sk.top();
sk.pop();
node = node->right;
}
return res;
}
};
347. 前 K 个高频元素
方法一：堆（这一部分解释搬运自leetcode官方题解） 思路与算法 首先遍历整个数组，并使用哈希表记录每个数字出现的次数，并形成一个「出现次数数组」。找出原数组的前 kk 个高频元素，就相当于找出「出现次数数组」的前 kk 大的值。 最简单的做法是给「出现次数数组」排序。但由于可能有 O(N)O(N) 个不同的出现次数（其中 NN 为原数组长度），故总的算法复杂度会达到 O(Nlog N)O(NlogN)，不满足题目的要求。 在这里，我们可以利用堆的思想：建立一个小顶堆，然后遍历「出现次数数组」： 如果堆的元素个数小于 kk，就可以直接插入堆中。 如果堆的元素个数等于 kk，则检查堆顶与当前出现次数的大小。如果堆顶更大，说明至少有 kk 个数字的出现次数比当前值大，故舍弃当前值；否则，就弹出堆顶，并将当前值插入堆中。 遍历完成后，堆中的元素就代表了「出现次数数组」中前 kk 大的值。
class Solution {
public:
static bool cmp(pair& a, pair& b) {
return a.second > b.second;
}
vector topKFrequent(vector& nums, int k) {
unordered_map mp;
for (int& x : nums) {
++mp[x];
}
priority_queue, vector>, decltype(&cmp)> q(cmp);
for (auto& [first, second] : mp) {
if (q.size() == k) {
if (q.top().second < second) {
q.pop();
q.emplace(first, second);
}
} else {
q.emplace(first, second);
}
}
vector ret;
while (!q.empty()) {
ret.emplace_back(q.top().first);
q.pop();
}
return ret;
}
};
快排效率没有堆排高，而且最坏时间复杂度可达O(n)，就当练手了
这里采用的是rand随机选取idx，随机快速选择排序，通常来说效果比普通的快排要好些
map的使用和上面一致，保存value+count
class Solution {
public:
void quicksort(vector& ret, vector> values, int l, int r, int k) {
int rand_idx = rand() % (r - l + 1) + l;
swap(values[rand_idx], values[r]);
int index = l;
int x = values[r].second;
for (int i = l; i < r; ++i) {
if (values[i].second <= x) {
swap(values[i], values[index++]);
}
}
swap(values[r], values[index]);
if (k < r - index + 1) {
quicksort(ret, values, index, r, k);
} else {
for (int i = r; i >= index; --i) {
ret.push_back(values[i].first);
}
if (k - (r - index + 1) > 0) quicksort(ret, values, l, index - 1, k - (r - index + 1));
}
}
vector topKFrequent(vector& nums, int k) {
unordered_map mp;
for (int& x : nums) {
++mp[x];
}
vector> values;
for (auto& x : mp) {
values.emplace_back(x);
}
vector ret;
quicksort(ret, values, 0, values.size() -1, k);
return ret;
}
};
