5.9 LeetCode
leetcode
2 分钟 读完 (大约 239 个字)

5.9 LeetCode

166. Fraction to Recurring Decimal

  1. 分数到小数
    给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以字符串形式返回小数。
    如果小数部分为循环小数，则将循环的部分括在括号内。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        long n=Math.abs((long)numerator),d=Math.abs((long)denominator);
        StringBuilder sb=new StringBuilder();
        if((long)numerator * (long)denominator < 0)
            sb.append("-");
        sb.append(String.valueOf(n/d));
        n%=d;
        if(n==0) return sb.toString();
        sb.append(".");
        int t=2;
        while(t<n){
            if((n/t)*t==n &&(d/t)*t==d)
            {
                n/=t;d/=t;
            }
            else t++;
        }
        //System.out.println(n+"   "+d);
        long index=sb.length();
        HashMap<Long,Long> m=new HashMap<>();
        while(n!=0){
            if(m.containsKey(n)){
                sb.insert(Integer.parseInt(m.get(n).toString()),"(");
                sb.append(")");
                break;
            }
            m.put(n,index);
            n*=10;
            sb.append(n/d);
            n=n%d;
            index++;
        }
        return sb.toString();
        
    }

}

371. Sum of Two Integers

371.两整数之和
不使用运算符 + 和 - ​​​​​​​，计算两整数 ​​​​​​​a 、b ​​​​​​​之和。

1
2
3
4
5
class Solution {
    public int getSum(int a, int b) {
        return b == 0 ? a : getSum(a^b,(a&b)<<1); 
    }
}
5.8 LeetCode
leetcode
1 分钟 读完 (大约 212 个字)

5.8 LeetCode

171. Excel Sheet Column Number

  1. Excel表列序号
1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int titleToNumber(String s) {
        int res=0;
        for(int i=0;i<s.length();i++){
            res*=26;
            res+=(s.charAt(i)-'A'+1);
        }
            
        return res;
    }
}

50. Pow(x, n)

50.Pow(x,n)
很经典的一道题。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public double myPow(double x, int n) {
        double res = 1.0;
        for(int i = n; i != 0; i /= 2){
            if(i % 2 != 0){
                res *= x;
            }
            x *= x;
        }
        return  n < 0 ? 1 / res : res;
    }
}

29. Divide Two Integers

  1. 两数相除
    给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
    返回被除数 dividend 除以除数 divisor 得到的商。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int divide(int dividend, int divisor) {
        boolean flag=(dividend>=0&&divisor>0)||(dividend<=0&&divisor<0);
        int res=0;
        long m=Math.abs((long)dividend);
        long n=Math.abs((long)divisor);
        int i=31;
        while(i>=0&&res<=Integer.MAX_VALUE){
            if((m>>i)>=n){
                res+=1<<i;
                m-=n<<i;
            }
                
            i--;
        } 
         if(res==Integer.MIN_VALUE&&flag)
            return Integer.MAX_VALUE;
        if(res==Integer.MIN_VALUE&&!flag)
            return Integer.MIN_VALUE;
        if(flag) return res; 
        return -res;
    }
}
5.7LeetCode
leetcode
3 分钟 读完 (大约 434 个字)

5.7LeetCode

昨天太累了，就没更新。。今天一起更下。
昨天主要做的基本都是比较简单的dp题目。

55. Jump Game

55.跳跃游戏

因为是dp专题，所以肯定有dp解法：其实感觉也不算严谨的dp吧。。canGo[n]表示n可否到达

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean canJump(int[] nums) {
        boolean[] canGo=new boolean[nums.length];
        canGo[0]=true;
        for(int i=0;i<nums.length;i++){
            if(canGo[i]){
                int j=i+1;
                while(j<nums.length&&j<=i+nums[i]){
                    canGo[j]=true;
                    j++;
                }   
            }
            if(canGo[nums.length-1]) return true;
        }
        return canGo[nums.length-1];
    }
}

还有种复杂度是O(n)的解法，求出从0出发可以到达的最远点。

1
2
3
4
5
6
7
8
9
10
class Solution {
    public boolean canJump(int[] nums) {
        int maxlength=nums[0];
        for(int i=0;i<=maxlength;i++){
            if(maxlength>=nums.length-1) return true;
            if(nums[i]+i>maxlength) maxlength=nums[i]+i;
        }
        return false;
    }
}

62. Unique Paths

62.不同路径

dp解法非常简单。。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp=new int[m][n];
        for(int i=0;i<n;i++) 
            dp[0][i]=1;
        for(int i=0;i<m;i++)
            dp[i][0]=1;
        for(int i=1;i<m;i++)
            for(int j=1;j<n;j++)
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
        return dp[m-1][n-1];
    }
}

另外一种解法就是求C(m-1,m+n-2)。

322. Coin Change

  1. 零钱兑换
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int coinChange(int[] coins, int amount) {
        if(amount==0) return 0;
        int[] dp=new int[amount+1];
        for(int i=0;i<amount+1;i++)
            dp[i]=Integer.MAX_VALUE;
        for(int i:coins)
            if(i<=amount)
                dp[i]=1;  
        for(int i=1;i<amount+1;i++)
            for(int j:coins){
                if(i-j>0&&dp[i-j]!=Integer.MAX_VALUE&&dp[i-j]+1<dp[i])
                    dp[i]=dp[i-j]+1;
            }
        //return dp[amount];
        return dp[amount]==Integer.MAX_VALUE? -1:dp[amount];
    }
}

300. Longest Increasing Subsequence

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp=new int[nums.length];
        for(int i=0;i<nums.length;i++)
            dp[i]=1;
        for(int i=1;i<nums.length;i++)
            for(int j=i-1;j>=0;j--)
                if(nums[i]>nums[j]&&dp[j]+1>dp[i])
                    dp[i]=dp[j]+1;
        int max=0;
        for(int i:dp){
            //System.out.println(i);
            if(i>max)
                max=i;
            
        }
            
        return max;
    }
}

