LeetCode一刷(521~540, Medium)

 1public int findLUSlength(String[] strs) {
 2        int length = strs.length;
 3        int max = -1;
 4        // 将每个字符串分别与其它的字符串对比，看这个字符串
 5        for(int i = 0; i < length; i++) {
 6                boolean flag = true;
 7                for(int j = 0; j < length; j++) {
 8                    // i == j,说明是同一个子串，不用比较
 9                    if(i != j && isSub(strs[i], strs[j])){// 看strs[i]是否是strs[j]的子串
10                        flag = false; // 只要有一个不满足，就全都不满足
11                        break;// 退出
12                    }
13                }
14            if(flag == true)  // 能来到这，说明找到了一个子串满足条件
15                max = Math.max(max, strs[i].length());// 找最长的
16        }
17        return max;  
18    }
19
20     //判断string1是否是string2的子串
21    private boolean isSub(String string1, String string2) {
22        if(string1.length() > string2.length())
23            return false;
24
25        int index = 0;
26        for(int i = 0; i < string2.length(); i++) {
27            if(index == string1.length()) return true;
28            // 字符相等，则往下走
29            if(string1.charAt(index) == string2.charAt(i)) {
30                index ++;
31            }
32        }
33        return index == string1.length();        
34    }

 1package com.medium.java;
 2
 3import java.util.HashMap;
 4import java.util.Map;
 5
 6/**
 7 * @author lxn
 8 * @description 523. Continuous Subarray Sum
 9 * @create 2019-04-23 21:10
10 */
11public class Algorithm523 {
12    public static void main(String[] args) {
13        int[] nums = {23, 2, 4, 6, 7};
14        int k = 6;
15        boolean b = new Solution523().checkSubarraySum(nums, k);
16    }
17}
18
19class Solution523 {
20    public boolean checkSubarraySum(int[] nums, int k) {// nums[i] >= 0, k可以是正、负整数、或0。
21        Map<Integer, Integer> map = new HashMap<>();
22/**当数组中出现两个及以上连续的0，且k=0时的情况,若没有这个初始值，会返回false，正确的应该是true。因为：
23 (1) 若没有初值，i=0时，map.get(0)==null,会将key=0(i=0),value=0(sum=0)放入map中，i=1时，sum仍为0，和之前的相同，这时i-pre=1-0=1<1，所以为false。
24 (2) 若有初值，i=0时，pre!=null,但i-pre=0-(-1)=1，map不变，i=1时，i-pre=1-(-1)=2>1,所以为true.
25 (3) 当数组中连续的0大于2时，map没有初始值也能得到正确的结果。*/
26        map.put(0, -1);
27        int sum = 0;
28        for (int i = 0; i < nums.length; i++) {
29            sum += nums[i];
30            if (k != 0) sum %= k; // sum对k取余，这步很关键
31            Integer pre = map.get(sum);
32            if (pre != null) {// map里的key有sum时，其实这里主要是找余数相等的两个和
33                if (i - pre > 1) // 长度至少为2
34                    return true;
35            }else { // map里的key没有sum时
36                map.put(sum, i);
37            }
38        }
39        return false;
40    }
41}

 1public String findLongestWord(String s, List<String> d) {
 2        String res = "";
 3        // 1. 每次先从list中拿一个字符串出来
 4        for (String dict : d) { // 遍历List
 5            int i = 0;
 6            // 2. 然后遍历s的每个字符
 7            for (char c : s.toCharArray()) { // 遍历s
 8                // 3. 若s的当前字符与dict的第i个相同，则下次对照dict的下一个字符
 9                if (i < dict.length() && c == dict.charAt(i)) {
10                    i++;
11                }// 4. 若不同，则比较s的下一个字符，dict还是原来的字符
12
13            }
14
15            // i == dict.length()：说明这个dict是s的子序列
16            // dict.length() >= res.length(): 说明这个dict的长度比res的更长，或等长，更长的直接更新结果为dict的长度，等长的要看字典序
17            if (i == dict.length() && dict.length() >= res.length()) {
18                // dict.length() > res.length(): 长度比res更长，不用比较字典序
19                // “||”后面是dict的长度等于res的长度的情况，要比较字典序
20                // String.compareTo(String2): 比较两个字符串的字典,若前面的小于后面的，则返回负数，等于则返回0，大于则返回正数
21                if (dict.length() > res.length() || dict.compareTo(res) < 0) {
22                    res = dict;
23                }
24            }
25        }
26        return res;
27    }

  1public int findMaxLength(int[] nums) {
 2        // key: 存的是sum  Value: 第一次出现这个sum的下标
 3        Map<Integer, Integer> map = new HashMap<>();
 4        int sum = 0, max = 0;
 5        map.put(0, -1);
 6        for (int i = 0; i < nums.length; i++) {
 7            if (nums[i] == 0) sum -= 1; // 其实这里的sum相当于记录多出的1的个数，有一个0就抵消(减)掉一个1
 8            else sum += 1;
 9            // 若两个sum相等，说明它们之间的0和1相互抵消掉了
10            if (!map.containsKey(sum)) {
11                map.put(sum, i);
12            }else {// map里有值的话，也不更新，map里只保存第一次出现sum的index
13                max = Math.max(max, i - map.get(sum));//i - map.get(sum): 长度
14            }   
15        }
16        return max;
17    }

 1class Solution {
 2    private int cnt = 0;
 3    public int countArrangement(int N) {
 4        // 长度为N+1的boolean数组，默认初始元素为false;
 5        // 用来记录是否已经访问过, 因为优美排列是1~N的数，不能重复.
 6        boolean[] visited = new boolean[N + 1];
 7        count(visited, N, 1);
 8        return cnt;
 9    }
10
11    // index: 已经生成的数字的个数
12    private void count(boolean[] visited, int N, int index) {
13        if (index > N) { // 递归结束条件
14            cnt++;
15            return;
16        }
17
18        for (int i = 1; i <= N; i++) { // 1~N的数，看看是不是都满足
19            if (visited[i] == true) continue; // 若已经访问过，则跳过
20            if (i % index == 0 || index % i == 0) { // 题目里说的是只要满足一个就满足
21                visited[i] = true; // 标为已访问
22                count(visited, N, index + 1); 
23                visited[i] = false; // 恢复初始状态
24            }
25        }
26    }
27}

 1package com.medium.java;
 2
 3import java.util.Random;
 4
 5/**
 6 * @author lxn
 7 * @description 528. Random Pick with Weight
 8 * @create 2019-04-28 17:34
 9 */
