Recursive training

1374 生成每种字符都是奇数个的字符串

解题思路

Analyze the key skills of a good question,
用’a’,'b’最简单.nReturn if it is an odd numbern个’a’即可
n如果为偶数,就返回n-1个’a’再加上一个’b’即可.

代码

class Solution {
    
public:
    string generateTheString(int n) {
    
        string s="";
        if(n % 2== 0){
    
            for(int i = 0;i<n-1;i++)
                s += 'a';
            s += 'b';
        }else{
    
            for(int i = 0;i<n;i++)
                s += 'a';
        }
        
        return s;
    }
};

622 设计循环队列

解题思路

The queue must point to the initial position,and the end positionfront和rear.
The question also records the length of the queue,用于进行front以及rearThe judgment of the remainder of the cycle.

注意：
1.队列长度为kBut actually the largest index is k-1,In addition, we need to vacate a position,To distinguish the starting position and the rest of the situation whether the queue is full.So the length of the final application is k+1.为了对front以及rearTake the remainder and we are rightk2设置为k+1.
2.We use the initial herefront= 0,rear = -1;的方式.If the queue is empty thenrear+1 == front为true.
3.Every time we empty that grid isfronta grid in front.
4.For the rest, it is determined whether it is full before each insertion,Check whether it is empty before deleting.

代码

class MyCircularQueue {
    
public:
	vector<int> ans;
	int front;
	int rear;
	int k2;
	//构造器,设置队列长度为 k .
    MyCircularQueue(int k) {
    
        front = 0;
        rear = -1;
        k2 = k+1;
        ans = vector<int>(k+1);//Open up such a large space in advance 
    }
    //向循环队列插入一个元素.如果成功插入则返回真.
    bool enQueue(int value) {
    
    	if(isFull()) return false;
    	else{
    
            rear++;rear %= k2; //Remember to take the remainder after adding each step.
    		ans[rear] = value;
    		
			return true;
    	}
			
    }
    //从循环队列中删除一个元素.如果成功删除则返回真.
    bool deQueue() {
    
		if(isEmpty())return false;
		else{
    
			front += 1;
			front %= k2;
			return true;
		}
    }
    //从队首获取元素.如果队列为空,返回 -1 .
    int Front() {
    
        if(isEmpty())return -1;
        else
		    return ans[front];
    }
    //获取队尾元素.如果队列为空,返回 -1 .
    int Rear() {
    
        if(isEmpty()) return -1;
        else
		    return ans[rear];
    }
    //检查循环队列是否为空.
    bool isEmpty() {
    
		return 	rear + 1 == front;
    }
    //检查循环队列是否已满.
    bool isFull() {
    
    	//The starting moment is the same as this case (rear+1) % k2 == front,So empty one. 
		return 	(rear + 2) % k2 == front;
    }
};

24 两两交换链表中的结点

解题思路

首先我们要知道,As long as the number of remaining unswapped nodes is 1或0Then the exchange can be stopped.

代码

/** * 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 {
    
    ListNode* node;
public:
    ListNode* swapPairs(ListNode* head) {
    
        if(head == nullptr || head->next == nullptr){
    
            return head;
        }
        ListNode* newhead = head->next;//After the exchangehead->next打头,Then directly let the head pointer point to the node.
        head->next = swapPairs(newhead->next);//要知道headThe pointed node will be connected to the following node,则重新更新head->next.
        newhead->next = head;//Connect the current head node to the second node.
        return newhead;//And the next node to be returned is still the first node.
    }
};

572 另一棵树的子树

解题思路

理解题意：Just walk byroot树的每个结点,combine it withsubRootA deep search comparison is done for the rooted tree.
通过checkIterate over each node in turn,其含义为：The current node succeeds or the left subtree of the current node succeeds,Or the right subtree of the current node is successful.
然后进入dfsmatch in sequence,Only if both nodes are empty,The description can be recursive to here and has not beenreturn false 则return true;

代码

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
class Solution {
    
public:
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
    
        /* 1.Start from the same root node,递归 */
        return check(root,subRoot);
    }
    bool check(TreeNode* root,TreeNode* subRoot){
    
        if(!root){
    
            return false;
        }
        return dfs(root,subRoot) || check(root->left,subRoot)||check(root->right,subRoot);
    }
    //Matches if two trees are exactly the same
    bool dfs(TreeNode* root, TreeNode* subRoot){
    
        if(!root && !subRoot)return true;//All return emptytrue
        if(!root || !subRoot||root->val != subRoot->val){
    //At least one is empty,返回false;
            return false;
        }
        /* Only the value of this pair of nodes is equal does not mean that the descendant nodes of this node are also correspondingly equal. Only after the corresponding node is judged, it cannot gofalse,until after the last leaf node,都为空了,It can be judged that the two trees are not different so far,则 返回true. */
        // if(root && subRoot){
    
        // return root->val == subRoot->val;
        // }
        return dfs(root->left,subRoot->left) && dfs(root->right,subRoot->right);
    }
};

