算法闭关修炼百题计划（二）

1.重排链表

class Solution {
public://找中间节点ListNode* midNode(ListNode* head){ListNode* slow = head, *fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;}//反转链表ListNode* reverseList(ListNode* head){ListNode* pre = nullptr, *cur = head;while(cur){ListNode* temp = cur->next;cur->next = pre;pre = cur;cur = temp;}return pre;}void reorderList(ListNode* head) {ListNode* m = midNode(head);//m是中间节点ListNode* rhead = reverseList(m);//返回后半截反转的头结点while(rhead->next){ListNode* nxt = head->next;ListNode* nxt2 = rhead->next;head->next = rhead;rhead->next = nxt;head = nxt;rhead = nxt2;}}
};

2.轮转数组

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

比如：
[1,2,3,4,5,6,7], k = 3
->
[5,6,7,1,2,3,4]

先把整个数组反转，再分别反转前k个和后n-k个即可

class Solution {
public:void reverse(vector<int>& nums, int begin, int end){while(begin < end) swap(nums[begin ++], nums[end --]);}void rotate(vector<int>& nums, int k) {k %= nums.size();reverse(nums, 0, nums.size() - 1);reverse(nums, k, nums.size() - 1);reverse(nums, 0, k - 1);}
};

3.除自身以外数组的乘积

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

左右累乘

class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int n = nums.size();int left = 1, right = 1;vector<int> res(n, 1);for(int i = 0; i < nums.size(); i ++){res[i] *= left;left *= nums[i];res[n - i - 1] *= right;right *= nums[n - i - 1];}return res;}
};

4.字母异位词分组

把每种字母出现次数都相同的字符串分到同一组。
例如 aab,aba,baa 可以分到同一组，但 abb 不行。

假如将aab，aba按照从小到大排序，可以得到同一个字符串aab，所以当且仅当两个字符串排序后一样，才把他俩分到一组。
根据这一点，用哈希表分组，把排序后的字符串当做key，原字符串组成的列表即答案当做value，最后把所有value加到一个列表中返回

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string, vector<string>> m;for(auto s : strs){string sorted_s = s;sort(sorted_s.begin(), sorted_s.end());m[sorted_s].push_back(s);}vector<vector<string>> ans;for(auto pair : m){ans.push_back(pair.second);}return ans;}
};

5.搜索二维矩阵II

找target，从右上角开始找，注意要用while，用for嵌套的话就回去等通知了

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int m = matrix.size(), n = matrix[0].size();int x = 0, y = n - 1;while (x < m && y >= 0) {if (matrix[x][y] == target) {return true;}if (matrix[x][y] > target) {y--;} else {x++;}}return false;}
};

6.矩阵置零

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

用bool记录需要变成0的行和列，妙啊

class Solution {
public:void setZeroes(vector<vector<int>>& matrix) {int m=matrix.size();int n=matrix[0].size();vector<int> row(m),col(n);for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(!matrix[i][j]){row[i]=col[j]=true;}}}for(int i=0;i<m;i++){for (int j=0;j<n;j++){if(row[i]||col[j]){matrix[i][j]=0;}}}}
};

7.岛屿数量

这题我是会的
但是我怕我忘了
还是记录一下吧

class Solution {
public:void dfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y){int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};for(int i = 0; i < 4; i ++){int nextx = x + dir[i][0];int nexty = y + dir[i][1];if(nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;if(!visited[nextx][nexty] && grid[nextx][nexty] == '1') {visited[nextx][nexty] = true;dfs(grid, visited, nextx, nexty);}}}int numIslands(vector<vector<char>>& grid) {int n = grid.size();int m = grid[0].size();int res = 0;vector<vector<bool>> visited(n, vector<bool>(m ,false));for(int i = 0; i < n; i ++){for(int j = 0; j < m; j ++){if(!visited[i][j] && grid[i][j] == '1'){res++;dfs(grid, visited, i, j);}}}return res;}
};