31 October 2019
LeetCode(54) -- 1184, 1185, 1189, 1207, 1217, 1
by Jerry Zhang
P1184. Distance Between Bus Stops (Easy)
环形公交线路，一个有n个公交站，从0到n-1。第i个公交站到第（i+1）% n个公交站之间的距离为distance[i]。 现在给一个起始站和一个到达站，问它们之间的最短距离是多少。也就是说，从这个环形的哪边走更近。
我的思路
从两边分别加，看到终点站后两个和哪个大。思路很简单，主要是代码实现。
我的代码
class Solution {
public int distanceBetweenBusStops(int[] distance, int start, int destination) {
int sum1 = 0, sum2 = 0;
int n = distance.length;
for (int i = start; i != destination; i = (i + 1) % n) {
sum1 += distance[i];
}
for (int i = (start - 1 + n) % n; i != (destination - 1 + n) % n; i = (i - 1 + n) % n) {
sum2 += distance[i];
}
return Math.min(sum1, sum2);
}
}
100%
最优解
class Solution {
public int distanceBetweenBusStops(int[] distances, int start, int destination) {
int minPos = Math.min(start, destination);
int maxPos = Math.max(start, destination);
if(minPos == maxPos){
return 0;
}
int totalSum = 0;
for(int distance : distances){
totalSum = totalSum + distance;
}
int partialSum = 0;
for(int i = minPos; i < maxPos; i++){
partialSum = partialSum + distances[i];
}
return Math.min(partialSum, totalSum - partialSum);
}
}
这个方法比较好，先把总和算出来，这样就不必像我一样找bug了。。。反向求和时容易出bug
P1185. Day of the Week (Easy)
给年月日，返回这一天是周几
我的思路
用自带的函数，或者自己算。
我的代码
public class E_1185_DayoftheWeek {
public String dayOfTheWeek(int day, int month, int year) {
String monthString = month < 10 ? "0" + month : String.valueOf(month);
String dayString = day < 10 ? "0" + day : String.valueOf(day);
String[] day_of_week = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};
SimpleDateFormat originalFormat = new SimpleDateFormat("yyyyMMdd");
Date date = null;
try {
date = originalFormat.parse(year + monthString + dayString);
} catch (ParseException e) {
e.printStackTrace();
}
Calendar c = Calendar.getInstance();
c.setTime(date);
int i = c.get(Calendar.DAY_OF_WEEK) - 1;
return day_of_week[i];
}
public static void main(String[] args) {
String s = new E_1185_DayoftheWeek().dayOfTheWeek(31, 8, 2019);
}
}
17%
最优解
class Solution {
public String dayOfTheWeek(int day, int month, int year) {
String[] week = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};
int[] daysOfMonth = {31,28,31,30,31,30,31,31,30,31,30,31};
int num = 0;
for(int i = 1971;i<year;i++){
if(i % 4 == 0) num += 366;
else num += 365;
}
if(year % 4 == 0) daysOfMonth[1] = 29;
for(int i = 0;i<month-1;i++){
num += daysOfMonth[i];
}
num += day - 1;
return week[(num + 5)%7];
}
}
算出来从1971年1月1日到这一天一共过了几天，然后再算是周几。
P1189. Maximum Number of Balloons (Easy)
一个长字符串，用其中的字母能组成多少个”balloon”?
我的思路
做字母统计表，然后依次用balloon消耗它。直到无法消耗为止。
我的代码
class Solution {
public int maxNumberOfBalloons(String text) {
int[] count = new int[26];
for (char c : text.toCharArray()) {
count[c - 'a']++;
}
int ans = 0;
while (true) {
if (count[1] < 1) {
break;
}
count[1]--;
if (count[0] < 1) {
break;
}
count[0]--;
if (count[11] < 2) {
break;
}
count[11] = count[11] - 2;
if (count[14] < 2) {
break;
}
count[14] = count[14] - 2;
if (count[13] < 1) {
break;
}
count[13]--;
ans++;
}
return ans;
}
}
100%
最优解
class Solution {
public int maxNumberOfBalloons(String text) {
int[] t1 = new int[26];
for (char c : text.toCharArray()) {
t1[c - 97] += 1;
}
return Math.min(Math.min(Math.min(Math.min(t1['b' - 97], t1['a' - 97]), t1['l' - 97]/2), t1['o' - 97]/2), t1['n' - 97]);
}
}
找出这些数的最小值就行，不需要像我那样真的使用它们。短板效应就可以确定最多能组成几个balloon。
值得学习。
P1207. Unique Number of Occurrences (Easy)
一个整数数组，判断每个数字出现的次数是否都不相同。
我的思路
数的范围从-1000到1000，一共2001个数，所以统计每个数出现的次数，然后再写进另一个统计boolean数组中，如果已经出现过，那说明失败了。
我的代码
class Solution {
public boolean uniqueOccurrences(int[] arr) {
int[] count = new int[2001];
for (int i : arr) {
count[i+1000]++;
}
boolean[] exist = new boolean[1000];
for (int i : count) {
if (i > 0) {
if (exist[i - 1]) {
return false;
}
exist[i - 1] = true;
}
}
return true;
}
}
99%
最优解
class Solution {
public boolean uniqueOccurrences(int[] arr) {
int[] resArr = new int[arr.length];
int[] countArr = new int[2001];
for (int num : arr) {
int count = countArr[num + 1000]++;
if (count > 0)
resArr[count]--;
resArr[count + 1]++;
}
for (int a : resArr) {
if (a > 1) {
return false;
}
}
return true;
}
}
思路差不多。用哪个都可以。
P1217. Play with Chips (Easy)
有一些筹码，摆放在数轴上的某一些位置。比如[2,2,2,3,3]就是指第一个筹码放在2这个位置，第二个筹码放在2这个位置，第三个筹码放在2这个位置，第四个筹码放在3这个位置，第五个筹码放在3这个位置。（话说这样表示真的很奇怪，我看了很久才明白）
向左或向右移动两步是0成本的，移动1步是1个成本。求：把所有的筹码移动到一起，至少需要多少成本？
我的思路
首先要考虑的一个问题就是，最终想把筹码移动到哪里？由于移动2步是免费的，所以无论它们在哪里，都可以免费移动到0或者1这两个位置。然后就看哪个数比较小，就把它再移动到较多的位置去。
我的代码
class Solution {
public int minCostToMoveChips(int[] chips) {
int even = 0, odd = 0;
for (int chip : chips) {
if ((chip & 1) == 0) {
even++;
} else {
odd++;
}
}
return Math.min(even, odd);
}
}
100%
最优解
class Solution {
public int minCostToMoveChips(int[] chips) {
int oddPosCount = 0;
int evenPosCount = 0;
for (int pos : chips) {
if (pos % 2 == 0) {
evenPosCount += 1;
} else {
oddPosCount += 1;
}
}
return Math.min(oddPosCount, evenPosCount);
}
}
P1. Two Sum (Easy)
在一个数组中，找出两个数之和等于目标值的这两个数的坐标。
最优解
class Solution {
public int[] twoSum(int[] nums, int target) {
int max = 2047;
int [] store = new int[max + 1];
for (int i = 0 ; i < nums.length; i ++) {
int diff = (target - nums[i]) & max;
if (store[diff] != 0) {
return new int[]{store[diff] - 1, i};
}
store[nums[i] & max] = i + 1;
}
throw new RuntimeException("no number found");
}
}
跟2047做&运算，相当于除以2048的余数。注意：如果是负数的话，要先加一个2048。 这个方法其实是在赌所有的数都是0到2047之间的数。如果超过这个范围，其实是有bug的。 在该范围内，做一个统计表，用来记录所有出现过的数的索引。
tags: LeetCode