java算法题发布于2019-10-06 07:37:27，更新于2021-03-17 13:04:03，标签：algorithm 文章会持续修订，转载请注明来源地址：https://meethigher.top/blog

Codewars算法记录

1. Take a Ten Minute Walk

描述

You live in the city of Cartesia where all roads are laid out in a perfect grid. You arrived ten minutes too early to an appointment, so you decided to take the opportunity to go for a short walk. The city provides its citizens with a Walk Generating App on their phones -- everytime you press the button it sends you an array of one-letter strings representing directions to walk (eg. ['n', 's', 'w', 'e']). You always walk only a single block in a direction and you know it takes you one minute to traverse one city block, so create a function that will return true if the walk the app gives you will take you exactly ten minutes (you don't want to be early or late!) and will, of course, return you to your starting point. Return false otherwise.

Note: you will always receive a valid array containing a random assortment of direction letters ('n', 's', 'e', or 'w' only). It will never give you an empty array (that's not a walk, that's standing still!).

思路

判断一个数组长度是否为10，里面n的数量等于s，w的数量等于s，则返回true，否则false

实现

我的解决方案

public class TenMinWalk {
	public static boolean isValid(char[] walk) {
		boolean flag=true;
		int[] directions =new int[4];
		if(walk.length!=10) 
			flag=false;
		for (int i = 0; i < walk.length; i++) {
			if(walk[i]=='n') {
				directions[0]++;
			}else if(walk[i]=='s') {
				directions[1]++;
			}else if(walk[i]=='e') {
				directions[2]++;
			}else if(walk[i]=='w') {
				directions[3]++;
			}
		}
		if(!(directions[0]==directions[1]&&directions[2]==directions[3]))
			flag=false;
		
		return flag;
	}
}

大佬的解决方案

public class TenMinWalk {
  public static boolean isValid(char[] walk) {
    if (walk.length != 10) {
      return false;
    }
    int x = 0, y = 0;
    for (int i = 0; i < 10; i++) {
      switch (walk[i]) {
        case 'n':
          y++;
          break;
        case 'e':
          x++;
          break;
        case 's':
          y--;
          break;
        case 'w':
          x--;
          break;
      }
    }
    return x == 0 && y == 0;
  }
}

2. 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.

思路

map集合，key存储数字，value存储次数。遍历集合，将value为奇数的key输出

实现

我的解决方案

import java.util.HashMap;
import java.util.Map;

public class FindOdd {
	public static int findIt(int[] a) {
	    Map<Integer,Integer> map=new HashMap<Integer,Integer>();
	    for (int i = 0; i < a.length; i++) {
			map.put(a[i], 0);
		}
	    for (int i = 0; i < a.length; i++) {
	    	int count=map.get(a[i]);
	    	++count;
			map.put(a[i], count);
		}
	    for(Integer key:map.keySet()) {
	    	if(map.get(key)%2==0)
	    		continue;
	    	return key;
	    }
	    return 0;
	  }
}

大佬的解决方案

public class FindOdd {
  public static int findIt(int[] A) {
    int xor = 0;
    for (int i = 0; i < A.length; i++) {
      xor ^= A[i];
    }
    return xor;
  }
}

异或的运算规则：相同为0，不同为1

异或要将运算的两个数字转换为二进制进行运算

// 比方说 1⊕2⊕1=2
0 0 0 1 -----1
0 0 1 0 -----2
-------------
0 0 1 1 -----3
0 0 0 1 -----1
-------------
0 0 1 0 -----2

3. Simple Encryption #1 - Alternating Split

描述

For building the encrypted string:
Take every 2nd char from the string, then the other chars, that are not every 2nd char, and concat them as new String.
Do this n times!

Examples:

"This is a test!", 1 -> "hsi  etTi sats!"
"This is a test!", 2 -> "hsi  etTi sats!" -> "s eT ashi tist!"
Write two methods:

String encrypt(final String text, final int n)
String decrypt(final String encryptedText, final int n)
For both methods:
If the input-string is null or empty return exactly this value!
If n is <= 0 then return the input text.

This kata is part of the Simple Encryption Series:
Simple Encryption #1 - Alternating Split
Simple Encryption #2 - Index-Difference
Simple Encryption #3 - Turn The Bits Around
Simple Encryption #4 - Qwerty

思路

加密：将字符串转换成字符数组，然后String1存储every 2nd，剩下的给String2，然后将String1跟String2拼接起来。

解密：将字符串分割成两部分，即分割成加密中的String1跟String2，然后将String1跟String2依次拼接。

实现

我的解决方案

 public class Kata {

	public static String encrypt(final String text, final int n) {
		if(n<1)
			return text;
		String[] arr=text.split("");
		String str1="";//存储every 2nd
		String str2="";
		String str="";
		int m=n;
		for (int i = 0; i < arr.length; i++) {
			if((i&1)==1) {
				str1+=arr[i];
				continue;
			}
			str2+=arr[i];
		}
		str=str1+str2;
		if(m>1) 
			str=encrypt(str,--m);
		return str;
	}

	public static String decrypt(final String encryptedText, final int n) {
		if(n<1)
			return encryptedText;
		String[] arr=encryptedText.split("");
		int splitNum=arr.length/2;
		String str1="";
		String str2="";
		String str="";
		int m=n;
		for(int i=0;i<splitNum;i++) {
			str2+=arr[i];
		}
		for(int i=splitNum;i<arr.length;i++) {
			str1+=arr[i];
		}
		for(int i=0;i<splitNum;i++) {
			str+=str1.charAt(i);
			str+=str2.charAt(i);
		}
		if(str1.length()>str2.length()) {
			str+=str1.charAt(splitNum);
		}
		if(m>1)
			str=decrypt(str,--m);
		return str;
	}
}

大佬的解决方案

public class Kata {

	public static String encrypt(final String text, int n) {
		if (n <= 0 || text == null || text.isEmpty()) {
			return text;
		}

		StringBuilder firstPart = new StringBuilder();
		StringBuilder secondPart = new StringBuilder();
		for (int i = 0; i < text.length(); i++) {
			char aChar = text.charAt(i);
			if (i % 2 == 1) {
				firstPart.append(aChar);
			} else {
				secondPart.append(aChar);
			}
		}

		return encrypt(firstPart.append(secondPart).toString(), --n);
	}

	public static String decrypt(final String encryptedText, int n) {
		if (n <= 0 || encryptedText == null || encryptedText.isEmpty()) {
			return encryptedText;
		}

		StringBuilder text = new StringBuilder();
		final int half = encryptedText.length() / 2;
		for (int i = 0; i < half; i++) {
			text.append(encryptedText.charAt(half + i)).append(encryptedText.charAt(i));
		}
		if (encryptedText.length() % 2 == 1) {
			text.append(encryptedText.charAt(encryptedText.length() - 1));
		}

		return decrypt(text.toString(), --n);
	}

}

StringBuilder是一个可变的字符序列

4. Maximum subarray sum

[^时间]: 2019-10-13 周日

描述

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

Max.sequence(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4});
// should be 6: {4, -1, 2, 1}
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.