297. Serialize and Deserialize Binary Tree

  1. 二叉树的序列化与反序列化
    一道不是非常hard的hard题，深切感受到了StringBuffer的快速。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        Queue<TreeNode> queue=new LinkedList<>();
        StringBuffer res=new StringBuffer();
        if(root==null) return res.toString();
        res.append(String.valueOf(root.val));
        queue.offer(root.left);
        queue.offer(root.right);
        while(!queue.isEmpty())
        {
            int size=queue.size();
            for(int i=0;i<size;i++){
                TreeNode t=queue.poll();
                if(t==null){
                    res.append(",null");
                }
                else{
                    res.append(",");
                    res.append(String.valueOf(t.val));
                    queue.offer(t.left);
                    queue.offer(t.right);
                }
            }
        }
        //System.out.println(res);
        return res.toString();
        
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data.length()==0) return null;
        String[] s=data.split(",");
        int n=s.length;
        for(int i=s.length-1;i>=0;i--)
            if(s[i].equals("null"))
                n--;
            else break;
        // for(int i=0;i<n;i++)
        //     System.out.println(s[i]);

        TreeNode[] node=new TreeNode[n];
        int j=1;
        for(int i=0;i<n;i++)
            if(!s[i].equals("null"))
                node[i]=new TreeNode(0);
            else node[i]=null;
        for(int i=0;i<n;i++)      
           if(!s[i].equals("null")){
               node[i].val=Integer.parseInt(s[i]);
               if(j<n&&!s[j].equals("null")) node[i].left=node[j];
               j++;
               if(j<n&&!s[j].equals("null")) node[i].right=node[j];
               j++;
               
            }
            else node[i]=null; 
         
        return node[0];
           
    }
}

172. Factorial Trailing Zeroes

  1. 阶乘后的零
    数学题。找规律。还以优化下，从两次循环减少到1次循环。
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int trailingZeroes(int n) {
        int max=0; int t=n;
        while(t!=0){
            t=t/5;
            max++;
        }
        int res=0;
        for(int i=1;i<max;i++)
            res+=n/Math.pow(5,i);
        return res;
    }
}
5.5LeetCode
leetcode
8 分钟 读完 (大约 1165 个字)

5.5LeetCode

215. Kth Largest Element in an Array

  1. 数组中的第K个最大元素
    感觉是非常经典的一道题目，一开始自己尝试了下手写快排。。一堆bug，又百度学了半天快排算法。。然后试了下评论区大佬的最小堆，这快的也太多了把！完全不是一个数量级的。
    感觉手写一个堆结构也是很基本的能力，任重而道远。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int findKthLargest(int[] nums, int k) {
        int left=0,right=nums.length-1;
        while (true) {
            int pos = help(left,right,nums);
            if (pos == k - 1) return nums[pos];
            else if (pos > k - 1) right = pos - 1;
            else left = pos + 1;
        }
    }
    public int help(int left,int right, int[] nums){
        int pivot = nums[left], l = left + 1, r = right;
        while (l <= r) {
            if (nums[l] < pivot && nums[r] > pivot) {
                int temp=nums[l]; nums[l]=nums[r]; nums[r]=temp;
                l++;
                r--;
            }
            if ( nums[l] >= pivot) ++l;
            if (nums[r] <= pivot) --r;
        }
        int temp=nums[r];
        nums[r]=nums[left];
        nums[left]=temp;
        return r;
    }
}

解法2️：最小堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
    //堆排序的过程就是首先构建大根堆，然后对顶元素（及最大元素）与最后个元素替换位置，heapsize减一，重新调整堆变成大根堆。
    //重复上面操作直到heapsize等于一的时候。排序完成。
    public int findKthLargest(int[] nums, int k) {
        // 建一个大小为k+1(第一个结点不使用)的数组
        int[] heap = new int[k+1];  
         for(int i = 0; i < k; i++){
            heap[i+1] = nums[i];
        }
        
        // 堆化。建立一个大小为k的小顶堆
        // 从最后一个非叶子结点k/2自上往下开始进行堆化，该结点堆化完后就轮到前一个非叶子结点再自上往下进行堆化
        for(int i = k/2; i > 0; i--){
            heapify(heap,k+1,i);
        }       
        // 继续遍历数组中剩余的数字，并与堆顶元素进行比较，
        // 若大于堆顶元素，则替换掉堆顶元素，并自顶向下堆化
        for(int i = k; i < nums.length; i++){
            if(nums[i] > heap[1]){
                heap[1] = nums[i];
                heapify(heap,k+1,1);
            }
        }
        return heap[1];
    }
    // 自顶向下堆化。一般在删除堆顶结点后，把最后一个结点放到堆顶的时候使用。
    // 即这时堆中已经是部分堆化
    private void heapify(int[] heap,int len,int index){
        while(true){
            // 找出当前结点和两个直接子结点的最小值
            int minPos = index;   
            if(2*index < len && heap[2*index] < heap[minPos]){
                minPos = 2*index;
            }
            if(2*index+1 < len && heap[2*index+1] < heap[minPos]){
                minPos = 2*index + 1;
            }
            // 若当前结点是最小的，说明下面的是堆化好的了，直接退出循环
            if(minPos == index){
                break;
            }
            // 当前结点与最小值进行交换
            swap(heap,index,minPos);
            // 当前结点更改为最小直接子结点，继续往下堆化
            index = minPos;
        }
    }
    private void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

56. Merge Intervals

56.合并区间
看评论区，基本上都是先按照区间头排序，然后再处理。自己写了个不用sort的算法，用map去替代。有点开心。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> res;
        map<int,int> hashmap;
        for(int i=0;i<intervals.size();i++){
            auto it=hashmap.find(intervals[i][0]); //处理该区间起点
            if(it==hashmap.end()) //先前未访问过该结点
                hashmap[intervals[i][0]]=1;
            else hashmap[intervals[i][0]]++;
            it=hashmap.find(intervals[i][1]);  //处理区间终点
            if(it==hashmap.end())  //先前未访问过
                hashmap[intervals[i][1]]=-1;
            else hashmap[intervals[i][1]]--;
        }
        for(auto it=hashmap.begin();it!=hashmap.end();it++){
            vector<int> temp;
            temp.push_back(it->first);
            int cnt=0;
            while(1) {
                cnt+=it->second;
                if(cnt<=0) break;
                it++;
            }
            temp.push_back(it->first);
            res.push_back(temp);
        }
        return res;
    }
};

