Leetcode刷题第二周

链表：插入快，查询慢，存储不连续
分为单链表，双链表和循环链表
在链表中使用虚拟头结点，可以减少增删改查中对头结点的特殊处理

为大英等地区用户提供了全套网页设计制作服务，及大英网站建设行业解决方案。主营业务为网站设计、网站建设、大英网站设计，以传统方式定制建设网站，并提供域名空间备案等一条龙服务，秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求，就会得到认可，从而选择与我们长期合作。这样，我们也可以走得更远！

移除链表元素

203

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        // 时间复杂度O(n)，空间复杂度O(1)
        if(head == null){//空链表的情况
            return head;
        }
        while(head != null && head.val == val){//头结点为val的情况
            head = head.next;
        }
        ListNode temp = head;
        while(temp != null && temp.next != null){
            while(temp != null && temp.next != null && temp.next.val == val){
                if(temp.next.next != null){
                    temp.next = temp.next.next;
                }else{//最后一个节点为val的情况
                    temp.next = null;
                }
                
            }
            temp = temp.next;
        }
        return head;
    }
}

707、设计链表

class MyLinkedList {
    int size;
    ListNode head;
    ListNode tail;
// 初始化链表,构建虚拟的头结点和尾节点
    public MyLinkedList() {
        size = 0;
        head = new ListNode(0);
        tail = new ListNode(0);
        head.next = tail;
        tail.prev = head;
    }
    public int get(int index) {
        ListNode cur = head;
        if(index > size - 1 || index < 0){
            return -1;
        }
        while(index >= 0){
            cur = cur.next;
            index--;
        }
        return cur.val;
    }
    
    public void addAtHead(int val) {
        addAtIndex(0,val);

    }
    
    public void addAtTail(int val) {
        addAtIndex(size,val);
    }
    
    public void addAtIndex(int index, int val) {
        if(index > size){
            return;
        }
        if(index < 0 ){
            index = 0;
        }
        size++;
        ListNode temp = new ListNode(val);
        ListNode cur = head;
        while(index > 0){
            cur = cur.next;
            index--;
        }
        temp.next = cur.next;
        cur.next = temp; 
        temp.prev = cur;
    }
    
    public void deleteAtIndex(int index) {
        ListNode cur = head;
        if(index > size - 1 || index < 0){
            return;
        }
        while(index > 0){
            cur = cur.next;
            index--;
        }
        cur.next = cur.next.next;
        size--;
    }
}
class ListNode {
    int val;
    ListNode next;
    ListNode prev;

    public ListNode(int val) {
        this.val = val;
    }
}

反转链表

206

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        // 方法一：在头结点不断插入
        // if(head == null){
        //     return head;//空节点不需要反转
        // }
        // ListNode temp = head.next;//临时节点前移一位
        // head.next = null;//代反转链表的头结点拆出来
        // ListNode newHead = head;//待反转链表的头结点赋给新的链表        
        // while(temp != null){
        //     head = temp;//找出待反转链表的新头结点
        //     temp = temp.next;//临时节点前移一位
        //     head.next = null;//待反转链表的新头拆出来
        //     head.next = newHead;//待反转链表的心头指向新的链表
        //     newHead = head;//得到新的链表的新头
        // }
        // return newHead;
        // 方法二：压栈，利用栈的先入后出
        // if(head == null){
        //     return head;
        // }
        // Stack stack = new Stack<>();
        // ListNode temp = head;
        // while(head != null){
        //     temp = head.next;
        //     head.next = null;
        //     stack.push(head);
        //     head = temp;
        // }
        // ListNode newHead = new ListNode();
        // temp = newHead;
        // while(!stack.isEmpty()){
        //     temp.next = stack.pop();
        //     temp = temp.next;
        // }
        // return newHead.next;
        // 方法三：递归
        return reverse(null, head);
        // 方法四：从后往前递归
        // if(head == null){
        //     return null;
        // }
        // if(head.next == null){
        //     return head;
        // }
        // ListNode newHead = reverseList(head.next);
        // head.next.next = head;
        // head.next = null;
        // return newHead;

    }
    public ListNode reverse(ListNode pre, ListNode cur){
        if(cur == null){
            return pre;
        }
        ListNode temp = cur.next;
        cur.next = pre;
        return reverse(cur,temp);
    }
}

