14~25

14- I. 剪绳子

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

1、数学方法

本题用到的结论：

① 当所有绳段长度相等时，乘积最大。② 最优的绳段长度为 33 。

证明如下：

均值不等式image-20220801224312141image-20220801224312141当且仅当n1=n2=n3=…=n n时成立

设将绳子按照 xx 长度等分为 aa 段，即 n = a x n=ax ，则乘积为 xa

观察以下公式，由于 nn 为常数，因此当image-20220801224447089image-20220801224447089取最大值时， 乘积达到最大值。

可将问题转化为求 y = x1/x 的极大值，因此对 x求导数。

image-20220801224401429image-20220801224401429

分别代入2， 3 y(2) =1.41 ,y(3)=1.44; 或者image-20220801224424098image-20220801224424098)

由此可得，尽可能将绳子以长度 3 等分为多段时，乘积最大。

image-20220801224417533image-20220801224417533

1
2
3
4
5
6
7
8
9
class Solution {
    public int cuttingRope(int n) {
        if(n<=3) return n-1;
        double b=n/3;
        if(n%3==0) return (int)Math.pow(3.0,b);
        else if(n%3==1) return  ((int)Math.pow(3.0,b-1)*4);
        return  ((int)Math.pow(3.0,b)*2);
    }
}

2、动态规划

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int cuttingRope(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, 1);
        for (int i = 3; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), dp[i - j] * j));
            }
        }
        return dp[n];
    }
}

14- II. 剪绳子 II

在上一题的基础上 扩大了数字的范围

1
2
3
4
5
6
7
8
9
class Solution {
    static int mod=1000000007;
    public int cuttingRope(int n) {
        return n<=3?n-1:(int)f(n);
    }
    public static  long f(int n){
        return n>4?(f(n-3)*3)%mod:n;
    }
}

反转指定范围内的字符数组

  • 双指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public String reverseWords(String s)
    {
        s+=" ";
        char[]ch=s.toCharArray();
        int start=0;
        for(int i=0;i<ch.length;i++){
            if(ch[i]==' ')
            {
                reverseString(ch,start,i);
                start=i+1;
            }	
        }
        return new String(ch).substring(0, ch.length-1);
    }
    public void reverseString(char[] s,int m,int n) {
        for (int left = m, right = n - 1; left < right; ++left, --right) {
            s[left]^=s[right];
            s[right]^=s[left];
            s[left]^=s[right];
        }
    }
}

15. 二进制中1的个数

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为 汉明重量).）。

提示：

请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。

在 Java 中，编译器使用 二进制补码 记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数 -3。

注意： 本题如果直接用>> :有符号右移 ，就会溢出

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int res=0;
        while(n!=0){
            if((n&1)==1)
                res++;
            n>>>=1;
        }
        return  res;
    }
}

’ >> ‘与’ >>> '的区别

  • >>运算符可以将int和long视为32位和64位无符号整数类型

  • >>>也是找到两个(大)整数的舍入平均值的安全有效方法：

    1 int mid = (low + high) >>> 1;

    如果整数high和low接近最大的机器整数，则以上内容是正确的，但

    1 int mid = (low + high) / 2;

    可能由于溢出而得到错误的结果。

    这是一个示例用法，它修复了天真的二进制搜索中的错误。

  • 区别：

    • >>> 负数高位补 0；
    • >> 负数高位补1；

在这里插入图片描述在这里插入图片描述

16. 数值的整数次方

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。

快速幂

注意

n - 2147483648
-n -2147483648
n-1 2147483647
n+1 -2147483648

原理解析：

原码 --按位取反–> 反码 --+1–> 补码

数字 原码 补码
-2147483647 1111 1111 1111 1111 1111 1111 1111 1111 1000 0000 0000 0000 0000 0000 0000 0001
-1 1000 0000 0000 0000 0000 0000 0000 0001 1111 1111 1111 1111 1111 1111 1111 1111
-2147483648 1000 0000 0000 0000 0000 0000 0000 0000 1000 0000 0000 0000 0000 0000 0000 0000

直接快速幂即可

可以看这个学习：算法学习笔记(4)：快速幂 - 知乎 (zhihu.com)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public double myPow(double x, int n) {
        //快速幂解决
        long nq=n;
        if(n<0)
        {
            nq=-nq;
            return 1/qp(x,nq);
        }else if(n==0){
             return 1.0;
        }else {
            return qp(x,nq);
        }
    }
    public static double qp(double x,long n)
    {
        double res=1.0;
        while(n!=0){
            if((n&1)==1)// 奇数
                res*=x;
            x*=x;
            n>>=1;
        }
        return res;
    }
}