240. Search a 2D Matrix II

  1. 搜索二维矩阵 II
    也就错了这么十几次。。。自闭了。 在分治到2*2范围时我就有点不知道该如何处理了。越写头越晕，无限改BUG。
    不过最后效率还是相当不错的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix.length==0||matrix[0].length==0) return false;
        int m=matrix.length;
        int n=matrix[0].length;
        return help(matrix,0,n-1,0,m-1,target);
    }
    public boolean help(int[][] matrix,int left,int right,int top,int button,int target){
        //System.out.println(left+"+"+right+"+"+top+"+"+button);
        if(left<0||right>=matrix[0].length||top<0||button>=matrix.length||left>right||top>button) return false;
        if(left==right&&top==button) return (matrix[top][right]==target);
        if(right-left==1&&button-top==1) return matrix[top][left]==target||matrix[top][right]==target||matrix[button][left]==target||matrix[button][right]==target;
        if(right-left==1&&button==top) return matrix[top][left]==target||matrix[top][right]==target;
        if(button-top==1&&right==left) return matrix[button][left]==target||matrix[top][left]==target;
        int midi=(top+button)/2;
        int midj=(left+right)/2;
        //System.out.println(midi+"+"+midj);
        if(matrix[midi][midj]==target) return true;
        else if(matrix[midi][midj]>target){
            boolean t=help(matrix,left,midj,top,midi,target);
            if(t) return true;
            if(matrix[midi][left]<=target)
                t=help(matrix,left,midj-1,midi+1,button,target);
            if(t) return true;
            if(matrix[top][midj]<=target)
                t=help(matrix,midj+1,right,top,midi-1,target);
            if(t) return true;
        }
        else if(matrix[midi][midj]<target){
            boolean t=help(matrix,midj,right,midi,button,target);
            if(t) return true;    
            if(matrix[button][midj]>=target)
                 t=help(matrix,left,midj-1,midi+1,button,target);
            if(t) return true;
            if(matrix[midi][right]>=target)
                t=help(matrix,midj+1,right,top,midi-1,target);
            if(t) return true;
        }
        return false;
    }
}

感觉时间真的挺紧的，今天上午有点事情就没学习，下午和晚上加起来也就只能刷个三题，书也看不了多少啦。

190504
leetcode
2 分钟 读完 (大约 318 个字)

190504

46. Permutations

46.全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res =new ArrayList<>();
        List<Integer> t= new ArrayList<>();
        boolean[] visited=new boolean[nums.length];
        helpBFS(res,t,nums,visited);
        return res;
        
    }
    public void helpBFS(List<List<Integer>> res,List<Integer> t,int[] nums,boolean[] visited){
        if(t.size()==nums.length){
            List<Integer> temp=new ArrayList<>();
            for(Integer i:t)
                temp.add(i);
            res.add(temp);
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(visited[i]) continue;
            else{
                t.add(nums[i]);
                visited[i]=!visited[i];
                helpBFS(res,t,nums,visited);
                t.remove((Integer)nums[i]);
                visited[i]=!visited[i];
            }
        }
    }
}

78. Subsets

  1. 子集
    和上一题类似
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res=new ArrayList<>();
        List<Integer> t=new ArrayList<>();
        boolean[] visited=new boolean[nums.length];
        help(res,t,visited,nums,0);
        return res;
    }
    public void help(List<List<Integer>> res,List<Integer> t,boolean[] visited,int[] nums,int start){
        res.add(new ArrayList(t));
        for(int i=start;i<nums.length;i++){
            if(visited[i]) continue;
            else{
                t.add(nums[i]);
                visited[i]=true;
                help(res,t,visited,nums,i+1); //关键点，从i+1往回再考虑
                visited[i]=false;
                t.remove((Integer)nums[i]);
            }
        }
    }
}
  1. 单词搜索
    DFS+回溯。。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
    public boolean exist(char[][] board, String word) {
        if(word.length()>board.length*board[0].length) return false;
        for(int i=0;i<board.length;i++)
            for(int j=0;j<board[0].length;j++){
                if(board[i][j]==word.charAt(0))
                {
                    boolean[][] visited=new boolean[board.length][board[0].length];
                    visited[i][j]=true;
                    boolean temp=help(i,j,board,word,0,visited);
                    if(temp) return true;
                }
            }
        return false;
    }
    public boolean help(int i,int j,char[][] board,String word,int num,boolean[][] visited){
        if(i<0||i>board.length||j<0||j>board[0].length||word.charAt(num)!=board[i][j]) return false;
        if(num+1==word.length()) return true;
        boolean t1,t2,t3,t4;
        t1=t2=t3=t4=false;
        if(i-1>=0&& board[i-1][j]==word.charAt(num+1)&&visited[i-1][j]==false) {
            visited[i-1][j]=true;
            if(t1=help(i-1,j,board,word,num+1,visited)) return true; 
            visited[i-1][j]=false;
        } 
        if(j+1<board[0].length&&board[i][j+1]==word.charAt(num+1)&&visited[i][j+1]==false) {
            visited[i][j+1]=true;
            if(t2=help(i,j+1,board,word,num+1,visited)) return true;
            visited[i][j+1]=false;  
        } 
        if(i+1<board.length&&board[i+1][j]==word.charAt(num+1)&&visited[i+1][j]==false)  {
            visited[i+1][j]=true;
            if(t3=help(i+1,j,board,word,num+1,visited)) return true;
            visited[i+1][j]=false;
        }
        if(j-1>=0&& board[i][j-1]==word.charAt(num+1)&&visited[i][j-1]==false){
            visited[i][j-1]=true;
            if(t4=help(i,j-1,board,word,num+1,visited)) return true;
            visited[i][j-1]=false;
        } 
        return false;
    }
}

