leetcode记录

记录leetcode做题时的想法、思路和解答(可能是官方),总结一些做题经验。

7.整数反转

看到这题第一反应是转换成字符串再转回整数没救了,代码写得臭长

class Solution {
    public int reverse(int x) {
        if(x <= Integer.MIN_VALUE || x >= Integer.MAX_VALUE){
            return 0;
        }
        int abs = Math.abs(x);
        String result = "";
        String num = String.valueOf(abs);
        int [] a = new int[num.length()];
        for(int i=0; i<num.length(); i++){
            a[i] = Integer.parseInt(String.valueOf(num.charAt(i)));
        }
        for(int i=num.length()-1; i>=0; i--){
            result = result + a[i];
        }
        if(x < 0){
            result = "-" + result;
        }
        try{
            return Integer.parseInt(result);    
        }catch(Exception e){
            return 0;
        }
    }
}

后面看了官方答案,精简!

class Solution {
    public int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            int pop = x % 10;
            x /= 10;
            if (rev > Integer.MAX_VALUE/10 || (rev == Integer.MAX_VALUE / 10 && pop > 7)) return 0;
            if (rev < Integer.MIN_VALUE/10 || (rev == Integer.MIN_VALUE / 10 && pop < -8)) return 0;
            rev = rev * 10 + pop;
        }
        return rev;
    }
}

官方解答

9.回文数

和整数反转差不多,稍微修改下即可

class Solution {
    public boolean isPalindrome(int x) {
        if(x < 0){
            return false;
        }
        Integer pal = 0;
        Integer a = x;
        while(x != 0){
            int pop = x % 10;
            x /= 10;
            pal = pal * 10 + pop;
        }
        if(pal.equals(a)){
            return true;
        }else{
            return false;
        }
    }
}

13.罗马数字转整数

这题想了蛮久的,没什么思路。看了下评论区的提示:遍历字符串,如果当前字符代表的值不小于其右边,就加上该值;否则就减去该值。以此类推到最左边的数,最终得到的结果即是答案

class Solution {
    public int romanToInt(String s) {
        String[] roman = s.split("");
        int result = 0;
        Map<String, Integer> map = new HashMap<>();
        map.put("I", 1);
        map.put("V", 5);
        map.put("X", 10);
        map.put("L", 50);
        map.put("C", 100);
        map.put("D", 500);
        map.put("M", 1000);
        for(int i=0; i<roman.length; i++){
            if (i<roman.length-1 && map.get(roman[i])<map.get(roman[i+1])){
                result -= map.get(roman[i]);
            }else{
                result += map.get(roman[i]);
            }
        }
        return result;
    }
}

21.合并两个有序链表

最开始是想在原链表上完成合并,但难度较大,于是新建一个链表完成合并。

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode ln = head;
        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                ln.next = l1;
                ln = ln.next;
                l1 = l1.next;
            }else{
                ln.next = l2;
                ln = ln.next;
                l2 = l2.next;
            }
        }
        if(l1 == null){
            ln.next = l2;
        }
        if(l2 == null){
            ln.next = l1;
        }
        return head.next;
    }
}

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

看了解析,使用双指针法,设i为慢指针,j为快指针。
nums[i]=nums[j] 时,增加j跳过重复项
nums[j]​!=nums[i] 时,跳过重复项的运行已经结束,因此我们必须把 nums[j] 的值复制到 nums[i+1]

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

58.最后一个单词的长度

使用 trim() 方法清除字符串两端空格,逆序遍历字符串,遇到第一个空格退出

class Solution {
    public int lengthOfLastWord(String s) {
        s = s.trim();
        int i = s.length()-1;
        for(; i >= 0; i--){
            if(s.charAt(i) == ' '){
                break;
            }
        }
        return s.length()-1-i;
    }
}

66.加一

最后一个元素加一,不等于 10 加一返回,否则逆序遍历、加一、判断。第一个元素为 10 时扩充数组。

class Solution {
    public int[] plusOne(int[] digits) {
        if(digits[digits.length-1]+1 == 10){
            for(int i = digits.length-1; i >= 0; i--){
                digits[i]++;
                if(digits[i] == 10){
                    digits[i] = 0;
                    if(i == 0){
                        digits = new int[digits.length+1];
                        digits[0] = 1;
                    }
                }else{
                    break;
                }
            }
        }else{
            digits[digits.length-1]++;
        }
        return digits;
    }
}

69.x的平方根

实现开方运算,可以用二分查找,int类型要注意溢出,判断条件 x/m >= m 代替 m*m <= x 防止溢出

class Solution {
    public int mySqrt(int x) {
        if(x <= 1){
            return x;
        }
        int l = 0;
        int r = x;
        int m = 0;
        while(l <= r){
            m = (l + r) / 2;
            if(x/m >= m && x/(m+1) < (m+1)){
                break;
            }
            if(x/m < m){
                r = m;
            }else{
                l = m;
            }
        }
        return m;
    }
}

还有一种数学方法,牛顿迭代法
牛顿法解 f(x)=0 的迭代公式是 next=cur-f(x)/f'(x)
实在不理解原理也没关系,只要知道,不断迭代 res = (res + x/res) / 2 就会趋于结果。

class Solution {
    public int mySqrt(int x) {
        if(x <= 1){
            return x;
        }
        long res = x;
        while(res > (x/res)){
            res = (res + x/res) / 2;
        }
        return (int)res; 
    }
}

70.爬楼梯

因为每次可以爬 12 级台阶,所以到达i阶的方法有:

  1. i-1 阶时,爬 1 级台阶
  2. i-2 阶时,爬 2 级台阶

