<span>蓝桥杯训练2</span>

旧键盘

旧键盘上坏了几个键，于是在敲一段文字的时候，对应的字符就不会出现。现在给出应该输入的一段文字、以及实际被输入的文字，请你列出肯定坏掉的那些键。

输入格式：
输入在 2 行中分别给出应该输入的文字、以及实际被输入的文字。每段文字是不超过 80 个字符的串，由字母 A-Z（包括大、小写）、数字 0-9、以及下划线 _（代表空格）组成。题目保证 2 个字符串均非空。

输出格式：
按照发现顺序，在一行中输出坏掉的键。其中英文字母只输出大写，每个坏键只输出一次。题目保证至少有 1 个坏键。

输入样例：

7_This_is_a_test
_hs_s_a_es

输出样例：

7TI

import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
        @SuppressWarnings("resource")
	Scanner in=new Scanner(System.in);
        String[] a=in.nextLine().toUpperCase().split("");//先将输入的字符串转换为大写，并用字符数组存储到a字符串数组中。
        String b=in.nextLine().toUpperCase();//读入残缺键盘的输入的字符串并存储到b
        String c="";//存储最后输出的字符
        //然后用contains比较两行字符
        for(int i=0;i<a.length;i++){//遍历a字符数组,a.length是求数组的长度.length是数组的成员变量！
            if(!b.contains(a[i])){//判断按键损坏，即如果判断b字符串中不包含a[i]的字符，则进入判断
                if(!c.contains(a[i])) {//判断重字符，即坏键只输出一次，如果c中不包含a[i]的字符，则进入判断
                    c =c+ a[i];//将不相重的字符存入c中
                }
            }
        }
        System.out.println(c);//输出每个坏键
    }
}

while True:
    try:
        originalString = input().upper()    #把输入变为大写
        actualString = input().upper()
        result = []
        for i in originalString:    
            if actualString.find(i) == -1: #如果在第二个字符串没查找到
                if i not in result:      #如果结果集里已经有了则不添加，以免破坏顺序
                    result.append(i)
        print("".join(result))
    except Exception:
        break

完美数列

给定一个正整数数列，和正整数 p，设这个数列中的最大值是 M，最小值是 m，如果 M≤mp，则称这个数列是完美数列。

现在给定参数 p 和一些正整数，请你从中选择尽可能多的数构成一个完美数列。

输入格式：
输入第一行给出两个正整数 N 和 p，其中 N（≤10^​5）是输入的正整数的个数，p（≤10​9）是给定的参数。第二行给出 N 个正整数，每个数不超过 10^​9​​ 。

输出格式：
在一行中输出最多可以选择多少个数可以用它们组成一个完美数列。

输入样例：

10 8
2 3 20 4 5 1 6 7 8 9

输出样例：

8

import java.util.Scanner;
import java.util.Arrays;
public class Main {
    public static void main(String[] args) {
        @SuppressWarnings("resource")//这句是装饰，为了美观
		Scanner in=new Scanner(System.in);
        int n = in.nextInt();//输入第一个数
        int p = in.nextInt();//输入第二个数
        int[] arr = new int[n];//定义一个一维数组
        for(int i = 0;i<n;i++)//遍历循环输入
            arr[i] = in.nextInt();
        Arrays.sort(arr);//对数组进行从小到大排序
        int maxlen = 0;//完美数列最多元素个数
        for(int i = 0;i<n;i++){//i从0开始依次递加作外层循环，a[i]为最小值
        	//System.out.println("i="+i);
            for(int j = i+maxlen;j<n;j++){//最大值从最小值位置加上当前完美数列最多元素个数处开始，a[j]为最大值
            	//System.out.println("j="+j);
                if(arr[j]>arr[i]*p) {//如果不符合完美数列，跳出循环
                    break;
                   }
                maxlen++;//符合条件计数
            }
        }
        System.out.println(maxlen);//输出最多可以选择多少个数可以用它们组成一个完美数列
    }
}

两数相加

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

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

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

题解
我们不断的遍历两个链表，每次遍历都将链表a和链表b的值相加，再赋给链表a。如果有进位我们还需要记录一个进位标志。
循环的条件是链表a不为空或者链表b不为空，这样当整个循环结束时，链表就被串起来了。
当循环结束时，如果进位标志>0还需要处理下边界条件。
我们不用生成一个新的节点，直接将两个节点相加的值赋给节点a就可以了，这样只用改变节点的内容，速度会更快一些

