黄圣杰

bjfuhsj.top

发表于 分类于 阅读次数：
本文字数： 1.1k 阅读时长 ≈ 1 分钟

1.解题思路：

  • 动态规划听上去非常高大上，但是其实都是源自于一个很自然的想法，就拿这道题来说，假如需要判断”onetwothreefour”这一个字符串能不能满足条件，我们很自然的想法就是：
  • 如果”onetwothree”这一段可以拆分，再加上four如果也可以，那不就行了；
  • 或者
  • 如果”onetwothre”这一段可以拆分，再加上efour如果也可以，那不就行了；
  • 这其实已经抓住了动态规划的最核心的东西了，换成式子来表达，就是
1
2
dp["onetwothreefour"] = dp["onetwothree"这一段] && 判断一下"four"
dp["onetwothreefour"] = dp["onetwothre"这一段] && 判断一下"efour"

2.代码：

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
import java.util.*;

public class 单词拆分_139 {
    public static void main(String[] args) {
    }
    public Map<String, Boolean> map = new HashMap<>();
    public boolean wordBreak(String s, List<String> wordDict){

        boolean[] dp = new boolean[s.length() + 1];
        //Java boolean数组默认值为False

        //将List中单词放进 HashMap
        for(String word:wordDict){
            map.put(word, true);
        }

        //初始化
        dp[0] = true;

        //遍历
        /*
        * public String substring(int beginIndex, int endIndex)
        * beginIndex -- 起始索引（包括）, 索引从 0 开始
        * endIndex -- 结束索引（不包括）
        * 索引：读取数组时的下标
        * */
        for(int i=1;i<s.length();i++){
            for(int j=i-1;j>=0;j--){
                dp[i] = dp[j] && check(s.substring(j, i));
                if(dp[i]) break;//这句也很精髓
            }
        }
        return dp[s.length()];
     }
     public boolean check(String s){
        return map.getOrDefault(s, false);
     }
}

3.Refrence

发表于 分类于 阅读次数：
本文字数： 2.8k 阅读时长 ≈ 3 分钟

1.最长公共子序列：

最长公共子序列(LCS):Longest Common Subsequence

  • 对于两个子序列 S1 和 S2，找出它们最长的公共子序列。

  • 定义一个二维数组 dp 用来存储最长公共子序列的长度，其中 dp[i][j] 表示 S1 的前 i 个字符与 S2 的前 j 个字符最长公共子序列的长度。考虑 S1i 与 S2j 值是否相等，分为两种情况：

  1. 当 S1i==S2j 时，那么就能在 S1 的前 i-1 个字符与 S2 的前 j-1 个字符最长公共子序列的基础上再加上 S1i 这个值，最长公共子序列长度加 1，即 dp[i][j] = dp[i-1][j-1] + 1。
  2. 当 S1i != S2j 时，此时最长公共子序列为 S1 的前 i-1 个字符和 S2 的前 j 个字符最长公共子序列，或者 S1 的前 i 个字符和 S2 的前 j-1 个字符最长公共子序列，取它们的最大者，即 dp[i][j] = max{ dp[i-1][j], dp[i][j-1] }。
  3. 综上，最长公共子序列的状态转移方程为：

4c4ff66ed0decdde711678563728e0cf_ecd89a22-c075-4716-8423-e0ba89230e9a.jpg

  • 对于长度为 N 的序列 S1 和长度为 M 的序列 S2，dp[N][M] 就是序列 S1 和序列 S2 的最长公共子序列长度。