17. 打印从1到最大的n位数

  • 书上的原意应该是考大树的问题， 不过实测发现leetcode并没有考这个
  1. 直接遍历
1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int[] printNumbers(int n) {
        int x=(int)(Math.pow(10,n)-1);
        int []res=new int[x];
        for(int i=1;i<=x;i++)
        {
            res[i-1]=i;
        }
        return res;
    }
}
  1. 使用BigInteger

注意最后要返回 int[ ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.math.BigInteger;

class Solution {
        public int[] printNumbers(int n) {
        int x=(int)(Math.pow(10,n)-1);
        BigInteger[]res=new BigInteger[x];
        res[0]=BigInteger.valueOf(1);
        for(int i=1;i<x;i++)
        {
            res[i]=res[i-1].add(BigInteger.valueOf(1));
        }
        int [] res2=new int[x];
        for (int i = 0; i < res2.length; i++) {
            res2[i]=res[i].intValue();
        }
        return res2;
    }
}
  1. 使用字符串

18.删除链表的节点

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

定义一个next 为 head 的指针， 用来过 需要删除的节点是第一个节点的情况， 对于别的位置，直接遍历即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
        public ListNode deleteNode(ListNode head, int val) {
            if(head.next==null) return null;
            ListNode t=new ListNode(1);
            t.next=head;
            while(t.next!=null){
                if(t.next.val==val){
                    if(t.next.val== head.val){
                        return head.next;
                    }
                    if(t.next.next!=null)
                    {
                        t.next=t.next.next;
                    }
                    else t.next=null;
                    return head;
                }
                t=t.next;
            }
            return head;
        }
}

删除链表的倒数第 N 个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

  • 双指针

定义两个指针， p1先不动，p2 先遍历 n个节点， 使得p1 与 p2 相差 N-1个节点，

然后让p1,p2一起移动， 直到p2指向链表末尾的节点， 此时p1的下一个节点就是需要删除的节点，然后

通过改变指向来删除元素即可， 如果需要删除的元素是头结点 此时会有 p1.next=head; , 直接另res=null; 然后返回p1.next.next即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head.next==null) return null;
        ListNode res=head;
        ListNode p1=new ListNode(1,head);
        ListNode p2=new ListNode(2,head);
        for(int i=0;i<n;i++){ 
// 应该让 p1 最后处于要删除的元素的前一个，然后调用next 删除,p1与p2相隔n-1个元素, 需要让p2提前走n步
            p2=p2.next;
        }
        while(p2.next!=null){
            p1=p1.next;
            p2=p2.next;
        }
        if(p1.next==head) // 判断p1 是否移动了， 如果没有移动，说明要删除的是头结点
            res=null;
        p1.next=p1.next.next;
        return res==null?p1.next:res;
    }
}

@Test

1
2
3
4
5
6
7
8
9
@Test
public void TestNull()
{
    ListNode l2 =new ListNode(10);
    ListNode l1=new ListNode(9,l2);
    ListNode res=l1;
    res=null;
    System.out.println(l1);
}
  • res与l1 虽然指向的是同一块内存，但是另res=null 之后，指向的那一块内存并不会为null;

19. 正则表达式匹配

难度困难420

请实现一个函数用来匹配包含'. '和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。

思路：
这道题主要用到思路是：滑动窗口

什么是滑动窗口？

其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！

如何移动？

我们只要把队列的左边的元素移出就行了，直到满足题目要求！

一直维持这样的队列，找出队列出现最长的长度时候，求出解！

