算法练习1

Add TwoNumbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

解题思路

题目意思大概就是整数相加，输入是两个反向存储整数的链表，以链表的形式输出两数之和。其实反向存储整数更方便两数相加，进位直接加到下一个节点上。设输入链表为l1、l2，当l1或l2不为空时，进行循环相加对应的位，并作进位处理。循环结束后判断时候仍有进位，若有就加一个进位节点。

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode head = new ListNode(0);
    ListNode p = l1, q = l2, curr = head;
    int carry = 0;
    while (p != null || q != null) {
        int x = (p != null) ? p.val : 0;
        int y = (q != null) ? q.val : 0;
        int sum = carry + x + y;
        carry = sum / 10;
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
        if (p != null) p = p.next;
        if (q != null) q = q.next;
    }
    if (carry > 0) {
        curr.next = new ListNode(carry);
    }
    return head.next;
}

---

Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

解题思路

题目意思是求最长不重复子串。我的思路是先求出字符串包含的字母个数num，最长不重复子串的长度必然小于等于num。接下来循环判断子串就好了。

代码

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] chars = new int[256];
        int res = 0;
        for (char c : s.toCharArray()) {
            chars[c] = 1;
        }
        int num = 0;
        for (int i = 0; i < 256; i++) {
            if (chars[i] != 0) num++;
        }

        for (int i = 0; i < s.length(); i++) {
            String ss;
            if (i > s.length() - num) {//不重复子串小于num且在s末尾
                ss = s.substring(i);
            } else {
                ss = s.substring(i, i + num);
            }
            int t = len(ss);
            res = t > res ? t : res;
        }
        return res;
    }
    
    public int len(String s) {//从左开始判断最长不重复子串长度
        int[] cs = new int[256];
        int lens = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (cs[c] == 1) return lens;
            else cs[c] = 1;
            lens++;
        }
        return lens;
    }
}