- 409. 最长回文串">Leecode 409. 最长回文串
- 5. 最长回文子串">5. 最长回文子串
Leetcode 1.两数字和
//暴力法// class Solution {// public int[] twoSum(int[] nums, int target) {// for(int i=0;i<nums.length;i++){// for(int j=i+1;j<nums.length;j++){// if(nums[j] == target - nums[i])// return new int []{i,j};// }// }// return new int [2];// }// }//哈希class Solution{public int[] twoSum(int[] nums, int target){Map<Integer,Integer> map = new HashMap<>();for(int i=0;i<nums.length;i++){int target_new = target-nums[i];if(map.containsKey(target_new)){return new int []{i,map.get(target_new)};}else{map.put(nums[i],i);}}return new int[2];}}
Leetcode 15: 三数之和
class Solution {public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums);int length = nums.length;List<List<Integer>> ans = new ArrayList<List<Integer>>();for(int first=0;first<length;++first){//第三个数从后往前int third = length-1;int target = -nums[first];if(first>0&&nums[first]==nums[first-1])continue;for(int second =first+1;second<length;++second){if(second>first+1&&nums[second]==nums[second-1])continue;while(second<third&&(nums[second]+nums[third])>target){--third;}if(second==third)break;if(nums[second]+nums[third]==target){List<Integer> list = new ArrayList<Integer>();list.add(nums[first]);list.add(nums[second]);list.add(nums[third]);ans.add(list);}}}return ans;}}
Leetcode 16:最近的三数之和
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int best = 1000000;
for(int first =0;first<nums.length;first++){
if(first>0 && nums[first] == nums[first-1]) continue;
int second = first+1;
int third = nums.length-1;
while(second<third){
int sum = nums[first]+nums[second]+nums[third];
if(sum==target) return target;
if(Math.abs(sum-target)<Math.abs(best-target)){
best =sum;
}
if(sum>target){
third--;
}else{
second++;
}
}
}
return best;
}
}
Leetcode 3 无重复字符最长子串
class Solution {
public int lengthOfLongestSubstring(String s) {
if(s==null||s=="") return 0;
LinkedList<Character> queue = new LinkedList<>();
int index =0;
int MaxLen = 0;
while(index<s.length()){
while(queue.contains(s.charAt(index))&& !queue.isEmpty()){
queue.poll();
}
queue.offer(s.charAt(index));
MaxLen = Math.max(MaxLen,queue.size());
index ++;
}
return MaxLen;
}
}
Leetcode 5 最长回文字符串 动态规划
class Solution {
public String longestPalindrome(String s) {
int maxLen = 1;
int len = s.length();
int begin =0;
if(len<2) return s;
boolean dp[][] = new boolean[len][len];
for(int i=0;i<len;i++){
dp[i][i] =true;
}
for(int j =1;j<len;j++){
for(int i=0;i<j;i++){
if(s.charAt(i)!=s.charAt(j)) dp[i][j] =false;
else{
if(j-i<3) dp[i][j] = true;
else dp[i][j] = dp[i+1][j-1];
}
if(dp[i][j]&&j-i+1>maxLen){
maxLen = j-i+1;
begin =i;
}
}
}
return s.substring(begin,begin+maxLen);
}
}
Leecode 409. 最长回文串
输入:
“abccccdd”
输出:
7
//hashMap hashSet 实现
public int longestPalindrome(String s){
HashMap<Character,Integer> map = new HashMap<>();
//使用hashMap统计字符个数
for(char c:s.toCharArray()){
map.put(c,map.getOrDefault(c,0)+1);
}
int len = 0;
boolean flag= false;
for(Character set :map.keySet()){
int count = map.get(set);
if(count>0&&count%2==0)len += count;
else if(count%2!=0) {
flag = true;
len+=(count-1);
}
}
return flag ? len+1: len;
}
解释:
我们可以构造的最长的回文串是”dccaccd”, 它的长度是 7。
5. 最长回文子串
class Solution {
//动态规划
public String longestPalindrome(String s) {
// [i,j] 判断 dp[i][j] = dp[i+1][j-1] && s[i]==s[j];
int maxLen =1;
int len = s.length();
int begin =0;
if(len<2) return s;
boolean dp[][] = new boolean[len][len];
for(int i=0;i<len;i++){
dp[i][i] = true;
}
for(int j =1;j<len;j++){
for(int i=0;i<j;i++){
if(s.charAt(i)!=s.charAt(j)) dp[i][j] = false;
else{
if(j-i<3) dp[i][j] = true;
else dp[i][j] = dp[i+1][j-1];
}
if(dp[i][j] && j-i+1>maxLen){
maxLen = j-i+1;
begin =i;
}
}
}
return s.substring(begin,begin+maxLen);
}
}
Leetcode 7:整数反转
class Solution {
public int reverse(int x) {
int rev = 0;
while (x != 0) {
int pop = x % 10;
x /= 10;
if (rev > Integer.MAX_VALUE/10 || (rev == Integer.MAX_VALUE / 10 && pop > 7)) return 0;
if (rev < Integer.MIN_VALUE/10 || (rev == Integer.MIN_VALUE / 10 && pop < -8)) return 0;
rev = rev * 10 + pop;
}
return rev;
}
}
Leetcode 9:回文数
class Solution {
public boolean isPalindrome(int x) {
//小于0或者不等于0且10的倍数不是回文数
if(x<0||(x!=0&&x%10==0))return false;
int reverseNum =0;
while(x>reverseNum){
reverseNum = reverseNum * 10 + x % 10;
x = x/10;
}
return x == reverseNum || x == reverseNum /10;
}
}
Leetcode 11:盛最多水的容器
class Solution {
public int maxArea(int[] height) {
//双指针，移动指针的较小者
int left = 0;
int right =height.length-1;
int maxArea =0;
while(left!=right){
if(height[left]<height[right]){
maxArea =Math.max(maxArea,height[left]*(right-left));
left++;
}else{
maxArea =Math.max(maxArea,height[right]*(right-left));
right--;
}
}
return maxArea;
}
}
Leetcode 14:最长公共前缀
class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
String str = strs[0];
int len = str.length();
int count = strs.length;
for(int i=0;i<len;i++){
for(int j=1;j<count;j++){
if(i==strs[j].length()||str.charAt(i)!=strs[j].charAt(i))
return str.substring(0,i);
}
}
return str;
}
}
Leetcode 214 最短回文字符串
class Solution {
public String shortestPalindrome(String s) {
int n = s.length();
int[] fail = new int[n];
Arrays.fill(fail, -1);
for (int i = 1; i < n; ++i) {
int j = fail[i - 1];
while (j != -1 && s.charAt(j + 1) != s.charAt(i)) {
j = fail[j];
}
if (s.charAt(j + 1) == s.charAt(i)) {
fail[i] = j + 1;
}
}
int best = -1;
for (int i = n - 1; i >= 0; --i) {
while (best != -1 && s.charAt(best + 1) != s.charAt(i)) {
best = fail[best];
}
if (s.charAt(best + 1) == s.charAt(i)) {
++best;
}
}
String add = (best == n - 1 ? "" : s.substring(best + 1));
StringBuffer ans = new StringBuffer(add).reverse();
ans.append(s);
return ans.toString();
}
}
Leetcode 60:第k个排列
class Solution {
public String getPermutation(int n, int k) {
//首先获得n的全排列
LinkedList<Integer> premute = new LinkedList<>();
for(int i=1;i<=n;i++){
premute.add(i);
}
int fac [] = new int [n];
fac[0] =1;
//获取阶乘数
for(int i=1;i<n;i++){
fac[i] = fac[i-1]*i;
}
//因为排列从0开始算起
k = k-1;
StringBuffer sb = new StringBuffer();
for(int i =n-1;i>=0;i--){
int index = k/fac[i];
k = k - index*fac[i];
sb.append(premute.get(index));
premute.remove(index);
}
return sb.toString();
}
}
回溯
Leetcode 46 全排列
class Solution {
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {
int len = nums.length;
//int count = fac(len);
boolean marked[] = new boolean[len];
List<Integer> list = new ArrayList<>();
dfs(nums,marked,0,list,len);
return res;
}
public void dfs(int nums[],boolean marked[],int depth,List<Integer>list,int len){
if(depth == len) {
res.add(new ArrayList<>(list));
return;
}
for(int i=0;i<len;i++){
if(!marked[i]) {
list.add(nums[i]);
marked[i] = true;
dfs(nums,marked,depth+1,list,len);
//回溯
marked[i] = false;
list.remove(list.size()-1);
}
}
}
}
Leetcode 47 全排列2：
class Solution {
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
//记录一组完整的排列
List<Integer> path = new ArrayList<>();
Arrays.sort(nums);
int len = nums.length;
boolean marked[] = new boolean[len];
dfs(nums,marked,path,0,len);
return res;
}
private void dfs(int nums[],boolean marked[],List<Integer>path,int depth,int len){
if(depth == len) {
res.add(new ArrayList<>(path));
}
for(int i=0;i<len;i++){
if(!marked[i]){
if(i>0&&marked[i-1] && nums[i] == nums[i-1]) continue;
else{
path.add(nums[i]);
marked[i] = true;
dfs(nums,marked,path,depth+1,len);
marked[i] =false;
path.remove(path.size()-1);
}
}
}
}
}
Leetcode 542 01矩阵
//BFS
// class Solution {
// public int[][] updateMatrix(int[][] matrix) {
// //思路从所有0元素开始进行广度搜索优先遍历，这样可以不用判断离哪个0最近，因为先
// //遍历到的就是最短距离
// int m = matrix.length;//行
// int n = matrix[0].length;//列
// //首先把0元素加入列
// LinkedList<int[]> queue = new LinkedList<>();
// for(int i=0;i<m;i++){
// for(int j=0;j<n;j++){
// if(matrix[i][j] == 0){
// queue.offer(new int[] {i,j});
// }else{
// matrix[i][j] = -1;
// }
// }
// }
// //把0值加入队列 同时 把非零值 -1 用于判断是否遍历过
// //四个方向 ：上 下 左 右
// int dir[][] = {{1,0},{-1,0},{0,-1},{0,1}};
// while(!queue.isEmpty()){
// int curPos[] = queue.poll();
// for(int i=0;i<4;i++){
// int [] nextPos = new int [2];
// nextPos[0] = curPos[0]+dir[i][0];
// nextPos[1] = curPos[1]+dir[i][1];
// if(nextPos[0]<m && nextPos[0]>=0 && nextPos[1]>=0 && nextPos[1]<n && matrix[nextPos[0]][nextPos[1]] == -1){
// matrix[nextPos[0]][nextPos[1]] = matrix[curPos[0]][curPos[1]]+1;
// queue.offer(nextPos);
// }
// }
// }
// return matrix;
// }
// }
// 动态规划 dp[i][j] = min{四个方向的最小值} +1；
class Solution{
public int[][] updateMatrix(int[][] matrix) {
int m = matrix.length;//行
int n = matrix[0].length;
int dp [][] = new int [m][n] ;
//初始化
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
dp[i][j] = (matrix[i][j] ==0)? 0 : 10000;
}
}
// 从左上角开始
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i - 1 >= 0) {
dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + 1);
}
if (j - 1 >= 0) {
dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + 1);
}
}
}
// 从右下角开始
for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
if (i + 1 < m) {
dp[i][j] = Math.min(dp[i][j], dp[i + 1][j] + 1);
}
if (j + 1 < n) {
dp[i][j] = Math.min(dp[i][j], dp[i][j + 1] + 1);
}
}
}
return dp;
}
}
若有收获，就点个赞吧
0 人点赞
