开发学习

发布日期: 2022-03-15

文章字数: 2k

阅读时长: 9 分

阅读次数:

leetcode

前言

淦作为一个web手为了面大厂还是要低下头去刷leetcode。虽然嘴很硬说考算法的渗透测试岗永远得不到我，但是没人会选择放弃BAT这种大厂的实习机会。顺便加强一下自己的代码能力吧。本篇文章的题目都尽量使用三种语言进行解题，分别是Java，python3和golang。python3应该是写起来手感更好的语言，但是因为最近在卷Java web和golang，不得不向生活低下了头。毕竟网络安全从业人员不能有短板。

easy

两数之和

题目描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

解题

package easy;
import java.util.HashMap;
import java.util.Map;
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i< nums.length; i++) {
            if(map.containsKey(target - nums[i])) {
                return new int[] {map.get(target-nums[i]),i};
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}
public class TwoCounts {
    public static void main (String[] args) {
        Solution solution = new Solution();
        int[] numList = {2,7,11,15};
        int target = 9;
        int[] answer = solution.twoSum(numList,target);
        for (int i = 0;i < answer.length;i++){
            int x = answer[i];
            System.out.println(x);
        }
    }
}

先定义一个map，使用target减去该值，如果结果存在于map的key值中，则判断存在，返回map的value值和该元素在数组中的下标。如果不存在则将其存入map。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] + nums[j] == target:
                    return [i, j]
        
        return []

这里的python和golang代码就是暴力穷举的思路

func twoSum(nums []int, target int) []int {
    for i, x := range nums {
        for j := i + 1; j < len(nums); j++ {
            if x+nums[j] == target {
                return []int{i, j}
            }
        }
    }
    return nil
}

回文数

题目描述

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

例如，121 是回文，而 123 不是。

解题

class Solution:
    def isPalindrome(self, x: int) -> bool:
        string = str(x)
        restring = string[::-1]
        if string == restring:
            return True
        else:
            return False

字符串倒叙使用**string[::-1]**即可

罗马数字专整数

题目描述

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

字符数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如，罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。

解题

class Solution:
    def romanToInt(self, s: str) -> int:
        dic = {'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000,'IV':4,'IX':9,'XL':40,'XC':90,'CD':400,'CM':900} #构建哈希表
        tmp = 0
        n = len(s)
        i = 0
        while i < n-1:
            tmp1 = s[i] + s[i+1]
            if tmp1 in dic:
                tmp = tmp + dic[tmp1]
                i = i+2

            else:
                tmp = tmp + dic[s[i]]
                i = i + 1
        if i < n:
            tmp = tmp + dic[s[n-1]]
        return tmp

import java.util.HashMap;

public class Solution {
    public int romanToInt(String s) {
        HashMap<String, Integer> map = new HashMap<>(20);
        map.put("I", 1);
        map.put("V", 5);
        map.put("X", 10);
        map.put("L", 50);
        map.put("C", 100);
        map.put("D", 500);
        map.put("M", 1000);
        map.put("IV", 4);
        map.put("IX", 9);
        map.put("XL", 40);
        map.put("XC", 90);
        map.put("CD", 400);
        map.put("CM", 900);
        Integer tmp = 0;
        Integer n = s.length();
        Integer i = 0;
        while (i < n - 1) {
            String tmp1 = String.valueOf(s.charAt(i));
            String tmp2 = String.valueOf(s.charAt(i + 1));
            String tmp3 = tmp1 + tmp2;
            if (map.containsKey(tmp3)) {
                tmp = tmp + map.get(tmp3);
                i = i + 2;
            }
            else {
                String a = String.valueOf(s.charAt(i));
                tmp = tmp + map.get(a);
                i++;
            }

        }
        if (i < n) {
            String a = String.valueOf(s.charAt(n - 1));
            tmp = tmp + map.get(a);
        }
        return tmp ;
    }
}

最长公共前缀

题目描述

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 “”。

示例 1：

输入：strs = [“flower”,”flow”,”flight”]
输出：”fl”
示例 2：

输入：strs = [“dog”,”racecar”,”car”]
输出：””
解释：输入不存在公共前缀。

解题

def longestCommonPrefix(s: list) -> str:
    if not s:
        return ""
    s.sort()
    n = len(s)
    a = s[0]
    b = s[n-1]
    res = ""
    for i in range(len(a)):
        if i < len(b) and a[i] == b[i]:
            res += a[i]
        else:
            break
    return res

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0){return "";}
        StringBuilder res = new StringBuilder();
        Arrays.sort(strs);
        char[] a = strs[0].toCharArray();
        char[] b = strs[strs.length - 1].toCharArray();

        for (int i = 0; i < a.length;i++) {
            if (i < b.length && a[i] == b[i]){
                res.append(a[i]);
            } else {
                break;
            }
        }
        return res.toString();
    }
}

