61. 旋转链表
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if(!head) return head;
int n = 0;
ListNode* tail;
for(auto p = head; p ; p = p->next) n ++,tail = p;
k = k % n; // 防止 k 很大
if(!k) return head;
ListNode* p = head;
for(int i = 0 ; i < n - k - 1; i++) p = p -> next;
tail -> next = head;
head = p -> next;
p -> next = nullptr;
return head;
}
};
头节点可以是虚拟节点,也可以不是虚拟节点
62. 不同路径
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> f(m,vector<int>(n));
for(int i = 0 ; i < m ; i ++)
for(int j = 0; j < n; j ++)
if(i == 0 && j == 0) f[i][j] = 1;
else{
if(i) f[i][j] += f[i - 1][j];
if(j) f[i][j] += f[i][j - 1];
}
return f[m - 1][n - 1];
}
};
emm,这就叫套路,哈哈
63. 不同路径 II
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& o) {
int m = o.size();
if(!m) return 0;
int n = o[0].size();
vector<vector<int>> f(m,vector<int>(n));
for(int i = 0 ; i < m ; i ++)
for(int j = 0; j < n; j ++)
if(o[i][j] == 0){
if(i == 0 && j == 0) f[i][j] = 1;
else{
if(i) f[i][j] += f[i - 1][j];
if(j) f[i][j] += f[i][j - 1];
}
}
else f[i][j] = 0;
return f[m - 1][n - 1];
}
};
64. 最小路径和
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int ans = 0;
int m = grid.size();
if(!m) return ans;
int n = grid[0].size();
vector<vector<int>> f(m,vector<int>(n));
for(int i = 0; i < m ; i++){
for(int j = 0 ; j < n ; j++){
if(!i && !j) f[i][j] = grid[i][j];
else{
if(i == 0) f[i][j] = f[i][j - 1] + grid[i][j]; // 行
if(j == 0) f[i][j] = f[i - 1][j] + grid[i][j]; // 列
// 到达(i,j) 点的不是 (i - 1,j)就是(i,j - 1),取一个最小值即可
if(i && j) f[i][j] = min(f[i][j - 1],f[i - 1][j]) + grid[i][j]; // 主体部分
}
}
}
return f[m - 1][n - 1];
}
};
65. 有效数字
y总都说可以不做,面向测试数据编程,没啥意思