Leetcode剑指offer（六）

Leetcode剑指offer

• 41、数据流中的中位数（41、Hard）
• 42、连续子数组的最大和（42、Easy）
• 43、整数中 1 出现的次数（43、Hard）
• 44、数字序列中某一位的数字（44、Medium）
• 45、把数组排成最小的数（45、Medium）
• 46、把数字翻译成字符串（46、Medium）
• 47、礼物的最大价值（47、Medium）
• 48、最长不含重复字符的子字符串（48、Medium）
• 49、丑数（49、Medium）
• 50、第一个只出现一次的字符（50、Easy）

41、数据流中的中位数（41、Hard）

1）题目要求

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

例如，

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。
示例 1：

输入：
[“MedianFinder”,“addNum”,“addNum”,“findMedian”,“addNum”,“findMedian”]
[[],[1],[2],[],[3],[]]
输出：[null,null,null,1.50000,null,2.00000]
示例 2：

输入：
[“MedianFinder”,“addNum”,“findMedian”,“addNum”,“findMedian”]
[[],[2],[],[3],[]]
输出：[null,null,2.00000,null,2.50000]

限制：

最多会对 addNum、findMedian 进行 50000 次调用。

2）我的解法

1、插入排序

class MedianFinder {

    /** initialize your data structure here. */
    int size=0;
    List<Double> list;
    public MedianFinder() {
        list=new ArrayList<Double>();
    }
    
    public void addNum(int num) {//插入排序
    	//之前的数组已经有序的情况下，时间复杂度为O(n)
    	//查找O(n),插入O(n)
        int j=0;
        for(Double i:list){
            if(i<num)j++;
            else break;
        }
        list.add(j,(double)num);
    }
    
    public double findMedian() {//时间复杂度为O(1)
        if(list.size()%2==1)return list.get(list.size()/2);
        else return (list.get(list.size()/2)+list.get(list.size()/2-1))/2;
    }
}

3）其他解法

1、堆

class MedianFinder {
    Queue<Integer> A, B;
    public MedianFinder() {
        A = new PriorityQueue<>(); // 小顶堆，保存较大的一半
        B = new PriorityQueue<>((x, y) -> (y - x)); // 大顶堆，保存较小的一半
    }
    public void addNum(int num) {
        if(A.size() != B.size()) {
            A.add(num);
            B.add(A.poll());
        } else {
            B.add(num);
            A.add(B.poll());
        }
    }
    public double findMedian() {
        return A.size() != B.size() ? A.peek() : (A.peek() + B.peek()) / 2.0;
    }
}

作者：jyd
链接：link
来源：力扣（LeetCode）

2、插入排序优化：查找位置改为二分查找，

class MedianFinder {
    vector<int> store; // resize-able container

public:
    // Adds a number into the data structure.
    void addNum(int num)
    {
        if (store.empty())
            store.push_back(num);
        else
            store.insert(lower_bound(store.begin(), store.end(), num), num);     // binary search and insertion combined
    }

    // Returns the median of current data stream
    double findMedian()
    {
        int n = store.size();
        return n & 1 ? store[n / 2] : (store[n / 2 - 1] + store[n / 2]) * 0.5;
    }
};

作者：z1m
链接： link
来源：力扣（LeetCode）

4）自己的优化代码

1、堆

class MedianFinder {

    /** initialize your data structure here. */
    int size=0;
    Queue<Integer> small,big;
    public MedianFinder() {
        small=new PriorityQueue<Integer>((o1,o2)->o2-o1);//较小，大顶堆
        big=new PriorityQueue<Integer>();//较大的一半，小顶堆
    }
    
    public void addNum(int num) {//插入排序
        if(small.size()==big.size()){
            small.offer(num);
            big.offer(small.poll());
        }
        else{
            big.offer(num);
            small.offer(big.poll());
        }
        size++;
    }
    