浅写一下String、StringBuffer和StringBuilder的区别：

String类是不可变类，即一旦一个String对象被创建以后，包含在这个对象中的字符序列是不可改变的，直至这个对象被销毁。

StringBuffer对象则代表一个字符序列可变的字符串，当一个StringBuffer被创建以后，通过StringBuffer提供的append()、insert()、reverse()、setCharAt()、setLength()等方法可以改变这个字符串对象的字符序列。一旦通过StringBuffer生成了最终想要的字符串，就可以调用它的toString()方法将其转换为一个String对象。

StringBuilder类也代表可变字符串对象。实际上，StringBuilder和StringBuffer基本相似，两个类的构造器和方法也基本相同。不同的是：StringBuffer是线程安全的，而StringBuilder则没有实现线程安全功能，所以性能略高。

有效括号

import string
def isvalid(test: str):
    dic = {')':'(',']':'[','}':'{'}
    stack = []
    for i in test:
        if stack and i in dic:
            if stack[-1] == dic[i]: stack.pop()
            else: return False
        else: stack.append(i)
    return not stack





if __name__ == "__main__":
    str = "{[]}"
    #isvalid(str)
    print(isvalid(str))

合并两个有效链表

题目描述

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的

解题

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if not list1:return list2
        if not list2:return list1
        if list1.val <= list2.val:
            list1.next = self.mergeTwoLists(list1.next,list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1, list2.next)
            return list2

剑指：两个栈实现队列

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

函数设计：
题目只要求实现加入队尾appendTail() 和删除队首deleteHead() 两个函数的正常工作，因此我们可以设计栈 A 用于加入队尾操作，栈 B 用于将元素倒序，从而实现删除队首元素。

加入队尾 appendTail()函数：将数字 val 加入栈 A 即可。
删除队首deleteHead()函数：有以下三种情况。
当栈 B 不为空： B中仍有已完成倒序的元素，因此直接返回 B 的栈顶元素。
否则，当 A 为空：即两个栈都为空，无元素，因此返回 -1−1 。
否则：将栈 A 元素全部转移至栈 B 中，实现元素倒序，并返回栈 B 的栈顶元素。

class CQueue:
    def __init__(self):
        self.A, self.B = [], []

    def appendTail(self, value: int) -> None:
        self.A.append(value)

    def deleteHead(self) -> int:
        if self.B: return self.B.pop()
        if not self.A: return -1
        while self.A:
            self.B.append(self.A.pop())
        return self.B.pop()

medium

hard

Wh1teR0be

https://m1yuu.com/2022/03/15/leetcode/

本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Wh1teR0be !

学习记录日记开发

java_web学习之路(二)：JavaByteCode从烧0到1

2022-03-23 web安全

java安全学习记录 java web

java_web学习之路(三)：CommonCollections 负无穷到烧0

2022-03-15 web安全

java安全学习记录 java web poc CommonCollections

web手的leetcode刷题记录

leetcode

前言

easy

两数之和

题目描述

解题

回文数

题目描述

解题

罗马数字专整数

题目描述

解题

最长公共前缀

题目描述

解题

浅写一下String、StringBuffer和StringBuilder的区别：

有效括号

合并两个有效链表

题目描述

解题

剑指：两个栈实现队列

medium

hard