时间复杂度：O(n)O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length()==0) return 0;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int max = 0;
        int left = 0;
        //abcabcbb
        for(int i = 0; i < s.length(); i ++){
            if(map.containsKey(s.charAt(i))){ // 如果有重复的字符
                left = Math.max(left,map.get(s.charAt(i)) + 1); // 第一次是 left 与 abc  left表示队列的首元素
            }
            map.put(s.charAt(i),i);
            max = Math.max(max,i-left+1);
        }
        return max;
    }
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        int maxLen = 0;
        int left = 0;////滑动窗口左下标，i相当于滑动窗口右下标
        for (int i = 0; i < s.length() ; i++)
        {
            /**
包含相同字符(字符都储存在map里面)————> 需要更新left的位置 ， 
如果相同字符位于窗口 ， 直接left=map.get(s.chat(i))+1
如果字符不在当前的窗口内，如果仍然使用上面的那中计算left的方法，就会导致maxSize过大，
	正确的做法应该是仍然使用当前left的值, 因为我们是可以确定 这个字符不在窗口里面的， 这里仍然使用left的值 相当于为窗口扩大了一个字	  符的范围（也就是吧当前遍历到的这个字符包含进去了）
            
            
1、首先，判断当前字符是否包含在map中，如果不包含，将该字符添加到map（字符，字符在数组下标）,此时没有出现重复的字符，左指针不需要变化。此时不重复子串的长度为：i-left+1，与原来的maxLen比较，取最大值；

2、如果当前字符 ch 包含在 map中，此时有2类情况：

1）当前字符包含在当前有效的子段中，如：abca，当我们遍历到第二个a，当前有效最长子段是 abc，我们又遍历到a，
 那么此时更新 left 为 map.get(a)+1=1，当前有效子段更新为 bca；

2）当前字符不包含在当前最长有效子段中，如：abba，我们先添加a,b进map，此时left=0，我们再添加b，发现map中包含b，
而且b包含在最长有效子段中，就是1）的情况，我们更新 left=map.get(b)+1=2，此时子段更新为 b，
而且map中仍然包含a，map.get(a)=0；
随后，我们遍历到a，发现a包含在map中，且map.get(a)=0，如果我们像 1）一样处理，就会发现 left=map.get(a)+1=1，实际上，left此时
应该不变，left始终为2，子段变成 ba才对。

为了处理以上2类情况，我们每次更新left，left=Math.max(left , map.get(ch)+1).
另外，更新left后，不管原来的 s.charAt(i) 是否在最长子段中，我们都要将 s.charAt(i) 的位置更新为当前的i，
因此此时新的 s.charAt(i) 已经进入到 当前最长的子段中！
             */
            if(map.containsKey(s.charAt(i)))
            {
                left = Math.max(left , map.get(s.charAt(i))+1);
            }
            //不管是否更新left，都要更新 s.charAt(i) 的位置！
            map.put(s.charAt(i) , i);
            maxLen = Math.max(maxLen , i-left+1);
        }
        
        return maxLen;
    }
}

无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度

  • 滑动窗口
  • left为窗口的左下标， i 相当于窗口的右下标
  • 窗口的长度= 右下标+1 - 左下标;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int max=0,left=0; //max用于记录最大不重复子串的长度
        if(s.length()==0) return 0;
        HashMap<Character,Integer> map=new HashMap<>();
        for(int i=0;i<s.length();i++){
            if(map.containsKey(s.charAt(i))){
                left=Math.max(map.get(s.charAt(i))+1,left);
/*这里 left 的赋值有两种可能
1. s.charAt(i) 的重复字符 在窗口内， 直接获取已经存储的这个字符的位置 ，在加一就是新的 窗口的首元素
2. s.charAt(i) 的重复字符不在窗口内， 这里需要这里仍然使用left的值 相当于为窗口扩大了一个字符的范围（也就是把当前遍历到的这个字符		包含进去了） !!!(如果仍然使用上面的那中计算left的方法，就会导致maxSize过大，)  			
				例如abba 再添加最后一个a的时候                       */
            }
            map.put(s.charAt(i),i);
            max=Math.max(max,i+1-left); 
        }
        return max;
    }
}

字符串的排列

难度中等724

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的 子串

由于排列不会改变字符串中每个字符的个数，所以只有当两个字符串每个字符的个数均相等时，一个字符串才是另一个字符串的排列

  • 双指针

注意本题的数组不要用 boolean类型，因为boolean类型只能判断一次

比如s1 =“hello” s2的字串为"heloo" 但是 boolean 数组相应的下标都为true

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int []b1=new int[26];
        int []b2=new int[26];
        for(int i=0;i<s1.length();i++){
            b1[s1.charAt(i)-97]++;
        }
        for(int m=0,n=s1.length();n<=s2.length();m++,n++){
            Arrays.fill(b2,0);
            String temp=s2.substring(m,n);
            for(int i=0;i<temp.length();i++){
                b2[temp.charAt(i)-97]++;
            }
            if(Arrays.equals(b1,b2))
                return true;
        }
        return false;
    }
}

20. 表示数值的字符串

难度中等374

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。