    public double findMedian() {
        if(size%2==0){
            return (double)(small.peek()+big.peek())/2;
        }
        else return (double)big.peek();
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

2、插入排序优化：二分查找，O(logn)+O(n)

二分查找目标：第一个>=num的元素x，
即x左边那个元素<num,x本身>=num

3、插入排序优化：边找边移动 O(n)

5）学到的东西

堆（多练几遍）

插入排序（二分，边找边移动）

42、连续子数组的最大和（42、Easy）

1）题目要求

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

示例1:

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

提示：

1 <= arr.length <= 10^5
-100 <= arr[i] <= 100

2）我的解法

class Solution {
    public int maxSubArray(int[] nums) {
        int max=Integer.MIN_VALUE,temp=0;
        for(int i=0;i<nums.length;i++){
            temp+=nums[i];
            if(nums[i]>temp)temp=nums[i];
            if(temp>max){max=temp;}

        }
        return max;
    }
}

3）其他解法

class Solution {
    public int maxSubArray(int[] nums) {
        int res = nums[0];
        for(int i = 1; i < nums.length; i++) {
            nums[i] += Math.max(nums[i - 1], 0);
            res = Math.max(res, nums[i]);
        }
        return res;
    }
}

作者：jyd
链接：link
来源：力扣（LeetCode）

4）自己的优化代码

class Solution {
    public int maxSubArray(int[] nums) {
        int max=nums[0];
        for(int i=1;i<nums.length;i++){
            nums[i]+=Math.max(nums[i-1],0);
            max=Math.max(max,nums[i]);
        }
        return max;
    }
}

5）学到的东西

动态规划

43、整数中 1 出现的次数（43、Hard）

1）题目要求

输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。

例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

示例 1：

输入：n = 12
输出：5
示例 2：

输入：n = 13
输出：6

限制：

1 <= n < 2^31

2）我的解法

只想到了超时的方法

class Solution {
    public int countDigitOne(int n) {
        int result=0,temp=0;
        for(int i=1;i<=n;i++){
            temp=i;
            while(temp>0){
                if(temp%10==1)result++;
                temp/=10;
            }
        }
        return result;
    }
}

感觉就是找规律。。太难找了

3）其他解法

class Solution {
    public int countDigitOne(int n) {
        int digit = 1, res = 0;
        int high = n / 10, cur = n % 10, low = 0;
        while(high != 0 || cur != 0) {
            if(cur == 0) res += high * digit;
            else if(cur == 1) res += high * digit + low + 1;
            else res += (high + 1) * digit;
            low += cur * digit;
            cur = high % 10;
            high /= 10;
            digit *= 10;
        }
        return res;
    }
}

2、

class Solution {
    public int countDigitOne(int n) {
        return f(n);
    }
    private int f(int n ) {
        if (n <= 0)
            return 0;
        String s = String.valueOf(n);
        int high = s.charAt(0) - '0';
        int pow = (int) Math.pow(10, s.length()-1);
        int last = n - high*pow;
        if (high == 1) {
            return f(pow-1) + last + 1 + f(last);
        } else {
            return pow + high*f(pow-1) + f(last);
        }
    }
}

作者：xujunyi
链接：link
来源：力扣（LeetCode）

4）自己的优化代码

class Solution {
    public int countDigitOne(int n) {
        int digit=1,res=0;
        int high=n/10,cur=n%10,low=0;
        while(n>0){
            if(cur==0)res+=high*digit;
            else if(cur==1)res+=high*digit+low+1;
            else res+=(high+1)*digit;
            low+=cur*digit;
            digit*=10;
            n/=10;
            high=n/10;cur=n%10;
        }
        return res;
    }
}

5）学到的东西

找规律

44、数字序列中某一位的数字（44、Medium）

1）题目要求

数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。

请写一个函数，求任意第n位对应的数字。

示例 1：

输入：n = 3
输出：3
示例 2：

输入：n = 11
输出：0

限制：

0 <= n < 2^31

2）我的解法

不会。。。找规律的题好让人绝望啊

3）其他解法

0 占第0位
1～9 共9x1 = 9个数字 占位9x1 = 9 位
10～99 共9x10 = 90个数字 占位90x2 = 180 位
100～999 共9x100 = 900个数字 占位900x3 = 2700 位
…

规律是不是很好理解啦，算法的逻辑就是：我们依次算一下占位数字，并不断地累加得到当前的总占位数，并判断和输入n的关系，总占位数小于n的话说明，第n位不在目前的范围內，继续累加；否则，说明在范围，然后找到相应数字返回。

举个例子秒懂：

假设输入n为14，我们想找到第14位：

(1)此时设置当前位置为0的位置 temp=0
(2)占1位的数字有9个: num=9,（1～9,除了0因为temp已设为0了）
(3)占1位 base=1
(4)我们判断一下，当占1位的数字都走完了，目前一共占到了多少位： temp + num x base = 0 + 9x1 = 9，说明占1位的数字走完后，当前占到了第9位。(更新temp=temp + num x base = 9）
(5)和输入的值比较下，9 < 14,说明我们想找的第14位不在当前占1位的数字中。
(6)那就有可能在占2位的数字中，所以这一轮我们看看占2位的数字（10～99）：
每个数字占位 base = base + 1 = 2
有多少个数字 num = num x 10 = 90
再回到第（4)步，算一下当占2位的数字也都走完了，目前一共占到了多少位
temp + num x base = 9 + 90 x 2 = 189
说明当占2位的数字走完后，当前占到了第189位
再回到第5步，发现 189 > 14,说明我们想找到的数字就在10～99之间
此时，循环终止…因为没必要再往下算占3位的情况了

(7)我们知道第14位就在10～99之间的话就很好办了：
前一轮我们知道占1位的数字走完后，占到了第9位，那我们想找的第14位的值也就是9之后的第5位：
14 - 9 = 5位
占两位的数字中（10～99），第一个起始数字是10，（10 = 10的1次方，也就10的(base-1)次方）
由于10～99这个范围内的数字，都是占base=2位，
所以 5/2 = 2
10 + 2 = 12，第14位就在数字12里
5%2 = 1，说明第14位就是数字12中的第一个位置值，如果把12当成字符串，那就是下标为0的值
“12”.charAt(1-1) = 1
最终我们找到了这个1

验证下0123456789101112…第14位确实是1

联系上面的思路，带到下面的代码，很好理解啦。

注意大数越界问题，所以这里用long型

class Solution {
    public int findNthDigit(int n) {
       if(n<0) return 0;
	   else if(n>=0 && n<=9) return n; 
	   else {
		   long m = n;
		   long temp = 0;
		   long base = 1;
		   long num = 9;
		   char res = '0';
		   while((temp+base*num) < m) {
			   temp += base*num;
			   base += 1;
			   num *= 10;
		   }
		   long a = (m-temp)/base;
		   long b = (m-temp)%base;
		   if(b!=0) {
			   long c = (long) (Math.pow(10, base-1) + a);
			   res = String.valueOf(c).charAt((int)b-1);
		   }else {
			   long c = (long) (Math.pow(10, base-1) + a - 1);
			   res = String.valueOf(c).charAt((int)base-1);
		   }
		   return Integer.parseInt(String.valueOf(res));
	   }

    }
}

作者：zhuguangyu
链接：link
来源：力扣（LeetCode）

4）自己的优化代码

class Solution {
    public int findNthDigit(int n) {
        if(n>=0&&n<=9)return n;
        long base=1,addNum=9,preNum=0,num=9;//preNum即下限，num即上限
        while(num<n){
            base++;
            addNum*=10;
            preNum=num;
            num+=base*addNum;
        }
        long pianyi=n-preNum;
        long index=pianyi/base;//第几个数
        long wei=pianyi%base;//第几位

        if(wei==0){wei=base;index--;}

        long number=(long)Math.pow(10,base-1)+index;//数字

        String numberString=number+"";

        int result=numberString.charAt((int)wei-1)-'0';
        return result;
    }
}

5）学到的东西

找规律

有可能越界的地方用Long

45、把数组排成最小的数（45、Medium）

1）题目要求

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

示例 1:

输入: [10,2]
输出: “102”
示例 2:

输入: [3,30,34,5,9]
输出: “3033459”

提示:

0 < nums.length <= 100
说明:

输出结果可能非常大，所以你需要返回一个字符串而不是整数
拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0

2）我的解法

感觉我想复杂了。。。。用了桶排序+堆排序

class Solution {
    public String minNumber(int[] nums) {
        StringBuilder sb=new StringBuilder();
        List<PriorityQueue<Integer>> number=new ArrayList<>();
        for(int i=0;i<10;i++)number.add(new PriorityQueue<Integer>(new Comparator<Integer>(){

            public int compare(Integer o1,Integer o2){
                int a=o1,b=o2;
                int len1=(a+"").length(),len2=(b+"").length();
                if(len1==len2)return a-b;
                else {
                    return Integer.parseInt(a+""+b)-Integer.parseInt(b+""+a);
                }
            }
        }));
        int high=0;//最高位
        for(int i=0;i<nums.length;i++){
            high=(nums[i]+"").charAt(0)-'0';
            number.get(high).offer(nums[i]);
        }
        PriorityQueue<Integer> temp=null;
        for(int i=0;i<10;i++){
            temp=number.get(i);
            if(temp.size()==0)continue;
            while(!temp.isEmpty())sb.append(""+temp.poll());
        }
        return sb.toString();

    }
}

3）其他解法

1、内置

class Solution {
    public String minNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for(int i = 0; i < nums.length; i++) 
            strs[i] = String.valueOf(nums[i]);
        Arrays.sort(strs, (x, y) -> (x + y).compareTo(y + x));
        StringBuilder res = new StringBuilder();
        for(String s : strs)
            res.append(s);
        return res.toString();
    }
}

2、自己写

class Solution {
    public String minNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for(int i = 0; i < nums.length; i++)
            strs[i] = String.valueOf(nums[i]);
        fastSort(strs, 0, strs.length - 1);
        StringBuilder res = new StringBuilder();
        for(String s : strs)
            res.append(s);
        return res.toString();
    }
    void fastSort(String[] strs, int l, int r) {
        if(l >= r) return;
        int i = l, j = r;
        String tmp = strs[i];
        while(i < j) {
            while((strs[j] + strs[l]).compareTo(strs[l] + strs[j]) >= 0 && i < j) j--;
            while((strs[i] + strs[l]).compareTo(strs[l] + strs[i]) <= 0 && i < j) i++;
            tmp = strs[i];
            strs[i] = strs[j];
            strs[j] = tmp;
        }
        strs[i] = strs[l];
        strs[l] = tmp;
        fastSort(strs, l, i - 1);
        fastSort(strs, i + 1, r);
    }
}

