分类:LeetCode

[LeetCode]Roman to Integer

[LeetCode]Roman to Integer

    public class Solution
    {
        public int RomanToInt(string s)
        {
            int l = s.Length;
            int tot = 0;
            for (int i = 0; i < l; i++)
            {
                if (s[i] == 'I')
                {
                    if (i + 1 < l && s[i + 1] == 'V')
                    {
                        tot += 4;
                        i++;
                    }
                    else if (i + 1 < l && s[i + 1] == 'X')
                    {
                        tot += 9;
                        i++;
                    }
                    else
                    {
                        tot += 1;
                    }
                }
                else if (s[i] == 'X')
                {
                    if (i + 1 < l && s[i + 1] == 'L')
                    {
                        tot += 40;
                        i++;
                    }
                    else if (i + 1 < l && s[i + 1] == 'C')
                    {
                        tot += 90;
                        i++;
                    }
                    else
                    {
                        tot += 10;
                    }
                }
                else if (s[i] == 'C')
                {
                    if (i + 1 < l && s[i + 1] == 'D')
                    {
                        tot += 400;
                        i++;
                    }
                    else if (i + 1 < l && s[i + 1] == 'M')
                    {
                        tot += 900;
                        i++;
                    }
                    else
                    {
                        tot += 100;
                    }
                }
                else if (s[i] == 'V') tot += 5;
                else if (s[i] == 'L') tot += 50;
                else if (s[i] == 'D') tot += 500;
                else if (s[i] == 'M') tot += 1000;
            }
            return tot;
        }
    }

[LeetCode]Intersection of Two Arrays

[LeetCode]Intersection of Two Arrays

很简单的一道题
扫一遍就好

    public class Solution
    {
        public int[] Intersection(int[] nums1, int[] nums2)
        {
            if (nums1.Length == 0 || nums2.Length == 0)
            {
                int[] emptyArray = new int[0];
                return emptyArray;
            }
            List<int> listNum = new List<int>();
            foreach (var i in nums2)
            {
                if (nums1.Contains(i) && !listNum.Contains(i))
                {
                    listNum.Add(i);
                }
            }
            return listNum.ToArray();
        }
    }
[LeetCode]Find All Duplicates in an Array

[LeetCode]Find All Duplicates in an Array

有一个不允许使用额外空间同时要在O(n)复杂度解决的要求
那就每找到一个数字,就把这个数字位置的数字置为负数。

    public class Solution
    {
        public IList<int> FindDuplicates(int[] nums)
        {
            IList<int> ans = new List<int>();
            for (int i = 0; i < nums.Length; i++)
            {
                int index = Math.Abs(nums[i]) - 1;
                if (nums[index] < 0)
                    ans.Add(Math.Abs(index + 1));
                nums[index] = -nums[index];
            }
            return ans;
        }
    }
[LeetCode]Longest Palindrome

[LeetCode]Longest Palindrome

很简单的题
统计一遍奇数个数字母和偶数个数字母
加起来减掉奇数个数字母的个数
然后如果存在奇数个数的字母就加一

    public class Solution
    {
        public int LongestPalindrome(string s)
        {
            Dictionary<char, int> countChar = new Dictionary<char, int>();
            foreach (var ch in s)
            {
                if (countChar.ContainsKey(ch))
                    countChar[ch]++;
                else
                    countChar.Add(ch, 1);
            }
            int numOdd = 0;
            int countOdd = 0;
            int countEven = 0;
            int hasOdd = 0;
            foreach (var temp in countChar)
            {
                if (temp.Value % 2 == 0)
                {
                    countEven += temp.Value;
                }
                else
                {
                    numOdd++;
                    countOdd += temp.Value;
                    hasOdd = 1;
                }
            }
            return countEven + countOdd - numOdd + hasOdd;
        }
    }
[LeetCode]Largest Number

[LeetCode]Largest Number

简单的字符串排序
比较S2+S1和S1+S2

    public class Solution
    {
        public string LargestNumber(int[] nums)
        {
            List<string> Nums = new List<string>();
            foreach (var temp in nums)
            {
                Nums.Add(Convert.ToString(temp));
            }
            Nums.Sort(Compare);
            string RetData = "";
            foreach (var temp in Nums)
            {
                RetData = string.Concat(RetData, temp);
            }
            int ZeroCount = 0;
            for (ZeroCount = 0; ZeroCount < RetData.Length; ZeroCount++)
            {
                if (RetData[ZeroCount] == '0') continue;
                if (RetData[ZeroCount] != '0') break;
            }
            RetData = RetData.Remove(0, ZeroCount);
            if (RetData == "") RetData = "0";
            return RetData;
        }
        private int Compare(string Comp1, string Comp2)
        {
            return string.Compare(string.Concat(Comp2, Comp1), string.Concat(Comp1, Comp2));
        }
    }
[LeetCode]Encode and Decode TinyURL

[LeetCode]Encode and Decode TinyURL

