给定一个数组 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:
输入: "{[]}"输出: truepublic 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就可以实现了。