LeetCode HOT100_力扣hot100

1.两数之和

这道题比较简单，直接利用哈希map建立一个字典，然后遍历循环，当前面存的key存在等于target-nums[i],则返回找到的数字的索引。若不存在，则将键值对放入hashmap中。最后遍历结束如果还没找到，就返回一个int数组[0],空数组。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap hashtable = new HashMap();
        for(int i = 0;i<nums.length;i++){
            if(hashtable.containsKey(target - nums[i])){
                return new int[]{i,(int)hashtable.get(target - nums[i])};
            }
            hashtable.put(nums[i],i);
        }
        return new int [0];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

2. 两数相加

这道题思路比较直接，因为数字是按照逆序存储的 ，所以可以把两个链表的数直接按照从头到尾进行相加，注意保存进位值。最后返回头结点即可。特别需要注意的就是加到最后一位，若还有进位，还需要new 一个ListNode,作为最高位

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
       ListNode head = null,res = null;
       int carry = 0;
       while(l1 != null || l2 != null){
           int n1 = l1 ==null ? 0:l1.val;
           int n2 = l2 ==null ? 0: l2.val;
           int sum = n1 + n2 + carry ;
           if(res == null) head = res = new ListNode(sum % 10);
           else {
               res.next = new ListNode(sum % 10);
               res = res.next;
           }
           carry = sum /10 ;
           if(l1 != null) l1 = l1.next;
           if(l2 != null) l2 = l2.next;
       }
       if(carry == 1) res.next = new ListNode(carry);
       return head;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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

方法1：滑动窗口解法：
这个方法主要就是利用一个hashmap保存字符串里的每一个字母和索引位置。然后遍历的时候，维护一个不重复的滑动窗口，主要是更新左边界。当存在重复的值时，左边界就变化为max(left,当前哈希表出现的索引值)，然后再往hashmap中添加键值对，得到结果res=max(res,i-left).其中left初始值为-1.