思路

解决方案：
1. 暴力破解
2. 分治法
分治法的核心思想就是将大问题分解为小问题，再将小问题逐个解决，然后从小问题的解得到原问题的解
如果把数组从任一点（一般取中点）分为两个数组，那最大子数组只能存在于三个位置
a.左数组 b.右数组 3.中间数组（左数组最大后缀和右数组最大前缀的拼接）
然后把分得的两个数组使用递归算法继续进行分割，直到每个子数组只含有一个元素

太难了，我放弃了
3. 动态规划

实现

我的解决方案

public static int sequence(int[] arr) {
		int max=-9999;
		for(int i=0;i<arr.length;i++) {
			for(int j=i;j<arr.length;j++) {
				int sum=0;
				for(int k=i;k<=j;k++) {
					sum+=arr[k];
				}
				if(max<sum)
					max=sum;
			}
		}
		return max<0?0:max;
}

大佬的解决方案

public class Max {

    public static int sequence(int[] arr) {
        int max_ending_here = 0, max_so_far = 0;
        for (int v : arr) {
            max_ending_here = Math.max(0, max_ending_here + v);
            max_so_far = Math.max(max_so_far, max_ending_here);
        }
        return max_so_far;
    }
}

//可以这样理解
public static int sequence(int[] arr) {
		 int max=-9999,cur=0;
		 for(int i=0;i<arr.length;i++) {
			 if(cur<0) {
				 cur=arr[i];
			 }else {
				 cur+=arr[i];
			 }
			 if(cur>=max) {
				 max=cur;
			 }
		 }
		 return max<0?0:max;
}

