Leetcode算法题

2022-07-26 Leetcode算法题 0 评论字数统计: 3.8k(字) 阅读时长: 16(分)

一：力扣第14题编写一个函数来查找字符串数组中的最长公共前缀
官方解法：
##方法一：横向扫描

如果在尚未遍历完所有的字符串时，最长公共前缀已经是空串，则最长公共前缀一定是空串，因此不需要继续遍历剩下的字符串，直接返回空串即可。

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        String prefix = strs[0];
        int count = strs.length;
        for (int i = 1; i < count; i++) {
            prefix = longestCommonPrefix(prefix, strs[i]);
            if (prefix.length() == 0) {
                break;
            }
        }
        return prefix;
    }

    public String longestCommonPrefix(String str1, String str2) {
        int length = Math.min(str1.length(), str2.length());
        int index = 0;
        while (index < length && str1.charAt(index) == str2.charAt(index)) {
            index++;
        }
        return str1.substring(0, index);
    }
}
复杂度分析
时间复杂度：O(mn)O(mn)，其中 mm 是字符串数组中的字符串的平均长度，nn 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。
空间复杂度：O(1)O(1)。使用的额外空间复杂度为常数。
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/longest-common-prefix/solution/zui-chang-gong-gong-qian-zhui-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

#leetcode 用户灵魂画手
思路
标签：链表
当字符串数组长度为 0 时则公共前缀为空，直接返回
令最长公共前缀 ans 的值为第一个字符串，进行初始化
遍历后面的字符串，依次将其与 ans 进行比较，两两找出公共前缀，最终结果即为最长公共前缀
如果查找过程中出现了 ans 为空的情况，则公共前缀不存在直接返回
时间复杂度：O(s)O(s)，s 为所有字符串的长度之和
代码

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs.length == 0) 
            return "";
        String ans = strs[0];
        for(int i =1;i<strs.length;i++) {
            int j=0;
            for(;j<ans.length() && j < strs[i].length();j++) {
                if(ans.charAt(j) != strs[i].charAt(j))
                    break;
            }
            ans = ans.substring(0, j);
            if(ans.equals(""))
                return ans;
        }
        return ans;
    }
}
作者：guanpengchn
链接：https://leetcode-cn.com/problems/longest-common-prefix/solution/hua-jie-suan-fa-14-zui-chang-gong-gong-qian-zhui-b/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

#最易理解：

class Solution {
    public String longestCommonPrefix(String[] strs) {
        String s="";
        int judge=1;
        if(strs.length==0){//数组为空直接返回""
            return s;
        }
        for(int i=0;i<strs[0].length();i++){
            char a=strs[0].charAt(i);//直接选择第一个数组元素，依次取这个字符串的字符
            
            for(int j=0;j<strs.length;j++){
                
                if(i>=strs[j].length()){//因为每个字符串长度不同，防止溢出
                    judge=0;
                    break;
                }
                
                if(a!=strs[j].charAt(i)){
                    judge=0;//只要存在不同，直接退出
                    break;
                }
                
                else{
                    if(j==strs.length-1){
                        s=s+a;
                    }
                }
                
            }
            if(judge==0){
                break;
            }
        }
    
        return s;
    }
}
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/shancx/article/details/82746264

二：未排序正整数数组中累加和为给定值的最长子数组长度
给定一个数组arr，该数组无序，每个数正数，给定一个K，求arr的所有子数组中所有元素相加和为k的最长子数组的长度。

例如：arr=[1,2,1,1,1],k=3

结果是3，[1,1,1]的长度。

思路：

首先用两个位置来标记子数组左右两头，记为left与right，开始的时候都在数组的最左边即left=right=0，过程如下：

1，开始变量left=0，right=0，代表子数组arr[left,right];

2，变量sum始终表示子数组arr[left,right]的和，开始的时候sum= arr[0],即是arr[0,0]的和；

3，变量len一直记录累加和为k的所有子数组中最大子数组的长度，开始的时候len=0;

4，根据sum与k的比较结果决定是left移动还right移动。若干sum==K，说明arr[left,right]累加和为k,如果长度大于len，更新len

package Array;

import java.util.Scanner;

/**
 * Created by wuxiaosi on 2017/9/24.
 */
public class getMaxLength {
    public static void main(String[] args){
        int k=3;
        int[] arr={1,2,1,1,1};
        System.out.println(getMaxLengthK(arr,k));
    }
    public static int getMaxLengthK(int[] arr,int k){
        if(arr==null||arr.length==0||k<=0){
            return  0;
        }
        int left=0;
        int right=0;
        int sum=arr[0];
        int len=0;
        while(right<arr.length){
            if(sum==k){
                len = Math.max(len,right-left+1);
                sum=sum-arr[left++];
            }
            else if(sum<k){
                right++;//向右移动
                if(right==arr.length){//right到数组边界长度，就break
                    break;
                }
                sum=sum+arr[right];
            }else{
                sum=sum-arr[left++];
            }
        }
        return len;

    }
}
————————————————
版权声明：本文为CSDN博主「wuxiaosi808」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/wuxiaosi808/article/details/78079574

