蓝桥杯定向刷题：递归篇

1、合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode root = new ListNode();
        ListNode temp = root;
        while(l1 != null && l2 != null){
            if(l1.val > l2.val){
                temp.next = l2;
                temp = temp.next;
                l2 = l2.next;
            }else{
                temp.next = l1;
                temp = temp.next;
                l1 = l1.next;
            }
        }
        if(l1 == null)
            temp.next = l2;
        else if(l2 == null)
            temp.next = l1;
        return root.next;
    }
}

经验：

水题一遍过，注意while逻辑。

2.二叉树坡度

给定一个二叉树，计算整个树的坡度。

一个树的节点的坡度定义即为，该节点左子树的节点之和和右子树节点之和的差的绝对值。如果没有左子树的话，左子树的节点之和为 0 ；没有右子树的话也是一样。空结点的坡度是 0 。

整个树的坡度就是其所有节点的坡度之和。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int gradroot = 0;
    public int findTilt(TreeNode root) {
        if(root == null)
            return 0;
        caculate(root);
        return gradroot;
    }

    public int caculate(TreeNode root){
        if(root.left == null && root.right == null){
            return root.val;
        }else{
            int left;
            int right;
            if(root.left == null)
                left = 0;
            else
                left = caculate(root.left);
            if(root.right == null)
                right = 0;
            else
                right = caculate(root.right);
            gradroot += Math.abs(right - left);
            return root.val + right + left;
        }
    }
}

经验：

此题一遍过，有一定难度，本来还想着再构造一棵树来记录值的后来发现返回值填和，坡度直接累加即可！

3.二叉搜索树最小节点距离

给定一个二叉搜索树的根节点 root，返回树中任意两节点的差的最小值。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    LinkedList<Integer> list = new LinkedList<Integer>();
    public int minDiffInBST(TreeNode root) {
        getValue(root);
        Collections.sort(list);
        int min = Integer.MAX_VALUE;
        for(int i = 0; i < list.size() - 1; i++){
            int temp = Math.abs(list.get(i) - list.get(i + 1));
            if(temp < min)
                min = temp;
        }
        return min;
    }

    public void getValue(TreeNode root){
        if(root == null){

        }else if(root.left ==  null && root.right == null){
            list.add(root.val);
        }else{
            list.add(root.val);
            getValue(root.right);
            getValue(root.left);
        }
    }
}

经验：

（1）DFS遍历取数，用LinkedList保存val。

（2）新知识，Collections提供了很多快捷方法，譬如最快乐的sort。

（3）该背api了。。。。

4.递增顺序查找树

给你一个树，请你按中序遍历重新排列树，使树中最左边的结点现在是树的根，并且每个结点没有左子结点，只有一个右子结点。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    ArrayList<Integer> list = new ArrayList<Integer>();
    public TreeNode increasingBST(TreeNode root) {
        midtravers(root);
        TreeNode result = new TreeNode();
        TreeNode temp = result;
        for(int i = 0; i < list.size(); i++){
            temp.right = new TreeNode(list.get(i));
            temp = temp.right;
        }
        return result.right;
    }
    public void  midtravers(TreeNode root){
        if(root != null){
            midtravers(root.left);
            list.add(root.val);
            midtravers(root.right);
        }
    }

}

经验：

（1）所谓的中序，先序，后序，是相对于根节点的访问顺序来说的。

5.二叉搜索树的范围和

给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        if(root == null){
            return 0;
        }else if(root.left == null && root.right == null){
            if(root.val >= low && root.val <= high)
                return root.val;
            else
                return 0;
        }else{
            int left = rangeSumBST(root.left, low, high);
            int right = rangeSumBST(root.right, low, high);
            int value;
            if(root.val >= low && root.val <= high)
                value = root.val + left + right;
            else
                value = left + right;
            return value;
        }
    }
}

经验：

一遍过，不说话

6.第N个泰波那契数

泰波那契序列 Tn 定义如下：

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给你整数 n，请返回第 n 个泰波那契数 Tn 的值。

