搜索[leetcode]结果-低调大师优秀个人博客

精选列表

搜索[leetcode]，共439篇文章

Java----------LeetCode----------46. 全排列

说起回溯算法，渊源颇深，我上次做过一道，本应该这次能拿下但是，又没拿下，不过这次有点理解它的思想了，每次的回溯就是一个二叉树，简单的说，就是你执行的操作需要回溯时它会返回调用它的方法哪里的状态，进行下一步的执行。 public List<List<Integer>> permute(int[] nums) { List<List<Integer>> temp = new ArrayList<>(20); zuhe(temp,0,nums); return temp; } private void zuhe(List<List<Integer>> temp, int n, int[] nums) { /* * 每次让其加一个就行了，就空了， * */ if (nums.length == n) { List<Integer> integers =new ArrayList<>(20); for (int r:nums){ integers.add(r); } temp.add(integers); } for (int i = n, length = nums.length; i <length ; i++) { change(nums,i,n); zuhe(temp,n+1,nums); change(nums,i,n); } } public void change(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } 这个需要多练，具体自己体会

2018-08-04

LeetCode刷题指南(Java版)

项目和架构师等免费学习资料，更有数据库、分布式、微服务等热门技术学习视频，内容丰富，兼顾原理和实践，另外也将赠送作者原创的Java学习指南、Java程序员面试指南等干货资源）参考@CyC2018的leetcode

2018-08-02

java之 ------------[LeetCode] House Robber 打家劫舍||

做完打家劫舍后我发现自己动态规划方面处理问题的能力，终于迎来了开篇，虽然打家劫舍是在我看网上的别的人做的，然后自己理解的，但是我知道我再遇到这类题不会再手足无措了，隔了两天再来挑战，我看看自己的动态规划能力是否有那么一点点，于是做了打家劫舍||，虽然我做了将近2个小时，但是庆幸的是自己依靠自己的能力做了出来，很感动，自己花了一晚上的时间做出来了，我都被自己感动的哭了，我算法如此垃圾，竟然能完全依靠自己的能力做出这个算法，真的很让我相信：天才是少数的，大多数人喜欢给自己的懒，找借口。好了不说，说思路吧： 1.不让它收尾都取，只让它取其一，首端取了，尾端就不取，尾端取了首端就不取，然后在打家劫舍的基础上多声明一个数组，这个数组的取值是从原数组的尾端开始取值的，其实算法和打家劫舍一样，只不过我把打家劫舍的算法用了两遍， 2.上代码吧 public int rob(int[] nums) { if (nums.length == 0) { return 0; } if (nums.length == 1) { return nums[0]; } int max = Math.max(nums[0],nums[1]); if (nums.length == 2) { return max; } int[] f = new int[nums.length]; int[] n = new int[nums.length]; f[0] = nums[0]; f[1] = max; n[nums.length-1] = nums[nums.length-1]; n[nums.length-2] = Math.max(nums[nums.length-1],nums[nums.length-2]); for (int i = 2; i <nums.length-1 ; i++) { f[i] = Math.max(f[i - 2] + nums[i], f[i - 1]); } for (int i = nums.length-3; i > 0; i--) { n[i] = Math.max(n[i+2] + nums[i], n[i+1]); } if (f[nums.length-2] >= n[1]){ return f[nums.length-2]; } return n[1]; }

2018-07-30

java之 ------------[LeetCode] House Robber 打家劫舍