作者：jyd
链接：link
来源：力扣（LeetCode）

4）自己的优化代码

1、

class Solution {
    public String minNumber(int[] nums) {
        StringBuilder sb=new StringBuilder();
        String[] Nums=new String[nums.length];
        for(int i=0;i<nums.length;i++)Nums[i]=nums[i]+"";
        Arrays.sort(Nums,(o1,o2)->(o1+o2).compareTo(o2+o1));
        for(int i=0;i<Nums.length;i++)sb.append(Nums[i]);
        return sb.toString();

    }
}

2、用String.valueOf()可以大幅提升效率
这是因为每个+号底层都会生成一个StringBuilder对象，

class Solution {
    public String minNumber(int[] nums) {
        StringBuilder sb=new StringBuilder();
        String[] Nums=new String[nums.length];
        for(int i=0;i<nums.length;i++)Nums[i]=String.valueOf(nums[i]);

        Arrays.sort(Nums,(o1,o2)->(o1+o2).compareTo(o2+o1));
        for(int i=0;i<Nums.length;i++)sb.append(Nums[i]);
        return sb.toString();

    }
}

3、手写快排

class Solution {
    public String minNumber(int[] nums) {
        StringBuilder sb=new StringBuilder();
        String[] Nums=new String[nums.length];
        for(int i=0;i<nums.length;i++)Nums[i]=String.valueOf(nums[i]);
        
        quickSort(Nums,0,Nums.length-1);
        
        for(int i=0;i<Nums.length;i++)sb.append(Nums[i]);
        return sb.toString();

    }
    public void quickSort(String[] Nums,int start,int end){
        int i=start,j=end;
        if(start>end)return;

        String X=Nums[start];


        while(i<j){
            while(i<j&&(Nums[j]+X).compareTo(X+Nums[j])>=0)j--;
            if(i<j)Nums[i++]=Nums[j];

            while(i<j&&(Nums[i]+X).compareTo(X+Nums[i])<=0)i++;
            if(i<j)Nums[j--]=Nums[i];
        }
        Nums[i]=X;

        quickSort(Nums,start,i-1);
        quickSort(Nums,i+1,end);
    }
}

