字符串的拍列

题目

Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string’s permutations is the substring of the second string.
Example 1:
Input:s1 = “ab” s2 = “eidbaooo”
Output:True
Explanation: s2 contains one permutation of s1 (“ba”).
Example 2:
Input:s1= “ab” s2 = “eidboaoo”
Output: False
Note:
The input strings only contain lower case letters.
The length of both given strings is in range [1, 10,000].

解析重点

1.s2的字串是s1的排列。那么，我们可以把查找过程分为两步。第一步，滑动窗口在s2上，步长为s1。第二步，比较滑动窗口字串和s1内容，判断是否是s1的排列。
2.第一步滑动s2好处理。第二步，我们要怎么处理呢，我们只需要统计两个串字母的数量是否相等即可。

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

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if(s1==null||s2==null||s1.length()>s2.length()) return false;
        int len1=s1.length(),len2=s2.length();
        int[] count=new int[26];
        for(int i=0;i<len1;i++){//初始化比较len1长度的串
            count[s1.charAt(i)-'a']--;
            count[s2.charAt(i)-'a']++;
        }
        if(allZero(count)) return true;
        for(int j=len1;j<len2;j++){//s2一直保持截取len1长度的串
            count[s2.charAt(j)-'a']++;//s2截取的串添加一个字符j
            count[s2.charAt(j-len1)-'a']--;//s2减少一个起始位置的字符（j-len1），这样保持s2截取的串一直是len1
            if(allZero(count)) return true;
        }
        return false;
        
    }
    private boolean allZero(int[] count) {
        for (int i = 0; i < 26; i++) {
            if (count[i] != 0) return false;
        }
        return true;
    }    
}

无重复字符串最长字串

题目

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.
Example 2:

Input: “bbbbb”
Output: 1
Explanation: The answer is “b”, with the length of 1.
Example 3:

Input: “pwwkew”
Output: 3
Explanation: The answer is “wke”, with the length of 3.
Note that the answer must be a substring, “pwke” is a subsequence and not a substring.

解析重点

1.我们可以滑动窗口i、j，窗口覆盖的即为字串。当滑动到下一个字符时，如果当前字符出现过，1.当前字符在滑动窗口外，则无影响。2.当前字符出现在滑动窗口内，
则出现了重复，起始位置重置为当前字符前一次出现的位置+1，即s.charAt(j)+1

java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n=s.length(),nas=0;
        Map<Character,Integer> map = new HashMap<>();
        for(int j=0,i=0;j<n;j++){//i->子串起始位置，j->子串结束位置
            if(map.containsKey(s.charAt(j))){//判断当前字符是否出现过
                i=Math.max(map.get(s.charAt(j))+1,i);//如果当前字符出现过，1.当前字符出现的位置在i前面，则i不变，
                                                     //2.当前字符出现的位置在i后面，则重置起始位置为s.charAt(j)+1
            }
            nas=Math.max(nas,j-i+1);//比较历史字串和当前窗口串的大小
            map.put(s.charAt(j),j);//当前位置索引放入hashmap
        }
        return nas;
    }
}

两个排序数组的中位数

题目

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0
Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

解析重点

1.什么是中位数，中位数就是把数组分为相等两份的数，且左边比右边小。假设m<n,那么对数组a[m]我们有m+1中切分方式。当我们从a[i]个位置切分数组时，b[j]要从哪里切分
才合适呢？j=m+n+1/2−i时，两个数组两边正好划分为相等的两部分。
2.划分为相等两份后，我们还要保证左边比右边小，这时我们需要移动i。
当B[j−1]≤A[i] 且 A[i−1]≤B[j]：这意味着我们找到了目标对象 i，所以可以停止搜索。
B[j−1]>A[i]：这意味着 A[i] 太小，我们必须调整 i 以使 B[j−1]≤A[i]。我们可以增大 i，因为当 i 被增大的时候，j 就会被减小。因此 B[j−1] 会减小，而 A[i] 会增大，
那么 B[j−1]≤A[i] 就可能被满足。所以我们必须增大 i。也就是说，我们必须将搜索范围调整为 [i+1,imax]。 因此，设 imin=i+1。
A[i−1]>B[j]： 这意味着 A[i−1] 太大，我们必须减小 i 以使 A[i−1]≤B[j]。 也就是说，我们必须将搜索范围调整为 [imin,i−1]。因此，设 imax=i−1。
也就是我们以二分法来搜索i的值。
3.目标值，max(A[i−1],B[j−1]), 当 m+n 为奇数时；
max(A[i−1],B[j−1])+min(A[i],B[j])/2, 当 m+n 为偶数时。

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