两两交换链表中的节点

24

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        // 方法一：从前往后进行迭代
        // if(head == null){
        //     return null;
        // }
        // if(head.next == null){
        //     return head;
        // }
        // ListNode temp = head.next;//依次记录偶数节点的位置
        // head.next = head.next.next;//交换相邻的节点
        // temp.next = head;
        // temp.next.next = swapPairs(temp.next.next);//迭代交换下一个相邻的节点
        // return temp;
        // 方法二：双指针
        if(head == null){
            return null;
        }
        if(head.next == null){
            return head;
        }
        ListNode temp = head.next;
        ListNode pre = head.next;//记录新的头结点
        while(temp != null){
            head.next = head.next.next;//交换相邻的节点
            temp.next = head;
            if(head.next == null || head.next.next == null){
                break;
            }else{
                head = head.next;//指向下一个相邻节点的奇数节点
                temp.next.next = temp.next.next.next;//上一个相邻节点的偶数节点指向下一个节点的偶数节点
                temp = head.next;//下一个相邻节点的偶数节点
            }  
        }
        return pre;
    }
}

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

19

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 方法一：快慢指针，返回头结点说明head的头结点不能动，所以把链表的地址赋给另外一个对象
        // 添加虚拟头结点，方便操作。比如需要删除的是头结点的时候不需要单独考虑这种特殊情况
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;
        ListNode cur = dummyHead;
        ListNode temp = dummyHead; 
        for(int i = 0; i < n; i++){
            temp = temp.next;
        }
        while(temp.next != null){
            cur = cur.next;
            temp = temp.next;
        }
        cur.next = cur.next.next;
        return dummyHead.next;
    }
}

链表相交

02.07

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null){
            return null;
        }
        ListNode dummyHeadA = headA;
        int countA = 0;
        int countB = 0;
        ListNode dummyHeadB = headB;
        while(dummyHeadA.next != null){
            dummyHeadA = dummyHeadA.next;
            countA++;
        }
        while(dummyHeadB.next != null){
            dummyHeadB = dummyHeadB.next;
            countB++;
        }
        if(dummyHeadA != dummyHeadB){
            return null;//尾节点不相交则说明不相交
        }
        dummyHeadA = headA;
        dummyHeadB = headB;
        int index = (countA - countB) > 0 ? (countA - countB) : -(countA - countB);//两个链表的长度差
        for(int i = 0; i < index; i++){//让较长的链表先移动index位
            if((countA - countB) > 0){
                dummyHeadA = dummyHeadA.next;
            }else{
                dummyHeadB = dummyHeadB.next;
            }
        }
        while(dummyHeadA != dummyHeadB){//两个链表逐次向前移动，找出相交的第一个节点
            dummyHeadA = dummyHeadA.next;
            dummyHeadB = dummyHeadB.next;
        }
        return dummyHeadA;
    }
}

环形链表 II

142

