给定一个数组 nums 和一个值 val,你需要原地移除所有数值等于 val 的元素,返回移除后数组的新长度。
不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。
public int RemoveElement(int[] nums, int val) { if(nums == null || nums.Length == 0) return 0; int index = 0; for(int i = 0;i<nums.Length;i++) { if(nums[i] != val) { nums[index++] = nums[i]; } } return index; }
给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。
不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例 1: 给定数组 nums = [1,1,2], 函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 你不需要考虑数组中超出新长度后面的元素。
public int RemoveDuplicates(int[] nums) { if(nums == null || nums.Length == 0) return 0; int index = 0; for(int i = 1;i<nums.Length;i++) { if(nums[i] != nums[index]) { nums[++index] = nums[i]; } } return index+1; }
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 ""。
示例 1: 输入: ["flower","flow","flight"]输出: "fl" 示例 2: 输入: ["dog","racecar","car"]输出: ""解释: 输入不存在公共前缀。
public string LongestCommonPrefix(string[] strs) { if(strs == null || strs.Length == 0) return ""; if(strs.Length == 1) return strs[0]; //找一个最短的长度的str int minLen = int.MaxValue; for(int i = 0;i<strs.Length;i++) { if(minLen > strs[i].Length) { minLen = strs[i].Length; } } int resLen = 0; for(int i = 0;i < minLen; i++) { for(int j = 0;j<strs.Length-1;j++) { if(strs[j][i] != strs[j+1][i]) { i = minLen; resLen--;//一下子跳不出,下面的++会执行,所以这里--矫正 break; } } resLen++; } return strs[0].Substring(0,resLen); }
给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
有效字符串需满足:左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。
示例 1: 输入: "()"输出: true 示例 2: 输入: "()[]{}"输出: true 示例 3: 输入: "(]"输出: false 示例 4: 输入: "([)]"输出: false 示例 5: 输入: "{[]}"输出: true
public bool IsValid(string s) { if(s == null) return true; Stack<char> stack = new Stack<char>(); char temp; for(int i = 0;i < s.Length;i++) { switch(s[i]) { case '(': stack.Push(')'); break; case '[': stack.Push(']'); break; case '{': stack.Push('}'); break; default: if(0 == stack.Count) return false; temp = stack.Pop(); if(temp != s[i]) return false; break; } } return 0 == stack.Count; }
利用栈来解决应该是没有异议的了。逻辑简单,但是需要注意细节的处理,一种是出现右边符号多的情况,栈是会为空的。一种是左边的多,右边的匹配了但是没有匹配完。
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例:
输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4
/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int x) { val = x; } * } */ public class Solution { public ListNode MergeTwoLists(ListNode l1, ListNode l2) { ListNode head = new ListNode(0); ListNode temp = head; while(l1 != null && l2 != null) { if(l1.val < l2.val) { temp.next = l1; temp = l1; l1 = l1.next; } else{ temp.next = l2; temp = l2; l2 = l2.next; } } if(l1 == null) { temp.next = l2; } if(l2 == null) { temp.next = l1; } return head.next; } }
根据题意是生成一个新的有序链表,使用原来两个链表的节点拼接而成的哈,本来我是傻傻的new个全新的啊,天啊,我真是个人才题都不看完!写了个很常规的,思想和合并排序差不多就注释也不写了。
后来看到一个很好的递归实现,简洁明了。
/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int x) { val = x; } * } */ public class Solution { public ListNode MergeTwoLists(ListNode l1, ListNode l2) { if(l1 == null) return l2; if(l2 == null) return l1; if(l1.val < l2.val) { l1.next = MergeTwoLists(l1.next,l2); return l1; } else { l2.next = MergeTwoLists(l1,l2.next); return l2; } } }
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。
请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n))。
示例 1:
nums1 = [1, 3] nums2 = [2] 中位数是 2.0
示例 2:
nums1 = [1, 2] nums2 = [3, 4] 中位数是 (2 + 3)/2 = 2.5
public double FindMedianSortedArrays(int[] nums1, int[] nums2) { int m = nums1.Length; int n = nums2.Length; if(m>n){ //保证m<=n int[] temp = nums1; nums1 = nums2;nums2 = temp; int t = m; m = n; n = t; } int iMin = 0; int iMax = m;//只需要在小的一个数组中寻找i int halfLen = (m + n + 1) / 2;//根据公式,用来计算j while(iMin <= iMax) { int i = (iMax + iMin) / 2; //2分法 int j = halfLen - i; //计算出对应的j if(i < iMax && nums2[j-1] > nums1[i]) { iMin = i+1; //数组1的i位置的值小了,数组2的j-1应该小于=数组1的i }else if(i > iMin && nums1[i-1] > nums2[j]) { iMax = i-1; //数组1的i位置的值大了,数组1的i-1应该小于=数组2的j }else { //这个位置很合适了,求左边的最大值,注意特殊情况 int maxLeft = 0; if(i == 0){ maxLeft = nums2[j-1]; }else if(j == 0) { maxLeft = nums1[i-1]; }else{ maxLeft = Math.Max(nums1[i-1],nums2[j-1]); } //奇数的话,直接返回左边最大,前面计算i和j会保证左边元素多1 if((m+n)%2 == 1) return maxLeft; //计算右边的最小 int minRight = 0; if(i == m) { minRight = nums2[j]; }else if(j == n) { minRight = nums1[i]; }else { minRight = Math.Min(nums2[j],nums1[i]); } return (maxLeft + minRight)/2f; } } return 0.0; }
在两个有序的数组中找中位数,中位数是什么,就是可以把一段有序数组分成两段,右边那一段比前面那一段都大。那么就可以想,将有序数组1用i分成两半,同样的将有序数组2用j分成两半,数组1的i和i的右边跟数组2的j和j的右边合并,使他们的个数和左边合并的相同或则少一个,同时合成的右边全都比左边的大,那么在相同个数的情况下,中位数就=(左边最大+右边最小)/2,在左边个数比较多的情况下,中位数就=左边最大。
所以寻找i和j的时候需要保证两个条件,1.左边比右边的个数相同或则多一个。2.数组2第j位大于数组1第i-1位,数组1第i位大于数组2第j-1位,因为i和j是在右边数组,所以一定得保证比它本身上一个元素大。
如果按照这样子区分后,左边最大不是数组1的i-1就是数组2的j-1,而右边最大不是数组1的i就是数组2的j。
时间复杂度是:O(log(min(n,m)))
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。你可以假设数组中无重复元素。
示例 1: 输入: [1,3,5,6], 5输出: 2 示例 2: 输入: [1,3,5,6], 2输出: 1 示例 3: 输入: [1,3,5,6], 7输出: 4 示例 4: 输入: [1,3,5,6], 0输出: 0
public int SearchInsert(int[] nums, int target) { if(nums == null || nums.Length == 0) return 0; int start = 0; int end = nums.Length - 1; int result = -1; int tempIndex = -1; while(start <= end) { //二分法查找位置 tempIndex = (end + start)/2; if(nums[tempIndex] == target) { return tempIndex;//找到匹配 } if(target > nums[tempIndex]) { //去右边那半 start = tempIndex + 1; } else { //去左边那半 end = tempIndex - 1; } } //没找到匹配就是start了 return start; }
看似简单,其实要考虑很多情况的,start是一个往上加的指标,而目的是找一个刚好比target大的值或者是数组尾部的下一位的位置,在两指标重合时,无论是比target值大的end--,还是比target值小的start++,start值总是那个比target大的指标。所以,最后没找到的情况下,返回start指标就是要插入的位置。
罗马数字包含以下七种字符:I, V, X, L,C,D 和 M。
字符 数值I 1 V 5 X 10 L 50 C 100 D 500 M 1000
例如, 罗马数字 2 写做 II ,即为两个并列的 1。12 写做 XII ,即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。 通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII,而是 IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况: I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。 X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。 C 可以放在 D (500) 和 M (1000) 的左边,来表示 400 和 900。 给定一个罗马数字,将其转换成整数。输入确保在 1 到 3999 的范围内。 示例 1: 输入: "III"输出: 3 示例 2: 输入: "IV"输出: 4 示例 3: 输入: "IX"输出: 9 示例 4: 输入: "LVIII"输出: 58解释: C = 100, L = 50, XXX = 30, III = 3. 示例 5: 输入: "MCMXCIV"输出: 1994解释: M = 1000, CM = 900, XC = 90, IV = 4.
public int RomanToInt(string s) { //建立一个哈希映射 Dictionary<char,int> map = new Dictionary<char,int>(); map.Add('I',1); map.Add('V',5); map.Add('X',10); map.Add('L',50); map.Add('C',100); map.Add('D',500); map.Add('M',1000); int res = 0; int pre = map['M'];//除数不能为0,且要初始化大一点跳过初始化值的特殊检查 for(int i = 0;i < s.Length; i++) { res += map[s[i]];//先加上去,如果是特殊值减两份就好了 if(map[s[i]] > pre && (map[s[i]]/pre <= 10)) { //检查到特殊,减去两份该值 res -= 2 * pre; } pre = map[s[i]];//设置上一个数 } return res; }
根据观察发现,特殊的罗马数字都是右边的大于左边的,且右边的除以左边的数后不是5就是10,也就是小于或等于10。用一个数记录上一个值,这样就可以判断是否是特殊值了,再减去两份的上一个值就行了。
判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。
示例 1: 输入: 121输出: true 示例 2: 输入: -121输出: false解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。 示例 3: 输入: 10输出: false解释: 从右向左读, 为 01 。因此它不是一个回文数。
public bool IsPalindrome(int x) { //负数不可能是回文数,除了0之外,个位数带0的都不可能是回文数,反转少了一位 if(x < 0 || (x % 10 == 0 && x != 0)) return false; int res = 0; while(res < x) { //只需要折半检查元素,回文数本身,左边就等于右边(偶数的情况,奇数的话不要中间的值) res = res * 10 + x % 10; x /= 10; } //偶数或奇数位数,奇数的话舍弃最后一位 return x == res || x == res/10; }
一开始我的想法就是直接反转整个整数,然后和原来的值作对比,代码一次过,结果看了下击败21%,就知道肯定有其他办法了(我这水B,都不仔细想想就做)。根据回文数的特性,只需要做一半的处理就行了,没必要反转整个数,效率直接提升了一半。
给定一个 32 位有符号整数,将整数中的数字进行反转。
示例 1: 输入: 123输出: 321 示例 2: 输入: -123输出: -321 示例 3: 输入: 120输出: 21
注意:
假设我们的环境只能存储 32 位有符号整数,其数值范围是 [−231, 231 − 1]。根据这个假设,如果反转后的整数溢出,则返回 0。
public int Reverse(int x) { int sign = (x < 0)?-1:1;//取符号啦 //转为负数来处理,因为abs后负数的范围比正数大1,转整数就有可能溢出啦 x *= -sign; int temp = x; Int64 tempRes = 0;//用一个更大范围的来计算结果和判断 //计算最大值偏移,负数的范围大1,正数的话就0 int offset = (int)Math.Round(sign/2f-0.5f); while(x < 0) { temp = x % 10; tempRes = tempRes * 10 + temp; //判断是否溢出,加上偏移 if(tempRes < -int.MaxValue + offset) return 0; x /= 10; } //前面有溢出判断了,这里大胆转,并进行原符号的恢复 return (int)tempRes * -sign; }
-1代表负数,1代表正数,同一转化为abs后范围比较大的负数(乘于-sign,事后再乘于-sign就可以恢复符号),范围判断时,使用-int.MaxValue进行判断,需要注意负数的范围时比它小一的,整数不变,所以需要将符号sign映射出一个偏移offset来,通过简单的除2减0.5就可以实现了。