解题--＞在线OJ(十八）
1.把数组排成最小的数(offer45)
class Solution {
public static String minNumber(int[] nums) {
String[] arr=new String[nums.length];
for(int i=0;i<nums.length;i++){
arr[i]=nums[i]+"";
}
Arrays.sort(arr,(o1,o2)->(o1+o2).compareTo(o2+o1));
StringBuilder stringBuilder=new StringBuilder();
for(String s:arr){
stringBuilder.append(s);
}
return stringBuilder.toString();
}
}
2.把数字翻译成字符串
动态规划解决此问题
class Solution {
public static int translateNum(int num) {
String s=num+"";
char[] arr=s.toCharArray();
int[] dp=new int[arr.length];
dp[0]=1;
int i=1;
for(;i<arr.length;i++){
dp[i]=dp[i-1];
int ret=10*(arr[i-1]-'0')+(arr[i]-'0');
if(ret>9 && ret<=25){
if(i==1){
dp[i]=dp[i]+1;
}else{
dp[i]=dp[i]+dp[i-2];
}
}
}
return dp[i-1];
}
}
3.礼物的最大价值
动态规划解决此问题
class Solution {
public static int maxValue(int[][] grid) {
int[][] dp=new int[grid.length][grid[0].length];
for(int i=0;i<grid.length;i++){
for(int j=0;j<grid[0].length;j++){
if(i==0 && j==0){
dp[i][j]=grid[0][0];
}else if(i==0 && j!=0){
dp[i][j]=grid[i][j]+dp[i][j-1];
}else if(j==0 && i!=0){
dp[i][j]=grid[i][j]+dp[i-1][j];
}else{
dp[i][j]=grid[i][j]+Math.max(dp[i-1][j],dp[i][j-1]);
}
}
}
return dp[grid.length-1][grid[0].length-1];
}
}
4.把字符串转换成整数
class Solution {
public static int strToInt(String str) {
List<Character> list=new ArrayList<>();
//如果字符串为空，直接返回 0
if(str.length()==0){
return 0;
}
//去除字符串str前面的空格
str=str.trim();
//去除空格之后，再次判断 此时的字符串是否为空，如果为空，返回 0
if(str==""){
return 0;
}
//将字符串转成字符数组
char[] temp=str.toCharArray();
//如果此时字符数组中，只有 + 或者 -，直接返回 0
if(temp.length==1 && (temp[0]=='+'||temp[0]=='-')){
return 0;
}
StringBuilder stringBuilder=new StringBuilder();
//当字符数组长度大于1的时候，判断字符数组第一位是否是 +/-/数字。 如果不是这三项，直接返回0即可
if(temp[0]=='+' ||temp[0]=='-' || (temp[0]>='0'&&temp[0]<='9')){
list.add(temp[0]);
stringBuilder.append(temp[0]);
}else{
return 0;
}
//遍历字符数组，所遍历到的字符必须得是数字，如果不是数字，就结束for循环
for(int i=1;i<temp.length;i++){
if(temp[i]>='0'&&temp[i]<='9'){
list.add(temp[i]);
stringBuilder.append(temp[i]);
}else {
break;
}
//当stringBuilder增加足够大的时候，超过了Integer的最大值或者是最小值的时候，就直接返回Integer的最大值或者最小值
Long result=Long.parseLong(stringBuilder.toString());
if(result<=Integer.MIN_VALUE){
return Integer.MIN_VALUE;
}else if(result>=Integer.MAX_VALUE){
return Integer.MAX_VALUE;
}
}
//这里是为了判断 " +-21"这种情况的，这种，list和stringBuilder中都只添加了 +,这种情况无法转换成数字，直接返回0即可。
if(list.size()==1 && (list.get(0)=='+'|| list.get(0)=='-')){
return 0;
}
return Integer.parseInt(stringBuilder.toString());
}
}
5.回文子字符串的个数
class Solution {
public static int countSubstrings(String s) {
//如果字符串长度为1，直接返回1 即可
if(s.length()==1){
return 1;
}
//定义result，从题目中可以得知，每一个单独的字符都是回文字符串
int result=s.length();
//开始遍历字符串s
for(int i=0;i<s.length();i++){
for (int j=i+1;j<s.length();j++){
//开始截取字符串，从i下标开始截取，截至到j+1下标
String temp=s.substring(i,j+1);
StringBuilder stringBuilder=new StringBuilder(temp);
//如果截取的字符串 等于 字符串的逆置，result++即可
if(temp.equals(stringBuilder.reverse().toString())){
result++;
}
}
}
return result;
}
}
6.和大于等于target的最短子数组
使用双层for循环来解决此题
class Solution {
public static int minSubArrayLen(int target, int[] nums) {
//ret记录:子数组之和 大于等于 target 的子数组最短长度
int ret=Integer.MAX_VALUE;
for(int i=0;i<nums.length;i++){
int temp=target;
//用list来记录满足的条件的数据
List<Integer> list=new ArrayList<>();
for(int j=i;j<nums.length;j++){
//如果temp>=0,就证明需要拿temp去减数组元素
//否则，直接退出当前for循环
if(temp>=0){
temp-=nums[j];
list.add(nums[j]);
}else{
break;
}
//验证temp是否小于等于0，如果满足条件，更新ret的值
if(temp<=0){
ret=Math.min(ret,list.size());
}
}
}
//如果没有子数组之和 大于等于 target ，此时ret的值还是初始化的值，此时，只需要返回0 即可
if(ret==Integer.MAX_VALUE){
return 0;
}
return ret;
}
}
7.字符串中的变位词
class Solution {
public static boolean checkInclusion(String s1, String s2) {
//如果第一个字符串长度大于第二个字符串长度，直接返回false
if(s1.length()>s2.length()){
return false;
}
//将字符串1转化成字符数组，并且将其排序
char[] ss1=s1.toCharArray();
Arrays.sort(ss1);
//排序之后，将字符数组转成字符串
String a=new String(ss1);
for(int i=0;i<(s2.length()-s1.length()+1);i++){
//在字符串2 中截取于字符串1相等的长度
String s=s2.substring(i,i+s1.length());
//将其转化为字符数组，排序
char[] temp=s.toCharArray();
Arrays.sort(temp);
String ret=new String(temp);
//如果两个字符串相等，就直接返回true
if(a.equals(ret)){
return true;
}
}
//遍历完之后，如果没有返回true，返回false
return false;
}
}
8.字符串中的所有变位词
class Solution {
public static List<Integer> findAnagrams(String s, String p) {
//定义一个list用于返回
List<Integer> list=new ArrayList<>();
//将字符串转成字符数组，并且将其排序，然后再转成字符串
char[] p1=p.toCharArray();
Arrays.sort(p1);
String pp=new String(p1);
for(int i=0;i<(s.length()-p.length()+1);i++){
//从s字符串中截取与p字符串相等长度的字符串，然后将其转化成字符数组，排序，再转成字符串
String temp=s.substring(i,i+p.length());
char[] t1=temp.toCharArray();
Arrays.sort(t1);
String tt=new String(t1);
//比较两个字符串是否相等，相等，就在list当中加入其下标
if(pp.equals(tt)){
list.add(i);
}
}
//返回list
return list;
}
}
9.乘积小于k的子数组
class Solution {
public static int numSubarrayProductLessThanK(int[] nums, int k) {
//定义左右指针
int ret=1;
int left=0;
int count=0;
for(int right=0;right<nums.length;right++){
//累计乘积
ret=ret*nums[right];
//如果累计乘积大于k的话，就把左指针往右边挪（ret除等），直到累计乘积小于k的时候，出循环
while(left<=right && ret>=k){
ret/=nums[left++];
}
//如果左边指针大于右边指针，直接返回0，如果左边指针小于等于右边指针，count+=right-left+1;
count+=right>=left?(right-left+1):0;
}
return count;
}
}
10.和为k的子数组
解题思路:
链接: bilibili LeetCode力扣
class Solution {
public static int subarraySum(int[] nums, int k) {
HashMap<Integer,Integer> map=new HashMap<>();
map.put(0,1);
int pre=0;
int count=0;
for(int i=0;i<nums.length;i++){
pre+=nums[i];
if(map.containsKey(pre-k)){
count+=map.get(pre-k);
}
map.put(pre,map.getOrDefault(pre,0)+1);
}
return count;
}
}