10public class Algorithm528 {
11    public static void main(String[] args) {
12        int[] w = {1, 2, 3, 4};
13        Solution528 obj = new Solution528(w);
14        int param_1 = obj.pickIndex();
15    }
16}
17
18class Solution528 {
19    int[] preSum; //preSum，每个数有w[i]个单位
20    Random random;
21    public Solution528(int[] w) {
22        preSum = new int[w.length];
23        preSum[0] = w[0]; // 因为题目说了w的长度至少是1
24        for (int i = 1; i < w.length; i++) { // 从1开始
25            preSum[i] += preSum[i - 1] + w[i];
26        }
27        random = new Random();
28    }
29
30    // 二分查找，唯一不同的是这里要查找的数是随机生成的
31    public int pickIndex() {
32        // Random.nextInt(n): 生成[0,n)的数
33        int num = random.nextInt(preSum[preSum.length - 1]);
34        int l = 0, r = preSum.length - 1;
35        while (l < r) {
36            int mid = l + (r - l) / 2;
37            if (preSum[mid] <= num ) {
38                l = mid + 1;
39            } else {
40                r = mid;
41            }
42        }
43        return l;
44    }
45}

 1    public char[][] updateBoard(char[][] board, int[] click) {
 2        int m = board.length, n = board[0].length;
 3        int row = click[0], col = click[1];
 4
 5        // rule1
 6        if (board[row][col] == 'M') { // M: unrevealed mine
 7            board[row][col] = 'X'; // X: revealed mine
 8            return board;
 9        }
10
11        // rule3
12        int count = 0; // 记录相邻的mine的个数
13        for (int i = -1; i <= 1; i++) {// 看上下左右的点
14            for (int j = -1; j <= 1; j++) {
15                if (i == 0 && j == 0) continue;
16                int r = row + i, c = col + j;
17                if (r < 0 || r >= m || c < 0 || c >= n) continue;
18                // M: unrevealed mine;     X: revealed mine.
19                if (board[r][c] == 'M' || board[r][c] == 'X') { 
20                    count++;
21                }
22            }
23        }
24        // rele3, 如果有相邻的mine, 转成int
25        if (count > 0) board[row][col] = (char)(count + '0'); 
26        else { // rule2, 没有的话，改成'B'，并且要递归地处理它相邻的unrevealed squares.
27            board[row][col] = 'B'; // B: revealed empty square
28            for (int i = -1; i <= 1; i++) { // 递归地看上下左右的点
29                for (int j = -1; j <= 1; j++) {
30                    if (i == 0 && j == 0) continue;
31                    int r = row + i, c = col + j;
32                    if (r < 0 || r >= m || c < 0 || c >= n) continue;
33                    if (board[r][c] == 'E') { // E: unrevealed empty square
34                        updateBoard(board, new int[]{r, c});//递归，click的点变成新的
35                    }
36                }
37            }
38        }
39        return board;
40    }

 1package com.medium.java;
 2
 3import java.util.HashMap;
 4import java.util.Map;
 5
 6/**
 7 * @author lxn
 8 * @description 535. Encode and Decode TinyURL
 9 * @create 2019-05-02 17:51
10 */
11public class Algorithm535 {
12    public static void main(String[] args) {
13        Codec535 codec = new Codec535();
14
15        String longUrl = "https://leetcode.com/problems/design-tinyurl";
16        String shortUrl = codec.encode(longUrl); // 编码
17        String longUrl2 = codec.decode(shortUrl); // 解码
18
19        System.out.println("shortUrl = " + shortUrl);
20        System.out.println("longUrl2 = " + longUrl2);
21
22    }
23}
24
25
26class Codec535 {
27    private Map<Integer, String> map = new HashMap<>();
28    private int index = 0; // int目前够用
29
30    // 编码方法
31    public String encode(String longUrl) {
32        String prefix = "http://tinyurl.com/";
33        map.put(++index, longUrl); // index在Map里: 1、2、3,...n
34        return prefix + index; // index拼在前缀后面
35    }
36
37    // 解码方法
38    public String decode(String shortUrl) {
39        int left = shortUrl.lastIndexOf("/");//拿到"http://tinyurl.com/"的最后一个/的下标
40        return map.get(Integer.parseInt(shortUrl.substring(left + 1, shortUrl.length()))); // shortUrl.substring(left + 1, shortUrl.length()): 得到index
41    }
42}

 1public String complexNumberMultiply(String a, String b) {
 2        int[] xa = getNumv(a);
 3        int[] xb = getNumv(b);
 4        int[] res = new int[2];
 5        res[0] = xa[0] * xb[0] - xa[1] * xb[1]; // 因为i²=-1，所以要减去
 6        res[1] = xa[0] * xb[1] + xa[1] * xb[0]; // 有一个i的那项
 7        String r = String.format("%d+%di", res[0], res[1]);
 8        return r;
 9    }
