读一读

给定两个大小为 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;
    int i = 0;
    int j = 0;
    int index = 0;
    int[] datas = new int[m+n];

    //合并排序
    while(i<m && j<n)
    {
        if(nums1[i] < nums2[j])
        {
            datas[index++] = nums1[i++];
        }
        else
        {
            datas[index++] = nums2[j++];
        }
    }

    //填充剩下的
    while(j<n)
    {
        datas[index++] = nums2[j++];
    }

    while(i<m)
    {
        datas[index++] = nums1[i++];
    }

    int mid = (m+n)/2;
    int offset = (m+n)%2;
    if(offset == 0)
    {
        return (datas[mid]+datas[mid-1])/2.0f;
    }else
    {
        return datas[mid];
    }
}


使用合并排序的方式,将两个数组合并排序到一个数组中,然后判断长度为偶数就取中间两个的平均数,为奇数就去取中间那位。时间复杂度应该是O(n)或O(m),空间复杂度是O(m+n)。还有更优的解法。


给定一个字符串,找出不含有重复字符的最长子串的长度。

示例:

给定 "abcabcbb" ,没有重复字符的最长子串是 "abc" ,那么长度就是3。

给定 "bbbbb" ,最长的子串就是 "b" ,长度是1。

给定 "pwwkew" ,最长子串是 "wke" ,长度是3。请注意答案必须是一个子串,"pwke" 是 子序列,而不是子串。

public int LengthOfLongestSubstring(string s) {
    if(s == null || s == "") return 0;//安全检测
    int lLength = 0;
    int tempLength = 0;

    Dictionary<char,int> dic = new Dictionary<char,int>();//记录字串中是否有重复
    for(int i = 0;i<s.Length;i++)
    {
        if(dic.ContainsKey(s[i]))
        {
            //有重复的情况
            if(tempLength > lLength)
            {
                lLength = tempLength;//赋予新长度
            }
            tempLength = i - dic[s[i]];//这个是重点,遗弃重复字符及前面的长度
            Dictionary<char,int> nDic = new Dictionary<char,int>();
            for(int j = dic[s[i]]+1;j<=i;j++)
            {
                //保留 重复字符间 的字符在字典中
                nDic.Add(s[j],j);
            }
            dic = nDic;
        }else{
            //无重复,直接加
            dic.Add(s[i],i);
            tempLength++;
        }
    }

    //一路绿灯无重复的情况
    if(tempLength > lLength)
    {
        lLength = tempLength;
    }

    return lLength;
}


这段代码写了挺快的,因为之前就看过思路,睡觉前也构思过了。但是无可避免的还是要提交很多次才能通过。

哈希字典主要记录当前字串的字符和每个字符的位置,当发现重复的时候,很容易得到两个重复字符的下标,两个下标相减就是遗弃重复字符前面后的字串长度了。

例如:abcabcbb,bcab,两个b为1和4,那么4-1=3,刚好为cab字串的长度3


给定两个非空链表来表示两个非负整数。位数按照逆序方式存储,它们的每个节点只存储单个数字。将两数相加返回一个新的链表。

你可以假设除了数字 0 之外,这两个数字都不会以零开头。

示例:

输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8 
原因:342 + 465 = 807
/**
 * 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 AddTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);//生成一个头结点的做法,省去了是否是第一节点的判断
        ListNode tempNode = head;
        int upVal = 0;
        int temp = 0;
        while(l1 != null || l2 != null || upVal != 0)//5+5的情况,所以就算两链表为空,进位不为空也要继续
        {
            temp = (l1==null?0:l1.val) + (l2==null?0:l2.val) + upVal;
            tempNode.next = new ListNode(temp%10);//取个位数
            upVal = temp/10;//读取出进位
            tempNode = tempNode.next;
            
            l1 = (l1==null?null:l1.next);
            l2 = (l2==null?null:l2.next);
        }
        
        return head.next;//头结点的第一个结点就是真第一节点了
    }
}

在一个数组中,寻找两个数的和等于目标值。

例如:[2,7,8,6] 目标值为9 那么输出[0,1]

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        Dictionary<int,int> dic = new Dictionary<int,int>();//空间换时间
        for(int i = 0;i<nums.Length;i++)
        {
            int complement = target - nums[i];//通过计算获取另外一个的Key值
            if(dic.ContainsKey(complement))
            {
                return new int[]{dic[complement],i};//得到索引
            }
            
            if(!dic.ContainsKey(nums[i]))
                dic.Add(nums[i],i);//缓存到哈希表中
        }
        
        return null;
    }
}


缓存一个使用值作为Key的哈希表,这样就可以通过目标值和一个加值获取到另外一个加值了,当然它得存在。


public static int kthLargestElement(int k, int[] nums)
{
    //两个哨兵ij,temp为临时值,start和end记录具体查找段的开始和结束
    int i, j, temp, start, end;
    
    //初始化值
    bool isEnd = false;
    i = 0;
    start = i;
    j = nums.Length - 1;
    end = j;
    temp = -1;

    if (nums.Length < k) return -1;

    //快排思想,但是不用管非目标段的排序
    while (!isEnd)
    {
        //处理每一段的排序,将比参考值小的往前靠,比参考值大的往后靠,参考值放中间
        temp = start;
        while (i != j)
        {
            while (nums[j] <= nums[temp] && j != i)
            {
                j--;//在右边找一个比参考值小的
            }

            while (nums[i] >= nums[temp] && i != j)
            {
                i++;//在左边找一个比参考值大的
            }

            if (i == j)
            {
                //两哨兵相遇,与参考值调换位置
                if (i != temp)//注意这两个相等的时候,这种交换就把值变成0了
                {
                    nums[i] = nums[i] + nums[temp];
                    nums[temp] = nums[i] - nums[temp];
                    nums[i] = nums[i] - nums[temp];
                }
                temp = i;
            }
            else
            {
                //交换两个找到的值
                nums[i] = nums[i] + nums[j];
                nums[j] = nums[i] - nums[j];
                nums[i] = nums[i] - nums[j];
            }
        }

        //判断是否找到了,参考的位置就是该数据的真实排名了
        if (temp + 1 == k)
        {
            isEnd = true;
            break;
        }

        if (temp + 1 < k)
        {
            //去右边
            j = end;
            start = temp + 1;
            i = temp + 1;
        }
        else
        {
            i = start;
            end = temp - 1;
            j = temp - 1;
        }

    }

    return nums[temp];
}


原来这叫Quick Select,和快排是同一个人提出的。

注释已经写得很明白了 也可以参考 快速排序-不用List速排序-不Lis


计算1000-9999中,插入最少一个运算符后使得结果为原来序列的反序。

例如:886-> 8 * 86 = 688

using System;
using System.Data;

namespace 算法实现
{
    class SiZeYunSuan
    {
        DataTable table = new DataTable();
        //private Calculator calculator = new Calculator();我的计算机类已经不知道跑去哪里了
        string[] sign = { "+", "-", "*", "/", "" };

        public void Cal()
        {
            string exp = "";
            for (int i = 1000; i < 10000; i++)
            {
                string num = i.ToString();
                for (int j = 0; j < sign.Length; j++)
                {
                    for (int k = 0; k < sign.Length; k++)
                    {
                        for (int l = 0; l < sign.Length; l++)
                        {
                            exp = num[3] + sign[j] + num[2] + sign[k] + num[1] + sign[l] + num[0];
                            if (exp.Length > 4) {
                                if (table.Compute(exp,"").ToString() == num) {
                                    
                                    Console.WriteLine(" "+num[3]+num[2]+num[1]+num[0]);
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

代码为穷举法,很简单不解释了。


求用十进制、二进制、八进制表示都是回文数的所有数字中,大于十进制数10的最小值
二进制数为回文数,所以不会以0开头结尾,所以必为奇数

class ReverseNum10_8_2
{
    public void Cal()
    {
        bool s_out = false;
        int i = 11;
        while (!s_out)
        {
            string str2 =  Convert.ToString(i, 2);
            string str8 = Convert.ToString(i, 8);
            string str10 = Convert.ToString(i, 10);
            /*char[] c2 = str2.ToCharArray();
            Array.Reverse(c2);
            char[] c8 = str8.ToCharArray();
            Array.Reverse(c8);
            char[] c10 = str10.ToCharArray();
            Array.Reverse(c10);*/
            if (str2 == reverse(str2) && str8 == reverse(str8) && str10 == reverse(str10))
            {
                Console.WriteLine("该数字为:" + str10);
                Console.WriteLine("二进制为:" + str2);
                Console.WriteLine("八进制为:" + str8);
                s_out = true;
            }
            i += 2;
        }
    }
    private string reverse(string str)
    {
        int Length = str.Length;
        char[] rChar = new char[Length];
        for (int i = 0; i < Length; i++)
        {
            rChar[i] = str[Length - i - 1];
        }
        return new string(rChar);
    }
}


暴力搞定法啊,哈!