4、堆排序

class Solution {
    public String minNumber(int[] nums) {
        StringBuilder sb=new StringBuilder();
        PriorityQueue<Integer> pq=new PriorityQueue<>((o1,o2)->(o1.toString()+o2.toString()).compareTo(o2.toString()+o1.toString()));


        for(int i=0;i<nums.length;i++)pq.offer(nums[i]);
        int high=0;//最高位

        while(!pq.isEmpty())sb.append(pq.poll());

        return sb.toString();

    }
}

5）学到的东西

用String.valueOf()替代 x+"";
因为使用加号时，每个+号底层都会生成一个StringBuilder对象

快速排序

46、把数字翻译成字符串（46、Medium）

1）题目要求

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

示例 1:

输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", “bwfi”, “bczi”, “mcfi"和"mzi”

提示：

0 <= num < 231

2）我的解法

class Solution {
    public int translateNum(int num) {
        char[] arr=String.valueOf(num).toCharArray();
        ArrayList[] dp=new ArrayList[arr.length];
        dp[0]=new ArrayList<Integer>();
        dp[0].add(arr[0]-'0');
        for(int i=1;i<arr.length;i++){
            dp[i]=new ArrayList<Integer>();
            for(int j=0;j<dp[i-1].size();j++){
                int number= arr[i]-'0'+(int)dp[i-1].get(j)*10;
                dp[i].add(arr[i]-'0');
                if((int)dp[i-1].get(j)!=0&&number<26&&number>=0){
                    dp[i].add(number);
                }
            }
            
            
        }
        return dp[arr.length-1].size();
    }
}

