做 LeetCode 的一些记录（持续更新…）
希望做公司业务的同时，能每天有一点时间，做做这种锻炼逻辑，数据结构的东西。
1. 字符串中最长的子字符串长度。
1.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 >Gmust be a substring, “pwke” is a subsequence and not a substring.
就是说通过一个字符串，找到里面的最长的长度，返回长度。
其实第一感觉就是一个DP问题，但是几个月前没有做出来，今天没怎么想，就做出来了，感觉，还是嘿嘿嘿。编程能力的提升吧，回到正题：
我一开始准备说用一个二维数组去通过存储每一个的字符开头的最大字符数，然后一个max不断比较。后来发现通过用map也可以，似乎会更好，而且看解决提交的submission发现也有这样，key-value;
但是感觉还是用list会更好，通过不断加入，然后比较有新的字符后，判断之前的字符中包含这个的，过滤之前的。以下是代码实现：
import java.util.ArrayList;
import java.util.List;
public class Solution {
public int lengthOfLongestSubstring(String s) {
int length = s.length();
List<Character> list = new ArrayList<Character>();
int max = 0;
for(int i = 0; i<length; i++){
int index = is_contain(list, s.charAt(i));
if(index == -1) list.add(s.charAt(i));
else{
max = max > list.size()? max :list.size();
for(int j = 0; j<=index; j++)
list.remove(0);
list.add(s.charAt(i));
}
}
max = max > list.size()? max :list.size();
return max;
}
public int is_contain(List<Character> list, char c){
int size = list.size();
for(int i = 0 ;i< size ;i++){
if(list.get(i)==c) return i;
}
return -1;
}
}
2. 今天的是一个Hard Tag的题目：
Median of Two Sorted Arrays
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). 就是在俩个排了序的数组中找到相应的要输出的东西，但是 一开始觉得方法，很好，但是做了之后发现太多if,补漏很不好，用例只通过了 1000多个，一共俩千，把错误代码copy出来以儆效尤把，不但长，还特别多if.这样很不好。：
public class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int total = nums1.length + nums2.length;
int h1 = 0;
int h2 = 0;
int i = 2;
if(nums1.length == 0){
i--;
if(total ==1)return nums2[0];
if(total ==2)return (nums2[0]+nums2[1])/2.0;
}
if(nums2.length == 0){
i--;
if(total ==1)return nums1[0];
if(total ==2)return (nums1[0]+nums1[1])/2.0;
}
if(i ==1){
if(nums1.length ==0){
h2 = nums2.length/2;
return total%2==0?(nums2[h2-1]+nums2[h2])/2.0:nums2[h2]*1.0;
}else{
h1 = nums1.length/2;
return total%2==0?(nums1[h1-1]+nums1[h1])/2.0:nums1[h1]*1.0;
}
}
for( ; h1<nums1.length && h2<nums2.length && i < total/2+1;i++){
if(nums1[h1]<nums2[h2])
h1++;
else
h2++;
}
if(i == total/2+1){
if(h1<nums1.length && h2<nums2.length) {
return total%2==0?(nums1[h1]+nums2[h2])/2.0:(nums1[h1]>nums2[h2]?nums1[h1]:nums2[h2])*1.0;
}
else{
if(h1 ==nums1.length){
return total%2==0?(nums2[h2+1]+nums2[h2])/2.0:nums2[h2+1]*1.0;
}else{
return total%2==0?(nums1[h1]+nums1[h1+1])/2.0:nums1[h1+1]*1.0;
}
}
}
else{
if(h1 == nums1.length){
h2 += (total/2+1-i);
return total%2==0?(nums2[h2-1]+nums2[h2])/2.0:nums2[h2]*1.0;
}
else{
h1 += total/2+1-i;
return total%2==0?(nums1[h1-1]+nums1[h1])/2.0:nums1[h1]*1.0;
}
}
}
}
通过几十分钟的优化处理
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int size= nums1.length+ nums2.length;
int [] arr = new int[size];
int length1 = nums1.length;
int length2 = nums2.length;
int h1 = 0;
int h2 = 0;
int i= 0;
for(; i<size/2+1; i++){
if(h1<length1 && h2<length2){
arr[i]= nums1[h1]<nums2[h2]?nums1[h1++]:nums2[h2++];
}else{
if(h1 == length1)arr[i] = nums2[h2++];
else arr[i] = nums1[h1++];
}
}
// return i;
return size%2 ==0? (arr[i-1]+arr[i-2])/2.0:arr[i-1]*1.0;
}
代码量下降了80%多 只不过有些可以进行效率上的优化，效率看那个比较排后，看以后吧。 思路，就是通过arr存放，从小到大，然后取中间。这是很多逻辑上的限制要写出来。
3. 处理一个以前看了很久的Medimu的题目ZigZag Conversion
思路: 其实就是说一串字符串 按照给定的有几行rownum 形成一个zigzag 的z字形环字符串 然后从第一行开始 吧字符拼在一起.
将其实就是按照 行去取 然后头尾 的规则不一样。 （ 只不过遇到一个PHP的坑， 一开始用的PHP去写发现没有初始化 行的 字符串 ，所以 一直报出来 output limit error 用Python写的 就一次性过了。
def convert(self, s: str, numRows: int) -> str:
if numRows == 1:
return s
is_head = False
rowIndex = 0
str_list =['' for _ in range(numRows)]
for char in s:
print(char)
str_list[rowIndex] += char
if rowIndex == 0 or rowIndex == numRows -1:
is_head = bool(1 - is_head)
rowIndex += 1 if is_head else -1
return "".join(str_list)
function convert($s, $numRows) {
if($numRows == 1)return $s;
$strList = array_fill(0, $numRows ,'');// 坑 ！
$isHead =false;
$rowIndex = 0;
$len = strlen($s);
for($i=0;$i<$len;$i++){
$strList[$rowIndex] .= $s[$i];
if($rowIndex == $numRows -1 || $rowIndex == 0 )$isHead = !$isHead;
$rowIndex += $isHead ? 1 :-1;
}
return implode("", $strList);
}
4. 这是编程珠玑上面的一个看了很久:就是一个数组,在整个里面的元素向一个方向偏移,形成一个新的数组. 其实就是一个换 换了之后 另一个接着来 但是偶数就不行了
#这是替换的函数.
def revs(arr:list , step: int, index= 0) ->list:
...: char_ = arr[index]
...: for x in range(0,len(arr)):
...: char_index = arr[(index+step-1)%len(arr)]
...: print(char_index)
...: if char_ == arr[(index+step-1)%len(arr)]:
...: break
...: arr[(index+step-1)%len(arr)] = char_
...: print('---->{}'.format(char_))
...: char_ = char_index
...: index += step -1
5. 一道题 关于把一个数组里面所有的0放到后面 ,然后不为零的放到前面并保持相对顺序.(没有注意到最后一个写了一个 ,感觉还蛮有意思的) easy 难度
int i =0;
int j =numsSize-1;
while(i<j){
if(0 ==nums[i] && nums[j] !=0){
nums[i] = nums[i] ^nums[j];
nums[j] = nums[i] ^nums[j];
nums[i] = nums[i] ^nums[j];
}else{
nums[i] != 0? i++:i;
nums[j] == 0? j--:j ;
}
}
6. Container With Most Water 很经典的最大水体积的题
Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
就是给你一个非负的整数数组，然后你给出 最大的 数组段围起来水体积 难怪 Medium 赞有5k dislike 只有500
首先思路就是直接暴力， 每个每个遍历，double for each最大的 前后体积， 直接就返回了。
func maxArea(height []int) int {
max := -1
temp := -1
for i, x := range height{
for j,y := range height[ i:]{
j += i
if x > y {
temp = y * (j-i)
}else{
temp = x * (j-i)
}
if temp > max{
max := temp
}
}
}
return max
}
太慢了 只比20% 的人快， 后来想了下， 求最大的体积 其实从最外部开始 ，从数组两端 头尾 ，一步一步往内收， 这样 只需要 n 次 就可以了， 以为 是以 俩边最小的为边界的，所以这种方式可行。
func maxArea(height []int) int {
head , tail := 0, len(height)-1
sum := 0
for head < tail {
sum = max(sum,(tail-head) * min(height[head],height[tail]))
if height[head] > height[tail] {
tail--
}else{
head++
}
}
return sum
}
func max(x int, y int ) (z int) {
if x > y{
z = x
}else{
z = y
}
return z
}
func min(x int ,y int)(z int){
if x > y{
z = y
}else{
z = x
}
return z
}
虽然代码多了点,但是 效率上来说 快了10倍不止。
7. Integer to Roman 今天做了一个整形转罗马数字 的提， 很简单就是 将 3999-0 的数字转换成罗马数字 。（不得不吐槽下，真的有点蠢，难怪 赞踩比 1：3了快） 先贴自己的实现吧
func intToRoman(num int) string {
lined := map[int][]string{1000: {"M"}, 100: {"C", "D", "M"}, 10: {"X", "L", "C"}, 1: {"I", "V", "X"}}
resultStr := ""
index := []int {1000,100,10,1}
for _,index := range index {
x := lined[index]
tempStr := ""
if num/index > 0 {
temp := num / index
if temp <= 3 {
tempStr = repeat(x[0], temp)
} else if temp == 4 {
tempStr = x[0] + x[1]
} else if temp == 5 {
tempStr = x[1]
} else if temp < 9 {
tempStr = x[1] + repeat(x[0], temp-5)
} else {
tempStr = x[0]+x[2]
}
resultStr += tempStr
}
num = num % index
}
return resultStr
}
func repeat(chars string, num int) (result string) {
for i := 0; i < num; i++ {
result += chars
}
return result
}
就是将 1000， 100，10，1作为一个阶段来进行处理， 就是 用了十进制的思维。但是，怎么看怎么不优雅。 然后看了一点 讨论
public static String intToRoman(int num) {
String M[] = {"", "M", "MM", "MMM"};
String C[] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
String X[] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
String I[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
return M[num/1000] + C[(num%1000)/100] + X[(num%100)/10] + I[num%10];
}
我真的 ，一开始就是这么想的，哈哈哈哈 底下评论当代图灵机 笑死。。。。