Codewars Java练习:Maximum subarray sum

题目

The maximum sum subarray problem consists in finding the maximum sum of a contiguous subsequence in an array or list of integers:

Easy case is when the list is made up of only positive numbers and the maximum sum is the sum of the whole array. If the list is made up of only negative numbers, return 0 instead.

Empty list is considered to have zero greatest sum. Note that the empty list or array is also a valid sublist/subarray.

题解

哇,终于做到动态规划了耶,将数组A本身转化为前缀和数组B,那么本题就是要求在前缀和数组B上找一前一后两个数,使得他们的差尽量大。

当然,这样的做法较为繁琐,可以一个for语句解决的事情就不要用多个,下面是我的代码——

其中,sum储存的是在某个位置结束的数组A的子序列最大字段和,为什么有这样的更新方法读者自己试一组样例就知道了。

原创文章地址:【Codewars Java练习:Maximum subarray sum】转载时请注明出处mhy12345.xyz

Codewars Java练习:Next bigger number with the same digits

题目

You have to create a function that takes a positive integer number and returns the next bigger number formed by the same digits:

If no bigger number can be composed using those digits, return -1:

题解

题意大概是找到一个数组成数字相同的,大一点的那个数。

实际上只要使用程序将我们解决这道题的思路翻译一遍就行了,先找出最低的可以变大的位(这个位的更低位有一个尽量小,但是比他大的数),交换后,将比他低的位从小到大排序。

 

原创文章地址:【Codewars Java练习:Next bigger number with the same digits】转载时请注明出处mhy12345.xyz

Java多线程实现归并排序

Java中,一个class可以继承Thread类以实现多线程调用

 

原创文章地址:【Java多线程实现归并排序】转载时请注明出处mhy12345.xyz

Codewars Java练习:Perimeter of squares in a rectangle

题目

The drawing shows 6 squares the sides of which have a length of 1, 1, 2, 3, 5, 8. It’s easy to see that the sum of the perimeters of these squares is : 4 * (1 + 1 + 2 + 3 + 5 + 8) = 4 * 20 = 80

Could you give the sum of the perimeters of all the squares in a rectangle when there are n + 1 squares disposed in the same manner as in the drawing:

alternative text

#Hint: See Fibonacci sequence

#Ref: http://oeis.org/A000045

The function perimeter has for parameter n where n + 1 is the number of squares (they are numbered from 0 to n) and returns the total perimeter of all the squares.

题解

题目大意就是求斐波那契前缀和第N项的值的四倍。斐波那契数列本身有很好的性质,我们可以考虑如何变幻前缀和的项,而保证和不变

(1)   \begin{align*} &1+1+2+3+5+8+13+...+fib(n-1)+fib(n) \\ =&2+5+13+..+fib(n-2)+fib(n+1) \\ =&(-1)+1+2+5+13+...+fib(n-2)+fib(n+1) \\ =&(-1)+fib(n)+fib(n+1) =&fib(n+2)-1 \end{align*}

 

上述推导,表示了fibonacci数列的前缀和恰好是一个fibonacci数列-1的数列。

 

原创文章地址:【Codewars Java练习:Perimeter of squares in a rectangle】转载时请注明出处mhy12345.xyz

Codewars Java练习:Number of trailing zeros of N!

题目

Write a program that will calculate the number of trailing zeros in a factorial of a given number.

N! = 1 * 2 * 3 * ... * N

Be careful 1000! has 2568 digits…

For more info, see: http://mathworld.wolfram.com/Factorial.html

Examples

Hint: You’re not meant to calculate the factorial. Find another way to find the number of zeros.

题解

这也是5级题???升级好慢==

统计1-n中5出现了多少次就好了。

 

 

原创文章地址:【Codewars Java练习:Number of trailing zeros of N!】转载时请注明出处mhy12345.xyz

Codewars Java练习:Gap in Primes

题目

The prime numbers are not regularly spaced. For example from 2 to 3 the gap is 1. From 3 to 5 the gap is 2. From 7 to 11 it is 4. Between 2 and 50 we have the following pairs of 2-gaps primes: 3-5, 5-7, 11-13, 17-19, 29-31, 41-43

