Code – 第145页

PAT 乙级 1005. 继续(3n+1)猜想 (25) Java版

卡拉兹(Callatz)猜想已经在1001中给出了描述。在这个题目里，情况稍微有些复杂。

当我们验证卡拉兹猜想的时候，为了避免重复计算，可以记录下递推过程中遇到的每一个数。例如对n=3进行验证的时候，我们需要计算3、5、8、4、2、1，则当我们对n=5、8、4、2进行验证的时候，就可以直接判定卡拉兹猜想的真伪，而不需要重复计算，因为这4个数已经在验证3的时候遇到过了，我们称5、8、4、2是被3“覆盖”的数。我们称一个数列中的某个数n为“关键数”，如果n不能被数列中的其他数字所覆盖。

现在给定一系列待验证的数字，我们只需要验证其中的几个关键数，就可以不必再重复验证余下的数字。你的任务就是找出这些关键数字，并按从大到小的顺序输出它们。

输入格式：每个测试输入包含1个测试用例，第1行给出一个正整数K(<100)，第2行给出K个互不相同的待验证的正整数n(1<n<=100)的值，数字间用空格隔开。

输出格式：每个测试用例的输出占一行，按从大到小的顺序输出关键数字。数字间用1个空格隔开，但一行中最后一个数字后没有空格。

输入样例：

6
3 5 6 7 8 11

1 2	6 3 5 6 7 8 11

输出样例：

7 6

7 6

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.TreeSet;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int k = in.nextInt();
		int[] n = new int[k];
		TreeSet[] treeSets = new TreeSet[k];
		for (int i = 0; i < k; i++) {
			n[i] = in.nextInt();
			treeSets[i] = new TreeSet<Integer>(getNumber(n[i]));
		}
		in.close();
		
		LinkedList<Integer> list = new LinkedList<Integer>();
		for (int i = 0; i < k; i++) {
			if (isMajor(n[i], treeSets, i)) {
				list.add(n[i]);
			}
		}
		
		int[] array = new int[list.size()];
		for (int i = 0; i < array.length; i++) {
			array[i] = list.get(i);
		}
		
		Arrays.sort(array);
		
		for (int i = array.length - 1; i > 0; i--) {
			System.out.print(array[i] + " ");
		}
		System.out.print(array[0]);
	}
	
	public static boolean isMajor(int n, TreeSet[] treeSets, int index) {
		for (int i = 0; i < treeSets.length; i++) {
			if (i != index && treeSets[i].contains(n)) {
				return false;
			}
		}
		return true;
	}
	public static TreeSet<Integer> getNumber(int n) {
		TreeSet<Integer> treeSet = new TreeSet<Integer>();
		treeSet.add(n);
		while (n != 1) {
			if (n % 2 == 0) {
				n = n / 2;
			} else {
				
				n = (3 * n + 1) / 2;
			}
			
			treeSet.add(n);
		}
		return treeSet;
	}
}

import java.util.Arrays;

import java.util.LinkedList;

import java.util.Scanner;

import java.util.TreeSet;

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int k = in.nextInt();

int[] n = new int[k];

TreeSet[] treeSets = new TreeSet[k];

for (int i = 0; i < k; i++) {

n[i] = in.nextInt();

treeSets[i] = new TreeSet<Integer>(getNumber(n[i]));

}

in.close();

LinkedList<Integer> list = new LinkedList<Integer>();

for (int i = 0; i < k; i++) {

if (isMajor(n[i], treeSets, i)) {

list.add(n[i]);

}

int[] array = new int[list.size()];

for (int i = 0; i < array.length; i++) {

array[i] = list.get(i);

}

Arrays.sort(array);

for (int i = array.length - 1; i > 0; i--) {

System.out.print(array[i] + " ");

}

System.out.print(array[0]);

}

public static boolean isMajor(int n, TreeSet[] treeSets, int index) {

for (int i = 0; i < treeSets.length; i++) {

if (i != index && treeSets[i].contains(n)) {

return false;

}

return true;

}

public static TreeSet<Integer> getNumber(int n) {

TreeSet<Integer> treeSet = new TreeSet<Integer>();

treeSet.add(n);

while (n != 1) {

if (n % 2 == 0) {

n = n / 2;

} else {

n = (3 * n + 1) / 2;

}

treeSet.add(n);

}

return treeSet;

}

PAT 乙级 1002. 写出这个数 (20) Java版

读入一个自然数n，计算其各位数字之和，用汉语拼音写出和的每一位数字。

输入格式：每个测试输入包含1个测试用例，即给出自然数n的值。这里保证n小于10¹⁰⁰。

输出格式：在一行内输出n的各位数字之和的每一位，拼音数字间有1 空格，但一行中最后一个拼音数字后没有空格。

输入样例：

1234567890987654321123456789

1	1234567890987654321123456789

输出样例：

yi san wu

yi san wu

import java.util.*;
public class Main {
public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    String n = in.nextLine();
    in.close();

    int sum = 0;
    for (int i = 0; i < n.length(); i++) {
      sum += n.charAt(i) - '0';
    }

    Stack<String> stack = new Stack<>();
    String[] s = {"ling", "yi", "er", "san", "si", "wu", "liu", "qi", "ba", "jiu"};
    do {
      stack.push(s[sum % 10]);
      sum /= 10;
    } while (sum != 0);

    System.out.print(stack.pop());
    while (!stack.isEmpty()) {
      System.out.print(" " + stack.pop());
    }
  }
}

