Array
448.找出数组中所有消失的数
要求：整型数组取值为 1 ≤ a[i] ≤ n，n是数组大小，一些元素重复出现，找出[1,n]中没出现的数，实现时时间复杂度为O(n)，并不占额外空间
思路1：（discuss）用数组下标标记未出现的数，如出现4就把a[3]的数变成负数，当查找时判断a的正负就能获取下标
tips：注意数组溢出
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> disList = new ArrayList<Integer>();
//用数组下标来记录出现过的数
for (int i = 0; i < nums.length; i++) {
int item = Math.abs(nums[i]) - 1;
//判断是否已经出现过
if (nums[item] > 0) {
nums[item] = -nums[item];
}
}
//把仍然是正数所对应的下标加入数组列表中
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) {
disList.add(i + 1);
}
}
return disList;
}
思路2：（discuss）下标标记数，但把出现过的数用作下标，然后此下标对应的数+n
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> disList = new ArrayList<Integer>();
int n = nums.length;
//用数组下标来记录出现过的数
for (int i = 0; i < nums.length; i++) {
nums[(nums[i] - 1) % n] += n;
}
//把a[i]小于n时的i+1加入数组列表中
for (int i = 0; i < nums.length; i++) {
if (nums[i] <= n) {
disList.add(i + 1);
}
}
return disList;
}
思路3：（discuss）整理数组，目的就是把数字与下标对应，整理后下标与数字不对应就证明此数消失，此方法称为数组原地实现（只改变顺序不改变值）
public List<Integer> findDisappearedNumbers(int[] nums) {
for (int i = 0; i < nums.length; i++) {
while (nums[i] != i + 1 && nums[i] != nums[nums[i] - 1]) {
int tmp = nums[i];
nums[i] = nums[tmp - 1];
nums[tmp - 1] = tmp;
}
}
List<Integer> res = new ArrayList<Integer>();
for (int i = 0; i < nums.length; i++) {
if (nums[i] != i + 1) {
res.add(i + 1);
}
}
return res;
}
2016-12-14
442.找出数组重复的数
要求与448类似
思路1：（自写一次AC）还是用下标标记，每出现一次，相应下标的数+n，检索时搜大于2n的就重复两次，还能检测出现次数大于两次的情况
public List<Integer> findDuplicates(int[] nums) {
List<Integer> dupList = new ArrayList<Integer>();
if (nums == null || nums.length == 0) {
return dupList;
}
int n = nums.length;
//出现一次就把相应下标所指整数+n
for (int i = 0; i < n; i++) {
nums[(nums[i] - 1) % n] += n;
}
for (int i = 0; i < n; i++) {
if (nums[i] > 2*n) {
dupList.add(i + 1);
}
}
return dupList;
}
思路2：（discuss）用正负法，巧用if的位置，但只适合出现两次，注意Math.abs用了两次（另：再遍历一次+Math.abs可恢复原数据）
public List<Integer> findDuplicates(int[] nums) {
List<Integer> dupList = new ArrayList<Integer>();
if (nums == null || nums.length == 0) {
return dupList;
}
for (int i = 0; i < nums.length; i++) {
//获得原下标
int item = Math.abs(nums[i]) - 1;
//只有出现过一次并且item一样才会满足
if (nums[item] < 0) {
dupList.add(Math.abs(item + 1));
}
nums[item] = -nums[item];
}
return dupList;
}
2016-12-14
414.第三大的数
要求：给出非空整型数组，返回第三大的数；若不存在，则返回最大数。时间复杂度要为O(n)
思路1： （discuss）尝试多次才成功，定义前三大数，并用continue跳出循环排除重复的情况，用右移插入数，判断好是否到第三大
warn：想好如何定义前三大的数，若定义为Integer.MIN_VALUE，输入为-2147483648时出错，可以投机定义为long类型
public int thirdMax(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
//创建三个变量存储前三大的数
long max, mid, min;
max = mid = min = Long.MIN_VALUE;
//判断第三个数是否赋值
int count = 0;
for (int x : nums) {
//防止重复输入,continue跳出本次循环
if (x == max || x == mid) {
continue;
}
//x大于max则三个变量都向右移
if (x > max) {
min = mid;
mid = max;
max = x;
count++;
} else if (x > mid) {
min = mid;
mid = x;
count++;
} else if (x >= min) {
min = x;
count++;
}
}
if (count >= 3) {
return (int)min;
}
return (int)max;
}
思路2： （discuss）使用TreeSet特性，有序且不能重复，当size()大于3时去掉第一位，小于3时输出最大值，时间复杂度为O(nlog3)
public int thirdMax(int[] nums) {
TreeSet<Integer> set = new TreeSet<Integer>();
for (int num : nums) {
set.add(num);
//超过3个则去除
if (set.size() > 3) {
set.remove(set.first());
}
}
//少于3个输出最大值
return set.size() < 3 ? set.last() : set.first();
2016-12-15
283.移动零
要求：把数组中的0都放在末尾，且保持其他数的相对位置
思路1： （自写一次AC）从末尾开始判断是否为0，是0就与旁边交换，直到旁边的不是0为止(24ms)
tips：注意超过数组长度
public void moveZeroes(int[] nums) {
for (int i = nums.length - 1; i >= 0; i--) {
if (nums[i] == 0) {
int j = i;
while (j < nums.length - 1 && nums[j + 1] != 0) {
nums[j] = nums[j + 1];
nums[j + 1] = 0;
j++;
}
}
}
}
思路2： （discuss）把非0数放在头，其余位置补齐0(0ms)
public void moveZeroes(int[] nums) {
int nonzero = 0;
for (int num : nums) {
if (num != 0) {
nums[nonzero] = num;
nonzero++;
}
}
//补全0
while (nonzero < nums.length) {
nums[nonzero] = 0;
nonzero++;
}
}
思路3： （discuss）一指针一直动判断是否为0，另一指针停留在非0头部的下一位处等待非0数的出现，从而进行交换(0ms)
public void moveZeroes(int[] nums) {
//指向非0数的指针
int j = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
int temp = nums[j];
nums[j] = nums[i];
nums[i] = temp;
j++;
}
}
}
2016-12-15
268.消失的数
要求：数组包含n个数，从0...n取值，找出缺失的那个值，时间复杂度要线性，空间复杂度恒定
思路1： （九章答案+自己想）把下标和值对应起来，等于是排序，然后判断下标和值不同的就是缺失项（对应448的思路3）
warn：记得用while，直到下标和值能对应，由于没有n这个下标，所以要排除这种情况，前面的都没缺失就返回n
public int missingNumber(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
//先排除n的情况，因为超出了长度
while (nums[i] != i && nums[i] < n) {
int t = nums[i];
nums[i] = nums[t];
nums[t] = t;
}
}
for (int i = 0; i < n; i++) {
if (nums[i] != i) {
return i;
}
}
return n;
}
思路2： （discuss）利用数学，比如求和，下标与值求异或（a ^ b ^ b = a，剩下单个的）
求和法：不缺失数组和（n+1项）减去缺失数组和（n项）
public int missingNumber(int[] nums) {
int n = nums.length;
int s = n * (n + 1) / 2;
int sum = 0;
for (int i = 0; i < n; i++) {
sum += nums[i];
}
return s - sum;
}
异或法：先设xor为n，数组有n时与n抵消可以输出缺失那一项，无n时就代表缺少n
public int missingNumber(int[] nums) {
//下标没有n项，所以把xor先设为n
int xor = nums.length;
for (int i = 0; i < nums.length; i++) {
xor = xor ^ i ^ nums[i];
}
//数组的值有n时与原始xor抵消，输出缺失的另一项，无n就输出n
return xor;
}
2016-12-15
238.排除自己后的乘积
要求：output数组上每个位置的值等于由原数组num除该位置外的所有数的乘积，不能使用除法，复杂度为O(n)
思路： （discuss）分成位置的两边相乘
tips：从左往右乘的时候，令output[0]为1，此后就可以把output[i - 1]作为是之前i - 1项的积，可重复利用；而从右往左时，第一个数已经是最终结果，而第二个数只需要乘一次...所以需要新的累积变量right
（其实也可以两个方向都用累积变量存储前面项的乘积，只不过左往右乘的时候可应用输出数组本身作为累积，更省空间）
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] output = new int[n];
output[0] = 1;
//从i=1开始，先算nums[i]左边数的乘积
for (int i = 1; i < n; i++) {
output[i] = output[i - 1] * nums[i - 1];
}
//新的累加值，算右边的乘积
int right = 1;
for (int i = n - 1; i >= 0; i--) {
output[i] *= right;
right *= nums[i];
}
return output;
}
2016-12-15
229.多数元素（众数）II
要求：在大小为n的数组中找出出现次数大于n / 3次的元素，用线性时间和O(1)空间
思路： （经典算法）“摩尔投票法”，这里的含义是先设置两个候选数，相同的时候就计1票，不同的时候就扣1票，当票数为0时，就换另一个候选数，并且计第1票；选好候选数之后，就真正计算各自的票数
tips：背下来思路...1、设候选数、计票器 2、确定候选数 3、真正计票 4、判断是否满足条件
warn：考虑空数组，数组长度为1，两个数相等的情况！！！
public List<Integer> majorityElement(int[] nums) {
List<Integer> res = new ArrayList<Integer>();
int n = nums.length;
if (nums == null || n == 0) {
return res;
}
if (n == 1) {
res.add(nums[0]);
return res;
}
//设2个候选数，2个对应的计票器
int number1, number2, count1, count2;
number1 = number2 = nums[0];
count1 = count2 = 0;
//挑选候选数
for (int i = 0; i < n; i++) {
if (nums[i] == number1) {
count1++;
} else if (nums[i] == number2) {
count2++;
} else if (count1 == 0) { //count减为0就换候选数
number1 = nums[i];
count1++;
} else if (count2 == 0) {
number2 = nums[i];
count2++;
} else {
count1--;
count2--;
}
}
//清空票数，计算两个候选数的真正票数
count1 = count2 = 0;
for (int i = 0; i < n; i++) {
if (nums[i] == number1) {
count1++;
}
if (nums[i] == number2) {
count2++;
}
}
//判断票数是否达到n/3以上
if (count1 > n / 3) {
res.add(number1);
}
//考虑两数相等的情况
if (count2 > n / 3 && number2 != number1) {
res.add(number2);
}
return res;
}
另：据说使用Map也行，但是空间复杂度比较大
2016-12-15
228.总结范围数
要求：数组不重复，出现连续的数列就用->表示，如0, 1, 2就变成了0->2，单个数不需改变
思路： （自写修改后AC）判断nums[i+1] == nums[i]，若等于则while循环获得范围结尾处，不等于就直接输出当前。
warn：注意数组溢出，注意数组溢出，注意数组溢出！！！考虑数组长度0，1，以及n-1位置上的情况
public List<String> summaryRanges(int[] nums) {
List<String> res = new ArrayList<String>();
int n = nums.length;
if (nums == null || n == 0) {
return res;
}
if (n == 1) {
String s = String.valueOf(nums[0]);
res.add(s);
return res;
}
for (int i = 0; i < n - 1; i++) {
if (nums[i + 1] == nums[i] + 1) {
int j = i;
while (i < n - 1 && nums[i + 1] == nums[i] + 1) {
i++;
}
String s = nums[j] + "->" + nums[i];
res.add(s);
} else {
String s = String.valueOf(nums[i]);
res.add(s);
}
}
if (nums[n - 1] != nums[n - 2] + 1) {
String s = String.valueOf(nums[n - 1]);
res.add(s);
}
return res;
}
2016-12-16
219.包含重复II
要求：给出数组和整数k，求是否在最大间隔j - i = k以内有重复数出现
思路1： （查HashSet用法后自写一次AC）根据HashSet特性，不能有重复数插入，让set长度为k + 1（头尾下标间隔为k，总共包含k + 1个数）
tips：超过长度删除数据时，虽set无序，但可根据输入数组的有序，来确定删除的是哪个数（输入nums[i]对应删除nums[i - k - 1]）
public boolean containsNearbyDuplicate(int[] nums, int k) {
if (nums == null || nums.length == 0 || k == 0) {
return false;
}
Set<Integer> set = new HashSet<Integer>();
for (int i = 0; i <nums.length; i++) {
//set长度超过k，则删除当前第1个
if (i > k) {
//set无序，但可利用数组有序
set.remove(nums[i - 1 - k]);
}
//插入不了证明重复
if (!set.add(nums[i])) {
return true;
}
}
return false;
}
思路2： （discuss）根据HashMap特性键不能重复，把数组的值当作map键，数组的下标当作map值，求长度时比较map值（对应数组下标）
tips：先判断是否已经存在再输入！！
public boolean containsNearbyDuplicate(int[] nums, int k) {
if (nums == null || nums.length == 0 || k == 0) {
return false;
}
Map<Integer, Integer> map = new HashMap();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(nums[i])) {
//get(nums[i])是找之前的
if (i - map.get(nums[i]) <= k) {
return true;
}
}
//调转键与值
map.put(nums[i], i);
}
return false;
}
2016-12-16
217.包含重复
要求：找出数组是否有重复数
思路： （自写map和set的）与219一样，比较简单，只放了map代码
public boolean containsDuplicate(int[] nums) {
if (nums == null || nums.length == 0) {
return false;
}
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(nums[i])) {
return true;
}
map.put(nums[i], i);
}
return false;
}
2016-12-16
216.组合和III
要求：用k个1-9的数，求所有加起来等于n的集合，每个集合中的元素不重复
思路： （经典算法）“BackTracking回溯算法”，满足条件就添加，不满足就继续递归
warn：背步骤...具体还没理解如何return，如何递归 backTracking：1、判断是否满足条件，是就添加并返回 2、循环：2.1、添加新循环元素 2.2、递归表达式 2.3、弹出最后一项
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> ans = new ArrayList<>();
backTracking(ans, new ArrayList<Integer>(), k, 1, n);
return ans;
}
private void backTracking(List<List<Integer>> ans, List<Integer> comb, int k, int start, int n) {
//数组中有k个数并相加为n就返回
if (comb.size() == k && n == 0) {
List<Integer> real = new ArrayList<Integer>(comb);
ans.add(real);
return;
}
for (int i = start; i <= 9; i++) {
//添加新数
comb.add(i);
//递归
backTracking(ans, comb, k, i+1, n-i);
//弹出最后一位
comb.remove(comb.size() - 1);
}
}
2016-12-17
209.最小子数组之和
要求：给出含有n个正数的数组，用最短的子数组各项加起来能够大于等于给定的正数s，若找不到则返回0
思路1： （discuss）“Two Pointers”用两个指针和一个记录最短长度的min，首先第一个指针用来叠加，第二个指针用来大于s时减去前面的数，并且更新最短长度min,时间复杂度为O(n)（虽然用了两层while）
public int minSubArrayLen(int s, int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int i = 0, j = 0, sum = 0, min = Integer.MAX_VALUE;
while (i < nums.length) {
sum += nums[i++];
while (sum >= s) {
//超过s就减去前面一位，保留最短长度
min = Math.min(min, i - j);
sum -= nums[j++];
}
}
return min == Integer.MAX_VALUE ? 0 : min;
}
思路2：（discuss）叠加和法
第一个循环先求出sums数组，其中sums[i] = sums[i - 1] + nums[i - 1]，此数组i项代表前i项的累计和；
第二个循环用二分法查找sums[i]+s的位置end，即代表sums[end] - sums[i] = s，此时子数组长度是end-i，复杂度为O(nlogn)
public int minSubArrayLen(int s, int[] nums) {
int[] sums = new int[nums.length + 1];
//求前i项和
for (int i = 1; i < sums.length; i++) {
sums[i] = sums[i - 1] + nums[i - 1];
}
int minLen = Integer.MAX_VALUE;
for (int i = 0; i < sums.length; i++) {
//二分法找累计和的差值为s的位置end
int end = binarySearch(i + 1, sums.length - 1, sums[i] + s, sums);
if (end == sums.length) break;
if (end - i < minLen) minLen = end - i;
}
return minLen == Integer.MAX_VALUE ? 0 : minLen;
}
private int binarySearch(int lo, int hi, int key, int[] sums) {
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (sums[mid] >= key){
hi = mid - 1;
} else {
lo = mid + 1;
}
}
return lo;
}
2016-12-17
189.旋转数组
要求：旋转n长度的数组，位数为k，用三种以上方法，其中最好消耗O(1)额外空间（即原地）
思路1： （九章思路+自写）假如原数组为1234567，旋转度为3，变成5671234，就从第4、5位中间（nums.length - k处）分割，进行三次首尾反转，前面1234首尾反转为4321，后面变成765，再统一首尾反转一次
warn：注意k大于数组长度的情况，用k %= nums.length解决
public void rotate(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return;
}
//防止k大于数组长度
k %= nums.length;
//由nums.length - k分割，进行三次首尾反转
reverse(nums, 0, nums.length - k - 1);
reverse(nums, nums.length - k, nums.length - 1);
reverse(nums, 0, nums.length - 1);
}
private void reverse(int[] nums, int start, int end) {
for (int i = start, j = end; i < j; i++, j--) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
思路2： （自写一次AC）创建另一数组存储，注意位置对应关系就行，由于无返回值，最后要重新赋给原数组
public void rotate(int[] nums, int k) {
int n = nums.length;
if (nums == null || n == 0) {
return;
}
k %= n;
int[] res = new int[n];
for (int i = 0; i < k; i++) {
res[i] = nums[n - k + i];
}
for (int i = k; i < n; i++) {
res[i] = nums[i - k];
}
for (int i = 0; i < n; i++) {
nums[i] = res[i];
}
}
思路3： （discuss）用数学方法（最大公因数GCD）计算反转次数，比较复杂，还没理解
public void rotate(int[] nums, int k) {
if (nums.length <= 1) {
return;
}
//step each time to move
int step = k % nums.length;
//find GCD between nums length and step
int gcd = findGcd(nums.length, step);
int position, count;
//gcd path to finish movie
for (int i = 0; i < gcd; i++) {
//beginning position of each path
position = i;
//count is the number we need swap each path
count = nums.length / gcd - 1;
for (int j = 0; j < count; j++) {
position = (position + step) % nums.length;
//swap index value in index i and position
nums[i] ^= nums[position];
nums[position] ^= nums[i];
nums[i] ^= nums[position];
}
}
}
public int findGcd(int a, int b) {
return (a == 0 || b == 0) ? a + b : findGcd(b, a % b);
}
Here use a example input array [1,2,3,4,5,6,7,8] (n = 8) to explain: 1.suppose k = 3: GCD = gcd(3,8) = 1, which means there is only one path. Count = (n / GCD) - 1 = 7, which means we need 7 swaps to finish the path. (actually for a path have x element, we need x - 1 swaps) Then we can simulate the process of the algorithm, path0(each time swap index0 element and indexPosition element): [1,2,3,4,5,6,7,8] (position = 3) -> [4,2,3,1,5,6,7,8] (position = 6) -> [7,2,3,1,5,6,4,8](position = 1) -> [2,7,3,1,5,6,4,8](position = 4) -> [5,7,3,1,2,6,4,8](position = 7) -> [8,7,3,1,2,6,4,5](position = 2) -> [3,7,8,1,2,6,4,5](position = 5) -> [6,7,8,1,2,3,4,5] -> finished, total 7 times swap. Final result [6,7,8,1,2,3,4,5] 2.suppose k = 2: Similary, GCD = 2, which means there are 2 paths. count = 3, which means we need 3 swaps to finish each path. Give the process: path0(swap index0 and position element): [1,2,3,4,5,6,7,8](position = 2) -> [3,2,1,4,5,6,7,8](position = 4) ->[5,2,1,4,3,6,7,8](position = 6) -> [7,2,1,4,3,6,5,8] -> path0 finished Then we continue processing path1(swap index1 and position element): [7,2,1,4,3,6,5,8](position = 3) -> [7,4,1,2,3,6,5,8](position = 5) -> [7,6,1,2,3,4,5,8](position = 7) ->[7,8,1,2,3,4,5,6] -> path1 finished -> all path finished we get the result [7,8,1,2,3,4,5,6]
example
2016-12-17
169.众数
要求：找出数组中出现次数超过n / 2的数，已设数组非空，并且众数肯定存在（若没此假设就要判断是否为空数组，最多的出现次数是否超过n / 2）
思路1： （自写一次AC）摩尔投票，简单
public int majorityElement(int[] nums) {
if (nums.length == 1) {
return nums[0];
}
int number = nums[0], count = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == number) {
count++;
} else if (count == 0) {
number = nums[i];
} else {
count--;
}
}
return number;
}
思路2： （discuss）排序，直接用Java内置的Arrays.sort()方法，返回n / 2位置的数
思路3： （discuss）利用HashMap，key用来表示数组的值，每增加1次，key对应的值+ 1，空间复杂度高
warn：记得map初始化<>有key, value两项
public int majorityElement(int[] nums) {
int number = 0;
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int num : nums) {
//第一次放入对应的值为1
if (! map.containsKey(num)) {
map.put(num, 1);
} else {
map.put(num, map.get(num) + 1); //之前的值+ 1
}
if (map.get(num) > nums.length / 2) {
number = num;
}
}
return number;
}
思路4： （discuss）还可以用位运算...
2016-12-17
1.两数之和
要求：给出target，从数组找出两数相加是它，并返回对应下标，假设只有一个解
思路： （自写一次AC）HashMap特性，键、值相反输入，找target - nums[i]是否存在就行
warn：循环外一定要有return
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(target - nums[i])) {
return new int[]{map.get(target - nums[i]), i};
}
map.put(nums[i], i);
}
return new int[2];
}
2016-12-21
167.两数之和II--输入有序数组
要求：数组升序排序，找出两个数能够相加等于目标数字，返回这两个数的下标，如[2, 7, 11, 15]，得到目标9，返回1和2，假设只有一个解
思路1： （有思路但写不出来）利用升序特性和two pointers，两个指针分别在首尾，首指针增大，和增大，尾指针减小，和减小
public int[] twoSum(int[] numbers, int target) {
int i = 0, j = numbers.length - 1;
int[] res = new int[2];
if (numbers == null || numbers.length < 2) {
return res;
}
while (i < j) {
int sum = numbers[i] + numbers[j];
//利用升序特性
if (sum == target) {
res[0] = i + 1;
res[1] = j + 1;
break;
} else if (sum > target) {
j--;
} else {
i++;
}
}
return res;
}
思路2： （discuss）二分查找，由于是两个数的和，把第一个数numbers[i]遍历，第二个数就在剩下的范围里面用二分查找搜target - numbers[i]，时间复杂度高
2016-12-18
162.找峰值
要求：找出数组中任意的峰值，且数组没有重复的数
思路1： （自写一次AC）二分查找，中值比右小就抛弃左边，比右大就抛弃右边，时间复杂度为O(logn)
public int findPeakElement(int[] nums) {
int low = 0;
int high = nums.length - 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (nums[mid] < nums[mid + 1]){
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
思路2： 笨方法，就是从开头遍历，看nums[i]是否同时比i + 1与i - 1大，时间复杂度为O(n)
public int findPeakElement(int[] nums) {
for (int i = 1; i < nums.length-1; i++) {
if (nums[i] > nums[i+1] && nums[i] > nums[i-1]) {
return i;
}
}
return nums.length <= 1 || nums[0] > nums[1] ? 0 : nums.length-1;
}
2016-12-18
153.旋转排序数组找最小值
要求：一排序数组在未知位置旋转，求最小值，假设数组不重复
思路： （discuss）二分查找，边界条件难找，判断nums[mid] < nums[mid - 1]证明mid是旋转点（最小点），并利用mid与low和high指向的数大小比较确定新的分界点
tips：分为三种情况，一没有旋转，二mid点在小的一边，三mid点在大的一边，考虑各种情况下边界情况应如何改变
public int findMin(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
if (nums.length == 1) {
return nums[0];
}
int low = 0;
int high = nums.length - 1;
while (low < high) {
int mid = low + (high - low) / 2;
//考虑没有旋转的情况nums[0]最小
if (mid > 0 && nums[mid] < nums[mid - 1]) {
return nums[mid];
}
if (nums[mid] >= nums[low] && nums[mid] > nums[high]) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return nums[low];
}
还有很多种边界的考虑方法，作为拓展可自己思考
2016-12-18
152.子数组的最大积
要求：找出子数组的最大乘积，子数组最少包含1个数
自写时以为排除所有负数，没考虑到负负得正...
2016-12-18
其实需要动态规划（Dynamic Programming）
2016-12-19
121.最好的时刻购买与出售股票
要求：数组中的第i个元素代表第i天股票的价格，限制只能买卖一次，而且买只能在卖之前，求最大利润
思路： （掌握思路后自写一次AC）“Dynamic Programming”，设置最低购买加个curMin来保存一直以来的最低价格，maxProfit来更新最大利润，也是第i天的“最优解”
public int maxProfit(int[] prices) {
if (prices == null || prices.length < 2) {
return 0;
}
int maxProfit = 0;
int curMin = prices[0];
for (int i = 1; i < prices.length; i++) {
//确保当前的比前面小才更新
curMin = Math.min(curMin, prices[i]);
maxProfit = Math.max(maxProfit, prices[i] - curMin);
}
return maxProfit;
}
注：还有II（不限制买卖次数）、III题，比较难
2016-12-19
118.杨辉三角形：
要求：输入行数得到对应的三角形阵列
思路： （自写但出现错误后改过来）利用上下层的关系即可，用另一数组保存上层结果
warn：每次赋值备用数组前记得清空！！！
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> ans = new ArrayList<>();
if (numRows < 1) {
return ans;
}
List<Integer> pre = new ArrayList<Integer>();
for (int i = 1; i <= numRows; i++) {
List<Integer> pas = new ArrayList<Integer>();
pas.add(1);
for (int j = 0; j < pre.size() - 1; j++) {
pas.add(pre.get(j) + pre.get(j + 1));
}
if (i > 1) {
pas.add(1);
}
ans.add(pas);
pre.clear();
pre.addAll(pas);
}
return ans;
}
2016-12-19
119.杨辉三角形II：
要求：输入特定第k行的元素
思路1： （自写一次AC）与118代码几乎一样
public List<Integer> getRow(int rowIndex) {
List<Integer> pre = new ArrayList<Integer>();
List<Integer> pas = new ArrayList<Integer>();
for (int i = 0; i <= rowIndex; i++) {
pas.clear();
pas.add(1);
for (int j = 0; j < pre.size() - 1; j++) {
pas.add(pre.get(j) + pre.get(j + 1));
}
if (i > 0) {
pas.add(1);
}
pre.clear();
pre.addAll(pas);
}
return pas;
}
思路2： （discuss）在新的一行开头插入1，然后从第2个元素（j = 1）开始计算与其下一个元素的和，并用set设为新一行的当前元素，此思路不用额外的空间，在原地添加，可应用到118题
tips：此方法code较简洁，且省空间
public List<Integer> getRow(int rowIndex) {
List<Integer> pas = new ArrayList<Integer>();
for (int i = 0; i <= rowIndex; i++) {
//在新一行的头部插入1
pas.add(0, 1);
for (int j = 1; j < pas.size() - 1; j++) {
//令j指向的为新元素
pas.set(j, pas.get(j) + pas.get(j + 1));
}
}
return pas;
}
2016-12-19
88.合并有序数组
要求：给出m长数组num1，n长数组num2，按顺序合并成m+n长的数组
思路： （没注意到数组足够长）由于nums1的数组长度是m + n，所以若在数组尾部开始赋值，不会覆盖掉nums1的内容
tips：由于在nums1内进行操作，只要保证nums2赋值完就行，第一循环条件为都没赋值完，而第二循环判断的是 是否nums2赋值完，若赋值完证明操作完毕，无需判断nums1
2016-12-19
80.去除有序数组的重复II
要求：保留重复两次，其余的删除，并返回新长度
思路1： （根据26题经验自写一次AC）设置计数器count，判断其重复次数，两次以内就继续保留下来
public int removeDuplicates(int[] nums) {
if (nums.length < 2) {
return nums.length;
}
int length = 1, count = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] == nums[i - 1]) {
count++;
if (count <= 2) {
nums[length++] = nums[i];
}
} else {
count = 1;
nums[length++] = nums[i];
}
}
return length;
}
思路2： （discuss）根据有序的优点，判断此项是否与前两项相等，就可以知道是否重复两次
public int removeDuplicates(int[] nums) {
int length = 0;
for (int num : nums) {
if (length < 2 || num != nums[length - 2]) {
nums[length++] = num;
}
}
return length;
}
2016-12-19
26.去除有序数组的重复
要求：去掉有序数组中所有重复的数，并返回新的长度，不能分配额外的空间，只能在原数组本地进行
思路： （自写没AC）思路正确，但忘记调整数组，只返回了新长度。可用长度length作为指针来更新数组
public int removeDuplicates(int[] nums) {
if (nums == null || nums.length == 0 || nums.length == 1) {
return nums.length;
}
int length = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] != nums[i - 1]) {
nums[length++] = nums[i];
}
}
return length;
}
discuss中使用foreach，省了一个指针的空间，思路一样
2016-12-19
75.排序颜色
要求：把红白蓝用0, 1, 2表示，将数组重新排序成红白蓝，且相同颜色相邻的形式
思路1： （看了follow up后自写一次AC）就是数0, 1的个数，然后按顺序赋值就行
public void sortColors(int[] nums) {
int count0 = 0, count1 = 0;
for (int num : nums) {
if (num == 0) {
count0++;
} else if (num ==1) {
count1++;
}
}
int i = 0;
while (i < count0) nums[i++] = 0;
while (i < count0 + count1) nums[i++] = 1;
while (i < nums.length) nums[i++] = 2;
}
思路2： （discuss）把0和2丢到两边，即碰到0或者2就和两边的数交换，而剩下中间的就是1
public void sortColors(int[] nums) {
int zero = 0; int two = nums.length - 1;
//遍历到2的位置即可
for (int i = 0; i <= two; i++) {
while (nums[i] == 2 && i < two) {
int temp = nums[i];
nums[i] = nums[two];
nums[two--] = temp;
}
while (nums[i] == 0 && i > zero) {
int temp = nums[i];
nums[i] = nums[zero];
nums[zero++] = temp;
}
}
}
2016-12-19
74.搜索二维矩阵
要求：矩阵的特点有一行中从小到大排列，一行的头元素大于上一行的所有元素，在矩阵中找出指定数
思路1： （自写一次AC）“二分查找思想”，选右上角的数（也可选左下角），大于target就列减，小于target就行加
warn：判断空矩阵，二维数组求列数是matrix[0].length
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0) {
return false;
}
int i = 0, j = matrix[0].length - 1;
while (i < matrix.length && j >= 0) {
if(matrix[i][j] == target) {
return true;
} else if (matrix[i][j] > target) {
j --;
} else {
i++;
}
}
return false;
}
思路2： （discuss）还是二分查找，根据条件可把其当作普通有序一维数组，其中在一维数组的位置mid可通过 / 列数，% 列数获得在二维数组的坐标
warn：判断条件是low <= high，可防止数组只有一个数的情况下无法判断
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0) {
return false;
}
int m = matrix.length, n = matrix[0].length;
int low = 0, high = m * n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (matrix[mid / n][mid % n] == target) {
return true;
} else if (matrix[mid / n][mid % n] > target) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return false;
}
2016-12-20
73.矩阵中置0
要求：凡是存在0元素，其对应的行和列上的所有元素都应为0
思路： （discuss）用第0行和第0列的元素置0来记录对应的j列（第0行第j个对应）和i行（第0列第i个对应）上的所有元素为0，但要区分它们是否本来就为0（用fr和fc），若本来就为0，则相应的0行0列也要全置为0
public void setZeroes(int[][] matrix) {
if (matrix == null || matrix.length == 0) {
return;
}
boolean fr = false, fc = false; //用来分辨第0行与第0列的元素是否本身为0
//找出矩阵中所有的0，并将其对应的第0行及第0列的元素置0
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] == 0) {
if (i == 0) fr = true;
if (j == 0) fc = true;
matrix[0][j] = 0;
matrix[i][0] = 0;
}
}
}
for (int i = 1; i < matrix.length; i++) {
for (int j = 1; j < matrix[0].length; j++) {
if (matrix[0][j] == 0 || matrix[i][0] == 0) {
matrix[i][j] = 0;
}
}
}
if (fr) {
for (int j = 0; j < matrix[0].length; j++) {
matrix[0][j] = 0;
}
}
if (fc) {
for (int i = 0; i < matrix.length; i++) {
matrix[i][0] = 0;
}
}
}
2016-12-20
66.加一
要求：数组代表一个数，越靠前权重越高
思路： （读懂题后自写一次AC）就是判断是否大于9，简单
tips：若溢出，数组长度要+ 1，新建数组默认每位都是0
public int[] plusOne(int[] digits) {
int n = digits.length;
digits[n - 1]++;
for (int i = n - 1; i > 0; i--) {
if (digits[i] > 9) {
digits[i - 1]++;
digits[i] = 0;
} else {
break;
}
}
if (digits[0] > 9) {
int[] res = new int[n + 1];
res[0] = 1;
return res;
}
return digits;
}
2016-12-20
54.螺旋矩阵
要求：给出m * n的矩阵，用螺旋顺序来返回它
思路： （discuss）用四个边界，定义每次开始与结束，分为“右->下->左->上”四步
warn：约束条件要想清楚
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> res = new ArrayList<Integer>();
if (matrix.length == 0) {
return res;
}
int rowBegin = 0;
int rowEnd = matrix.length-1;
int colBegin = 0;
int colEnd = matrix[0].length - 1;
while (rowBegin <= rowEnd && colBegin <= colEnd) {
// Traverse Right
for (int j = colBegin; j <= colEnd; j ++) {
res.add(matrix[rowBegin][j]);
}
rowBegin++;
// Traverse Down
for (int j = rowBegin; j <= rowEnd; j ++) {
res.add(matrix[j][colEnd]);
}
colEnd--;
if (rowBegin <= rowEnd) {
// Traverse Left
for (int j = colEnd; j >= colBegin; j --) {
res.add(matrix[rowEnd][j]);
}
}
rowEnd--;
if (colBegin <= colEnd) {
// Traverse Up
for (int j = rowEnd; j >= rowBegin; j --) {
res.add(matrix[j][colBegin]);
}
}
colBegin++;
}
return res;
}
2016-12-20
59.螺旋矩阵II
要求：给出n，生成1到n ^ 2的螺旋矩阵
思路： （自写一次AC）参照54题
public int[][] generateMatrix(int n) {
int[][] matrix = new int[n][n];
if (n == 0) {
return matrix;
}
int startRow = 0, startCol = 0;
int endRow = n - 1, endCol = n - 1;
int count = 1;
while (startRow <= endRow && startCol <= endCol) {
for (int j = startRow; j <= endRow; j++) {
matrix[startCol][j] = count++;
}
startCol++;
for (int i = startCol; i <= endCol; i++) {
matrix[i][endRow] = count++;
}
endRow--;
if (startCol <= endCol) {
for (int j = endRow; j >= startRow; j--) {
matrix[endCol][j] = count++;
}
}
endCol--;
if (startRow <= endRow) {
for (int i = endCol; i >= startCol; i--) {
matrix[i][startRow] = count++;
}
}
startRow++;
}
return matrix;
}
tips：方阵时，约束条件可以少一点，后两个if判断可以去掉，只判断startRow <= endRow即可
2016-12-21
48.翻转图片
要求：用n * n矩阵代替图片，把此方阵顺时针旋转90度
思路： （自写一次AC）分为两步：1、根据对角元素进行逐行逐列交换 2、把首尾列依次交换
public void rotate(int[][] matrix) {
int n = matrix.length;
if (n < 2) {
return;
}
for (int i = 0; i <= n - 2; i++) {
for (int j = i + 1; j <= n - 1; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
for (int col = 0; col < n / 2; col++) {
for (int row = 0; row < n; row++) {
int temp = matrix[row][col];
matrix[row][col] = matrix[row][n - 1 - col];
matrix[row][n - 1 - col] = temp;
}
}
}
2016-12-21
35.寻找插入位置
要求：给出有序数组，若数组中存在数target，返回对应下标，否则返回它应该插入的位置，假设无重复
思路： （自写但一次没AC）就是简单的二分查找实现
tips：约束条件为low <= high
public int searchInsert(int[] nums, int target) {
int low = 0, high = nums.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return low;
}
2016-12-21
34.寻找数的区间
要求：给出有序数组，返回目标数target所在开始到结束的区间，若不存在target则返回[-1, -1]，时间复杂度为O(logn)
思路1： （自写第二次AC）先用二分查找搜到target，然后在mid左右进行缩进，直到不是target为止，得到首末位置（虽AC但不知道满不满足复杂度）
warn：第一次没AC原因是在while循环内定义mid，导致在下一循环中mid有可能没定义
public int[] searchRange(int[] nums, int target) {
int[] res = {-1, -1};
int low = 0, high = nums.length - 1, mid = 0;
boolean ex = false;
while (low <= high) {
mid = (low + high) / 2;
if (nums[mid] == target) {
ex = true;
break;
} else if (nums[mid] > target) {
high = mid - 1;
} else {
low = mid + 1;
}
}
if (ex) {
int i = mid;
while (i > 0 && nums[i - 1] == nums[i]) {
i--;
}
res[0] = i;
int j = mid;
while (j < nums.length - 1 && nums[j + 1] == nums[j]) {
j++;
}
res[1] = j;
}
return res;
}
思路2： （discuss）用两次二分查找，找出target和target + 1第一次出现的时候，构成区间
warn：数组溢出条件，无论是||还是&&都要放在前面！
tips：开始令high = nums.length，找第一次出现时，满足nums[mid] >= target时high = mid；同理找最后一次时，满足nums[mid] <= target时low = mid
public int[] searchRange(int[] nums, int target) {
int start = firstEqual(nums, target);
if (start == nums.length || nums[start] != target) {
return new int[]{-1, -1};
}
return new int[]{start, firstEqual(nums, target + 1) - 1}; //利用有序，寻找更大的数位置
}
private int firstEqual(int[] nums, int target) {
int low = 0, high = nums.length;
while (low < high) {
int mid = (low + high) / 2;
if (nums[mid] < target) {
low = mid + 1;
} else { //找第一次出现，相等或大于target都要令high = mid
high = mid;
}
}
return low;
}
思路3： （discuss）就是按照tips所说直接找第一和最后一次出现，代码略
2016-12-21
27.去除元素
要求：给出数组和一个数，去除数组中的该数（其实就是将其放到结尾）并返回去除后数组长度，数的顺序可改变，但必须原地进行
思路1： （自写一次AC）two pointers问题，首尾一个指针，判断首部是否为val值，是的话就判断尾部是否为val，不是val就交换，是就左移直到不是val为止
public int removeElement(int[] nums, int val) {
int n = nums.length;
int i = 0, j = n - 1;
while (i <= j) {
if (nums[i] == val) {
n--;
while (j > i && nums[j] == val) {
j--;
n--;
}
nums[i++] = nums[j];
nums[j--] = val;
} else {
i++;
}
}
return n;
}
思路2： （自写一次AC）foreach方法，直接把新长度同时作为指针，不等于val值时才在头部开始赋值，较思路1简单
public int removeElement(int[] nums, int val) {
int n = 0;
for (int num : nums) {
if (num != val) {
nums[n++] = num;
}
}
return n;
}
2016-12-21
11.装最多的水
要求：把数组的下标当成横坐标，值代表纵坐标，题目求的是a(i), a(j), i, j作为端点时，容器最多装多少水（这道题真难理解...）
思路： （明白题目后一次AC）two pointers，设首尾指针i, j，找最长的边（ai大时j左移，反之i右移），并每次都算v，用Math.max与之前的比较保留较大值
public int maxArea(int[] height) {
int i = 0, j = height.length - 1;
int v = 0;
while (i < j) {
v = Math.max(v, (j - i) * Math.min(height[i], height[j]));
if (height[i] < height[j]) {
i++;
} else {
j--;
}
}
return v;
}
2016-12-21
15.三数之和
要求：找出所有a, b, c，满足a + b + c = 0的集合
错误思路：想着用HashMap，先确定第一个数，然后后面两数加起来等于nums[i]，但这样会出现重复，无法去除类似于[0, 0, 0, 0]这种情况
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i <= nums.length - 3; i++) {
if (i == 0 || nums[i] != nums[i - 1]) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int j = i + 1; j < nums.length; j++) {
if (map.containsKey(-nums[i] - nums[j])) {
List<Integer> three = new ArrayList<Integer>();
three.add(nums[i]);
three.add(-nums[i] - nums[j]);
three.add(nums[j]);
res.add(three);
}
map.put(nums[j], j);
}
}
}
return res;
}
如何改进HashMap方法才能不重复？
正确思路：（discuss）two pointers，思路和我的一样，但确定第一个数后，要判断是否与之前确定的数一样，再用两个指针可排除后面出现的重复情况，出现第一次等于0后，指针要一直跳到不重复的数为止
warn：先排序能确保用来确定的数（作为后面two pointers的和）不重复，新情况时不用new，直接用Arrays.asList();
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i <= nums.length - 3; i++) {
if (i == 0 || nums[i] != nums[i - 1]) {
int low = i + 1, high = nums.length - 1;
while (low < high) {
if (nums[low] + nums[high] == - nums[i]) {
res.add(Arrays.asList(nums[i], nums[low], nums[high]));
while (low < high && nums[low + 1] == nums[low]) low++;
while (low < high && nums[high - 1] == nums[high]) high--;
low++;
high--;
} else if (nums[low] + nums[high] < - nums[i]) {
low++;
} else {
high--;
}
}
}
}
return res;
}
2016-12-22
16.最接近的三数和
要求：找出相加和最接近目标数target的三个数，并返回它们的和，假设只存在一个解
思路：和15题一样，但不可以像它一样用while判断不重复，不然会错过了一些情况
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int res = nums[0] + nums[1] + nums[nums.length - 1];
for (int i = 0; i < nums.length - 2; i++) {
if (i == 0 || nums[i] != nums[i - 1]) {
int low = i + 1, high = nums.length - 1;
while (low < high) {
int sum = nums[i] + nums[low] + nums[high];
if (Math.abs(target - sum) < Math.abs(target - res)) {
res = sum;
if (res == target) {
return res;
}
}
if (sum > target) {
high--;
} else {
low++;
}
}
}
}
return res;
}
2016-12-22
18.四数之和
要求：找出所有a, b, c, d相加等于target的集合
思路：和15题一样，但这样的话时间复杂度就要O(n ^ 3)了，其实就是多一重循环，多的循环从j = i + 1开始
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length - 3; i++) {
if (i == 0 || nums[i - 1] != nums[i]) {
for (int j = i + 1; j < nums.length - 2; j++) {
if (j == i + 1 || nums[j - 1] != nums[j]) {
int low = j + 1, high = nums.length - 1;
while (low < high) {
int sum = nums[i] + nums[j] + nums[low] + nums[high];
if (sum == target) {
res.add(Arrays.asList(nums[i], nums[j], nums[low], nums[high]));
while (low < high && nums[low] == nums[low + 1]) low++;
while (low < high && nums[high] == nums[high - 1]) high--;
low++;
high--;
} else if (sum < target) {
low++;
} else {
high--;
}
}
}
}
}
}
return res;
}
2016-12-22
581. Shortest Unsorted Continuous Subarray
要求：找出最短需要排序的连续子序列
思路：取前后指针，并每次更新前面的最大，后面的最小，若发现前面的下一位比较小，就证明需要排序，更新所需排序子序列的末端点，后面反之。
public class Solution {
public int findUnsortedSubarray(int[] nums) {
int n = nums.length, beg = -1, end = -2, max = nums[0], min = nums[n - 1];
for (int i = 1; i < n; i++) {
max = Math.max(max, nums[i]);
min = Math.min(min, nums[n - i - 1]);
if (nums[i] < max) {
end = i;
}
if (nums[n - i - 1] > min) {
beg = n - i - 1;
}
}
return end - beg + 1;
}
}
2017-06-15
Hash Table
3.不含重复字符的最大子字符串(Longest Substring Without Repeating Characters)
要求：如题，一定要是子字符串
思路1：（自写经修改后AC）HashSet不重复特性，若能添加则计数器count++，并更新长度，不能添加的时候删除i - count不与i相同的字符，同时count--，直到相同为止
（sliding window）
public int lengthOfLongestSubstring(String s) {
Set<Character> set = new HashSet<Character>();
int length = 0, count = 0;
for (int i = 0; i < s.length(); i++) {
if (set.add(s.charAt(i))) {
count++;
length = Math.max(count, length);
} else {
while (s.charAt(i - count) != s.charAt(i)) {
set.remove(s.charAt(i - count));
count--;
}
}
}
return length;
}
另一写法：more simple, together with two pointers
public int lengthOfLongestSubstring(String s) {
Set<Character> set = new HashSet<Character>();
int i = 0, j = 0, length = 0;
//two pointers, while j for the end of the substring, i for the start
while (j < s.length()) {
if (set.add(s.charAt(j))) {
j++;
length = Math.max(length, j - i);
} else {
set.remove(s.charAt(i++));
}
}
return length;
}
思路2：（Optimized Solution）HashMap，不是很清楚为什么要+ 1
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
Map<Character, Integer> map = new HashMap<>(); // current index of character
// try to extend the range [i, j]
for (int j = 0, i = 0; j < n; j++) {
if (map.containsKey(s.charAt(j))) {
i = Math.max(map.get(s.charAt(j)), i);
}
ans = Math.max(ans, j - i + 1);
map.put(s.charAt(j), j + 1);
}
return ans;
}
2016-12-22
36.有效九宫格(Valid Sudoku)
要求：分辨九宫格是否有效，九宫格有可能有空格，用'.'表示，只考虑已填的是否正确
思路1：（discuss）巧妙运用对应关系，只需要i，j两个循环，如i = 0对应0行0列0大格
tips：用i作为支点，与j相反就可以调转行和列，而i = 0, 1, 2，对应的是前三个大格，即对应关系为row = 3 * (i / 3), column = 3 * (i % 3)
public boolean isValidSudoku(char[][] board) {
for (int i = 0; i < board.length; i++) {
Set<Character> rows = new HashSet<Character>();
Set<Character> columns = new HashSet<Character>();
Set<Character> cube = new HashSet<Character>();
for (int j = 0; j < board[0].length; j++) {
//判断第i行
if (board[i][j] != '.' && ! rows.add(board[i][j])) {
return false;
}
//判断第i列
if (board[j][i] != '.' && ! columns.add(board[j][i])) {
return false;
}
//计算第i个大格，算对应关系
int row = 3 * (i / 3);
int col = 3 * (i % 3);
if (board[row + j / 3][col + j % 3] != '.' && ! cube.add(board[row + j / 3][col + j % 3])) {
return false;
}
}
}
return true;
}
思路2：（discuss）为每个数添加相同的第几行几列几格的标记，只有满足同一数同一标记才返回false，more simple
public boolean isValidSudoku(char[][] board) {
//存任何类型的set
Set seen = new HashSet();
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] != '.') {
//为此项打上标签输入
String b = "(" + board[i][j] + ")";
//i行在后面添加i标记，j列在前面加j标记，这样就把行列分开了
if (! seen.add(b + i) || ! seen.add(j + b) || ! seen.add(i / 3 + b + j / 3))
return false;
}
}
}
return true;
}
2016-12-22
49.组合颠倒字符串(Group Anagrams)
要求：把颠倒的字符串放在一起
思路1：（discuss + 自己修改）把字符串排序后当成key，用它来标记一个ArrayList，存放排序后一样的字符串
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String s : strs) {
//让旋转后的字符串按照顺序排列
char[] chars = s.toCharArray();
Arrays.sort(chars);
String keyStr = String.valueOf(chars);
if (! map.containsKey(keyStr)) {
map.put(keyStr, new ArrayList<String>(){{add(s);}});
} else {
map.get(keyStr).add(s);
}
}
return new ArrayList<List<String>>(map.values());
}
思路2：（discuss）用prime number，hard to read，代码略
2016-12-23
136.单身数(Single Number)
要求：除了一个数，其他数全部出现两次，找出这一个
思路：异或自己为0，之前碰过
public int singleNumber(int[] nums) {
int res = 0;
for (int num : nums) {
res ^= num;
}
return res;
}
另一思路：若使用HashMap，key用nums填入，返回value为2对应的key值（没有用value找key方法？）
2016-12-23
166.分数转成循环小数(Fraction to Recurring Decimal)
要求：给出分子与分母，以字符串的形式返回对应的小数，其中小数部分若循环的话用（）括起来
思路：（discuss）1、判断正负 2、获得整数部分 3、获得小数部分，用map的key判断是否重复，用value记录每次除完的长度，出现重复时就在当前数前一次出现时插入“（”
tips：用StringBuider来进行添加与插入，把分子分母转成long，求小数时每次除之前要乘以10（即做除法时补0）
public String fractionToDecimal(int numerator, int denominator) {
if (numerator == 0) {
return "0";
}
StringBuilder res = new StringBuilder();
//判断正负
res.append(((numerator > 0) ^ (denominator > 0)) ? "-" : "");
long num = Math.abs((long)numerator);
long den = Math.abs((long)denominator);
//整数部分
res.append(num / den);
num %= den;
if (num == 0) {
return res.toString();
}
//小数部分
res.append(".");
Map<Long, Integer> map = new HashMap<Long, Integer>();
while (num != 0) {
//存放余数
map.put(num, res.length());
num *= 10;
res.append(num / den);
num %= den;
if (map.containsKey(num)) {
res.insert(map.get(num), "(");
res.append(")");
break;
}
}
return res.toString();
}
2016-12-26
187.重复DNA片段(Repeated DNA Sequences)
要求：DNA中包含ACGT四个字母，求重复出现的10位长的DNA片段
思路1：（discuss+自己修改）HashMap+位运算，由于只含有ACGT，可把它用00, 01, 10, 11表示，即每读一个10位长的DNA，就变成了20位的二进制数，用HashMap来存储，第一次出现value设为0，出现过后设为1，以防止添加重复的子串
public List<String> findRepeatedDnaSequences(String s) {
Map<Integer, Integer> map = new HashMap<>();
List<String> rv = new ArrayList<>();
//把ACGT转换成两位二进制数
char[] trans = new char[26];
//trans['A' - 'A'] = 0;
trans['C' - 'A'] = 1;
trans['G' - 'A'] = 2;
trans['T' - 'A'] = 3;
for(int i = 0; i < s.length() - 9; i++) {
int v = 0;
for(int j = i; j < i + 10; j++) {
//移位存储每一个字母
v |= trans[s.charAt(j) - 'A'];
v <<= 2;
}
if (map.containsKey(v)) {
//判断是否第一次重复
if (map.get(v) == 0) {
rv.add(s.substring(i, i + 10));
}
map.put(v, 1);
} else {
map.put(v, 0);
}
}
return rv;
}
思路2：（自写一次AC）HashMap，根本就不用转换，遍历一次，把每个位置后面以10位子字符串ss截取，都存进map中即可，照样用value判断是否第一次重复
public List<String> findRepeatedDnaSequences(String s) {
Map<String, Integer> map = new HashMap<>();
List<String> rv = new ArrayList<>();
for (int i = 0; i < s.length() - 9; i++) {
String ss = s.substring(i, i + 10);
if (map.containsKey(ss)) {
//判断是否第一次重复
if (map.get(ss) == 0) {
rv.add(ss);
}
map.put(ss, 1);
} else {
map.put(ss, 0);
}
}
return rv;
}
另一写法：用两个HashSet防止结果重复
public List<String> findRepeatedDnaSequences(String s) {
Set seen = new HashSet(), repeated = new HashSet();
for (int i = 0; i + 9 < s.length(); i++) {
String ten = s.substring(i, i + 10);
if (!seen.add(ten))
repeated.add(ten);
}
return new ArrayList(repeated);
}
2016-12-26
202.快乐数字(Happy Number)
要求：判断这个数是否happy number，就是把各个位上的数取平方相加，直到循环之前能够实现和为1
思路1：（自写一次AC）就是通过整除10来获得每一位，然后HashSet判断重复
public boolean isHappy(int n) {
Set<Integer> set = new HashSet<>();
while (n != 1) {
if (! set.add(n)) {
return false;
}
int sum = 0;
while (n != 0) {
int temp = n % 10;
sum += temp * temp;
n /= 10;
}
n = sum;
}
return true;
}
思路2：（discuss）可以不用set，空间复杂度为O(1)
2016-12-26
204.数质数(Count Primes)
要求：数出少于n的所有质数的个数
思路：（答案）把所有不是质数的算出来，剩下的就是质数 O(n)空间，O(n log log n)时间
public int countPrimes(int n) {
boolean[] isPrime = new boolean[n];
for (int i = 2; i < n; i++) {
isPrime[i] = true;
}
// Loop's ending condition is i * i < n instead of i < sqrt(n)
// to avoid repeatedly calling an expensive function sqrt().
for (int i = 2; i * i < n; i++) {
if (!isPrime[i]) continue;
for (int j = i * i; j < n; j += i) {
isPrime[j] = false;
}
}
int count = 0;
for (int i = 2; i < n; i++) {
if (isPrime[i]) count++;
}
return count;
}
另一种写法，每次循环时的设置不一样，但同样是求非质数
public int countPrimes(int n) {
boolean[] notPrime = new boolean[n];
int count = 0;
for (int i = 2; i < n; i++) {
if (notPrime[i] == false) {
count++;
for (int j = 2; i*j < n; j++) {
notPrime[i*j] = true;
}
}
}
return count;
}
2016-12-26
205.同构字符串(Isomorphic Strings)
要求：判断s能否把相同的字符一起转换成另一个字符来得到t（包括数字），假设s, t两字符串长度相等
思路1：（discuss）用256位数组来存储可能出现的256个字符的位置，先判断当前字符上一次在的位置是否一样，然后再更新它的位置
warn：要考虑256种，不用减‘a’，由于初始化时数组为0，为了区分，需要用i + 1确保i = 0时的情况
public boolean isIsomorphic(String s, String t) {
int[] ss = new int[256];
int[] ts = new int[256];
for (int i = 0; i < s.length(); i++) {
if (ss[s.charAt(i)] != ts[t.charAt(i)]) {
return false;
}
ss[s.charAt(i)] = i + 1;
ts[t.charAt(i)] = i + 1;
}
return true;
}
(10ms)
思路2：（自写一次AC）用两张HashMap来判断，一张key是s的字符，另一张则是t，用此来判断每次来的新配对是否与之前的一样
tips：discuss中可用一张map完成，但用containsValue判断的话逻辑比较乱，自写后理顺得到第三种代码，当前的输入若之前不存在这个key但存在这个value，证明与之前的配对不一样
public boolean isIsomorphic(String s, String t) {
Map<Character, Character> map1 = new HashMap<>();
Map<Character, Character> map2 = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
char a = s.charAt(i);
char b = t.charAt(i);
if (map1.containsKey(a) && map1.get(a) != b) {
return false;
} else if (map2.containsKey(b) && map2.get(b) != a){
return false;
} else {
map1.put(a, b);
map2.put(b, a);
}
}
return true;
}
(49ms)
public boolean isIsomorphic(String s, String t) {
Map<Character, Character> map = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
char a = s.charAt(i);
char b = t.charAt(i);
if (map.containsKey(a)) {
if (map.get(a) != b) {
return false;
}
} else if (map.containsValue(b)){ //在不含key的情况下有一样的value，证明与之前的配对不一样
return false;
} else {
map.put(a, b);
}
}
return true;
}
(19ms)
2016-12-27
242.有效旋转(Valid Anagram)
要求：判断t是否经过s移位获得
思路1：（自写一次AC）HashSet+Sort把字符串转成数组排序之后用Set判断是否重复(7ms)
public boolean isAnagram(String s, String t) {
char[] sc = s.toCharArray();
char[] tc = t.toCharArray();
Arrays.sort(sc);
Arrays.sort(tc);
s = String.valueOf(sc);
t = String.valueOf(tc);
Set<String> set = new HashSet<>();
set.add(s);
if (set.add(t)) return false;
return true;
}
思路2：（discuss）不用排序，用26位长的数组分别代表26个字母，然后用来计数每一个字母的数量，s含有某字母对应位置+ 1，而t则- 1，最后判断是否每个位都为0(8ms)
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
int[] alps = new int[26];
for (int i = 0; i < s.length(); i++) {
//得到某字母对应的位置+ 1
alps[s.charAt(i) - 'a']++;
alps[t.charAt(i) - 'a']--;
}
for (int alp : alps) {
if (alp != 0) {
return false;
}
}
return true;
}
2016-12-26
290.单词模式(Word Pattern)
要求：按照Pattern如abba，造字符串str"dog cat cat dog"，判断是否合规
思路1：（自写经修改成功）对应205题思路2，就是用一张map建立pattern与str之间的链接，判断新的是否与之前的一样
tips：由于这题判断的是String，要用equals方法
public boolean wordPattern(String pattern, String str) {
Map<Character, String> map = new HashMap<>();
String[] words = str.split(" ");
if (words.length != pattern.length()) {
return false;
}
for (int i = 0; i < words.length; i++) {
char c = pattern.charAt(i);
String s = words[i];
if (map.containsKey(c)) {
if (!map.get(c).equals(s)) {
return false;
}
} else if (map.containsValue(s)) {
return false;
} else {
map.put(c, s);
}
}
return true;
}
(2ms)
思路2：（discuss）对应205思路1，不过这里可以用一张map记录位置，因为pattern的key是char，而str的key是string，彼此不相同
warn：若使用!= 来判断位置的话，位置太大时会报错
public boolean wordPattern(String pattern, String str) {
Map map = new HashMap();
String[] words = str.split(" ");
if (words.length != pattern.length()) {
return false;
}
for (int i = 0; i < words.length; i++) {
if (!Objects.equals(map.put(pattern.charAt(i), i), map.put(words[i], i))) { //此处用!=的话会超过长度
return false;
}
}
return true;
}
(3ms)
2016-12-27
299.Bulls and Cows
要求：题目真难懂，就是两个四位数，位置与数字相同的时候bull++，位置不同但数字相同的时候cow++，但这种情况重复只算一个猜对
思路1：（discuss）用10位数组代表10个数（其实相当于长度为10的HashMap吧），当两个数字对应位置不相同时更新数组，然后用每个位上代表每种数的有无，判断大小于0确定是否有一样但位置不一样的
public String getHint(String secret, String guess) {
int bull = 0;
int cow = 0;
int[] nums = new int[10];
for (int i = 0; i < secret.length(); i++) {
if (secret.charAt(i) == guess.charAt(i)) {
bull++;
} else {
//数字字符转成整数
if (nums[secret.charAt(i) - '0']++ < 0) cow++;
if (nums[guess.charAt(i) - '0']-- > 0) cow++;
}
}
return bull + "A" + cow + "B";
}
思路2：（discuss）用两个数组分别存储位置不同时各自的数，最后遍历一次对比哪个少，只有guess数组中大于等于1时才会有cow，代码略
2016-12-27
349.两数组交集(Intersection of Two Arrays)
要求：把两数组交集无重复地列出
思路1：（自写一次AC）two pointers，先排序，后用ArrayList（需判断同个数组相邻两个是否重复）或者HashSet存储相同的数，O(nlogn)
public int[] intersection(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
int i = 0, j = 0;
List<Integer> list = new ArrayList<Integer>();
while (i < nums1.length && j < nums2.length) {
if (nums1[i] == nums2[j]) {
list.add(nums1[i]);
while (i < nums1.length - 1 && nums1[i] == nums1[i + 1]) i++;
while (j < nums2.length - 1 && nums2[j] == nums2[j + 1]) j++;
i++;
j++;
} else if (nums1[i] < nums2[j]) {
i++;
} else {
j++;
}
}
int[] res = new int[list.size()];
for (int k = 0; k < list.size(); k++) {
res[k] = list.get(k);
}
return res;
}
(ArrayList)
思路2：（自写修改）两个set，第一个set排除原数组重复，第二次循环时判断当第一个set中有当前数时再添加，第二个set防止了子数组的重复，O(n)
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set1 = new HashSet<Integer>();
Set<Integer> set2 = new HashSet<Integer>();
for (int num : nums1) {
set1.add(num);
}
for (int num : nums2) {
if (set1.contains(num)) {
set2.add(num);
}
}
int[] res = new int[set2.size()];
int i = 0;
for (int num : set2) {
res[i++] = num;
}
return res;
}
思路3：（discuss）二分查找，遍历nums1，查找nums2中与nums1相同的数，放入set中防止重复，O(nlogn)，代码略
2016-12-27
350.两数组交集II(Intersection of Two Arrays II)
要求：重复也要列出
思路和349完全一样，还不用判断结果是否有重复，给出ArrayList存储代码吧
public int[] intersect(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
int i = 0, j = 0;
List<Integer> list = new ArrayList<Integer>();
while (i < nums1.length && j < nums2.length) {
if (nums1[i] == nums2[j]) {
list.add(nums1[i]);
i++;
j++;
} else if (nums1[i] < nums2[j]) {
i++;
} else {
j++;
}
}
int[] res = new int[list.size()];
for (int k = 0; k < list.size(); k++) {
res[k] = list.get(k);
}
return res;
}
2016-12-27
389.找不同(Find the Difference)
要求：找出两个字符串中，某字符串中多出来的那个
思路：（自写）异或，char也可以直接运算，求和也行
tips：把结果首先赋成较长字符串最后的那个字符，要用^=
public char findTheDifference(String s, String t) {
char c = t.charAt(t.length() - 1);
for (int i = 0; i < s.length(); i++) {
c ^= (s.charAt(i) ^ t.charAt(i));
}
return c;
}
不能用set直接做，因为有可能插入的是已存在的字符
2016-12-28
409.最长回文(Longest Palindrome)
要求：用字符串的字符以任意顺序组成一个最长的对称字符串，返回长度
思路1：（discuss+自修改）需要出现双数次才能对称，每次set中有重复时就去掉这个字符并count++（也就是记录出现双数次），没重复就是出现单数次正常添加，最后把count * 2就是总次数，判断此时set是否为空可确定回文长度的奇偶
public int longestPalindrome(String s) {
Set<Character> set = new HashSet<>();
int count = 0;
char[] cc = s.toCharArray();
//计算出现的双数次保证对称
for (char c : cc) {
if (set.contains(c)) {
set.remove(c);
count++;
} else {
set.add(c);
}
}
//判断回文长度是奇数还是偶数
return set.isEmpty() ? count * 2 : count * 2 + 1;
}
(21ms)
思路2：（discuss）分别用两个26位数组代表52个大小写字母，然后计算所有字母出现的次数
tips：除2再乘2可把奇数减1变成偶数（1变0），符合对称要求，a的ASCII码是97
public int longestPalindrome(String s) {
int[] lower = new int[26];
int[] upper = new int[26];
int res = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c >= 97) {
lower[c - 'a']++;
} else {
upper[c - 'A']++;
}
}
for (int i = 0; i < 26; i++) {
//保证输出的都是双数
res += (lower[i] / 2) * 2;
res += (upper[i] / 2) * 2;
}
//只有等于原s长度时回文长度才是偶数
return res == s.length() ? res : res + 1;
}
(11ms)
2016-12-28
438.找出字符串所有颠倒的子字符串(Find All Anagrams in a String)
要求：如题，返回子字符串开始的位置，Input: s: "cbaebabacd" p: "abc" Output: [0, 6]
思路：（discuss）Sliding Windows，（还没完全理解：假定窗口长度（right - left）是字符串p的长度并设置同样的count，两指针都从左边开始，rigth指针一直移动，相应位置上的字符数量一直--，出现p的字符时count--；left指针只有当两指针的差值等于p长度时才移动（确保窗口长度能够一直不变），移动时相应位置上的字符一直++（确保存储数组中各个字符的数量不变，包括p中不存在的），出现p的字符时count++；当count为0时输出left位置）
还不理解left移动时为什么要count++？？也许是为了防止right已经遍历过p存在的数算多了一次 2016-12-28
public List<Integer> findAnagrams(String s, String p) {
List<Integer> list = new ArrayList<>();
if (s == null || s.length() == 0 || p == null || p.length() == 0) return list;
int[] hash = new int[256]; //character hash
//record each character in p to hash
for (char c : p.toCharArray()) {
hash[c]++;
}
//two points, initialize count to p's length
int left = 0, right = 0, count = p.length();
while (right < s.length()) {
//move right everytime, if the character exists in p's hash, decrease the count
//current hash value >= 1 means the character is existing in p
if (hash[s.charAt(right++)]-- >= 1) count--;
//when the count is down to 0, means we found the right anagram
//then add window's left to result list
if (count == 0) list.add(left);
//if we find the window's size equals to p, then we have to move left (narrow the window) to find the new match window
//++ to reset the hash because we kicked out the left
//only increase the count if the character is in p
//the count >= 0 indicate it was original in the hash, cuz it won't go below 0
if (right - left == p.length() && hash[s.charAt(left++)]++ >= 0) count++;
}
return list;
}
同类子字符串问题的总结：
https://discuss.leetcode.com/topic/30941/here-is-a-10-line-template-that-can-solve-most-substring-problems
还缺一些游戏题和堆排序的题没做
String
5.最长回文子字符串(Longest Palindromic Substring)
要求：找出字符串s中最长的对称子字符串
思路：（discuss）把s遍历一次，在每个位置i用two pointers判断最长的回文（判断是否与旁边字符相同确保回文长度为偶数的情况），超过之前的情况就更新回文开始点与长度
tips：为了每个方法都能调用变量，可定义类private属性，substring的用法，substring(a, b)是截取从a到b - 1的子字符串
private int lo, maxLen; //定义类的private属性，使类中所有方法都可用
public String longestPalindrome(String s) {
if (s.length() < 2) {
return s;
} //以每个位置为中心向两边找回文
for (int i = 0; i < s.length() - 1; i++) {
extendPalindrome(s, i, i); //寻找以i为中心的回文
extendPalindrome(s, i, i + 1); //若i与i + 1相同，则中心为它们两个
}
return s.substring(lo, lo + maxLen);
} //two pointers以中心向头尾移动
private void extendPalindrome(String s, int j, int k) {
while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) {
j--;
k++;
}
if (maxLen < k - j - 1) {
lo = j + 1;
maxLen = k - j - 1;
}
}
2017-01-02
6.Z型变换(ZigZag Conversion)
要求：把字符串按照Z型分布排成numRows行，并逐行读出
思路：（discuss）创建numRows行的不定长度的存储空间（数组），然后逐个存进，最后逐行读出，用StringBuilder(Buffer)或者ArrayList存储
tips：用StringBuilder更快且更省空间，因为可用append一次过把一行都加起来，最后把后面的行都加在第一行就toString输出了，StringBuilder的线程不安全
public String convert(String s, int numRows) {
StringBuilder[] rows = new StringBuilder[numRows]; //数组
for (int row = 0; row < numRows; row++) {
rows[row] = new StringBuilder(); //数组每一个元素都是一个builder
}
int i = 0;
//Z型存储进数组
while (i < s.length()) {
for (int row = 0; row < numRows && i < s.length(); row++) {
rows[row].append(s.charAt(i++));
}
for (int row = numRows - 2; row > 0 && i < s.length(); row--) {
rows[row].append(s.charAt(i++));
}
}
//读取
for (int row = 1; row < numRows; row++) {
rows[0].append(rows[row]);
}
return rows[0].toString();
}
(StringBuilder)
public String convert(String s, int numRows) {
ArrayList<Character>[] rows = (ArrayList<Character>[]) new ArrayList[numRows];
for (int row = 0; row < numRows; row++) {
rows[row] = new ArrayList<Character>();
}
int i = 0;
//Z型存储进数组
while (i < s.length()) {
for (int row = 0; row < numRows && i < s.length(); row++) {
rows[row].add(s.charAt(i++));
}
for (int row = numRows - 2; row > 0 && i < s.length(); row--) {
rows[row].add(s.charAt(i++));
}
}
//读取
StringBuilder sb = new StringBuilder(s.length());
for (int row = 0; row < numRows; row++) {
for (int col = 0; col < rows[row].size(); col++) {
sb.append(rows[row].get(col));
}
}
return sb.toString();
}
(ArrayList)
2017-01-02
8.字符串转整数(String to Integer)
要求：考虑各种情况
思路：（discuss）考虑四方面：1、空字符串 2、去掉前面的空格 3、判断正负 4、逐个字符转成整数并加起来，判断是否溢出
tips：字符转整数可- ‘0’也可用Character.getNumericValue(char)
public int myAtoi(String str) {
int index = 0, sign = 1, total = 0;
//1. Empty string
if (str.length() == 0) {
return 0;
}
//2. Remove Spaces
while (str.charAt(index) == ' ' && index < str.length()) {
index++;
}
//3. Handle signs
if (str.charAt(index) == '+' || str.charAt(index) == '-') {
sign = str.charAt(index) == '+' ? 1 : -1;
index++;
}
//4. Convert number and avoid overflow
while (index < str.length()) {
int digit = str.charAt(index) - '0'; //char to int
if(digit < 0 || digit > 9) break; //if not a number, break
//check if total will be overflow after 10 times and add digit
if (Integer.MAX_VALUE / 10 < total || Integer.MAX_VALUE / 10 == total && Integer.MAX_VALUE % 10 < digit) {
return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
}
total = 10 * total + digit;
index++;
}
return total * sign;
}
2017-01-02
12.整数转罗马数字(Integer to Roman)
要求：如题
思路：（discuss）最主要是罗马数字个十百千怎么表示，然后直接除就完了 1 5 10 50 100 500 1000分别是I V X L C D M
public static String intToRoman(int num) {
String M[] = {"", "M", "MM", "MMM"};
String C[] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
String X[] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
String I[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
return M[num / 1000] + C[(num % 1000) / 100] + X[(num % 100) / 10] + I[num % 10];
}
2017-01-02
13.罗马数字转整数(Roman to Integer)
要求：如题
思路1：（discuss）把所有'4'当成'6'，'9'当成'11'先相加，然后减去出现4，9的情况
public int romanToInt(String s) {
int sum = 0;
//排除个十百位上出现的4，9
if (s.indexOf("IV") != -1) sum -= 2;
if (s.indexOf("IX") != -1) sum -= 2;
if (s.indexOf("XL") != -1) sum -= 20;
if (s.indexOf("XC") != -1) sum -= 20;
if (s.indexOf("CD") != -1) sum -= 200;
if (s.indexOf("CM") != -1) sum -= 200;
char[] c = s.toCharArray();
for (int i = 0; i < s.length(); i++) {
if (c[i] == 'M') sum += 1000;
if (c[i] == 'D') sum += 500;
if (c[i] == 'C') sum += 100;
if (c[i] == 'L') sum += 50;
if (c[i] == 'X') sum += 10;
if (c[i] == 'V') sum += 5;
if (c[i] == 'I') sum += 1;
}
return sum;
}
思路2：（自写AC）用Map或者数组来存储字母与数字的对应关系，然后按照罗马数字的规则来算，比如I在V左边，就是V(5) - I(1)，否则就是加（就是判断前后两个字母对应的数字的大小）
public int romanToInt(String s) {
Map<Character, Integer> map = new HashMap<>();
map.put('I', 1);
map.put('V', 5);
map.put('X', 10);
map.put('L', 50);
map.put('C', 100);
map.put('D', 500);
map.put('M', 1000);
char[] c = s.toCharArray();
int sum = map.get(c[c.length - 1]);
for (int i = 0; i < s.length() - 1; i++) {
if (map.get(c[i]) < map.get(c[i + 1])) {
sum -= map.get(c[i]);
} else {
sum += map.get(c[i]);
}
}
return sum;
}
2017-01-02
14.最长相同前缀(Longest Common Prefix)
要求：找出字符串数组中，所有字符串共同的最长前缀
思路1：（自写修改后AC）用str[0]与后面的相比，比到maxLen或者字符不同为止，然后更新maxLen
warn：注意数组的边界条件，留意后面的字符串的长度有可能比之前的maxLen还要小
public String longestCommonPrefix(String[] strs) {
if (strs.length == 0) {
return "";
}
int maxLen = strs[0].length();
for (int i = 1; i < strs.length; i++) {
maxLen = Math.min(maxLen, strs[i].length());
int j = 0;
while (j < maxLen && strs[0].charAt(j) == strs[i].charAt(j)) {
j++;
}
maxLen = j;
}
return strs[0].substring(0, maxLen);
}
思路2：（discuss+自改）把字符串数组排序，然后比较头尾两个，因为头尾两个的差异最大，判断它们两个最长前缀即是结果
public String longestCommonPrefix(String[] strs) {
if (strs.length == 0) {
return "";
}
//排序确保了中间项出现不一样的问题
Arrays.sort(strs);
char[] a = strs[0].toCharArray();
char[] b = strs[strs.length - 1].toCharArray();
int i = 0;
while (i < a.length && i < b.length && a[i] == b[i]) {
i++;
}
return strs[0].substring(0, i);
}
另：还可以用indexOf是否为0来判断一个子字符串是否存在，且是否在头部开始
2017-01-04
20.有效括号(Vaild Parentheses)
要求：每个(, [, {要有对用的), ], }
思路1：（discuss）用栈，左括号进，当前输入的右括号满足与上一次输入的左括号对应就弹，否则出错
tips：最后判断栈是否为空，就能确定每一个左括号是否都有对应的右括号，easy to understand
public boolean isValid(String s) {
Stack<Character> stack = new Stack<Character>();
//如果左括号则入栈，有上一个入栈对应的右括号则出栈，否则错误
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{') {
stack.push(s.charAt(i));
} else if (s.charAt(i) == ')' && !stack.empty() && stack.peek() == '(') {
stack.pop();
} else if (s.charAt(i) == ']' && !stack.empty() && stack.peek() == '[') {
stack.pop();
} else if (s.charAt(i) == '}' && !stack.empty() && stack.peek() == '{') {
stack.pop();
} else {
return false;
}
}
//判断是否为空，确保都有右括号对应
return stack.empty();
}
(9ms)
思路2：（discuss）若当前的是左括号，则让它对应的右括号入栈；若当前的是右括号，则栈为空（意味着把左括号的情况全弹完）或者不等于上次输入的右括号的时候就出错
tips：可以把pop()和判断相等同时进行，more simple
public boolean isValid(String s) {
Stack<Character> stack = new Stack<Character>();
//入栈的是与当前左括号对应的右括号
for (char c : s.toCharArray()) {
if (c == '(') {
stack.push(')');
} else if (c == '[') {
stack.push(']');
} else if (c == '{') {
stack.push('}');
} else if (stack.empty() || stack.pop() != c) {
return false;
}
}
return stack.empty();
}
(8ms)
2017-01-04
28.实现strStr()函数(Implement strStr())
要求：实现Java中String类的indexOf()
思路：（自写AC）最笨的方法，不考虑KMP等算法，一位位的比较字符串与目标子字符串是否一样
public int strStr(String haystack, String needle) {
int m = haystack.length();
int n = needle.length();
for (int i = 0; i <= m - n; i++) {
for (int j = 0; ; j++) {
if (j == n) return i;
if (needle.charAt(j) != haystack.charAt(i + j)) break;
}
}
return -1;
}
还有更高级的算法有待学习
2017-01-04
38.Count and Say(数和读)
要求：初始为1，第二个是“1个1”，即11，第三个是两个1，即“21”
思路：（discuss）找出每一个字符串，并读上一个字符串时，按照其规律，相同就继续数count++，不相同就say(添加到新的字符串中)
public String countAndSay(int n) {
StringBuilder cur = new StringBuilder("1");
StringBuilder pre;
//标记要说的字符及其数量
int count;
char say;
//从头开始数
for (int i = 1; i < n; i++) {
pre = cur;
//存放say之后的字符串
cur = new StringBuilder();
count = 1;
say = pre.charAt(0);
for (int j = 1; j < pre.length(); j++) {
if (pre.charAt(j) == say) {
count++;
} else {
cur.append(count).append(say);
count = 1;
say = pre.charAt(j);
}
}
cur.append(count).append(say);
}
return cur.toString();
}
2017-01-05
43.字符串相乘(Multiply Strings)
要求：返回两个字符串相乘的结果，它们所代表的数字不大于110，而且头部没有0
思路：（discuss）用数组存储相乘结果，按照相乘法则，记录每次相乘后所放的位置，并把个位与上一次循环中的十位相加，再把当前循环的十位（十位上的数要加上本来在该位的数）个位放进去相应位置
tips：每次循环中的数字相乘为0~9，其乘积只有两位
public String multiply(String num1, String num2) {
//用数组来存储相乘结果
int[] pos = new int[num1.length() + num2.length()];
//从末尾开始相乘
for (int i = num1.length() - 1; i >= 0; i--) {
for (int j = num2.length() - 1; j >= 0; j--) {
//字符转数字后相乘
int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
//当前乘积的十位个位应当放的位置
int p1 = i + j, p2 = i + j + 1;
//算出与上一次循环中十位上的数的和
int sum = mul + pos[p2];
//算出当前乘积的最后结果的十位个位
pos[p1] += sum / 10;
pos[p2] = sum % 10;
}
}
//把数组转字符串
StringBuilder res = new StringBuilder();
for (int p : pos) {
//不输入头部的0
if (!(res.length() == 0 && p == 0)) {
res.append(p);
}
}
//判断是否为0
return res.length() == 0 ? "0" : res.toString();
}
2017-01-05
58.最后一个单词的长度(Length of Last Word)
要求：以' '分割单词，求最后一个单词长度
思路1：（自写AC）从尾判断，不是空格就len++，是空格且len不等于0（避免空格在末尾的情况）就跳出
public int lengthOfLastWord(String s) {
int len = 0;
for (int i = s.length() - 1; i >= 0; i--) {
if (s.charAt(i) != ' ') {
len++;
}
if (s.charAt(i) == ' ' && len != 0) {
break;
}
}
return len;
}
思路2：（discuss）用lastIndexOf判断最后一个' '的位置
public int lengthOfLastWord(String s) {
return s.trim().length()-s.trim().lastIndexOf(" ")-1;
}
2017-01-05
67.二进制相加(Add Binary)
要求：给出两个二进制的字符串，返回相加后的二进制的字符串
思路：（discuss）自写思路虽对，但太复杂，逐位算时，每次相加结果sum % 2是该位的数，sum / 2是进位（和用异或、与那题不同）
tips：记得最后一个进位，从个位开始加就放进StringBuilder里面，最后可以转置reverse()
public String addBinary(String a, String b) {
StringBuilder res = new StringBuilder();
int i = a.length() - 1, j = b.length() - 1, ca = 0;
while (i >= 0 || j >= 0) {
int sum = ca;
if (i >= 0) sum += a.charAt(i--) - '0';
if (j >= 0) sum += b.charAt(j--) - '0';
//余数是该位结果，商是进位
res.append(sum % 2);
ca = sum / 2;
}
//最后一个进位
if (ca == 1) res.append(1);
//转置
return res.reverse().toString();
}
2017-01-05
125.有效回文(Valid Palindrome)
要求：判断一个字符串是不是回文，但不算除字母和数字外的字符，大小写忽略
思路：（知道怎么做但写不出来）two pointers在首尾向里移动，排除非字母数字，转为小写，不同返回错误
tips：排除可用isLetterOrDigit()方法，转小写用toLowerCase()
warn：要考虑只含非字母数字的情况
public boolean isPalindrome(String s) {
int i = 0, j = s.length() - 1;
while (i < j) {
//判断是否数字或字母
char a = s.charAt(i);
char b = s.charAt(j);
if (!Character.isLetterOrDigit(a)) {
i++;
} else if (!Character.isLetterOrDigit(b)) {
j--;
} else {
if (Character.toLowerCase(a) != Character.toLowerCase(b)) {
return false;
}
i++;
j--;
}
}
return true;
}
2017-01-06
344.旋转字符串(Reverse String)
要求：如题
思路：（自写AC）简单
public String reverseString(String s) {
StringBuilder res = new StringBuilder();
for (int i = s.length() - 1; i >= 0; i--) {
res.append(s.charAt(i));
}
return res.toString();
}
还有多种用位运算、首尾交换的方法
2017-01-06
345.旋转字符串中的元音字母(Reverse Vowels of a String)
要求：如题
思路：（有思路但写不出）two pointers首尾向里移动，判断是否元音，两边都是元音的时候则交换
tips：用String代替Set保存元音，也可以用contains()方法，但Set读取更快
warn：要转成字符数组才能交换，字符数组转回字符串可用New String(char[])
public String reverseVowels(String s) {
//string直接用作set
String vowels = "aeiouAEIOU";
char[] res = s.toCharArray();
int i = 0, j = s.length() - 1;
while (i < j) {
while (i < j && !vowels.contains(res[i] + "")) i++;
while (i < j && !vowels.contains(res[j] + "")) j--;
//i = j时与自己交换
char c = res[i];
res[i] = res[j];
res[j] = c;
i++;
j--;
}
return new String(res);
}
2017-01-06
383.Ransom Note
要求：用字符串magazine里含有的字符来组成ransomNote，m中字符只能用一次
思路：（自写AC）用26位数组存储各个字符的数量
public boolean canConstruct(String ransomNote, String magazine) {
int[] chars = new int[26];
for (int i = 0; i < ransomNote.length(); i++) {
chars[ransomNote.charAt(i) - 'a']++;
}
for (int i = 0; i < magazine.length(); i++) {
chars[magazine.charAt(i) - 'a']--;
}
for (int c : chars) {
if (c > 0) {
return false;
}
}
return true;
}
discuss写得更simple
public boolean canConstruct(String ransomNote, String magazine) {
int[] arr = new int[26];
for (int i = 0; i < magazine.length(); i++) {
arr[magazine.charAt(i) - 'a']++;
}
for (int i = 0; i < ransomNote.length(); i++) {
if(--arr[ransomNote.charAt(i)-'a'] < 0) {
return false;
}
}
return true;
}
2017-01-09
434.字符串的分区数目(Number of Segments in a String)
要求：用空格来分开字符串，求字符串的分区数
思路1：（自写修改AC）数空格数来确定分区数
warn：1、空字符串（返回0） 2、头部有空格（决定赋值res是0还是1） 3、分区之间有多个空格（移动到没空格为止） 4、尾部有空格（若最后一个仍是空格则不计数）
public int countSegments(String s) {
if (s.length() == 0) {
return 0;
}
//保证开始不是空格
int res = s.charAt(0) == ' ' ? 0 : 1;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == ' ') {
//排除中间有多个空格
while (i < s.length() - 1 && s.charAt(i + 1) == ' ') i++;
//排除最后一个是空格
if (i != s.length() - 1) res++;
}
}
return res;
}
思路2：（discuss）数出现i不是空格，且i - 1是空格的情况来确定分区，more simple
warn：注意排除首字符无i - 1的情况
public int countSegments(String s) {
int res=0;
for(int i=0; i<s.length(); i++)
if(s.charAt(i)!=' ' && (i==0 || s.charAt(i-1)==' '))
res++;
return res;
}
2017-01-09
459.重复子字符串模式(Repeated Substring Pattern)
要求：判断一个字符串是否由一个子字符串复制而成
思路1：（自写但一直没AC？）用数组先存储字符出现次数，然后判断每个字符应该出现一样次数
public boolean repeatedSubstringPattern(String str) {
int[] chars = new int[26];
for (int i = 0; i < str.length(); i++) {
chars[str.charAt(i) - 'a']++;
}
int temp = 0;
for (int c : chars) {
if (temp == 0 && c != 0) {
temp = c;
} else if (c != temp) {
return false;
}
}
return true;
}
???
思路2：（dicuss）从长度一半开始判断，若能整除str的长度，则复制从开始到截取点的子字符串，再与str比较（其实就是根据题意）
public boolean repeatedSubstringPattern(String str) {
int len = str.length();
for (int i = len / 2; i > 0; i--) {
//若被整除则有可能组成str
if (len % i == 0) {
int m = len / i;
String subStr = str.substring(0, i);
StringBuilder sb = new StringBuilder();
//复制m次判断是否str
for (int j = 0; j < m; j++) {
sb.append(subStr);
}
if (sb.toString().equals(str)) {
return true;
}
}
}
return false;
}
2017-01-09
Math
7.反转数字(Reverse Integer)
要求：如题
思路1：（discuss）由于头尾反转，每次取末尾，然后把上次的乘以10（左移）就行
public int reverse(int x) {
long rev = 0;
while (x != 0) {
//把之前保存的左移
rev = 10 * rev + x % 10;
x = x /10;
//判断溢出
if (rev > Integer.MAX_VALUE || rev < Integer.MIN_VALUE) {
return 0;
}
}
return (int)rev;
}
思路2：（自想）用字符串强行反转，但这样处理溢出很麻烦
2017-01-09
9.回文数字(Palindrome Number)
要求：如题，不实用额外空间
思路1：（自写AC）反转后判断是否一样，方法与7题一样，不过翻转后有可能溢出
public boolean isPalindrome(int x) {
if (x < 0) {
return false;
}
int rev = 0;
int temp = x;
while (temp != 0) {
rev = rev * 10 + temp % 10;
temp /= 10;
}
return x == rev;
}
(有缺陷)
思路2：（discuss）反转一半看是否一样，更快但难理解，防止了溢出
warn：考虑奇偶长度
public boolean isPalindrome(int x) {
if (x < 0 || (x != 0 && x % 10 == 0)) { //末尾为0不可能回文
return false;
}
int rev = 0;
//判断一半是否相同
while (x > rev) {
rev = rev * 10 + x % 10;
x /= 10;
}
return (x == rev || x == rev / 10); //考虑奇偶数
}
2017-01-09
29.整数相除(Divide Two Integers)
要求：不能用乘除，取余数
思路：（discuss）递归，从1个ldivisor开始叠加，数到ldividend
tips：进入递归，每次递归重置ldividend，ldivisor不变，跳出递归，设置条件ldividend < ldivisor(return 0应在递归表达式return ldivide(n - 1)之前才能跳出)
public int divide(int dividend, int divisor) {
int sign = 1;
if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)) {
sign = -1;
}
if (divisor == 0) {
return Integer.MAX_VALUE;
}
long ldividend = Math.abs((long)dividend);
long ldivisor = Math.abs((long)divisor);
if (ldividend < ldivisor) {
return 0;
}
long res = ldivide(ldividend, ldivisor);
int ans;
if (res > Integer.MAX_VALUE) {
return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
} else {
ans = (int)((sign == 1) ? res : -res);
}
return ans;
}
private long ldivide(long ldividend, long ldivisor) {
//增加这句能跳出递归
if (ldividend < ldivisor) {
return 0;
}
long sum = ldivisor;
long multiple = 1;
while ((sum + sum) <= ldividend) {
sum += sum;
multiple += multiple;
}
return multiple + ldivide(ldividend - sum, ldivisor);
}
2017-01-11
50.Pow(x, n)???
public double myPow(double x, int n) {
double ans = 1;
long absN = Math.abs((long)n);
while(absN > 0) {
if((absN & 1) == 1) ans *= x;
absN >>= 1;
x *= x;
}
return n < 0 ? 1 / ans : ans;
}
2017-01-11
168.Excel表格列名(Excel Sheet Column Title)
要求：1 -> 'A', 2 -> 'B', 27 -> 'AA'...
思路：（自写修改AC）把n整除26得到末尾，然后更新n（n /= 26），原理与十进制时候一样
warn：由于1对应A而不是0，故要先--n再整除26，还有记得reverse()
public String convertToTitle(int n) {
StringBuilder res = new StringBuilder();
while (n != 0) {
res.append((char)('A' + --n % 26));
n /= 26;
}
return res.reverse().toString();
}
2017-01-11
171.Excel表格列数(Excel Sheet Column Number)
要求：171相反过来
思路：（自写AC）从字符串头部开始读，然后上一次的 * 26，简单
public int titleToNumber(String s) {
int sum = 0;
for (int i = 0; i < s.length(); i++) {
int temp = s.charAt(i) - 'A' + 1;
sum = sum * 26 + temp;
}
return sum;
}
2017-01-12
172.阶乘的尾0(Factorial Trailing Zeroes)
要求：如题
思路：（自写AC）做过，数5的个数
public int trailingZeroes(int n) {
int num = 0;
while (n != 0) {
n /= 5;
num += n;
}
return num;
}
2017-01-12
223.Rectangle Area(矩形面积)
要求：求有可能重叠的两个举行组成的面积之和，其中A、B、C、D代表一个举行的左下和右上的顶点坐标，E、F、G、H代表另一个
思路：（discuss）求出重叠面积，巧用max来包括两矩形不重叠的情况
public int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
//已假设C > A, D > B; G > E, H > F
int left = Math.max(A, E), right = Math.max(Math.min(C, G), left); //防止两长方形左右不重叠
int bottom = Math.max(B, F), top = Math.max(Math.min(D, H), bottom); //防止上下不重叠
return (C - A) * (D - B) + (G - E) * (H - F) - (right - left) * (top - bottom);
}
2017-01-16
231.2的次方(Power of Two)
要求：判断是否二的次方
思路1：（discuss）由于2的次方只有1个位上是1，减去1与自己位运算的结果为0
public boolean isPowerOfTwo(int n) {
if (n <= 0) return false;
//2的次方对应二进制只有一个位是1
return (n & (n - 1)) == 0;
}
思路2：（discuss）直接数1的个数，bitCount()方法
public boolean isPowerOfTwo(int n) {
return n > 0 && Integer.bitCount(n) == 1;
}
2017-01-16
258.叠加数字(Add Digits)
要求：把数字的每一位加起来，直到只有个位数
思路1：（自写AC）按照题意，转成String遍历，暴力解法
public int addDigits(int num) {
while (num / 10 != 0) {
int sum = 0;
String numStr = num + "";
char[] numArr = numStr.toCharArray();
for (char c : numArr) {
int temp = c - '0';
sum += temp;
}
num = sum;
}
return num;
}
思路2：（discuss）利用9的性质，被9整除的数最终加起来是等于9，否则加起来是余数
public int addDigits(int num) {
return num == 0 ? 0 : (num % 9 == 0 ? 9 : (num % 9));
}
更优美的写法：
public int addDigits(int num) {
return 1 + (num - 1) % 9;
}
2017-01-16
263.丑数(Ugly Number)
要求：判断是否只被质数2, 3, 5整除，若是则为丑数
思路：（自写AC）三个if，能整除则除，最后为1则是丑数
warn：排除0，排除0，排除0
public boolean isUgly(int num) {
while (num != 0 && (num % 2 == 0 || num % 3 == 0 || num % 5 == 0)) {
if (num % 2 == 0) {
num /= 2;
}
if (num % 3 == 0) {
num /= 3;
}
if (num % 5 == 0) {
num /= 5;
}
}
return num == 1;
}
2017-01-16
264.丑数II(Ugly Number II)
要求：算出第n个丑数
思路：（自写AC）三个指针，与前一数比较，添加最小的一个数（动态规划...）
public int nthUglyNumber(int n) {
List<Integer> uglys = new ArrayList<>();
uglys.add(1);
int p2 = 0, p3 = 0, p5 = 0;
for (int i = 0; i <= n - 2; i++) {
int lastNum = uglys.get(i);
while (uglys.get(p2) * 2 <= lastNum) p2++;
while (uglys.get(p3) * 3 <= lastNum) p3++;
while (uglys.get(p5) * 5 <= lastNum) p5++;
uglys.add(Math.min(uglys.get(p5) * 5, //三个数最小值
Math.min(uglys.get(p2) * 2,
uglys.get(p3) * 3)));
}
return uglys.get(n - 1);
}
2017-01-16
319.灯泡开关(Bulb Switcher)
要求：进行到第i次操作时，凡是含有i为因子的灯泡序号，都进行一次开关操作
思路：（discuss）除了平方数，都有一个对称的数将其熄灭，所以直接算开方就行
public int bulbSwitch(int n) {
return (int)Math.sqrt(n);
}
2017-01-16
326.3的次方(Power of Three)
要求：判断一个数是否3的次方，不能用循环
思路：（cheating）直接算出int中最大的3的次方...还有其他数学运算上的方法，没意思
public boolean isPowerOfThree(int n) {
return n>0 && 1162261467 % n == 0;
}
2017-01-16
365.水桶问题(Water and Jug Problem)
要求：给出x和y容量的水桶，求能否得出z容量的水
思路：（search）根据定理，有解的情况就是x和y的最大公约数能整除z
tips：记住求最大公约数的方法，也就是一直做%运算
public boolean canMeasureWater(int x, int y, int z) {
return z == 0 || x + y >= z && z % gcd(x, y) == 0;
}
//求最大公约数
private int gcd(int x, int y) {
return y == 0 ? x : gcd(y, x % y);
}
2017-01-16
367.平方数(Valid Perfect Square)
要求：判断一个数是否为某数的平方
思路1：（discuss）二分法，查找1到num是否有数乘以自己是num
warn：定义为long类型防止溢出
public boolean isPerfectSquare(int num) {
long low = 1, high = num;
while (low <= high) {
long mid = (low + high) / 2;
if (mid * mid == num) {
return true;
} else if (mid * mid < num) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return false;
}
(Olog(n))
思路2：（discuss）平方数可以拆分成1 + 3 + 5 + ...
public boolean isPerfectSquare(int num) {
int i = 1;
while (num > 0) {
num -= i;
i += 2;
}
return num == 0;
}
(O(sqrt(n)))
2017-01-16
415.字符串相加(Add Strings)
要求：如题
思路：（自写AC）把每一位加起来就行
tips：for循环中只要有一个不溢出或还有进位就进入，进入后才判断有没有溢出的
public String addStrings(String num1, String num2) {
StringBuilder res = new StringBuilder();
int ca = 0;
for (int i = num1.length() - 1, j = num2.length() - 1;
i >= 0 || j >= 0 || ca == 1; i--, j--) {
int x = 0, y = 0;
if (i >= 0) {
x = num1.charAt(i) - '0';
}
if (j >= 0) {
y = num2.charAt(j) - '0';
}
int sum = x + y + ca;
res.append(sum % 10);
ca = (sum >= 10) ? 1 : 0;
}
return res.reverse().toString();
}
2017-01-16
Stack
456. 132 Pattern
要求：判断是否数组中能找出满足i < j < k，ai < ak < aj的三个数
思路：把一对数（两个）放进stack中，然后分析它们与第三个数的关系
public class Solution {
class Pair {
int min, max;
public Pair(int min, int max) {
this.min = min;
this.max = max;
}
}
public boolean find132pattern(int[] nums) {
Stack<Pair> stack = new Stack();
for (int n : nums) {
if (stack.isEmpty() || n < stack.peek().min) {
//压入较小的新元素n
stack.push(new Pair(n, n));
}
else if (n > stack.peek().min) {
Pair last = stack.pop();
if (n < last.max) {
return true;
}
else {
last.max = n;
//把不够新元素n大的对都弹出
while (!stack.isEmpty() && n >= stack.peek().max) {
stack.pop();
}
if (!stack.isEmpty() && stack.peek().min < n) {
return true;
}
stack.push(last);
}
}
}
return false;
}
}
![[翻译]LSP程序的分类](https://www.kunjuke.com/file/css/thumb/8.jpg/280-180.jpg)