class Solution {
    public int lengthOfLongestSubstring(String s) {
  	if (s == null || s.length() <= 0) return 0;
        int leftIndex = -1;
        int result = 0;
        Map<Character, Integer> leftIndexMap = new HashMap<Character, Integer>();
        for (int i = 0; i < s.length(); i++) {
            if (leftIndexMap.containsKey(s.charAt(i)) ){   // 当前数字 在之前遍历时出现过，就更新 窗口左边界
                leftIndex = Math.max(leftIndex,leftIndexMap.get(s.charAt(i)));
            }
            leftIndexMap.put(s.charAt(i), i);

            result = Math.max(result, i - leftIndex);   // 计算 当前结果
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

方法2：动态规划问题，好难得看。。。放弃这种方法。

4.寻找两个正序数组的中位数2339*

此题很容易想到对两个数组进行逐位判断，奇偶性需要注意，不管奇偶都需要遍历len/2 +1次，只是偶数个的时候，需要保存前一次结果。
不过此方法时间复杂度为O（m+n）,与题目要求有差距，另外一种是动态规划方法，较难想到，先暂时跳过

class Solution {
   public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int m =nums1.length;
    int n = nums2.length;
    int len = m + n;
    int left = -1, right = -1;
    int aStart = 0, bStart = 0;
    for (int i = 0; i <= len / 2; i++) {
        left = right;
        if (aStart < m && (bStart >= n || nums1[aStart] <nums2[bStart])) {
            right = nums1[aStart++];
        } else {
            right = nums2[bStart++];
        }
    }
    if ((len & 1) == 0)
        return (left + right) / 2.0;
    else
        return right;
}

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

5.最长回文子串（2339**）

动态规划的典型题，不过边界很难想到，初次做的时候，定义dp状态转移方程比较困难。后面回过头来再看。要知道，一个回文子串需要满足，当前回文子串首尾字符相等，且除掉首尾字符后仍然满足回文条件。边界条件就是只有一个字符即符合回文条件，转移方程dp[i][j]==dp[i+1][j-1] &&s[i] ==s[j]。代表以i,j索引区间的字符串为回文串。

public class Solution {

    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }

        int maxLen = 1;
        int begin = 0;
        // dp[i][j] 表示 s[i..j] 是否是回文串
        boolean[][] dp = new boolean[len][len];
        // 初始化：所有长度为 1 的子串都是回文串
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }

        char[] charArray = s.toCharArray();
        // 递推开始
        // 先枚举子串长度
        for (int L = 2; L <= len; L++) {
            // 枚举左边界，左边界的上限设置可以宽松一些
            for (int i = 0; i < len; i++) {
                // 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                int j = L + i - 1;
                // 如果右边界越界，就可以退出当前循环
                if (j >= len) {
                    break;
                }

                if (charArray[i] != charArray[j]) {
                    dp[i][j] = false;
                } else {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }

                // 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }
}


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

6. Z字形变换

看题解下的评论真是笑死个人。这个题又遇到K神写题解了，说明这道题可以拿下了，hhhhh
此题主要理解题意，由于给出的字符串是按照z字形存储的，那么需要按照行数进行读取为另外一个字符串。
主要思路就是按照顺序，从第1行到第n行，将每个字符进行读取，并放到相应的res[]数组中，然后将数组进行拼接起来即可。需要注意的就是每次遇到转角处，需要将flag反转一下，确定是该从小到大放，还是从大到小放。

class Solution {
    public String convert(String s, int numRows) {
        if(numRows < 2) return s;
        List<StringBuilder> rows = new ArrayList<StringBuilder>();
        for(int i = 0; i < numRows; i++) rows.add(new StringBuilder());
        int i = 0, flag = -1;
        for(char c : s.toCharArray()) {
            rows.get(i).append(c);
            if(i == 0 || i == numRows -1) flag = - flag;
            i += flag;
        }
        StringBuilder res = new StringBuilder();
        for(StringBuilder row : rows) res.append(row);
        return res.toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

7.整数反转

通过循环取出每一位，然后开始逐位相乘，计算新值，需要每一次判断是否溢出。假设当前结果为res,下一位为next.则res = res *10 +next;
然后判断是否溢出，具体如下：

class Solution {
    public int reverse(int x) {
        int ans = 0;
        while (x != 0) {
            int pop = x % 10;
            if (ans > Integer.MAX_VALUE / 10 || (ans == Integer.MAX_VALUE / 10 && pop > 7)) 
                return 0;
            if (ans < Integer.MIN_VALUE / 10 || (ans == Integer.MIN_VALUE / 10 && pop < -8)) 
                return 0;
            ans = ans * 10 + pop;
            x /= 10;
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

11. 盛最多水的容器

这道题利用双指针的思路是很明显的。然后主要是根据题意需要知道如何移动双指针，每轮循环只需要移动短板就行了，然后计算水量值与之前的值做对比，保留最大值。至于为什么每次只需要向内移动短板，是因为当向内移动长板时，若新板比短板等于或更长，则短板不变；若新板比短板短，则新短板会更短，水量只会更少，因此只需向内移动短板就ok.两指针初始值分别在0和最右边。

class Solution {
    public int maxArea(int[] height) {
        int i =0,j = height.length-1,res =0 ;
        while(i<j){
            res = height[i] < height[j] ?
            Math.max(res,(j-i)*height[i++]):
            Math.max(res,(j-i)*height[j--]);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11

15. 三数之和

此题先对数组进行升序排列，然后利用三指针进行查找。首先定义一个k，固定为第一个值，然后开始循环，查找三数之和为0的值，接下来开始判断，当nums[k]>0时，说明后面的值都大于0，肯定不存在，直接break;接下里跳过重复值；然后开始确定双指针i和j的值，当i<j时开始循环，判断三数之和是否为0；if sum==0,则把对应的三个值放入结果列表中，然后判断i
和j是否有重复的值，有的话就跳过，相应的执行i++和j–;若和小于0，则i++；并跳过重复的i值；若和大于0，则j–,并跳过重复的值。最后返回结果列表。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for(int k = 0; k < nums.length-2;k++){
            if(nums[k] >0) break;
            if(k>0&&nums[k]== nums[k-1]) continue;
            int i = k+1,j=nums.length-1;
            while(i<j){
                int sum = nums[k] + nums[i] + nums[j];
                if (sum<0){
                    i++;
                }
                else if (sum>0){
                    j--;
                }
                else{
                    res.add(new ArrayList<Integer>(Arrays.asList(nums[k], nums[i], nums[j])));
                    while(i<j && nums[i] == nums[i+1]) i++;
                    while(i<j && nums[j] == nums[j-1]) j--;
                    i++;
                    j--;
                }
            }
        }
        return res;
    }
}
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

17. 电话号码的字母组合

这道题典型的属于思路容易想到，但是用代码写的话很难想到。首先定义一个字符串数组，保存对应数字所表示的字母。然后定义一个结果列表和用来保存每一个可行结果的StringBuilder。首先考虑特殊情况，空字符串直接返回空字符串，然后开始进入回溯函数，参数为输入的数字串以及索引。然后进入回溯函数，当暂存字符串的长度等于输入字符串的长度时，将暂存字符串添加到结果列表中，并返回。然后取出每个数字代表的字母，开始循环，先添加第一个字母，然后递归进入回溯函数，直到遍历完数字串，再回溯删除最后一个字母，开始下一轮循环。

class Solution {

    // 数字到号码的映射
    private String[] map = {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};

    // 路径
    private StringBuilder sb = new StringBuilder();

    // 结果集
    private List<String> res = new ArrayList<>();

    public List<String> letterCombinations(String digits) {
        if(digits == null || digits.length() == 0) return res;
        backtrack(digits,0);
        return res;
    }

    // 回溯函数
    private void backtrack(String digits,int index) {
        if(sb.length() == digits.length()) {
            res.add(sb.toString());
            return;
        }
        String val = map[digits.charAt(index)-'2'];
        for(char ch:val.toCharArray()) {
            sb.append(ch);
            backtrack(digits,index+1);
            sb.deleteCharAt(sb.length()-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

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

这道题之前做过类似的题，因此很容易想到双指针，一个先走n步，然后两个指针再一起走。直接写代码也是一次性过，挺好的。

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy  = new ListNode(0,head);
        ListNode slow = dummy,fast = head;
        for(int i =0;i<n;i++){
            fast = fast.next;
        }
        while(fast !=null){
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

20.有效的括号

终于来了一道相对比较简单的题，此题的思路很直接，肯定要借助栈先进后出的特点进行匹配。因为若光想统计括号的数目的话，是不行的，因为还与括号的位置有关。题解里面提到需要使用map，还有初始化为？的一些tricks，根本用不着啊。
解题思路就是：
首先判断字符串字符的个数，若为奇数，肯定不匹配。
然后定义一个栈，用来保存对应的左括号。
然后开始循环遍历，得到字符串的第i个字符，若属于左括号，则进栈；若属于右括号，则开始判断，若栈为空，说明全是右括号，肯定返回false;然后得到出栈元素top，如果当前右括号字符与弹出的字符不匹配，则返回false;
当遍历结束后，看stack是否为空，为空，这说明是完全匹配的。

class Solution {
    public boolean isValid(String s) {
        int n = s.length();
        if((n & 1) == 1) return false; // 若字符串字数为奇数则肯定不匹配
        Stack<Character> stack = new Stack<>();
        for(int i  = 0 ;i < n; i++){
            char s1 = s.charAt(i);
            if (s1 == '(' ||s1 == '{' || s1 == '[' ) stack.push(s1);
            else{
                if(stack.isEmpty()) return false; //若全是右括号，则栈中会没有元素
                char top = stack.pop();
                if(s1 == ')' && top !='(') return false;
                if(s1 == '}' && top !='{') return false;
                if(s1 == ']' && top !='[') return false;
            }
        }
        return stack.isEmpty();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

21. 合并两个有序链表

这道题初看，就感觉在哪里做过。后面想了想，原来剑指offer里面就有这道题，归为简单类。不过刚开始上来写代码的时候，居然还卡了一会儿，主要是没想到要设置几个节点。这道题只需要设置一个头结点用来保存结果链表，然后定义一个节点指向要求的有序链表即可。
算法流程就是：
设置一个头结点用来保存结果链表，然后定义一个节点指向要求的有序链表即可。先来一个while循环，当有一个链表为null时，跳出循环，因此判断条件为l1 != null && l2!=null;然后判断两个链表的值哪个小，就指向哪个节点，并移动当前节点。最后跳出循环时，判断哪个链表不为null，就指向当前节点，然后返回定义的头结点.next.

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
       ListNode dum = new ListNode(0), cur = dum;
        while(l1 != null && l2 != null) {
            if(l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            }
            else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        if(l1 != null){
            cur.next = l1;
        }
        else{
            cur.next =l2;
        }
        return dum.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

22. 括号生成

这道题是生成括号，与之前的判断括号是否成对的题 感觉有一点点互逆的关系，最开始以为还是要使用栈的方法，但想半天还是想不出来，就只有看看题解。题解说可以采用深度优先遍历或者广度优先遍历，但广度优先需要考虑的东西多一些，就舍弃了这种方法。因此，总结一下深度优先的思路吧：
要生成完全匹配的括号对，就需要知道以下几个结论：
1、当当前左右括号数量为0时，将此字符串添加在结果列表中
2、当产生了右括号分支时，会受到左分支的限制，若左括号剩余数量大于右括号剩余数量，则剪枝，也就是直接return，不保存当前结果值。
3、当产生左右括号的时候，只要还有剩余的括号即可。

public class Solution {
    // 做减法
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        // 特判
        if (n == 0) {
            return res;
        }
        // 执行深度优先遍历，搜索可能的结果
        dfs("", n, n, res);
        return res;
    }

    /**
     * @param curStr 当前递归得到的结果
     * @param left   左括号还有几个可以使用
     * @param right  右括号还有几个可以使用
     * @param res    结果集
     */
    private void dfs(String curStr, int left, int right, List<String> res) {
        // 因为每一次尝试，都使用新的字符串变量，所以无需回溯
        // 在递归终止的时候，直接把它添加到结果集即可，注意与「力扣」第 46 题、第 39 题区分
        if (left == 0 && right == 0) {
            res.add(curStr);
            return;
        }
        // 剪枝（如图，左括号可以使用的个数严格大于右括号可以使用的个数，才剪枝，注意这个细节）
        if (left > right) {
            return;
        }
        if (left > 0) {
            dfs(curStr + "(", left - 1, right, res);
        }
        if (right > 0) {
            dfs(curStr + ")", left, right - 1, res);
        }
    }
}
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

23. 合并K个升序链表

这道题思路很多，虽然是一道困难级别的题。首先最容易想到就是对于合并K个链表，可以采用两两合并的方法。因为之前已经做过合并两个升序链表的题。因此，遍历K个链表，两两合并即可。

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode ans = null;
        for (int i = 0; i < lists.length; ++i) {
            ans = mergeTwoLists(ans, lists[i]);
        }
        return ans;
    }

    public ListNode mergeTwoLists(ListNode a, ListNode b) {
        if (a == null || b == null) {
            return a != null ? a : b;
        }
        ListNode head = new ListNode(0);
        ListNode tail = head, aPtr = a, bPtr = b;
        while (aPtr != null && bPtr != null) {
            if (aPtr.val < bPtr.val) {
                tail.next = aPtr;
                aPtr = aPtr.next;
            } else {
                tail.next = bPtr;
                bPtr = bPtr.next;
            }
            tail = tail.next;
        }
        tail.next = (aPtr != null ? aPtr : bPtr);
        return head.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

方法二：可以采用之前合并两个链表的思路，对k个链表，每次找到最小的值，然后添加到新链表中，遍历结束即可。这种方法时间效率极快，只需要几毫秒，是上种方法的几十分之一。不过需要注意的就是，每次取最小值需要使用到优先队列这种抽象数据结构。需要new一个comparator,重写compare方法，最小堆就是直接返回o1.val-o2.val；最大堆就是返回o2.val-o1.val看看题解代码是如何写的

class Solution {
   public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        //最小堆优先队列，也就是值小的先出队
        PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length, new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                // if (o1.val < o2.val) return -1;
                // else if (o1.val == o2.val) return 0;
                // else return 1;
                return o1.val-o2.val;
            }
        });
        ListNode dummy = new ListNode(0);
        ListNode p = dummy;
        for (ListNode node : lists) {
            if (node != null) queue.add(node);
        }
        while (!queue.isEmpty()) {
            p.next = queue.poll();
            p = p.next;
            if (p.next != null) queue.add(p.next);
        }
        return dummy.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

31. 下一个排列

这道题思路还是很明确的，对数组从尾到头进行遍历，查找是否有当前索引i对应的值比i-1的值大的，如果有，则交换两者的顺序 。写完才发现，是我太单纯了，这样做的话会出问题。因为题目要求的是第一个更大的值，也就是说当找到这个i-1对应的值时，可能i到n之间还存在比i-1只大一点的值，因此还需要遍历这区间的值，找到要交换的值。交换之后，还有一步就是，对i到n之间的值进行升序排列才行，也就是reverse逆转一下，使其从小到大排序。若遍历完毕都没有找到这样的值的话，说明数组就是从大到小排列的，则就将原数组进行升序排列，也就是reverse一下即可。

class Solution {
    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        if (i >= 0) {
            int j = nums.length - 1;
            while (j >= 0 && nums[i] >= nums[j]) {
                j--;
            }
            swap(nums, i, j);
        }
        reverse(nums, i + 1);
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public void reverse(int[] nums, int start) {
        int left = start, right = nums.length - 1;
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }
}
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.最长有效括号

这道题最容易想到的思路就是利用栈的特点。不过与之前判断有效括号不同的是，这道题需要利用右括号为分隔符，且每次在匹配的时候，即遇到右括号首先要弹栈，然后再判断栈是否为空，若为空，说明当前的右括号为没有匹配的右括号，需要将其下标放入栈中来更新最后一个没有匹配的右括号的下标。说到这，需要注意的是，栈底始终存放的是最后一个未匹配的右括号的下标。若栈不为空，则当前右括号的下标减去栈顶元素即为以该右括号为结尾的最长有效括号长度。（还有一个小技巧：如果一开始栈为空，第一个字符为左括号的时候会直接放入其中，为了保证栈底放的是最后一个没有匹配的右括号的下标，需要在最开始往栈中放入一个值为-1的元素）

class Solution {
    public int longestValidParentheses(String s) {
        int maxans = 0;
        Deque<Integer> stack = new LinkedList<Integer>();
        stack.push(-1);
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    maxans = Math.max(maxans, i - stack.peek());
                }
            }
        }
        return maxans;
    }
}

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

33. 搜索旋转排序数组

这道题由于部分有序，想到采用二分法是比较合理的。但是需要注意不少细节，例如：
定义左右指针L和R，当L<=R时，进入循环，把旋转数组二分，左右两边的数组一个是无序的，另一个肯定是有序的。令mid = (l+r)/2首先判断mid值是否等于target，若相等则返回。然后需要判断[L,mid-1]和【mid+1,length-1】区间哪个是有序数组，主要通过左边界值是否大于右边界值来界定是否有序。如果左边的是有序的，然后通过将target
与有序数组进行判断，判定target是否在[L,mid-1]其中，如果在的话，就将右指针r = mid-1；如果不在的话，就令左指针l=mid+1。

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        if (n == 0) {
            return -1;
        }
        if (n == 1) {
            return nums[0] == target ? 0 : -1;
        }
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[0] <= nums[mid]) {
                if (nums[0] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[n - 1]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return -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

34. 在排序数组中查找元素的第一个和最后一个位置

很明显又是一个涉及到二分查找的题。其实二分查找主要考察对细节的控制，也就是里面的左右指针到底如何改变。国外著名算法大师曾说过二分法大致原理虽然原理比较简单，但是其细节和边界是非常具有技巧性的。
然后我在B站搜了一下讲解二分查找的讲解视频，终于找到了一个总结二分查找方法模板的视频，简直是宝藏视频，虽然看的人不多，链接如下：
二分查找模板视频

用这个二分法模板写代码简直不要太酸爽！！！！！之前折磨了快一天的其他解法关于mid+1,mid,mid-1的处理终于可以给我get out了。按照题目要求得到边界值后，再对其进行一些细节判断就可以得到最终答案了。

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left = -1,right = nums.length;
        while(left +1 !=right){
            int mid = (left + right )/2;
            if(nums[mid] < target){
                left = mid;
            }
            else right = mid;
        }
        int leftIndex = right;
        left = -1;
        right = nums.length;
        while(left +1 !=right){
            int mid = (left + right )/2;
            if(nums[mid] <= target){
                left = mid;
            }
            else right = mid;
        }
        int rightIndex = left;
        if(leftIndex<=rightIndex && nums[leftIndex]==target&&nums[rightIndex]==target) return new int[]{leftIndex,rightIndex};
        return new int []{-1,-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

46.全排列

这是一道典型的回溯算法题。这种算法入门级详解见威神题解。
这道题其实解题思路很清晰，主要是如何转化为程序语言来刻画这个问题。要想找到全排列的结果，需要采用深度优先搜索算法，找到每一条可行的路径，然后回溯，恢复源节点的状态，再选择另外一条路径。这里的dfs(状态变量参数)，其中状态变量参数的设计如下：

public class Solution {

    public List<List<Integer>> permute(int[] nums) {
        int len = nums.length;
        // 使用一个动态数组保存所有可能的全排列
        List<List<Integer>> res = new ArrayList<>();
        if (len == 0) {
            return res;
        }

        boolean[] used = new boolean[len];
        Deque<Integer> path = new ArrayDeque<>(len);

        dfs(nums, len, 0, path, used, res);
        return res;
    }

    private void dfs(int[] nums, int len, int depth,
                     Deque<Integer> path, boolean[] used,
                     List<List<Integer>> res) {
        if (depth == len) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < len; i++) {
            if (!used[i]) {
                path.addLast(nums[i]);
                used[i] = true;
                dfs(nums, len, depth + 1, path, used, res);
                used[i] = false;
                path.removeLast();

            }
        }
    }
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

48. 旋转图像******

这题主要的难点在于要求原地旋转，不能额外使用内存。其实是个找规律题，也就是说要知道如何暂存改变的值，将即将改变的值添加到下一个合适的位置。至于规律推导，有点略长了，见力扣题解把。代码倒是不长。其实比较好理解的就是可以从矩阵的四个角出发，想象如何对着四个角的值进行原地置换，需要使用一个temp，保存初始值，然后四个角的值轮流对换就可以实现图像的旋转。当然如何划分四个角的元素呢？主要是(n/2,(n+1)/2）,采用两个for循环进行遍历即可。

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < (n + 1) / 2; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - j - 1][i];
                matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
                matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
                matrix[j][n - i - 1] = temp;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

49. 字母异位词分组

这道题说白了就是将相同字母不同排序的单词组合在一起，思路就是通过一个哈希map保存相同字母的单词。首先遍历每一个单词，将其转换为字符数组，然后排序，这就对应于一个key，然后判断map中是否存在此键值对，若没有的话，则new 一个空数组，若存在的话，就得到此对应的value值，也就是一个list，存放的是相同字母不同排序的单词，然后添加这个新的单词到list，再重新put进hashmap中，遍历结束即可得到对应完整的hashmap，然后getvalues即可。

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map map = new HashMap();
            for(String str :strs){
            char[] array = str.toCharArray();
            Arrays.sort(array);
            String key = new String(array);
            List list = (List)map.getOrDefault(key,new ArrayList());
            list.add(str);
            map.put(key,list);
        }
        return new ArrayList(map.values());
    }
}

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

53.最大子序和

这道题是一道典型的动态规划问题。状态定义为当前i条件下，连续子数组最大和。状态转移方程就是dp[i] = Max(dp[i-1]+nums[i] || nums[i],dp[i-1]),为了减少内存空间的使用，可以定义一个临时变量sum，保存当前状态值,res代表之前状态的最大值。

class Solution {
    public int maxSubArray(int[] nums) {
        int res = nums[0],sum = 0;
        for(int num:nums){
            if(sum>0) sum += num;
            else sum = num;
            res = Math.max(sum,res);
    }
    return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11