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 则另一个元素为a
                int 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+1
            ListNode 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;
        }
    }