作者：bryank-3
链接：https://leetcode-cn.com/problems/longest-common-subsequence/solution/jian-dan-yi-dong-zui-chang-gong-gong-zi-xu-lie-by-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2.代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int longestCommonSubsequence(String text1, String text2) {
    int n1 = text1.length(), n2 = text2.length();
    int[][] dp = new int[n1 + 1][n2 + 1];
    for (int i = 1; i <= n1; i++) {
        for (int j = 1; j <= n2; j++) {
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
              dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
              dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[n1][n2];
}

3.几种解法：

  1. 暴力递归（不用DP Table）

  • 是 从后往前 比较计数的；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def longestCommonSubsequence(str1, str2) -> int:
    def dp(i, j):
        # 空串的 base case
        if i == -1 or j == -1:
            return 0
        if str1[i] == str2[j]:
            # 这边找到一个 lcs 的元素，继续往前找
            return dp(i - 1, j - 1) + 1
        else:
            # 谁能让 lcs 最长，就听谁的
            return max(dp(i-1, j), dp(i, j-1))
        
    # i 和 j 初始化为最后一个索引
    return dp(len(str1)-1, len(str2)-1)

2. 法二，借用DP Table来记录（也可用备忘录）

  • 双层遍历：
  • 判断：当前两个字符一样吗？
    • 一样：左斜上角空格数字（dp[i-1][i-1]） 加1;
    • 不一样：比较 上 && 下 的最大值，取大的那一个来填充当前dp[ i ][ j ]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def longestCommonSubsequence(str1, str2) -> int:
    m, n = len(str1), len(str2)
    # 构建 DP table 和 base case
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    # 进行状态转移
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if str1[i - 1] == str2[j - 1]:
                # 找到一个 lcs 中的字符
                dp[i][j] = 1 + dp[i-1][j-1]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        
    return dp[-1][-1]

3. 优化：用动态数组（一维数组）来解决：

  1. 在利用二维dp数组记录dp[ i ][ j ]时，需要用到dp[ i-1 ][ j-1 ] (左上方),dp[ i-1 ][ j ] (上边),dp[ i ][ j-1 ] (左边)。
  2. 优化为滚动数组记录dp[ j ] (dp[ i ][ j ]) 时，dp[ j-1 ] ( i-1 ) 已被更新为dp[ j-1 ]（ i ），所以需定义变量last去记录未被更新前的dp[ j-1 ]（ i-1 ）;
  3. 所以计算dp[j]的当前值时，会用到last（dp[ i-1 ][ j-1 ]）、dp[ j ] (dp[ i-1 ][ j ])和dp[ j-1 ] (dp[ i ][ j-1 ]);
    注意：计算每一行的第一个元素时候，last需要初始化为0。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n=text1.size(),m=text2.size();
				int dp[m+1],last=0,temp;
				fill(dp,dp+m+1,0);//fill(数组名，起始地【包括】，结束地【不包括】，填充值)
        for(int i=1;i<=n;++i,last=0){
						for(int j=1;j<=m;++j){
            	    temp=dp[j];
		   						if(text1[i-1]==text2[j-1])	dp[j]=last+1; 
		   						else	 dp[j]=max(dp[j],dp[j-1]);
        	  			last=temp;
						}
        }
	return dp[m];
    }
};
  • 画一下流程图你就懂了，顺着 DP Table，按着上面的代码（一维数组）推一遍：
    1. 先用 temp 保存当前节点，然后更新当前节点；
    2. 其中更新的时候，有两种情况：
      1. 不相等：用 左边 （体现在一维数组的前一个位置）和 上面（体现在一维数组的当前位置）进行比较，取更大的值来刷新当前节点（体现在一维数组当前的位置）
      2. 相等：用 last + 1 ，其中 last 表征左上角（是在每一轮结束之后，把之前保存的 旧的 当前位置值 给保存下来；从二位数组角度看来，就是左上角：因为 temp 下一轮已经右移，但是 last 还在上一个位置；）
    3. 更新完当前节点位置数据之后，用 last 把当前的节点 旧的信息保存下来，last = temp，从二位数组角度看，就像是左上角数据；
    4. 然后循环1，2，3步骤
  • 注意，每一行结束更新之后，要把 last 重新归零！相当于 左上角数据从零开始重新移动（默认第零行、第零列 全为零）
  • img

发表于 更新于 分类于 阅读次数：
本文字数： 2.5k 阅读时长 ≈ 2 分钟

1.题目：

image-20200624145409923

2.思路：

3.滑动窗口的概念：

  • 利用 双指针 来实现；即左指针 表示窗口左边界，右指针 表示窗口右边界；
  • 然后滑动，即意味着 有序地，左右指针移动

4.判断重复字符：

5.代码：

法一：用HashSet直接查（里面只存一个值对象）

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
import java.util.*;

