41. 缺失的第一个正数
思路：让数组的第i个位置应该存放值i + 1
本题是一道纯算法题，和数据结构无关，而且题目中的说明几乎把算法给限定死了。这个思路也很巧妙，对于一个正数number，我们将其放在数组nums中第number – 1个位置。具体的实现见JAVA代码，写几个注意点。
（1）交换的过程不是一次完成的，而是一个循环过程。
（2）终止循环的条件有以下三个：
a.当nums[i] <= 0时，我们应该终止循环，因为我们不知道这个值应该放在哪里。
b.当nums[i] > nums.length时，我们应该终止循环，因为我们不知道这个值应该放在哪里。
c.当nums[nums[i] – 1] == nums[i]时，我们应该终止循环，因为此时数组中索引为i的位置已经存放了正确的数。
注意：这个条件容易弄错。
（3）交换过程结束之后，遍历nums数组，寻找第一个nums[i]不等于i + 1的位置，返回即可。如果遍历完整个数组都没有找到，则说明该数组中的元素是[1, 2, 3, 4, …]的一个排列形式，我们应该返回nums.length + 1。
注意：交换前的那个条件是while，不能写成if，因为交换了之后，还要进行判断，如果满足上述的条件还需要继续交换
public class Solution {
//position i must be put number i + 1
public int firstMissingPositive(int[] nums) {
for (int i = 0; i < nums.length; i++) {
while(nums[i] > 0 && nums[i] <= nums.length && nums[nums[i] - 1] != nums[i]) {
swap(nums, i, nums[i] - 1);
}
}
for (int i = 0; i < nums.length; i++) {
if(nums[i] != i + 1) {
return i + 1;
}
}
return nums.length + 1;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
42. 接雨水
LeetCode 解题链接
注意：最两端的列是不用考虑的，因为一定不会有水
方法1：动态规划：
class Solution {
public int trap(int[] height) {
int ans = 0;
int[] max_left = new int[height.length];
int[] max_right = new int[height.length];
for(int i = 1;i < height.length -1;i++){
max_left[i] = Math.max(height[i-1],max_left[i-1]);
}
for(int i = height.length-2;i>0;i--){
max_right[i] = Math.max(height[i+1],max_right[i+1]);
}
for(int i = 1;i<height.length-1;i++){
int min = Math.min(max_left[i],max_right[i]);
if(min > height[i]){
ans = ans + (min - height[i]);
}
}
return ans;
}
}
43.字符串相乘
LeetCode 参考链接
易错：
1.对于两个数相乘和相加的时候carry!=0的条件最容易遗忘
2.还有相乘的时候StringBuilder放置的位置也必须是在循环之内
3.对于StringBuilder到String之间的转换
class Solution {
public String multiply(String num1, String num2) {
if(num1.equals("0") || num2.equals("0")){
return "0";
}
String res = "0";
for(int i = num2.length()-1;i>=0;i--){
int carry = 0;
StringBuilder temp = new StringBuilder();
for(int j = 0;j<num2.length()-1-i;j++){ //对最后的结果进行补0操作
temp.append(0);
}
int n2 = num2.charAt(i) -'0';
for(int k = num1.length()-1;k>=0||carry!=0;k--){
int n1 = k<0?0:num1.charAt(k) -'0';
int product =(n1*n2+carry)%10;
temp.append(product);
carry = (n1*n2+carry)/10;
}
res =addString(res,temp.reverse().toString());
}
return res;
}
public String addString(String s1,String s2){
int carry = 0;
StringBuilder sb = new StringBuilder();
for(int i = s1.length()-1,j = s2.length()-1;i>=0||j>=0 ||carry!=0;i--,j--){
int x = i>=0?s1.charAt(i)-'0':0;
int y = j>=0?s2.charAt(j)-'0':0;
int sum = (x+y+carry)%10;
sb.append(sum);
carry = (x+y+carry)/10;
}
return sb.reverse().toString();
}
}
49. 字母异或词分组
LeetCode 参考链接
注意：
1.将字符串对象转换成一个字符数组：toCharArray();
2.对于HashMap中，去所有Values的值。map.values（）；
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String,List<String>> map = new HashMap<>();
for(int i = 0;i < strs.length;i++){
char[] ans = strs[i].toCharArray();
Arrays.sort(ans);
String key = String.valueOf(ans);
if(map.containsKey(key)){
map.get(key).add(strs[i]);
}else{
List<String> temp = new ArrayList<>();
temp.add(strs[i]);
map.put(key,temp);
}
}
return new ArrayList<List<String>>(map.values());
}
}
50. Pow(x,n)
class Solution {
public double myPow(double x, int n) {
double res = 1;
if(equal(x,0)){
return 0;
}
if(n == 0){
return 1.0;
}
if(n> 0 ){
res = helper(x,n);
}else{
res= helper(1/x,-n);
}
return res;
}
public double helper(double x,int n){
double res = 1;
for(int i = 0;i < n;i++){
res = res * x;
}
return res;
}
public boolean equal(double a,double b){
if(a - b < 0.000001 && a-b > -0.000001){
return true;
}
return false;
}
}
53. 最大子序和
其实这道题可以这么想： 1.假如全是负数，那就是找最大值即可，因为负数肯定越加越大。 2.如果有正数，则肯定从正数开始计算和，不然前面有负值，和肯定变小了，所以从正数开始。 3.当和小于零时，这个区间就告一段落了，然后从下一个正数重新开始计算(也就是又回到 2 了)。而 dp 也就体现在这个地方。
class Solution {
public int maxSubArray(int[] nums) {
int ans = nums[0];
int sum = 0;
for(int i = 0;i < nums.length;i++){
if(sum > 0){
sum += nums[i];
}else{
sum = nums[i];
}
ans = Math.max(ans,sum);
}
return ans;
}
}
56.合并区间
class Solution {
private static class Interval {
int start;
int end;
Interval(int[] interval) {
this.start = interval[0];
this.end = interval[1];
}
int[] toArray() {
return new int[]{this.start, this.end};
}
}
private static class IntervalComparator implements Comparator<Interval> {
@Override
public int compare(Interval a, Interval b) {
return Integer.compare(a.start, b.start);
}
}
public int[][] merge(int[][] intervals) {
List<Interval> intervalsList = new LinkedList<>();
for (int[] interval : intervals) {
intervalsList.add(new Interval(interval));
}
intervalsList.sort(new IntervalComparator());
LinkedList<Interval> merged = new LinkedList<>();
for (Interval interval : intervalsList) {
// if the list of merged intervals is empty or if the current
// interval does not overlap with the previous, simply append it.
if (merged.isEmpty() || merged.getLast().end < interval.start) {
merged.add(interval);
}
// otherwise, there is overlap, so we merge the current and previous
// intervals.
else {
merged.getLast().end = Math.max(merged.getLast().end, interval.end);
}
}
int i = 0;
int[][] result = new int[merged.size()][2];
for (Interval mergedInterval : merged) {
result[i] = mergedInterval.toArray();
i++;
}
return result;
}
}