75. Sort Colors

75.颜色分类
三路快排

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public void sortColors(int[] nums) {
        int i=-1,j=nums.length;
        int k=0;
        while(k<j){
            if(nums[k]==0){
                i++;   
                nums[k]=nums[i];
                nums[i]=0;                 
                k++;
            }
            else if(nums[k]==2){
                j--;    
                nums[k]=nums[j];
                nums[j]=2;                
            }
            else k++;
        }
    }
}
5.3LeetCode
leetcode
9 分钟 读完 (大约 1361 个字)

5.3LeetCode

前两天放假，就没更新，每天也做不了几题，今天集中更新下。

步入五月，感觉生活正在逐渐变得紧凑，这学期的课程都还没咋学，还有三门实验课要应付，再加上最近开始看java了，所以以后刷题量可能会减少点，但肯定不会停下！
还有个问题就是，初级算法卡片刷完了，现在开始刷中级算法了，感觉好难啊！。。头秃。

15.3Sum

15.三数之和
C++.感觉好难啊！一开始不知道为什么总想着用map做，试了半天总是无法解决漏解的问题。。
看了答案才会做。
第一个是三指针的处理方式，将复杂度从O(n^3)降到了O(n^2)。学习了。
第二个是重复解的剔除，不需要通过set就可以实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        std::sort(nums.begin(),nums.end());
        vector<vector<int>> res; 
        int n=nums.size();
        for(int k=n-1;k>1;k--){
            int i=0,j=k-1;
            while(i<j){
                if(nums[i]+nums[j]+nums[k]>0) j--;
                else if(nums[i]+nums[j]+nums[k]<0) i++;
                else{
                    vector<int> temp={nums[i],nums[j],nums[k]};
                    res.push_back(temp);
                    while(i+1<n&&nums[i+1]==nums[i]) i++;
                    i++;
                    while(j-1>=0&&nums[j-1]==nums[j]) j--;
                    j--;
                }
            }
            while(k-1>=0&&nums[k-1]==nums[k]) k--;
        }
        return res;
    }
};

73. Set Matrix Zeroes

73.矩阵置零
之前看过这道题，大概知道不用额外空间思路，但是自己写起来又犯蠢了。。
用来做标志位的首行和首列不能先乱动(不然就全部变成0了)，，
解决方案是用两个bool去存是否要把首行首列变0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public void setZeroes(int[][] matrix) {
        boolean row=false,coloum=false;
        for(int j=0;j<matrix[0].length;j++)
            if(matrix[0][j]==0){
                row=true; break;
            }
        for(int i=0;i<matrix.length;i++)
            if(matrix[i][0]==0){
                coloum=true; break;
            }
        
        for(int i=0;i<matrix.length;i++)
            for(int j=0;j<matrix[0].length;j++)
                if(matrix[i][j]==0){
                    matrix[i][0]=0;
                    matrix[0][j]=0;
                }
        for(int i=1;i<matrix.length;i++)
            for(int j=1;j<matrix[0].length;j++)
                if(matrix[i][0]==0||matrix[0][j]==0)
                    matrix[i][j]=0;
        
        if(row)
            for(int j=0;j<matrix[0].length;j++)
                matrix[0][j]=0;
        if(coloum)
            for(int i=0;i<matrix.length;i++)
                matrix[i][0]=0;
        
    }
}

5. Longest Palindromic Substring

  1. 最长回文子串
    这道题简直是剧毒。。做得我头都大了。昨天晚上做了俩小时，今天下午又看了俩小时 做了三种方法，dp，中心拓展，马拉车算法

解法1： 动态规划
二维动态规划，不看答案根本想不到。bobo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public String longestPalindrome(String s) {
        String res=new String();
        int n=s.length();
        boolean[][] dp=new boolean[n][n];
        for(int i=0;i<n;i++)
            dp[i][i]=true;
        for(int i=0;i<n-1;i++){
            if(s.charAt(i)==s.charAt(i+1))
                dp[i][i+1]=true;
            else dp[i][i+1]=false;
        }
        for(int k=2;k<n;k++){
            for(int i=0;i<n-k;i++){
                if(dp[i+1][k+i-1]==true && s.charAt(i)==s.charAt(k+i))
                    dp[i][k+i]=true;
                else dp[i][k+i]=false;
            }
        }
        int flag=0;
        for(int i=n-1;i>=0;i--){
            for(int j=0;j<n-i;j++)
                if(dp[j][i+j]==true){
                    flag=1;
                    res=s.substring(j,i+j+1);
                    break;
                }
            if(flag==1) break;
        }

        return res;
    }
}

解法2： 中心拓展算法
比较容易理解，但是没想到当时。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public String longestPalindrome(String s) {
    if (s == null || s.length() < 1) return "";
    int start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
        int len1 = expandAroundCenter(s, i, i);
        int len2 = expandAroundCenter(s, i, i + 1);
        int len = Math.max(len1, len2);
        if (len > end - start) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    return s.substring(start, end + 1);
}

private int expandAroundCenter(String s, int left, int right) {
    int L = left, R = right;
    while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
        L--;
        R++;
    }
    return R - L - 1;
}

解法3： 马拉车算法
网上博客都看不太懂，说得都不是人话。。找了篇漫画感觉讲的还挺形象的，附上链接：
点击查看漫画

