解题--＞在线OJ(十三)

1.二叉搜索树的最近公共祖先（235）

解题思路：
1.首先判断p,q是否为同一个节点；
2.其次，判断p,q节点是否为根节点，如果其中之一是根节点，直接返回根节点就好了；
3.判断p,q节点的位置，二叉搜索树的特点是：左<中<右，依据这个来判断，p,q节点是位于根节点的左侧还是右侧还是分布在根节点的两侧，依据判断出来的结果来做出相应的操作。
4.如果是左侧，直接递归调用，将传入的参数，根节点换成根节点的左节点，如果是右侧，将根节点换成根节点的右节点。如果分布在根节点的左右两侧，就直接返回根节点即可。

class Solution {
    
      public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    
        if(p.val==q.val){
    
            return p;
        }
        if(root.val==p.val || root.val==q.val){
    
            return root;
        }
        if(p.val<root.val && q.val<root.val){
    
            return lowestCommonAncestor(root.left,p,q);
        }else if(p.val>root.val && q.val>root.val){
    
            return lowestCommonAncestor(root.right,p,q);
        }else{
    
            return root;
        }
    }
}

2.反转字符串中的单词III(557)

解题思路：
本题反转字符串，要求，以空格为断点，每一个单词独立反转，所以，解这个题目：
首先，需要将这个字符串以空格分割，分割成一个字符数组，然后再对每一个单词进行反转，在每一个单词反转之后，都需要再加上一个空格。最后，需要把stringBuilder类型转化为String类型。

class Solution {
    
 public  static String reverseWords(String s) {
    
        String[] ret=s.split(" ");
        StringBuilder stringBuilder=new StringBuilder();
        for(int i=0;i<ret.length;i++){
    
           stringBuilder.append(reverse(ret[i]));
           if(i!=ret.length-1){
    
               stringBuilder.append(" ");
           }
        }
        return stringBuilder.toString();
    }
    public static String reverse(String s){
    
        StringBuilder stringBuilder=new StringBuilder(s);
        return stringBuilder.reverse().toString();

    }
}

3.Fizz Buzz(412)

class Solution {
    
   public List<String> fizzBuzz(int n) {
    
        List<String> list=new ArrayList<>();
        for(int i=1;i<=n;i++){
    
            if(i%3==0 && i%5==0){
    
                list.add("FizzBuzz");
            } else if(i%3==0){
    
                list.add("Fizz");
            }else if(i%5==0){
    
                list.add("Buzz");
            }else{
    
                list.add(i+"");
            }
        }
        return list;
    }
}

4.LRU缓存(146)

解题思路：
1.LinkedHashMap:哈希表和链表实现的Map接口，具有可预测的迭代次序。 这种实现不同于HashMap，它维持于所有条目的运行双向链表。 此链接列表定义迭代排序，通常是将键插入到地图（插入顺序 ）中的顺序 。 请注意，如果将键重新插入到地图中，则插入顺序不受影响。 （A键k被重新插入到地图m如果当m.containsKey(k)将返回true之前立即调用m.put(k, v)被调用。）
2.
有三个参数：第一个表示：初始容量，第二个表示负载因子，第三个参数：如果为true：就表示按照 时间访问顺序，如果为false,就按照数据元素插入顺序。
3.
removeEldestEntry：当数据插入的数量大于capacity的时候，会按照时间访问顺序，删除最久没有访问的<key,value>.
4.
getOrDefault：如果找到了key，返回其对应的值，如果没有找到，直接返回-1。

class LRUCache {
    
int capacity;
    LinkedHashMap<Integer,Integer> linkedHashMap;
    public LRUCache(int capacity) {
    
        this.capacity=capacity;
        linkedHashMap=new LinkedHashMap<Integer, Integer>(capacity,0.75f,true){
    
          @Override
          protected boolean removeEldestEntry(Map.Entry eldest){
    
              return size()>capacity;
          }
        };
    }

    public int get(int key) {
    
        return linkedHashMap.getOrDefault(key,-1);
    }

    public void put(int key, int value) {
    
        linkedHashMap.put(key,value);
    }
}

5.排序链表（148）

解题思路：
用归并方式解决。
将链表拆分，然后再合并。
归并方式的时间复杂度:O(N*(log2 N)),空间复杂度:O(N)

class Solution {
    
  public static ListNode sortList(ListNode head) {
    
       if(head ==null || head.next ==null){
    
           return head;
       }
       ListNode slow =head;
       ListNode fast =head.next;
       //找到链表中间结点，目的是为了后续的将链表一分为二。
       while(fast!=null && fast.next!=null){
    
           slow=slow.next;
           fast =fast.next.next;
       }
       ListNode newNode2=slow.next;
       slow.next =null;
       //递归调用，目的是：不断的拆分链表，直到拆成一个一个的结点
       ListNode left = sortList(head);
       ListNode right =sortList(newNode2);
       //链表拼接
       //tempHead：作为拼接链表的临时头结点
       ListNode tempHead =new ListNode(0);
       ListNode h=tempHead;
       //实施链表拼接
       while(left!=null && right!=null){
    
           if(left.val<=right.val){
    
               h.next=left;
               left =left.next;
           }else{
    
               h.next=right;
               right=right.next;
           }
            h=h.next;
       }
       //当左边链表为空或者右边链表为空的时候，将不为空的链表接在h结点之后，然后，返回临时结点的下一个结点。
       h.next=left!=null?left:right;
       return tempHead.next;
    }
}