刚开始做这一道题感觉卧槽，这不简单吗，直接去把数组下标和2取余的数相加再把剩下的数相加，比较这两个和谁大就输出谁，不就行了，但是啊，我操，事实证明，我还是太天真了，我操出现[2,1,1,2]这种情况，我当时还怀疑为什么那么简单后来一想，我操，这不是动态规划吗，于是乎，恶补一下怎么实现动态规划的，说白了，动态规划就是把大的数据拆成小的数据，如我想计算f(10),我就要计算出f(9)+1,然后我想计算出f(9)=f(8)+1，递推的方式直到f(1)=f(0)+1,就结束了。就是上面的结果依赖与下边的结果。 /* 注意这里的返回值，你一定在疑惑为什么返回值，返回的是arry.length-1，那是因为我刚开始计算的时候 * 就涉及到前三个数字，如果返回arry.length，那么会报越界异常。 * 其实啊，说白了，就是【表情】那个对一个数组的递推，只不过借助一个空的数组来实现 * 前期给【表情】【表情】这个空的数组赋初值，这里是两个，借助的这个数组就前两个是有值的，其它没值 * */ public int leastPath(int[] arry) { int length = arry.length; // 声明一个空的数组，就是为了递推做准备 int[] another = new int[arry.length]; if (length == 0) { return 0; } if (length == 1) { return arry[0]; } int many = Math.max(arry[0],arry[1]); if (length == 2) { return many; } // 设置要进行递推的初值 another[0] = arry[0]; another[1] = many; // 注意这里的another.length，的设置，注意长度和下标的区别 for (int i = 2; i <another.length ; i++) { // 这是最核心的代码，当你计算出第一步递推，后边就简单了 another[i] = Math.max(another[i-2]+arry[i],arry[i-1]); } return another[arry.length-1]; }

2018-07-28

leetcode 20 Valid Parentheses 括号匹配

Given a string containing just the characters '(', ')', '{', '}', '[' and']', determine if the input string is valid. The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not. 写了一个0ms 的代码： // 20150630.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include <iostream> #include <stack> #include <string> using namespace std; bool isValid(string s) { if (s=="")return false; stack<char> Parentheses; int size =s.size(); Parentheses.push(s[0]); for(int i = 1;i < size ;++i) { if(Parentheses.top()=='('&&s[i]==')'||Parentheses.top()=='['&&s[i]==']'||Parentheses.top()=='{'&&s[i]=='}') { Parentheses.pop(); if (Parentheses.empty()&&(i+1)!=size) { Parentheses.push(s[i+1]); i++; } } else { Parentheses.push(s[i]); } } if(Parentheses.empty()) { return true; } else { return false; } } int _tmain(int argc, _TCHAR* argv[]) { string s = "()[]{}"; isValid(s); return 0; } 另外一个看着好看点的： class Solution { public: bool isValid(string s) { std::stack<char> openStack; for(int i = 0; i < s.length(); i++) { switch(s[i]) { case '(': case '{': case '[': openStack.push(s[i]); break; case ')': if(!openStack.empty() && openStack.top() == '(' ) openStack.pop(); else return false; break; case '}': if(!openStack.empty() && openStack.top() == '{' ) openStack.pop(); else return false; break; case ']': if(!openStack.empty() && openStack.top() == '[' ) openStack.pop(); else return false; break; default: return false; } } if(openStack.empty()) return true; else return false; } }; python代码： class Solution: # @return a boolean def isValid(self, s): stack = [] dict = {"]":"[", "}":"{", ")":"("} for char in s: if char in dict.values(): stack.append(char) elif char in dict.keys(): if stack == [] or dict[char] != stack.pop(): return False else: return False return stack == [] </pre><pre class="python" name="code">class Solution: # @param s, a string # @return a boolean def isValid(self, s): paren_map = { '(': ')', '{': '}', '[': ']' } stack = [] for p in s: if p in paren_map: stack.append(paren_map[p]) else: if not stack or stack.pop() != p: return False return not stack class Solution: # @param s, a string # @return a boolean def isValid(self, s): d = {'(':')', '[':']','{':'}'} sl = [] for i in s: if i in d: sl.append(i) else: if not sl or d[sl.pop()] != i: return False if sl: return False return True

2015-06-29

LeetCode27|最长公共前缀

1，问题简述编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串""。 2，示例示例1:输入: ["flower","flow","flight"]输出: "fl"示例2:输入: ["dog","racecar","car"]输出: ""解释: 输入不存在公共前缀。 3，题解思路对比 4，题解程序 import java.util.Arrays;public class LongestCommonPrefixTest { public static void main(String[] args) { String[] strs = {"flower", "flow", "flight"}; String longestCommonPrefix = longestCommonPrefix(strs); System.out.println("longestCommonPrefix = " + longestCommonPrefix); } public static String longestCommonPrefix(String[] strs) { if (strs == null || strs.length == 0) { return ""; } if (strs.length == 1) { return strs[0]; } Arrays.sort(strs); char[] c1 = strs[0].toCharArray(); char[] c2 = strs[strs.length - 1].toCharArray(); int maxLength = Math.min(c1.length, c2.length); StringBuilder stringBuilder = new StringBuilder(maxLength); int i = 0; while (i < maxLength) { if (c1[i] == c2[i]) { stringBuilder.append(c1[i]); } else { break; } i++; } return stringBuilder.toString(); }} 5，总结，这道题想着是上周有时间总结输出来的，但是还是延迟了一个周，才将这道题总结输出出来，这道题就是一个对比的题，本质上利用了缓存这一原理，之前自己在写类似键值对集合时，也有了自己的一点思考，输出总结这道题时也是有了自己的一点思考，觉得这个缓存这个概念真的很宽泛，单体应用下的map，分布式缓存常用的就是redis这样的缓存组件了，缓存，字面理解就是暂时存储，起到了一个缓冲的作用，估计和缓冲区又不太一样，写过redis的内容，我都忘了自己用它来做什么的了，看下过往写过redis用法的文章springboot整合redis进行缓存的使用,java进阶|Springboot整合Redis+Aop+自定义注解实现数据埋点操作，后面这篇文章是我觉得写得比较满意的一篇文章，业务场景用到的，其实输出文章就是帮助自己记录，顺便帮助需要的人，这就是写文章记录的意义了本文分享自微信公众号 - WwpwW（gh_245290c1861a）。如有侵权，请联系 support@oschina.cn 删除。本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。

2020-08-16

LeetCode 344. 反转字符串

题目编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。示例 1：输入：["h","e","l","l","o"] 输出：["o","l","l","e","h"] 示例 2：输入：["H","a","n","n","a","h"] 输出：["h","a","n","n","a","H"] 解题思路 class Solution: def reverseString(self, s: [str]) -> None: """ Do not return anything, modify s in-place instead. """ #交叉替换 # midNum = len(s)//2 # for i in range(midNum): # s[i], s[len(s)-1-i] = s[len(s)-1-i], s[i] #python内置函数 s.reverse()

2020-06-05

LeetCode 1：两数之和 Two Sum

题目：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。 Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution, and you may not use the same element twice. 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1] 解题思路：暴力穷举：外循环遍历每个元素 x，内循环查找是否存在一个值与 target - x 相等的目标元素，返回相等的目标元素和 x 的索引。时间复杂度 O (n^2)，效率太低，pass。哈希表：哈希映射（map、dict），key 保存该元素，value 保存该元素索引。两次遍历法：第一次遍历把所有元素及其索引保存到哈希映射，第二次遍历查找 target - x 相等的目标元素一次遍历法：假如 y = target - x，则 x = target -y，所以一次遍历在存入哈希映射的同时查找是否存在一个值与 target - x 相等的目标元素。例：nums = [2, 11, 7, 15], target = 9, hashmap = { } 遍历： i = 0: target - x = 9 - 2 = 7, 7 不存在于 hashmap 中，则 x(2) 加入 hashmap, hashmap = {2 : 0} i = 1: target - x = 9 - 11 = -2, -2 不存在于 hashmap 中，则 x(-2) 加入 hashmap, hashmap = {2 : 0, 11 : 1} i = 2: target - x = 9 - 7 = 2, 2 存在于 hashmap 中，则返回列表 [2, 0] 代码：两次遍历（Java）： class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) {//一次遍历转换成键值对，key为元素值，value为索引值 map.put(nums[i], i); } for (int i = 0; i < nums.length; i++) {//二次遍历查找符合条件的元素 int res = target - nums[i]; if (map.containsKey(res) && map.get(res) != i) {//查找到的目标元素不能为其本身 return new int[]{i, map.get(res)}; } } return null; } } 一次遍历 (Java)： class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int res = target - nums[i]; if (map.containsKey(res)) {//因为自身元素还未加入到 hashmap，无需 map.get(res) != i 条件判断 return new int[]{i, map.get(res)}; } map.put(nums[i], i);//未找到目标元素则将其加入 hashmap } return null; } } 一次遍历 (Python)： class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: dic = {} for i, num in enumerate(nums): #枚举 nums 数组 if num in dic: return [dic[num], i] else: dic[target-num] = i 利用 Python 数组自带 index 方法解题： class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: for i, num in enumerate(nums): if target-num in nums and nums.index(target-num) != i: return [i, nums.index(target-num)] list.index(): 描述: index () 函数用于从列表中找出某个值第一个匹配项的索引位置。语法: index () 方法语法： list.index(x, start, end) 参数: x-- 查找的对象。 start-- 可选，查找的起始位置。 end-- 可选，查找的结束位置。返回: 该方法返回查找对象的索引位置，如果没有找到对象则抛出异常。欢迎关注微.信.公.众号: 爱写Bug

2019-10-15

LeetCode 706：设计哈希映射 Design HashMap

题目：不使用任何内建的哈希表库设计一个哈希映射具体地说，你的设计应该包含以下的功能 put(key, value)：向哈希映射中插入(键,值)的数值对。如果键对应的值已经存在，更新这个值。 get(key)：返回给定的键所对应的值，如果映射中不包含这个键，返回-1。 remove(key)：如果映射中存在这个键，删除这个数值对。 Design a HashMap without using any built-in hash table libraries. To be specific, your design should include these functions: put(key, value) : Insert a (key, value) pair into the HashMap. If the value already exists in the HashMap, update the value. get(key): Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key. remove(key) : Remove the mapping for the value key if this map contains the mapping for the key. 示例： MyHashMap hashMap = new MyHashMap(); hashMap.put(1, 1); hashMap.put(2, 2); hashMap.get(1); // 返回 1 hashMap.get(3); // 返回 -1 (未找到) hashMap.put(2, 1); // 更新已有的值 hashMap.get(2); // 返回 1 hashMap.remove(2); // 删除键为2的数据 hashMap.get(2); // 返回 -1 (未找到) 注意：所有的值都在 [1, 1000000]的范围内。操作的总数目在[1, 10000]范围内。不要使用内建的哈希库。 Note: All keys and values will be in the range of [0, 1000000]. The number of operations will be in the range of [1, 10000]. Please do not use the built-in HashMap library. 解题思路：与设计哈希集合一题相似，只需要将布尔类型数组改成 int 整型数组，元素索引位置为Key值，元素值为Value值。题目中要求Key不存在时返回 -1 ，Python中可以直接初始化值为 -1 的长度为 1000001 的数组，直接返回 Value值即可。其他语言初始化数组后元素值默认为0，可以遍历一遍把值改为 -1，或存储值为真实值加 1，返回 Value - 1，如果 Key 不存在时 Value 为 0，返回 Value - 1 = -1，符合要求。代码： Java： class MyHashMap { private int[] hashMap; /** Initialize your data structure here. */ public MyHashMap() { this.hashMap=new int[1000001]; } /** value will always be non-negative. */ public void put(int key, int value) { hashMap[key] = value+1;//存储真实值加 1 } /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */ public int get(int key) { return hashMap[key] - 1;//返回存储值为 -1 得到真实值 } /** Removes the mapping of the specified value key if this map contains a mapping for the key */ public void remove(int key) { hashMap[key] = 0; } } Python： class MyHashMap: def __init__(self): """ Initialize your data structure here. """ self.hash_table = [-1]*1000001 def put(self, key: int, value: int) -> None: """ value will always be non-negative. """ self.hash_table[key] = value def get(self, key: int) -> int: """ Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key """ return self.hash_table[key]#直接返回Value def remove(self, key: int) -> None: """ Removes the mapping of the specified value key if this map contains a mapping for the key """ self.hash_table[key] = -1

2019-09-24

LeetCode 20：有效的括号 Valid Parentheses

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。 Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. 有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。 An input string is valid if: Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. 注意空字符串可被认为是有效字符串。 Note that an empty string is also considered valid. 示例 1: 输入: "()" 输出: true 示例 2: 输入: "()[]{}" 输出: true 示例 3: 输入: "(]" 输出: false 示例 4: 输入: "([)]" 输出: false 示例 5: 输入: "{[]}" 输出: true 解题思路：很简单的题，将字符串每个字符压入栈，简单判断即可。如：输入: "{[]}" 初始栈为空，'{' 入栈下一个字符栈顶元素 '{'与 '[' 不匹配，'[' 入栈下一个字符栈顶元素 '['与 ']' 匹配，'[' 出栈下一个字符栈顶元素 '{'与 '}' 匹配，'}' 出栈结束，栈为空，返回 True 关键在于判断字符是否匹配，匹配的标准是相反的括号字符，并非相同字符。可以用 switch 判断三种括号字符，或者三个 if 语句，再或者可以用散列表映射括号关系。 Java： class Solution { public boolean isValid(String s) { Stack<Character> stack = new Stack<>();//初始化栈 for (char b : s.toCharArray()) { switch (b) { case '(': { stack.push(')'); break; } case '{': { stack.push('}'); break; } case '[': { stack.push(']'); break; } default: {//不匹配的情况返回false if (stack.isEmpty() || stack.pop() != b) { return false; } } } } return stack.isEmpty();//栈为空则证明全部匹配，返回true，否则返回false } } Python: 注：python中没有 switch...case... 语句，官方让用 if 判断代替... class Solution: def isValid(self, s: str) -> bool: stack = [] for c in s: if c == '[': stack.append(']') elif c == '(': stack.append(')') elif c == '{': stack.append('}') elif len(stack) == 0 or stack.pop() != c: return False return len(stack) == 0 欢迎关注微.信公.众号：爱写Bug

2019-08-01

LeetCode第20题：有效的括号

题目给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。有效字符串需满足：1、左括号必须用相同类型的右括号闭合。2、左括号必须以正确的顺序闭合。3、注意空字符串可被认为是有效字符串。示例1:输入: "()" 输出: true 示例2:输入: "()[]{}" 输出: true 示例3:输入: "(]" 输出: false 示例4:输入: "([)]" 输出: false 示例5:输入: "{[]}" 输出: true 代码 class Solution(object): def isValid(self, s): """ :type s: str :rtype: bool """ stack = [] dict = {"]":"[", "}":"{", ")":"("} for char in s: if char in dict.values(): stack.append(char) elif char in dict.keys(): if stack == [] or dict[char] != stack.pop(): return False else: return False return not stack 本文链接：时光不写博客-有效的括号

2019-07-31

LeetCode第1题：两数之和

题目给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。示例:输入: nums = [2, 7, 11, 15], target = 9 解释: 因为nums[0] + nums[1] = 2 + 7 = 9 输出: [0, 1] 代码 class Solution(object): def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ d = {} for i in range(len(nums)): if d.get(target - nums[i], None) == None: d[nums[i]] = i else: return (d[target - nums[i]], i) 本文链接：时光不写博客-Two Sum

2019-07-29

LeetCode 206：反转链表 Reverse Linked List

反转一个单链表。 Reverse a singly linked list. 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 进阶:你可以迭代或递归地反转链表。你能否用两种方法解决这道题？ Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both? 解题思路：每次遍历到最后一位取节点这种方法就算了时间复杂度太高。如题目进阶要求的两种方法，迭代和递归：迭代：每次分出来一个节点把节点作为头节点添加到新链表上：原链表：1->2->3->4->5 分离第一个节点作为头节点添加到新链表：1 原链表：2->3->4->5 分离下一个节点作为头节点添加到新链表：2->1 原链表：3->4->5 分离下一个节点作为头节点添加到新链表：3->2->1 原链表：4->5 分离下一个节点作为头节点添加到新链表：4->3->2->1 原链表：5 分离下一个节点作为头节点添加到新链表：5->4->3->2->1 原链表：null Java： class Solution { public ListNode reverseList(ListNode head) { if (head == null || head.next == null) return head; ListNode pre = null; ListNode tmp = null; while (head != null) { tmp = head.next;//tmp暂存当前节点的下一个节点 head.next = pre;//当前节点下一个指向pre pre = head;//刷新pre head = tmp;//刷新当前节点为tmp } return pre; } } Python3： class Solution: def reverseList(self, head: ListNode) -> ListNode: if not head or not head.next: return head pre,tmp=None,None while(head): tmp=head.next head.next=pre pre=head head=tmp return pre 递归：其实就是用递归完成栈的功能：先进后出基线条件为遇到空节点（到链表末尾），返回对象为链表的最后一个节点，在递归函数中传递一直不变。从链表末尾向头部逐个分离节点，并将节点添加到新链表的末尾。与迭代法原理相似。原链表：1->2->3->4->5 递归到最后一层时遇到null节点返回尾节点5 回到上一层递归分离节点 5 作为新链表的尾节点：5，置空原本5节点，原链表1->2->3->4->null 回到上一层递归分离节点 4 作为新链表的尾节点：5->4，置空原本4节点，原链表1->2->3->null 回到上一层递归分离节点 3 作为新链表的尾节点：5->4->3，置空原本3节点，原链表1->2->null 回到上一层递归分离节点 2 作为新链表的尾节点：5->4->3->2，置空原本2节点，原链表1->null 回到上一层递归分离节点 1 作为新链表的尾节点：5->4->3->2->1，置空原本1节点，原链表null Java： class Solution { public ListNode reverseList(ListNode head) { //基线条件 if (head == null || head.next == null) return head; //递归 ListNode tmp = head.next;//暂存头节点的下一个节点 ListNode pre = reverseList(head.next);//递归调用该函数，pre为返回的新链表的头节点，原链表的最后一个节点，无论递归多少层该返回值一直传递不变 tmp.next = head;//暂存的下一个节点指向传入节点 head.next = null;//下一个节点即原本指向tmp的节点置空 return pre; } } Python3： class Solution: def reverseList(self, head: ListNode) -> ListNode: if not head or not head.next: return head tmp = head.next pre = self.reverseList(head.next) tmp.next = head head.next = None return pre 欢迎关注公.众号一起刷题：爱写Bug

2019-07-21

LeetCode 141：环形链表 Linked List Cycle

给定一个链表，判断链表中是否有环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。 Given a linked list, determine if it has a cycle in it. To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list. 示例 1：输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。示例 2：输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。示例 3：输入：head = [1], pos = -1 输出：false 解释：链表中没有环。进阶：你能用 O(1)（即，常量）内存解决此问题吗？ Follow up: Can you solve it using O(1) (i.e. constant) memory? 解题思路：从头节点向后遍历整个链表只要遍历到节点为 null ，就证明不是环形，而如果遍历到一个节点的地址之前存在过就证明有环。 1、哈希表：解决重复问题最容易想到的数据结构就是哈希表，哈希表添加节点时只要发现节点已经存在了，证明就有环形链表。并且哈希表查找和插入复杂度都为O(1)，但是空间复杂度会随着原链表长度而增大:O(n)，总的来说：时间复杂度：O(n)，虽然哈希表的查找和添加操作的时间复杂度是 O(1) ，但是先需要遍历链表然后插入，遍历的复杂度是O(n) 空间复杂度：O(n)，最多需要保存链表的 n个节点 2、双指针：这道题就如同小学跑步问题，假设有两个人（双指针）一个快一个慢，不停地向前跑，如果跑得快的那个最后到终点了（遇到空节点 null），就证明是直线跑道（没有环形链表）。如果是存在环形跑道（环形链表）：两个人一起跑步（双指针）一个快一个慢，那么这两个人因为速度不同，在环形跑道里跑得快的那个人一定会追上慢的。即两个指针相遇了，证明存在环形链表。空间复杂度为O(1)，即进阶要求的常量内存。哈希表解题： Java： public class Solution { public boolean hasCycle(ListNode head) { if (head == null) return false;//如果是空链表直接返回 Set<ListNode> nodeSet = new HashSet<>();//构造哈希表 while (head.next != null) {//链表下一个不为空 if (nodeSet.contains(head)) return true;//哈希表包含该节点则存在环形链表 nodeSet.add(head);//加入节点 head = head.next;//下移一位 } return false; } } Python： class Solution(object): def hasCycle(self, head): """ :type head: ListNode :rtype: bool """ if head is None: return False hashSet=set()#构造集合 while(head.next is not None): if head in hashSet:#是否已存在 return True hashSet.add(head) head=head.next return False 双指针解题： Java： public class Solution { public boolean hasCycle(ListNode head) { if (head == null || head.next == null) { return false; } ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) {//快指针及其下一位是否为空 slow = slow.next; fast = fast.next.next; if (slow == fast) {//如果相遇，存在环形链表 return true; } } return false; } } Python： class Solution(object): def hasCycle(self, head): """ :type head: ListNode :rtype: bool """ if head is None or head.next is None: return False slow, fast = head, head while fast is not None and fast.next is not None: slow, fast = slow.next, fast.next.next if slow == fast: return True return False 扩展： python 中is 与 == 区别： is 用于判断两个变量引用对象（即内存地址）是否为同一个， == 用于判断引用变量的值是否相等。而Python出于对性能的考虑，不可变对象、同一代码块中的对象、值相同的对象，都不会重复创建，而是直接引用已经存在的对象。欢迎关注公众号：爱写bug，一起学习。

2019-07-15

LeetCode 189：旋转数组 Rotate Array

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。 Given an array, rotate the array to the right by k steps, where k is non-negative. 示例 1: 输入: [1,2,3,4,5,6,7] 和 k = 3 输出: [5,6,7,1,2,3,4] 解释: 向右旋转 1 步: [7,1,2,3,4,5,6] 向右旋转 2 步: [6,7,1,2,3,4,5] 向右旋转 3 步: [5,6,7,1,2,3,4] 示例 2: 输入: [-1,-100,3,99] 和 k = 2 输出: [3,99,-1,-100] 解释: 向右旋转 1 步: [99,-1,-100,3] 向右旋转 2 步: [3,99,-1,-100] 说明: 尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。要求使用空间复杂度为 O(1) 的原地算法。 Note: Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem. Could you do it in-place with O(1) extra space 解题思路：如果按照示例那种一步一步向右移，太慢。我们直接看示例1输入和最终结果输出（移动步数k=3）：输入: [1,2,3,4,5,6,7]输出: [5,6,7,1,2,3,4] 找一下规律，我起先是以为直接以该索引 i 与 i+3 交换位置，不过仔细看一下就发现错的太离谱了。我们可以发现输出前三位数是输入的后三位，输出后四位数是输入的前四位。而移动步数 k=3，剩余长度=数组长度 - 移动步数 = 7-3=4 ，刚好对应我们发现的规律。只要截取输入的后k位的数组与输入的剩余长度的数组，即为所求：[5,6,7]+[1,2,3,4] 但是：题目要求使用空间复杂度为 O(1) 的原地算法。这在python中可以利用切片特性直接像上面那样截取，而空间复杂度不变。但是在CC++、Java里是肯定会改变空间复杂度，不满足要求。这时候可以换个思路，如下所示不断反转特定长度数组：输入: [1,2,3,4,5,6,7] 反转整个数组: [7,6,5,4,3,2,1] 反转前k位：[5,6,7] 反转剩余的: [1,2,3,4] 输出: [5,6,7,1,2,3,4] 或者改变一下顺序先反转前剩余位数和后k位：输入: [1,2,3,4,5,6,7] 反转前剩余长度的: [4,3,2,1] 反转后k位：[7,6,5] 此时数组：[4,3,2,1,7,6,5] 反转整个数组: [5,6,7,1,2,3,4] 输出: [5,6,7,1,2,3,4] Java（反转数组）： class Solution { public void rotate(int[] nums, int k) { int numsLen=nums.length,temp; k=k%numsLen; if(k==0) return; swapArray(nums,0,numsLen-1);//反转整个数组 swapArray(nums,0,k-1);//反转0到k-1索引，前k位的数组 swapArray(nums,k,numsLen-1);//反转k到末尾索引，后剩余位数位的数组 } private void swapArray(int[] nums,int start,int end){//反转函数 int temp; for (int i=start,j=end;i<j;i++,j--){ temp=nums[i]; nums[i]=nums[j]; nums[j]=temp; } } } 注：Java段代码是以反转方法里介绍的第一个方法为例，第二种方法只要改变一下 swapArray(nums,0,numsLen-1);//反转整个数组 swapArray(nums,0,k-1);//反转0到k-1索引，前k位的数组 swapArray(nums,k,numsLen-1);//反转k到末尾索引，后剩余位数位的数组的顺序和参数即可，不再复现。 Python3（利用切片）： class Solution: def rotate(self, nums: List[int], k: int) -> None: """ Do not return anything, modify nums in-place instead. """ nums_len = len(nums) k = k%nums_len nums[0:nums_len] = nums[nums_len-k:] + nums[:nums_len-k]#切片组成新数组

2019-07-08

Leetcode加一（java、python3）

加一给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。最高位数字存放在数组的首位，数组中每个元素只存储一个数字。你可以假设除了整数 0 之外，这个整数不会以零开头。 Given a non-empty array of digits representing a non-negative integer, plus one to the integer. The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit. You may assume the integer does not contain any leading zero, except the number 0 itself. 示例 1: 输入: [1,2,3] 输出: [1,2,4] 解释: 输入数组表示数字 123。示例 2: 输入: [4,3,2,1] 输出: [4,3,2,2] 解释: 输入数组表示数字 4321。 java: class Solution { public int[] plusOne(int[] digits) { for( int i=digits.length;i>=0;i--){ if(digits[i]+1==10){ digits[i]=0; }else { digits[i]+=1; break; } } if(digits[0]==0){ int[] digits2=new int[digits.length+1]; digits2[0]=1; return digits2; }else { return digits; } } } 思路：指针从最后往前移动，若值为10逐个加一，并赋值0。不等于10则退出循环。首位如果为是0则证明需要进一。这里新建一个长度比原数组大一。只需首位赋值1即可。 python3: class Solution: def plusOne(self, digits: List[int]) -> List[int]: """ :type digits:int :return: int """ num = 0 for i in range(len(digits)): num = num*10 + digits[i] return [int(i) for i in str(num+1)] python3则可以有很多实现方法，可以像以上java那种。可以把数组digits倒置，reversed(digits)然后逐项加1，最后如果为0，则直接对数组下一项赋值1（python3数组可动态扩展）。最后返回倒置数组。

2019-06-02

leetcode-53 最大子序和

题目给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例: 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。分析第一感觉要用到动态规划，就需要找出状态和状态转移方程。找状态至关重要，状态找的好，对应的状态转移方程可能就非常简单，状态找的不好，对应的状态转移方程可能就比较麻烦。找状态一般找问题本身或者问题的等价问题，先尝试以问题本身作为状态来分析，如果对应的状态转移方程很复杂，再根据问题尝试有没有其他的等价问题来作为状态初步分析首先以题目作为状态 f(n)为前n个元素的最大子序和的值由于f(n)只是前n个元素中的最大子序和，这个子序可能并不包含nums[n]元素，所以再来一个nums[n+1]时，并不太好确定f(n+1)，需要分如下2种情况来分析：当最大子序包含nums[n]，则f(n+1)的求解如下：如果nums[n+1]>0 则f(n+1)=f(n)+nums[n+1] 如果nums[n+1]<0 则f(n+1)=f(n) 当最大子序不包含nums[n]，则f(n+1)的求解如下：来一个nums[n+1]只会对以nums[n]结尾的每个子序的最大和产生更新影响，同时如果前面的子序和都是负的话，则nums[n+1]则是最大子序和，所以只需要计算出这部分更新后的最大子序和与f(n)对比求最大值即为f(n+1)的最大子序和即f(n+1)=max(f(n),以第n个元素结尾的最大子序和+nums[n+1],nums[n+1]) 这里我们就会发现针对上述f(n)的状态转移方程还是非常复杂，并且状态转移方程里面还包含了一个暂时没有结论的问题即：以第n个元素结尾的最大子序。这个问题其实也是一个动态规划，这个问题的解如下： g(n)为以第n个元素结尾的最大子序和，则g(n+1)的解如下：当g(n)>0 则g(n+1)=g(n)+nums[n] 当g(n)<=0 则g(n+1)=nums[n] 所以这个g(n)问题还是很好求解的。综上所述对于f(n)的求解是动态规划里面还嵌套动态规划，简述为父动态规划嵌套了子动态规划，不过还好，每一轮都可以求出这一轮的子动态规划值，然后利用这个值进而可以求出父动态规划的值。所以对于上述思路还是可以做出来结果的。不过上述思路也太复杂了，很可能是我们选择的状态不合适导致的，所以此时我们就需要转换思路有没有更合适的状态转换思路等价命题的转换并没有太多的规律可循，与实际题目息息相关，可能需要从上面的初始分析中进行提取。比如上面的g(n)还是很简单的，能否充分利用g(n)来解题？假如我知道了每个g(n)的值，那么f(n)其实就是max(g(k)) 0<=k<=n 所以整个问题其实就清晰明了了很多，最终是以第N个元素结尾的最大子序和作为状态来进行动态规划，利用动态规划的结果来求解最终的问题套路总结很多时候动态规划的出题者不会给你一个一眼就能看出的状态，这时候就可能需要重新去找一个等价命题的状态，比如对于该题，你能够快速想到g(n)这个状态假如想不到对应的等价命题的状态，看能否根据已有的简单的动态规划的解来求解问题，比如我已知了g(n)，能够利用g(n)作为突破口来推导目标问题的答案某个子序的解可能是所有以某个元素结尾的子序的解的max或者min等其他函数，以某个元素结尾的子序的解可以简化好多问题代码利用一个变量来记录g(n-1)的值，通过g(n-1)和状态转移方程来求解出g(n)，同时用一个变量来记录g(n)的最大值即为f(n) public static int maxSubArray(int[] nums) { int fn = nums[0]; int lastGn = nums[0]; for (int i = 1; i < nums.length; i++) { if (lastGn > 0) { lastGn += nums[i]; } else { lastGn = nums[i]; } if (lastGn > fn) { fn = lastGn; } } return fn; } 代码很简单，关键点不在于解决了此题，而是在于解决此题的思考过程，其中还是有一些套路可循的跑分欢迎关注微信公众号：乒乓狂魔

2019-04-08

Leetcode 142. Linked List Cycle II

地址：Leetcode 142. linked list Cycle II 问题描述：检测链表是否存在环，是的话返回环入口，否则返回None.

2019-01-05

leetcode算法题学习Java版（2）

但是参照了leetcode上别人的代码，效率更高，思路就是不断比较二者的最大值，把最大值放在nums1数组的最后，知道排序成功。

2018-10-01

leetcode算法题学习Java版（1）

https://leetcode-cn.com/explore/learn/card/queue-stack/217/queue-and-bfs/872/ 解题思路：广度优先，从某个为1的点开始，广度优先搜索他附近所有为

2018-09-29

资源下载

更多资源

腾讯云软件源

为解决软件依赖安装时官方源访问速度慢的问题，腾讯云为一些软件搭建了缓存服务。您可以通过使用腾讯云软件源站来提升依赖包的安装速度。为了方便用户自由搭建服务架构，目前腾讯云软件源站支持公网访问和内网访问。

Spring

Spring框架（Spring Framework）是由Rod Johnson于2002年提出的开源Java企业级应用框架，旨在通过使用JavaBean替代传统EJB实现方式降低企业级编程开发的复杂性。该框架基于简单性、可测试性和松耦合性设计理念，提供核心容器、应用上下文、数据访问集成等模块，支持整合Hibernate、Struts等第三方框架，其适用范围不仅限于服务器端开发，绝大多数Java应用均可从中受益。

Rocky Linux

Rocky Linux（中文名：洛基）是由Gregory Kurtzer于2020年12月发起的企业级Linux发行版，作为CentOS稳定版停止维护后与RHEL（Red Hat Enterprise Linux）完全兼容的开源替代方案，由社区拥有并管理，支持x86_64、aarch64等架构。其通过重新编译RHEL源代码提供长期稳定性，采用模块化包装和SELinux安全架构，默认包含GNOME桌面环境及XFS文件系统，支持十年生命周期更新。

Sublime Text

Sublime Text具有漂亮的用户界面和强大的功能，例如代码缩略图，Python的插件，代码段等。还可自定义键绑定，菜单和工具栏。Sublime Text 的主要功能包括：拼写检查，书签，完整的 Python API ， Goto 功能，即时项目切换，多选择，多窗口等等。Sublime Text 是一个跨平台的编辑器，同时支持Windows、Linux、Mac OS X等操作系统。