到达 i 阶的方法总数可有 (i-1) + (i-2) 得出

动态规划:

class Solution {
    public int climbStairs(int n) {
        if(n == 1){
            return 1;
        }
        int[] dp = new int[n+1];
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i <= n; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
}

根据上述分析,可以得出 dp[] 其实是一个斐波那契数列

斐波那契数:

public class Solution {
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        int first = 1;
        int second = 2;
        for (int i = 3; i <= n; i++) {
            int third = first + second;
            first = second;
            second = third;
        }
        return second;
    }
}

官方解答

83.删除排序链表中的重复元素

将首次出现的元素存入HashMap,如果已存在,则跳过该元素。该方法效率比较低。

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        Map<Integer, Integer> map = new HashMap<>();
        ListNode myhead = new ListNode(0);
        ListNode ln = myhead;
        while(head != null){
            if(!map.containsKey(head.val)){
                map.put(head.val, 1);
                ln.next = head;
                ln = ln.next;
            }
            head = head.next;
        }
        ln.next = null;
        return myhead.next;
    }
}

直接法:

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode current = head;
        while(current != null && current.next != null){
            if(current.next.val == current.val){
                current.next = current.next.next;
            }else{
                current = current.next;
            }
        }
        return head;
    }
}

88.合并两个有序数组

nums2 的元素从 nums1 的尾部开始插入,也可以替换 nums1 中的 0 最后调用内置排序算法,算是一种偷懒的解法

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int j = n+m-1;
        for(int i = 0; i < n; i++){
            nums1[j] = nums2[i];
            j--;
        }
        Arrays.sort(nums1);
    }
}

因为两个数组是有序的,且长度固定,可以使用逆序归并排序

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int k = n+m-1;
        int i = m-1;
        int j = n-1;
        while(k >= 0){
            if(i < 0){
                nums1[k--] = nums2[j--];
            }else if(j < 0){
                break;
            }else if(nums1[i] < nums2[j]){
                nums1[k--] = nums2[j--];
            }else{
                nums1[k--] = nums1[i--];
            }
        }
    }
}

100.相同的树

需要注意空指针,难度不大,使用递归即可

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null){
            return true;
        }else if(p != null && q != null && p.val == q.val){
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }else{
            return false;
        }
    }
}

101.对称二叉树

这题与上一题有点类似,将 p 的左子树与 q 的右子树比较,p 的右子树与 q 的左子树比较。

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return isMirror(root, root);
    }
    public boolean isMirror(TreeNode p, TreeNode q){
        if(p == null && q == null){
            return true;
        }else if(p != null && q != null && p.val == q.val){
            return isMirror(p.left, q.right) && isMirror(p.right, q.left);
        }else{
            return false;
        }
    }
}

官方解答

104.二叉树的最大深度

使用DFS(深度优先搜索)即可

递归:

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }else{
            return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
        }
    }
}

迭代:

class Solution {
  public int maxDepth(TreeNode root) {
    Queue<Pair<TreeNode, Integer>> stack = new LinkedList<>();
    if (root != null) {
      stack.add(new Pair(root, 1));
    }

    int depth = 0;
    while (!stack.isEmpty()) {
      Pair<TreeNode, Integer> current = stack.poll();
      root = current.getKey();
      int current_depth = current.getValue();
      if (root != null) {
        depth = Math.max(depth, current_depth);
        stack.add(new Pair(root.left, current_depth + 1));
        stack.add(new Pair(root.right, current_depth + 1));
      }
    }
    return depth;
  }
}

官方解答

107.二叉树的层序变量II

使用广度优先搜索,遍历完成后反转列表即可

迭代:

class Solution {
    public List<List<Integer>> levelOrderBottom(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>temp=new ArrayList<>();
			for(int i=0;i<size;i++){
				TreeNode node=queue.poll();
				temp.add(node.val);
				if(node.left!=null)
					queue.offer(node.left);
				if(node.right!=null)
					queue.offer(node.right);
			}
			res.add(temp);
		}
		Collections.reverse(res);
		return res;
    }
}

递归:

class Solution {
    public List<List<Integer>>levelOrderBottom(TreeNode root){
		List<List<Integer>>res=new ArrayList<>();
		helper(root,0,res);
		Collections.reverse(res);
		return res;
	}
	public void helper(TreeNode root,int depth,List<List<Integer>>res){
		if(root==null)
			return;
		if(depth+1>res.size())
			res.add(new ArrayList());
		res.get(depth).add(root.val);
		if(root.left!=null)helper(root.left,depth+1,res);
		if(root.right!=null)helper(root.right,depth+1,res);
	}
}

108.将有序数组转换为二叉搜索树

一直纠结使用深度优先搜索来解决,无果。阅读评论和解答后,完全想不到使用二分查找。理解后其实不难

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return nums == null? null:buildTree(nums, 0, nums.length - 1);
    }
    
    public TreeNode buildTree(int nums[], int l, int r){
        if(l > r){
            return null;   
        }
        int mid = l + (r - l) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = buildTree(nums, l, mid - 1);
        root.right = buildTree(nums, mid + 1, r);
        return root;
    }
}

110.平衡二叉树

可以使用之前求二叉树最大深度的方法,判断左右子树的高度差是否大于1

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }
        if(Math.abs(maxDepth(root.left)-maxDepth(root.right)) > 1){
            return false;
        }
        return isBalanced(root.left) && isBalanced(root.right);
    }
    public int maxDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }else{
            return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
        }
    }
}

111.二叉树的最小深度

