Leetcode日记

1.两数之和

暴力法：

    public int[] twoSum(int[] nums, int target) {
        //遍历数组
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    int[] result = {i, j};
                    return result;
                }
            }
        }
        return null;
    }

利用hashmap

hashmap的算法使用特性就在于其对数组的特殊处理，数组有下标和value值，而hashmap有键值对，正好可以同时存储数组的下标与值。

优势体现在哪里？

显然优势体现在hashmap的随机存取。

同样的事讲数组替换为hashmap，时间复杂度能够提升。

    public int[] twoSum2(int[] nums, int target) {
        //遍历数组
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        for (int i = 0; i < nums.length; i++) {
            if (map.get(target-nums[i])!=null) {
                return new int[]{i,map.get(target-nums[i])};
            }
        }
        return null;
    }

简单来讲，我们遍历一次数组，让target去与数组中的值nums[i]做减法，然后我们去hashmap利用其随机存取的特性，以O(1)的时间复杂度判断是否存在与target-nums[i]的值，从而减少了时间复杂度

2.移动零

数据结构为线性表

算法思想：双指针，i找到第一个为零的数，j找到i右边第一个不为零的数，交换。

class Solution {
    public void moveZeroes(int[] nums) {
        int i = 0;
        int j = 1;
        int temp;
        //算法思想：找到nums[i]等于0，并且nums[j]!=0的情况，两者交换，并将i指针指向为j
        while (i < nums.length - 1) {
            if (j==nums.length) break;
            if (nums[i] == 0) {
                j = i + 1;
                while (j <= nums.length - 1) {
                    if (nums[j] == 0) j++;
                    else {
                        temp = nums[i];
                        nums[i] = nums[j];
                        nums[j] = temp;
                        i++;
                        break;
                    }
                }
            }
            else i++;
        }
    }
}

3.相交链表

/**
 * 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 i = headA;
        ListNode j = headB;
        //成功条件为两者的尾指针指向节点相同
        while (true) {
            if (i == j) return i;
            if (i.next == null && j.next == null) return null;
            if (i.next == null) i = headB;
            else i = i.next;
            if (j.next == null) j = headA;
            else j = j.next;
        }
    }
}

算法思想就是让A、B同步走，当遍历A指针的下个节点为空时，让遍历指针指向B，当遍历B指针的下个节点为空时，让遍历指针指向A。

当AB指针内容相同时，返回该节点，当A与B的下个指针都为null时返回null

这道题简单讲就是不在第一轮（A从头走到尾）去判断，因为长度不同，AB每次走的路径大小也相同，所以始终无法相遇，但在第二圈的时候，A会去走B的路，B会去走A的路，所以第二圈一定会相遇。