5. Double Cola

[^时间]: 2019-10-13 周日

描述

Sheldon, Leonard, Penny, Rajesh and Howard are in the queue for a "Double Cola" drink vending machine; there are no other people in the queue. The first one in the queue (Sheldon) buys a can, drinks it and doubles! The resulting two Sheldons go to the end of the queue. Then the next in the queue (Leonard) buys a can, drinks it and gets to the end of the queue as two Leonards, and so on.

For example, Penny drinks the third can of cola and the queue will look like this:

Rajesh, Howard, Sheldon, Sheldon, Leonard, Leonard, Penny, Penny
Write a program that will return the name of the person who will drink the n-th cola.

Input
The input data consist of an array which contains at least 1 name, and single integer n which may go as high as the biggest number your language of choice supports (if there's such limit, of course).

Output / Examples
Return the single line — the name of the person who drinks the n-th can of cola. The cans are numbered starting from 1.

string[] names = new string[] { "Sheldon", "Leonard", "Penny", "Rajesh", "Howard" };
Line.WhoIsNext(names, 1) == "Sheldon"
Line.WhoIsNext(names, 52) == "Penny"
Line.WhoIsNext(names, 7230702951) == "Leonard"

思路

每到一个人，喝下后会拥有分身术，并且移动到末尾
其实就是一个等比数列，a1=5,q=2,an=5*Math.pow(2,n-1);
等比数列前n项和为 sn=5*Math.pow(2,n)-5;
如果求第六个喝饮料的人，就是6-s1==1,这时候，复制的镜像为copies=Math.pow(2,1)==2;所以1/copies向上取整即为结果
如果求第52个喝饮料的人，就是52-s3==17,这时候，复制的镜像为copies=Math.pow(2,3)==8;所以17/copies向上取整即为结果

实现

我的解决方案

public static String WhoIsNext(String[] names, int n) {
		int length = names.length;
		int i = 1;
		double sum=0;
		if (n < length)
			return names[n - 1];
		while (true) {
			sum = 5 * Math.pow(2, i) - 5;
			if (sum > n) {
				break;
			}
			i++;
		}
		double div=n-(5*Math.pow(2, i-1)-5);
		double copies=Math.pow(2, i-1);
		
		return names[(int) Math.ceil(div/copies)-1];
	}

大佬的解决方案

public class Line {
  public static String WhoIsNext(String[] names, int n){
    while ( n > names.length){
      n = (n - (names.length - 1)) / 2;
    }
    return names[n-1];
  }
}

6. Scramblies

[^时间]: 2019-10-13 周日

描述

Complete the function scramble(str1, str2) that returns true if a portion of str1 characters can be rearranged to match str2, otherwise returns false.

Notes:

Only lower case letters will be used (a-z). No punctuation or digits will be included.
Performance needs to be considered
Input strings s1 and s2 are null terminated.
Examples
scramble('rkqodlw', 'world') ==> True
scramble('cedewaraaossoqqyt', 'codewars') ==> True
scramble('katas', 'steak') ==> False

思路

判断str1中是否有str2里面的字符。如果有，就把str1中的删掉。没有就直接false

实现

我的解决方案

public class Scramblies {
	public static boolean scramble(String str1, String str2) {
		
		boolean flag=true;
		StringBuilder strbu2=new StringBuilder(str2);
		StringBuilder strbu1=new StringBuilder(str1);
		for (int i = 0; i < strbu2.length(); i++) {
			int index=strbu1.indexOf(""+strbu2.charAt(i));
			if(index>-1) {
				strbu1.delete(index, index+1);
			}else {
				flag=false;
				break;
			}
		}
		return flag;
	}

	public static void main(String[] args) {
		System.out.println(scramble("rkqodlw", "world"));
		System.out.println(scramble("cedewaraaossoqqyt", "codewars"));
		System.out.println(scramble("katas", "steak"));
		System.out.println(scramble("scriptjavx","javascript"));//false
	}
}

大佬的解决方案

public class Scramblies {
    
    public static boolean scramble(String str1, String str2) {
        if (str2.length() > str1.length()) return false;
        for (String s: str2.split("")) {
          if (!str1.contains(s))  return false;
          str1 = str1.replaceFirst(s,"");
        }        
       
        return true;
    }
}

7. Number of trailing zeros of N!

[^时间]: 2019-10-13 周日

描述

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
zeros(6) = 1
# 6! = 1 * 2 * 3 * 4 * 5 * 6 = 720 --> 1 trailing zero

zeros(12) = 2
# 12! = 479001600 --> 2 trailing zeros
Hint: You're not meant to calculate the factorial. Find another way to find the number of zeros.

思路

这个题一个司马的坑！
我一开始直接求阶乘，int变量接收阶乘，发现，超出了最大范围，即使改成long型，也是一样。
所以就重新开始考虑
6！=6*5*4*3*2*1=720--->1
10!=10*9*8*7*6*5*4*3*2*1=3628800--->2
14!=14*13*12*11*10*9*8*7*6*5*4*3*2*1=87178291200--->2
15!=15*14*13*12*11*10*9*8*7*6*5*4*3*2*1=1307674368000--->3
看上面的例子，是不是发现这个司马的坑了？还是这个司马作者牛逼！

实现

我的解决方案

public class Solution {
	public static int zeros(int n) {
		int res=0;
		for(int i=5;i<=n;i*=5) {
			res+=n/i;
		}
		return res;
	}
}

大佬的解决方案

public class Solution {
  public static int zeros(int n) {
    int res = 0;
    for (int i = 5; i <= n; i *= 5) {
      res += n / i;
    }
    return res;
  }
}

8. Range Extraction

[^时间]: 2019-10-19 周六

描述

A format for expressing an ordered list of integers is to use a comma separated list of either

individual integers
or a range of integers denoted by the starting integer separated from the end integer in the range by a dash, '-'. The range includes all integers in the interval including both endpoints. It is not considered a range unless it spans at least 3 numbers. For example ("12, 13, 15-17")
Complete the solution so that it takes a list of integers in increasing order and returns a correctly formatted string in the range format.

Example:

Solution.rangeExtraction(new int[] {-6, -3, -2, -1, 0, 1, 3, 4, 5, 7, 8, 9, 10, 11, 14, 15, 17, 18, 19, 20})
# returns "-6,-3-1,3-5,7-11,14,15,17-20"

思路

这个题，刚开始理解的时候，有误区。以为连续的数字像3,2,1这种的也算，其实不是，只要1,2,3这种的才算连续的数字
两个判断1.是否连续 2.连续数字是否>=3

但是向上面这种思维方式，会把简单的问题复杂化。有时候，不能从传统的思维中去考虑。
定义一个变量flag，如果连续，则加一。不连续的时候，就追加相应的数字

实现

我的解决方案

public static String rangeExtraction(int[] arr) {
		String list="";
		int flag=0;
		for (int i = 0; i < arr.length; i++) {
			if(i==arr.length-1||arr[i]+1!=arr[i+1]) {//前后两个数不连续的时候执行
				if(flag==0) {
					list+=" "+arr[i];
				}else if(flag==1) {
					list+=" "+arr[i-1];
					list+=" "+arr[i];
					flag=0;
				}else if(flag>1) {
					list+=" "+arr[i-flag]+"-"+arr[i];
					flag=0;
				}
			}else {//前后两个数连续的时候执行
				flag++;
			}
		}
		return list.trim().replace(' ', ',');
	}

大佬的解决方案

static String rangeExtraction(final int[] array) {
        final StringBuilder sb = new StringBuilder();
        for (int i = 0; i < array.length; i++) {
            int rangeStart = array[i];
            sb.append(rangeStart);
            for (int j = i + 1; j <= array.length; j++) {
                if (j == array.length || array[j] != rangeStart + (j - i)) {
                    if (j - i >= 3) {
                        sb.append('-').append(array[j - 1]);
                        i = j - 1;
                    }
                    sb.append(',');
                    break;
                }
            }
        }
        return sb.deleteCharAt(sb.length() - 1).toString();
}

9. Weight for weight

[^时间]: 2019-10-19 周六

描述

My friend John and I are members of the "Fat to Fit Club (FFC)". John is worried because each month a list with the weights of members is published and each month he is the last on the list which means he is the heaviest.

I am the one who establishes the list so I told him: "Don't worry any more, I will modify the order of the list". It was decided to attribute a "weight" to numbers. The weight of a number will be from now on the sum of its digits.

For example 99 will have "weight" 18, 100 will have "weight" 1 so in the list 100 will come before 99. Given a string with the weights of FFC members in normal order can you give this string ordered by "weights" of these numbers?

Example:
"56 65 74 100 99 68 86 180 90" ordered by numbers weights becomes: "100 180 90 56 65 74 68 86 99"

When two numbers have the same "weight", let us class them as if they were strings and not numbers: 100 is before 180 because its "weight" (1) is less than the one of 180 (9) and 180 is before 90 since, having the same "weight" (9), it comes before as a string.

All numbers in the list are positive numbers and the list can be empty.

Notes
it may happen that the input string have leading, trailing whitespaces and more than a unique whitespace between two consecutive numbers
Don't modify the input
For C: The result is freed.

思路

老子不会做！

实现

我的解决方案

public static String orderWeight(String string) {
		ArrayList<String> list=new ArrayList<String>(Arrays.asList(string.split(" ")));
		String temp;
		for (int i = 0; i < list.size(); i++) {
			for(int j=0;j<list.size()-1;j++) {
				if(getWeight(list.get(j))>getWeight(list.get(j+1))) {
					temp=list.get(j);
					list.set(j, list.get(j+1));
					list.set(j+1, temp);
				}
			}
		}
		String str="";
		for (int i = 0; i < list.size(); i++) {
			str+=" "+list.get(i);
		}
		return str.trim();
	}

大佬的解决方案

public static String orderWeight(String string) {
    String[] split = string.split(" ");
    Arrays.sort(split, new Comparator<String>() {
      public int compare(String a, String b) {
        int aWeight = a.chars().map(c -> Character.getNumericValue(c)).sum();
        int bWeight = b.chars().map(c -> Character.getNumericValue(c)).sum();
        return aWeight - bWeight != 0 ? aWeight - bWeight : a.compareTo(b);
      }
    });
    return String.join(" ", split);
  }

10. Is my friend cheating?

[^时间]: 2019-10-19 周六

描述

A friend of mine takes a sequence of numbers from 1 to n (where n > 0).
Within that sequence, he chooses two numbers, a and b.
He says that the product of a and b should be equal to the sum of all numbers in the sequence, excluding a and b.
Given a number n, could you tell me the numbers he excluded from the sequence?
The function takes the parameter: n (n is always strictly greater than 0) and returns an array or a string (depending on the language) of the form:

[(a, b), ...] or [[a, b], ...] or {{a, b}, ...} or or [{a, b}, ...]
with all (a, b) which are the possible removed numbers in the sequence 1 to n.

[(a, b), ...] or [[a, b], ...] or {{a, b}, ...} or ...will be sorted in increasing order of the "a".

It happens that there are several possible (a, b). The function returns an empty array (or an empty string) if no possible numbers are found which will prove that my friend has not told the truth! (Go: in this case return nil).

(See examples of returns for each language in "RUN SAMPLE TESTS")

Examples:
removNb(26) should return [(15, 21), (21, 15)]
or

removNb(26) should return { {15, 21}, {21, 15} }
or

removeNb(26) should return [[15, 21], [21, 15]]
or

removNb(26) should return [ {15, 21}, {21, 15} ]
or

removNb(26) should return "15 21, 21 15"
or

in C:
removNb(26) should return  **an array of pairs {{15, 21}{21, 15}}**
tested by way of strings.

思路

从1-n的n个数中，找到2个数a,b,使得除去a,b,剩下的数之和与a，b之积相等

实现

我的解决方案

package source;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class RemovedNumbers {

	// 超时了
//	public static List<long[]> removNb(long n) {
//		List<long[]> list=new ArrayList<long[]>();
//		long sum = n * (1 + n) / 2;
//		for (long i = 1; i <= n; i++) {
//			for (long j = 1; j <= n; j++) {
//				if(i*j==(sum-i-j))
//					list.add(new long[] {
//						i,j
//					});	
//			}
//		}
//		// your code
//		return list;
//	}

	public static List<long[]> removNb(long n) {
		List<long[]> list = new ArrayList<>();
		long sum = n * (1 + n) / 2;
		for (long i = 1; i <= n; i++) {
			long j = (sum - i) / (i + 1);
			if (j >= 1 && j <= n && i * j == (sum - i - j)) {
				list.add(new long[] {
						i,j
				});
			}
		}
		return list;
	}

	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		int n = input.nextInt();
		System.out.println(removNb(n));
	}
}

