68. 文本左右对齐

给定一个单词数组和一个长度 maxWidth，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。

你应该使用“贪心算法”来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。

要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。

文本的最后一行应为左对齐，且单词之间不插入额外的空格。

说明:

  • 单词是指由非空格字符组成的字符序列。
  • 每个单词的长度大于 0，小于等于 maxWidth。
  • 输入单词数组 words 至少包含一个单词。

示例:

1
2
3
4
5
6
7
8
9
输入:
words = ["This", "is", "an", "example", "of", "text", "justification."]
maxWidth = 16
输出:
[
   "This    is    an",
   "example  of text",
   "justification.  "
]

示例 2:

1
2
3
4
5
6
7
8
9
10
11
12
输入:
words = ["What","must","be","acknowledgment","shall","be"]
maxWidth = 16
输出:
[
  "What   must   be",
  "acknowledgment  ",
  "shall be        "
]
解释: 注意最后一行的格式应为 "shall be    " 而不是 "shall     be",
     因为最后一行应为左对齐，而不是左右两端对齐。       
     第二行同样为左对齐，这是因为这行只包含一个单词。

示例 3:

1
2
3
4
5
6
7
8
9
10
11
12
13
输入:
words = ["Science","is","what","we","understand","well","enough","to","explain",
         "to","a","computer.","Art","is","everything","else","we","do"]
maxWidth = 20
输出:
[
  "Science  is  what we",
  "understand      well",
  "enough to explain to",
  "a  computer.  Art is",
  "everything  else  we",
  "do                  "
]

解答：分三种情况一种是一个单词一行、普通情况、最后一行；每个写成一个 函数，返回String，主函数ArrayList.append();算出每行还剩多少空格在进行分配。

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
78
79
class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> resultList = new ArrayList<>();
        int count = 0;
        int start = 0;
        for(int i = 0; i < words.length; i++) {
            count += words[i].length();
            if(count > maxWidth) {
                resultList.add(helper(words, start, i - 1, maxWidth));
                start = i ;
                count =  words[i].length();
            }
            //单词结束后的空格
            count++;
        }
        //处理最后一截
        resultList.add(helper(words,start,words.length-1,maxWidth));
        return resultList;
    }

    private String helper(String[] words, int start, int end, int maxWidth) {
        StringBuilder sb = new StringBuilder();
        if(start == end) {
            // 一行只有一个单词
            oneWordOneRow(words,start,maxWidth,sb);
        }else if(end == words.length-1) {
            //最后一行
            lastRow(words,start,end,maxWidth,sb);

        }else{
            normal(words,start,end,maxWidth,sb);
        }
        return sb.toString();

    }

    private void oneWordOneRow(String[] words, int start, int maxWidth, StringBuilder sb) {
        sb.append(words[start]);
        int num = maxWidth - words[start].length();
        for(int i = 0; i < num; i++) {
            sb.append(" ");
        }

    }

    private void lastRow(String[] words, int start, int end, int maxWidth, StringBuilder sb) {
        for(int i = start; i<=end; i++) {
            sb.append(words[i]);
            if(i != end) {
                sb.append(" ");
            }else {
                int num = maxWidth - sb.length();
                for (int j = 0; j < num; j++) {
                    sb.append(" ");
                }
            }

        }
    }
    private void normal(String[] words, int start, int end, int maxWidth, StringBuilder sb) {
        int wordsLength = 0;
        for(int i = start; i <= end; i++) {
            wordsLength += words[i].length();
        }
        int seperate =  (maxWidth -wordsLength) / (end - start);
        int remain = (maxWidth -wordsLength) % (end - start);
        for(int i = start;i<=end;i++) {
            sb.append(words[i]);
            if(i != end) {
                for(int j=0; j < seperate; j++) {
                    sb.append(" ");
                }
                if(remain-- > 0){
                    sb.append(" ");
                }
            }
        }
    }
}

3. 无重复字符的最长子串

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

示例 1:

1
2
3
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

