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

1.重排链表

1. class Solution {
2. public:
3.     //找中间节点
4.     ListNode* midNode(ListNode* head){
5.         ListNode* slow = head, *fast = head;
6.         while(fast && fast->next){
7.             slow = slow->next;
8.             fast = fast->next->next;
9.         }
10.         return slow;
11.     }
12.     //反转链表
13.     ListNode* reverseList(ListNode* head){
14.         ListNode* pre = nullptr, *cur = head;
15.         while(cur){
16.             ListNode* temp = cur->next;
17.             cur->next = pre;
18.             pre = cur;
19.             cur = temp;
20.         }
21.         return pre;
22.     }
23.     void reorderList(ListNode* head) {
24.         ListNode* m = midNode(head);//m是中间节点
25.         ListNode* rhead = reverseList(m);//返回后半截反转的头结点
26.         while(rhead->next){
27.             ListNode* nxt = head->next;
28.             ListNode* nxt2 = rhead->next;
29.             head->next = rhead;
30.             rhead->next = nxt;
31.             head = nxt;
32.             rhead = nxt2;
33.         }
35.     }
36. };

复制代码

2.轮转数组

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，此中 k 黑白负数。
比如：
[1,2,3,4,5,6,7], k = 3
->
[5,6,7,1,2,3,4]
先把整个数组反转，再分别反转前k个和后n-k个即可

1. class Solution {
2. public:
3.     void reverse(vector<int>& nums, int begin, int end){
4.         while(begin < end) swap(nums[begin ++], nums[end --]);
5.     }
6.     void rotate(vector<int>& nums, int k) {
7.         k %= nums.size();
8.         reverse(nums, 0, nums.size() - 1);
9.         reverse(nums, k, nums.size() - 1);
10.         reverse(nums, 0, k - 1);
11.     }
12. };

复制代码

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

给你一个整数数组 nums，返回 数组 answer ，此中 answer 便是 nums 中除 nums 之外别的各元素的乘积 。
标题数据 包管 数组 nums之中恣意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要利用除法，且在 O(n) 时间复杂度内完成此题。
输入: nums = [1,2,3,4]
输出: [24,12,8,6]
左右累乘

1. class Solution {
2. public:
3.     vector<int> productExceptSelf(vector<int>& nums) {
4.         int n = nums.size();
5.         int left = 1, right = 1;
6.         vector<int> res(n, 1);
7.         for(int i = 0; i < nums.size(); i ++){
8.             res[i] *= left;
9.             left *= nums[i];
11.             res[n - i - 1] *= right;
12.             right *= nums[n - i - 1];
13.         }
14.         return res;
15.     }
16. };

复制代码

4.字母异位词分组

把每种字母出现次数都类似的字符串分到同一组。
比方 aab,aba,baa 可以分到同一组，但 abb 不可。
如果将aab，aba按照从小到大排序，可以得到同一个字符串aab，以是当且仅当两个字符串排序后一样，才把他俩分到一组。
根据这一点，用哈希表分组，把排序后的字符串当做key，原字符串构成的列表即答案当做value，末了把全部value加到一个列表中返回

1. class Solution {
2. public:
3.     vector<vector<string>> groupAnagrams(vector<string>& strs) {
4.         unordered_map<string, vector<string>> m;
5.         for(auto s : strs){
6.             string sorted_s = s;
7.             sort(sorted_s.begin(), sorted_s.end());
8.             m[sorted_s].push_back(s);
9.         }
10.         vector<vector<string>> ans;
11.         for(auto pair : m){
12.             ans.push_back(pair.second);
13.         }
14.         return ans;
15.     }
16. };

复制代码

5.搜刮二维矩阵II

找target，从右上角开始找，留意要用while，用for嵌套的话就归去等关照了

1. class Solution {
2. public:
3.     bool searchMatrix(vector<vector<int>>& matrix, int target) {
4.         int m = matrix.size(), n = matrix[0].size();
5.         int x = 0, y = n - 1;
7.         while (x < m && y >= 0) {
8.             if (matrix[x][y] == target) {
9.                 return true;
10.             }
12.             if (matrix[x][y] > target) {
13.                 y--;
14.             } else {
15.                 x++;
16.             }
17.         }
19.         return false;
20.     }
21. };

复制代码

6.矩阵置零

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的全部元素都设为 0 。请利用 原地 算法。
用bool纪录必要变成0的行和列，妙啊

1. class Solution {
2. public:
3.     void setZeroes(vector<vector<int>>& matrix) {
4.         int m=matrix.size();
5.         int n=matrix[0].size();
6.         vector<int> row(m),col(n);
7.         for(int i=0;i<m;i++)
8.         {
9.             for(int j=0;j<n;j++)
10.             {
11.                 if(!matrix[i][j])
12.                 {
13.                     row[i]=col[j]=true;
14.                 }
15.             }
16.         }
17.         for(int i=0;i<m;i++)
18.         {
19.             for (int j=0;j<n;j++)
20.             {
21.                 if(row[i]||col[j])
22.                 {
23.                     matrix[i][j]=0;
24.                 }
25.             }
26.         }
27.      
28.     }
29. };

复制代码

7.岛屿数量

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

1. class Solution {
2. public:
3.     void dfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y){
4.         int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
5.         for(int i = 0; i < 4; i ++){
6.             int nextx = x + dir[i][0];
7.             int nexty = y + dir[i][1];
8.             if(nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;
9.             if(!visited[nextx][nexty] && grid[nextx][nexty] == '1') {
10.                 visited[nextx][nexty] = true;
11.                 dfs(grid, visited, nextx, nexty);
12.             }
13.         }
15.     }
16.     int numIslands(vector<vector<char>>& grid) {
17.         int n = grid.size();
18.         int m = grid[0].size();
19.         int res = 0;
20.         vector<vector<bool>> visited(n, vector<bool>(m ,false));
21.         for(int i = 0; i < n; i ++){
22.             for(int j = 0; j < m; j ++){
23.                 if(!visited[i][j] && grid[i][j] == '1'){
24.                     res++;
25.                     dfs(grid, visited, i, j);
26.                 }
27.             }
28.         }
29.         return res;
30.         
31.     }
32. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！qidao123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金