3）其他解法

1、空间优化的动态规划

class Solution {
    public int translateNum(int num) {
        String s = String.valueOf(num);
        int a = 1, b = 1;
        for(int i = 2; i <= s.length(); i++) {
            String tmp = s.substring(i - 2, i);
            int c = tmp.compareTo("10") >= 0 && tmp.compareTo("25") <= 0 ? a + b : a;
            b = a;
            a = c;
        }
        return a;
    }
}

逆序

class Solution {
    public int translateNum(int num) {
        String s = String.valueOf(num);
        int a = 1, b = 1;
        for(int i = s.length() - 2; i > -1; i--) {
            String tmp = s.substring(i, i + 2);
            int c = tmp.compareTo("10") >= 0 && tmp.compareTo("25") <= 0 ? a + b : a;
            b = a;
            a = c;
        }
        return a;
    }
}

2、再次优化的动态规划

class Solution {
    public int translateNum(int num) {
        int a = 1, b = 1, x, y = num % 10;
        while(num != 0) {
            num /= 10;
            x = num % 10;
            int tmp = 10 * x + y;
            int c = (tmp >= 10 && tmp <= 25) ? a + b : a;
            b = a;
            a = c;
            y = x;
        }
        return a;
    }
}

作者：jyd
链接： link
来源：力扣（LeetCode）

4）自己的优化代码

1、

class Solution {
    public int translateNum(int num) {
        char[] arr=String.valueOf(num).toCharArray();
        int[] dp=new int[arr.length+1];
        dp[0]=1;
        dp[1]=1;
        for(int i=2;i<arr.length+1;i++){
            int number=(arr[i-2]-'0')*10+arr[i-1]-'0';
            dp[i]=(arr[i-2]-'0'!=0&&number>=0&&number<26)?dp[i-1]+dp[i-2]:dp[i-1];
        }
        return dp[arr.length];
    }
}

2、空间优化

class Solution {
    public int translateNum(int num) {
        char[] arr=String.valueOf(num).toCharArray();
        
        int a=1, b=1,result=1,number=0;
        for(int i=2;i<arr.length+1;i++){
            number=(arr[i-2]-'0')*10+arr[i-1]-'0';
            result=(arr[i-2]-'0'!=0&&number>=0&&number<26)?a+b:b;
            a=b;
            b=result;
        }
        return result;
    }
}

3、