三有两个整数数组A1，A2，设计函数求其两个数组的最大值和第二大的值
思路一：

1.获取最值需要进行比较，每一次比较都会有一个较大的值，因为该值的不确定性，通过一个变量进行临时存储。

2.让数组中的每一个元素都和这个变量中的值进行比较，如果大于变量中的值，就用该变量记录较大值。

3.当所有的元素都比较完成，那么该变量中的存储就是数组中的最大值了。

步骤：

1.定义变量，初始化为数组中的任意一个元素。

2.通过循环语句对数组进行遍历。

3.在变量过程中定义判断条件，如果遍历到的元素比变量中的元素大，就赋值给该变量。

注意：

通过定义一个功能来完成，以便提高代码的复用性。该功能结果为数组中的最大元素，未知内容为数组。

class Test
{
	public static void main(String[] args) 
	{
		int[] arr1 = {9,5,6,3,1,2,8,7};
		int max1 = getMax(arr1);
		System.out.println("max1="+max1);
		double[] arr2 = {9.0,5.0,6.0,3.0,1.0,2.0,8.0,7.0};
		double max2 = getMax(arr2);
		System.out.println("max2="+max2);
 
	}
	//获取int类型数组最大值
	public static int getMax(int[] arr)
	{
		int max = arr[0];
		for(int i=0;i<arr.length;i++)
		{
			if(arr[i]>max)
				max = arr[i];
		}
		return max;
	}
	//获取double类型数组最大值，功能相似，以重载的形式存在
	public static double getMax(double[] arr)
	{
		double max = arr[0];
		for(int i=0;i<arr.length;i++)
		{
			if(arr[i]>max)
				max = arr[i];
		}
		return max;
	}
}

思路二：

1.定义变量，初始化为数组角标0。

2.通过循环语句对数组进行遍历。

3.在变量过程中定义判断条件，如果遍历到的元素比角标所在的元素中的数值大，就将较大值的角标赋值给变量。

class Test
{
	public static void main(String[] args) 
	{
		int[] arr1 = {9,5,6,3,1,2,8,7};
		int max1 = getMax(arr1);
		System.out.println("max1="+max1);
		double[] arr2 = {9.0,5.0,6.0,3.0,1.0,2.0,8.0,7.0};
		double max2 = getMax(arr2);
		System.out.println("max2="+max2);
	}
	//获取int类型数组最大值
	public static int getMax(int[] arr)
	{
		int max = 0;
		for(int i=0;i<arr.length;i++)
		{
			if(arr[i]>arr[max])
				max = i;
		}
		return arr[max];
	}
	//获取double类型数组最大值，功能相似，以重载的形式存在
	public static double getMax(double[] arr)
	{
		double max = 0;
		for(int i=0;i<arr.length;i++)
		{
			if(arr[i]>arr[max])
				max = i;
		}
		return arr[max];
	}
}
————————————————
版权声明：本文为CSDN博主「Destiny_lt」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/ytu_lt/article/details/70160598

四翻转单词顺序列（I am a student.->student. a am I）

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串”I am a student. “，则输出”student. a am I”
方法一：双指针
算法解析：
倒序遍历字符串 ss ，记录单词左右索引边界 ii , jj ；
每确定一个单词的边界，则将其添加至单词列表 resres ；
最终，将单词列表拼接为字符串，并返回即可。
复杂度分析：
时间复杂度 O(N)O(N) ：其中 NN 为字符串 ss 的长度，线性遍历字符串。
空间复杂度 O(N)O(N) ：新建的 list(Python) 或 StringBuilder(Java) 中的字符串总长度 \leq N≤N ，占用 O(N)O(N) 大小的额外空间。
代码

class Solution {
    public String reverseWords(String s) {
        s = s.trim(); // 删除首尾空格
        int j = s.length() - 1, i = j;
        StringBuilder res = new StringBuilder();
        while(i >= 0) {
            while(i >= 0 && s.charAt(i) != ' ') i--; // 搜索首个空格
            res.append(s.substring(i + 1, j + 1) + " "); // 添加单词
            while(i >= 0 && s.charAt(i) == ' ') i--; // 跳过单词间空格
            j = i; // j 指向下个单词的尾字符
        }
        return res.toString().trim(); // 转化为字符串并返回
    }
}

方法二：分割 + 倒序
利用 “字符串分割”、“列表倒序” 的内置函数（面试时不建议使用），可简便地实现本题的字符串翻转要求
复杂度分析：
时间复杂度 O(N)O(N) ：总体为线性时间复杂度，各函数时间复杂度和参考资料链接如下。
split() 方法：为 O(N)O(N) ；
trim() 和 strip() 方法：最差情况下（当字符串全为空格时），为 O(N)O(N) ；
join() 方法：为 O(N)O(N) ；
reverse() 方法：为 O(N)O(N) ；
空间复杂度 O(N)O(N) ：单词列表 strsstrs 占用线性大小的额外空间。

