Leetcode做题记录----2

1、两数之和

思路：

1、不能使用相同元素，可以想到哈希表，，C#中可以通过字典建立当前值和下标的关系

2、显然，依次判断数组中的每个数即可

3、定义other == target - num[ i ] 这个other就是我们用于在字典中进行寻找的另一个元素

    public class Solution{public int[] TwoSum(int[] nums, int target){//Array.Sort(nums);//for (int i = 0; i < nums.Length; i++)//{//    for (int j = i + 1; j < nums.Length; j++)//    {//        if (nums[i] + nums[j] == target)//        {//            return new int[] { i, j };//        }//    }//}//return new int[0];//利用字典Dictionary<int,int> dic = new Dictionary<int,int>();for (int i = 0; i < nums.Length; i++){//目标元素 我们设目标元素为b 则另一个元素为aint other = target - nums[i];//如果找到目标元素 直接返回目标元素的位置 和当前的第一个元素的位置if (dic.ContainsKey(other)){return new int[]{dic[other],i};}//如果当前字典中没有第一个元素 即a 就将它添加至字典中if (!dic.ContainsKey(nums[i])){dic.Add(nums[i],i);}}return new int[0];}}

注释的部分是用双重循环写的，时间复杂度会高，所以不用，本体应该也可以使用双指针的方法。

1929、数组串联

思路：

最简单的方式就是，直接创建一个新的数组，为原数组的二倍，然后用一个for循环直接加进去就行。

代码：

        public class Solution{public int[] GetConcatenation(int[] nums){int[] ans = new int[nums.Length*2];for (int i = 0; i < nums.Length; i++){ans[i] = nums[i];ans[i + nums.Length] = nums[i];}return ans;}}

206、反转链表

思路：

1、本体给的是一个单向链表，也就是只存值和指向下一个位置，所以本体思路将指向性反转即：从1->2->3->4->5到 1<-2-<3-<4-<5 最后返回头结点5就行了

2.如此我们可以想到先把当前节点的下一个（current.next）拿出来先存为next，然后这个位置是不是就可以随便处理了，于是乎，我们就设置一个前置指针pre用来移位，于是继续的操作就是将pre =current,在这步之前得将pre的值先用了，不然就会因为修改而混乱，即current.next = pre;,最开始时pre可以设置为null，然后就是移动到下一个节点

代码：

    public class ListNode{public int val;public ListNode next;public ListNode(int val = 0, ListNode next = null){this.val = val;this.next = next;}}public class Solution{public ListNode ReverseList(ListNode head){ListNode pre = null;ListNode current = head;while (current != null){ListNode next = current.next;current.next = pre;pre = current;current = next;}return pre;}}

237、删除链表中节点的节点

思路：

1、链表中怎么删除节点？很简单将当前节点的下一个跳过下一个不就删除了下一个节点吗，即current.next = current.next.next;

2、仔细读题可以发现，题目要求的是删除当前节点，那很简单了，就是按照1所说的换节点和值

public class Solution {public void DeleteNode(ListNode node) {node.val = node.next.val;node.next = node.next.next;}
}

19删除链表中的倒数第N个节点

思路：

1、可以先确定倒数第N个节点的前一个节点，然后将这个节点的next设置为倒数第N节点的下一个节点即可，那么怎么寻找呢，可以用个计数器进行寻找，但是这里可以用双指针定位的方式，即我先将一个快指针移动N+1次，然后在同时移动慢指针和快指针，那么此时两个指针同时移动，必然当快指针移动到最后一个时候，慢指针将会指向的是倒数N+1个位置，即我们寻找的倒数第N个节点的前一个。

2、在整个过程中，我们必须得维护初始的头结点，不然后面就找不到了，可以用虚拟节点的方式，最开始将虚拟节点的下一个指向头结点，就像一个路牌指向了一条公路，在公路上头结点这辆汽车将会奔驰，初始将快慢指针都赋予虚拟节点。

代码：

    public class Solution{public ListNode RemoveNthFromEnd(ListNode head, int n){ListNode dummy = new ListNode();dummy.next = head;ListNode slow = dummy;//用于找到倒数N+1ListNode fast = dummy;//用于定位for (int i = 0; i <= n; i++){//不断跑跑跑fast = fast.next;}while (fast != null){fast = fast.next;slow = slow.next;}slow.next = slow.next.next;return dummy.next;}}