/**
 * 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) {
        // O(1)空间的要求，所以不能用递归
        if(head == null){
            return null;
        }
        ListNode slowList = head;
        ListNode fastList = head;
        boolean flag = false;//判断是否有环
        while(fastList != null && fastList.next != null){
            fastList = fastList.next.next;
            slowList = slowList.next;
            if(fastList == slowList){
                flag = true;//有环
                break;
            }
        }
        if(!flag){//没有环
            return null;
        }else{//有环，找出环的入口，也就是索引的位置
            slowList = head;
            while(fastList != slowList){
                fastList = fastList.next;
                slowList = slowList.next;
            }
            return slowList;
        }
    }
}

哈希表：也叫散列表，用来快速判断一个元素是否出现在集合中，实际上是用空间换时间

有效的字母异位词

242

class Solution {
public boolean isAnagram(String s, String t) {
// 方法一：使用hashmap
// if(s.length() != t.length()){
// return false;
// }
// HashMap map = new HashMap<>();
// for(int i = 0; i < s.length(); i++){
// map.put(s.charAt(i), (map.getOrDefault(s.charAt(i), 0) + 1));
// }
// for(int i = 0; i < t.length(); i++){
// if(map.containsKey(t.charAt(i))){
// if(map.get(t.charAt(i)) == 1){
// map.remove(t.charAt(i));
// }else{
// map.put(t.charAt(i), (map.get(t.charAt(i)) - 1));
// }
// }else{
// return false;
// }
// }
// return true;
// 方法二：用数组来构造哈希表，字典解法
if(s.length() != t.length()){
return false;
}
int[] arr = new int[26];
for(int i = 0; i < s.length(); i++){
int index = s.charAt(i) - 'a';
arr[index] = arr[index] + 1;
}
for(int i = 0; i < t.length(); i++){
int index = t.charAt(i) - 'a';
if(arr[index] != 0){
arr[index] = arr[index] - 1;
}else{
return false;
}
}
return true;
}
}

两个数组的交集

349

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        // 使用hashset，无序，且不能存储重复数据，符合题目要求
        HashSet set = new HashSet<>();
        HashSet record = new HashSet<>();
        for(int i = 0; i < nums1.length; i++){
            set.add(nums1[i]);
        }
        for(int i = 0; i < nums2.length; i++){
            if(set.remove(nums2[i])){
                record.add(nums2[i]);
            }
        }
        return record.stream().mapToInt(x -> x).toArray();
    }
}

快乐数

202

class Solution {
    public boolean isHappy(int n) {
        // 使用hashset，当有重复的数字出现时，说明开始重复，这个数不是快乐数
        HashSet set = new HashSet();
        int sum = 0;
        while(true){
            while(n != 0){
                sum = sum + (n%10)*(n%10);
                n = n / 10;
            }
            if(sum == 1){
                return true;
            }
            if(!set.add(sum)){
                return false;
            }
            n = sum;
            sum = 0;
        }
    }
}

两数之和

1

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 方法一：暴力解法
        // int[] arr = new int[2];
        // for(int i = 0; i < nums.length - 1; i++){
        //     for(int j = i + 1 ; j < nums.length; j++){
        //         if(target == (nums[i] + nums[j])){
        //             return new int[]{i,j};
        //         }
        //     }
        // }
        // return new int[0];
        // 方法二：HashMap
        HashMap map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            int find = target - nums[i];
            if(map.containsKey(find)){
                return new int[]{i, map.get(find)};
            }else{
                map.put(nums[i],i);
            }
        }
        return null;
    }
}

四数相加 II

454

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        // 四个数，用哈希表，参考代码随想录
        HashMap map = new HashMap<>();
        int count = 0;
        for(int i : nums1){
            for(int j : nums2){
                int temp = i + j;
                if(map.containsKey(temp)){
                    map.put(temp, map.get(temp) + 1);
                }else{
                    map.put(temp, 1);
                }
            }
        }
        for(int i : nums3){
            for(int j : nums4){
                int temp = 0- (i + j);
                if(map.containsKey(temp)){
                    count += map.get(temp);
                }
            }
        }
        return count;
    }
}

赎金信

383

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        // 方法一；hashmap
        // HashMap map = new HashMap<>();
        // char temp;
        // for(int i = 0; i < ransomNote.length(); i++){
        //     temp = ransomNote.charAt(i);
        //     if(map.containsKey(temp)){
        //         map.put(temp, map.get(temp) + 1);
        //     }else{
        //         map.put(temp, 1);
        //     }
        // }
        // for(int i = 0; i < magazine.length(); i++){
        //     temp = magazine.charAt(i);
        //     if(map.containsKey(temp)){
        //         if(map.get(temp) == 1){
        //             map.remove(temp);
        //         }else{
        //             map.put(temp, map.get(temp) - 1);
        //         }
        //     }
        // }
        // if(map.isEmpty()){
        //     return true;
        // }else{
        //     return false;
        // }
        // 方法二：数组在哈希法的应用，比起方法一更加节省空间，因为字符串只有小写的英文字母组成
        int[] arr = new int[26];
        int temp;
        for(int i = 0; i < ransomNote.length(); i++){
            temp = ransomNote.charAt(i) - 'a';
            arr[temp] = arr[temp] + 1;
        }
        for(int i = 0; i < magazine.length(); i++){
            temp = magazine.charAt(i) - 'a';
            if(arr[temp] != 0){
                arr[temp] = arr[temp] - 1;
            }
        }
        for(int i = 0; i < arr.length; i++){
            if(arr[i] != 0){
                return false;
            }
        }
        return true;
    }
}

三数之和

15

class Solution {
    public List> threeSum(int[] nums) {
        // 如果考虑使用跟四数之和类似的求解方式，由于三元组是在同一个数组中寻找的，且要求不重复的三元组，因此求解会比较复杂
        // 题目要求返回的是三元组的具体数值，而不是索引值，因此可以考虑使用双指针
        List> list = new ArrayList>();
        for(int i=0;inums[j+1]){
					int temp = nums[j+1];
					nums[j+1] = nums[j];
					nums[j] = temp;
				}
			}
		}
        int leftNode;
        int rightNode;
        for(int i = 0; i < nums.length; i++){
            if (nums[i] > 0) {
                return list;
            }
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            leftNode = i + 1;
            rightNode = nums.length - 1;
            while(leftNode < rightNode){
                if((nums[i] + nums[leftNode] + nums[rightNode]) < 0){
                    leftNode++;
                }else if((nums[i] + nums[leftNode] + nums[rightNode]) > 0){
                    rightNode--;
                }else{
                    list.add(Arrays.asList(nums[i], nums[leftNode], nums[rightNode]));

                    while (rightNode > leftNode && nums[rightNode] == nums[rightNode - 1]) rightNode--;
                    while (rightNode > leftNode && nums[leftNode] == nums[leftNode + 1]) leftNode++;
                    
                    rightNode--; 
                    leftNode++;
                }
            }
        }
        return list;
    }
}

四数之和

18

class Solution {
    public List> fourSum(int[] nums, int target) {
        List> list = new ArrayList>();
        for(int i=0;inums[j+1]){
					int temp = nums[j+1];
					nums[j+1] = nums[j];
					nums[j] = temp;
				}
			}
		}
        for(int i = 0; i < nums.length; i++){
            if (nums[i] > 0 && nums[i] > target) {
                return list;
            }
            if(i > 0 && nums[i] == nums[i - 1]){
                continue;
            }
            for(int j = i + 1; j < nums.length; j++){
                if(j > i + 1 && nums[j] == nums[j - 1]){
                    continue;
                }
                int left = j + 1;
                int right = nums.length - 1;
                while(left < right){
                    long sum = (long)(nums[i] + nums[j] + nums[left] + nums[right]);
                    if(sum > target){
                        right--;
                    }else if(sum < target){
                        left++;
                    }else{
                        list.add(Arrays.asList(nums[i] , nums[j] , nums[left] , nums[right]));
                        while(left < right && nums[left] == nums[left + 1]){
                            left++;
                        }
                        while(left < right && nums[right] == nums[right - 1]){
                            right--;
                        }
                        left++;
                        right--;
                    }
                }
            }
        }
        return list;
    }
}