思路：

  • 主要是用了一个滑动窗口法
  • 设立一个当前最大值和当前left边界
  • 遇见相同的元素就改变当前left边界位置
  • 然后比较之前获得的最大值，当前得到的不重复字符串长度取最大
  • 遍历结束则得到最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length() == 0) return 0;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int max = 0, left = 0;
        for(int i = 0; i < s.length(); i++) {
            if(map.containsKey(s.charAt(i))) {
                left = Math.max(left, map.get(s.charAt(i)) + 1);
            }
            map.put(s.charAt(i), i);
            //求最大窗口
            max = Math.max(max, i-left+1);
        }
        return max;
    }
}

500. 键盘行

难度简单164

给你一个字符串数组 words ，只返回可以使用在 美式键盘 同一行的字母打印出来的单词。键盘如下图所示。

美式键盘 中：

  • 第一行由字符 "qwertyuiop" 组成。
  • 第二行由字符 "asdfghjkl" 组成。
  • 第三行由字符 "zxcvbnm" 组成。

American keyboard

示例 1：

1
2
输入：words = ["Hello","Alaska","Dad","Peace"]
输出：["Alaska","Dad"]

示例 2：

1
2
输入：words = ["omk"]
输出：[]

示例 3：

1
2
输入：words = ["adsdf","sfd"]
输出：["adsdf","sfd"]

提示：

  • 1 <= words.length <= 20
  • 1 <= words[i].length <= 100
  • words[i] 由英文字母（小写和大写字母）组成

思路：

  • 大小写的处理：全部存入String遍历
  • 返回字符串数组 的构造： List ans = new ArrayList<>(); 返回String需要对其进行重新构造ans.toArray(new String[ans.size()]);
  • 字符串的s.contains()使用：最后+“”，使其变成字符串

解答：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public String[] findWords(String[] words) {
        List<String> ans = new ArrayList<>();
        String[] ss = new String[] {"qwertyuiopQWERTYUIOP", "asdfghjklASDFGHJKL", "zxcvbnmZXCVBNM"};
        for(String word : words) {
            int n1 = 0, n2 = 0, n3 = 0, leng = word.length();
            for(int i = 0; i < leng; i++) {
                if(ss[0].contains(word.charAt(i)+"")) n1++;
                else if(ss[1].contains(word.charAt(i)+"")) n2++;
                else n3++;
            }
            if(n1 == leng || n2 == leng || n3 == leng) ans.add(word);
        }
        return ans.toArray(new String[ans.size()]);
    }
}

NC17 最长回文子串

描述

对于长度为n的一个字符串A（仅包含数字，大小写英文字母），请设计一个高效算法，计算其中最长回文子串的长度。

要求：空间复杂度 O(1)，时间复杂度 O(n^2)

进阶: 空间复杂度 O(n)，时间复杂度 O(n)

示例1

输入：

1
"ababc"

返回值：

1
3

说明：

1
最长的回文子串为"aba"与"bab"，长度都为3

示例2

输入：

1
"abbba"

返回值：

1
5

示例3

输入：

1
"b"

返回值：

1
1

思路：

  • 中心扩散法
  • 两种类型回文“aba”，“abba”
  • 判断两次下标（i, i）（i, i+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
import java.util.*;

public class Solution {
    public int getLongestPalindrome (String A) {
        // write code here
        int n = A.length();
        int maxLen = 1;
        for(int i = 0; i < n; i++){
            int len = centerSpread(A, i, i) > centerSpread(A, i, i+1) ? centerSpread(A,i,i):centerSpread(A,i,i+1);
            maxLen = Math.max(maxLen, len);
        }
        return maxLen;
    }
    
    public int centerSpread(String s, int left, int right) {
        while(left >= 0 && right < s.length()) {
            if(s.charAt(left) != s.charAt(right)) break;
            left--;
            right++;
        }
        //这里left和right多操作了一次
        return right-left-1;
    }
}