然后照着源码写了下java版本的，第一次用StringBuffer. sb哈哈哈。
感慨On复杂度确实比On^2快了好多……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
    public String preHandle(String s){
        StringBuffer sb=new StringBuffer();
        sb.append('#');
        for(int i=0;i<s.length();i++){
            sb.append(s.charAt(i));
            sb.append('#');
        }
        return sb.toString();
    }
    public String longestPalindrome(String s) {
        String str=preHandle(s);
        int rightboard=0;
        int rightcenter=0;
        int[] halflen = new int[str.length()];
        int center=0;
        int maxlen=0;
        for(int i=0;i<str.length();i++){
            boolean needSearch=true;
            if(i<rightboard){
                int left=2*rightcenter-i;
                halflen[i]=halflen[left];
                if(i+halflen[i]>rightboard)
                    halflen[i]=rightboard-i;
                if(i+halflen[i]<rightboard)
                    needSearch=false;
            }
            if(needSearch){
                while(i-halflen[i]-1>=0 &&i+halflen[i]+1<str.length()){
                    if(str.charAt(i-halflen[i]-1)==str.charAt(i+halflen[i]+1)){
                        halflen[i]++;
                    }
                    else break;
                }
                rightboard=i+halflen[i];
                rightcenter=i;
                if(halflen[i]>maxlen){
                    center=i;
                    maxlen=halflen[i];
                }
            }

        }
        StringBuffer sb=new StringBuffer();
        for(int i = center - maxlen + 1; i <= center + maxlen; i += 2) {
            sb.append(str.charAt(i));
        }
        return sb.toString();
    }
}

334. Increasing Triplet Subsequence

  1. 递增的三元子序列
    挺有意思的一道题，想清楚就好了，只要记录当前最小值和某个子序列里第二大的数就可以了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean increasingTriplet(int[] nums) {
        if(nums.length<3) return false;
        int low=Integer.MAX_VALUE, mid=Integer.MAX_VALUE;
        int i=0;
        while(i<nums.length){
            if(nums[i]<=low)
                low=nums[i];
            else if(nums[i]<mid)
                mid=nums[i];
            else if(nums[i]>mid) return true;
            i++;
        }
        return false;
    }
}

103. Binary Tree Zigzag Level Order Traversal

  1. 二叉树的锯齿形层次遍历
    层次遍历的变种，没啥难度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res= new ArrayList<>();
        Stack<TreeNode> left=new Stack<>();
        Stack<TreeNode> right=new Stack<>();
        if(root==null) return res;
        right.push(root);
        boolean flag=true;
        while(!left.isEmpty() ||!right.isEmpty()){
            List<Integer> l=new ArrayList<>();
            if(flag){
                while(!right.isEmpty()){
                    TreeNode temp=right.pop();
                    l.add(temp.val);
                    if(temp.left!=null) left.push(temp.left);
                    if(temp.right!=null) left.push(temp.right);
                }
            }
            else
                while(!left.isEmpty()){
                    TreeNode temp=left.pop();
                    l.add(temp.val);
                    if(temp.right!=null) right.push(temp.right);
                    if(temp.left!=null) right.push(temp.left);
                }
            res.add(l);
            flag=!flag;
        }
        return res;
    }
}

230. Kth Smallest Element in a BST

  1. 二叉搜索树中第K小的元素
    中序遍历即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int kthSmallest(TreeNode root, int k) {
        List<Integer> list=new ArrayList<>();
        help(root,list,k);
        return (int)list.get(k-1);
        
    }
    public void help(TreeNode p,List<Integer> list,int k){
        if(p==null||k==0) return;
        help(p.left,list,k);
        k--;
        list.add(p.val);
        help(p.right,list,k);
    }
}

17. Letter Combinations of a Phone Number

  1. 电话号码的字母组合
    发现之前好久没接触过回溯的题目了。。第一个想法就是for循环，但是不知道String的长度
    偷看了评论区答案，用递归去写。。。没有必要记录步长、。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public List<String> letterCombinations(String digits) {
        int n=digits.length();
        String s=new String();
        List<String> res=new ArrayList<>();
        if(n==0) return res;
        help(res,"",digits);
        return res;
    }
    private void help(List<String> list,String s,String digits){
        String[] reps={"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        if(s.length()==digits.length()){
            list.add(s); 
            return;
        }
        int n=s.length();
        String rep=reps[digits.charAt(n)-50];
        for(int i=0;i<rep.length();i++)
        {
            help(list,s+rep.charAt(i),digits);
        }
    }
}

22. Generate Parentheses

22.括号生成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res=new ArrayList<>();
        if(n==0) return res;
        help(res,0,0,n,"");
        return res;
    }
    public void help(List<String> list, int left, int right,int n, String s){
        if(left==right&&left==n) {
            list.add(s);
            return;
        }
        if(left<n) help(list,left+1,right,n,s+'(');
        if(right<left) help(list,left,right+1,n,s+')');
        return;
    }
}

终于贴完了，收工！

4.30LeetCode
leetcode
1 分钟 读完 (大约 137 个字)

4.30LeetCode

五一快乐！！！

今天只做了三道ez，给自己放个假

461. Hamming Distance

  1. 汉明距离
1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int hammingDistance(int x, int y) {
        int z=x^y;
        int res=0;
        while(z!=0){
            res++;
            z=z&(z-1);
        }
        return res;
    }
}

190. Reverse Bits

  1. 颠倒二进制位
1
2
3
4
5
6
7
8
9
10
public class Solution {
    public int reverseBits(int n) {
        int rs = 0;
		for (int i = 0; i < 32; i++) {
			rs <<= 1;
			rs -= n << 31 - i >> 31;
		}
		return rs;
    }
}

268. Missing Number

  1. 缺失数字
1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int missingNumber(int[] nums) {
        int res=0;
        for(int i=0;i<nums.length;i++){
            res^=nums[i];
            res^=i;
        }
        res^=nums.length;
        return res;
    }
}
4.29LeetCode
leetcode
6 分钟 读完 (大约 856 个字)

4.29LeetCode

说一下，今天开始代码尽量准备用java写了，感觉好不习惯。。

198. House Robber

  1. 打家劫舍
    比较简单的动态规划题目。
    dp[i]=max(dp[i-1],dp[i-2]+nums[i])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// dp[i]表示前n户并且抢劫过第n家的max，感觉自己想复杂了。。。也可以通过。