和求最大深度类似,取左右子树中的最小值即可。不过,有一种情况例外,遇到如下的二叉数时,要取两者间的最大值。

    1
   /        当根节点只有左子树(或右子树)时等价于求最大深度
 2          
class Solution {
    public int minDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }else{
            if(root.left != null && root.right != null){
                return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
            }
            return Math.max(minDepth(root.left), minDepth(root.right)) + 1;
        }
    }
}

112.路径总和

结点的左右子树为空时,判断当前值是否等于目标和。不相等时,目标和减去当前值并递归。

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root == null){
            return false;
        }
        if(root.left == null && root.right == null){
            return sum == root.val;
        }
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
}

118.杨辉三角

numRows > 0 时,初始化 ans[0],之后每一行由前一行推出(跳过头尾元素)。

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ans = new ArrayList<>();
        if(numRows == 0) return ans;
        ans.add(new ArrayList<Integer>(){{add(1);}});
        for(int i = 1; i < numRows; i++){
            List<Integer> list = new ArrayList<>();
            List<Integer> preList = ans.get(i-1);
            list.add(1);
            for(int j = 1; j < i; j++){
                list.add(j, preList.get(j) + preList.get(j-1));
            }
            list.add(1);
            ans.add(list);
        }
        return ans;
    }
}

119.杨辉三角II

可以修改上一题实现,不过空间复杂度和时间复杂度都较高。

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<List<Integer>> ans = new ArrayList<>();
        ans.add(new ArrayList<Integer>(){{add(1);}});
        if(rowIndex == 0) return ans.get(0);
        for(int i = 1; i <= rowIndex; i++){
            List<Integer> list = new ArrayList<>();
            List<Integer> preList = ans.get(i-1);
            list.add(1);
            for(int j = 1; j < i; j++){
                list.add(j, preList.get(j) + preList.get(j-1));
            }
            list.add(1);
            ans.add(list);
        }
        return ans.get(rowIndex);
    }
}

还可以使用动态规划,在一个数组里修改

每次循环在原数组尾部加 1,逆序遍历

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> ans = new ArrayList<>();
        ans.add(1);
        if(rowIndex == 0) return ans;
        for(int i = 0; i < rowIndex; i++){
            ans.add(1);
            for(int j = i; j >= 1; j--){
                ans.set(j, ans.get(j) + ans.get(j - 1));
            }
        }
        return ans;
    }
}

121.买卖股票的最佳时机

寻找两个数字的最大差值(最大利润),且小的数字(买入价格)必须在大的数字之前(卖出价格)

暴力法:

class Solution {
    public int maxProfit(int[] prices) {
        int i = prices.length-1;
        int j = prices.length-2;
        int max = 0;
        while(i >= 0 && j >= 0){
            max = Math.max(max, prices[i]-prices[j]);
            if(j == 0 || prices[i] < prices[i-1]){
                i--;
                j = i;
            }
            j--;
        }
        return max;
    }
}

虽然可以完成该题,但时间复杂度很高,推荐使用动态规划

遍历一次数组,记录最小的值(买入价格),比较最大利润和当前的值(今日卖出价格)- 最小的值,这样保证了小的数值一定在大的数值前面

class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length == 0) return 0;
        int max = 0;
        int min = prices[0];
        for(int i = 0; i < prices.length; i++){
            min = Math.min(min, prices[i]);
            max = Math.max(max, prices[i] - min);
        }
        return max;
    }
}

122.买卖股票的最佳时机II

这题允许多次买入卖出,但再次买入时需卖掉之前买入的股票

以数组[7,1,5,3,4,8]为例,第二天买,第三天卖 (5-1),第四天买,第七天买 (8-3),收益为 9 ,最大。

可问题就在于如何卖出的时机,纠结于此的话便会陷入泥潭,使问题变复杂。

其实只要明天的价格比今天高,那就可以卖出,并再买入明天的股票。即 (5-1) + (4-3) + (8-4) = 9

class Solution {
    public int maxProfit(int[] prices) {
        int max = 0;
        for(int i = 0; i < prices.length-1; i++){
            if(prices[i] < prices[i+1]){
                max += prices[i+1] - prices[i];
            }
        }
        return max;
    }
}

125.验证回文串

使用双指针,一前一后扫描,遇到非数字字母直接跳过

不知道是不是因为正则匹配还是截取字符串的效率较低,此解法在 leecode 上跑了 130ms,实在太慢了

class Solution {
    public boolean isPalindrome(String s) {
        int i = 0;
        int j = s.length();
        while(i < j){
            if(!s.substring(i,i+1).matches("[0-9a-zA-Z]")){
                i++;
                continue;
            }
            if(!s.substring(j-1,j).matches("[0-9a-zA-Z]")){
                j--;
                continue;
            }
            if(!s.substring(i,i+1).toLowerCase().equals(s.substring(j-1,j).toLowerCase())){
                return false;
            }else{
                i++;
                j--;
            }
        }
        return true;
    }
}

后面了解到 Character 类有静态方法 isLetterOrDigit 可以判断数字和字母,更改代码后只用了 3ms 就跑完了

class Solution {
    public boolean isPalindrome(String s) {
        int i = 0;
        int j = s.length()-1;
        while(i < j){
            if(!Character.isLetterOrDigit(s.charAt(i))){
                i++;
                continue;
            }
            if(!Character.isLetterOrDigit(s.charAt(j))){
                j--;
                continue;
            }
            if(Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j))){
                return false;
            }else{
                i++;
                j--;
            }
        }
        return true;
    }
}

136.只出现一次的数字

