1.递归与数学计算的结合
LeetCode 50. Pow(x, n)
题目链接：点击这里
数学中的特殊情况：
作除数没有意义
没有意义
class Solution {
public:
double myPow(double a, int b) {
if(a == 0 && b == 0) return -1;
else if(a == 0 && b < 0) return -1;
else if(b < 0) return 1 / quick_power(a, b);
else return quick_power(a, b);
}
double quick_power(double a, int b) {
if(b == 0) return 1.0;
double half = quick_power(a, b / 2);
if(b % 2 == 0) return half * half;
else return half * half * a;
}
};
2.递归与一维数组的结合
MergeSort
void merge_sort(int q[], int l, int r)
{
if(l >= r) return;
int mid = l + r >> 1;
merge_sort(q, l, mid);
merge_sort(q, mid + 1, r);
int k = 0, i = l, j = mid + 1;
while(i <= mid && j <= r)
{
if(q[i] <= q[j]) tmp[k++] = q[i++];
else tmp[k++] = q[j++];
}
while(i <= mid) tmp[k++] = q[i++];
while(j <= r) tmp[k++] = q[j++];
for(i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
}
QuickSort
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 1e5 + 10;
int q[N];
int n;
void quick_sort(int q[], int l, int r)
{
if(l >= r) return;
int x = q[l + r >> 1], i = l - 1, j = r + 1;
while(i < j)
{
do i++; while(q[i] < x);
do j--; while(q[j] > x);
if(i < j) swap(q[i], q[j]);
}
quick_sort(q, l, j);
quick_sort(q, j + 1, r);
}
int main()
{
scanf("%d", &n);
for(int i = 0; i < n; ++i)
scanf("%d", &q[i]);
quick_sort(q, 0, n-1);
for(int i = 0; i < n; ++i)
printf("%d ", q[i]);
return 0;
}
3.递归与二维数组的结合
LeetCode 52. N皇后 II
题目链接：点击这里
思路：按行
image.png
class Solution {
public:
int ans;
int a[50];
int totalNQueens(int n) {
EightQueen(0, n);
return ans;
}
void EightQueen(int curret_row, int n)
{
if(curret_row == n)
{
ans++;
return;
}
for(int i = 0; i < n; i++)
{
a[curret_row] = i;
if(check(curret_row)) EightQueen(curret_row + 1, n);
}
}
bool check(int curret_row)
{
for(int i = 0; i < curret_row; i++)
if(a[i] == a[curret_row] || abs(i - curret_row) == abs(a[i] - a[curret_row]))
return false;
return true;
}
};
LeetCode 59. 螺旋矩阵 II
题目链接：点击这里
思路：像洋葱一样，按圈
image.png
class Solution {
public:
vector<vector<int>> a;
vector<vector<int>> generateMatrix(int n) {
a = vector(n, vector<int>(n));
print(0, n, 1, n);
return a;
}
void print(int offset, int size, int counter, int n)
{
if(size <= 0) return;
if(size == 1)
{
a[offset][offset] = counter++;
return;
}
for(int i = 0; i < size - 1; i++) a[0 + offset][i + offset] = counter++;
for(int i = 0; i < size - 1; i++) a[i + offset][n - 1 - offset] = counter++;
for(int i = 0; i < size - 1; i++) a[n - 1 - offset][n - 1 - offset - i] = counter++;
for(int i = 0; i < size - 1; i++) a[n - 1 - offset - i][0 + offset] = counter++;
print(offset + 1, size - 2, counter, n);
}
};
4.递归与链表的结合
LeetCode 206. 反转链表
题目链接：点击这里
image.png
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* cur) {
if(!cur || !cur->next) return cur;
ListNode *head = reverseList(cur->next);
cur->next->next = cur;
cur->next = NULL;
return head;
}
};
LeetCode 24. 两两交换链表中的节点
题目链接：点击这里
image.png
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode cur) {
if(cur == null || cur.next == null) {
return cur;
}
ListNode newhead = swapPairs(cur.next.next);
ListNode temp = cur.next;
cur.next.next = cur;
cur.next = newhead;
return temp;
}
}
5.递归与字符串的结合
LeetCode 344. 反转字符串
题目链接：点击这里
class Solution {
public void reverseString(char[] s) {
reverse(s, 0, s.length - 1);
}
public void reverse(char[] s, int i, int j) {
if(i >= j) {
return ;
}
reverse(s, i + 1, j - 1);
swap(s, i, j);
}
public void swap(char[] s, int i, int j) {
char t = s[i];
s[i] = s[j];
s[j] = t;
}
}
6.递归与树的结合
image.png
image.png
第一类：从下往上返回值
LeetCode 104. 二叉树的最大深度
题目链接：点击这里
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int maxDepth(TreeNode* root) {
if(root == NULL) return 0;
int left = maxDepth(root->left);
int right = maxDepth(root->right);
return max(left, right) + 1;
}
};
LeetCode 111. 二叉树的最小深度
题目链接：点击这里
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int minDepth(TreeNode* root) {
if(root == NULL) return 0;
int left = minDepth(root->left);
int right = minDepth(root->right);
if(left == 0 && right != 0) return right + 1;
else if(left != 0 && right == 0) return left + 1;
return min(left, right) + 1;
}
};
LeetCode 236. 二叉树的最近公共祖先
题目链接：点击这里
image.png
LCA(3,1) = 3 //其中一个节点与3相等 }
LCA(1,3) = 3 //其中一个节点与3相等 }
LCA(5,8) = 3 //分布在3的左右子树中 }
我们可以发现，只要 (一个在3的左边,一个在3的右边) || (其中一个节点的值与root相等），LCA的值都为3
LCA(6,8) = 3 //分布在3的左右子树 }
LCA(8,7) = 3 //分布在3的左右子树中 }
LCA(6,4) = 5 //分布在5的左右子树中 }
当root为5时，与上一情况相同(一个在左一个在右) || (其中一个节点的值与root相同)
LCA(5,2) = 5 //其中一个节点与5相等 }
image.png
image.png
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || root == p || root == q) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if(left != null && right != null) {
return root;
}
return left == null ? right : left;
}
}
image.png
image.png
