【lc刷题 day7】二叉搜索树与双向链表字符串的排列最小的k个数连续子数组的最大和数字序列中某一位的数字把数字翻译成字符串

剑指offer 36.二叉搜索树与双向链表 medium

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
    List<Node> list=new ArrayList<>();
    public Node treeToDoublyList(Node root) {
        if(root==null) return null;
        inorder(root);
        for(int i=0;i<list.size();i++){
            Node node=list.get(i);
            node.left=i==0?list.get(list.size()-1):list.get(i-1);
            node.right=i==list.size()-1?list.get(0):list.get(i+1);
        }
        return list.get(0);
    }
    void inorder(Node node){
        if(node==null) return;
        inorder(node.left);
        list.add(node);
        inorder(node.right);
    }
}

有一点需要注意，就是但root==null的时候，返回null
如果不判断这个边界条件的话通不过
时间复杂度O(n),空间复杂度O(n)

有一个hard题，二叉树的序列化，跳过去了

剑指offer 38.字符串的排序 medium

class Solution {
    public String[] permutation(String s) {
        Set<String> set=new HashSet<>();
        char[] arr=s.toCharArray();
        boolean[] visited=new boolean[arr.length];
        dfs(arr,"",visited,set);
        return set.toArray(new String[0]);
    }
    void dfs(char[] arr,String s,boolean[] visited,Set<String> set){
        if(s.length()==arr.length){
            set.add(s);
            return;
        }
        for(int i=0;i<arr.length;i++){
            if(visited[i]) continue;
            visited[i]=true;
            dfs(arr,s+String.valueOf(arr[i]),visited,set);
            visited[i]=false;
        }
    }
}

dfs的思想
其中 void dfs(char[] arr,String s,boolean[] visited,Set<String> set)
char[] arr为char数组，记录字符串s中每个字符
s为本次dfs的字符串结果
boolean[] visited记录字符是否出现过
Set<String> set是记录结果

剑指offer 39.数组中出现次数超过一般的数字 easy

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }
}

剑指Offer 40.最小的k个数 easy

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if(arr.length==0) return new int[0];
        quiksort(arr,0,arr.length-1);
        int[] res=new int[k];
        for(int i=0;i<k;i++){
            res[i]=arr[i];
        }
        return res;
    }
    void quiksort(int[] arr,int left,int right){
        int leftIndex=left,rightIndex=right;
        if(left>=right) return;
        int key=arr[left];
        while(left<right){
            while(left<right&&arr[right]>=key){
                right--;
            }
            arr[left]=arr[right];
            while(left<right&&arr[left]<=key){
                left++;
            }
            arr[right]=arr[left];
        }
        arr[left]=key;
        quiksort(arr,leftIndex,left-1);
        quiksort(arr,right+1,rightIndex);
    }
}

写了一个快排，各个排序算法还需要复习一下
时间复杂度O(nlogN),空间复杂度O(logN)

跳过了一个hard，数据流中的中位数

剑指Offer 42.连续子数组的最大和 easy

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

动态规划的思想
dp[i]代表以i为结尾的连续子数组的最大和
时间复杂度O(N),空间复杂度O(n)
这道题还有更好的方法，空间复杂度可以简化为O(1)

跳过了一道hard

剑指 Offer 44. 数字序列中某一位的数字

class Solution {
    public int findNthDigit(int n) {
        int digit = 1;
        long start = 1;
        long count = 9;
        while (n > count) { // 1.
            n -= count;
            digit += 1;
            start *= 10;
            count = digit * start * 9;
        }
        long num = start + (n - 1) / digit; // 2.
        return Long.toString(num).charAt((n - 1) % digit) - '0'; // 3.
    }
}

蚌埠住了，好难

剑指 Offer 46. 把数字翻译成字符串 medium

class Solution {
    public int translateNum(int num) {
        String s=num+"";
        int a=1,b=1;
        for(int i=1;i<s.length();i++){
            String substring=s.substring(i-1,i+1);
            if(substring.compareTo("10")>=0&&substring.compareTo("26")<0){
                b=b+a;
                a=b-a;
            }else{
                a=b;
            }
        }
        return b;
    }
}