class Solution {
    public int translateNum(int num) {
        char[] arr=String.valueOf(num).toCharArray();
        
        int a=1, b=1,result=1,number=0;
        for(int i=arr.length-2;i>=0;i--){
            number=(arr[i]-'0')*10+arr[i+1]-'0';
            result=(arr[i]-'0'!=0&&number>=0&&number<26)?a+b:b;
            a=b;
            b=result;
        }
        return result;
    }
}

4、

class Solution {
    public int translateNum(int num) {
        
        int a=1, b=1,result=1,number=0;
        
        int cur=0,next=0;//当前位，后一位
        while(num>0){
            cur=(num/10)%10;next=num%10;
            number=cur*10+next;
            result=(cur!=0&&number>=0&&number<26)?a+b:b;
            a=b;
            b=result;
            num/=10;
        }
        return result;
    }
}

5）学到的东西

动态规划

通过找规律找出状态转移方程

47、礼物的最大价值（47、Medium）

1）题目要求

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

示例 1:

输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物

提示：

0 < grid.length <= 200
0 < grid[0].length <= 200

2）我的解法

class Solution {
    public int maxValue(int[][] grid) {
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(i==0&&j==0)continue;
                else if(i==0||j==0)grid[i][j]+=(i==0)?grid[i][j-1]:grid[i-1][j];
                else grid[i][j]+=Math.max(grid[i-1][j],grid[i][j-1]);
            }
        }
        return grid[grid.length-1][grid[0].length-1];
    }
}

3）其他解法

1、

class Solution {
    public int maxValue(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(i == 0 && j == 0) continue;
                if(i == 0) grid[i][j] += grid[i][j - 1] ;
                else if(j == 0) grid[i][j] += grid[i - 1][j];
                else grid[i][j] += Math.max(grid[i][j - 1], grid[i - 1][j]);
            }
        }
        return grid[m - 1][n - 1];
    }
}

2、优化

以上代码逻辑清晰，和转移方程直接对应，但仍可提升效率：当 gridgrid 矩阵很大时， i = 0 或 j = 0的情况仅占极少数，相当循环每轮都冗余了一次判断。因此，可先初始化矩阵第一行和第一列，再开始遍历递推。

class Solution {
    public int maxValue(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        for(int j = 1; j < n; j++) // 初始化第一行
            grid[0][j] += grid[0][j - 1];
        for(int i = 1; i < m; i++) // 初始化第一列
            grid[i][0] += grid[i - 1][0];
        for(int i = 1; i < m; i++)
            for(int j = 1; j < n; j++) 
                grid[i][j] += Math.max(grid[i][j - 1], grid[i - 1][j]);
        return grid[m - 1][n - 1];
    }
}

作者：jyd
链接：link
来源：力扣（LeetCode）

4）自己的优化代码

class Solution {
    public int maxValue(int[][] grid) {
        for(int i=1;i<grid[0].length;i++){
            grid[0][i]+=grid[0][i-1];
        }

        for(int i=1;i<grid.length;i++){
            grid[i][0]+=grid[i-1][0];
        }

        for(int i=1;i<grid.length;i++){
            for(int j=1;j<grid[0].length;j++){
                grid[i][j]+=Math.max(grid[i-1][j],grid[i][j-1]);
            }
        }
        return grid[grid.length-1][grid[0].length-1];
    }
}

5）学到的东西

动态规划

48、最长不含重复字符的子字符串（48、Medium）

1）题目要求

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

示例 1:

输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:

输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:

输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。

提示：

s.length <= 40000

2）我的解法

1、

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character,Integer> map=new HashMap<>();
        int max=0,temp=0;
        char c='0';
        for(int i=0;i<s.length();i++){
            c=s.charAt(i);
            if(map.containsKey(c)){
                temp=i-map.get(c)-1;
                int start=map.get(c)+1;
                map.clear();
                for(int j=start;j<i;j++)map.put(s.charAt(j),j);
            }
            map.put(c,i);
            temp++;
            max=Math.max(max,temp);
        }
        return max;
    }
}

