刷题总结

1,count数组

#include <iostream>
#include <unordered_map>
using namespace std;
// 输入: 11223344455
// 输出:{1:2, 2: 2, 3: 2, 4: 3, 5: 1}
void printNums(vector<int> nums) {
    for(int i = 0; i < nums.size(); i++) {
        cout << nums[i] << '\t';
    }
}

vector<pair<int,int>> analysis(vector<int> nums) {
    unordered_map<int, int> mp;
    for(int i = 0; i < nums.size(); i++) {
        if(mp.find(nums[i]) == mp.end()) {
            mp.insert(pair(nums[i], 1));
        } else {
            mp[nums[i]] = mp.find(nums[i])->second + 1;
        }
    }
    vector<pair<int, int>> result(mp.begin(), mp.end());
    sort(result.begin(), result.end(), [](pair<int,int>&a, pair<int, int>&b) {
        return a.second < b.second;
    });
    return result;
}

void printPair(vector<pair<int, int>> &nums) {
    for(int i = 0; i < nums.size(); i++) {
        cout << nums[i].first << ": " << nums[i].second << "\t";
    }
}
int main() {
    vector<int> nums = {7, 7, 2, 2, 3, 3, 4, 4 , 4, 5, 5};
    // printNums(nums);
    vector<pair<int, int>> result = analysis(nums);
    printPair(result);

}

2, leetcode 1. 两数之和

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> mp = new HashMap<>();
        for(int i = 0; i < nums.length; i++) {
            if(mp.containsKey(target - nums[i])) {
                return new int[] {i, mp.get(target-nums[i])};
            }
            mp.put(nums[i], i);
        }
        return new int[2];
    }
}

3,leetcode 4.寻找两个有序数组的中位数

解法一:

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 合并两个数组
        ArrayList<Integer> array = new ArrayList<>();
        int i = 0, j = 0;
        while(i < nums1.length || j < nums2.length) {
            if(i < nums1.length && j < nums2.length && nums1[i] < nums2[j]) {
                array.add(nums1[i++]);
            } else if(j < nums2.length && i < nums1.length && nums1[i] >= nums2[j]) {
                array.add(nums2[j++]);
            }else if (j < nums2.length) {
                array.add(nums2[j++]);
            } else if (i < nums1.length) {
                array.add(nums1[i++]);
            }
        }
        int totalLength = nums1.length + nums2.length;
        int middle = (totalLength - 1) / 2;
        if(totalLength % 2 == 0) {
            return (array.get(middle) + array.get(middle+1) )/ 2.0;
        } else {
            return array.get(middle);
        }
    }
}

解法二:

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        if(m > n) {
            return findMedianSortedArrays(nums2, nums1);
        }

        int c1 = 0, c2 = 0, lo = 0, hi = 2*m, LMAX1 = 0, LMAX2 = 0, RMIN1 = 0, RMIN2 = 0;
        while(lo <= hi) {
            c1 = (lo + hi) / 2;
            c2 = m + n - c1;

            LMAX1 = (c1 == 0) ? Integer.MIN_VALUE : nums1[(c1-1)/2];
            LMAX2 = (c2 == 0) ? Integer.MIN_VALUE : nums2[(c2-1)/2];
            RMIN1 = (c1 == 2*m) ? Integer.MAX_VALUE : nums1[c1/2];
            RMIN2 = (c2 == 2*n) ? Integer.MAX_VALUE : nums2[c2/2];

            if(LMAX1 > RMIN2) {
                hi = c1 - 1;
            } else if(LMAX2 > RMIN1) {
                lo = c1 + 1;
            } else {
                break;
            }
        }
        return (Math.max(LMAX1, LMAX2) + Math.min(RMIN1, RMIN2)) / 2.0;
    }
}

4,leetcode 11.盛水最多的容器

解法一(暴力)

class Solution {
    public int maxArea(int[] height) {
        int max = Integer.MIN_VALUE;
        int len = height.length;
        int tmp = 0;
        for(int i = 0; i < len - 1; i++) {
            for (int j = i + 1; j < len; j++) {
                tmp = (j - i)*(Math.min(height[i], height[j]));
                if(tmp > max) {
                    max = tmp;
                }
            }
        }
        return max;
    }
}

解法二(双指针)

class Solution {
    public int maxArea(int[] height) {
        int res = Integer.MIN_VALUE;
        int i = 0, j = height.length - 1;
        while(i < j) {
            if(height[i] < height[j]){
                res = Math.max(res, height[i]*(j - i));
                i++;
            } else {
                res = Math.max(res, height[j]*(j - i));
                j--;
            }
        }
        return res;
    }
}

5, leetcode 15. 三数之和

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList();
        int len = nums.length;
        if(len < 3) return result;
        Arrays.sort(nums);
        for(int i = 0; i < len; i++) {
            if(nums[i] > 0) break;
            if(i > 0 && nums[i] == nums[i-1]) continue;
            int L = i+1, R = len - 1;
            while(L < R) {
                int sum = nums[i] + nums[L] + nums[R];
                if(sum == 0) {
                    result.add(Arrays.asList(nums[i], nums[L], nums[R]));
                    while(L < R && nums[L] == nums[L+1]) L++;
                    while(L < R && nums[R] == nums[R-1]) R--;
                    L++;
                    R--;
                }

                if(sum > 0) R--;
                if(sum < 0) L++;
            }
        }
        return result;
    }
}