112 路径总和

解题思路

代码

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
class Solution {
    
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
    
        return dfs(root,0,targetSum);
    }
    bool dfs(TreeNode* root,int sum,int targetSum){
    
        if(root==nullptr) return false;//首先要 判断是否为空,要不然sum已经被赋值为0了,可能遇到targetSum的第一个值为0,而root为空的情况.
        if(root->left == nullptr && root->right==nullptr) return (sum+root->val) == targetSum;
         //Judgment can only be made if the left and right children are empty.The description has only reached the leaf node.
        // int leftSum = 0,rightSum = 0;Can't declare any more,will be assigned every time 成0的,Still have to put it in the function parameter.
       return
       dfs(root->left,sum+root->val,targetSum) ||
        
        dfs(root->right,sum+root->val,targetSum);
         
    }
};

解题思路

The first is to pay attention to the problem of carry,Each addition is the corresponding node value and carry of the two linked listscount相加,
Take the form of a new linked list,Build each node recursively,As well as each node and the previous nodenext联系.
Only if both nodes are empty and the carry is 0,时才会返回nullptr.

代码

/** * 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* addTwoNumbers(ListNode* l1, ListNode* l2) {
    
        return dfs(l1,l2,0);
    }
    ListNode* dfs(ListNode*l,ListNode* r,int count){
    
        if(!l&&!r&&!count)return nullptr;
        int sum = (l?l->val:0) + (r?r->val:0) + count;//必须要加括号,否则结果不对,The addition operator has higher precedence than the ternary operator
        count = sum /10;
        ListNode * node = new ListNode(sum%10);
        node->next = dfs(l?l->next:nullptr,r?r->next:nullptr,count);
        return node;
    }
};

95 不同的二叉搜索树II

解题思路

代码

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
class Solution {
    
public:
    vector<TreeNode*> generateTrees(int n) {
    
        if(!n){
    
            return {
    };
        }
        return generateTrees(1,n);
    }
    vector<TreeNode*> generateTrees(int start,int end){
    
        if(start > end){
    //It is equivalent to returning the case of this node.
            return {
    nullptr};//Must be empty 返回,Only in the left and right children set 出现.
        }
        vector<TreeNode*> allTrees;
        for(int i = start;i<=end;i++){
    //从start到endcan be used as a root node
            vector<TreeNode*> leftTrees = generateTrees(start,i-1);//Note that any one of the left and right child queues can act as its left and right child.
            vector<TreeNode*> rightTrees = generateTrees(i+1,end);
            //Recursively until the left and right children are empty,,That is, step twogenerateTrees()返回两个nullptr.
            //下面currTreeThe left and right children are set tonullptr,而currTree为叶子结点,
            for(auto& left: leftTrees)
                for(auto& right: rightTrees){
    
                    TreeNode* currTree = new TreeNode(i);
                    currTree->left = left;
                    currTree->right = right;
                    allTrees.emplace_back(currTree);
                }
        }
        return allTrees;
    }
};