2、优化

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character,Integer> map=new HashMap<>();
        int max=0,temp=0,start=0;
        char c='0';
        for(int i=0;i<s.length();i++){
            c=s.charAt(i);
            if(map.containsKey(c)&&map.get(c)>=start){
                temp=i-map.get(c)-1;
                start=map.get(c)+1;
                map.remove(c);
            }
            map.put(c,i);
            temp++;
            max=Math.max(max,temp);
        }
        return max;
    }
}

3）其他解法

1、

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> dic = new HashMap<>();
        int res = 0, tmp = 0;
        for(int j = 0; j < s.length(); j++) {
            int i = dic.getOrDefault(s.charAt(j), -1); // 获取索引 i
            dic.put(s.charAt(j), j); // 更新哈希表
            tmp = tmp < j - i ? tmp + 1 : j - i; // dp[j - 1] -> dp[j]
            res = Math.max(res, tmp); // max(dp[j - 1], dp[j])
        }
        return res;
    }
}

2、

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> dic = new HashMap<>();
        int i = -1, res = 0;
        for(int j = 0; j < s.length(); j++) {
            if(dic.containsKey(s.charAt(j)))
                i = Math.max(i, dic.get(s.charAt(j))); // 更新左指针 i
            dic.put(s.charAt(j), j); // 哈希表记录
            res = Math.max(res, j - i); // 更新结果
        }
        return res;
    }
}

作者：jyd
链接：link
来源：力扣（LeetCode）

评论区：

 public int lengthOfLongestSubstring(String s) {
        //if(s==null) return 0;这句话可以不加，s.length()长度为0时，不进入下面的循环，会直接返回max=0;
        //划定当前窗口的坐标为(start,i],左开右闭,所以start的初始值为-1，而非0。
        int max = 0,start =-1;
        //使用哈希表map统计各字符最后一次出现的索引位置
        HashMap<Character,Integer> map = new HashMap<>();
        for(int i=0;i<s.length();i++){
            char tmp = s.charAt(i);
            
            //当字符在map中已经存储时，需要判断其索引值index和当前窗口start的大小以确定是否需要对start进行更新:
            //当index>start时，start更新为当前的index,否则保持不变。
            //注意若index作为新的start，计算当前滑动空间的长度时也是不计入的，左开右闭，右侧s[i]会计入，这样也是防止字符的重复计入。
            if(map.containsKey(tmp)) start = Math.max(start,map.get(tmp));
            
            //如果map中不含tmp，此处是在map中新增一个键值对，否则是对原有的键值对进行更新
            map.put(tmp,i);
            
            //i-start,为当前滑动空间(start,i]的长度，若其大于max，则需要进行更新。
            max = Math.max(max,i-start);
        }
        return max;
    }

3、滑动窗口

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int left = 0, right = 0, res = 0;
        while(right < s.length()){
            char c = s.charAt(right++);
            //存在重复的字符，则移动左指针，直到滑动窗口中不含有该字符
            while(set.contains(c)){
                set.remove(s.charAt(left++));
            }
            set.add(c);
            res = Math.max(res, right-left);
        }
        return res;
    }
}

作者：eager-2
链接：link
来源：力扣（LeetCode）

4）自己的优化代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character,Integer> map=new HashMap<>();
        int max=0,start=-1;//start为-1，在只有一个字符时用
        char c='0';
        for(int i=0;i<s.length();i++){
            c=s.charAt(i);
            if(map.containsKey(c))start=Math.max(start,map.get(c));

            map.put(c,i);
            max=Math.max(max,i-start);
        }
        return max;
    }
}

5）学到的东西

滑动窗口，HashMap

边界值的考虑

49、丑数（49、Medium）

1）题目要求

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

示例:

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:

1 是丑数。
n 不超过1690。

2）我的解法

1、暴力（超时）

class Solution {
    public int nthUglyNumber(int n) {
        int i=1,num=0;
        Set<Integer> set=new HashSet<>();
        set.add(1);set.add(2);set.add(3);set.add(5);
        while(true){
            if(set.contains(i))num++;
            else if((i%2==0&&set.contains(i/2))||(i%3==0&&set.contains(i/3))||(i%5==0&&set.contains(i/5))){
                num++;
                set.add(i);
            }
            if(num==n)break;
            i++;
        }
        return i;
    }
}

