疯狂数列 题目描述： 东东从京京那里了解到有一个无现长的数字序列：1，2，2，3，3，3，4，4，4，4，5，5，5，5，5，…（数字k在该序列正好出现k次）。东东想知道这个数字序列的第n项是多少，你能帮帮他么
输入描述: 输入包括一个整数n（1<=n<=10^18）
输出描述: 输出一个整数，即数字序列的第n项，注意long long
示例1 输入 169
输出 18
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); long n=sc.nextInt() ; long x=(long) Math.ceil((Math.sqrt(1+8*n)-1)/2); System.out.println(x); } }java 向上取整用 Math.ceil(double a) 用数学符号 ⌈ ⌉ 表示,比自己大的最小整数； 向下取整用 Math.floor(double a) 用数学符号 ⌊ ⌋ 表示,比自己小的最大整数；
交换使括号匹配 https://www.cnblogs.com/Sunshine-tcf/p/5761816.html 题意： 左右括号匹配 给出一个字符串，是否可以经过且只经过一次交换操作，使得结果串合法. (不能不交换，不能与自己位置交换) “”, “()”, “()()()”, “(()())”, and “(((())))” 都是合法的字符串
Sample Input 3 ())( ()() )))(((
Sample Output Yes Yes No
题解1： ①如果原串本身就合法，长度为2时：”()”->”No” , “)(“->”Yes”. 长度大于2时，一定为”Yes”，因为可以交换两个相同的括号。 ②如果原串非法，那么交换时一定交换的不同的符号（否则没用） 那么符合条件的串一定是把一个 ‘(’ -> ‘)’ 且一个 ‘)’ -> ‘(’ .
考虑如何判断一个串是否合法的过程： 依次处理字符，若是’(‘则入栈，若是’)’则从栈中弹出一个’(‘. 若没有’(‘则不合法. 那么此题就是上述过程的变种，在处理过程中允许两次变换. 由于’(‘->’)’的时机不方便考虑, 这里就只考虑’)’->’(‘. ①. 如果当前是’(‘，直接入栈. ②. 如果当前是’)’，如果栈非空，则弹出一个’(‘; 如果栈空就把当前的’)’变成’(‘入栈. (标记最多只能变化一次).
用flag标记是否有将’)’变为’(‘的操作. 结果栈要么为空，要么全是’(‘. 1、如果整个字串没有被处理完，那么肯定是”No”. 2、如果flag=0, 那么要求没有’(‘剩下. 3、如果flag=1, 那么结果栈中的’(‘只能是两个. “((” -> “()”.
import java.util.Scanner; import java.util.Stack; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); while (n-- > 0) { String str = sc.next(); if (str.length() == 2) { if (str.charAt(0) == '(' && str.charAt(1) == ')') { System.out.println("No"); continue; } } int flag = 0; Stack stack = new Stack(); int i; for (i = 0; i < str.length(); i++) { if (str.charAt(i) == '(') { stack.push('('); } else { if (!stack.isEmpty()) { stack.pop(); } else { if (flag == 1) {//如果桟空，且已经交换过了，无法与当前的）匹配，所以肯定不行 break; } flag = 1; stack.push('('); } } } if (i == str.length()) { if (flag == 0) { if (stack.isEmpty()) { System.out.println("Yes"); } else { System.out.println("No"); } } else { if (stack.size() != 2) { System.out.println("No"); } else { System.out.println("Yes"); } } } else { System.out.println("No"); } } } }题解2： 暴力交换任意两个位置的符号 判断字符串是否合法： 首先统计所有括号数，如果左括号数不等于右括号数，可以直接认为不匹配，不进行计算。 不需要用 Stack，只需要用一个计数量 cnt 统计左括号数量就行，匹配到右括号，就另 cnt- -，当遇到右括号时，如果 cnt<0 就认为不匹配。
import java.util.Scanner; import java.util.Stack; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); while (n-- > 0) { String s = sc.next(); char[] chars=s.toCharArray(); System.out.println(check(chars)? "Yes":"No"); } } private static boolean check(char[] chars) { int lCnt=0,rCnt=0; for(char c:chars){ if(c=='(') lCnt++; else rCnt++; } if(lCnt!=rCnt) return false; for(int i=1;i<chars.length;i++){//交换任意两个位置的字符 for(int j=0;j<i;j++){ swap(chars,i,j); if(isRightStr(chars)){//判断是否合法 return true; } swap(chars,i,j); } } return false; } private static boolean isRightStr(char[] chars) { int cnt=0; for(char c:chars){ if(c=='('){ cnt++; }else{ if(cnt<=0) return false; cnt--; } } return cnt==0; } private static void swap(char[] chars, int i, int j) { char temp=chars[i]; chars[i]=chars[j]; chars[j]=temp; } }题解3： 结合上面两种方法，不用暴力交换，不用桟，用题解1的思路，当时用一个变量表示桟中左括号的数目来代替桟
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); while (n-- > 0) { String s = sc.next(); System.out.println(solve(s)); } } public static String solve(String str) { if (str.length() == 2) { if (str.charAt(0) == '(' && str.charAt(1) == ')') { return "No"; } } int flag = 0; int count=0;//记录左括号的个数 for (int i = 0; i < str.length(); i++) { if(str.charAt(i)=='('){ count++; }else{ if(count!=0){ count--; }else{ if(flag==1){ return "No"; } flag=1; count++; } } } if(flag==0){ if(count==0){ return "Yes"; }else{ return "No"; } }else{ if(count!=2){ return "No"; }else{ return "Yes"; } } } }分解整数 给出一个整数（小于2^63），如果能分解为一个奇数*一个偶数，就输出“这个奇数 和 偶数”，否则输出“No”，如果有多组满足条件，则输出偶数最小的组。
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); while (n-- > 0) { int flag = 0; Long a = sc.nextLong(); if (a % 2 == 1) {// 如果是奇数，肯定不能分 System.out.println("No"); } else { Long y = (long) 2; for (; y <= a; y = y + 2) { if (a % y == 0 && a / y % 2 != 0) { break; } } System.out.println(a / y + " " + y); } } } }反思，简单题不能AC： 1、注意题目属于为2^63，所以要用 Long 2、考注意思考，如果是奇数，就不可能分解成一个偶数和一个奇数相乘了，所以应该优先判断直接返回“No”，如果不加这个判断直接遍历，会超时！如果遇到超时，就要像前面是否可以增加判断，直接跳出，简化程序。
生成回文串 给出一个字符串，去掉若干个字符后，成为回文串，求有多少种去掉的方法。 认为空字符串不是回文串。 本题的意思其实和求 所有的子串是回文串的个数 一样。 https://www.geeksforgeeks.org/count-palindromic-subsequence-given-string/
输入： XYY 输出： 4 对应的抽出字符和子串为： X->YY XY->Y YY->X YX->Y
输入： ABA 输出： 5 对应的抽出字符和子串为： ”->ABA B->AA AB->A BA->A AA->B
题解1： 暴力求解，递归求所有的子串，然后检查每个子串是否是回文串，可能超时
import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Main3 { public static void main(String[] args) { Scanner sc=new Scanner(System.in); String s=sc.next(); int count=0; if(s.length()==0) { System.out.println(count); return; } List<String> slist=getAllSubstrings(s,""); for(String str:slist) { if(check(str)) { count++; } } System.out.println(count); } private static List<String> getAllSubstrings(String str, String substr) {//得到所有子串 List<String> subs = new ArrayList(); if (substr.length() != 0) { subs.add(substr); } for (int i = 0; i < str.length(); i++) { List<String> results = getAllSubstrings(str.substring(i+1), substr+str.charAt(i)); for (String re : results) { subs.add(re); } } return subs; } private static boolean check(String s) { int i=0,j=s.length()-1; while(i<j) { if(s.charAt(i)!=s.charAt(j)) { return false; } i++; j--; } return true; } }题解2： 动态规划 cps[i][j]表示[i,j]子序列中回文串的个数 状态转移公式： if (i == j) return 1 else if (str[i] == str[j)) return cps(i, j-1) +cps(i+1, j) + 1; else return cps(i, j-1) + cps(i+1, j) - cps(i+1, j-1)
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); String str=sc.next(); int N=str.length(); //创建2D数组存储子序列的回文数，cps[a][b]表示[a,b]子序列中回文串的个数 int[][] cps=new int[N+1][N+1]; //每个字符都是1个回文 for(int i=0;i<N;i++){ cps[i][i]=1; } //检查长度为L的子序列是不是回文 for(int L=2;L<=N;L++){ for(int i=0;i<N;i++){ int k=L+i-1; if(k<N){ if(str.charAt(i)==str.charAt(k)){ cps[i][k]=cps[i][k-1]+cps[i+1][k]+1; }else{ cps[i][k]=cps[i][k-1]+cps[i+1][k]-cps[i+1][k-1]; } } } } System.out.println(cps[0][N-1]); } }分成 和 相等的两个子集 https://leetcode.com/problems/partition-equal-subset-sum/description/ 给出一个仅包含正整数的非空数组，检测能够将其分成两个和相等的子集。 每个数组元素不会超过100，数组大小不会超过200。
Example 1: Input: 1,5,11,5 Output: true Explanation: The array can be partitioned as [1, 5, 5] and [11].
Example 2: Input: 1,2,3,5 Output: false Explanation: The array cannot be partitioned into equal sum subsets.
题解1： 暴力遍历所有子序列，如果 和为总和的一半，说明可以，否则不可以。
import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); String str=sc.nextLine(); String[] strs=str.split(","); int[] nums=new int[strs.length]; for(int i=0;i<strs.length;i++){ nums[i]=Integer.parseInt(strs[i].trim()); } System.out.println(canPartition(nums)); } private static boolean canPartition(int[] nums) { int sum=0; for(int num:nums){ sum+=num; } if(sum%2!=0){//如果和是奇数，肯定不能分 return false; } sum/=2; List<Integer> numslist=new ArrayList<>(); for(int x:nums){ numslist.add(x); } List<ArrayList<Integer>> ints=getAllSubArray(numslist,new ArrayList()); for(ArrayList al:ints){ int thissum=0; for(Object x:al){ thissum=thissum+(int)x; } if(thissum==sum){ return true; } } return false; } private static List<ArrayList<Integer>> getAllSubArray(List<Integer> nums, ArrayList<Integer> subnums) { List<ArrayList<Integer>> subs=new ArrayList(); if(subnums.size()!=0){ subs.add((ArrayList<Integer>) subnums.clone());//此处要克隆，不然后面subnums改变了，subs里的也跟着改变 } for(int i=0;i<nums.size();i++){ subnums.add(nums.get(i)); List<ArrayList<Integer>> results=getAllSubArray(nums.subList(i+1, nums.size()),subnums); for(ArrayList al:results){ subs.add(al); } subnums.remove(nums.get(i)); } return subs; } }题解2： 动态规划 0/1背包问题，对于每个数字，我们可以选择或不选择。 设 dp[i][j] 表示总和 j 是否能从前 i 个数字中得到。如果能从 0-i中找到序列，使其和为 j ,则 dp[i][j] 是 true，否则为false.
已知 dp[0][0] is true; 因为0个数字的总和可以为 0 。
转换方程： 对于每一个数字，如果我们不选择它，则 dp[i][j] = dp[i-1][j] ，意味着前 i-1 个数的子序列和可以为 j , dp[i][j] 也能为 j （忽略 nums[i]）;如果我们选择 nums[i] ，则 dp[i][j] = dp[i-1][j-nums[i]] ， 因为 总和 j 需要当前的值 nums[i] , j-nums[i] 包含以前数字的子序列的和。
所以：dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]]
public static boolean canPartition(int[] nums) { int sum = 0; for (int num : nums) { sum += num; } if ((sum & 1) == 1) {//如果和是奇数，肯定不能分 return false; } sum /= 2; int n = nums.length; boolean[][] dp = new boolean[n+1][sum+1]; for (int i = 0; i < dp.length; i++) { Arrays.fill(dp[i], false); } //填充已知的数据 dp[0][0] = true;//前0个数字的总和可以为 0 for (int i = 1; i < n+1; i++) { //前i个数，可以找到和为0的子序列，空序列即可 dp[i][0] = true; } for (int j = 1; j < sum+1; j++) { //前0个数字，不可能有子序列之和大于0 dp[0][j] = false; } for (int i = 1; i < n+1; i++) { for (int j = 1; j < sum+1; j++) { dp[i][j] = dp[i-1][j]; if (j >= nums[i-1]) {//防止数组越界 dp[i][j] = (dp[i][j] || dp[i-1][j-nums[i-1]]); } } } return dp[n][sum]; }被抓小偷个数
题目描述： 有一条很长的队伍，队伍里面一共有n个人。所有的人分为三类：警察，小偷和普通人。 将队伍里面的人从前到后由1到n编号，编号为i的人与编号为j的人的距离为i与j之差的绝对值。 每一个警察有一个能力值x，表示他能够监视与他距离不超过x的所有人， 小偷被警察发现当且仅当他被一个或多个警察监视到。你知道在整条队伍中，一共有多少个小偷会被警察发现吗？
输入: 输入有两行，第一行一个数n(1<=n<=100000)，接下来一行有一个长度为n的字符串，依次表示队伍中的每一个人。如果某一位是1-9的某个数字x， 表示这一位是一个能力值为x的警察；如果某一位是字符X表示这一位是小偷；如果某一位是字符#表示这是一个普通人。输入保证不会出现其它字符。
输出: 输出一个数，整条队伍中被警察发现的小偷总数。
样例输入: 9 X1X#2X#XX
样例输出: 3
思路：从头到尾扫描整个字符串，设置一个power变量表示当前位置的最大警力值，每扫描一个字符则power–，若当前字符代表小偷，则保存在桟里；若是警察，则更新当前的最大警力值power，然后从桟依次删除在该警力范围的小偷。最终遍历完这个字符串的时候，桟里保存了所有不能被警察抓到的小偷在字符串中的索引，由于只遍历了一次字符串，而桟最多只压入n个索引，最多也只删除n个索引，所以时间复杂度仍然为O(n)。
import java.util.Scanner; import java.util.Stack; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); String str=sc.next(); int count=0;//小偷总数 int power=0;//当前位置警力 Stack<Integer> stack=new Stack<Integer>();//存放未被抓的小偷 for(int i=0;i<n;i++){ char c=str.charAt(i); if(c=='X'){ count++; if(power<=0){ stack.push(i); } }else if(Character.isDigit(c)){ int police=c-'0'; power=Math.max(power,police); while(!stack.isEmpty()){ if((i-stack.peek()) <= power){ stack.pop(); }else{ break; } } } power--; } System.out.println(count-stack.size()); } }