// class Solution {
// public:
//     int rob(vector<int>& nums) {
//         if(nums.empty()) return 0;
//         if(nums.size()==1) return nums[0];
//         if(nums.size()==2) return max(nums[0],nums[1]);
//         vector<int> dp;
//         dp.resize(nums.size());
//         dp[0]=nums[0]; dp[1]=nums[1]; dp[2]=nums[0]+nums[2];
//         for(int i=3;i<nums.size();i++)
//             dp[i]=max(dp[i-2]+nums[i],dp[i-3]+nums[i]);
//         return max(dp[nums.size()-1],dp[nums.size()-2]);
//     }
// };


class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.empty()) return 0;
        if(nums.size()==1) return nums[0];
        vector<int> dp;
        dp.resize(nums.size());
        dp[0]=nums[0]; dp[1]=max(nums[0],nums[1]);
        for(int i=2;i<nums.size();i++)
            dp[i]=max(dp[i-1],dp[i-2]+nums[i]);
        return dp[nums.size()-1];
    }
};

384. Shuffle an Array

  1. 打乱数组
    第一次写java，感觉好难啊。。踩了好多坑，数组的深浅拷贝和伪随机函数等等.. 慢慢学吧 注释的是评论区大佬的答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution {
    int[] Arr;
    int[] Nature;
    public Solution(int[] nums) {
        Arr=nums;
        Nature= Arrays.copyOf(Arr, Arr.length);
    }
    
    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        for(int i=0;i<Arr.length;i++)
            Arr[i]=Nature[i];
        return Arrays.copyOf(Arr, Arr.length);
    }
    
    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
        for(int i=Arr.length-1;i>0;i--){
            Random rand=new Random();
            int t=rand.nextInt(i+1); //随机数生成范围要注意
            int temp=Arr[t];
            Arr[t]=Arr[i];
            Arr[i]=temp;
        }
        return Arr;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int[] param_1 = obj.reset();
 * int[] param_2 = obj.shuffle();
 */


// class Solution {
//     int[] nums;

//     public Solution(int[] nums) {
//         this.nums = nums;
//     }
    
//     /** Resets the array to its original configuration and return it. */
//     public int[] reset() {
//         return nums;
//     }
    
//     /** Returns a random shuffling of the array. */
//     public int[] shuffle() {
//         int[] result = Arrays.copyOf(nums, nums.length);
//         Random rand=new Random();
//         for(int i = nums.length - 1; i > 0; i--) {
//             int n = rand.nextInt(i + 1);
//             // swap n and i 
//             int tmp = result[n];
//             result[n] = result[i];
//             result[i] = tmp;
//         }
//         return result;
//     }
// }

412. Fizz Buzz

java:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public List<String> fizzBuzz(int n) {
        List<String> res=new ArrayList<String>();
        for(int i=1;i<=n;i++){
            if(i%3==0&&i%5==0)
                res.add("FizzBuzz");
            else if(i%3==0&&i%5!=0) res.add("Fizz");
            else if(i%5==0&&i%3!=0) res.add("Buzz");
            else res.add(Integer.toString(i));
        }
        return res;
    }
}

204. Count Primes

计数质数
一开始的想法就是判断从1-n的每个数是否为质数，时间复杂度O(n^2)
最简单的方法当然通过不了，参考了某大佬的一篇博客进行剪枝
附连接：判断一个数是不是质数(素数)，3种方式介绍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int countPrimes(int n) {
        int res=0;
        for(int i=1;i<n;i++)
            if(isPrime(i)) res++;
        return res;
        
    }
    public static boolean isPrime(int num) {
        if (num <= 3) {
            return num > 1;
        }
        // 不在6的倍数两侧的一定不是质数
        if (num % 6 != 1 && num % 6 != 5) {
            return false;
        }
        int sqrt = (int) Math.sqrt(num);
        for (int i = 5; i <= sqrt; i += 6) {
            if (num % i == 0 || num % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }

}

然后根据题目下面的提示，了解了埃拉托色尼筛选法（质数问题）。唯一疑惑就是明明应该可以从i*i开始覆盖，不知道为什么总会报错说数组越界。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int countPrimes(int n) {
        if(n<3) return 0; 
        int res=0;
        int[] temp=new int[n];
        for(int i=0;i<n;i++)
            temp[i]=i;
        for(int i=2;i<n;i++){
            if(temp[i]==i){
                res++;
                for(int j=2;j*i<n;j++)
                    temp[j*i]=i;
            }
        }
        return res;
        
    }
}

326. Power of Three

递归解法很常规

1
2
3
4
5
6
7
class Solution {
    public boolean isPowerOfThree(int n) {
        if(n==1) return true;
        else if(n%3!=0||n==0) return false;
        else return isPowerOfThree(n/3);
    }
}

评论区大佬的两种解法：

1
2
3
4
5
6
7
class Solution {
    public boolean isPowerOfThree(int n) {
        String str=Integer.toString(n,3); //将n由十进制转化为3进制(java进制转换的写法，学到了)
        boolean result = str.matches("^10*$");//^表示正则开始，$表示正则结束,意思为匹配1开头中间可以无数个0的字符
        return result;
    }
}
1
2
3
4
5
class Solution {
    public boolean isPowerOfThree(int n) {
        return n > 0 && 1162261467%n == 0;
    }
}

13. Roman to Integer