6.乘积最大子数组(152)

解题思路：
这个题目求解的是：连续序列的最大乘积。
设置两个临时数组，一个存放每次计算结果的最大值，一个存放每次计算结果的最小值，然后再根据每次计算结果的最大值来不断的更新替换max。
举例分析：[-2,1,3,-4]
numsMax:[-2,1,3,24]
numsMin:[-2,-2,-6,-6]
max=24

class Solution {
    
       public static int maxProduct(int[] nums) {
    
        int length=nums.length;
        int[] numsMax=new int[length];
        int[] numsMin=new int[length];
        numsMax[0]=nums[0];
        numsMin[0]=nums[0];
        int max=numsMax[0];
        for(int i=1;i<nums.length;i++){
    
            numsMax[i]=Math.max(nums[i],Math.max(numsMax[i-1]*nums[i],numsMin[i-1]*nums[i]));
            numsMin[i]=Math.min(nums[i],Math.min(numsMax[i-1]*nums[i],numsMin[i-1]*nums[i]));
            max=Math.max(numsMax[i],max);
        }
        return max;
    }
}

7.打家劫舍(198)

动态规划，
设置一个dp数组，这里面记录每一项的最优值，
比如:[7,2,9,3,1]
dp[0]=7;
dp[1]=7;(dp[1]=Math.max(dp[0],nums[1]):这么做的原因是:dp数组表示每一步的最优值，对于只能选择1号屋和2号屋来说，我们最好的选择是1号屋)；
dp[2]=16;Math.max(7,9+7)=16
dp[3]=16;Math.max(16,3+7)=16
dp[4]=17;Math.max(16,16+1)=17

class Solution {
    
 public static int rob(int[] nums) {
    
       if(nums.length==1){
    
            return nums[0];
        }
      int length=nums.length;
     int dp[]=new int[length];
     dp[0]=nums[0];
     dp[1]=Math.max(dp[0],nums[1]);
     for(int i=2;i<length;i++){
    
         dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);
     }
     return dp[length-1];
    }
}

8.岛屿数量（200）

class Solution {
    
  public static int numIslands(char[][] grid) {
    
        int row=grid.length;
        int col=grid[0].length;
        int result=0;
        for(int i=0;i<row;i++){
    
            for(int j=0;j<col;j++){
    
                if(grid[i][j]=='1'){
    
                    result++;
                    dfs(grid,i,j);
                }
            }
        }
        return result;
    }
    public static void dfs(char[][] grid,int i,int j){
    
        if(i<0 || j<0 || i>=grid.length || j>=grid[0].length || grid[i][j]=='0'){
    
            return;
        }
        grid[i][j]='0';
        dfs(grid,i+1,j); //下
        dfs(grid,i-1,j); //上
        dfs(grid,i,j-1); //左
        dfs(grid,i,j+1); //右
    }
}

9.Z字形变换(6)

class Solution {
    
  public String convert(String s, int numRows) {
    
               StringBuilder[] stringBuilders=new StringBuilder[numRows];
        for(int i=0;i<stringBuilders.length;i++){
    
            stringBuilders[i]=new StringBuilder();
        }
       char[] temp=s.toCharArray();
        int length=s.length();
        for(int i=0;i<length;){
    
            for(int row=0;row<numRows&&i<length;row++){
    
                stringBuilders[row].append(temp[i]);
                i++;
            }
            for(int row=numRows-2;row>0&&i<length;row--){
    
                stringBuilders[row].append(temp[i]);
                i++;
            }
        }
        StringBuilder result=new StringBuilder();
        for(StringBuilder t:stringBuilders){
    
            result.append(t);
        }
        return result.toString();
    }
}

10.从前序与中序遍历序列构造二叉树（105）

class Solution {
    
  public TreeNode buildTree(int[] preorder, int[] inorder) {
    
        TreeNode root= createTree(preorder,0,inorder,0,inorder.length-1);
        return root;
    }
    public TreeNode createTree(int[] preorder,int rootIndex,int[] inorder,int left,int right){
    
        if(rootIndex>=preorder.length || left>right){
    
            return null;
        }
        TreeNode root=new TreeNode(preorder[rootIndex]);
        int i=0;
        for(;i<inorder.length;i++){
    
            if(root.val==inorder[i]){
    
                break;
            }
        }
        root.left=createTree(preorder,rootIndex+1,inorder,left,i-1);
        root.right=createTree(preorder,i+rootIndex-left+1,inorder,i+1,right);
        return root;
    }
}