大佬的解决方案

import java.util.LinkedList;

public class RemovedNumbers {
  /*
  We desire: ab = 1 + ... + n - a - b
  Take advantage of b = sum - a
                        -------
                         a + 1
  */
  public static LinkedList<long[]> removNb(long n) {
    LinkedList<long[]> numbers = new LinkedList<long[]>();
    long sum = (n * n + n) / 2;
    for (long a = 1; a < n; a++) {
      double b = (sum - a) / (double) (a + 1);
      if (b <= n && b % 1 == 0) {
        numbers.add(new long[] {a, (long) b});
      }
    }
    return numbers;
  }
}

我居然发现我的思路，跟大佬的思路是一样的，看来我也是大佬了，嘎嘎嘎

11. Longest Common Subsequence

[^时间]: 2019-10-27 周日

描述

Write a function called LCS that accepts two sequences and returns the longest subsequence common to the passed in sequences.

Subsequence
A subsequence is different from a substring. The terms of a subsequence need not be consecutive terms of the original sequence.

Example subsequence
Subsequences of "abc" = "a", "b", "c", "ab", "ac", "bc" and "abc".

LCS examples
Solution.lcs("abcdef", "abc") => returns "abc"
Solution.lcs("abcdef", "acf") => returns "acf"
Solution.lcs("132535365", "123456789") => returns "12356"
Notes
Both arguments will be strings
Return value must be a string
Return an empty string if there exists no common subsequence
Both arguments will have one or more characters (in JavaScript)
All tests will only have a single longest common subsequence. Don't worry about cases such as LCS( "1234", "3412" ), which would have two possible longest common subsequences: "12" and "34".
Note that the Haskell variant will use randomized testing, but any longest common subsequence will be valid.

Note that the OCaml variant is using generic lists instead of strings, and will also have randomized tests (any longest common subsequence will be valid).

Tips
Wikipedia has an explanation of the two properties that can be used to solve the problem:

First property
Second property

思路

这个问题，soeasy!就是两个字符串比较共有的最长的子串呗

实现

我的解决方案

大佬的解决方案

12. Is my friend cheating?

[^时间]: 2019-10-27 周日

描述

思路

实现

我的解决方案

大佬的解决方案

13. Is my friend cheating?

[^时间]: 2019-10-27 周日

描述

思路

实现

我的解决方案

大佬的解决方案

招聘算法题

反转链表

输入一个链表，反转链表后，输出新链表的表头。

public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head==null)
            return null;
        ListNode pre=null;
        ListNode next=null;
        while(head!=null){
            next=head.next;
            head.next=pre;
            pre=head;
            head=next;
        }
        return pre;
    }
}