letcode 1-day

剑指 Offer 09. 用两个栈实现队列

class CQueue:

    def __init__(self):
        self.stack_a = []
        self.stack_b = []

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


    def deleteHead(self) -> int:
        if self.stack_b:
            return self.stack_b.pop()
        else:
            while self.stack_a:
                self.stack_b.append(self.stack_a.pop())
            if self.stack_b: 
                return self.stack_b.pop()
            else:
                return -1

剑指 Offer 03. 数组中重复的数字

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        for i in range(len(nums)):
            while nums[i]!=i:
                if nums[nums[i]]!=nums[i]:
                    tmp = nums[nums[i]]
                    nums[nums[i]] = nums[i]
                    nums[i] = tmp
                else:
                    return nums[i]
            

快速排序

def partition(arr, l, r):
    val = arr[l]
    while l < r:
        while l < r and arr[r] >= val:
            r -= 1
        if l < r:
            arr[l] = arr[r]
        while l < r and arr[l] <= val:
            l += 1
        if l < r:
            arr[r] = arr[l]
    arr[l] = val
    return l


def qsort(arr, l, r):
    if r <= l:
        return

    mid = partition(arr, l, r)

    qsort(arr, l, mid - 1)
    qsort(arr, mid + 1, r)


if __name__ == '__main__':
    arr = [3, 2, 41, 4]
    qsort(arr, 0, len(arr)-1)
    print(arr)

两数之和

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] indexs = new int[2];
        Map<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<nums.length;i++){
            if(map.containsKey(nums[i])){
                indexs[0]=i;
                indexs[1] = map.get(nums[i]);
                return indexs;
            }
            map.put(target-nums[i],i);
        }
        return indexs;
    }
}

整数反转

class Solution {
    public int reverse(int x) {
        int res = 0;
        while(x>0){
            int a = x %10;
            x = x/10;
            res = res * 10 + a;
        }
        return (int)res==res? (int)res:0;
    }
    
}

回文数

class Solution {
public:
    bool isPalindrome(int x) {
        // 特殊情况：
        // 如上所述，当 x < 0 时，x 不是回文数。
        // 同样地，如果数字的最后一位是 0，为了使该数字为回文，
        // 则其第一位数字也应该是 0
        // 只有 0 满足这一属性
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }

        int revertedNumber = 0;
        while (x > revertedNumber) {
            revertedNumber = revertedNumber * 10 + x % 10;
            x /= 10;
        }

        // 当数字长度为奇数时，我们可以通过 revertedNumber/10 去除处于中位的数字。
        // 例如，当输入为 12321 时，在 while 循环的末尾我们可以得到 x = 12，revertedNumber = 123，
        // 由于处于中位的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。
        return x == revertedNumber || x == revertedNumber / 10;
    }
};

最长公共前缀

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        String prefix = strs[0];
        int count = strs.length;
        for (int i = 1; i < count; i++) {
            prefix = longestCommonPrefix(prefix, strs[i]);
            if (prefix.length() == 0) {
                break;
            }
        }
        return prefix;
    }

    public String longestCommonPrefix(String str1, String str2) {
        int length = Math.min(str1.length(), str2.length());
        int index = 0;
        while (index < length && str1.charAt(index) == str2.charAt(index)) {
            index++;
        }
        return str1.substring(0, index);
    }
}

数组中重复的数字

    def findRepeatNumber(self, nums: List[int]) -> int:
        hashmap = set()
        for num in nums:
            if num in hashmap:
                return num
            else:
                hashmap.add(num)
        return -1

二叉树的深度

    def maxDepth(self, root: TreeNode) -> int:
        def dfs(root):
            if not root:return 0
            left = dfs(root.left)
            right = dfs(root.right)
            return max(left,right) + 1
        return dfs(root)

两个链表的第一个公共节点

    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        p, q = headA, headB
        while not p == q:
            p = p.next if p else headB
            q = q.next if q else headA
        return p

    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        s = set()
        p, q = headA, headB
        while p:
            s.add(p)
            p = p.next
        while q:
            if q in s:
                return q
            q = q.next
        return None

和为s的两个数字

    def twoSum(self, nums: List[int], target: int) -> List[int]:
        startPoint = 0
        endPoint = len(nums) - 1
        while startPoint < endPoint:
            s = nums[startPoint] + nums[endPoint]
            if s > target:
                endPoint -= 1
            elif s <target:
                startPoint += 1
            elif s == target:
                return [nums[startPoint], nums[endPoint]]

翻转单词顺序

    def reverseWords(self, s: str) -> str:
        s = s.strip()
        s = s.split()
        s = s[::-1]
        return ' '.join(s)

反转链表

    def reverseList(self, head: ListNode) -> ListNode:
        cur, pre = head, None
        while cur:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
        return pre

二叉树的镜像

    def mirrorTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return

        root.left, root.right =  root.right, root.left
        self.mirrorTree(root.left)
        self.mirrorTree(root.right)

        return root

包含min函数的栈

class MinStack:

    def __init__(self):
        self.stack = []

    def push(self, x: int) -> None:
        if not self.stack:
            self.stack.append((x,x))
        else:
            min_num = self.min()
            if x <= self.min():
                self.stack.append((x,x))
            else:
                self.stack.append((x,min_num))

    def pop(self) -> None:
        self.stack.pop(-1)

    def top(self) -> int:
        return self.stack[-1][0]

    def min(self) -> int:
        return self.stack[-1][1]



# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.min()

调整数组顺序使奇数位于偶数前面

    def exchange(self, nums: List[int]) -> List[int]:
        i, j = 0, len(nums) - 1
        while i < j:
            while i < j and nums[i] & 1 == 1: i += 1
            while i < j and nums[j] & 1 == 0: j -= 1
            nums[i], nums[j] = nums[j], nums[i]
        return nums