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节点
//记录下他的下一个即next
ListNode 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)
{
//注意是先移动了已经存好的数组的下标
//因为下一个元素为0
nextNonZero++;
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;
}
}