2、动态规划

class Solution {
    public int nthUglyNumber(int n) {
        int[] dp=new int[n+1];
        int index2=1,index3=1,index5=1;
        dp[1]=1;
        int min=0;
        for(int i=2;i<=n;i++){//三指针
        //三个指针分别用来*2，*3，*5
            min=Math.min(dp[index2]*2,Math.min(dp[index3]*3,dp[index5]*5));
            if(min==dp[index2]*2){
                dp[i]=min;
                index2++;
            }
            if(min==dp[index3]*3){
                dp[i]=min;
                index3++;
            }
            if(min==dp[index5]*5){
                dp[i]=min;
                index5++;
            }
        }
        return dp[n];
    }
}

3）其他解法

class Solution {
    public int nthUglyNumber(int n) {
        int a = 0, b = 0, c = 0;
        int[] dp = new int[n];
        dp[0] = 1;
        for(int i = 1; i < n; i++) {
            int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5;
            dp[i] = Math.min(Math.min(n2, n3), n5);
            if(dp[i] == n2) a++;
            if(dp[i] == n3) b++;
            if(dp[i] == n5) c++;
        }
        return dp[n - 1];
    }
}

作者：jyd
链接：link
来源：力扣（LeetCode）

4）自己的优化代码

class Solution {
    public int nthUglyNumber(int n) {
        int[] dp=new int[n];
        int index2=0,index3=0,index5=0;
        dp[0]=1;
        int min=0;
        for(int i=1;i<n;i++){//三指针
            min=Math.min(dp[index2]*2,Math.min(dp[index3]*3,dp[index5]*5));
            if(min==dp[index2]*2){
                dp[i]=min;
                index2++;
            }
            if(min==dp[index3]*3){
                dp[i]=min;
                index3++;
            }
            if(min==dp[index5]*5){
                dp[i]=min;
                index5++;
            }
        }
        return dp[n-1];
    }
}

5）学到的东西

动态规划

50、第一个只出现一次的字符（50、Easy）

1）题目要求

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

示例:

s = “abaccdeff”
返回 “b”

s = “”
返回 " "

限制：

0 <= s 的长度 <= 50000

2）我的解法

1、两次遍历

class Solution {
    public char firstUniqChar(String s) {

        Map<Character,Integer> map=new HashMap<>();
        for(char c:s.toCharArray()){
            if(!map.containsKey(c))map.put(c,1);
            else map.put(c,map.get(c)+1);
        }
        for(char c:s.toCharArray()){
            if(map.get(c)==1)return c;
        }
        return ' ';
    }
}

3）其他解法

1、

class Solution {
    public char firstUniqChar(String s) {
        HashMap<Character, Boolean> dic = new HashMap<>();
        char[] sc = s.toCharArray();
        for(char c : sc)
            dic.put(c, !dic.containsKey(c));
        for(char c : sc)
            if(dic.get(c)) return c;
        return ' ';
    }
}

2、

class Solution {
    public char firstUniqChar(String s) {
        Map<Character, Boolean> dic = new LinkedHashMap<>();
        char[] sc = s.toCharArray();
        for(char c : sc)
            dic.put(c, !dic.containsKey(c));
        for(Map.Entry<Character, Boolean> d : dic.entrySet()){
           if(d.getValue()) return d.getKey();
        }
        return ' ';
    }
}

作者：jyd
链接：link
来源：力扣（LeetCode）

4）自己的优化代码

class Solution {
    public char firstUniqChar(String s) {

        Map<Character,Integer> map=new LinkedHashMap<>();

        char result=' ';

        for(char c:s.toCharArray()){
            if(!map.containsKey(c))map.put(c,1);
            else map.put(c,map.get(c)+1);
        }
        for(Map.Entry<Character,Integer> entry:map.entrySet()){
            if(entry.getValue()==1)return entry.getKey();
        }
        return ' ';
    }
}

5）学到的东西

有序哈希表
Map<Character,Integer> map=new LinkedHashMap<>();

Map.Entry<Character,Integer> map.entrySet() 得到所有键值对

entry.getValue()获取value entry.getKey()获取key

本文地址：https://blog.csdn.net/weixin_43674414/article/details/109177347