import java.util.*;

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

String n = in.nextLine();

in.close();

int sum = 0;

for (int i = 0; i < n.length(); i++) {

sum += n.charAt(i) - '0';

}

Stack<String> stack = new Stack<>();

String[] s = {"ling", "yi", "er", "san", "si", "wu", "liu", "qi", "ba", "jiu"};

do {

stack.push(s[sum % 10]);

sum /= 10;

} while (sum != 0);

System.out.print(stack.pop());

while (!stack.isEmpty()) {

System.out.print(" " + stack.pop());

}

使用Genymotion Android模拟器无法连接电脑本机的服务器

在Android Virtual Device Manager里面创建的Android虚拟机连接本机服务器的ip地址是10.0.2.2。千万不要用localhost或者127.0.0.1，localhost和127.0.0.1是指本机（这里指Android虚拟机），所以localhost和127.0.0.1并不能访问到电脑本机的服务器。

如果你是使用Genymotion模拟器来作为Android的虚拟设备，那么访问电脑本机的服务器地址是10.0.3.2。

Android Device Monitor 的 File Explorer 打开一片空白，不显示文件

据说这是一个bug，在Android 7 (API 24+)里面会出现，已经有人把反馈这个问题https://code.google.com/p/android/issues/detail?id=229628了，相信下个版本应该就能解决了吧。

LeetCode 526. Beautiful Arrangement

526. Beautiful Arrangement
Suppose you have N integers from 1 to N. We define a beautiful arrangement as an array that is constructed by these N numbers successfully if one of the following is true for the ith position (1 ≤ i ≤ N) in this array:

The number at the ith position is divisible by i.
i is divisible by the number at the ith position.
Now given N, how many beautiful arrangements can you construct?

Example 1:
Input: 2
Output: 2
Explanation:

The first beautiful arrangement is [1, 2]:

Number at the 1st position (i=1) is 1, and 1 is divisible by i (i=1).

Number at the 2nd position (i=2) is 2, and 2 is divisible by i (i=2).

The second beautiful arrangement is [2, 1]:

Number at the 1st position (i=1) is 2, and 2 is divisible by i (i=1).

Number at the 2nd position (i=2) is 1, and i (i=2) is divisible by 1.
Note:
N is a positive integer and will not exceed 15.

题目大意：N个数1～N，求它有多少种排列方式，满足：对于每一位，i位上的数字能被i整除，或者i能被i位上的数字整除～
分析：深度优先搜索，从N开始一直到0，用visit标记当前元素是否访问过，当当前下标为1的时候表示当前深度优先的一条路径满足条件，result+1，否则遍历visit数组看有没有没被访问过的元素，如果满足(i % index == 0 || index % i == 0)就标记为已经访问过，然后继续向下遍历dfs(index-1)～最后返回result的结果～

class Solution {
public:
    int countArrangement(int N) {
        visit.resize(N+1);
        dfs(N);
        return result;
    }
private:
    int result = 0;
    vector<bool> visit;
    void dfs(int index) {
        if (index == 1) {
            result++;
            return;
        }
        for (int i = 1; i < visit.size(); i++) {
            if (visit[i] == false && (i % index == 0 || index % i == 0)) {
                visit[i] = true;
                dfs(index-1);
                visit[i] = false;
            }
        }
    }
};

class Solution {

public:

int countArrangement(int N) {

visit.resize(N+1);

dfs(N);

return result;

}

private:

int result = 0;

vector<bool> visit;

void dfs(int index) {

if (index == 1) {

result++;

return;

}

for (int i = 1; i < visit.size(); i++) {

if (visit[i] == false && (i % index == 0 || index % i == 0)) {

visit[i] = true;

dfs(index-1);

visit[i] = false;

}

};

LeetCode 525. Contiguous Array

525. Contiguous Array
Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

Example 1:
Input: [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.
Example 2:
Input: [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.
Note: The length of the given binary array will not exceed 50,000.

题目大意：给一个二进制数组，找最长的连续子数组，要求子数组里面的0和1的个数相等～
分析：0和1数组，可以考虑把0换成-1，变成-1和0数组，那么本质上就是找是否有下标从i～j的总和为0的子数组～
令map保存sum和sum对应的下标的值，遍历数组每次计算数组当前的sum，如果当前sum之前已经出现过，比如说之前有过一个sum = 2，现在又sum = 2了，说明在第一次sum等于2的时候，它前面所有元素加起来总和是2，那么在它前面去掉2个元素1就能满足0，同理当前的sum = 2也可以通过去掉最前面的2个元素1使sum = 0，所以看看i – m[sum]是否比之前的最大值大，如果比之前最大值大就更新最大值～

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int result = 0, sum = 0;
        for (int i = 0; i < nums.size(); i++)
            if (nums[i] == 0) nums[i] = -1;
        map<int, int> m;
        m[0] = -1;
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            if (m.find(sum) != m.end())
                result = max(result, i - m[sum]);
            else
                m[sum] = i;
        }
        return result;
    }
};

class Solution {

public:

int findMaxLength(vector<int>& nums) {

int result = 0, sum = 0;

for (int i = 0; i < nums.size(); i++)

if (nums[i] == 0) nums[i] = -1;

map<int, int> m;

m[0] = -1;

for (int i = 0; i < nums.size(); i++) {

sum += nums[i];

if (m.find(sum) != m.end())

result = max(result, i - m[sum]);

else

m[sum] = i;

}

return result;

}

};