hahah, the first time to pass the hard difficulty problem.

缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int firstMissingPositive(int[] nums) {
        Set<Integer> set1 = new HashSet<Integer>();
        int temp = 0;
        for(int num: nums){
            set1.add(num);
        }
        for(int i = 1;i <= nums.length+1; i++){
            if(!set1.contains(i)){
                temp = i;
                break;
            }
        }
        return temp;
    }
}

最大子数组的和

感觉貌似使用的算法叫贪心算法,设置一个max值,如果对于cur位上的数进行相加的时候大于max,那么max就等于cur上的数,否则max就等于max加上cur上的数,最后返回max即可.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int maxSubArray(int[] nums) {
        int max = nums[0];
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            max = Math.max(max, sum);
            sum = Math.max(sum, 0);
        }
        return max;
    }
}

只出现一次的数字

多数元素

两道题可以使用无敌的hash来解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int singleNumber(int[] nums) { 
        int temp = 0;
        Map<Integer,Integer> map1 =new HashMap<Integer,Integer>();
        for(int num : nums){
            map1.put(num,map1.getOrDefault(num,0)+1);
        }
        for(int num : map1.keySet()){
            if(map1.get(num)==1){
                temp = num;
            }
        }
        return temp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int majorityElement(int[] nums) {
        int temp = 0;
        Map<Integer,Integer> map1 = new HashMap<Integer,Integer>();
        for(int num: nums){
            map1.put(num,map1.getOrDefault(num,0)+1);
        }
        for(int num:map1.keySet()){
            if(map1.get(num)>nums.length/2){
                temp = num;
            }
        }
        return temp;
    }
}

括号匹配

没啥说的,注意字符串转字符型

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

class Solution {
    public boolean isValid(String s) {
        Stack<Character> nstack = new Stack<>();
        char[] ca = s.toCharArray();
        for (char c : ca) {
            if (c == '(' || c == '[' || c == '{') {
                nstack.push(c);
            } else if (c == ')') {
                if (nstack.isEmpty() || nstack.pop() != '(') {
                    return false;
                }
            } else if (c == '}') {
                if (nstack.isEmpty() || nstack.pop() != '{') {
                    return false;
                }
            } else if (c == ']') {
                if (nstack.isEmpty() || nstack.pop() != '[') {
                    return false;
                }
            }
        }
        return nstack.isEmpty(); // 检查是否还有未匹配的左括号
    }
}

删除链表的中间节点

无敌的快慢指针,此题应该快指针从头开始

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public ListNode deleteMiddle(ListNode head) {
        if(head==null||head.next==null){
            return null;
        }
        ListNode fast = head; // 修改这里
        ListNode low = head;

        while(fast!=null&&fast.next!=null){
            low = low.next;
            fast = fast.next.next;
        }
        ListNode cur = head;
        while(cur.next != low){
            cur = cur.next;
        }
        cur.next = low.next;
        low.next = null;
        return head;
    }
}