写得太丑陋了。。不忍直视。。。有空一定重新用switch写下。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
class Solution {
    public int romanToInt(String s) {
        int res=0;
        int i=0;
        while(i<s.length()){
            if(s.charAt(i)=='M') {
                res+=1000;
                i++;
                continue;
            }
            if(s.charAt(i)=='D'){
                res+=500;
                i++;
                continue;
            }
            if(s.charAt(i)=='C'){
                if(i+1<s.length()&&s.charAt(i+1)=='D'){
                    res+=400;
                    i+=2;
                }
                else if(i+1<s.length()&&s.charAt(i+1)=='M'){
                    res+=900;
                    i+=2;
                }
                else {
                    res+=100;
                    i++;
                }
                continue;
            }
            if(s.charAt(i)=='L'){
                res+=50;
                i++;
                continue;
            }
            if(s.charAt(i)=='X'){
                if(i+1<s.length()&&s.charAt(i+1)=='L'){
                    res+=40;
                    i+=2;
                }
                else if(i+1<s.length()&&s.charAt(i+1)=='C'){
                    res+=90;
                    i+=2;
                }
                else {
                    res+=10;
                    i++;
                }   
                continue;
            }
            if(s.charAt(i)=='V'){
                res+=5;
                i++;
                continue;
            }
            if(s.charAt(i)=='I'){
                if(i+1<s.length()&&s.charAt(i+1)=='V'){
                    res+=4;
                    i+=2;
                }
                else if(i+1<s.length()&&s.charAt(i+1)=='X'){
                    res+=9;
                    i+=2;
                }
                else {
                    res+=1;
                    i++;
                }       
                continue;
            }
        }
        return res;
    }
}

191. Number of 1 Bits

为什么java里面没有unsignedint啊？？？？？？
学了了评论区大佬的解法，体会了下n=n&(n-1)的妙用(每次可以消掉一个1).

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
         int count = 0;
        while (n != 0) {
            count++;
            n = n & (n - 1);
        }
        return count;
    }
}
4.28LeetCode
leetcode
4 分钟 读完 (大约 544 个字)

4.28LeetCode

38. Count and Say

  1. 报数
    emmmmm.题目比较难读懂，读懂很简单啦。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    string countAndSay(int n) {
        string res="1";
        for(int i=1;i<n;i++)
            res=next(res);
        return res;
    }
    string next(string n) {
        int i=0;
        string res;
        while(i<n.length()){
            char temp=n[i];
            int num=1;
            while(1){
                if(i+1!=n.length()&&n[i+1]==n[i])
                {
                    num++; 
                    i++;
                }
                else break;
            }
            res+=to_string(num);
            res+=temp;
            i++;
        }
        return res;
    }
};

237. Delete Node in a Linked List

  1. 删除链表中的节点
    感觉还是思路被桎梏了哈哈，说到删除节点第一时间想的永远是让被删除的前一个结点next指向被删除的next，为什么不换个思路去重新生成从被删除开始之后的整个链表呢
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    void deleteNode(ListNode* node) {
        ListNode* p=node;
        while(p->next){
            p->val=p->next->val;
            p=p->next;
        } 
        while(node->next!=p)
            node=node->next;
        node->next=nullptr;
        return;
    }
};

88. Merge Sorted Array

  1. 合并两个有序数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i=0,j=0;
        vector<int> temp;
        while(i<m&&j<n){
            if(nums1[i]<=nums2[j])
            {
                temp.push_back(nums1[i]);
                i++;
            }else{
                temp.push_back(nums2[j]);
                j++;
            }
        }
        if(i!=m){
            while(i!=m){
                temp.push_back(nums1[i]);
                i++;               
            }
        }
        if(j!=n){
            while(j!=n){
                temp.push_back(nums2[j]);
                j++;                
            }
        }
        i=0;
        for(int it:temp){
            nums1[i]=it;
            i++;
        }
        return;
    }
};

70. Climbing Stairs

爬楼梯
斐波那契数列。。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int climbStairs(int n) {
        if(n==1) return 1;
        vector<int> dp;
        dp.resize(n);
        dp[0]=1;dp[1]=2;
        for(int i=2;i<n;i++)
            dp[i]=dp[i-1]+dp[i-2];
        return dp[n-1];
    }
};

53. Maximum Subarray

  1. 最大子序和
    这题实在是太难了。。。想了一上午都没想明白，说到底还是自己太菜了。。。到现在也只是勉强能理解标准答案。
    评论区大佬解答：这道题难度不该是easy 这道题的一开始我想到的是暴力的滑窗去做，复杂度O(n^2)，显然达不到题目中要求的复杂度 这道题根据题目关键词，“最大”“连续”，可以判断是一道动态规划，附上这道题目的wiki链接https://zh.wikipedia.org/wiki/%E6%9C%80%E5%A4%A7%E5%AD%90%E6%95%B0%E5%88%97%E9%97%AE%E9%A2%98 方法如下：
    1.定义一个函数f(n)，以第n个数为结束点的子数列的最大和，存在一个递推关系f(n) = max(f(n-1) + A[n], A[n]);
    2.将这些最大和保存下来后，取最大的那个就是，最大子数组和。因为最大连续子数组 等价于 最大的以n个数为结束点的子数列和 
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int tempmax,res;
        res=nums[0];
        tempmax=0;
        for(int i=0;i<nums.size();i++){
            tempmax=max(tempmax+nums[i],nums[i]);
            res=max(res,tempmax);
        }
        return res;
    }
};
4.27LeetCode
leetcode
6 分钟 读完 (大约 835 个字)

4.27LeetCode

26. Remove Duplicates from Sorted Array

从排序数组中删除重复项
双指针法解决。当数值不同且不指向同一个时替换。写的有点丑陋，可以利用nums[i]的值去替代temp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.empty()) return 0; 
        int i=j=0;
        int temp=nums[i];
        int res=1;
        while(j<nums.size()){
            if(temp<nums[j]){
                res++;                
                if(i!=j)
                {
                    i++;
                    nums[i]=nums[j];
                }  
                temp=nums[j];
            }
            j++;
        }
        return res;
    }
};

121. Best Time to Buy and Sell Stock

买卖股票的最佳时机
动态规划 前i天的最大收益 = max{前i-1天的最大收益，第i天的价格-前i-1天中的最小价格}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.empty()) return 0;
        vector<int> dp;
        dp.resize(prices.size());
        dp[0]=0;
        int minp=prices[0];
        for(int i=1;i<prices.size();i++){
            if(prices[i]<=prices[i-1])
                dp[i]=dp[i-1];
            else if(prices[i]-minp>dp[i-1])
                dp[i]=prices[i]-minp;
            else dp[i]=dp[i-1];
            minp=min(minp,prices[i]);
        }
        return dp[prices.size()-1];
    }
};

