LeetCode-无重复字符的最长子串

题目

给定一个字符串,找出不含有重复字符的最长子串的长度。

示例 1:

输入: "abcabcbb"
输出: 3
解释: 无重复字符的最长子串是 "abc",其长度为 3。
示例 2:

输入: "bbbbb"
输出: 1
解释: 无重复字符的最长子串是 "b",其长度为 1。
示例 3:

输入: "pwwkew"
输出: 3
解释: 无重复字符的最长子串是 "wke",其长度为 3。

 请注意,答案必须是一个子串,"pwke" 是一个子序列 而不是子串。

思路

从字符串中找出最长的子串。
首先分析得,子串肯定是连续的,那么可以定义一个滑动的窗口。
这个窗口保存的是当前没有重复字母的子串,一旦出现重复,则将窗口向前移动,也就是把从(包括)重复的那个字母前面的字符删除除。看上去就像一个窗口向前移动。最后记录下最大的不重复的长度即是结果。

答案

class Solution {
    public int lengthOfLongestSubstring(String str) {
        if(str.length() == 0){
            return 0;
        }
        HashMap<Character, Integer> map = new HashMap<>();
        StringBuilder window = new StringBuilder();
        int maxLen = -1;
        for (int i = 0; i < str.length(); i++){
            Character character = str.charAt(i);
            if(map.containsKey(character)){
                if (window.length() > maxLen){
                    maxLen = window.length();
                }
                int index = map.get(character);
                window.replace(0, index + 1, "");
                window.append(character);
                map.clear();
                for (int j = 0; j < window.length(); j++){
                    map.put(window.charAt(j), j);
                }
                continue;
            }
            window.append(character);
            map.put(character, window.length() - 1);
        }
        if (window.length() > maxLen){
            maxLen = window.length();
        }
        return maxLen;  
    }
}

哎代码太复杂,其实不需要弄个真正的字符串来充当window。只需要用一个index来表示即可。下面是优化过的代码时间复杂度为O(n):

class Solution {
    public int lengthOfLongestSubstring(String str) {
        HashMap<Character, Integer> map = new HashMap<>();
        int count = str.length();
        int len = 0;
        int startIndex = 0;
        for (int i = 0; i < count; i++){
            Character character = str.charAt(i);
            if(map.containsKey(character)){
                int index = map.get(character);
                if (index >= startIndex){
                    len = Math.max(i - startIndex, len);
                    startIndex = index + 1;
                }
            }
            map.put(character, i);
        }
        return Math.max(count - startIndex, len);
    }
}

LeetCode

这又扯淡了。
没事刷刷LeetCode。对自己面试也有帮助。

LeetCode-两数相加

题目

给定两个非空链表来表示两个非负整数。位数按照逆序方式存储,它们的每个节点只存储单个数字。将两数相加返回一个新的链表。

你可以假设除了数字 0 之外,这两个数字都不会以零开头。

示例:

输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807

思路

1.两个链表每次同时取一个item相加
2.记录进位的情况,在下一次相加时加上进位
3.考虑两个链表长度不一的情况
4.最后一个如果进位记得加一个node

答案

答案比较丑。看了官方答案写的挺简洁··

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l11, ListNode l22) {
        ListNode l1 = l11;
        ListNode l2 = l22;
            
        ListNode l3 = null;
        ListNode l4 = null;
        int tmp = 0;
        boolean end = false;
        while(true){
            int l1Val = 0;
            int l2Val = 0;
            if(l1 != null){
                l1Val = l1.val;
            }
            if(l2 != null){
                l2Val = l2.val;
            }
            int val = l1Val + l2Val + tmp;
            if(val >= 10){
                tmp = 1;
                val = val % 10;
            }else {
                tmp = 0;
            }
            if(l3 == null){
                l3 = new ListNode(val);
                l4 = l3;
            }else {
                ListNode tmpNode = new ListNode(val);
                l4.next = tmpNode;
                l4 = tmpNode;
            }
            
            if((l1 == null || l1.next == null) && (l2 == null || l2.next == null)){
                if(tmp == 1){
                    l4.next = new ListNode(1);
                }
                break;
            }
            if(l1 != null){
                l1 = l1.next;
            }
            if(l2 != null){
                l2 = l2.next;
            }
          
        }
       
        return l3;
    }
}