第一个想到的是用哈希表记录出现次数,比较简单,时间复杂度 O(n),空间复杂度 O(n)

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            map.merge(nums[i], 1, Integer::sum);
        }
        if(!map.isEmpty()){
            for(Integer key: map.keySet()){
                if(map.get(key) == 1){
                    return key;
                }
            }
        }
        return 0;
    }
}

题目提示可以使用位运算解决,思考无果后查看评论区,可以使用异或运算解决

异或运算:两个一样的数异或等于 0,任何数与 0 异或等于本身

因为该题重复的数字最多只会出现两次,所以可以使用异或,否则重复次数为奇数时会出错

class Solution {
    public int singleNumber(int[] nums) {
        int ans = 0;
        for(int num: nums){
            ans = ans ^ num;
        }
        return ans;
    }
}

141.环型链表

使用哈希表记录遍历过的结点,如果存在环路,那一定会在哈希表中找到该结点

时间复杂度 O(n)、空间复杂度 O(n)

public class Solution {
    public boolean hasCycle(ListNode head) {
        Map<ListNode, Integer> map = new HashMap<>();
        while(head != null){
            if(!map.containsKey(head)){
                map.put(head, 1);
                head = head.next;
            }else{
                return true;
            }
        }
        return false;
    }
}

还可以使用双指针,以下是官方的解释:

通过使用具有 不同速度 的快、慢两个指针遍历链表,空间复杂度可以被降低至 O(1)。慢指针每次移动一步,而快指针每次移动两步。

如果列表中不存在环,最终快指针将会最先到达尾部,此时我们可以返回 false

现在考虑一个环形链表,把慢指针和快指针想象成两个在环形赛道上跑步的运动员(分别称之为慢跑者与快跑者)。而快跑者最终一定会追上慢跑者。这是为什么呢?考虑下面这种情况(记作情况 A)- 假如快跑者只落后慢跑者一步,在下一次迭代中,它们就会分别跑了一步或两步并相遇。

其他情况又会怎样呢?例如,我们没有考虑快跑者在慢跑者之后两步或三步的情况。但其实不难想到,因为在下一次或者下下次迭代后,又会变成上面提到的情况 A

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }
}

155.最小栈

因为要求能在常数时间内找到最小的数,所以必须将最小数保存下来

而删除栈顶时可能会将最小数删掉,需将每次入栈时的最小数保存下来

使用双栈,一个存储数据,一个存储最小值

class MinStack {
    
    private Stack<Integer> min;
    private Stack<Integer> stack;

    public MinStack() {
        min = new Stack<>();
        stack = new Stack<>();
    }

    public void push(int x) {
        stack.push(x);
        if(min.empty() || x <= min.peek()){
            min.push(x);
        }
    }

    public void pop() {
        if(stack.peek().equals(min.peek())){
            min.pop();
        }
        stack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return min.peek();
    }
}

还可以在一个栈上进行操作,每次入栈前,先将目前栈中的最小值入栈,这样每次出栈后,就可以顺便更新最小值

class MinStack {
    
   private int min = Integer.MAX_VALUE;
    private Stack<Integer> stack;

    public MinStack() {
        stack = new Stack<>();
    }

    public void push(int x) {
        if(min >= x){
            stack.push(min);
            min = x;
        }
        stack.push(x);
    }

    public void pop() {
        if(stack.pop() == min){
            min = stack.pop();
        }
    }

    public int top() {
      return stack.peek();
    }

    public int getMin() {
        return min;
    }
}

160.相交链表

我们需要将较长的链表移动 k 位,与较短的链表同步遍历,如果两个结点相同,即相交。

而 k 的值等于长链表的长度减去短链表的长度

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int len1=0;
        int len2=0;
        ListNode a = headA;
        ListNode b = headB;
        while(a!=null){
            len1++;
            a= a.next;
        }
        while(b!=null){
            len2++;
            b= b.next;
        }
       
        if(len1>len2){
             int k = len1-len2;
            while(k>0){
                headA = headA.next;
                k--;
            }
        }else{
             int k = len2-len1;
             while(k>0){
                headB = headB.next;
                k--;
            }
        }
        while(headA!=null){
            if(headA==headB)
                return headA;
            headA= headA.next;
            headB= headB.next;
        }
        return null;
    }
}

167.两数之和II - 输入有序数组

使用哈希表,存储每个位置的 target - numbers[i],再次遍历,返回解

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

使用哈希表虽然可以解决,但需要使用额外的空间,时间复杂度也较高。

使用双指针从前后扫描数组,如果等于 target 则直接返回。

因为数组是有序的,所以右指针指向的数一定比左指针大,因此当两数之和比 target 大时,右指针左移,反之,左指针右移

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int l = 0;
        int r = numbers.length-1;
        while(l < r){
            if(numbers[l] + numbers[r] == target){
                return new int[]{l+1, r+1};
            }
            if(numbers[l] + numbers[r] < target){
                l++;
            }else{
                r--;
            }
        }
        return new int[]{0, 0};
    }
}

168.Excel表列名称

每次循环需要将 n - 1。这样处理可以将其 A ~ Z0 ~ 25 所对应。

class Solution {
    public String convertToTitle(int n) {
        StringBuilder ans = new StringBuilder();
        while(n != 0){
            n -= 1;
            ans.append((char)(n % 26 + 'A'));
            n /= 26;
        }
        return ans.reverse().toString();
    }
}

169.求众数

万能的哈希表

class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int num: nums){
            map.merge(num, 1, Integer::sum);
            if(map.get(num) > nums.length / 2){
                return num;
            }
        }
        return 0;
    }
}

