蓝桥杯每日一题冲刺国赛
1.
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
示例 2：
输入：s = "a"
输出：[["a"]]
class Solution { List<List> res = new ArrayList(); List list = new ArrayList(); int n; boolean[][] f; public List<List> partition(String s) { n = s.length(); f = new boolean[n][n]; for (int i = 0; i = 0; i--) { for (int j = i + 1; j < n ; j++) { f[i][j] = (s.charAt(i) == s.charAt(j)) && f[i + 1][j - 1]; } } dfs(0,s); return res; } public void dfs(int i,String s) { if (i == n) { res.add(new ArrayList(list)); return; } for (int j = i; j < n; j++) { if (f[i][j]) { list.add(s.substring(i,j + 1)); dfs(j + 1,s); list.remove(list.size() - 1); } } }}2.
给你一个整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
class Solution { int res = 0; public int findTargetSumWays(int[] nums, int target) { int len = nums.length; if (len == 1) if (Math.abs(nums[0]) == Math.abs(target)) return 1; back(0,0,len,target,nums); return res; } public void back(int sum,int count,int len,int target,int[] nums) { if (count == len) { if (sum == target) res++; return; } back(sum+nums[count],count+1,len,target,nums); back(sum-nums[count],count+1,len,target,nums); }}3.
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
class Solution { boolean isSuccess; public boolean exist(char[][] board, String word) { if (board == null) return false; int len1 = board.length; int len2 = board[0].length; boolean[][] isVisited = new boolean[len1][len2]; isSuccess = false; for (int i = 0; i < len1; i++) { for (int j = 0; j < len2; j++) { back(i,j,len1,len2,board,word,0,isVisited); } } return isSuccess; } public void back(int i,int j,int len1,int len2,char[][] board, String word,int pos,boolean[][] isVisited) { if (i < 0 || j = len1 || j >= len2 || isVisited[i][j] || board[i][j] != word.charAt(pos) || isSuccess) return; if (pos == word.length() - 1) { isSuccess = true; return; } isVisited[i][j] = true; back(i + 1,j,len1,len2,board,word,pos + 1,isVisited); back(i - 1,j,len1,len2,board,word,pos + 1,isVisited); back(i,j+1,len1,len2,board,word,pos + 1,isVisited); back(i,j-1,len1,len2,board,word,pos + 1,isVisited); isVisited[i][j] = false; }}4.
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
class Solution { public int lengthOfLongestSubstring(String s) { int[] last = new int[128]; for(int i = 0;i < 128;i++) { last[i] = -1; } int n = s.length(); int start = 0; int res = 0; for(int i = 0;i < n;i++) { int index = s.charAt(i); start = Math.max(start,last[index] + 1); res = Math.max(res,i - start + 1); last[index] = i; } return res; }}5.
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
class Solution { public String longestPalindrome(String s) { int len = s.length(); if(len < 2) { return s; } int maxlen = 1; int begin = 0; char[] arr = s.toCharArray(); Boolean[][] isSuccess = new Boolean[len][len]; for(int i = 0;i < len;i++) { isSuccess[i][i] = true; } for(int l = 2;l <= len;l++) { for(int i = 0;i = len) { break; } if(arr[i] != arr[j]) { isSuccess[i][j] = false; }else { if(j - i maxlen) { maxlen = j - i + 1; begin = i; } } } return s.substring(begin,begin+maxlen); }}6.排列
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]
示例 2：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
class Solution { List<List> lists = new ArrayList(); List list = new ArrayList(); int len; public List<List> permuteUnique(int[] nums) { len = nums.length; boolean[] isVisit = new boolean[len]; dfs(0,isVisit,nums); return lists; } public void dfs(int m,boolean[] isVisit,int[] nums) { if (m == len) { if (!lists.contains(list)) lists.add(new ArrayList(list)); return; } for (int i = 0; i < len; i++) { if (isVisit[i]) continue; isVisit[i] = true; list.add(nums[i]); dfs(m + 1,isVisit,nums); isVisit[i] = false; list.remove(list.size() - 1); } }}7.
给定一个整数数组，找出总和最大的连续数列，并返回总和。
示例：
输入： [-2,1,-3,4,-1,2,1,-5,4]
输出： 6
解释： 连续子数组 [4,-1,2,1] 的和最大，为 6。
class Solution { public int maxSubArray(int[] nums) { int len = nums.length; int[] arr = new int[len]; int max = Integer.MIN_VALUE; arr[0] = nums[0]; max = Math.max(max,arr[0]); for (int i = 1; i < len; i++) { arr[i] = Math.max(nums[i],arr[i - 1] + nums[i]); max = Math.max(arr[i],max); } return max; }}