魔术师发牌问题的简介:一位魔术师掏出一叠扑克牌,魔术师取出其中13张黑桃,洗好后,把牌面朝下。说:“我不看牌,只数一数就能知道每张牌是什么?”魔术师口中念一,将第一张牌翻过来看正好是A;魔术师将黑桃A放到桌上,继续数手里的余牌,第二次数1,2,将第一张牌放到这叠牌的下面,将第二张牌翻开,正好是黑桃2,也把它放在桌子上。第三次数1,2,3,前面二张牌放到这叠牌的下面,取出第三张牌,正好是黑桃3,这样依次将13张牌翻出,全部都准确无误。求解:魔术师手中牌的原始顺序是什么样子的?


class MoShuShiFaPai
{
    private CycleLink<int> cycle = new CycleLink<int>();

    public void Cal()
    {
        cycle.Clear();

        for (int i = 0; i < 13; i++)
        {
            //初始化为-1  用来区分头结点
            cycle.Add(-1);
        }

        //第一张肯定是1
        CycleLink<int>.Node node = cycle.GetNodeByIndex(1);
        node.data = 1;
        int index = 0;

        for (int i = 2; i <= 13; i++)
        {
            //设置其他位置的牌  头结点也计算进去了
            while (index < i)
            {
                node = node.next;
                if (node.data > 0) continue;
                    
                index++;
                if (node.data == 0) index--;//跳过头结点不能算
            }

            index = 0;
            node.data = i;
        }
    }

    public void Print()
    {
        int data = 0;
        for (int i = 1; i <= 13; i++)
        {
            cycle.GetElement(i, ref data);
            Console.Write(data + " ");
        }
    }
}


TIM图片20180510153438.png


41一个人围成一个圈,由第一个人开始报数,没数到第3个人就自杀,那么剩下的是在第几个。

圈的问题,使用循环链表的数据结构就很好解答了

我这里没有用到循环链表的特性,我这种做法,普通的链表数组其实都可以做到。

使用一个计数器,每记到第几位,就移除对应位置的元素,所以需要一个能够准确指向对应元素的index,index随着计数器往下加,注意不能超过数组范围,超过就回到原点。

最重要的是,在移除之后,index指向的元素就是移除元素的后一个了,所以要把index往前移动一下再进行计数。

如果使用循环链表的特性,就是不停的下几位,移除,下几位,移除.....

class YueSeFuProbrom
{
    CycleLink<int> cycleLink = new CycleLink<int>();

    public void Cal(int pNum, int which)
    {
        cycleLink.Clear();
        //构建循环链表 表示圆圈
        for (int i = 1; i <= pNum; i++)
        {
            cycleLink.Add(i);
        }

        int index = 0;
        int counter = 0;
        int who = 0;
        while (cycleLink.GetCycleLinkLength() >= which)
        {
            index = index % cycleLink.GetCycleLinkLength();
            counter++;
            index++;
            if (counter % which == 0)
            {
                cycleLink.Delete(index, ref who);
                Console.Write(who + " ");
                index--;
            }
        }
        Console.WriteLine();
        Console.Write("活着的有:");
        for (int i = 1; i < which; i++)
        {
            cycleLink.GetElement(i, ref who);
            Console.Write(who + " ");
        }
        Console.WriteLine();
        Console.WriteLine();
    }
}



//测试
static void TestYueSeFu()
{
    YueSeFuProbrom yueSeFu = new YueSeFuProbrom();
    yueSeFu.Cal(5, 2);
    yueSeFu.Cal(100, 3);
    yueSeFu.Cal(6, 3);
    yueSeFu.Cal(41, 3);
}

捕获.PNG


给你一个整数n. 从 1 到 n 按照下面的规则打印每个数:

  • 如果这个数被3整除,打印fizz.

  • 如果这个数被5整除,打印buzz.

  • 如果这个数能同时被35整除,打印fizz buzz.

要求:只用一个if判断

static List<string> Cal(int n)
{
    List<string> res = new List<string>();
    string[] temp = { "fizz", "fizz buzz", "buzz" };

    for (int i = 1; i <= n; i++)
    {
        if (i % 3 != 0 && i % 5 != 0)
        {
            res.Add(i.ToString());
        }
        else
        {
            int a = i % 3;
            int b = i % 5;

            int off = a - b;
            //映射(-1-0),(0,1),(1,2)
            int index = Math.Sign(off / (double)int.MaxValue) + 1;

            res.Add(temp[index]);
        }
    }

    return res;
}

我想的办法就是排除不是3和5倍数的数,然后将是3和5倍数的数通过一个映射计算到数组的下标,得到对应的字符串。

这里使用了Math.Sign不知道是不是取巧了,刚好这个函数是返回-1,0,1的,估计函数里面也有判断的,估计不是这样解的哈