public class 无重复字符的最长子串_3 {
    public static void main(String[] args) {
    }
    public int lengthOfLongestSubstring(String s){
        //HashSet:记录每个字符是否出现过
        Set<Character> occ = new HashSet<Character>();
        /*
        · set.remove()
        · set.add()
        · srt.contains()
        * */
        //对比：
//        Map<String, String> map = new HashMap<>();
        int rk = -1,ans = 0;//rk:右指针；
        int n = s.length();
        for(int i = 0; i < n ; i++){
            if(i != 0){//左指针右移
                occ.remove(s.charAt(i-1));
            }
            while(rk + 1 < n && !occ.contains(s.charAt(rk+1))){
                occ.add(s.charAt(rk+1));
                ++rk;
            }
            ans = Math.max(ans, rk - i + 1);//返回最长的长度值；
        }
        return ans;
    }
}

法二：，更简洁的滑动

HashMap（Key， Value）

  • 标签：滑动窗口

  • 暴力解法时间复杂度较高，会达到 O($N^2$)

  • 故而采取滑动窗口的方法降低时间复杂度

  • 定义一个 map 数据结构存储 (k, v)，其中 key 值为字符，value 值为字符位置 +1，加 1 表示从字符位置后一个才开始不重复

  • 我们定义不重复子串的开始位置为 start，结束位置为 end

  • 随着 end 不断遍历向后，会遇到与 [start, end] 区间内字符相同的情况，此时将字符作为 key 值，获取其 value 值，并更新 start，此时 [start, end] 区间内不存在重复字符

  • 无论是否更新 start，都会更新其 map 数据结构和结果 ans。

  • 时间复杂度：O(n)

  • public int lengthOfLongestSubstring_滑动窗口(String s){
  int n = s.length(), ans = 0;
  Map<Character, Integer> map = new HashMap<>();
  for(int end=0,start=0; end<n; end++){
    char alpha = s.charAt(end);
    if(map.containsKey(alpha)){
      start = Math.max(map.get(alpha), start);//这个很重要
    }
    /*
    * if(map.containsKey(s.charAt(i)))
    * j = Math.max(map.get(s.charAt(i)),j);
    * 为什么有这个判断，是因为在滑动过程中会出现当前loop出现的重复元素之间的区间，
    * 可能还有其他元素也是重复的。
    * 如果仅仅 j =map.get(s.charAt(i)) 
    * 则你会忽略两个重复元素之间还有的其他元素也是重复的，
    * 例如 a bba ，如果没有max，则答案会是3，因为最后一个a和前一个a的间距是3，
    * 不加max就考虑不到中间两个b也是重复的。）
    * */
    ans = Math.max(ans, end - start + 1);
    map.put(s.charAt(end), end+1);
  }
  return ans;
}
<!--1-->

  • 返回从 fromIndex 位置开始查找指定字符在字符串中第一次出现处的索引，如果此字符串中没有这样的字符，则返回 -1。

  • int indexOf(String str);
<!--2-->

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
class Solution {
	public int lengthOfLongestSubstring(String s) {
		int i = 0;
		int flag = 0;
		int length = 0;
		int result = 0;
		while (i < s.length()) {
			int pos = s.indexOf(s.charAt(i),flag);
			if (pos < i) {
				if (length > result) {
					result = length;
				}
				if (result >= s.length() - pos - 1) {
					return result;
				}
				length = i - pos - 1;
				flag = pos + 1;
			}
			length++;
			i++;
		}
		return length;
	}
}

作者：VioletKiss
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/javati-jie-3wu-zhong-fu-zi-fu-de-zui-chang-zi-chua/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

发表于 更新于 分类于 阅读次数：
本文字数： 2.9k 阅读时长 ≈ 3 分钟

1.知识点：

  • 双指针
  • 数组排序（默认升序）；自定义降序

2.排序代码

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

/*
 * Java 中 实现 数组的排序
 * 默认是 上升序列；
 * 若要 下降，则默认需要 Integer 或者 Float 等 "类"类型，不能使用基础类型；
 *
 * */
import java.util.*;