122. Best Time to Buy and Sell Stock II

  1. 买卖股票的最佳时机 II
    贪心没啥思路，偷看了评论区的答案：[7, 1, 5, 6] 第二天买入，第四天卖出，收益最大（6-1），所以一般人可能会想，怎么判断不是第三天就卖出了呢? 这里就把问题复杂化了，根据题目的意思，当天卖出以后，当天还可以买入，所以其实可以第三天卖出，第三天买入，第四天又卖出（（5-1）+ （6-5） === 6 - 1）。所以算法可以直接简化为只要今天比昨天大，就卖出。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.empty()) return 0;
        int res=0;
        int pricenow=prices[0];  //默认持有价格
        for(int i=1;i<prices.size();i++){   
            if(prices[i]<=pricenow)    //当天价格比你持有的低,直接放弃之前的
                pricenow=prices[i];
            else{
                res+=prices[i]-pricenow;
                pricenow=prices[i];
            }
        }
        return res;
    }
};

48. Rotate Image

旋转图像
虽然是道medium题，但是感觉其实也没很难。。想了很久才明白旋转规则。（四个结点旋转）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        if(matrix.empty()) return;
        int n=matrix.size();
        for(int i=0;i<n/2;i++){
            for(int j=i;j<n-i-1;j++){
                int temp=matrix[i][j];
                matrix[i][j]=matrix[n-1-j][i];
                matrix[n-1-j][i]=matrix[n-1-i][n-1-j];
                matrix[n-1-i][n-1-j]=matrix[j][n-1-i];
                matrix[j][n-1-i]=temp;
            }
        }
        return;
    }
};

242. Valid Anagram

  1. 有效的字母异位词
    建立字母表 再比较。 也可以用map去做。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool isAnagram(string s, string t) {
        int a[26]={0};
        int b[26]={0};
        for(int i=0;i<s.length();i++)
            a[s[i]-'a']++;
        for(int i=0;i<t.length();i++)
            b[t[i]-'a']++;
        for(int i=0;i<26;i++)
            if(a[i]!=b[i]) return false;
        return true;
    }
};

125. Valid Palindrome

  1. 验证回文串
    双指针法，感觉贴题目好有成就感。。题目不难，比较繁琐的是大小写的转换以及干扰字符去除的写法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    bool isPalindrome(string s) {
        if(s.empty()) return true;
        int i=0,j=s.length()-1;
        while(i<j){
            while(1){
                if((s[i]>='0'&&s[i]<='9')||(s[i]>='a'&&s[i]<='z')||(s[i]>='A'&&s[i]<='Z')||i==j) break;
                i++;
            }
            while(1){
                if((s[j]>='0'&&s[j]<='9')||(s[j]>='a'&&s[j]<='z')||(s[j]>='A'&&s[j]<='Z')||i==j) break;
                j--;
            } 
            if(i==j) break;
            char p=s[i],q=s[j];
            if(p>='A'&&p<='Z') p+=32;
            if(q>='A'&&q<='Z') q+=32;
            if(p!=q) return false;
            i++;
            j--;
        }
        return true;
        
    }
};

8. String to Integer (atoi)

  1. 字符串转换整数 (atoi)
    还是属于比较简单的medium主要考察一个细心把。。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int myAtoi(string str) {
        long long res=0;
        if(str.empty()) return 0;
        int i;
        for(i=0;i<str.length();i++)
            if(str[i]!=' ') break;
        if(i==str.length()||(str[i]<'0'&&str[i]!='-'&&str[i]!='+')||str[i]>'9') return 0;
        char temp=str[i];
        if(str[i]=='-'||str[i]=='+') i++;
        while(i<str.length()){
            if(str[i]>='0'&&str[i]<='9')
            {
                if(res>pow(2,31)-1) return temp=='-'?INT_MIN:INT_MAX;
                res=res*10+(int)(str[i]-'0');
                i++;
            }
            else break;
        }
        if(temp=='-') res=res*(-1);
        if(res>pow(2,31)-1) return INT_MAX;
        if(res<pow(2,31)*(-1)) return INT_MIN;
        return res;
    }
};

28. Implement strStr()

实现strStr()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 我枯了，明明是道ez题，居然随便写写过不了。。。还要剪枝。。

class Solution {
public:
    int strStr(string haystack, string needle) {
        if(needle.empty()) return 0;
        int n1=haystack.length(),n2=needle.length();
        if(n2>n1) return -1;
        int i=0;
        while(i+n2<=haystack.length()){
            int t=i;
            int j=0;
            for( j=0;j<needle.length();j++)
            {
                if(haystack[t]!=needle[j]) break;
                t++;
            }
            if(j==needle.length()) return i;
            i++;
        }
        return -1;
    }
};
关注我

链接

分类

标签云

ASR C++ DFS Java N叉树 SR/LID java n叉树 二叉搜索树 位运算 前缀树 动态规划 双指针 合并排序 回溯 字符串 排序搜索 数组 算法 贪心算法 递归迭代 链表 随便写写

最新文章

归档

标签

ASR 1
C++ 3
DFS 1
Java 1
N叉树 1
SR/LID 1
java 1
n叉树 1
二叉搜索树 1
位运算 1
前缀树 1
动态规划 5
双指针 2
合并排序 1
回溯 1
字符串 1
排序搜索 1
数组 3
算法 1
贪心算法 1
递归迭代 1
链表 1
随便写写 2

最新文章

归档

标签

ASR 1
C++ 3
DFS 1
Java 1
N叉树 1
SR/LID 1
java 1
n叉树 1
二叉搜索树 1
位运算 1
前缀树 1
动态规划 5
双指针 2
合并排序 1
回溯 1
字符串 1
排序搜索 1
数组 3
算法 1
贪心算法 1
递归迭代 1
链表 1
随便写写 2
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×