class Solution {
	public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
		ListNode p = null;
		ListNode a = l1;
		ListNode b = l2;
		//定义一个进位标志
		int carry = 0;
		while(a!=null || b!=null) {
			//a和b节点的值相加，如果有进位还要加上进位的值
			int val = (a==null?0:a.val) + (b==null?0:b.val) + carry;
			//根据val判断是否有进位
			carry = val>=10? 1:0;
			//不管有没有进位，val都应该小于10
			val = val%10;
			p = (a==null? b : a);
			p.val = val;
			//a和b指针都前进一位
			a = (a==null? null : a.next);
			b = (b==null? null : b.next);
			//根据a和b是否为空，p指针也前进一位
			p.next = (a==null? b : a);
		}
		//不要忘记最后的边界条件，如果循环结束carry>0说明有进位需要处理这个条件
		if(carry>0) {
			p.next = new ListNode(1);
		}
		//每次迭代实际上都是将val赋给a指针的，所以最后返回的是l1
		return l1;
	}
}

class Solution(object):
	def addTwoNumbers(self, l1, l2):
		# 定义一个进位标志
		a,b,p,carry = l1,l2,None,0
		while a or b:
			# a和b节点的值相加，如果有进位还要加上进位的值
			val = (a.val if a else 0)+(b.val if b else 0)+carry
			# 根据val判断是否有进位,不管有没有进位，val都应该小于10
			carry,val = val/10 if val>=10 else 0,val%10
			p,p.val = a if a else b,val
			# a和b指针都前进一位
			a,b = a.next if a else None,b.next if b else None
			# 根据a和b是否为空，p指针也前进一位
			p.next = a if a else b
		# 不要忘记最后的边界条件，如果循环结束carry>0说明有进位需要处理这个条件 
		if carry:
			p.next = ListNode(carry)
		# 每次迭代实际上都是将val赋给a指针的，所以最后返回的是l1 
		return l1

寻找两个有序数组的中位数

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0

示例 2:

nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

解法

• 其实，我们不需要将两个数组真的合并，我们只需要找到中位数在哪里就可以了。

• 开始的思路是写一个循环，然后里边判断是否到了中位数的位置，到了就返回结果，但这里对偶数和奇数的分类会很麻烦。当其中一个数组遍历完后，出了 for 循环对边界的判断也会分几种情况。总体来说，虽然复杂度不影响，但代码会看起来很乱。

• 首先是怎么将奇数和偶数的情况合并一下。

• 用 len 表示合并后数组的长度，如果是奇数，我们需要知道第 （len+1）/2 个数就可以了，如果遍历的话需要遍历 int(len/2 ) + 1 次。如果是偶数，我们需要知道第 len/2和 len/2+1 个数，也是需要遍历 len/2+1 次。所以遍历的话，奇数和偶数都是 len/2+1 次。

• 返回中位数的话，奇数需要最后一次遍历的结果就可以了，偶数需要最后一次和上一次遍历的结果。所以我们用两个变量 left 和 right，right 保存当前循环的结果，在每次循环前将 right 的值赋给 left。这样在最后一次循环的时候，left 将得到 right 的值，也就是上一次循环的结果，接下来 right 更新为最后一次的结果。

• 循环中该怎么写，什么时候 A 数组后移，什么时候 B 数组后移。用 aStart 和 bStart 分别表示当前指向 A 数组和 B 数组的位置。如果 aStart 还没有到最后并且此时 A 位置的数字小于 B 位置的数组，那么就可以后移了。也就是aStart＜m&&A[aStart]< B[bStart]。

• 但如果 B 数组此刻已经没有数字了，继续取数字 B[ bStart ]，则会越界，所以判断下 bStart 是否大于数组长度了，这样 || 后边的就不会执行了，也就不会导致错误了，所以增加为 aStart＜m&&(bStart) >= n||A[aStart]<B[bStart]) 。

public double findMedianSortedArrays(int[] A, int[] B) {
    int m = A.length;
    int n = B.length;
    int len = m + n;
    int left = -1, right = -1;
    int aStart = 0, bStart = 0;
    for (int i = 0; i <= len / 2; i++) {
        left = right;
        if (aStart < m && (bStart >= n || A[aStart] < B[bStart])) {
            right = A[aStart++];
        } else {
            right = B[bStart++];
        }
    }
    if ((len & 1) == 0)
        return (left + right) / 2.0;
    else
        return right;
}

from typing import List
class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        m = len(nums1)
        n = len(nums2)
        nums1.extend(nums2)

        nums1.sort()

        if (m + n) & 1:
            return nums1[(m + n - 1) >> 1]
        else:
            return (nums1[(m + n - 1) >> 1] + nums1[(m + n) >> 1]) / 2