思路：中心扩散法，返回具体子串

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
class Solution {
    public String longestPalindrome(String s) {
        //设置最长回文子串的初始和截尾位置
        int start = 0, end = 0;

        for (int i = 0; i < s.length(); i++) {
            //两种类型回文“aba”，“abba” ,所以判断两次(i,i)(i,i+1)
            int len1 = centerSpread(s, i, i);
            int len2 = centerSpread(s,i, i+1);
            int len = Math.max(len1, len2);
            // 发现更长的之后更新end，start
            if (len > end - start) {
                //符合两种情况（3/2=1）
                start = i - (len - 1)/2;
                end = i + (len)/2;
            }
        }
        //[start, end+1)
        return s.substring(start, end + 1);

    }

    public int centerSpread(String s, int left, int right) {
        while(left >= 0 && right < s.length()) {
            if (s.charAt(left) != s.charAt(right)) break;
            left--;
            right++;
        }

        //这里left和right多操作了一次
        return right - left -1;
    }
}

NC1 大数加法

描述

以字符串的形式读入两个数字，编写一个函数计算它们的和，以字符串形式返回。

数据范围：len(s),len(t) \le 100000len(s),len(t)≤100000，字符串仅由’0’~‘9’构成

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

示例1

输入：

1
"1","99"

返回值：

1
"100"

说明：

1
1+99=100

示例2

输入：

1
"114514",""

返回值：

1
"114514"

思路：

  • StringBuilder构建
  • 从后往前加
  • 字符的数=s.charAt(i) - ‘0’
  • StringBuilder反转再转为String

解答：

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


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算两个数之和
     * @param s string字符串 表示第一个整数
     * @param t string字符串 表示第二个整数
     * @return string字符串
     */
    public String solve (String s, String t) {
        // write code here
        int carry = 0;
        StringBuilder ans = new StringBuilder();
        int sLen = s.length();
        int tLen = t.length();
        while(sLen > 0 || tLen > 0 || carry > 0) {
            int sVal = sLen > 0 ? s.charAt(sLen - 1)-'0' : 0;
            int tVal = tLen > 0 ? t.charAt(tLen - 1)-'0' : 0;
            int sum = carry + sVal + tVal;
            carry = sum/10;
            ans.append(sum % 10);
            sLen --;
            tLen --;
        }
        return ans.reverse().toString();
    }
}

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


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算两个数之和
     * @param s string字符串 表示第一个整数
     * @param t string字符串 表示第二个整数
     * @return string字符串
     */
    public String solve (String s, String t) {
        // write code here
        int lenS = s.length(), lenT = t.length();
        int [] arrS = new int [lenS];
        int [] arrT = new int [lenT];
        for(int i = 0; i < lenS; i++) {
            arrS[i] = s.charAt(i)-'0';
        }
        for(int i = 0; i < lenT; i++) {
            arrT[i] = t.charAt(i)-'0';
        }
        
        int maxLen = lenS > lenT ? lenS : lenT;
        int [] res = new int [maxLen + 1];
        int carry = 0;
        for(int i = 0; i < maxLen; i++) {
            res[maxLen-i] = (i < lenS ? arrS[lenS-1-i] : 0) + (i <lenT? arrT[lenT-1-i] : 0);
        }

        for(int i = maxLen; i >= 0; i--) {
            res[i] = res[i]+carry;
            carry = res[i]/10;
            res[i] = res[i]%10;
        }
        int cur = 0;
        while(cur < maxLen + 1 && res[cur] == 0) {
            cur++;
        }
        StringBuilder ans = new StringBuilder();
        for(int i = cur; i < maxLen+1; i++) {
            ans.append(res[i]);
        }
        return ans.length() == 0 ? "0" : ans.toString();
    }
}

NC10 大数乘法

描述

以字符串的形式读入两个数字，编写一个函数计算它们的乘积，以字符串形式返回。

数据范围： 读入的数字大小满足 0 \le n \le 10^{1000}0≤n≤101000
要求：空间复杂度 O(n)O(n)，时间复杂度 O(n^2)O(n2)