10
11    private int[] getNumv(String t) {
12        int index = t.indexOf("+");
13        int[] x = new int[2];
14        x[0] = Integer.valueOf(t.substring(0, index));
15        x[1] = Integer.valueOf(t.substring(index + 1, t.length() - 1));
16        return x;
17    }

 1public int findMinDifference(List<String> timePoints) {
 2        int min = Integer.MAX_VALUE;
 3        Collections.sort(timePoints, new Comparator<String>() { // 先排序，其实也可以将原列表timePoints每个元素分别转换成分钟(用个一维数组接收)，然后直接用数组的排序Arrays.sort()
 4            @Override
 5            public int compare(String o1, String o2) {
 6                return transToMinute(o1) - transToMinute(o2);
 7            }
 8        });
 9
10        // 两两求时间间隔，更新min
11        for(int i = 0; i < timePoints.size() - 1; i ++){
12            int res1 = transToMinute(timePoints.get(i));
13            int res2 = transToMinute(timePoints.get(i + 1));
14            if(min >= res2 - res1) min = res2 - res1;
15        }
16
17        // 特殊处理第一个和最后一个时间，就是00:00和23:59这种情况
18        int res1 = transToMinute(timePoints.get(0));
19        int res2 = transToMinute(timePoints.get(timePoints.size() - 1));
20        if(min >= res2 - res1) min = res2 - res1;
21        // 00:00+1天后再减，1天=24h*60mins
22        if(min >= res1 + 24 * 60 - res2) min = res1 + 24 * 60 - res2;
23        return min;
24    }
25
26    // 转成分钟
27    private int transToMinute(String time) { 
28        String[] arr = time.split(":"); 
29        int a = Integer.valueOf(arr[0]).intValue() * 60; 
30        int b = Integer.valueOf(arr[1]).intValue(); 
31        return a + b; 
32    }

 1    public int findMinDifference(List<String> timePoints) {
 2        int[] minuteArr = new int[timePoints.size()]; // 用个数组来接收分钟化后的时间
 3        for (int i = 0; i < minuteArr.length; i++) { 
 4            minuteArr[i] = transToMinute(timePoints.get(i)); //transToMinute同上面的
 5        } 
 6        Arrays.sort(minuteArr); 
 7        // 直接让res的初值为：第一个时间加一天 - 最后一个时间
 8        int res = 24 * 60  + minuteArr[0] - minuteArr[minuteArr.length - 1]; 
 9        for (int i = 0; i < minuteArr.length - 1; i++) { 
10            if (minuteArr[i + 1] - minuteArr[i] < res) // 后一个减前一个
11                res = minuteArr[i + 1] - minuteArr[i]; 
12        } 
13        return res; 
14    }

1    public int singleNonDuplicate(int[] nums) {
2        int res = nums[0];
3        for (int i = 1; i < nums.length; i++) {
4            res ^= nums[i];
5        }
6        return res;
7    }

1    public int singleNonDuplicate(int[] nums) {
2        for (int i = 1; i < nums.length - 1; i++) {
3            if (nums[i] != nums[i - 1] && nums[i] != nums[i + 1])
4                return nums[i];
5        }
6        return nums[0] == nums[1] ? nums[nums.length - 1] : nums[0];
7    }