class Solution {
    public int tribonacci(int n) {
        if(n == 0)
            return 0;
        else if(n == 1)
            return 1;
        else if( n == 2)
            return 1;
        else{
            int[] tribo = new int[n + 1];
            tribo[0] = 0;
            tribo[1] = 1;
            tribo[2] = 1;
            for(int i = 3; i <= n; i++)
                tribo[i] = tribo[i - 1] + tribo[i - 2] + tribo[i - 3];
            return tribo[n];
        }
    }
}

经验：

憨批题目，一遍打了递归的label，另一边得用数组，不然要超时。

7.两数相加

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int flag = 0;
        ListNode result = new ListNode();
        ListNode temp = result;
        while(l1 != null && l2 != null){
            temp = temp.next;
            int val = l1.val + l2.val + flag;
            temp = new ListNode(val % 10);
            flag = (val) / 10;
            l1 = l1.next;
            l2 = l2.next;
            
        }
        while(l1 != null){
            temp = temp.next;
            int val = l1.val + flag;
            temp = new ListNode(val % 10);
            flag = (val) / 10;
            l1 = l1.next;
        }
        while(l2 != null){
            temp = temp.next;
            int val = l2.val + flag;
            temp = new ListNode(val % 10);
            flag = (val) / 10;
            l2 = l2.next;
            
        }
        return result.next;
    }
}

经验：全程报nullpointer的异常或者就是读不到正确的链表点，TM的和以前写的基本一样的代码到现在都不知道错在哪里了。

（2021/4/13记）

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode result = new ListNode();
        ListNode temp = result;
        int flag = 0;
        while(l1 != null && l2 != null){
            temp.next = new ListNode();
            temp = temp.next;
            int num = (l1.val + l2.val + flag);
            temp.val = num % 10;
            flag = num / 10;
            l1 = l1.next;
            l2 = l2.next; 
        }
        while(l1 != null){
            temp.next = new ListNode();
            temp = temp.next;
            int num = (l1.val + flag);
            temp.val = num % 10;
            flag = num / 10;
            l1 = l1.next;
        }
        while(l2 != null){
            temp.next = new ListNode();
            temp = temp.next;
            int num = (l2.val + flag);
            temp.val = num % 10;
            flag = num / 10;
            l2 = l2.next;
        }
        if(flag == 1)
            temp.next = new ListNode(1);
        return result.next;
    }
}

经验：

此版本的代码在next方法和定义新变量的地方进行了修改（果然早上起来脑子好像就正常了），此问题主要是对引用的概念不熟悉干出来的蠢事（我是憨批），next的值赋值给temp本质上是两者都引用变量，此时修改temp的值只会修改其指向，并不会改变原来那个引用对象。

8.电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

class Solution {

    public List<String> letterCombinations(String digits) {
        HashMap<Character, String> hashmap = new HashMap<Character, String>();
        hashmap.put('2', "abc");
        hashmap.put('3', "def");
        hashmap.put('4', "ghi");
        hashmap.put('5', "jkl");
        hashmap.put('6', "mno");
        hashmap.put('7', "pqrs");
        hashmap.put('8', "tuv");
        hashmap.put('9', "wxyz");
        if(digits.equals("")){
           ArrayList<String> list = new ArrayList<String>();
           return list;
        }
            
        else if(digits.length() == 1){
            String temp = hashmap.get(digits.charAt(0));
            ArrayList<String> list = new ArrayList<String>();
            for(int i = 0; i < temp.length(); i++){
                list.add(temp.charAt(i) + "");
            }
            return list;
        }else{
            String temp = hashmap.get(digits.charAt(0));
            ArrayList<String> list = new ArrayList<String>();
            ArrayList<String> target = (ArrayList<String>)letterCombinations(digits.substring(1));
            for(int i = 0; i < temp.length(); i++){
                String tempstr = temp.charAt(i) + "";
                for(int j = 0; j < target.size(); j++){
                    list.add(tempstr.concat(target.get(j)));
                }
            }
            return list;
        }

    }
}

经验：

一遍AC，不过做法复杂度很高，也是看到了他字符串长度限制在4才敢这么干的。