class Solution {
    public double findMedianSortedArrays(int[] A, int[] B) {
        int m = A.length;
        int n = B.length;
        if (m > n) { // to ensure m<=n
            int[] temp = A; A = B; B = temp;
            int tmp = m; m = n; n = tmp;
        }
        int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
        while (iMin <= iMax) {
            int i = (iMin + iMax) / 2;
            int j = halfLen - i;
            if (i < iMax && B[j-1] > A[i]){
                iMin = i + 1; // i is too small
            }
            else if (i > iMin && A[i-1] > B[j]) {
                iMax = i - 1; // i is too big
            }
            else { // i is perfect
                int maxLeft = 0;
                if (i == 0) { maxLeft = B[j-1]; }
                else if (j == 0) { maxLeft = A[i-1]; }
                else { maxLeft = Math.max(A[i-1], B[j-1]); }
                if ( (m + n) % 2 == 1 ) { return maxLeft; }

                int minRight = 0;
                if (i == m) { minRight = B[j]; }
                else if (j == n) { minRight = A[i]; }
                else { minRight = Math.min(B[j], A[i]); }

                return (maxLeft + minRight) / 2.0;
            }
        }
        return 0.0;
    }
}

二叉树中的最大路径和

题目

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Example 1:

Input: [1,2,3]

  1
 / \
2   3

Output: 6
Example 2:

Input: [-10,9,20,null,null,15,7]

-10
/ \
9 20
/ \
15 7

Output: 42

解析重点

1.最大路径和，我们需要递归计算路径的和，然后把最大的路径和存储起来。当路径上的和小于0时，我们需要舍弃这部分节点。同时我们还需要比较左右节点，路径大的
一边才是我们需要的。

java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
    int max;

    public int maxPathSum(TreeNode root) {
        max = Integer.MIN_VALUE;
        maxCySum(root);
        return max;
    }

    int maxCySum(TreeNode root) {
        if (root == null) return 0;
        int left = Math.max(0, maxCySum(root.left));//左节点路径和，当左节点小于0时舍弃
        int right = Math.max(0, maxCySum(root.right));//右节点路径和，当右节点小于0时舍弃
        max = Math.max(max, left + right + root.val);//累计计算max，保存最大的max
        return Math.max(left, right) + root.val;//返回路径和大的路径和
    }
}

字符串转换整数

题目

Implement atoi which converts a string to an integer.

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned.

Note:

Only the space character ‘ ‘ is considered as whitespace character.
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. If the numerical value is out of the range of representable values, INT_MAX (231 − 1) or INT_MIN (−231) is returned.
Example 1:

Input: “42”
Output: 42
Example 2:

Input: “ -42”
Output: -42
Explanation: The first non-whitespace character is ‘-‘, which is the minus sign.
Then take as many numerical digits as possible, which gets 42.
Example 3:

Input: “4193 with words”
Output: 4193
Explanation: Conversion stops at digit ‘3’ as the next character is not a numerical digit.
Example 4:

Input: “words and 987”
Output: 0
Explanation: The first non-whitespace character is ‘w’, which is not a numerical
digit or a +/- sign. Therefore no valid conversion could be performed.
Example 5:

Input: “-91283472332”
Output: -2147483648
Explanation: The number “-91283472332” is out of the range of a 32-bit signed integer.
Thefore INT_MIN (−231) is returned.

解析重点

1.这题不是很复杂，根据逻辑判断下即可。需要注意的是，数字越界的判断。

三数之和

题目

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]

解析重点

1.我们需要知道当移动数组时，三数的和改变的情况。那么，先对数组进行排序，这样移动数组时，我们知道和是变大还是变小。
2.固定一个数a之后，那么就变成了两数之和。这时，我们怎么移动b和c呢。b从左边开始移动，c从右边开始移动，当b+c>0-a时,我们需要减小值，那么移动c，反之，
移动b，直到b、c相交。