class Solution {
    public String reverseWords(String s) {
        String[] strs = s.trim().split(" "); // 删除首尾空格，分割字符串
        StringBuilder res = new StringBuilder();
        for(int i = strs.length - 1; i >= 0; i--) { // 倒序遍历单词列表
            if(strs[i].equals("")) continue; // 遇到空单词则跳过
            res.append(strs[i] + " "); // 将单词拼接至 StringBuilder
        }
        return res.toString().trim(); // 转化为字符串，删除尾部空格，并返回
    }
}

作者：jyd
链接：https://leetcode-cn.com/problems/fan-zhuan-dan-ci-shun-xu-lcof/solution/mian-shi-ti-58-i-fan-zhuan-dan-ci-shun-xu-shuang-z/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

方法二

public class Solution {
    public String ReverseSentence(String str)
    {
        //先单个单词反转,再整体反转。I am a student.》》I ma a .tneduts 》》student. a am I
        if(str.length()==0)
            return str;

        char[]chs=str.toCharArray();

        //对单个字符数组元素进行反转
        int i=0,j=0;//定义两个指针进行遍历
        while(j<=str.length()){

            //以空格作为区分，对每个单词进行反转
            if(j==str.length()||chs[j]==' '){//j==str.length()不要忘记
                reverse(chs,i,j-1);
                i=j+1;
            }
            //如果chs[j]!=' '那么继续遍历直到找到空格
            j++;
        }

        //整体字符串反转
        reverse(chs,0,str.length()-1);

        return new String(chs);//学习

    }
    private void reverse(char[]ch,int i,int j){
        while(i<j){
            //反转交换,代码是一样的
            char temp=ch[i];
            ch[i]=ch[j];
            ch[j]=temp;
            i++;
            j--;
        }
    }
}
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/hefenglian/article/details/79932709

最牛逼的解法：JavaScript

解法：先用trim()把字符串两端空格去掉，split(‘ ‘)把字符串切割成以空格为界限的单词块，filter()过滤掉数组中的纯空格，reverse()进行数组反转，join(‘ ‘)把数组变成中间只带一个空格的字符串

    var reverseWords = function (s) {
        var str = s.trim().split(' ').filter(item => item!='').reverse().join(' ')
        console.log(str)
    };
作者：CHH_
链接：https://leetcode-cn.com/problems/fan-zhuan-dan-ci-shun-xu-lcof/solution/yi-xing-dai-ma-jie-jue-suo-you-by-chen-1wz/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

暴力求解法(百度百科)

暴力求解法, 又名直接带入法（Directly Calculating）它是已知最古老的算法之一，与"直观目测法"，"心灵感应法"并称世界三大不可思议数学计算法则， 其可追溯至3200年前，古老的埃及人便开始使用象形文字进行复杂的数学演算。它首次的文本出现是欧几里德的《几何原本》（第V卷，命题i和ii）中，而在中国则可以追溯至宋朝末年出现的沈括《梦溪笔谈》
暴力求解法的由来

在汉高祖时期有一个有趣的小故事是这样的:

“高祖年间,大将军韩信征讨突厥得胜,七月七日凯旋而归，其时举国腾。信进宫，高祖曰:’淮阴侯乃真人也，战无不功克，朕三年尝闻智勇，招为爱卿，果其然，甚好甚慰。’信曰:’大王聪明仁惠，敬贤礼士，江表英豪贤归附，臣听闻蜀地龙光射牛斗之墟，人杰多地灵，又适王举兵招马，无怪骏才星驰。’高祖对曰:’今汝方成大业，且问卿求?’信:’乃望众亲赐匹布，以二渐累。’回:’善，明日使文库之卿，方得人数。’隔日使返，帝问:”需布甚许?”曰:”臣不才，方得淮阴侯亲友八十五者，食客则七百七十六人之众，臣斗胆以树枝编排数之方得须七三万千三百二十馀一匹”帝惊道:”甚许!乃至库之空不能所期，淮阴岂谋他意?”遂隔日将信斩之，不知了了。”
暴力求解法的演算
1.例题:在地面上的同一1地点分别以速率V1、V2先后竖直像上抛出两个可视为质点的小球。第二个小球抛出后经过T时间与第一个小球相遇

设第一小球抛出后t0时间与第二小球相遇 (此时第二小球已运动T,T<t0)
因为 h1 = h2
v1t0 - 1/2g(t0)^2 = v2T -1/2gT^2
所以 T = (v2+√(v2^2-2g(v1t0 - 1/2g(t0)^2))) / g
又 T < v2/g
根据复杂计算
可得 T = (v2-√v2^2-v1^2) / g
所以 Tmax = (v2-√v2^2-v1^2) / g

本文链接： https://zkkget.github.io/posts/20220726clw0bu8fm000vtcujhcjp34l4.html

版权声明： 本博客所有文章除特别声明外，均采用 CC BY 4.0 CN协议许可协议。转载请注明出处！

赵kkjava Developer & pm

纠结体本体,同步记录日常笔记，Write the code, Change the world！

Leetcode算法题

四 翻转单词顺序列（I am a student.->student. a am I）

最牛逼的解法：JavaScript

赵kkjava Developer & pm

四翻转单词顺序列（I am a student.->student. a am I）