image-20220812153137800image-20220812153137800image-20220812153202773image-20220812153202773image-20220812153241357image-20220812153241357

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public boolean isNumber(String s) {
        Map[] states = {
            new HashMap<>() {{ put(' ', 0); put('s', 1); put('d', 2); put('.', 4); }}, // 0.
            new HashMap<>() {{ put('d', 2); put('.', 4); }},                           // 1.
            new HashMap<>() {{ put('d', 2); put('.', 3); put('e', 5); put(' ', 8); }}, // 2.
            new HashMap<>() {{ put('d', 3); put('e', 5); put(' ', 8); }},              // 3.
            new HashMap<>() {{ put('d', 3); }},                                        // 4.
            new HashMap<>() {{ put('s', 6); put('d', 7); }},                           // 5.
            new HashMap<>() {{ put('d', 7); }},                                        // 6.
            new HashMap<>() {{ put('d', 7); put(' ', 8); }},                           // 7.
            new HashMap<>() {{ put(' ', 8); }}                                         // 8.
        };
        int p = 0;
        char t;
        for(char c : s.toCharArray()) {
            if(c >= '0' && c <= '9') t = 'd';
            else if(c == '+' || c == '-') t = 's';
            else if(c == 'e' || c == 'E') t = 'e';
            else if(c == '.' || c == ' ') t = c;
            else t = '?';
            if(!states[p].containsKey(t)) return false;
            p = (int)states[p].get(t);
        }
        return p == 2 || p == 3 || p == 7 || p == 8;
    }
}

21. 调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。

双指针

  • 首尾双指针，快慢双指针

定义两个指针, 通过循环使左右两个指针左右两边的数字分别是 奇数和偶数(遇到不是的就停下), 然后交换

停止条件:

  • 两个指针相遇( i >= j )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[] exchange(int[] nums) {
        //奇数  n&1==1  这里不能 i<=j , 如果前一次交换刚刚好是 结果
        // 如果在循环一次就会导致  i j 都 分别向后 向前走了一步， 而且这个时候也满足交换条件
        // 就会再交换一次， 导致错误
        int i=0,j=nums.length-1,temp=0;
        while(i<j){
            while(i<j&&(nums[i]&1)==1) i++;
            while(i<j&&(nums[j]&1)==0) j--;   
            if((nums[i]&1)==0&&(nums[j]&1)==1)
            {
                temp=nums[j];
                nums[j]=nums[i];
                nums[i]=temp;
            }
        }
        return nums;
    }
}

22. 链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

  • 双指针

写过了之前的删除链表的倒数第k个节点 ，这道题反而退化版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode p1=new ListNode(1);
        ListNode p2=new ListNode(2);
        p1.next=head;
        p2.next=head;
        for(int i=0;i<k;i++){
            p2=p2.next;
        }
        while(p2.next!=null){
            p1=p1.next;
            p2=p2.next;
        }
        return p1.next;
    }
}
  • 要保存当前节点的后面的节点， 然后让当前的节点执行他前面的节点

24. 反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

  • 双指针

定义pre ， 用来使当前的节点指向前一个节点， cur 是当前的节点， temp 储存cur 的下一个节点（因为如果cur先改变指向就无法在获得下一个节点）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre=null;
        ListNode cur =head;
        while(cur!=null){
            ListNode temp=cur.next;
            cur.next=pre;
            pre=cur;
            cur=temp;
        }
        return pre;
    }
}

25. 合并两个排序的链表

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

直接同时遍历 l1 ,l2 ， 挑选其中数值较小的节点，new 一个与这个节点的值相等的节点作为res 的next即可

最后在链接没有链接完的节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode res=new ListNode(4);
        ListNode op=res;
        while(l1!=null&&l2!=null){
            if(l1.val<=l2.val){
                res.next=new ListNode(l1.val);
                res=res.next;
                l1=l1.next;
            }else{
                res.next=new ListNode(l2.val);
                res=res.next;
                l2=l2.next;
            }
        }
        if(l1==null){   // 直接链接没有new完的链表的剩下那一部分即可
            // while(l2!=null){
            //     res.next=new ListNode(l2.val);
            //     res=res.next;
            //     l2=l2.next;
            // }
            res.next=l2;
        }else{
            // while(l1!=null){
            // res.next=new ListNode(l1.val);
            // res=res.next;
            // l1=l1.next;
            // }  
            res.next=l1;
        }
        return op.next==null?null:op.next;
    }
}