38. Count and Say

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, …

1 is read off as “one 1” or 11.
11 is read off as “two 1s” or 21.
21 is read off as “one 2, then one 1” or 1211.
Given an integer n, generate the nth sequence.

Note: The sequence of integers will be represented as a string.

思路:刚开始被这题绕了好久,后来发现就是个循环计数问题。

1 可以被读作 “1个1″, 也就是 11

11可以被读作 “2个1″, 也就是 21

21可以被读作”1个2,1个1″,也就是 1211

依次类推….

大概要解决的问题有2个,如何找到第n次的读数结果,可以拆分为:

  1. 那么对于给定的n,我们要找到第n次结果,那总共就要做n-1次的读数。可以用一个循环来解决
  2. 我们在读每个数的时候,要查下前几位跟后一位是否相同,读数的结果就是: 这个数出现的次数 + 这个数的数值本身。 我们在做的时候需要用指针来判断前后两个数是否相同,并用变量count来记录出现的次数
  1. 每次读完一个数生层的读数结果,要临时保存下来,给下次读数计算使用。 所以我们需要个临时中间变量来保存。
public class Solution {
    public String countAndSay(int n) {
        if (n <= 1) return "1";
        String oldStr = "1";
        for (int i = 0; i < n - 1; i++) {
            int count = 1;
            String tmp = "";
            for (int j = 1; j < oldStr.length() + 1; j++) {
                if (j < oldStr.length() && oldStr.charAt(j) == oldStr.charAt(j - 1)) {
                    count++;
                } else {
                    tmp += String.valueOf(count) + oldStr.charAt(j - 1);
                    count = 1;
                }
            }
            oldStr = tmp;
        }

        return oldStr;
    }
}

几个注意的细节:
1. 读数的时候指针以j-1为主,我们循环的从1 -> oldStr的长度 + 1
2. n<=1的情况都返回"1"

Advertisements

125. Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
“A man, a plan, a canal: Panama” is a palindrome.
“race a car” is not a palindrome.

思路: 两指针分别从两头往中间找,挨个比较。
注意用到Java Character的API,在此列举下:

Method Description
boolean isLetter(char ch)
boolean isDigit(char ch)
char toUpperCase(char ch)
char toLowerCase(char ch)
boolean isUpperCase(char ch)
boolean isLowerCase(char ch)
boolean isWhitespace(char ch)

public class Solution {
    public boolean isPalindrome(String s) {
        if (s == null || s.length() == 0) return true;
        int left = 0;
        int right = s.length() - 1;
        while(left &amp;lt; right) {
            while (!isLetterOrDigit(s.charAt(left)) &amp;amp;&amp;amp; left &amp;lt; right) {
                left++;
            }
            while (!isLetterOrDigit(s.charAt(right)) &amp;amp;&amp;amp; left &amp;lt; right) {
                right--;
            }
            if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    public boolean isLetterOrDigit(char s) {
        return Character.isLetter(s) || Character.isDigit(s);
    }



}

67. Add Binary

Given two binary strings, return their sum (also a binary string).

For example,
a = “11”
b = “1”
Return “100”.

思路:
从右往左挨个比较,进行二进制的数值计算。把每位获得的值放到StringBuffer里面,最后检查carry是否为1,并reverse,最后以String返回。

public class Solution {
    public String addBinary(String a, String b) {
        if (a == null || a.length() == 0) return b;
        if (b == null || b.length() == 0) return a;

        StringBuilder sb = new StringBuilder();
        int carry = 0;
        int alen = a.length() - 1;
        int blen = b.length() - 1;
        for (int ia = alen, ib = blen; ia &gt;= 0 || ib &gt;= 0; ia--,ib--) {
            int aNum = ia &lt; 0 ? 0 : a.charAt(ia) - '0';
            int bNum = ib &lt; 0 ? 0 : b.charAt(ib) - '0';
            int sum = aNum + bNum + carry;
            int digit = sum % 2;
            sb.append(digit);
            carry = sum / 2;
        }
        if (carry == 1) {
            sb.append('1');
        }
        sb.reverse();
        return sb.toString();
    }
}

注意点:

  • 如何从char转化为对应的数字? 可以char的值跟’a’, ‘A’, ‘0’做减法
  • 处理String做运算的题目可以考虑是否能用StringBuilder, 依次把计算的数值放进去,最后reverse。
  • 二进制carry的情况,最后别忘了检查carry是否为1. 如果为1,则要进位。

 

404. Sum of Left Leaves

Find the sum of all left leaves in a given binary tree.

思路: 套用tree traversal的模板,用in-order traversal来做,需要加个parent节点来跟踪,用来判断何时做和

 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        int sum = 0;
        TreeNode cur = root;
        TreeNode parent = root;
        Stack<TreeNode> stack = new Stack<>();
        while(cur!= null || !stack.isEmpty()) {
            if (cur != null) {
                if (cur.left != null){
                     parent = cur;
                }
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop();
                if (parent.left == cur && cur.left == null && cur.right == null) {
                    sum += cur.val;
                }
                cur = cur.right;
            }
        }
        return sum;
    }
}

9. Palindrome Number

Determine whether an integer is a palindrome. Do this without extra space.

思路:可以把从低位往高位挨个取得的余数,组成的数字跟原来数字比较是否相等。注意:1.负数不为Palindrome 2. 0 为Palindrome

public class Solution {
    public boolean isPalindrome(int x) {
    if (x < 0) return false;
    if (x == 0) return true;
    int target = x;
    int r = 0;
    while (x != 0) {
        r = r* 10 + x % 10;
        x = x / 10;
    }
    if (r == target) return true;
        return false;
    }
}

也可以挨个比较第一位跟最后一位, 第二位跟倒数第二位,。。。。。

public class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0) return false;
        if (x == 0) return true;
        int div = 1;
        while(x / div >= 10) {
            div *= 10;
        }
        while(x != 0) {
            int left = x / div;
            int right = x % 10;
            if (left != right) 
                return false;
            x = (x % div) / 10;
            div /= 100;
        }
        return true;
    }
}

开Leetcode博客了,每天坚持刷题,督促自己

 

楼主开这个博客也是无奈之举,之前多次刷题但是都半途而废了,越来越怀疑自己的行动力了!。 每次想跳槽跳个好公司,但总是被算法牢牢卡死。开这个博客也是监督自己能坚持下来,记录刷题面试过程中的点点滴滴,最后拿到心仪的offer。目前先设立个小目标,希望100天内能够把leetcode中的全部easy,跟绝大部分medium难度的题目15分钟内bug free。 有目标就有动力! C’mon man! 就是要跟leetcode死磕到底。