6, leetcode 16. 最接近三数之和

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int len = nums.length;
        if(len < 3) return 0;
        int result = nums[0] + nums[1] + nums[2];
        Arrays.sort(nums);
        for(int i = 0; i < len; i++) {
            int L = i + 1;
            int R = len - 1;
            while(L < R) {
                int sum = nums[i] + nums[L] + nums[R];
                result = Math.abs(result - target) > Math.abs(sum - target) ? sum : result;
                if(sum > target) {
                    R--;
                }else if(sum < target) {
                    L++;
                }else {
                    return target;
                }

            }
        }
        return result;
    }
}

7, leetcode 18. 四数之和

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList();
        int len = nums.length;
        if(len < 4) return result;
        Arrays.sort(nums);
        for(int i = 0; i <= len - 4; i++) {
            if(i > 0 && nums[i] == nums[i-1]) continue;
            for(int j = i+1; j <= len - 3; j++) {
                if(j > i+1 && nums[j] == nums[j-1]) continue;
                int l = j+1, r = len - 1;
                while(l < r) {
                    int sum = nums[i] + nums[j] + nums[l] + nums[r];
                    if(sum > target) {
                        r--;
                    }else if(sum < target) {
                        l++;
                    }else {
                        result.add(Arrays.asList(nums[i], nums[j], nums[l], nums[r]));
                        while(nums[l]==nums[l+1]) l++;
                        while(nums[r] == nums[r-1]) r--;
                        l++;
                        r--;
                    }
                }
            }
        }
        return result;
    }
}

8. leetcode 26. 删除排序数组中的重复项

解法一:(暴力移动法)

class Solution {
    public int removeDuplicates(int[] nums) {
        //判断重复 记录位置 删除
        int end = nums.length, i = 0;
        while(i < end) {
            if(i > 0 && nums[i] == nums[i-1]) {
                //移动
                for(int j = i+1; j < end; j++) {
                    nums[j-1] = nums[j];
                }
                end--;
            }else {
                i++;
            }
        }
        return end;
    }
}

解法二:(双指针法)

class Solution {
    public int removeDuplicates(int[] nums) {
        int len = nums.length;
        if(len == 0) return 0;
        else if(len == 1) return 1;
        else {
            int i = 0;
            for(int j = 1; j < len; j++) {
                if(nums[i] != nums[j]) {
                    i++;
                    nums[i] = nums[j];
                }
            }
            return i+1;
        }
    }
}

9. leetcode 3. 无重复字符的最长字串

解法一:

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        int i = 0;
        int result = 0;
        while(i < len) {
            Set<String> set= new HashSet();
            int j = 0;
            for(j = i; j < len; j++) {
                if(!set.contains(s.charAt(j)+"")) {
                    result = Math.max(result, j-i+1);
                }else {
                    break;
                }
                set.add(s.charAt(j)+"");
            }
            i++;
        }
        return result;
    }
}

解法二:(滑动窗口)

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int LeftIndex = 0;
        int result = 0;
        for(int j = 0; j < s.length(); j++) {
            for(int CurIndex = LeftIndex; CurIndex < j; CurIndex++) {
                if(s.charAt(CurIndex) == s.charAt(j)) {
                    result = Math.max(result, j - LeftIndex);
                    LeftIndex = CurIndex + 1;
                    break;
                }
            }
        }
        return Math.max(s.length()-LeftIndex, result);
    }
}

10. leetcode 27. 移除元素

解法一:

class Solution {
    public int removeElement(int[] nums, int val) {
        int i = 0;
        for(int j = 0; j < nums.length; j++) {
            if(nums[j] != val) {
                nums[i] = nums[j];
                i++;
            }
        }
        return i;
    }
}

解法二:

class Solution {
    public int removeElement(int[] nums, int val) {
        int len = nums.length;
        int i = 0;
        while(i < len) {
            if(nums[i] == val) {
                nums[i] = nums[len-1];
                len--;
            }else {
                i++;
            }
        }
        return len;
    }
}

11. leetcode 6. Z字形变换

解法一:

class Solution {
    public String convert(String s, int numRows) {
        int len = s.length();
        //根据s的长度 和numRows来分配初始数组的大小
        StringBuilder sb = new StringBuilder();
        if(len == 0) return sb.toString();
        if(numRows == 1) return s;

        int numCols = (len / (2*numRows - 2) + 1) * (numRows-1);
        char[][] result = new char[numRows][numCols];
        int i = 0, row = 0, col = 0;
        while(i < len) {
            for(int j = 0; j < numRows && i < len; j++) {
                result[j][col] = s.charAt(i++);
            }
            col++;
            for(int j = numRows-2; j >= 1 && i < len; j--) {
                result[j][col++] = s.charAt(i++);
            }
        }
        for(i = 0; i < result.length; i++) {
            for(int j = 0; j < result[0].length; j++) {
                if(result[i][j] != '\0') {
                    sb.append(result[i][j]);
                }
            }
        }
        return sb.toString();

    }
}