示例1

输入：

1
"11","99"

返回值：

1
"1089"

说明：

1
11*99=1089

示例2

输入：

1
"1","0"

返回值：

1
"0"

思路：

  • 字符串转整数数组
  • 拆分每个数字相乘
  • 每个位置的数字进位和留下来的数字取出
  • 整数数组转字符串（注意0*0）

解答：

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

public class Solution {
    /**
     *代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param s string字符串 第一个整数
     * @param t string字符串 第二个整数
     * @return string字符串
     */
    public String solve (String s, String t) {
        // write code here
        // 字符串转数组
        int lenS = s.length();
        int lenT = t.length();
        int[] arrS = new int[lenS];
        int[] arrT = new int[lenT];
        for(int i = 0; i< lenS; i++) {
            arrS[i] = s.charAt(i) - '0';
        }
        for(int i = 0; i< lenT; i++) {
            arrT[i] = t.charAt(i) - '0';
        }
        // 存放结果
        int[] res = new int[lenS + lenT];
        for(int i = 0; i < lenS; i++) {
            for(int j = 0; j < lenT; j++) {
                // 留了一位进位
                res[i + j + 1] += arrS[i] * arrT[j];
            }
        }
        StringBuilder ans = new StringBuilder();
        // 进位的处理
        int carry = 0;
        for(int i = lenT + lenS - 1; i >= 0; i--) {
            res[i] += carry;
            carry = res[i] / 10;
            res[i] = res[i] % 10;
        }
        // 找到有数字的那一位
        int cur = 0;
        while(cur < lenT + lenS && res[cur] == 0) {
            cur++;
        }
        // 整数转字符串
        for(int i = cur; i < res.length; i++) {
            ans.append(res[i]);
        }
        return ans.length() == 0 ? "0" : ans.toString();
    }
}

NC111 最大数

描述

给定一个长度为n的数组nums，数组由一些非负整数组成，现需要将他们进行排列并拼接，每个数不可拆分，使得最后的结果最大，返回值需要是string类型，否则可能会溢出。

数据范围：1 \le n \le 1001≤n≤100，0 \le nums[i] \le 100000≤num**s[i]≤10000

进阶：时间复杂度O(nlogn)O(nlogn) ，空间复杂度：O(n)O(n)

示例1

输入：

1
[30,1]

返回值：

1
"301"

示例2

输入：

1
[2,20,23,4,8]

返回值：

1
"8423220"

示例3

输入：

1
[2]

返回值：

1
"2"

示例4

输入：

1
[10]

返回值：

1
"10"

思路：

  • 整数转字符串
  • 字符串比较（a.compareto.b），比较字符串可以比较它首个的ASCIIC码
  • 注意[0,0]情况返回00不规范
  • StringBuilder构建字符串返回值

解答：

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 Solution {
    /**
     * 最大数
     * @param nums int整型一维数组 
     * @return string字符串
     */
    public String solve (int[] nums) {
        // write code here
        ArrayList<String> list = new ArrayList<>();
        //整形转字符串
        for(int i = 0; i < nums.length; i++) {
            list.add(String.valueOf(nums[i]));
        }
        // 比较字符串可以比较它首个的ASCIIC码，而不是整体的大小
        for(int i = 0; i < nums.length; i++) {
            for(int j = i; j < nums.length; j++) {
                if(((list.get(i)+list.get(j)).compareTo(list.get(j)+list.get(i))) < 0) {
                    swap(list, i, j);
                }
            }
        }
        if(list.get(0).equals("0")) return "0";
        //字符串拼接
        StringBuilder res = new StringBuilder();
        for(int i = 0; i<list.size(); i++) {
            res.append(list.get(i));
        }
        return res.toString();
    }
    public void swap(ArrayList<String> list, int i, int j) {
        String tmp = list.get(i);
        list.set(i, list.get(j));
        list.set(j, tmp);
    }
}