9.两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null)
            return null;
        else if(head.next == null){
            return head;
        }else{
            ListNode temp = head;
            ListNode temb = head.next;
            temp.next = swapPairs(head.next.next);
            head = temb;
            head.next = temp;
            return head;
        }
    }
}

经验：

主要还是指向问题和引用问题，一遍AC

10.验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。

节点的右子树只包含大于当前节点的数。

所有左子树和右子树自身必须也是二叉搜索树。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    ArrayList<Integer> list = new ArrayList<Integer>();
    public boolean isValidBST(TreeNode root) {
        midTravers(root);
        for(int i = 0; i < list.size() - 1; i++){
            if(list.get(i) >= list.get(i + 1))
                return false;
        }
        return true;
    }

    public void midTravers(TreeNode root){
        if(root == null)
            return;
        else{
            midTravers(root.left);
            list.add(root.val);
            midTravers(root.right);
        }
    }
}

经验：

中序遍历结果为升序链表

11.二叉树的右视图

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        if(root == null){
            ArrayList<Integer> list = new ArrayList<Integer>();
            return list;
        }
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        ArrayList<Integer> result = new ArrayList<Integer>();
        int depth = 0;
        queue.add(root);
        while(queue.size() != 0){
            int size = queue.size();
            for(int i = 0; i < size; i++){
                if(i != size - 1){
                    TreeNode temp = queue.getFirst();
                    if(temp.left != null)
                        queue.add(temp.left);
                    if(temp.right != null)
                        queue.add(temp.right);
                    queue.removeFirst();
                }else{
                    TreeNode temp = queue.getFirst();
                    if(temp.left != null)
                        queue.add(temp.left);
                    if(temp.right != null)
                        queue.add(temp.right);
                    result.add(temp.val);
                    queue.removeFirst();
                }
            }
        } 
        return result;
    }
}

经验：

第一次BFS，一遍过。

12.至少有K个重复字符的最长字符串

给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串，要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。

class Solution {
    public int longestSubstring(String s, int k) {
        HashMap<Character, Integer> countMap = new HashMap<Character, Integer>();
        for(int i = 0; i < 26; i++)
        	countMap.put((char)('a' + i), 0);
        for(int i = 0; i < s.length(); i++) {
        	char temp = s.charAt(i);
        	countMap.replace(temp, countMap.get(temp) + 1);
        }
        	
    	for(int i = 0; i < 26; i++){
    		char temp = (char)('a' + i);
            if(s.indexOf(temp) != -1) {
            	if(countMap.get(temp) < k) {
            		String[] splitedLiStrings = s.split(temp + "");
            		int maxLength = 0;
            		for(int j = 0; j < splitedLiStrings.length; j++) {
            			int templength = longestSubstring(splitedLiStrings[j], k);
            			if(templength > maxLength)
            				maxLength = templength;
            		}
            		return maxLength;
            			
            	}
            }
        }
    	return s.length();
    }
}

经验：

此题的分治思想比较独特，如果一个字母的总长度不达标，就根据他全部裁开再寻找字符串。

————————————不定期更新————————————

蓝桥杯定向刷题：递归篇

继续阅读

Codeforces 1417 D. Make Them Equal(思维+构造)

查找算法之二分查找查找算法之二分查找

查找算法学习之二分查找（Python版本）——BinarySearch

CQ V1.0分词bates(基于双数组tire树)—应该是目前最快的中文分词算法

Command Network(POJ 3164)---定根最小树形图模板题题目描述输入格式输出格式输入样例输出样例分析源程序

开源低带宽语音编解码器

241 Different Ways to Add Parentheses（C代码版）

【趋高机器视觉】机器视觉技术原理解析及解决方案

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制规程及特点4． CSMA/CD协议5． CSMA/CD的优点6．结束语

极大似然法(ML)与最大期望法(EM)

C++ 第十五周报告1--《冒泡法排序》

笔试面试题目：滑动窗口(二)

数据结构与算法（27）——排序（二）

Dijkstra--简易版（最短路径）

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

hdu7108哈希