public class 最接近的三数之和_16  {
    public static void main(String[] args) {
        //注意，要想改变默认的排列顺序，不能使用基本类型（int,double, char）,而要使用它们对应的类
        Integer[] arr = {9, 8, 7, 2, 3, 4, 1, 0, 6, 5};
        //定义一个自定义类MyComparator的对象
      //法一：实现降序；需要类型，不能是基础类型
//        Arrays.sort(arr,Collections.reverseOrder());
      //法二：实现降序
//        Arrays.sort(arr, (a,b) -> (b - a));         

      //法三：需要自己重写 Comparator
        Comparator cmp = new MyComparator();      
        Arrays.sort(arr, cmp);
        for (int x : arr) {
            System.out.print(x + " ");
        }

        //若得到的是 int ，需要先手动转为 Integer 类型！
        int scores[] = new int[]{1,2,3,89,4};
        Integer newScores[] = new Integer [5];
        for(int i=0;i<scores.length;i++){
//            newScores[i]= new Integer(scores[i]);
            newScores[i] = scores[i];
        }
        System.out.println();

        Arrays.sort(newScores,Collections.reverseOrder());
        for (int x : newScores) {
            System.out.print(x + " ");
        }

    }
}

//实现Comparator接口
class MyComparator implements Comparator<Integer> {
    @Override //作用是检查下面的方法名是不是父类中所有的，也起到注释的作用
    public int compare(Integer a, Integer b) {
        return a > b ? -1 : 1;
    }
}

  • 注意点：

  • Collections.reverseOrder()
<!--1-->

* 道理同上
  • 自己重写 Comparator
<!--2-->

才可以实现 用 int 类型直接排序（默认是升序列）

  • 若要降序，基本都需要 Integer 类型；

  • 若是 int 基础类型，那么需要手动 转换一下类型；

3.题目：

寻找数组中三个数字之和，要求和最接近于目标数值

image-20200624135415119

  • 法一：暴力：O（$N^3$）

  • ```java
    //法一：暴力 O(n^3)
    int best = 100000;
    int diff = 100000;
    for(int i=0;i<nums.length;i++){

    for(int j = i+1;j<nums.length;j++){
    for(int k = j+1;k<nums.length;k++){
        if(Math.abs(nums[i]+nums[j]+nums[k] - target) < diff){
            diff = Math.abs(nums[i]+nums[j]+nums[k] - target);
            best = nums[i]+nums[j]+nums[k];
        }
    }
}

    }
    return best;

    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

    * 

    * 法二：双指针：第一个元素从头到尾遍历，二、三元素从表头、尾向中间靠拢。

      * 好处是：省掉了很多没必要的不可能组合；（有点剪枝的意思了）

    ```java
    import java.util.*;

    public class 最接近的三数之和_16 {
        public static void main(String[] args) {
        }
        public int threeSumClosest(int[] nums, int target){
            Arrays.sort(nums);//升序排列
            int n = nums.length;
            int best = 10001000;

            for(int i = 0;i < n; i++){
                //若下一个元素和当前元素内容一样，则可以跳过；
                //continue，直接跳过当前循环，进入下一次循环；
                if(i>0 && nums[i] == nums[i-1]){
                    continue;
                }

                //使用双指针，枚举 b 和 c；
                int j = i+1, k = n-1;
                while(j < k){
                    int sum = nums[i] + nums[j] + nums[k];
                    //如果直接等于target，那么直接返回，最接近；
                    if(sum == target){
                        return target;
                    }
                    if(Math.abs(sum - target) < Math.abs(best - target)){
                        best = sum;
                    }
                    if(sum > target){
                        int k0 = k - 1;
                        //开始移动 c 的指针，直到比原本的 c 值要小；
                        // 向左移动到下一个不想等的元素；
                        while(j < k0 && nums[k0] == nums[k]){
                            --k0;
                        }
                        k = k0;  // 如果发生 k = k0 == j;那么会退出现在的 while(j < k)
                    }else{
                        //如果 sum < target，那么就把 b 指针向左移动；
                        int j0 = j+1;
                        while(j0 < k && nums[j0] == nums[j]){
                            ++j0;
                        }
                        j = j0;
                    }
                }
            }
            return best;
        }
    }

发表于 更新于 分类于 阅读次数：
本文字数： 866 阅读时长 ≈ 1 分钟

1.一些新的知识点：

  • 当对字符串进行修改的时候，需要使用 StringBuffer 和 StringBuilder 类。

