博客

1. 查找有效服务
   
   （凭记忆描叙）有一系列的服务，例如a1,a2,a3,…等，a1-a2表示a1依赖a2，如果服务a2出错，那么a1也就不正常了，假设a1-a2,a2-a3, a3出错，或导致a1,a2都不正常，但如果只是a1出错，不会影响a2.
   
   输入的第一行是依赖关系，第二行是出错的服务，以逗号隔开，例如：
   
   输入：
   
   a1-a2,a3-a4,a5-a6
   
   a2,a5

输出(能正常运行的服务，按关系列表前后顺序）

a3,a4,a6

如果没有存活的服务，打印error

算法分析：

算法的关键点是要注意传递依赖关系，例如a1-a2,a2-a3这种。

算法描叙：在出错列表中，选择第一个出错服务ai，查找依赖列表，将所有依赖ai的关系找出来，例如aj-ai，将ai设置为ERROR（flag），并把aj加入到出错列表，知道所有错误服务都已查询，将关系列表中存活的服务打印出来即可。

package test;

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Set;
import java.util.HashSet;

public class Main {
	static final String flag = "error";
	static class Relation{
		String node;
		String rNode;
		public Relation(String node, String rNode) {
			this.node = node;
			this.rNode = rNode;
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String relations = sc.nextLine();
		String errors = sc.nextLine();
		sc.close();
		long startTime = System.currentTimeMillis(); 
		ArrayList<String> errList = new ArrayList<>();
		Collections.addAll(errList, errors.split(","));
		ArrayList<Relation> rList = new ArrayList<>();
		for(String relation:relations.split(",")) {
			String rStr[] = relation.split("-");
			rList.add(new Relation(rStr[0], rStr[1]));
		}
		Set<String> checked = new HashSet<>();
		for(int i=0; i<errList.size(); ++i) {
			String errNode = errList.get(i);
			if(checked.contains(errNode)) {
				continue;
			}
			checked.add(errNode);
			for(int j=0;j<rList.size();) {
				Relation r = rList.get(j);
				if(r.node.equals(errNode)) {
					r.node = flag;
					++j;
				} else if(r.rNode.equals(errNode)){
					if(!r.node.equals(flag)) {
						errList.add(r.node);
					}
					rList.remove(j);
				} else {
					++j;
				}
			}
		}
		StringBuilder sb = new StringBuilder();
		Set<String> exist = new HashSet<>();
		for(int i=0;i<rList.size(); ++i) {
			Relation r = rList.get(i);
			if(!r.node.equals(flag)) {
				addNode(r.node, exist, sb);
			}
			addNode(r.rNode, exist, sb);
		}
		System.out.println(sb.toString());
		System.out.println("cost:" + (System.currentTimeMillis() - startTime));
	}
	
	public static void addNode(String node, Set<String> exist, StringBuilder sb) {
		if(!exist.contains(node)) {
			sb.append(node);
			sb.append(",");
			exist.add(node);
		}
	}
}

注：我这没考虑结果为空的情况

2. 度假天数
   
   （凭记忆描叙）某人打算去欧洲旅行，然后给定一个数组，表示某天可以去旅游的景点，例如，[1,2,1,2,3,7,2,1]:
   
   a[0] = 1
   
   a[1] = 2
   
   a[2] = 1
   
   a[3] = 2
   
   a[4] = 7
   
   a[5] = 2
   
   a[6] = 1
   
   我们可以看到，如果从第一天开始（序号为0），到第五天就可以看完所有景点，总共需要5天时间，但是如果从第三天开始，那么只需要三天就可以看完所有景点。

输入，给定一个数组，值为1~200，

输出，看完素有景点需要的最少天数（必须是连续的）

算法描叙：用map<Integer, integer>来计算，前者表示景点的数，后者表示看过该景点的次数，并用count来记录已看过的景点个数，用指针begin表示起始的日期，当count=n（总共的景点个数）时，begin到i当前的索引天数就是满足要求的一个窗口，然后移动窗口，计数减一，查找下一个窗口：

	static int findSortestDaily(int[] arr) {
		Map<Integer, Integer> map = new HashMap<>();
		for(int a:arr) {
			map.put(a, 0);
		}
		int goal = map.size();
		
		int begin=0;
		int count=0;
		int min = goal;
		for(int i=0;i<arr.length; ++i) {
			int a = arr[i];
			if(map.get(a) == 0) {
				map.put(a, 1);
				++count;
				if(count == goal) {
					while(count == goal) {
						int b = arr[begin];
						int tmp = map.get(b) -1;
						map.put(b, tmp);
						if(tmp == 0) {
							--count;
						}
						++begin;
					}
					min = Math.min(min, i - begin + 2);
				}
			} else {
				int tmp = map.get(a) + 1;
				map.put(a, tmp);
			}
		}
		
		return min;
	}

3. 打印所欲有效括号
   
   输入一个整数，打印出所有有效的括号组合，例如
   
   n=1, 输出
   
   （）
   
   n=2，输出：
   
   (()),()()

算法简单，找到规律就行，不解释，直接上代码：

	static ArrayList<String> getComp(int n) {
		ArrayList<String> res = new ArrayList<>();
		if(n < 1) {
			return res;
		}
		if(n == 1) {
			res.add("()");
		} else if(n == 2) {
			res.add("(())");
			res.add("()()");
		} else {
			ArrayList<String> subs = getComp(n-1);
			for(String sub: subs) {
				res.add("(" + sub + ")");
			}
			Set<String> set = new HashSet<>();
			for(String sub: subs) {
				String tmp = "()" + sub;
				if(!set.contains(tmp)) {
					res.add(tmp);
					set.add(tmp);
				}
				tmp = sub + "()";
				if(!set.contains(tmp)) {
					res.add(tmp);
					set.add(tmp);
				}
			}
			set.clear();
			subs.clear();
		}
		return res;
	}

4. 两数之和
   
   给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

	static int[] fun(int[] nums, int target) {
		int len=nums.length;
		Map<Integer, Integer> map = new HashMap<>();
		for(int i=0; i<len; i++) {
			if(map.containsKey(nums[i])) {
				int[] res = new int[2];
				res[0] = map.get(nums[i]);
				res[1] = i;
				return res;
			} else {
				int diff = target - nums[i];
				map.put(diff, i);
			}
		}
		return new int[0];
	}

5。 查找重复数

	static int findDup(int nums[]) {
		int px=0;
		int py=0;
		do {
			px = nums[px];
			py = nums[nums[py]];
		}
		while(px != py);
		px = 0;
		while(px != py) {
			px = nums[px];
			py = nums[py];
		}
		return px;
	}

6. 计算降雨量

	static int findTrap(int height[]) {
		int left = 0;
		int right = height.length - 1;
		int sum = 0;
		int leftMax = 0;
		int rightMax = 0;
		while(left < right) {
			leftMax = Math.max(leftMax, height[left]);
			rightMax = Math.max(rightMax, height[right]);
			if(height[left] < height[right]) {
				sum += (leftMax - height[left++]);
			} else {
				sum += (rightMax - height[right--]);
			}
		}
		return sum;
	}