众数占总数的至少一半以上,可以使用摩尔投票来解决

设置一个计数器 count,一个初始数 ans,当遇到相同的数时,count++,否则 count--count == 0 时,重置 countans

举个栗子:

大小为100的数组,有51个0,49个非0的数字(比如49个1),无论怎么加减,最后count总会大于等于1,ans等于0

class Solution {
    public int majorityElement(int[] nums) {
        int ans = nums[0];
        int count = 1;
        for(int i = 0; i < nums.length; i++){
            if(nums[i] != ans){
                count--;
                if(count == 0){
                    ans = nums[i];
                    count = 1;
                }
            }
            else{
                count++;
            }
        }
        return ans;
    }
}

171.Excel表列序号

该题其实可以转变为进制转换问题,只需把二十六制转成十进制即可

逆序遍历,字母转换成所对应的数并乘上倍数,倍数再乘26

class Solution {
    public int titleToNumber(String s) {
        int ans = 0;
        int mul = 1;
        for(int i = s.length()-1; i >= 0; i--){
            ans = ans + ((int)s.charAt(i) - 64) * mul;
            mul *= 26;
        }
        return ans;
    }
}

172.阶乘后的零

这题可以简化为求5的个数,以下是评论区的解释:

首先题目的意思是末尾有几个0 比如6! = 【1* 2* 3* 4* 5* 6】 其中只有2*5末尾才有0,所以就可以抛去其他数据 专门看2 5 以及其倍数 毕竟 4 * 25末尾也是0 比如10! = 【2*4*5*6*8*10】 其中 4能拆成2*2 10能拆成2*5 所以10! = 【2*(2*2)*5*(2*3)*(2*2*2)*(2*5)】 一个2和一个5配对 就产生一个0 所以10!末尾2个0 转头一想 2肯定比5多 所以只数5的个数就行了 假若N=31 31里能凑10的5为[5, 2*5, 3*5, 4*5, 25, 6*5] 其中 25还能拆为 5**2 所以 里面的5的个数为 int(31/(5**1)) + int(31/(5**2)) 所以 只要先找个一个 5**x < n 的x的最大数 然后按上面循环加起来
class Solution {
    public int trailingZeroes(int n) {
        return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);
    }
}

189.旋转数组

双循环,一个一个移动

class Solution {
    public void rotate(int[] nums, int k) {
        for (int j = 0; j < k; j++) {
            int a = nums[nums.length - 1];
            for (int i = nums.length - 2; i >= 0; i--) {
                nums[i + 1] = nums[i];
            }
            nums[0] = a;
        }
    }
}

三次反转

第一次数组全反转,第二次前半部分反转,第三次后半部分反转(以 k 划分前后部分)

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n;
        reverse(nums, 0, n - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
    }
    
    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start++] = nums[end];
            nums[end--] = temp;
        }
    }
}

190.颠倒二进制位

使用 Integer.reverse()

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        return Integer.reverse(n);
    }
}

自己实现反转:取出最低位,反转(左移),累加

class Solution {
    public int reverseBits(int n) {
        int res = 0;
        for(int i = 0; i < 32; i++){
            int temp = n >> i;
            temp &= 1;
            temp <<=(31 - i);
            res |= temp;
        }
        return res;
    }
}

191.位1的个数

与上一题类似,不过是把反转改成相加

public class Solution {
    public int hammingWeight(int n) {
        int res = 0;
        for(int i = 0; i < 32; i++){
            int temp = n >> i;
            res += temp &= 1;
        }
        return res;
    }
}

198.打家劫舍

根据题目,两个数不能相连,很容易想到分别求奇偶数和,但有些最优解并不是全为奇数或偶数

举个栗子:[2,1,1,2] ,最优解为 4(1,4),所以我们需要比较每次奇偶和的大小,这样就能保证每次的和是目前最大的

class Solution {
    public int rob(int[] nums) {
        int oddSum = 0;
        int evenSum = 0;
        for(int i = 0; i < nums.length; i++){
            if(i % 2 == 0){
                oddSum += nums[i];
                oddSum = Math.max(oddSum, evenSum);
            }else{
                evenSum += nums[i];
                evenSum = Math.max(oddSum, evenSum);
            }
        }
        return Math.max(oddSum, evenSum);
    }
}

或使用动态规划解决,比较 dp[i-1]dp[i-2] + nums[i](不能偷相邻的)即可

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

PS:偷个东西都要求收益最大化,是个狼灭

202.快乐数

本题的难点在于返回 false 的条件,通过百度得知所有不快乐数 (false) 都会陷入 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 的循环中。所以只要出现该循环中的数,即可返回 true

class Solution {
    public boolean isHappy(int n) {
        while(n != 1){
            int temp = 0;
            while(n > 0){
                temp += Math.pow(n % 10, 2);
                n /= 10;
            }
            if(temp == 4){
                return false;
            }
            n = temp;
        }
        return true;
    }
}

203.移除链表元素

这题没什么难度,将不等于 val 值的节点添加进新的链表即可

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode myhead = new ListNode(0);
        ListNode ln = myhead;
        while(head != null){
            if(head.val != val){
                ln.next = head;
                ln = ln.next;
            }
            if(head.next == null){
                ln.next = null;
            }
            head = head.next;
        }
        return myhead.next;
    }
}

204.计数质数

用直接法对其进行求解:

class Solution {
    public int countPrimes(int n) {
        if(n < 3) return 0;
        int ans = n-2;
        for (int i = 2; i < n; i++){
            for(int j = 2; j < (n/2+1); j++){
                if (i != j && i % j == 0){
                    ans--;
                    break;
                }
            }
        }
        return ans;
    }
}