解法二:

class Solution {
    public String convert(String s, int numRows) {
        int len = s.length();
        numRows = Math.min(numRows, len);
        if(numRows == 1) return s;
        //构造stringbuilder
        List<StringBuilder> sb = new ArrayList<>();
        for(int i = 0; i < numRows; i++) {
            sb.add(new StringBuilder());
        }
        boolean goDown = false;
        int row = 0;
        for(int i = 0; i < len; i++) {
            sb.get(row).append(s.charAt(i));
            if(row == 0 || row == numRows - 1) goDown = !goDown;
            row += goDown ? 1 : -1;
        }

        StringBuilder res = new StringBuilder();
        for(int i = 0; i < sb.size(); i++) {
            res.append(sb.get(i));
        }
        return res.toString();
    }
}

12. leetcode 5. 最长回文子串

解法一:(暴力)

class Solution {
    public String longestPalindrome(String s) {
        if(s.length() < 2) return s;
        String res = s.substring(0, 1);
        int maxLen = 1;
        for(int i = 0; i < s.length() - 1; i++) {
            for(int j = i + 1; j < s.length(); j++) {
                if(j-i+1 > maxLen && valid(i, j, s)) {
                    maxLen = j - i + 1;
                    res = s.substring(i, j+1);
                }
            }
        }
        return res;
    }

    public boolean valid(int i, int j, String s) {
        char[] ss = s.toCharArray();
        while(i <= j) {
            if(ss[i++] != ss[j--]) {
                return false;
            }
        }
        return true;
    }
}

解法二:(中心扩散法)

class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        if(len < 2) return s;
        String res = s.substring(0, 1);
        int maxLen = 1;
        for(int i = 0; i < len-1; i++) {
            String s1 = centerS(s, i, i);
            String s2 = centerS(s, i, i+1);
            String maxS = s1.length() > s2.length() ? s1 : s2;
            if(maxS.length() > maxLen) {
                maxLen = maxS.length();
                res = maxS;
            }
        }
        return res;
    }

    public String centerS(String s, int l, int r) {
        int len = s.length();
        while(l >= 0 && r < len) {
            if(s.charAt(l) == s.charAt(r)) {
                l--;
                r++;
            } else {
                break;
            }
        }
        return s.substring(l+1, r);
    }
}

解法三:(动态规划)

class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        if(len < 2) return s;
        boolean[][] dp = new boolean[len][len];
        String res = s.substring(0, 1);
        int maxLen = 1;
        for(int r = 1; r < len; r++) {
            for(int l = 0; l < r ; l++) {
                if(s.charAt(l) == s.charAt(r) && (r - l <= 2 || dp[l+1][r-1])) {
                    dp[l][r] = true;
                    if(r - l + 1 > maxLen) {
                        maxLen = r - l + 1;
                        res = s.substring(l, r+1);
                    }
                }
            }
        }
        return res;
    }
}

13. leetcode 102. 二叉树的层次遍历

解法一:(递归)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public static  List<List<Integer>> res;
    public List<List<Integer>> levelOrder(TreeNode root) {
        res = new ArrayList<>();
        if(root == null) return res;
        helper(root, 0);
        return res;
    }

    public void helper(TreeNode root, int level) {
        if(res.size() == level) {
            res.add(new ArrayList());
        }
        res.get(level).add(root.val);
        if(root.left != null) {
            helper(root.left, level+1);
        }
        if(root.right != null) {
            helper(root.right, level+1);
        }
    }
}

解法二:(迭代)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int _size = queue.size();
            List<Integer> tmp = new ArrayList<>();
            for(int i = 0; i < _size; i++) {
                TreeNode node = queue.remove();
                tmp.add(node.val);
                if(node.left != null) {
                    queue.offer(node.left);
                }
                if(node.right != null) {
                    queue.offer(node.right);
                }
            }
            res.add(tmp);
        }
        return res;
    }
}

14. leetcode 103. 二叉树的锯齿形层次遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null) return  res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int _size = queue.size();
            List<Integer> tmp = new ArrayList<>();
            for(int i = 0; i < _size; i++) {
                TreeNode node = queue.remove();
                tmp.add(node.val);
                if(node.left != null){
                    queue.offer(node.left);
                }
                if(node.right != null) {
                    queue.offer(node.right);
                }
            }
            if(res.size()%2 == 0) {
                res.add(tmp);
            } else {
                Collections.reverse(tmp);
                res.add(tmp);
            }
        }
        return res;
    }
}

15, leetcode 100.相同的树

解法一:(递归)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null) return true;
        else if(p == null || q == null) return false;
        else {
            if(p.val != q.val) return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

树的框架套路

nextT hexo主题

01-06 20:54