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指针指向为jwhile (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的路，所以第二圈一定会相遇。