Leetao's Blog

Talk is cheap, show me the code

0%

发表于 更新于

Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]....

Example:
(1) Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6].
(2) Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2].

Note:
You may assume all input has valid answer.

Follow Up:
Can you do it in O(n) time and/or in-place with O(1) extra space?

Solutions

  1. 将列表进行排序
  2. 找到排序后的中位数
  3. 以中位数将列表分为前后两个部分A,B
  4. 依次逆序输出A,B中的结果集

Python

1
2
3
4
5
6
7
8
9
class Solution(object):
    def wiggleSort(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        sorted_nums = sorted(nums)
        half = len(sorted_nums[::2])
        nums[0::2],nums[1::2] = sorted_nums[0:half][::-1],sorted_nums[half:][::-1]

发表于 更新于

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

Solution

两个区间(A,B)能合并,说明这 A.end >= B.start and A.start <= B.start ,将这些区间以 start 的值从小到大排序,
如果两个区间有重叠则合并这个区间,否则直接将该区间存入结果中

Python 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: List[Interval]
        """
        res = []
        for i in sorted(intervals, key=lambda i: i.start):
            if res and i.start <= res[-1].end:
                res[-1].end = max(res[-1].end, i.end)
            else:
                res.append(i)
        return res

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

// 来自讨论区

public List<Interval> merge(List<Interval> intervals) {
    if (intervals.size() <= 1)
        return intervals;
    
    // Sort by ascending starting point using an anonymous Comparator
    intervals.sort((i1, i2) -> Integer.compare(i1.start, i2.start));
    
    List<Interval> result = new LinkedList<Interval>();
    int start = intervals.get(0).start;
    int end = intervals.get(0).end;
    
    for (Interval interval : intervals) {
        if (interval.start <= end) // Overlapping intervals, move the end if needed
            end = Math.max(end, interval.end);
        else {                     // Disjoint intervals, add the previous one and reset bounds
            result.add(new Interval(start, end));
            start = interval.start;
            end = interval.end;
        }
    }
    
    // Add the last interval
    result.add(new Interval(start, end));
    return result;
}

发表于 更新于

Given a string and a string dictionary, find the longest string in the dictionary that can be formed by deleting some characters of the given string. If there are more than one possible results, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.

Example 1:

1
2
3
4
5
Input:
s = "abpcplea", d = ["ale","apple","monkey","plea"]

Output: 
"apple"

Example 2:

1
2
3
4
5
Input:
s = "abpcplea", d = ["a","b","c"]

Output: 
"a"

Note:

  1. All the strings in the input will only contain lower-case letters.
  2. The size of the dictionary won’t exceed 1,000.
  3. The length of all the strings in the input won’t exceed 1,000.

Solutions

通过删除字符串去形成字典中的单词,保持原有字符串的相对顺序,对于结果优先考虑最长的字符串,长度相等的情况下考虑字典序最小的字符串

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution(object):
    def findLongestWord(self, s, d):
        """
        :type s: str
        :type d: List[str]
        :rtype: str
        """
        res_list = []
        def isSubstring(sub, source):
            for item in sub:
                if source.find(item) != -1:
                    j = source.find(item)
                    source = source[j+1:]
                else:
                    return False      
            return True

        for item in d:
            if(isSubstring(item, s)):
                res_list.append(item)

        res = ""
        max_len = 0

        for item in res_list:
            if len(item) > max_len or (len(item) == max_len and item < res):
                res = item
                max_len = len(item)
                
        return res

比较简洁的 Python 代码

1
2
3
4
5
def findLongestWord(self, s, d):
    def isSubsequence(x):
        it = iter(s)
        return all(c in it for c in x)
    return max(sorted(filter(isSubsequence, d)) + [''], key=len)

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class Solution {
    public String findLongestWord(String s, List<String> d) {
        String res = "";
        if (s.length() == 0 || d.size() == 0) {
            return res;
        }
        for (String str : d) {
            int resLen = res.length();
            int strLen = str.length();
            if (isSequence(s, str) &&
                (strLen > resLen || (strLen == resLen && str.compareTo(res) < 0))) {
                res = str;
            }
        }
        return res;
    }
    
    private boolean isSequence(String s, String d) {
        int i = 0;
        int j = 0;
        while (i < s.length() && j < d.length()) {
            while (i < s.length() && s.charAt(i) != d.charAt(j)) {
                i ++;
            }
            if (i < s.length()) {
                i ++;
                j ++;
            }
        }
        return j == d.length();
    }
}

简洁版的 Java 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
public String findLongestWord(String s, List<String> d) {
    String longest = "";
    for (String dictWord : d) {
        int i = 0;
        for (char c : s.toCharArray()) 
            if (i < dictWord.length() && c == dictWord.charAt(i)) i++;

        if (i == dictWord.length() && dictWord.length() >= longest.length()) 
            if (dictWord.length() > longest.length() || dictWord.compareTo(longest) < 0)
                longest = dictWord;
    }
    return longest;
}

发表于 更新于

Sort a linked list using insertion sort.

Solution

插入排序

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def insertionSortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head is None:
            return head
        dummy = ListNode(-1)
        dummy.next = head
        current = head
        while current:
            print(current.val)
            begin = dummy
            current_next = current.next
            if current_next and current_next.val < current.val:
                tmp_current = current
                current.next = current_next.next
                while begin != tmp_current:
                    if begin.next.val > current_next.val:
                        current_next.next = begin.next
                        begin.next = current_next
                        break
                    else:
                        begin = begin.next
            else:
                current = current.next
        return dummy.next

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode helper = new ListNode(0);
        ListNode pre = helper;
        ListNode current = head;
        while(current!=null) {
            pre = helper;
            while(pre.next != null && pre.next.val < current.val) {
                pre = pre.next;
            }
            ListNode next = current.next;
            current.next = pre.next;
            pre.next = current;
            current = next;
        }
        return helper.next;
    }
}

发表于 更新于

Given a list of non negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

Solution

主要思路排序,这里需要意识到:int(str(A) + str(B)) > int(str(B) + str(A)),那么 A 应该在 B 之前,否则
B 应该在 A之前,注意对前导零的处理,[0,0] 结果应该是 “0”

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

# 归并排序

class Solution:
    # @param {integer[]} nums
    # @return {string}
    def largestNumber(self, num):
        num = [str(x) for x in num]
        num = self.mergeSort(num)
        return str(int("".join(num)))
    
    def mergeArray(self,left, right):
        """
            merge the left and right array
        """
        res = []
        i = j = 0
        while i < len(left) and j < len(right):
            if int(left[i] + right[j]) < int(right[j] + left[i]):
                res.append(right[j])
                j += 1
            else:
                res.append(left[i])
                i += 1
        while i < len(left):
            res.append(left[i])
            i += 1
        
        while j < len(right):
            res.append(right[j])
            j += 1
        return res
                
    def mergeSort(self,lists):
        if len(lists) <= 1:
            return lists
        mid = int(len(lists)/2)
        left = self.mergeSort(lists[:mid])
        right = self.mergeSort(lists[mid:])
        return self.mergeArray(left,right)

另外一种简洁的代码

1
2
3
4
5
6
7
class Solution:
    # @param {integer[]} nums
    # @return {string}
    def largestNumber(self, num):
        num = [str(x) for x in num]
        num.sort(cmp=lambda x, y: cmp(y+x, x+y))
        return ''.join(num).lstrip('0') or '0'

发表于 更新于

前言

In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct key value, and using arithmetic on those counts to determine the positions of each key value in the output sequence. Its running time is linear in the number of items and the difference between the maximum and minimum key values, so it is only suitable for direct use in situations where the variation in keys is not significantly greater than the number of items. However, it is often used as a subroutine in another sorting algorithm, radix sort, that can handle larger keys more efficiently.——摘自 Wikipedia Counting sort

从上述的文字中我们可以了解到以下的信息:

  1. 计数排序是一个整数排序算法
  2. 计数排序的时间复杂度是线性的
  3. 计数排序通常只适用于键值范围不是远大于元素数量的情况
  4. 基数排序可以解决3不适用的范围

思想

这里以数组 [2,5,3,1,2,3,1,3],作为测试数据,这里很容易看出来键值范围为 0~5(k).对于数组中的元素来说,如果我知道有多少元素不大于该元素的话,基于这样的前提条件下,就可以知道排序后该元素在数组中的位置.

过程

基于上述的思路,我们尝试去模拟一下整个过程:

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class CountSort {

	private static int[] countSort(int[] A,int k) {
		int[] B = new int[A.length];
		int[] C = new int[k+1];

		for(int i = 0; i < A.length; i++) {
			C[A[i]]++;
		}

		for(int i = 1; i < C.length; i++) {
			C[i] = C[i] + C[i-1];
		}

		for(int j = A.length -1; j >=0 ; j--) {
			B[C[A[j]]-1] = A[j];
			C[A[j]]--;
		}
		return B;
	}

	public static void main(String[] args) {
		int[] A = new int[]{2,5,3,1,2,3,1,3};
		int[] B = countSort(A, 5);
		for(int i: B) {
			System.out.print(i+" ");
		}
	}
}

输出结果如下:

1
1 1 2 2 3 3 3 5

优化

仔细观察一下数组C,我们可以发现对于数组C,其索引为0的元素对应的值为0,有没有可能将数组C的所有元素全部左移一位呢.从而减少开销呢？完全可以的,我们可以将长度由原来的k+1，优化为max-min+1,其中max,min分别对应为A的最大值和最小值.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public class CountSort {

	private static int[] countSort(int[] A) {
		int[] B = new int[A.length];
		int max = A[0], min = A[0];
		
		// 获取max,min
		for(int a: A) {
			if(a > max) {
				max = a;
			}
			if(a < min ) {
				min = a;
			}
		}
		
		int k = max - min + 1;
		int[] C = new int[k];

		//减少了C数组的大小
		for(int i = 0; i < A.length; i++) {
			C[A[i]-min]++; 
		}

		for(int i = 1; i < C.length; i++) {
			C[i] = C[i] + C[i-1];
		}

		for(int i = A.length - 1; i >= 0; i--) {
			B[C[A[i]-min] - 1] = A[i];
			C[A[i]-min]--;
		}

		return B;
	}

	public static void main(String[] args) {
		int[] A = new int[]{2,5,3,1,2,3,1,3};
		int[] B = countSort(A);
		for(int i: B) {
			System.out.print(i+" ");
		}
	}
}

参考资料

CountingSort


计数排序详解以及java实现


计数排序

发表于 更新于

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:

You are not suppose to use the library’s sort function for this problem.

Solution

计数排序

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        zeros = 0
        ones = 0
        twos = 0
        for num in nums:
            if num == 0:
                zeros += 1
            if num == 1:
                ones += 1
            if num == 2:
                twos += 1
            
        for i in range(zeros):
            nums[i] = 0
        for i in range(ones):
            nums[zeros + i] = 1
        for i in range(twos):
            nums[zeros + ones + i] = 2

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static void sortColors(int []nums){
	int red=0,white=0,blue=0;
	for(int i=0;i!=nums.length;i++){//first, count their numbers
		if(nums[i]==0){
			red++;
		}else if(nums[i]==1){
			white++;
		}else{
			blue++;
		}
	}
	for(int i=0;i!=nums.length;i++){//second, rewrite the original array
		if(i<red){
			nums[i]=0;
		}else if(i<white+red){
			nums[i]=1;
		}else{
			nums[i]=2;
		}
	}
}

发表于 更新于

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

Note:

  1. Each element in the result must be unique.
  2. The result can be in any order.

solutions

Python

1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def intersection(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        nums1 = set(nums1)
        nums2 = set(nums2)
        return list(nums1&nums2)

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
public class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set = new HashSet<>();
        Arrays.sort(nums2);
        for (Integer num: nums1) {
            if (binarySearch(nums2, num)) {
                set.add(num);
            }
        }
        int i = 0;
        int[] res = new int[set.size()];
        for (Integer num : set) {
            res[i++] = num;
        }
        return res;
    }
    
    public boolean binarySearch(int[] nums, int target) {
        int low = 0;
        int high = nums.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] == target) {
                return true;
            }
            if (nums[mid] > target) {
                high = mid - 1;
            } else{
                low = mid + 1;
            }
        }
        return false;
    }
}




// recommended
public class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        if (nums1 == null || nums2 == null) {
            return null;
        }

        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int i = 0, j = 0, index = 0;
        int[] temp = new int[nums1.length];
        while (i < nums1.length && j < nums2.length) {
        	if (nums1[i] == nums2 [j]) {
        		if (index == 0 || temp[index - 1] != nums1[i]) {
        			temp[index] = nums1[i];
        			index ++;
        		}
        		i ++;
        		j ++;
        	} else if (nums1[i] < nums2[j]){
        		i ++;
        	} else {
        		j ++;
        	}
        }
        int[] result = new int[index];
        for(int k = 0; k < index; k++) {
            result[k] = temp[k];
        }
        return result;
    }
}

发表于 更新于

Given a string s and a non-empty string p, find all the start indices of p‘s anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

1
2
3
4
5
6
7
8
9
Input:
s: "cbaebabacd" p: "abc"

Output:
[0, 6]

Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

1
2
3
4
5
6
7
8
9
10
Input:
s: "abab" p: "ab"

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from collections import Counter
class Solution(object):
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        res  = []
        p_len = len(p)
        s_len = len(s)
        p_counter = Counter(p)
        s_tmp_counter = Counter(s[:p_len])
        if s_tmp_counter == p_counter:
            res.append(0)
        for i in range(p_len,s_len):
            s_tmp_counter[s[i-p_len]] -= 1
            if s_tmp_counter[s[i-p_len]] == 0:
                del s_tmp_counter[s[i-p_len]]
            s_tmp_counter[s[i]] += 1
            if s_tmp_counter == p_counter:
                res.append(i+1-p_len)
        return res

发表于 更新于

最近准备入机器学习的坑,啃书之余还想顺便看看相关学习视频,然后自然想起了 Coursera, Coursera 现在已经开始诱导收费了,老实说收费也是无可厚非的,在经济允许范围内,我觉得付费还是值得提倡的。当然没钱的话，就试试下面的方法吧。以 Deep Learning 为例.

搜索
在其目录搜索框输入deep learning 获取到如下结果:

显然点进去任意一门课程,注册都是提示需要收费的,那么我们就不点开了。我们挑选其中一个合适的课程，选取图中的华盛顿大学。ok，接下来，将滚动条拉到最下方,找到合作伙伴点进去:

然后在合作伙伴页面中找到华盛顿大学:

然后点进去,在其页面中有许多课程，然后找到我们要找的 deep learning 再次点击进去

然后选择注册，然后点击旁听

以上就可以获取免费学习的机会了最后还是说一句，有条件的还是选择一两门付费吧