很简单
dictionary就可以了

	public class Codec
	{
		Dictionary<string,string> dictUrl = new Dictionary<string,string> ();
		List<char> charSet = new List<char> ();

		public Codec ()
		{
			for (int i = 65; i <= 90; i++) {
				charSet.Add ((char)i);
			}
			for (int i = 97; i <= 122; i++) {
				charSet.Add ((char)i);
			}
			for (int i = 48; i <= 57; i++) {
				charSet.Add ((char)i);
			}
		}
		//EUREKA
		private string genUrl ()
		{
			Random rand = new Random ();
			string subUrl = "";
			for (int i = 0; i < 6; i++) {
				subUrl += charSet [rand.Next () % (charSet.Count)];
			}
			return "http://tinyurl.com/" + subUrl;
		}
		// Encodes a URL to a shortened URL
		public string encode (string longUrl)
		{
			if (dictUrl.ContainsKey (longUrl))
				return dictUrl [longUrl];
			while (true) {
				string shortUrl = genUrl ();
				if (dictUrl.ContainsValue (shortUrl))
					continue;
				else {
					dictUrl.Add (longUrl, shortUrl);
					break;
				}
			}
			return dictUrl [longUrl];
		}

		// Decodes a shortened URL to its original URL.
		public string decode (string shortUrl)
		{
			if (!dictUrl.ContainsValue (shortUrl))
				return "";
			foreach (var temp in dictUrl) {
				if (temp.Value == shortUrl)
					return temp.Key;
			}
			return "";
		}
	}
[LeetCode]Remove Duplicates from Sorted Array

[LeetCode]Remove Duplicates from Sorted Array

一开始没注意到要在nums中修改= =WA了好多次
自己还是蠢啊= =

public class Solution {
    public int removeDuplicates(int[] nums) {
        Set<Integer> set=new HashSet<>();
        List<Integer> list=new ArrayList<>();
        for (Integer integer : nums) {
        	if (!set.contains(integer)) list.add(integer);
			set.add(integer);
		}
        for(int i=0;i<list.size();i++)
        {
        	nums[i]=list.get(i);
        }
        return set.size();
    }
}
[LeetCode]Swap Nodes in Pairs

[LeetCode]Swap Nodes in Pairs

注意记录前一个节点

//JAVA
public class Solution {
	public ListNode swapPairs(ListNode head) {
		ListNode currNode = head;
		if (head == null)
			return head;
		if (head.next == null)
			return head;
		ListNode newHead = head.next;
		ListNode prev = null;
		boolean flag = true;
		while (flag) {
			if (currNode.next == null)
				break;
			if (currNode.next.next == null)
				flag = false;
			ListNode tempNode = currNode.next;

			currNode.next = tempNode.next;
			tempNode.next = currNode;
			if (prev != null)
				prev.next = tempNode;
			prev = currNode;
			currNode = currNode.next;
		}
		return newHead;
	}
}
[LeetCode]146 LRU Cache

[LeetCode]146 LRU Cache

双向链表,每次有get之后就把get的元素放到链表头,put的时候满了就删掉链表尾的元素。

    public class LRUCache
    {
        private int Length;
        private Node Head;
        private Node Tail;
        private int Capacity;
        public LRUCache(int capacity)
        {
            Length = 0;
            Head = new Node();
            Tail = new Node();
            Head.Next = Tail;
            Tail.Prev = Head;
            Capacity = capacity;
        }

        public int Get(int key)
        {
            if (Length == 0) return -1;
            Node FindNode = Head;
            while (FindNode != null)
            {
                if (FindNode.Key == key)
                {
                    FindNode.Prev.Next = FindNode.Next;
                    FindNode.Next.Prev = FindNode.Prev;
                    FindNode.Prev = Head;
                    FindNode.Next = Head.Next;
                    Head.Next.Prev = FindNode;
                    Head.Next = FindNode;
                    return FindNode.Value;
                }
                FindNode = FindNode.Next;
            }
            return -1;
        }

        public void Put(int key, int value)
        {
            if (Get(key) != -1)
            {
                Node FindNode = Head;
                while (FindNode != null)
                {
                    if (FindNode.Key == key)
                    {
                        FindNode.Value = value;
                        return;
                    }
                    FindNode = FindNode.Next;
                }
            }
            Node NewNode = new Node(key, value);
            if (Length < Capacity)
            {
                //Node NewNode = new Node(key, value);
                NewNode.Prev = Head;
                NewNode.Next = Head.Next;
                Head.Next.Prev = NewNode;
                Head.Next = NewNode;
                Length++;
                return;
            }
            if (Capacity == 1)
            {
                //Node NewNode = new Node(key, value);
                NewNode.Prev = Head;
                Head.Next = NewNode;
                Tail.Prev = NewNode;
                NewNode.Next = Tail;
                Length++;
                return;
            }
            Node OldNode = Tail.Prev;
            Tail.Prev = Tail.Prev.Prev;
            Tail.Prev.Next = Tail;
            OldNode = null;
            NewNode.Next = Head.Next;
            Head.Next.Prev = NewNode;
            Head.Next = NewNode;
            NewNode.Prev = Head;
            Length++;
            return;
        }
    }
    public class Node
    {
        public int Key;
        public int Value;
        public Node Next, Prev;
        public Node(int key, int value) { Key = key; Value = value; Next = null; Prev = null; }
        public Node() { Key = 0; Value = 0; Next = null; Prev = null; }
    }