A prime gap of length n is a run of n-1 consecutive composite numbers between two successive primes (see: http://mathworld.wolfram.com/PrimeGaps.html).

We will write a function gap with parameters:

g (integer >= 2) which indicates the gap we are looking for

m (integer > 2) which gives the start of the search (m inclusive)

n (integer >= m) which gives the end of the search (n inclusive)

In the example above gap(2, 3, 50) will return [3, 5] or (3, 5) or {3, 5} which is the first pair between 3 and 50 with a 2-gap.

So this function should return the first pair of two prime numbers spaced with a gap of g between the limits mn if these numbers exist otherwise nil or null or None or Nothing (depending on the language).

In C++ return in such a case {0, 0}. In F# return [||]. In Kotlin return []

#Examples: gap(2, 5, 7) --> [5, 7] or (5, 7) or {5, 7}

gap(2, 5, 5) --> nil. In C++ {0, 0}. In F# [||]. In Kotlin return[]`

gap(4, 130, 200) --> [163, 167] or (163, 167) or {163, 167}

([193, 197] is also such a 4-gap primes between 130 and 200 but it’s not the first pair)

gap(6,100,110) --> nil or {0, 0} : between 100 and 110 we have 101, 103, 107, 109 but 101-107is not a 6-gap because there is 103in between and 103-109is not a 6-gap because there is 107in between.

题解

看讨论区说这道题不能用for循环,还在想是不是MillerRabin素性判定过不了==,结果标准解法不就是一个for循环吗_(:з」∠)_

 

 

原创文章地址:【Codewars Java练习:Gap in Primes】转载时请注明出处mhy12345.xyz

Codewars Java练习:Decode the Morse code

题目

Part of Series 1/3
This kata is part of a series on the Morse code. After you solve this kata, you may move to the next one.

In this kata you have to write a simple Morse code decoder. While the Morse code is now mostly superceded by voice and digital data communication channels, it still has its use in some applications around the world.

The Morse code encodes every character as a sequence of “dots” and “dashes”. For example, the letter A is coded as ·−, letter Q is coded as −−·−, and digit 1 is coded as ·−−−−. The Morse code is case-insensitive, traditionally capital letters are used. When the message is written in Morse code, a single space is used to separate the character codes and 3 spaces are used to separate words. For example, the message HEY JUDE in Morse code is ···· · −·−− ·−−− ··− −·· ·.

NOTE: Extra spaces before or after the code have no meaning and should be ignored.

In addition to letters, digits and some punctuation, there are some special service codes, the most notorious of those is the international distress signal SOS (that was first issued by Titanic), that is coded as ···−−−···. These special codes are treated as single special characters, and usually are transmitted as separate words.

Your task is to implement a function that would take the morse code as input and return a decoded human-readable string.

For example:

NOTE: For coding purposes you have to use ASCII characters . and -, not Unicode characters.

The Morse code table is preloaded for you as a dictionary, feel free to use it:

  • Coffeescript/C++/Go/JavaScript/PHP/Python/Ruby/TypeScript: MORSE_CODE['.--']
  • C#: MorseCode.Get(".--") (returns string)
  • Elixir: morse_codes variable
  • Haskell: morseCodes ! ".--" (Codes are in a Map String String)
  • Java: MorseCode.get(".--")
  • Kotlin: MorseCode[".--"] ?: "" or MorseCode.getOrDefault(".--", "")
  • Rust: self.morse_code

All the test strings would contain valid Morse code, so you may skip checking for errors and exceptions. In C#, tests will fail if the solution code throws an exception, please keep that in mind. This is mostly because otherwise the engine would simply ignore the tests, resulting in a “valid” solution.

Good luck!

After you complete this kata, you may try yourself at Decode the Morse code, advanced.

题解

感觉字符串首尾有一些莫名其妙的空白字符。。。需要使用String.trim()函数先去掉他们。

这个代码和标准答案基本一致。

原创文章地址:【Codewars Java练习:Decode the Morse code】转载时请注明出处mhy12345.xyz

Codewars Java练习:Counting Duplicates

题目

Count the number of Duplicates

Write a function that will return the count of distinct case-insensitive alphabetic characters and numeric digits that occur more than once in the input string. The input string can be assumed to contain only alphabets (both uppercase and lowercase) and numeric digits.

Example

“abcde” -> 0 # no characters repeats more than once
“aabbcde” -> 2 # 'a' and 'b'
“aabBcde” -> 2 # 'a' occurs twice and 'b' twice (bandB)
“indivisibility” -> 1 # 'i' occurs six times
“Indivisibilities” -> 2 # 'i' occurs seven times and 's' occurs twice
“aA11” -> 2 # 'a' and '1'
“ABBA” -> 2 # 'A' and 'B' each occur twice

题解

做了这么几道题,基本上对于Collection和Stream有了一些了解,不用每次写搜索引擎了。思路非常直接,就是先生成一个词频映射,然后对于词频映射的Value值找大于1的个数——

标准解法没有什么非常特别的。

原创文章地址:【Codewars Java练习:Counting Duplicates】转载时请注明出处mhy12345.xyz

Codewars Java练习:Your order, please

题目

Your task is to sort a given string. Each word in the String will contain a single number. This number is the position the word should have in the result.

Note: Numbers can be from 1 to 9. So 1 will be the first word (not 0).

If the input String is empty, return an empty String. The words in the input String will only contain valid consecutive numbers.

For an input: “is2 Thi1s T4est 3a” the function should return “Thi1s is2 3a T4est”

题解

数字的提取可以使用正则表达式(java.util.regex)完成,提取出数值之后,按照数值排序,这里需要使用自定义比较器,自定义比较器的一种做法是直接实例化Comparator接口。代码如下——

当然,如果觉得类的重载MyCmp显得有些多余,Java支持了类的匿名重载,可以将比较器的定义实现在order函数内,代码变成了——

在完成排序之后,将数组转换为stream,方便后续处理,stream支持reduce函数,reduce函数传入合并两项的lambda表达式,返回一个Optional<T>类,Optional<T>类实在T的基础上,增加了一个表示是否为null的指示符,在这里,我们不需要关心为null的情况,故直接使用Optional<T>.get()得到最终答案。

不过笔者确实很傻逼,别人一行能解决的事情自己写了那么久——

 

原创文章地址:【Codewars Java练习:Your order, please】转载时请注明出处mhy12345.xyz

Codewars Java练习:Find the odd int

题目

Given an array, find the int that appears an odd number of times.

There will always be only one integer that appears an odd number of times.

题解

运用异或运算,异或xor满足一个特殊的性质,即a xor a == 0,因此,将整个输入数组异或起来的话,出现偶数次的数将会全部被抵消掉,仅剩下唯一的,出现了奇数次的数。

当然,这个实现方式最简单的代码应该是——

和之前TwoToOne那一道题相似,运用到了stream类,不同的是,这次使用了stream类的reduce函数。

原创文章地址:【Codewars Java练习:Find the odd int】转载时请注明出处mhy12345.xyz