image-20200623191413447

  • “charAt() 方法用于返回指定索引处的字符。索引范围为从 0 到 length() - 1。”
  • image-20200623191946701
  • Java 的反转函数 reverse() 将字符串反转
  • string.reverse（）；
  • image-20200623192245991
  • 位运算符：
  • image-20200623193029996
  • ^ : 按位抑或：不进位的加法：

2.想法

  • 突然看到string字符串求和，想起了以前的各种题目，但是很没有头绪；
  • 印象中，都是用最笨的 数组 的方式来进行，从没有尝试过用string来进行处理；

是个学习的机会；

3.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public String addBinary(String a, String b) {
        StringBuffer ans = new StringBuffer();
        int carry = 0;
        int n = Math.max(a.length(),b.length());

        for(int i=0;i<n;i++){
            //string.charAt（）:寻找当前string在指定位置的 字符 char；
            // 细节： string.length() 需要用上括号！ 别忘记括号！
            carry += i < a.length()? (a.charAt(a.length() - 1 - i) - '0') : 0;
            carry += i < b.length()? (b.charAt(b.length() - 1 - i) - '0') : 0;

            ans.append((char)(carry % 2 + '0'));
            carry /= 2;
        }
        if(carry > 0){
            ans.append('1');
        }
        ans.reverse();// 这个方法实现的功能是，将 StringBuffer 字符串进行反转！！！
        return ans.toString();
      //因为是 StringBuffer 类型，而返回类型要求是 String，所以调用 toString（）方法；
    }
}

发表于 更新于 分类于 阅读次数：
本文字数： 2.4k 阅读时长 ≈ 2 分钟

1.445题目

image-20200623182854483

2.类型：链表 && 栈

正序的数字链表，求和时希望从个位开始算（逆序算），所以应该想到利用 栈（FILO）

3.与002区别：

  • 002采用的是直接逆序存储的数字链表，所以可以直接从数字的尾巴开始求和，另外增加一个 进位标志符号 就可以；

4.代码 Java

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
import java.util.*;

public class twoSum_445 {
    public static void main(String[] args) {
    }
    public class ListNode {
         int val;
         ListNode next;
         ListNode(int x) { val = x; }
    }
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        while( l1 != null){
            stack1.push(l1.val);
            l1 = l1.next;
        }
        while( l2 != null){
            stack2.push(l2.val);
            l2 = l2.next;
        }

        int carry = 0;//进位符号
        ListNode head = null;
        while(!stack1.empty() || !stack2.empty()){
            int sum = carry;
            sum += stack1.isEmpty()? 0:stack1.pop();
            sum += stack1.isEmpty()? 0:stack2.pop();
            ListNode node = new ListNode(sum % 10);
            node.next = head;
            head = node;
            carry = sum / 10;
        }
        return head;
    }

}

5.比较 002 代码：

image-20200623182835143

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
import java.util.*;

public class twoSum_002 {
    public static void main(String[] args) {
    }
    public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }
    
    //这份写的更漂亮，更优美，学习一个！
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int carry = 0;
        ListNode dummyHead = new ListNode(0);

        ListNode p = l1, q = l2, curr = dummyHead;
        while(p != null || q!= null){
            int x = (p != null)? p.val : 0;
            int y = (q != null)? q.val : 0;
            int sum = x + y + carry;
            carry = sum / 10;
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
            if(p != null) p = p.next;
            if(q != null) q = q.next;
        }
        if(carry > 0){
            curr.next = new ListNode(carry);
        }
        return dummyHead.next;
    }
    
    //这个我自己写的，改了好多地方才对，细节很多
    public ListNode addTwoNumber_HSJ(ListNode l1, ListNode l2){
        int carry = 0;
        ListNode head = new ListNode(0);
        ListNode curr = head;

        while( l1 != null || l2 != null){//细节，不是 l1.next !!!
            int sum = 0;
            sum += carry;

            if( l1 != null)
                sum += l1.val;
            if( l2 != null)
                sum += l2.val;

            ListNode node = new ListNode(0);

            carry = sum / 10;
            node.val = sum % 10;
            curr.next = node;
            curr = node;
//            node.next = head;
//            head = node;

            if(l1 != null) l1 = l1.next;
            if(l2 != null) l2 = l2.next;

        }
        if(carry > 0){//细节！
            curr.next = new ListNode(carry);
        }
        return head.next;

    }

}