Leetcode做题记录----3

1474、删除链表M个节点之后的N个节点

思路：

1、两个循环解决问题 第一个循环移动M个位置，第二个循环确定移动N个位置后的，然后将M位置的节点的next指向，N位置后的节点即可

2、注意边界条件和判空处理

代码实现：

    public class Solution{public ListNode DeleteNodes(ListNode head, int m, int n){//定义一个虚拟头结点 也叫哑节点//后面我们直接用这个dummy就不会担心找不到头结点了ListNode dummy = new ListNode();dummy.next = head;ListNode curr = dummy;while (curr != null){if(curr==null)break;//往后移动M个位置for (int i = 0; i < m &&curr!=null; i++){curr = curr.next;}//此时的current就是M节点//记录下他的下一个即nextListNode delStartNode = curr.next;//这里是用来寻找到移动N个节点后的//注意不能用Current这个后面还会利用的 不要破坏for (int i = 0; i < n &&delStartNode!=null; i++){delStartNode = delStartNode.next;}//赋过来就是删除了curr.next = delStartNode;}//最后返回头结点return dummy.next;}}

2011、执行操作后的变量值 

思路：

遍历字符串数组，比较每一个字符串的含义，然后利用条件分支语句执行即可

代码

    public class Solution{public int FinalValueAfterOperations(string[] operations){int res = 0;for (int i = 0; i < operations.Length; i++){switch (operations[i]){case "X++":case "++X":res += 1;break;case "X--":case "--X":res -= 1;break;default:break;}}return res;}}

202、快乐数

思路：

1、想办法获取到每个位置上的数字，怎么获取呢，首先我们是从右边开始获取数字的，所以用%10获取最后一位数字，然后使用/10就将整体减少了最后一位数字，就可以得到每个位置上的数字了

2、看到循环和一个固定的结果，我们就要想到，利用快慢指针进行算法的实现，当快指针和慢指针汇合时或者快指针为1，则说明题目已经完成了。

2160、拆分数位后四位数字的最小和 

思路：这道题很简单，将获得的整数，通过/10和%10获得每一位，然后通过排序就行了 

public class Solution {public int MinimumSum(int num) {string s = num.ToString();char[] chars = s.ToCharArray();//对于字符数组进行排序Array.Sort(chars);//强转为整型int n1 = int.Parse (chars[0].ToString());int n2 = int.Parse (chars[1].ToString());int n3 = int.Parse (chars[2].ToString());int n4 = int.Parse(chars[3].ToString());//计算得出结果return (n1 + n2)*10 + (n3+n4);}
}

2520、统计能整除数字的位数 

 

思路：这个也很简单，通过不断的%10找尾数，然后再让自身去除，看能否整除，能的话，计数器就加一，不能就直接进入下一轮。要注意一下输入的输入的情况，可能他输入个0整你

代码实现： 

public static int CountDigits(int num)
{if(num ==0)return 0;//计数器int counter = 0;while (num > 0){int last = num % 10;if (last == 0) continue;if (num % last == 0){counter++;}num /= 10;}return counter;
}

496、下一个更大元素

思路：

先对nums2进行预处理， 构建一个严格单调递减栈，然后将 每个“对”存到一个字典中，处理完之后，如果栈中还有剩余元素，就按照题目要求，配置他的另一半为-1.然后在遍历nums1,寻找字典中的键，然后返回结果。

代码：

    public class Solution{public int[] NextGreaterElement(int[] nums1, int[] nums2){//构建单调栈Stack<int> stack = new Stack<int>();//创建字典 用于存当前元素后面的第一个比自己的元素Dictionary<int ,int> nextGreater = new Dictionary<int ,int>();//遍历nums2预处理foreach (var num in nums2){//只要栈不为空，当前栈顶的元素小于下一个元素就直接加入字典//那么就是(当前元素，当前元素的下一个更大值)while (stack.Count != 0 && stack.Peek() < num){nextGreater[stack.Pop()] = num;}//反之压入stack.Push(num);}while (stack.Count != 0){//处理栈中剩余的元素nextGreater[stack.Pop()] = -1;}//结果数组int[] res = new int[nums1.Length];for (int i = 0; i < nums1.Length; i++){res[i] = nextGreater[nums1[i]];}return res;}}

633、平方数之和

思路：双指针思路，一个指针指向0，一个指针指向sqrt(c)。然后二者的平方和如果小于c那么a++，反之b--

代码： 

    public class Solution{public bool JudgeSquareSum(int c){int a = 0;int b =(int)Math.Sqrt(c);while (a <= b){int sum = a * a + b * b;if (sum == c)return true;else if (sum < c){a++;}else if (sum > c){b--;}}return false;//for (int a = 0; a < Math.Sqrt(c); a++)//{//    for (int b = (int)Math.Sqrt(c); b > a; b++)//    {//        if(b*b + a*a == c*c)//            return true;//    }//}//return false;}}

注释的部分是会超时算法

520、检测大写字母

思路：

分析题目，无非三种正常情况。

首字母大写后面小写，全部大写，全部小写。那么是不是可以这样想，只有首字母小写加第二个字母大写是不合理的，但是只要后续字母和第一个字母是状态相同的话，是不是就是一个正确的单词组合。

代码：

    public class Solution{public bool DetectCapitalUse(string word){//return (word == word.ToUpper())|| (word == word.ToLower())//    || (char.IsUpper(word[0]) && (word.Substring(1).ToLower() == word.Substring(1)));if (word.Length >= 2 && (word[0] == char.ToLower(word[0])) && (word[1] == char.ToUpper(word[1]))){return false;}for (int i = 2; i < word.Length; i++){if (char.IsLower(word[i]) ^ char.IsLower(word[1])){return false;}}return true;}}

二分查找

思路：

典型的二分查找，设置两个指针，一个指向最左边，一个指向最右边，然后从中间开始查找，注意这里会有左闭右闭，和左闭右开的两种写法。
左闭右闭：说明左右都可以取到，那么循环条件就是左边<=右边，然后里面就是正常的，目标值大于中间值，就左边界移动为mid+,反之右边界为mid-1.

左闭右开：那么说明取不到右边，则循环条件为左边界<右边界，里面就是左边等于mid+1，右边界变化就是直接为mid即可

本道题的代码实现：

    public class Solution{public int Search(int[] nums, int target){int left = 0;int right = nums.Length - 1;while (left <= right){int mid  = left + (right - left) / 2;if (nums[mid] < target){left = mid + 1;}else if (nums[mid] > target) {right = mid - 1;}else return nums[mid];}return -1;}}

另外两种写法

//左闭右闭
public class Solution
{public int Search(int[] nums, int target){int left = 0;int right = nums.Length - 1;while (left <= right){int mid = (right - left) / 2 + left;if (nums[mid] == target){return mid;}else if (nums[mid] < target){left = mid + 1;}else if (nums[mid] > target){right = mid - 1;}}return -1;}
}//左闭右开
public class Solution
{public int Search(int[] nums, int target){int left = 0;int right = nums.Length;while (left < right){int mid = (right - left) / 2 + left;if (nums[mid] == target){return mid;}else if (nums[mid] < target){left = mid + 1;}else if (nums[mid] > target){right = mid;}}return -1;}
}

和二分查找类似的相关题目：

34、在排序数组中查找元素的第一个和最后一个位置

思路：先找到左边界，然后重新设置右边界。同样是利用二分查找的方式寻找左边界。经过二分查找后，那么最左边的下标一定就是目标值所在的位置，如果这个位置的元素和目标元素不一样的话，那么就不存在这个目标元素。

代码实现：

    public class Solution{public int[] SearchRange(int[] nums, int target){int left = 0;int right = nums.Length - 1;//定义结果数组int[] result = new int[] { -1, -1 };//如果为空直接返回if(nums.Length==0) return result;//为什么是<呢，因为这是一个区间就算为一也不能左右相等，因为不是同一个while (left < right){//防止溢出int mid = left + (right - left) / 2;//设置左边界if (nums[mid] < target) left = mid + 1;//设置右边界else right = mid;}if (nums[left]!=target) return result;result[0] = left;//重置 开始找右边界right = nums.Length - 1;while (left < right){int mid = left + (right - left +1) / 2;if(nums[mid] > target) right = mid - 1;else left = mid;}//装结果result[1] = right;return result;}}

34、在排序数组中查找元素的第一个和最后一个位置

    public class Solution{public int[] SearchRange(int[] nums, int target){int left = 0;int right = nums.Length - 1;//定义结果数组int[] result = new int[] { -1, -1 };//如果为空直接返回if(nums.Length==0) return result;//为什么是<呢，因为这是一个区间就算为一也不能左右相等，因为不是同一个while (left < right){//防止溢出int mid = left + (right - left) / 2;//设置左边界if (nums[mid] < target) left = mid + 1;//设置右边界else right = mid;}if (nums[left]!=target) return result;result[0] = left;//重置 开始找右边界right = nums.Length - 1;while (left < right){int mid = left + (right - left +1) / 2;if(nums[mid] > target) right = mid - 1;else left = mid;}//装结果result[1] = right;return result;}}

35、搜索插入位置

思路：继续二分查找即可，这个是左闭右闭的区间。

public class Solution {public int SearchInsert(int[] nums, int target) {int left = 0;int right = nums.Length - 1;while (left <= right){int mid = left + (right - left)/2;if (nums[mid] < target){left = mid + 1;}else if (nums[mid] > target){right = mid - 1;}else return mid;}return left;}
}

69、x的平方根

思路：同理继续二分查找就行，只不过注意的是最后的结果是mid.

代码实现：

    public class Solution{public int MySqrt(int x){int left = 1;int right = x;while (left <= right){int mid = left + (right - left) / 2;if (mid > x / mid) right = mid - 1;else left = mid + 1;}return left - 1;}}

367、有效的完全平方数

思路：这道题得单独的将0和1拿出来考虑，这样会比较的方便处理。然后就是可能会数据溢出，所以得拿个大的容器去装我们的mid*mid，然后如果大于num的话，就需要进行左移，那么就是改变有边界。小于的话，就需要右移，那么就改左边界。

代码实现：

    public class Solution{public bool IsPerfectSquare(int num){long left = 1;long right = num;if(num == 0||num==1) return true;while (left <= right){long mid = (left + right) / 2;long square = mid * mid;if(square==num) return true;else if(square<num) left = mid +1;else right = mid - 1;}return false;}}

双指针

26删除有序数组中的重复项

思路：定义一个指针用来进行维护答案的数组，然后另外一个指针负责移动，然后在移动的时候，注意题目条件的处理，即可得解。

    public class Solution{public int RemoveDuplicates(int[] nums){//判空if(nums.Length==0) return 0;//维护的数组下标int netIndex = 0;for (int i = 1; i < nums.Length; i++){//如果当前元素还没有出现过 就加进来//如果当前元素已经出现过，那么 一个指针一直往后移动//直到遇到下一个没有出现过的元素//然后将这个新元素 赋值到维护数组的下一个位置if (nums[i] != nums[netIndex]){netIndex++;nums[netIndex] = nums[i];}}//你维护的是数组的下标//返回的是长度return netIndex + 1;}}

27、移除元素

思路和上题目一样：

代码实现：

public class Solution {public int RemoveElement(int[] nums, int val) {int slow = 0;for (int i = 0; i < nums.Length; i++){if (nums[i] != val){nums[slow++] = nums[i];}}return slow;}
}

283、移动零

思路：先把不为零的数字往前移动，一个贴一个，最后补0即可

代码实现：

    public class Solution{public void MoveZeroes(int[] nums){int nextNonZero = 0;//移位for (int i = 0; i < nums.Length; i++){if (nums[i] != 0){//注意是先移动了已经存好的数组的下标//因为下一个元素为0nextNonZero++;nums[nextNonZero] = nums[i];}}//补零for (int i = nextNonZero; i < nums.Length; i++){nums[i] = 0;}}}

977、有序数组的平方

思路：

①全部平方完以后，排序得解。

②利用双指针，因为这个数组本就是一个有序数组，那么平方一定是两侧的最大，你可以反复比较左右的元素的平方，然后你再加到你的结果数组中去就行

代码实现：

public class Solution {public int[] SortedSquares(int[] nums) {int[] result = new int[nums.Length];int k =nums.Length-1;for (int i = 0, j = nums.Length - 1; i <= j;){if (nums[i] * nums[i] > nums[j] * nums[j]){result[k] = nums[i] *nums[i];i++;k--;}else{result[k] = nums[j] *nums[j];j--;k--;}}return result;}
}

844、比较含空格的字符串

思路：注意其中一个指针的移动位置就好。

代码实现：

    public class Solution{public bool BackspaceCompare(string s, string t){int kongge_1 = 0;int kongge_2 = 0;char[] schars = s.ToCharArray();char[] tchars = t.ToCharArray();foreach (char c in schars){if (c != '#'){schars[kongge_1] = c;kongge_1++;}else{if(kongge_1 > 0)kongge_1--;}}foreach(char c in tchars){if (c != '#'){tchars[kongge_2] = c;kongge_2++;}else{if (kongge_2 > 0)kongge_2--;}}if(kongge_1-kongge_2!=0)return false;for (int i = 0; i < kongge_2; i++){if (schars[i] != tchars[i]) return false;}return true;}}