在数值不大时可行,但随着数值增大,其时间复杂度呈指数式增长,导致会超出时间限制,所以该方法无法求解大数字

于是需要使用厄拉多塞筛法求解,其原理如下:

先将2-N的各数放入表中,然后在2的上面画一个圆圈,然后划去2的其他倍数;第一个既未画圈又没有被划去的数是3,将它画圈,再划去3的其他倍数;现在既未画圈又没有被划去的第一个数 是5,将它画圈,并划去5的其他倍数……依次类推,一直到所有小于或等于N的各数都画了圈或划去为止。这时,表中画了圈的以及未划去的那些数正好就是小于 N的素数。

具体实现如下:

class Solution {
    public int countPrimes(int n) {
        boolean[] nums = new boolean[n];
        for (int i = 2; i < nums.length; i++) {
            nums[i] = true;
        }

        for(int i = 2; i*i < nums.length; i++) {
            if (nums[i]) {
                for(int j = i*i; j < nums.length; j+=i) {
                    nums[j] = false;
                }
            }
        }

        int ans = 0;
        for(boolean bool : nums) {
            ans += bool ? 1 : 0;
        }
        return ans;
    }
}

通过对每个数字进行标记,区分质数合数,最后求和即可。

205.同构字符串

使用哈希表记录下两个字符串所对应的字符。判断哈希表中是否存在当前字符的 Key,有的话继续判断是否相等。否则检查值中是否有另一个字符。

class Solution {
    public boolean isIsomorphic(String s, String t) {
        Map<Character, Character> map = new HashMap<>();
        for(int i = 0; i < s.length(); i++){
            char sc = s.charAt(i);
            char tc = t.charAt(i);
            if(map.containsKey(sc)){
                if(map.get(sc) != tc) return false;
            }else{
                if(map.containsValue(tc)) return false;
            }
            map.put(sc, tc);
        }
        return true;
    }
}

206.反转链表

迭代法:

定义前指针:prev,当前指针:curr,临时指针:nextTemp

首先用临时指针保存当前节点的下一节点,改变当前节点的下一节点为前节点,前节点、当前节点后移。

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }
}

递归法比较复杂,可以看下官方解答

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode p = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return p;
}

217.存在重复元素

哈希表记录首次出现元素,存在即可返回 true

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int num: nums){
            if(map.containsKey(num)){
                return true;
            }else{
                map.put(num, 1);
            }
        }
        return false;
    }
}

哈希表虽方便,但需要消耗更多的空间和时间。因为只要找到一个重复的数字即可,所以可以先对数组进行排序,再存储第一个元素(如果存在的话),相同返回 true,不同跳过。

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);
        if(nums.length == 0) return false;
        int temp = nums[0];
        for(int i = 1; i < nums.length; i++){
            if(nums[i] != temp){
                temp = nums[i];
            }else{
                return true;
            }
        }
        return false;
    }
}

219.存在重复元素 II

这道题的描述有点含糊不清,以下是原题目:

给定一个整数数组和一个整数 k,判断数组中是否存在两个不同的索引 i 和 j,使得 nums [i] = nums [j],并且 ij 的差的绝对值最大为 k

ij 的差的绝对值要大于等于 k ,剩下的与上一题类似,同样使用哈希表即可。

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            if(map.containsKey(nums[i])){
                if(i - map.get(nums[i]) <= k) return true;
            }
            map.put(nums[i], i);
        }
        return false;
    }
}

226.翻转二叉树

使用递归,互换左右子树,当节点为空是返回

刚开始写的时候考虑到有左右子树都不为空、左为空右不为空、右为空左不为空三种情况,用了三个判断,思路比较容易理解。不过这样的写法很繁琐,我们可以写得更加简洁。

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null) return root;
        if(root.left != null && root.right != null){
            TreeNode temp = root.left;
            root.left = root.right;
            root.right = temp;
            invertTree(root.left);
            invertTree(root.right);
        }else if(root.left == null && root.right != null){
            root.left = root.right;
            root.right = null;
            invertTree(root.left);
        }else if(root.left != null && root.right == null){
            root.right = root.left;
            root.left = null;
            invertTree(root.right);
        }
        return root;
    }
}

不管是哪种情况,左右子树都要交换,所以不用考虑左右子树是否为空,可以直接交换

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null) return root;
        TreeNode temp = root.left;
        root.left = invertTree(root.right);
        root.right = invertTree(temp);
        return root;
    }
}

231.2的幂

将 n 不断地除以2,如果是2的幂,最终肯定会是1

class Solution {
    public boolean isPowerOfTwo(int n) {
        if(n == 0) return false;
        while(n % 2 == 0){
            n = n >> 1;
        }
        if(n == 1) return true;
        return false;
    }
}

2的幂的二进制都有一个特点,其二进制数只会有一个1,比如16的二进制数就是10000,而15则是01111,利用这点,将 n & n-1,如果是2的幂,那一定等于0。(不看评论还真不知道这么巧妙的解法)

class Solution {
    public boolean isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }
}

232.用栈实现队列

使用双栈来实现双队列。添加元素时,将 stack1 中的元素弹出并压入 stack2,此时元素反转。将新元素压入 stack2 中,执行相反操作。

其余操作使用栈自带 API 即可

class MyQueue {
    
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;

    /** Initialize your data structure here. */
    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        while(!stack1.empty()){
            stack2.push(stack1.pop());
        }
        stack2.push(x);
        while(!stack2.empty()){
            stack1.push(stack2.pop());
        }
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        return stack1.pop();
    }
    
    /** Get the front element. */
    public int peek() {
        return stack1.peek();
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return stack1.empty();
    }
}