java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public List<List<Integer>> threeSum(int[] num) {
    Arrays.sort(num);
    List<List<Integer>> res = new LinkedList<>(); 
    for (int i = 0; i < num.length-2; i++) {
        if (i == 0 || (i > 0 && num[i] != num[i-1])) {
            int lo = i+1, hi = num.length-1, sum = 0 - num[i];
            while (lo < hi) {
                if (num[lo] + num[hi] == sum) {
                    res.add(Arrays.asList(num[i], num[lo], num[hi]));
                    while (lo < hi && num[lo] == num[lo+1]) lo++;
                    while (lo < hi && num[hi] == num[hi-1]) hi--;
                    lo++; hi--;
                } else if (num[lo] + num[hi] < sum) lo++;
                else hi--;
           }
        }
    }
    return res;
}
}

最长回文字串

题目

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: “babad”
Output: “bab”
Note: “aba” is also a valid answer.
Example 2:

Input: “cbbd”
Output: “bb”

解析重点

1.最长回文字串就是最长的对称字串，那么对于一个字符串，这样的对称中心有几个呢，有2n-1个，以字母为对称中心和以字母间隙为对称中心，
那么我们就可以以对称中心为基础进行搜索。

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

class Solution {
    public String longestPalindrome(String s) {
    if (s == null || s.length() < 1) return "";
    int start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
        int len1 = expandAroundCenter(s, i, i);
        int len2 = expandAroundCenter(s, i, i + 1);
        int len = Math.max(len1, len2);
        if (len > end - start) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    return s.substring(start, end + 1);
}

private int expandAroundCenter(String s, int left, int right) {
    int L = left, R = right;
    while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
        L--;
        R++;
    }
    return R - L - 1;
}
}

循环链表||

题目

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Note: Do not modify the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.

Follow up:
Can you solve it without using extra space?

解析重点

1.为了知道是否有循环，我们使用通用的方式使用快慢指针。
2.这里重要的是快慢指针相交的点c，他到head点的距离和循环的距离是相等的，那么从head点和交点c出发，他们相等的点就是交点。

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

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
	ListNode slow = head, fast = head;
	while(fast != null && fast.next != null) {
		fast = fast.next.next;
		slow = slow.next;
		if (slow == fast) {
			while (head != slow) {
				head = head.next;
				slow = slow.next;
			}
			return slow;				
		}
	}			
	return null;
}
}

优化思路

我们的程序运行会涉及到硬件（网络）、操作系统、大数据产品及配置、应用程序开发、数据这几个方面，当我们优化时，也可以从这几个方面着手。
当资源没有全面利用时，我们可以考虑优化配置、大数据应用程序、数据本身；当资源利用到极限，那就具体看是集群资源不足，还是对某项硬件、操作系统、
jvm，甚至是大数据产品源码进行调优。

数据

应用程序开发

大数据配置

大数据产品

操作系统

硬件（网络）

旋转矩阵

题目

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

Example 1:

Input:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]
Example 2:

Input:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

解析重点

1.我们查看矩阵，旋转矩阵的时候会涉及到4个点，上top下bottom左left右right。当我们第一次旋转时，left->right，将这些点旋转完后，top将会受到影响，top+1
类似的，top->bottom，right->left,boottom->top，也会有同样的规律。那么我们什么时候终止呢，当top和bottom，left和right重合时我们就可以终止了。

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

public class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<Integer>();
        if(matrix.length == 0 || matrix[0].length == 0) return res;
        
        int top = 0;
        int bottom = matrix.length-1;
        int left = 0;
        int right = matrix[0].length-1;
        
        while(true){
            for(int i = left; i <= right; i++) res.add(matrix[top][i]);
            top++;
            if(left > right || top > bottom) break;
            
            for(int i = top; i <= bottom; i++) res.add(matrix[i][right]);
            right--;
            if(left > right || top > bottom) break;
            
            for(int i = right; i >= left; i--) res.add(matrix[bottom][i]);
            bottom--;
            if(left > right || top > bottom) break;
            
            for(int i = bottom; i >= top; i--) res.add(matrix[i][left]);
            left++;
            if(left > right || top > bottom) break;
        }
        
        return res;
    }
    
}