读一读

给定一个数组 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就可以实现了。