234.回文链表

使用快慢指针定位链表的中点,然后反转后半(或前半)段链表来进行比较。

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        slow = reverse(slow.next);
        while(slow != null) {
            if (head.val != slow.val) {
                return false;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }
    
    private ListNode reverse(ListNode head){
        if (head.next == null) {
            return head;
        }
        ListNode newHead = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

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

该题主要利用二叉搜索数树的的性质来解决,其性质如下:

  1. 节点 N 左子树上的所有节点的值都小于等于节点 N 的值
  2. 节点 N 右子树上的所有节点的值都大于等于节点 N 的值
  3. 左子树和右子树也都是 有以上性质

所以当 p、q 的值都小于 root 时,那么 p、q 都在左子树,反之,则在右子树。如果一大一小,则当前 root 就是最近的祖先。

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

237.删除链表中的节点

这题只给了要删除的节点,所以无法直接删除,需要复制下一个节点的 valnext。 

class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

242.有效的字母异位词

对两个字符串进行排序,如果相等的话,即使异位词

class Solution {
    public boolean isAnagram(String s, String t) {
        char[] c1 = s.toCharArray();
        char[] c2 = t.toCharArray();
        Arrays.sort(c1);
        Arrays.sort(c2);
        return Arrays.equals(c1, c2);
    }
}

或者使用一个长度为26的数组记录每个字母,s 中出现加一,t 中出现减一。最后遍历该数组,只要数组中全为0,即是异位词。

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        int[] counter = new int[26];
        for (int i = 0; i < s.length(); i++) {
            counter[s.charAt(i) - 'a']++;
            counter[t.charAt(i) - 'a']--;
        }
        for (int count : counter) {
            if (count != 0) {
                return false;
            }
        }
        return true;
    }
}

257.二叉树的所有路径

使用递归,将每层的 val 拼接到一个字符串中。到达叶子节点时,将字符串添加到数组中。

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> results = new ArrayList<>();
        test(root, "", results);
        return results;     
    }
    
    public void test(TreeNode root, String s, List<String> lists){
        if(root == null) return;
        if(root.left == null && root.right == null){
            lists.add(s + root.val);
        }
        s = s + root.val + "->";
        test(root.left, s, lists);
        test(root.right, s, lists);
    }
}

258.各位相加

循环

class Solution {
    public int addDigits(int num) {
        int temp = 0;
        while(true){
            int pop = num % 10;
            num /= 10;
            temp += pop;
            if(num == 0){
                if(temp < 10) {
                    return temp;
                }
                else {
                    num = temp;
                    temp = 0;
                }
            }
        }
    }
}

还有一种是用数学方法求解,具体可以看这里的解答

class Solution {
    public int addDigits(int num) {
        if(num == 0) return 0;
        return num % 9 == 0 ? 9 : num % 9;
    }
}

263.丑数

遇到这类数学问题,一定要先弄清楚其定义或性质。以下是百度百科的描述和判断方法:

丑数描述

        把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但7、14不是,因为它们包含质因子7。 习惯上我们把1当做是第一个丑数。
        前20个丑数为:1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36。

判断方法

        首先除2,直到不能整除为止,然后除5到不能整除为止,然后除3直到不能整除为止。最终判断剩余的数字是否为1,如果是1则为丑数,否则不是丑数。

清楚了这些之后,就能很容易解决该题了

class Solution {
    public boolean isUgly(int num) {
        if(num == 0) return false;
        int divisor = 2;
        while(true){
            if(num == 1) return true;
            if(num % divisor == 0){
                num /= divisor;
            }else{
                if(divisor == 2) divisor = 3;
                else if(divisor == 3) divisor = 5;
                else if(divisor == 5) return false;
            }
        }
    }
}

268.缺失数字

排序法,比较常规的方法。直接遍历排序后的数组,找出缺失的数字。

class Solution {
    public int missingNumber(int[] nums) {
        Arrays.sort(nums);
        for(int i = 0; i < nums.length; i++){
            if(i != nums[i]) return i;
        }
        return nums.length;
    }
}

位运算法,对一个数字进行两次相同的异或运算会得到原来的数字,这样就能找到缺失的数字(缺失的数字只会出现一次)。

class Solution {
    public int missingNumber(int[] nums) {
        int res = nums.length;
        for(int i = 0; i < nums.length; i++){
            res = res ^ nums[i] ^ i;
        }
        return res;
    }
}

还可以使用高斯公式求和,与数组的和的差即是缺失的数字。

class Solution {
    public int missingNumber(int[] nums) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++){
            sum += nums[i];
        }
        return (nums.length * (nums.length + 1) ) / 2 - sum;
    }
}

278.第一个错误版本

典型的二分查找题目,求中点时要注意溢出,用 l + (r - l) / 2 来代替 (r + l) / 2

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int l = 1;
        int r = n;
        while(l < r){
            int m = l + (r - l) / 2;
            if(isBadVersion(m)) r = m;
            else l = m + 1;
        }
        return l;
    }
}

283.移动零

本题使用双指针 i、j,i 指向第一个0,j 指向需要交换的元素。先遍历数组寻找第一个0(如果存在),j 从 i + 1 开始遍历寻找非0元素。

交换后,i + 1,这样可以让 i  一直指向第一个0。重复上述过程即可完成后移。

class Solution {
    public void moveZeroes(int[] nums) {
        int i = 0;
        for(; i < nums.length; i++){
            if(nums[i] == 0) break;
        }
        int j = i + 1;
        while(j < nums.length){
            if(nums[j] != 0){
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
                i++;
            }
            j++;
        }
    }
}