LeetCode-两数之和

题目

给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

思路

首先将每个item与target的结果算出与对应的index存放起来,因为差值肯定还是在nums数组中,因此再遍历nums找出对应的index即可。

答案

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<String, Integer> resultMap = new HashMap<String, Integer>();
        for(int i = 0; i < nums.length; i++){
            resultMap.put(String.valueOf(target - nums[i]), i);
        }
        for(int i = 0; i < nums.length; i++){
            Integer index = resultMap.get(String.valueOf(nums[i]));
            if(index != null && !index.equals(i)){
                return new int[]{i, index};
            }
        }
        return new int[]{0, 0};
    }
}

游戏4-消砖块-绘制砖块、球

还是先上效果,画了一个10*3的方块阵,一个底部的长条,和一个小球
Screenshot_2018-10-08-14-07-28-231_com.lhxia.app.png

思路很简单:
1.方块阵其实就是一个二维数组
3.分为3个Spirite分别绘制,方块、长条、球。

下面是部分代码。还是老规矩会上传github
1.先创建3个精灵

//砖块
class Block : Spirit() {
    override fun render(time: Long, canvas: Canvas) {

        canvas.drawRect(x.toFloat(), y.toFloat(), (x + width).toFloat(), (y + height).toFloat(), Paint().apply {
            color = Color.RED
        })
    }

    override fun update(time: Long) {
    }
}

//ball
class Ball : Spirit() {
    override fun render(time: Long, canvas: Canvas) {
        canvas.drawCircle((x + width / 2).toFloat(), ((y + height / 2).toFloat()), (height / 2).toFloat(), Paint().apply {
            color = Color.RED
        })
    }

    override fun update(time: Long) {
    }
}

//boat,底部的那个长条东东
class Boat : Spirit() {
    override fun render(time: Long, canvas: Canvas) {
        canvas.drawRect(x.toFloat(), y.toFloat(), (x + width).toFloat(), (y + height).toFloat(), Paint().apply {
            color = Color.RED
        })
    }

    override fun update(time: Long) {
    }
}

2.分别初始化精灵

init {
    makeBlocks()
    makeBoat()
    makeBall()
}

//球
private fun makeBall(){
    val w = 30
    val h = 30
    ball = Ball()
    ball.width = w
    ball.height = h
    ball.x = Director.director.screenWidth / 2 - w / 2
    ball.y = boat.y - h
}

//底部长条
private fun makeBoat(){
    val w = blockList[0].width * 3
    val h = w * 2 / 5
    boat = Boat()
    boat.width = w
    boat.height = 60
    boat.x = Director.director.screenWidth / 2 - w / 2
    boat.y = Director.director.screenHeight - h - 30
}

private fun makeBlocks(){
    val col = 10
    val row = 3
    val paddingLeftRight = 50
    val marginLeftRight = 10
    val blockCount = col * row
    //居中
    val blockWidth = (Director.director.screenWidth - 2 * paddingLeftRight - (col - 1) * marginLeftRight) / col
    val blockHeight = blockWidth * 3 / 4
    blockList = ArrayList(blockCount)
    var x = paddingLeftRight
    var y = 0
    //绘制二维数组,这里使用一维数组模拟二维数组
    for (i in (0 .. blockCount)){
        val block = Block()
        block.x = x
        block.y = y
        block.width = blockWidth
        block.height = blockHeight
        blockList.add(block)
        x += (marginLeftRight + blockWidth)

        if (i != 0 && i % 10 == 0){
            y += (blockHeight + 10)
        }
        if (i % 10 == 0){
            x = paddingLeftRight
        }

    }
}

github