290.单词规律

这种类型的题目还是用哈希表还解决。我这里没有把 pattern 转换为字符串数组,这样可以筛选出 patternstrs 长度不一的测试用例。

检查是否存在已有值是为了防止 strs 全部一样的情况。

class Solution {
    public boolean wordPattern(String pattern, String str) {
        String[] strs = str.split(" ");
        Map<Character, String> map = new HashMap<>();
        if (pattern.length() != strs.length) return false;
        for (int i = 0; i < strs.length; i++){
            if (map.containsKey(pattern.charAt(i))){
                if (!map.get(pattern.charAt(i)).equals(strs[i])) return false;
            }else {
                if (map.containsValue(strs[i])) return false;
                map.put(pattern.charAt(i), strs[i]);
            }
        }
        return true;
    }
}

292.Nim游戏

Nim游戏说明

这题乍看之下有点复杂,但我们可以从官方给的示例中找到解决的思路,以下的示例:

输入: 4
输出: false
解释: 如果堆中有 4 块石头,那么你永远不会赢得比赛;
        因为无论你拿走 1 块、2 块 还是 3 块石头,最后一块石头总是会被你的朋友拿走。

我们可以先假设当有5块石头时,你可以先拿走1块,而你朋友无论拿走几块,你总能拿走最后一块。之后再假设6、7、8块石头的情况,会发现,当有8块时,最后一块会被你朋友拿走。

到此,我们就能看出规律,只要石头数量是4的倍数时,你必输。

class Solution {
    public boolean canWinNim(int n) {
        return n % 4 != 0;
    }
}

303.区域和检索 - 数组不可变

暴力法,将 ij 之间的元素相加,时间复杂度 O(n)

class NumArray {
    
    private int[] nums;

    public NumArray(int[] nums) {
        this.nums = nums;
    }
    
    public int sumRange(int i, int j) {
        int sum = 0;
        for(; i <= j; i++){
            sum += nums[i];
        }
        return sum;
    }
}

动态规划,实例化时先将从 0 ~ 1 、0 ~ 2 、…… 、0 ~ n-1、0 ~ n 的和存入数组 sum

调用 sumRange 时计算 sum[j+1] - sum[i] 即可。

class NumArray {
    
    private int[] sum;

    public NumArray(int[] nums) {
        sum = new int[nums.length + 1];
        sum[0] = 0;
        for (int i = 0; i < nums.length; i++) {
            sum[i + 1] = sum[i] + nums[i];
        }
    }
    
    public int sumRange(int i, int j) {
        return sum[j + 1] - sum[i];
    }
}

326.3的幂

循环,比较常规的解法

class Solution {
    public boolean isPowerOfThree(int num) {
        if(num < 1) return false;
        
        while(num % 3 == 0) num /= 3;
        
        return num == 1;
    }
}

还有其他不用循环和递归的方法,可以看下官方解答

342.4的幂

循环解法和3的幂类似

class Solution {
    public boolean isPowerOfFour(int num) {
        if(num < 1) return false;
        
        while(num % 4 == 0) num /= 4;
        
        return num == 1;
    }
}

如果一个数是4的幂,那也肯定是2的幂。反之不一定。所以可以在2的幂上进行拓展,只要从2的幂中筛选出4的幂即可。

class Solution {
    public boolean isPowerOfFour(int num) {
        return (num & (num - 1)) == 0 && (num - 1) % 3 == 0;
    }
}

344.反转字符串

出现的所有字符都是 ASCII 中出现的,可以利用其完成反转

class Solution {
    public void reverseString(char[] s) {
        int len = s.length - 1;
        int temp = 0;
        for(int i = 0; i < s.length / 2; i++){
            if(s[i] - s[len-i] > 0){
                temp = s[i] - s[len-i];
                s[i] = (char) (s[i] - temp);
                s[len-i] = (char) (s[len-i] + temp);
            }else{
                temp = s[len-i] - s[i];
                s[i] = (char) (s[i] + temp);
                s[len-i] = (char) (s[len-i] - temp);
            }
        }
    }
}

或者使用双指针,比较简单

class Solution {
    public void reverseString(char[] s) {
        int i = 0;
        int j = s.length -1;
        while(i < j){
            char c = s[i];
            s[i++] = s[j];
            s[j--] = c;
        }
    }
}

345.反转字符串中的元音字母

与上一题类似,增加对元音字母的判断即可,注意大写字母也需要判断。

class Solution {
    public String reverseVowels(String s) {
        int i = 0;
        int j = s.length() - 1;
        char[] c = s.toCharArray();
        while(i <= j){
            if(c[i] == 'a' || c[i] == 'e' || c[i] == 'i' || c[i] == 'o' || c[i] == 'u' ||
              c[i] == 'A' || c[i] == 'E' || c[i] == 'I' || c[i] == 'O' || c[i] == 'U'){
                if(c[j] == 'a' || c[j] == 'e' || c[j] == 'i' || c[j] == 'o' || c[j] == 'u' ||
                  c[j] == 'A' || c[j] == 'E' || c[j] == 'I' || c[j] == 'O' || c[j] == 'U'){
                    char temp = c[j];
                    c[j] = c[i];
                    c[i++] = temp;
                }
                j--;
            }else{
                i++;
            }
        }
        return new String(c);
    }
}
  • 用支付宝打我
  • 用微信打我

Long may the sunshine

发表评论

电子邮件地址不会被公开。 必填项已用*标注

召唤蕾姆